Routability and Stability of Switching Networks and Their Applications in Load-Balanced Switches

交換網路之繞通性與穩定性之研究及其於負載平衡交換機之應用

連卿閔(Ching-Min Lien)

指導教授 ： 張正尚

國立清華大學/電機資訊學院/通訊工程研究所/博士(2011年)

https://doi.org/10.6843/NTHU.2011.00451

摘要

這篇論文可區分為兩個部分。第一部分主要是討論特定多級互連網路（multistage interconnection network）的繞通性（routability）以及條件式非阻通性（conditional nonblocking property）。和目前存在於文獻中的架構相比，負載平衡交換機已經被證實為是一種更具有可行性的高速交換機架構。而在這篇論文中，我們提出了兩種多級互連網路，分別是漩渦網路（twister network）及退化性榕樹網路（degenerated banyan network），並探討如何利用這兩種多級互連網路（及其各自的條件式非阻通性）來達成目的：只用一組固定的硬體架構，便能實現任意輸入輸出埠數目的負載平衡交換機。其中，在光佇列（optical queueing）理論方面的進展，啟發了我們對於漩渦網路的設計；另一方面，退化性榕樹網路則是傳統榕樹網路的一種變形，可透過以特定方式保留傳統榕樹網路的一半輸入輸出埠所獲得。對這兩種多級互連網路，我們提出了一種對兩者通用的線卡更新規則。此規則能夠保證在新增或移除線卡時都不必更動（與此變動無關的）其他既有線卡，同時保證封包在這兩種架構中進行交換時，不僅具有自我繞送（self-routing）的特性，而且所有的繞送路徑都不會在交換網路中共用任何連結。

接著，我們討論了將 fat-tree 網路拓樸用以實現負載平衡交換機時會遭遇到的問題：所需的連結頻寬會由底部向上層成指數成長，同時導致位於上層的交換節點必須以具備大量輸入輸出埠的非阻通性交換機加以實現。在論文中，我們證明了位元倒置（bit-reverse）排列及其所有的循環位移（circular shift）排列不僅可作為負載平衡交換機的一組交換配對（connection pattern），同時由於這些排列均滿足均勻映射性（uniform mapping property），當我們採用 fat-tree 拓樸作為實現負載平衡交換機的硬體架構時，便能夠保證實現其中任一排列所需連結頻寬都只需要理論上的最低下限即可。此外，我們找到了一組特定的類榕樹網路（banyan-type network）可以進一步降低利用 fat-tree 拓樸來實現負載平衡交換機時的硬體複雜度，並同時保留了封包在類榕樹網路中交換時所應具備的自我繞送特性。

論文的第二部分，我們討論的是網路的穩定性。藉由網路微積分（network calculus）以及大偏離法則（large deviation principle）的幫助，我們首先提出針對有線網路環境的動態頁框演算法（dynamic frame sizing algorithm）並證明該演算法具有下列特性：所有網路內部節點暫存器的尺寸大小均只需要兩個封包便足夠，同時保證達到百分之百的網路效能（100% throughput），而這樣的保證並不需要任何預先關於外界輸入的資訊。另外，在動態頁框演算法中，整個網路的中央仲裁者（central arbitrator）只在每個頁框的開頭收集並傳送資訊給所有連結。而當所有連結接收到中央仲裁者所廣播的訊息之後，在每個時槽（time slot），所有的內部連結都可以自行決定在該時槽內所要傳送的封包。

接下來，我們將原本針對有線網路所發展出來的動態頁框演算法推廣至無線網路環境。在無線網路中，不同連結傳輸時可能會對彼此造成干擾，以致於同一時間只有某些特定的連結集合能夠同時傳輸信號，而在論文中我們將這樣的集合以向量的形式表示，稱為配置向量（configuration vector）。在這樣的限制下，我們發展出針對無線網路的動態頁框演算法。每個頁框的開始，中央仲裁者會藉由解決一個最佳化問題而找到該頁框應有的尺寸大小。而在該頁框的大小決定之後，封包排程則是透過階層式平穩排程（hierarchical smooth schedule）所達成：上層是對配置向量的排程，下層則是每條連結各自對流經該連結的群播資料流（multicast traffic flow）做排程。最後，我們同樣證明了，針對無線網路環境的動態頁框演算法仍然能夠保證網路內部各節點暫存均有個有限的上限值，同時在伯努利（Bernoulli）輸入的假設之下，能夠確保網路效能達到百分之百。

關鍵字

負載平衡交換機 ； 繞通性 ； 穩定性 ； 多級互連網路 ； 均勻映射性 ； 動態頁框演算法 ； 排程

並列摘要

This thesis consists of two parts. The first part is devoted to the routability andconditional nonblocking properties of families of multistage interconnection networks(MINs). Moreover, as the load-balanced switches are much more scalable than other existing switching architecture in the literature, we show how these conditional nonblocking properties can be used to help implement load-balanced switches. First, to construct a universal load-balanced switch for an arbitrary number of linecards, we propose two special families of MINs, twister networks and degenerated banyan networks: the first one is inspired by the recent development of optical queueing theory, and the second one can be obtained by using only halves of input and output ports of classical banyan networks. Then, we depict a placement rule for adding a new linecard to both of these families of MINs so that all the existing linecards need not be changed, while the packets can still be self-routed and the routing paths are guaranteed to be link-disjoint.

We also consider the problem of implementation of load-balanced switches with fattree networks, where the link capacity has to be increased exponentially from the bottom of the tree to the root, and each node at higher level has to be thus constructed as a nonblocking switch with a large number of input/output lines. We show that the bitreverse
permutation and all its variants obtained by circular shifts, which all satisfy the uniform mapping property, can be used as a set of connection patterns of a load-balanced switch while the capacity of each link in the fat-tree is specified by the lower bound. Moreover, we found that a banyan-type network can be used to further reduce the implementation complexity of a fat-tree when used as a load-balanced switch, where the self-routing property is preserved.

In the second part of this thesis, we consider the stability of wired networks. By using the network calculus and the large deviation principle, we propose the Dynamic Frame Sizing (DFS) algorithm that not only needs only a buffer of size two at each internal node but also guarantees 100% throughput even if we have no prior information about arrival processes. Moreover, by using the DFS algorithm, each internal link makes its own decision independently at each time slot, whereas the central arbitrator only collects and broadcasts information once a frame.

We then extend our result for wired networks to wireless networks. In wireless networks, the transmission of each link might interfere with each other and thus only a certain set of links can transmit at the same time. The DFS algorithm for wireless networks also does not have a fixed frame size. An optimization problem needs to be solved at the beginning of each frame to determine the frame size. Once the frame size is determined, a hierarchical smooth schedule is devised to determine both the schedule for configuration vectors and the schedule for multicast traffic flows in each link. Under the assumption of Bernoulli arrival processes with admissible rates, we show that the number of packets of each multicast traffic flow inside the wireless network is bounded above by a constant
and thus one only requires to implement a finite internal buffer in each link in such a wireless network.

並列關鍵字

Load-Balanced Switch ； Routability ； Stability ； Multistage Interconnection Network ； Uniform Mapping Property ； Dynamic Frame Sizing Algorithm ； Scheduling

參考文獻

[1] M. Al-Fares, A. Loukissas, and A. Vahdat. A scalable, commodity data center network architecture. In ACM SIGCOMM 2008, Seattle, USA, August 2008.

[2] B. W. Arden and H. Lee. Analysis of chordal ring network. IEEE Transactions onComputers, C-30:291–295, 1981.

[5] C. S. Chang. Performance Guarantees in Communication Networks. London: Springer-Verlag, 2000.

[6] C. S. Chang, W. J. Chen, and H. Y. Huang. Birkhoff-von Neumann input buffered crossbar switches. In IEEE INFOCOM 2000, Tel Aviv, Israel, March 2000.

[7] C. S. Chang, J. Cheng, and D. S. Lee. SDL constructions of FIFO, LIFO and absolute contractors. In IEEE INFOCOM 2009, Rio de Janeiro, Brazil, April 2009.