高速網路交換機之設計與實作

The Design and Implementation of High-speed Network Switches

許育豪(Yu-Hao Hsu)

指導教授 ： 張正尚 ； 邱瀞德 ； 吳仁銘 ； 徐碩鴻

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

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

摘要

由於近來光纖技術的發展，使得建立一個高速的網路交換機更顯得重要。現今市售的交換機都是建構在共享記憶體的基礎上，記憶體的存取速度便成了交換機系統的瓶頸，本篇論文乃設計與實現兩種突破性的交換機，以期能應用於未來光纖普及的高速網路。 第一種架構乃是基於本團隊所提出的負載平衡式布可夫－范紐曼交換機(Load Balanced Birkhoff-von Neumann Switch)。理論上已證明此架構可達效能百分百（100% throughput）的傳輸品質。此前瞻性架構的好處是來自於架構本身的可擴充性(scalability)，只要我們將4x4 埠的交換機實現，便能以此為單元建構出64x64、512x512 或更高埠的骨幹級交換器。本論文除了介紹核心的交換機數位電路，亦包含與外界溝通的類比SERDES (serializer-deserializer)介面，並介紹如何整合成混合性的系統晶片。最後並介紹此架構的第二代高速交換機晶片，說明如何將此交換機架構直接用射頻電路實現。 我們更進一步提出第二種架構：結合輸入及交叉點佇列交換機(Combinedinput and crosspoint queueing Switch)，提出使用動態方框演算法以期達到百分百效能下對數延遲（O(logN) delay）的可能性並且提供其理論驗證。此外，此種結合輸入及交叉點佇列交換機在單一傳送交通下每個交叉點只需要兩個封包大小的佇列。不同於輸入佇列交換機，動態方框演算法在多重傳送的交通設定下依舊可以達到效能百分百，而僅需增加每個交叉點的佇列大小。

關鍵字

網路交換機 ； 效能百分百 ； 可擴充性

並列摘要

There is an urgent need to built high speed switches that scale with the transmission speed of fiber optics. Most switches in the current market are based on the so-called shared memory switch architecture. As the speed of fiber optics advances, the memory access speed becomes a bottleneck.
A breakthrough in high-speed switch is the load balanced Birkhoff-von Neumann switch. It is proposed to resolve the memory access conflict and yield 100% throughput with high scalability. We implement the digital core of the load balanced switch in first, and then develop the analog SERDES interface to reduce the switch IC pin counts. The mixed-signal design of the switch system is then integrated
successfully. In the next generation, we also implement the switch IC directly in RF domain without the use of SERDES interfaces to achieve low propagation delay and high scalability.
We also propose the Combined Input and Crosspoint Queueing (CICQ) switch with the dynamic frame sizing algorithm for the possibility of O(logN) delay. It is formally shown that such the CICQ switch indeed achieves 100% throughput for certain Poisson-like traffic models. Moreover, such a CICQ switch only requires a two-cell buffer at each crosspoint when there is only unicast traffic. Unlike input-buffered switches, the dynamic frame sizing algorithm also achieves 100% throughput in the setting of multicast traffic. This is done at the cost of increasing the buffer size at each crosspoint.

並列關鍵字

Network Switch ； 100% Throughput ； Scability

參考文獻

[1]. C. S. Chang, D. S. Lee and Y. S. Jou, “Load balanced Birkhoff-von Neumann switch, part I: one-stage buffering,” Computer Communications, Vol. 25, pp. 611-622, 2002.

[2]. C. S. Chang, D. S. Lee and C. M. Lien, “Load balanced Birkhoff-von Neumann switch, part II: Multi-stage buffering,” Computer Communications, Vol. 25, pp. 623-634, 2002.

[3]. Keslassy, I., Shang-Tse Chuang; McKeown, N., “A loadbalanced switch with arbitrary number of line cards,” Infocom 2004, pp. 2007-1026, March 2004.

[4]. Widmer, A.X&Franaszek, P.A., “A DC-Balanced, Partitioned-Block, 8/10B Transmission Code,” IBM J. Res. Develop., Vol. 27, No. 5. September 1983.

[6]. Yorozu, S.; Hashimoto, Y.; Kameda, Y.; Terai, H.; Fujimaki, A.; Yoshikawa, N., ” A 40 GHz clock 160 Gb/s 4/spl times/4 switch circuit using single flux quantum technology for high-speed packet switching systems,” High Performance Switching and Routing, 2004. HPSR. 2004 Workshop on 2004 pp.20-23