大容量交换机多级交换结构及其调度算法的研究与设计
摘要
随着因特网和宽带通信技术的高速发展,因特网的信息流量和设备的数量以惊人的速度增长,同时传输技术的长足发展使得传输容量大幅度提高。交换机和路由器是架构因特网的主要互连设备,因而对交换机和路由器提出了更高的要求。高速、高性能的交换机和路由器是实现高速骨干网并决定其性能的关键所在。
本文首先介绍了三级Clos网络的应用以及无阻塞条件,在此基础上提出了基于三级Clos网络大容量分组交换机的体系结构,并且分析了交换机的数据流程,输入控制器和输出控制器的帧处理,以及集中调度器的功能结构。
本文详细讨论了集中调度器的逻辑结构以及分组调度策略的设计。集中调度器在交换机设计中处于中心位置,是整个交换机协调工作的关键。本文提出了一种基于帧的双重匹配调度策略,该策略分为模块级匹配和端口级匹配两部分,采用启发式并行匹配算法进行路由,采用本文根据iSLIP输入排队调度算法提出的E-iSLIP算法进行调度。E-iSLIP算法采用竭力服务策略和优先级概念,可以改善算法在突发流量下的性能。在这些设计思想的指导下,本文对E-iSLIP算法进行了性能仿真,仿真结果表明,与iSLIP算法相比,E-iSLIP算法在突发流量下的性能有明显改善,在均匀流量下是稳定的,而且采用了优先级的E-iSLIP算法比未采用优先级之前具有更好的公平性。
With the rapid development of Internet and broadband communications technology, the information and devices of Internet is growing with exponential speed, meanwhile, the capacity of transmission is largely improved by the growing transmission technology. Switches and routers are highly demanded and the key of realization of high speed back bone network as the main interconnection devices of Internet construction.
This paper introduces the application and nonblocking conditions of the three-stage Clos network firstly. After that, the architecture of a packet switch based on the three-stage Clos network is proposed. Next, the data flow, frame processing of input port controller and output port controller and the structure of centralized packet scheduler are described.
After introducing the concepts and architectures of the multistage switch, the author focuses on the design of packet scheduler and the strategy of scheduling. Packet scheduler is the center and key of the design of switch. A dual-level matching strategy based on frame is proposed in this paper. The strategy is composed of module-level matching and port-level matching, a heuristic parallel matching algorithm is used for routing, and the E-iSLIP algorithm based on the iSLIP algorithm is used for scheduling. The exhaustive service strategy and priority concept are both used in the E-iSLIP algorithm to improve the performance under burst traffic. After that, the simulation of E-iSLIP and iSLIP are introduced in details and the results of simulation are analyzed also. It can be seen clearly that the E-iSLIP outperforms the iSLIP algorithm under burst traffic in delay performance and maintains stable under uniform traffic. Besides, E-iSLIP which employs priorities has better fairness than that without priorities.
本文首先介绍了三级Clos网络的应用以及无阻塞条件,在此基础上提出了基于三级Clos网络大容量分组交换机的体系结构,并且分析了交换机的数据流程,输入控制器和输出控制器的帧处理,以及集中调度器的功能结构。
本文详细讨论了集中调度器的逻辑结构以及分组调度策略的设计。集中调度器在交换机设计中处于中心位置,是整个交换机协调工作的关键。本文提出了一种基于帧的双重匹配调度策略,该策略分为模块级匹配和端口级匹配两部分,采用启发式并行匹配算法进行路由,采用本文根据iSLIP输入排队调度算法提出的E-iSLIP算法进行调度。E-iSLIP算法采用竭力服务策略和优先级概念,可以改善算法在突发流量下的性能。在这些设计思想的指导下,本文对E-iSLIP算法进行了性能仿真,仿真结果表明,与iSLIP算法相比,E-iSLIP算法在突发流量下的性能有明显改善,在均匀流量下是稳定的,而且采用了优先级的E-iSLIP算法比未采用优先级之前具有更好的公平性。
With the rapid development of Internet and broadband communications technology, the information and devices of Internet is growing with exponential speed, meanwhile, the capacity of transmission is largely improved by the growing transmission technology. Switches and routers are highly demanded and the key of realization of high speed back bone network as the main interconnection devices of Internet construction.
This paper introduces the application and nonblocking conditions of the three-stage Clos network firstly. After that, the architecture of a packet switch based on the three-stage Clos network is proposed. Next, the data flow, frame processing of input port controller and output port controller and the structure of centralized packet scheduler are described.
After introducing the concepts and architectures of the multistage switch, the author focuses on the design of packet scheduler and the strategy of scheduling. Packet scheduler is the center and key of the design of switch. A dual-level matching strategy based on frame is proposed in this paper. The strategy is composed of module-level matching and port-level matching, a heuristic parallel matching algorithm is used for routing, and the E-iSLIP algorithm based on the iSLIP algorithm is used for scheduling. The exhaustive service strategy and priority concept are both used in the E-iSLIP algorithm to improve the performance under burst traffic. After that, the simulation of E-iSLIP and iSLIP are introduced in details and the results of simulation are analyzed also. It can be seen clearly that the E-iSLIP outperforms the iSLIP algorithm under burst traffic in delay performance and maintains stable under uniform traffic. Besides, E-iSLIP which employs priorities has better fairness than that without priorities.
引文
[1] Singhal A. Terabit switches and routers. http://www.cis.ohio-state.edu, 2000
[2] Dally W J. Architecture of the Avici terabit switch router. Proc. Hot Interconnects XIII, 1998
[3] Chao J. Saturn: A terabit packet switch using dual round-robin. IEEE Communications Magazine, 2000. 78～84
[4] Chao J and Wang T S. An optical interconnection network for terabit IP routers. IEEE journal of Lightwave Technology, 2000. 18(12): 2095～2112
[5] Turner J S. Terabit burst switching. Journal of high speed networks, 1999. 8(1): 18～31
[6] Wang W, Yang K, Lin T. A terabit switch fabric with integrated high-speed CMOS Transceivers. Hot Interconnects, Stanford University, 2000
[7] Abel F, Minkenberg C, Luijten R P, et al. A four-terabit single-stage packet switch with large round-trip time support. Proc. of the 10th Symposium on High Performance Interconnects, IEEE press, 2002. 314～322
[8] Iyer S, Zhang Rui, Mckeown N. Routers with a single stage of buffering. Proc. ACM SIGCOMM, Pittsburgh, 2002
[9] Keslassy I, Chuang S T, Su K, et al. Scaling routers using optics. Proc. of ACM SIGCOMM, Karlsruhe, Germany, 2003
[10] Mckeown N. Optics inside routers. Proc of ECOC 2003, Rimini, Italy, 2003
[11] Mckeown N, Calamvokis C, Chuang S T. A 2.5Tb/s LCS switch core. Hot Chips XIII, 2001
[12] Chao H J, Lam C, and Oki E. Broadband packet switching technologies — A practical guide to ATM switches and IP routers, Wiley, 2001
[13] Karol M, Hluchyj M, Morgan S. Input versus output queuing on a space division switch. IEEE Trans. Communications, 1987, 35(12): 1347～1356
[14] Tamir Y, Frazier G. Dynamically-allocated multi-queue buffer for VLSI communication switches. IEEE Transanctions on Computers, 1992, 41(6):725～737
[15] Iyer S, Awadallah A, Mckeown N. Analysis of a packet switch with memories running slower than the line-rate. Proc. of the IEEE INFOCOM, 2000, 529～537
[16] Chang C S, Lee D S, Jou Y S. Load balanced Birkhoff-von Neumann switches Part I: One-stage buffering. Computer Communications, 2002, 25(6): 611～622
[17] Chang C S, Lee D S, Lien C M. Load balanced Birkhoff-von Neumann switches Part II: Multi-Stage buffering. Computer Communications, 2002, 25(6): 623～634
[18] Clos C. A study of Non-Blocking switching networks. Bell Systems Technical Journal, 1953, 406～424
[19] 江勇,吴建平,徐恪.高性能交换体系结构及其调度算法分析.电子学报,2001,28(11):105～109
[20] Chao H J, Deng K L, and Jing Z. A petabit photonic packet switch (P3S). IEEE INFOCOM, San Francisco, CA, 2003
[21] Chao H J, Deng K L, and Jing Z. PetaStar: a petabit photonic packet switch. IEEE JSAC Special Issue on High Performance Optical/Electronic Switches/Routers for High-Speed Internet, 2003, 21(7)
[22] 胡嘉,罗志祥,夏鸣等. 使用多级交换网络进行大容量光纤通道交换机设计. 光通信技术,2006,30(139):11～13
[23] Lee T T and Lam C H. Path Switching: a quasi-static routing scheme for large-scale ATM packet switches. IEEE JSAC, vol.15, 1997, 914～924
[24] Pun K and Hamdi M. Distro: a distributed static round-robin scheduling algorithm for bufferless Clos-Network switches. IEEE GLOBECOM, Taipei, 2002
[25] Cole R, Ost K, and Schirra S. Edge-coloring bipartite multigraphs in O(E log D) Time. Combinatorica 21, 2001, 5～12
[26] Lee T T and Liew S Y. Parallel routing algorithms in Bens-Clos network. IEEE Trans. Commun., 2002, 50(11): 1841～1847
[27] Karol M and I C-L. Performance analysis of a growable architecture for broadband packet (ATM) switching. GLOBECOM, 1989, 1173～1180
[28] 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, 2003
[29] Bianco A, et al. Frame-based matching algorithms for input-queued switches. Workshop on High Performance Switching and Routing, Kobe, Japan, 2002
[30] Oki E, Rojas-Cessa R, and Chao H J. A Pipeline-Based Approach for Maximal-Sized Matching Scheduling in Input-Buffered Switches, IEEE Commun. Letts, 2001, 5 (6): 263～265
[31] 庞斌,贺思敏,高文. 高速 IP 路由器中输入排队调度算法综述. 软件学报,2003, 14(5): 1011～1022
[32] Hopcroft J E, Karp RM. An n5/2 algorithm for maximum matching in bipartite graphs. SIAM Journal on Computing, 1973, 1 (2): 225～231
[33] McKeown N, Mekkittikui A, Anantharam V, Walrand J. Achieving 100% throughput in an input-queued switch. IEEE Transactions on Communication, 1999, 47(8): 1260～1267
[34] Anderson T, Owicki S, Saxes J, Thacker C. High speed switch scheduling for local area networks. ACM Transactions on Computer Systems, 1993, 11(4): 319～352
[35] McKeown N. The iSLIP scheduling algorithm for input-queued switches. IEEE/ACM Transactions on Networking, 1999, 7(2): 188～201
[36] McKeown N. Scheduling algorithms for input-queued switches [Ph.D. Thesis]. University of California at Berkeley, 1995
[37] Li Yihan, Panwar S, Chao H J. Exhaustive service matching algorithms for input queued switches. High Performance Switching and Routing, 2004, 253～358
[38] Yoohan Kim, H. J. Chao. Performance of exhaustive matching for input-queued switches. ICC 2003–IEEE International Conference on Communications, 2003, 1817～1822
[39] SIM Manual. High Performance Networking Group at Stanford University. http://klamath.stanford.edu/tools/SIM, 1999
[40] 彭来献,田畅,郑少仁. 高速 crossbar 控制算法 iDRR 及其性能分析. 电子学报,2003,31(10): 1465～1468
[2] Dally W J. Architecture of the Avici terabit switch router. Proc. Hot Interconnects XIII, 1998
[3] Chao J. Saturn: A terabit packet switch using dual round-robin. IEEE Communications Magazine, 2000. 78～84
[4] Chao J and Wang T S. An optical interconnection network for terabit IP routers. IEEE journal of Lightwave Technology, 2000. 18(12): 2095～2112
[5] Turner J S. Terabit burst switching. Journal of high speed networks, 1999. 8(1): 18～31
[6] Wang W, Yang K, Lin T. A terabit switch fabric with integrated high-speed CMOS Transceivers. Hot Interconnects, Stanford University, 2000
[7] Abel F, Minkenberg C, Luijten R P, et al. A four-terabit single-stage packet switch with large round-trip time support. Proc. of the 10th Symposium on High Performance Interconnects, IEEE press, 2002. 314～322
[8] Iyer S, Zhang Rui, Mckeown N. Routers with a single stage of buffering. Proc. ACM SIGCOMM, Pittsburgh, 2002
[9] Keslassy I, Chuang S T, Su K, et al. Scaling routers using optics. Proc. of ACM SIGCOMM, Karlsruhe, Germany, 2003
[10] Mckeown N. Optics inside routers. Proc of ECOC 2003, Rimini, Italy, 2003
[11] Mckeown N, Calamvokis C, Chuang S T. A 2.5Tb/s LCS switch core. Hot Chips XIII, 2001
[12] Chao H J, Lam C, and Oki E. Broadband packet switching technologies — A practical guide to ATM switches and IP routers, Wiley, 2001
[13] Karol M, Hluchyj M, Morgan S. Input versus output queuing on a space division switch. IEEE Trans. Communications, 1987, 35(12): 1347～1356
[14] Tamir Y, Frazier G. Dynamically-allocated multi-queue buffer for VLSI communication switches. IEEE Transanctions on Computers, 1992, 41(6):725～737
[15] Iyer S, Awadallah A, Mckeown N. Analysis of a packet switch with memories running slower than the line-rate. Proc. of the IEEE INFOCOM, 2000, 529～537
[16] Chang C S, Lee D S, Jou Y S. Load balanced Birkhoff-von Neumann switches Part I: One-stage buffering. Computer Communications, 2002, 25(6): 611～622
[17] Chang C S, Lee D S, Lien C M. Load balanced Birkhoff-von Neumann switches Part II: Multi-Stage buffering. Computer Communications, 2002, 25(6): 623～634
[18] Clos C. A study of Non-Blocking switching networks. Bell Systems Technical Journal, 1953, 406～424
[19] 江勇,吴建平,徐恪.高性能交换体系结构及其调度算法分析.电子学报,2001,28(11):105～109
[20] Chao H J, Deng K L, and Jing Z. A petabit photonic packet switch (P3S). IEEE INFOCOM, San Francisco, CA, 2003
[21] Chao H J, Deng K L, and Jing Z. PetaStar: a petabit photonic packet switch. IEEE JSAC Special Issue on High Performance Optical/Electronic Switches/Routers for High-Speed Internet, 2003, 21(7)
[22] 胡嘉,罗志祥,夏鸣等. 使用多级交换网络进行大容量光纤通道交换机设计. 光通信技术,2006,30(139):11～13
[23] Lee T T and Lam C H. Path Switching: a quasi-static routing scheme for large-scale ATM packet switches. IEEE JSAC, vol.15, 1997, 914～924
[24] Pun K and Hamdi M. Distro: a distributed static round-robin scheduling algorithm for bufferless Clos-Network switches. IEEE GLOBECOM, Taipei, 2002
[25] Cole R, Ost K, and Schirra S. Edge-coloring bipartite multigraphs in O(E log D) Time. Combinatorica 21, 2001, 5～12
[26] Lee T T and Liew S Y. Parallel routing algorithms in Bens-Clos network. IEEE Trans. Commun., 2002, 50(11): 1841～1847
[27] Karol M and I C-L. Performance analysis of a growable architecture for broadband packet (ATM) switching. GLOBECOM, 1989, 1173～1180
[28] 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, 2003
[29] Bianco A, et al. Frame-based matching algorithms for input-queued switches. Workshop on High Performance Switching and Routing, Kobe, Japan, 2002
[30] Oki E, Rojas-Cessa R, and Chao H J. A Pipeline-Based Approach for Maximal-Sized Matching Scheduling in Input-Buffered Switches, IEEE Commun. Letts, 2001, 5 (6): 263～265
[31] 庞斌,贺思敏,高文. 高速 IP 路由器中输入排队调度算法综述. 软件学报,2003, 14(5): 1011～1022
[32] Hopcroft J E, Karp RM. An n5/2 algorithm for maximum matching in bipartite graphs. SIAM Journal on Computing, 1973, 1 (2): 225～231
[33] McKeown N, Mekkittikui A, Anantharam V, Walrand J. Achieving 100% throughput in an input-queued switch. IEEE Transactions on Communication, 1999, 47(8): 1260～1267
[34] Anderson T, Owicki S, Saxes J, Thacker C. High speed switch scheduling for local area networks. ACM Transactions on Computer Systems, 1993, 11(4): 319～352
[35] McKeown N. The iSLIP scheduling algorithm for input-queued switches. IEEE/ACM Transactions on Networking, 1999, 7(2): 188～201
[36] McKeown N. Scheduling algorithms for input-queued switches [Ph.D. Thesis]. University of California at Berkeley, 1995
[37] Li Yihan, Panwar S, Chao H J. Exhaustive service matching algorithms for input queued switches. High Performance Switching and Routing, 2004, 253～358
[38] Yoohan Kim, H. J. Chao. Performance of exhaustive matching for input-queued switches. ICC 2003–IEEE International Conference on Communications, 2003, 1817～1822
[39] SIM Manual. High Performance Networking Group at Stanford University. http://klamath.stanford.edu/tools/SIM, 1999
[40] 彭来献,田畅,郑少仁. 高速 crossbar 控制算法 iDRR 及其性能分析. 电子学报,2003,31(10): 1465～1468
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |