臺灣博碩士論文加值系統

近年來由於高速傳輸網路的需求增加，交換器在這高速交換網路之中扮演了一個很重要的角色。在本篇的論文中，我們提出了一種新的交換架構叫做First-In Arbitrary-Out (FIAO)交換器。此FIAO交換器是一結合特殊設計的輸入端佇列與先進先出輸出端佇列的交換器。在此篇論文中我們證明了使用 lowest occupancy output cell first (LOOCF) 作為排程演算法搭配Speedup 2可以使FIAO交換器達到work conserving。 另外根據模擬結果可以得知此FIAO交換器的產能與封包延遲均有非常出色的表現。在不定長度的封包交換的效能表現也是非常出色。

Since the demand for Gigabit or even Terabit communications is increasing, switching system play an important role for high-speed networking. In this thesis, we present a novel switch architecture called First-In Arbitrary-Out (FIAO) switch, which uses input queuing, output queuing, and a maximal matching algorithm, to achieve low latency as well as high throughput. We has proven the FIAO switch running under the speedup factor equal to two times of the input or output line rate is always work conserving. To assure our analysis, several simulation experiments are devised and the simulation results also show that under uniform traffic, the FIAO switch performance is similar to output queuing switches. Even running under burst traffic patterns, the FIAO switch still performs quite outstanding.

1. Introduction 4
2. A Classification of Switching Architectures 6
2.1 General switch model 6
2.2 Terms and definitions 7
2.3 Output Queuing Switch 9
2.4 Input Queuing Switch 10
2.5 VOQ switch 12
2.6 Combined Input and Output Queuing switch 14
3. The Firs-In Arbitrary-Out Switch Architecture 16
4. Performance Analysis of the FIAO Switch 21
4.1 The necessity of the speedup strategy 21
4.2 The work conserving property of FIAO switches 23
5. Simulation Results of FIAO Switches 30
5.1 Simulation model 30
5.2 Simulation results 34
5.2.1 The performance of a FIAO switch under speedup 1 34
5.2.2 The performance of a FIAO switch under speedup 2 36
5.2.3 The performance of a FIAO switch under bursty traffic 37
5.2.4 The maximum size of AOZ 38
6. Conclusions 39
Reference: 40
Appendix 43

[1] M. Karol, M. Hluchyj, and S. Morgan, “Input versus output queueing on a space division switch,” IEEE Trans. Commun., vol. 35, pp. 1347–1356, 1987.
[2] Yuji OIE, Masayuki MURATA, Koji KUBOTA, and Hideo MIYAHARA, “Effect of Speedup in Non-blocking Packet Switch,” 1989, IEEE.
[3] Hopcroft, J.E., Karp, R.M.,” An n5/2 algorithm for maximum matching in bipartite graphs” Society for Industrial and Applied Mathematics , J.Comput.2(1973),pp225-231.
[4] Anderson T., S. Owicki, J. Saxe, and C.Thacker : “High Speed Switch Scheduling for Local Area Networks” Proc. Fifth Interna - tional Conference on Architectural Support for Programming Languages and Operating Systems Oct. 1992 ,pp98-110.
[5] Nick McKeowen, “The i-SLIP Scheduling Algorithm for Input-Queued Switches”, IEEE/ACM Transaction on Networking, Vol7, No.2,April,1999.
[6] Shang-Tse Chuang, Ashush Goel, Nick McKeown, and Balaji Prabhakar, “Matching Output Queuing with a Combined Inout/Output-Queued Switch,” IEEE JSAC, VOL.17, NO. 6, June 1999.
[7] Pattabhiraman Krishna, Naimish S. Patel, Anna Charny, and Robert J.Simcoe, “On the Speedup Required for Work-Conserving Croosbar Switch,” IEEE JSAC, VOL.17, NO. 6, June 1999.
[8] Kevin Thompson, Gregory J.Miller, and Rick Wilder ,”Wide-Area Internet Traffic Patterns and Characteristic” IEEE Network, Nov/Dec 1997.
[9] Cyriel Minkenberg, Ton Engbersen , Michel Colmant* ,“A Robust Switch Architecture For Bursty Traffic,” IBM Research , Zurich Research Laboratory ,IEEE, pp. 207-214.
[10] Dimitrios N.Serpanos, Manolis G.H. Katenenis and Emmanuel Spyridakis, “ATLAS I: Building Block for ATM Neyworks with Credit-based Flow Control,” Institute of Computer Science Foundation for Research and Technology – Hellas Science and Technology Park of Crete.
[11] H. Kuwahara, N. Endo, M. Ogino, and T. Kozaki, “A shared buffer memory switch for ATM exchange,” in Proc. ICC’89, vol. 1, Boston, MA, June 1989, pp. 118–122.
[12] A. P. J. Engbersen ,” Prizma switch technology,” IBM J. RES. & DEV. VOL. 47 NO. 2/3 MARCH/MAY 2003.
[13] Georgios Kornaros, Dionisios Pnevmatikatos, Panagiota Vatsolaki, Georgios Kalokerinos, Chara Xanthaki, Dimitrios Mavroidis, Dimitrios Serpanos, and Manolis Katevenis ,“ATLAS I: IMPLEMENTING A SINGLE-CHIP ATM SWITCH WITH BACKPRESSURE,”FORTH and the University of Crete, IEEE, 1999.
[14] A. Pattavina, “Nonblocking architecture for ATM switching,” IEEE Commun., vol. 31, pp. 38–48, Feb. 1993.
[15] Dionisios Pnevmatikatos and George Kornaros, “ATLAS II: Optimizing a 10Gbps SingleChip ATM Switch,” Institute of Computer Science (ICS) Foundation for Research & Technology – Hellas (FORTH), 12th Annual IEEE 1999 International ASIC/SOC Conference, Washington DC, USA, 1518 September 1999
[16] Yihan Li; Panwar, S.; Chao, H.J. , “On the performance of a dual round-robin switch” INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE Volume 3, 22-26 April 2001 Page(s):1688 - 1697 vol.3
[17] M. Karol, M. Hluchyj, and S. Morgan, “Input versus output queueing on a space division switch,” IEEE Trans. Commun., vol. 35, pp. 1347–1356, 1987.
[18] Ronald P, Luijten, Ton Engbersen and Cyriel Minkenberg,”Share memory switching + Virtual output queue,” IBM Research, Zurich Research Laboratory,IEEE,2001
[19] Pattavina. A. “Multichannel bandwidth allocation in a broadband packet switch” IEEE JSAC. Vol. Vol 6. NO.9 , Dec 1988, PP1489-99
[20] Li S.Q., “Performance of trunk grouping in packet switch design” Proc IEEE Infocom’91,Miami, FL., p688-693 ,Apr 1