合併的光學多級式網路之無開關干擾之可重排性

Abstract

一個多級式連接網路的可重排性，是指這個網路的N個輸入到N個輸出，在必要時允許重新連線的情況下，是否可以連接所有N!種可能的輸入輸出排列。在文獻[8]中，Das對於合併的2n – 1階級的多級式連接網路的可重排性，提出了一個漂亮的充分條件，其中n = log2N，Das並且對符合這個充分條件的多級式連接網路提出一個時間複雜度為O(Nn)的排列繞送演算法。然而，上述的可重排性的定義以及Das的結果，皆只適用於電子的多級式連接網路。如今，光學的多級式連接網路，因其高效能，已是許多人的網路選擇。如同文獻[26]中所提，電子的多級式連接網路、與光學的多級式連接網路，其最大的區別是：在電子的多級式連接網路中，兩個訊息傳送之需求，當它們的傳送路徑的邊均不重覆時，可以同時傳送；而在光學的多級式連接網路中，兩個訊息傳送之需求，只有當它們的傳送路徑的點均不重覆時，才能同時傳送（這意味著這兩條傳送路徑不能同時通過同一個開關，也因此不會有開關干擾的問題產生）。這篇論文的目的便是針對光學的多級式連接網路來重做Das的工作。我們對於合併的2n – 2階級、以及2n – 1階級的光學多級式連接網路的無開關干擾之可重排性各提出一個充分條件，對於符合充分條件的光學多級式連接網路提出時間複雜度為O(Nn)的排列繞送演算法。另外，我們也針對baseline網路提出在四回合之內、點均不重覆的排列繞送演算法。

Rearrangeability of a multistage interconnection network (MIN) is that if the MIN can connect its N inputs to its N outputs in all N! possible ways, by rearranging the existing connections if required. In [8], Das formulated an elegant sufficient condition for the rearrangeability of a combined (2n − 1)-stage MIN, where n = logN, and presented an O(NlogN)-time routing algorithm for MINs that satisfy the sufficient condition. However, the above definition of rearrangeability and the results of Das are for electronic MINs. Recently, optical MINs have become a promising network choice for their high performance. As was mentioned in [28], the fundamental difference between an electronic MIN and an optical MIN is that: two routing requests in an electronic MIN can be sent simultaneously if they are link-disjoint, while two routing requests in an optical MIN can be sent simultaneously only when their routing paths are node-disjoint, meaning that these two paths do not pass through the same switching element and therefore there is no crosstalk problem. The purpose of this thesis is to redo the works of Das for optical MINs. In particular, we formulate a sufficient condition for the crosstalk-free rearrangeability of a combined (2n−2)-stage and a combined (2n−1)-stage optical MIN, we propose an O(N logN)-time routing algorithm for optical MINs that satisfy the sufficient condition. In this thesis we also propose an algorithm to realize any permutation in a baseline network with node-disjoint paths in four passes.