三級式克勞斯網路與多重對數網路的廣義不阻塞

Abstract

克勞斯(Clos)在1953年首先提出了「三級式網路」，這也是最基本的多級式交換網路之一；假設 n 是一個輸入交換器的進線個數，克勞斯證明了這樣的網路只需要用到 2n-1 個中繼交換器，即能使得此網路達到絕對不阻塞。在1965年，班尼斯 Benes 舉了一個例子說明，使用「優先選最忙的中繼交換器」的策略，真的可以降低中繼交換器的使用數目，而依然還是能讓此網路不阻塞。不過，這個例子也是至今唯一個三級式克勞斯網路是廣義不阻塞，而不是絕對不阻塞的例子。 在這篇論文裡，我們證明了文獻中所提到的一些傳遞策略：不用的最後(STU)、最忙錄的優先(P)、編號小的優先(MI)、從上次的編號開始(CS)及從下一個編號開始(CD)，在這些策略之下，要達到不阻塞所需要的中繼交換器個數與要達到絕對不阻塞所需要的一樣。而我們也將這個結果推廣到不對稱的情況，甚至我們還在多重對數網路上也得到了同樣的結果。最後，我們也將此結果推廣到了同類型的網路上。

The 3-stage network was first proposed by Clos and is one of the most basic multistage interconnecting network. Clos (1953) showed that the number of middle crossbar required for strictly nonblocking is 2n-1, where n is the number of inlets of an input crossbar. Benes (1965) constructed an example to show that using packing routing strategy can make the number of middle crossbar required lower. This has remained the only example of wide-sense non-blocking 3-stage Clos network which is not strictly nonblocking.

In this thesis, we showed that the number of middle rossbar required for wide-sense nonblocking under several routing strategies: save the unused, packing, minimum index, cyclic static, and cyclic dynamic, which has been studied in the literature is the same as required for strictly nonblocking and extended them to asymmetric $3$-stage Clos network. In particular, we prove the same conclusion for the multi-log_dN network and extend to a general class of network.