在本篇論文中，我們分別對高速的電子及光學交換系統，進行排程演算法及效能評估之研究。在電子交換系統部分，我們提出一個全新的交換機架構，稱為三維虛擬輸出佇列交換機 (3D-VOQ)，藉由細胞排程演算法能夠避免交換機傳送封包時的內部競爭。此三維虛擬輸出佇列交換機在內部結構不需要加速的情形下，且不論任何網路流量和交換機的大小，皆能夠完全的仿效 (emulate) 輸出佇列交換機。 首先，說明N × N大小的三維虛擬輸出佇列交換機，能夠完全避免輸入端/輸出端競爭 (Input/Output Contention)，且採用虛擬輸出佇列技術 (Virtual Output Queue, VOQ) 消除線頭阻擋問題 (Head-of-Line blocking problem)，使得三維虛擬輸出佇列架構成為內部傳送無競爭的交換機。 接著提出最小細胞離開時效值細胞排程演算法 (Smallest Time-to-leave Cell First algorithm, STCF algorithm)，此演算法有多對多的配對能力，此外也證明三維虛擬輸出佇列架構採用最小細胞離開時效值細胞排程演算法能夠完全仿效輸出佇列交換機，最後分析及模擬數據以評估三維虛擬輸出佇列架構的效能。
在光學交換系統部分，研究在克勞斯網路交換器以門襤為基礎的排程演算法(t-MAC)。在研究中使用一個中間為光學交換機體來傳送高速光訊號，而在輸入輸出兩端為電子控制裝置。我們在克勞斯網路提出配對演算法來解決排程問題，這個排程演算法整合直達傳送、變動門襤調整及搶奪排程。在效益評估部分，t-MAC排程演算法使用了爆發及非平衡流量模型下，交換延遲能有顯著的降低，比較Chao所提出c-MAC在有接近36 %到45%的改善。

This work studies scheduling algorithms and evaluates the performance of high-speed electronic and photonic switching systems. A novel architecture for three-dimensional Virtual Output Queue (3D-VOQ) switches is proposed for use in electronic switching systems, in connection with a scheduling algorithm to improve the competitive transfer of service. This 3D-VOQ switch, which exactly emulates an output-queued switch with a broad class of service scheduling algorithms, requires no speedup, independently of its incoming traffic pattern and switch size. First, an N×N 3D-VOQ switch is proposed. In this contention-free architecture, the head-of-line problems are eliminated using a few virtual output queues (VOQ) from input ports and the output sides were arranged using sufficient separate queues. Next, a Small Time-to-leave Cell First (STCF) algorithm is proposed to generate a stable many-to-many assignment. The proposed 3D-VOQ switch is demonstrated to be able to mimic an exact OQ switch. Finally, analysis and simulation confirm the performance of 3D-VOQ and its satisfying high/low QoS requirements.
The photonic switching system applies a threshold-based matching algorithm for Clos (t-MAC) network switches. The studied Clos network uses a central photonic switch fabric for transporting high-speed optical signals and electronic controllers at the input and output ports. The proposed matching algorithm can be used to solve the scheduling problems associated with the Clos network. The matching algorithm incorporates cut-through transmission, variable-threshold adjustment and preemptive scheduling. The performance is evaluated using the bursty and unbalanced traffic model, and simulation results obtained by t-MAC are presented. The results indicate that the proposed algorithm significantly reduces switching latency by approximately 45 to 36 % below that of Chao’s c-MAC.

Contents
Acknowledgements--------------------------I
摘要--------------------------------------II
Abstract---------------------------------III
Contents-----------------------------------V
Figure Contents-------------------------VIII
Table Contents----------------------------XI
Chapter 1 Introduction--------------------1
1.1 Motivation-----------------------------1
1.2 Switch Architecture--------------------2
1.3 Organization of Thesis-----------------5
Chapter 2 Background and Related Research-6
2.1 The Matching on a Bipartite Graph------7
2.1.1 Maximum Matching---------------------7
2.1.2 Maximum Weight Matching--------------9
2.1.3 Parallel Iterative Matching---------10
2.1.4 Maximal Matching--------------------11
2.1.5 Stable Matching---------------------12
2.1.6 Summary-----------------------------15
2.2 Relative Algorithm for Emulating Output-Queueing--16
2.2.1 Most Urgent Cell First Algorithm (MUCFA)--------17
2.2.2 Comparison of MUFCA, CCF and JPM----------------19

Chapter 3 System Architectures-----------------------21
3.1 System Architecture of 3D-VOQ---------------------21
3.2 System Designed of 3D-VOQ-------------------------23
3.2.1 Input Port--------------------------------------24
3.2.2 Output Port-------------------------------------25
3.2.3 Internal Line of Switching Fabric---------------26
3.3 System Architecture of Clos MAC-------------------29
3.3.1 Structure of t-MAC Packet scheduler-------------31
3.3.2 Illustration of t-MAC Matching------------------34
3.4 t-MAC System--------------------------------------36
3.4.1 System Architecture and Specification-----------36
Chapter 4 Scheduling Algorithms----------------------40
4.1 Parallel Polled Cell Scheduling Algorithm---------40
4.2 Smallest Time-to-leave Cell First (STCF) algorithm-45
4.3 Proof of Emulation OQ Switch----------------------50
4.4 Threshold-based Matching Algorithm for Clos-------55
4.4.1 Threshold-based port-to-port matching-----------56
4.4.2 Concurrent Routing Assignment-------------------57
Chapter 5 Performance Analysis and Evaluation--------60
5.1 Analysis of 3D-VOQ Delay--------------------------60
5.2 Traffic Models------------------------------------63
5.2.1 Bernoulli traffic and on-off traffic------------63
5.2.2 Polarized traffic model-------------------------65
5.3 Performance Evaluation of 3D-VOQ------------------67
5.3.1 Evaluating Performance of OQ, CIOQ and 3D-VOQ switches--67
5.3.2 Bursty traffic influence------------------------78
5.3.3 Effect of Switch Size on 3D-VOQ-----------------80
5.3.4 Estimating Performance with Different Output Queues-----81
5.3.5 3D-VOQ Emulate OQ Switch by Simulation----------85
5.3.6 Comparison of efficiencies of 3D-VOQ and PPVOQ switches-86
5.4 Evaluating Performance of t-MAC Clos Switch-------87
5.4.1 Comparison of Throughputs and Delays------------88
5.4.2 Effect of the Length of Frame on Delay----------90
5.4.3 Effect of Unbalanced Flow on Efficiency---------91
5.4.4 Variation of Efficiency with Number of Central Modules--92
5.4.5 Comparison between Fixed Threshold and Variable Threshold-93
5.4.6 Evaluating Performance for Various Busty Lengths--------95
5.5 Quality of Service of 3D-VOQ----------------------97
5.5.1 Support High/Low Priority QoS-------------------98
5.5.2 Support Class of Service of 3D-VOQ-------------100
Chapter 6 Conclusions and Future Works--------------101
6.1 Conclusion of this Dissertation------------------101
6.2 Research Direction for Future Works--------------103
References-------------------------------------------104
Index------------------------------------------------110
Vita-------------------------------------------------113
Publication List-------------------------------------114

[1]H. Ahmadi and W. E. Denzel, "A survey of modern high-performance switching techniques", IEEE Journal on Selected Areas in Communications, Vol. 7, pp.1091-1103, Sep. 1989.
[2]Rainer Handel, Manfred N. Huber, and Stefan Schroder, ATM Networks: Concepts, Protocols, Applications. Addison-Wesley Publishers, 1994.
[3]Hyoung-Il Lee and Seung-Woo Seo, “Matching Output Queueing with a Multiple Input/Output-Queued Switch” INFOCOM 2004. IEEE International Conference, Hong-Kong, Vol. 1, 07-11 March 2004
[4]N. Mckeown, “Scheduling Algorithms for Input-queued Cell Switches,” Ph. D. dissertation, Univ. California at Berkeley, 1995.
[5]N. Mckeown, “The iSLIP Scheduling Algorithm for Input-Queued Switches,” IEEE/ACM Transactions on Networking, Vol. 7, No. 2, pp. 188-201, April 1999.
[6]R. O. LaMaire and D. N. Serpanos, “Two Dimensional Round-Robin Schedulers for Packet Switches with Multiple Input Queues,” IEEE/ACM Trans. Networking, Vol. 2, pp. 471-482, Oct. 1994.
[7]H. J. Chao, “Saturn: A Terabit Packet Switch using Dual Round-Robin,” IEEE Comunnications Magazine, Vol. 38, pp. 78-84, Dec. 2000.
[8]M. Karol, M. Hluchyj, and S. Morgan, "Input Versus Output Queueing on a Space Division Switch", IEEE Trans. Commun., Vol.35, No.12, pp.1347-1356, Dec. 1987.
[9]N. McKeown, V. Anantharam, and J.Walrand, "Achieving 100% Throughput in an Input-Queued Switch", IEEE INFOCOM '96, pp.296-302, 1996
[10]T. Anderson, S. Owicki, J. Saxe, and C. Thacker, “High-Speed Switch Scheduling for Local-Area Networks,” ACM Transactions on Computer Systems, Vol. 11, No. 4, pp. 319-352, Nov. 1993.
[11]Y. S. Yeh, M. G. Hluchyj, and A. S. Acampora, “The knockout switch: a simple, modular architecture for high-performance switching,” IEEE J. Selected Areas in Communications., Vol. 5, No. 8, pp. 1274-1283, Oct. 1987.
[12]P. Krishna, N. Patel, A. Charny, and R. Simcoe, "On the Speedup Required for Work-Conserving Crossbar Switches", Proc. IWQOS’98, pp. 1057-1066, 1998
[13]B. Prabhakar, N. Mckeown, “On the speedup required for combined input and output queued switching”, Automatica, Vol. 35, No. 12, Dec. 1999
[14]S. T. Chuang, A. Goel, N. Mckeown, and B. Prabhakar, “Matching output queueing with a combined input output queued switch”, IEEE Journal on Selected Areas in Communications, Vol. 17, No. 6, pp. 1030-1039, June 1999.
[15]I. Stoica and H. Zhang, “Exact emulation of an output queueing switch by a combined input output queueing switch”, Proc. 6th IEEE/IFIP IWQoS’98, Napa Valley, CA, pp. 218-224, May 1998.
[16]S. T. Chuang, S. Iyer, and N. Mckeown, “Practical Algorithms for Performance Guarantees in Buffered Crossbars” Proceedings of IEEE INFOCOM ‘05, Miami, Florida, March 2005.
[17]Ding-Jyh Tsaur, Xian-Yang Lu, Chin-Chi Wu, and Woei Lin “3D-VOQ Switch Design and Evaluation” IEEE 19th International Conference on Advanced Information Networking and Applications(AINA’05), Vol.2, pp. 359-362, 2005
[18]T. Chaney, J. A. Fingerhut, M. Flucke and J. S. Turner. "Design of a gigabit ATM switch," Proc. IEEE INFOCOM'97, 1997
[19]A. Hwang and S. Knauer, "Starlite: A wideband digital switch," Proceedings of Globecom'84, Dec. 1984, pp. 659-665, 1984
[20]J. Y. Hm and E. Arthurs, "A broadband packet switch for integrated transport," IEEE Journal on Selected Areas in Communications, pp. 1264-1273, Oct. 1987
[21]S-Q Li, "Performance of a non-blocking space-division packet switch with correlated input traffic." Conf. Reord, Globecom'89, Vol. 3, pp. 1754-1763, 1989
[22]H. Obara and Y. Hamazumi, "Parallel contention resolution control for input queueing ATM switches," Electronics Letters, pp. 838-839, Apr. 1992
[23]H. Matsunago and H. Uematsu, "A 1.5 Gb/s 8x8 cross-connect switch using a time reservation algorithm," IEEE Journal on Selected Areas in Communications. Vol. 9, pp. 1308-1317, Oct. 1991
[24]N. McKeown, M. Izzard, A. Mekkittikul, B. Ellersick and M. Horowitz, "The Tiny Tera: A packet switch core", IEEE Micro, pp. 26-33, Jan/Feb 1997.
[25]Y. Tamir, and G. Frazier, "High performance multi-queue buffers for VLSI communication switchers," Proc. of 15th Ann. Symp. on Comp. Arch., pp. 343-354, June 1988
[26]H Duan, J. W. Lockwood, S. M. Kang, and J. D. Will, "A high-performance OC-12/OC-48 queue design prototype for input-buffered ATM switches," Proc. IEEE INFOCOM'97, pp. 20-28, 1997
[27]M. R. Hashemi and A. Leon-Garcia, "The Single-Queue Switch: A building block for switches with programmable scheduling," IEEE Journal on Selected Areas in Communications, Vol. 15, pp. 785-793, June 1997
[28]M. D. Prycker, Asynchronous Transfer Mode: Solution for Broadband ISDN. Prentice Hall, 1995
[29]R. J. McEliece, R. B. Ash and Carol Ash, Introduction To Discrete Mathematics. McGraw-Hill, 1989
[30]C. H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithm and Complexity. New Jersey: Prentice-Hall, 1982
[31]A. Mekkittikul and N. McKeown, "A starvation-free algorithm for achieving 100% throughput in an input-queued switch," Proc. ICCCN'96, 1996
[32]A. Mekkittikul and N. McKeown, "A practical scheduling algorithm to achieve 100% throughput in input-queued switches," Proc. IEEE INFOCOM'98, 1998
[33]J. Hui, Switching and Traffic Theory for Integrated Broadband Networks Boston: Kluwer Academic Publishers, 1990
[34]N. McKeown, P. Varaiya, and J. Walrand, "Scheduling cells in an input-queued switch," IEEE Electronics Letters, pp. 2174-5, Dec. 1993
[35]A. Charny, P. Krishna, N. Patel, and R. Simcoe, "Algorithms for providing bandwidth and delay guarantees in input-buffered crossbars with speedup," Proc. IWQOS'98, 1998
[36]B. Prabhakar and N. Mckeown, “On the speedup required for combined input and output queued switching”, Computer Lab., Stanford University Technical Report, STAN-CSL-TR-97-738. Nov. 1997
[37]D. Gale and L.S. Shapley, “College admissions and the stability marriage,” Mathematical Monthly, Vol. 69, pp. 9-15, 1962
[38]D. Gusfield and R. W. Irving, The Stable Marriage Problem: Structure and Algorithms. MIT press, 1989
[39]H. J. Chao, C. H. Lam, and E. Oki, “Broadband Packet Switch Technologies” WILEY-INTERSCIENCE, 2001.
[40]T. H. Lee and Y. C. Kuo, “Parallel match algorithm for CIOQ switches with multiple traffic classes” IEE Proc. Commun., Vol. 150, No. 5, pp. 354-360, October 2003
[41]J.J. Bae, and T. Suda, “Survey of traffic control schemes and protocols in ATM networks,” Proc. IEEE, Vol. 79, No. 2, pp. 170-189, Feb. 1991.
[42]G.D. Stamoulis, M.E. Anagnostou, and A.D. Georgantas, “Traffic models for ATM networks: a survey,” Computer Commun., Vol. 17, No. 6, pp. 428-438, June 1994.
[43]J. Blanton, H. Badt, G. Damm, and P. Golla, “Impact of polarized traffic on scheduling algorithms for high speed optical switches”, ITCom2001, Denver, Aug. 2001
[44]H. J. Chao, Cheuk H. Lam, and Eiji Oki, “Broadband Packet Switching Technologies,” Wiley, 2001.
[45]H. J. Chao, K. L. Deng, and Z. Jing, "Packet scheduling scheme for a 3-stage Clos-network photonic switch," IEEE ICC 2003, Anchorage, Alaska, pp. 1293-1298, May 2003.
[46]H. J. Chao, K-L. Deng, and Z. Jing, “ A Petabit Photonic Packet Switch(P3S),” IEEE INFOCOM ’03, pp. 775-785, San Francisco, CA, Apr. 2003.
[47]H. J. Chao, S. Y. Liew, and Z. Jing, “Matching Algorithms for Three-Stage Bufferless Clos Network Switches,” IEEE Communications Magazine, pp. 46 -54, Oct. 2003.
[48]H. J. Chao, K-L. Deng, and Z. Jing, “PetaStar: A Petabit Photonic Packet Switch,” IEEE JSAC Special Issue on High-Performance Optical/Electronic Switches/Routers for High-Speed Internet, Vol. 21, No. 7, pp. 1096-1112, Sept. 2003.
[49]H. J. Chao, S. Y. Liew, and Z. Jing, “A Dual-Level Matching Algorithm for 3-stage Clos-Network Packet Switches,” Proc. Hot Interconnects 11, Stanford Univ., CA, Aug. 2003.
[50]E. Oki, Z. Jing, R. Rojas-Cessa, and H. J. Chao, “The dual round robin matching switch with exhaustive service,” Merging Optical and IP Technologies, pp. 58-63, May. 2002.
[51]Y. Li, S. S. Panwar, and H. J. Chao, “Performance analysis of a dual round robin matching switch with exhaustive service,” Global Telecommunications Conference, 2002. GLOBECOM '02. IEEE, Vol. 3, pp. 2292-2297, Nov. 2002.
[52]E. Oki, Z. Jing, R. Rojas-Cessa, and H. J. Chao, “Concurrent round-robin-based dispatching schemes for Clos-network switches,” IEEE/ACM Transactions on Networking, Vol. 10, No. 6, pp. 830-844, Dec. 2002.
[53]K. Yoshigoe and K. J. Christensen, “A Parallel-Polled Virtual Output Queued Switch with a Buffered Crossbar.” 2001 IEEE Workshop, pp. 271– 275, May 2001
[54]D. Gross and C. M. Harris, “Fundamentals of Queueing theory”, 3rd Edition. New York Wiley, 1998.
[55]Bellcore, “Broadband switching system (BSS) generic requirements, BSS performance,” GR-110-CORE, Issue 1, Sep. 1994
[56]D. J. Tsaur, C. F. Tang, C. C. Wu, and W. Lin; “A Threshold- based Matching Algorithm for Photonic Clos Network Switches” Springer's Lecture Note in Computer Science – LNCS, Vol. 3726, pp.176~189, 2005