臺灣博碩士論文加值系統

在本論文中提出了一個含有虛擬輸出佇列的高速對稱分時多工交換機系統本交換機系統主要為實現負載平衡Birkhoff-von Neumann交換機架構。在將此架構中的兩級交換機電路進一步折疊成同一個電路以減少50%的硬體複雜度之後，將其以晶片實現於0.13μm CMOS製程。這個交換機原型晶片大小為1.38 mm × 1.08 mm ，其中包含一個全客製化的(full-customized)的4×4交換機核心、一個數位的交換機路徑選擇器和一組電流型輸入/輸出介面。其中，數位的交換機路徑選擇器會產生特殊的路徑選擇訊號給每個4×4交換機核心，以期達到以多個4×4交換機單位來組成一個N×N (N為4的冪次方)的大型交換機系統。與傳統的數位方法相比，全客製化的(full-custom)設計增進了大約1.43倍的速度，並且節省了86%的功耗以及80%的晶片面積。模擬結果顯示4×4交換機核心可達到40Gbps的資料處理速度（每個通道10Gbps，與OC-192的標準一樣）並且只消耗134mW的功耗。一個每秒幾兆等級處理速度的交換機可以以串接此交換機核心單元的方法組建。此外，為了提供一個速度夠快且有足夠儲存空間的虛擬輸出佇列給如此高速的交換機系統，本論文提出了一個大並且快的虛擬輸出佇列架構以達到9.6Gbps的資料速率和2.048Gb的記憶體容量。這個虛擬輸出佇列結合了封包暫存器排程機制和以先進先出法(first-in-first-out)處理的記憶體控制器來有效率的控制四組同步動態隨機存儲記憶體晶片以儲存、轉送交換機吞吐的封包。

In this thesis, we propose a high speed symmetric TDM switch system with VOQ. The STDM switch applies the architecture of the load balanced Birkhoff-von Neumann switch proposed in [10]. We fold this two-stage switch to reduce 50% hardware complexity, and then implement a 1.38 mm × 1.08 mm prototype switch fabric IC, including a full-customized 4×4 switch core, a digital switch pattern generator, and a set of CML I/O interfaces in 0.13μm CMOS technology. The digital pattern generator generates reconfigurable connection patterns for the 4×4 switch core to easily scale up to an N×N switch (N is power of 4). The full-custom design approximately improves 1.43 times of speed while saving 86% of the power and 80% of the area, compared with the traditional digital approach for switch IC with SERDES interfaces. Our simulation results show that a 4×4 switch fabric IC can achieve 40Gbps switching rate (10Gbps for each channel as the OC-192 standard) and consumes only about 134mW power. A terabit switch fabric can then be constructed by cascading the designed switch ICs with low power consumption. Furthermore, to provide a large capacity and high throughput VOQ for such a high speed STDM switch system, we introduce an ultra fast super capacity virtual VOQ architecture that supports data rate up to 9.6Gbps per channel with 2.048 Gb storage. This ultra fast super capacity virtual VOQ includes a first-in-first-out memory controller design with buffer manager functions to coordinates the packet flows of the switch fabric and four off-chip SDRAM chips efficiently and coherently.

Contents
List of Figures iii List of Tables vi
1 Introduction
1.1 The High Speed Data Transfer ……………………………………… 1
1.2 Motivation …………………………………………………………… 2
1.3 Innovation & Contribution …………………………………………… 2
1.4 Thesis Organization ………………………………………………… 5
2 The Overview of Switch Fabric System
2.1 History of Switch Fabrics …………………………………………… 6
2.2 Traditional Packet Switches …………………………………………… 8
2.2.1 Output-buffered Switches ....…………………………………… 9
2.2.2 Input-buffered Switches ..…………………………………… 10
2.2.3 Birkhoff-von Neuman Switches ………………………………… 12
2.3 Load Balanced Birkhoff-von Neuman Switches ……………………… 13
2.4 Line Card and Virtual Output Queue ………………………………… 16
3 The Architecture of the Switch Fabric – the Load Balanced Birkhoff-von Neuman Switch
3.1 Symmetric TDM Connection Patterns in Load Balanced Birkhoff-von
Neuman Switch …………………………………………………….. 19
3.2 The Cascade Construction of an N×N Symmetric TDM Switch ……… 21
3.3 An 4×4 Symmetric TDM Switch ……………………………………… 23
3.4 The 4×4 Symmetric TDM Switch IC ………………………………… 25
4 The Circuit of the 4×4 Symmetric TDM Switch IC
4.1 Previous Work ……………………………………………………… 27
ii
4.2 Architecture ……………………………………………………… 28
4.3 4×4 STDM Switch Circuit Components …………………………… 29
4.3.1 The Switch Pattern Generator ………………………………… 29
4.3.2 The CML Multiplexer in a 2×2 Switch Basic Block …………… 32
4.3.3 The CML D-flip-flop in a 2×2 Switch Basic Block …………… 34
4.3.4 The CML Buffer …………………………………………… 38
4.4 Layout Consideration ………………………………………………… 40
5 Simulation Results of the Switch IC
5.1 Post-layout Simulations ………………………………………………… 42
5.2 Performance Comparison …………………………………………… 50
6 Virtual Output Queue – FIFO Memory Controller
6.1 Overview …………………………………………………………… 51
6.2 System Architecture ………………………………………………… 52
6.3 The FIFO Memory Controller Circuit ………………………………… 65
6.4 Simulations …………………………………………………………… 72
7 Conclusion & Future Work
7.1 Conclusion of the STDM Switch IC ………………………………… 77
7.2 Conclusion of the FIFO Memory Controller …………………………… 78
7.3 Final Conclusion & Future Work ……………………………………… 78
References 80

References
[1] M. J. Karol, M. G. Hluchyj, and S. P. Morgan, “Input versus output queueing on a space-division packet switch,” IEEE Transactions on Communications, Vol. 35, pp. 1347-1356, Dec 1987
[2] T. Anderson, S. Owicki, J. Saxe, and C. Thacker, “High-speed switch scheduling for local-area networks,” ACM Transactions on Computer Systems, Vol. 11, pp. 319-352, 1993.
[3] Y. Tamir, and H.C. Chi, “Symmetric crossbar arbiters for VLSI communication switches,” IEEE Transactions on Parallel and Distributed Systems, Vol. 4, pp. 13-27, 1993.
[4] N. McKeown, “Scheduling algorithms for input-queued cell switches,” PhD Thesis. University of California at Berkeley, 1995.
[5] N. McKeown, V. Anantharam, and J. Walrand, “Achieving 100% throughput in an input-queued switch,” IEEE Transactions on Communications, Vol. 47, pp. 1260-1267, 1999.
[6] A. Mekkittikul, and N. McKeown, “A practical scheduling algorithm to achieve 100% throughput in input-queued switches,” Proceedings of IEEE INFOCOM, Vol. 2, pp. 792-799, 1998.
[7] J. Dai, and B. Prabhakar, “The throughput of data switches with and without speedup” Proceedings of IEEE INFOCOM, Vol. 2, pp. 556-564, 2000.
[8] Y. Li, S. Panwar, and H.J. Chao, “On the performance of a dual round-robin switch,” Proceedings of IEEE INFOCOM, Vol. 3, pp. 1688-1697, 2001.
81
[9] C. S. Chang, D. S. Lee, and Y. J. Shih, “Mailbox switch: a scalable two-stage switch architecture for conflict resolution of ordered packets,” Proceedings of IEEE INFOCOM, Vol. 3, pp. 1995-2006, 2004.
[10] C. S. Chang, D. S. Lee and Y. S. Jou, “Load balanced Birkhoff-von Neumann switches, part I: one-stage buffering,” Computer Communications, Vol. 25, pp. 611-622, 2002.
[11] Y. Shen, Shi Jiang, Panwar S.S., and J.H. Chao, “Byte-focal: a practical load balanced switch,” IEEE High Performance Switching and Routing, pp. 6-12, 2005.
[12] J. J. Jaramillo, F. Milan, and R. Srikant, “Padded frames: a novel algorithm for stable scheduling in load-balanced switches,” Proceedings of CISS, 2006.
[13] I. Keslassy, and N. McKeown, “Maintaining packet order in two-stage switches,” Proceedings of IEEE INFOCOM, Vol. 2, pp. 1032-1041, 2002.
[14] I. Keslassy, S. T. Chuang, K. Yu, D. Miller, M. Horowitz, O. Solgaard, and N. McKeown, “Scaling internet routers using Optics,” Proceedings of ACM SIGCOMM, 2003.
[15] C. L. Yu, C. S. Chang, and D. S. Lee, “CR switch: a load-balanced switch with contention and reservation,” accepted by IEEE INFOCOM, 2007.
[16] C.-S. Chang, W.-J. Chen and H.-Y. Huang, “On service guarantees for input buffered crossbar switches: a capacity decomposition approach by Birkhoff and von Neumann,” IEEE IWQos’99, pp. 79-86, London, U.K., 1999
[17] G. Birkhoff, “Tres observaciones sobre el algebra lineal,” Univ. Nac. Tucumάn Rev. Ser. A, Vol. 5, pp. 147-151, 1946.
[18] J. von Neumann, “A certain zero-sum two-person game equivalent to the optimal assignment problem,” Contributions to the Theory of Games, Vol. 2, pp. 5-12, Princeton University Press, Princeton, New Jersey, 1953.
82
[19] B. Razavi, “Prospects of CMOS technology for high-speed optical communication circuits,” IEEE J. Solid-State Circuits, vol. 37, pp. 1135–1145, Sept. 2002.
[20] H. Wohlmuth, D. Kehrer, M. Tiebout; H. Knapp, M. Wurrer, and W. Simhiirger, “High speed CMOS circuits up to 40Gb/s and 50 GHz,” IEEE GaAs IC, pp. 31-34, San Diego, USA, Nov. 2003.
[21] H.-D. Wohlmuth and D. Kehrer, “A low power 13-Gb/s 27 – 1 pseudo random bit sequence generator IC in 120 nm bulk CMOS,” in Symposium on Integrated Circuits and Systems Design. Pernambuco, Brasil: IEEE, September 2004, pp. 233–236.
[22] F. Weiss, H.-D Wohlmuth, D. Kehrer and A. L. Scholtz, “A 24-Gb/s 27 – 1 pseudo random bit sequence generator IC in 0.13 um bulk CMOS,” Solid-State Circuits Conference, 2006. ESSCIRC 2006. Proceedings of the 32nd European Sept. 2006
[23] P. Heydari and R. Mohanavelu, “Design of ultrahigh-speed low-voltage CMOS CML buffers and latches,” IEEE Trans. on Very Large Scale Integr. (VLSI) Syst., vol. 12, no. 10, pp. 1081–1093, Oct. 2004.
[24] T. Otsuji, M. Yoneyama, K. Murata, and E. Sano, “A super-dynamic flip–flop circuit for broadband applications up to 24 Gbit/s utilizing production-level 0.2-um GaAs MESFETS,” in IEEE Journal of Solid-state Circuits, Vol. 32, No. 9, September 1997.
[25] M. G. Chen, “A half-tone frequency detector and digital circuit techniques for high-speed clock/data recovery,” Ph.D. dissertation, Univ. Southern CA, Los Angeles, CA, Dec. 1998.
[26] C. T. Chiu, J. M. Wu, S. H. Hsu, M. S. Kao, C. H. Jen, and Y. S. Hsu, “A 10 Gb/s wide-Band current-mode logic I/O interface for high-speed interconnect in
83
0.18μm CMOS technology,” IEEE International SOC Conference, pp. 257-260, 2005.
[27] Ping-Lin Yang, “The high speed quarter-rate 16/20:1 parallel-to-serial multiplexer with the area-saving RF devices,” Master dissertation, National Tsing Hua Univ., Hsin-chu, Taiwan, ROC, Jun. 2007.
[28] Ching-Te Chiu; Yu-Hao Hsu; Min-Sheng Kao; Hou-Cheng Tzeng; Ming-Chang Du; Ping-Ling Yang; Ming-Hao Lu; Fanta Chen; Hung-Yu Lin; Jen-Ming Wu; Shuo-Hung Hsu; Yar-Sun Hsu, “A scalable load balanced birkhoff-von Neumann symmetric TDM switch IC for high-speed networking applications,” IEEE International Symposium on Circuits and Systems, pp. 2754-2757, May 2007.
[29] Yu-Hao Hsu,; Ming-Hao Lu,; Ping-Lin Yang,; Fan-Ta Chen,; You-Hung Li,; Min-Sheng Kao,; Chih-Hsing Lin,; Ching-Te Chiu,; Jen-Ming Wu,; Shuo-Hung Hsu,; YarSun Hsu, “A 28Gbps 4×4 switch with low jitter SerDes using area-saving RF model in 0.13μm CMOS technology,” IEEE International Symposium on Circuits and Systems, pp. 3086-3089, May 2008.
[30] John L. Hennessy, David A. Patterson, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers, CA, 2003
[31] Micron MT47H32M datasheet, Micron, 2004. Available from http://www.micron.com/ddr2.