基于CICQ排队机制与调度策略的研究
|
摘要
交换结构和调度策略作为路由交换设备中的核心技术,其性能直接影响甚至决定路由交换设备的性能。近年来随着现代网络技术的迅猛发展,互联网在总体规模和体系结构上发生了重大改变,传统交换调度机制已经成为制约网络规模进一步发展的瓶颈之一,网络核心结点路由交换设备的交换性能正面临严峻的挑战。
论文结合国家“十五”863计划信息技术领域“高性能宽带信息网(3Tnet)”重大专项课题《大规模接入汇聚路由器(ACR)系统性能和关键技术研究》(简称ACR)的研发,从交换系统的普遍模型出发对现有的交换系统进行了分类和比较,对该领域的成果进行了较为全面的总结,并基于带缓存交叉开关这一新型交换单元,在高速环境的可扩展性、组播支持方面进行了研究,为ACR构建了一种合适的交换系统解决方案。本文主要工作如下;
■针对目前交换技术领域理论分析的不足以及仿真实验评价手段缺乏对交换系统性能评估的有力支撑,采用系统级设计方法和面向对象技术设计实现了一种专用的交换技术性能仿真与评价系统—SPES(Switch Performance Evaluation System)。具有良好的可扩展与可继承特性,为交换技术领域的技术创新和方案设计提供了一个基础研究平台。
■分析了具有良好可扩展性交换结构和调度策略设计的基本准则。依据这一准则重点研究了基于联合输入交叉节点排队交换结构调度算法的设计,提出了一种基于份额的动态轮询调度策略FDR,其算法复杂度仅为O(1),具有良好的动态与可扩展特性。SPES系统仿真结果表明FDR具有良好的吞吐量、时延和抗突发性能。
■从传统交换结构支持组播交换方面存在的不足出发,提出了支持单组播混合调度的交换结构—MCICQ(Multicast Supporting CICQ)。该结构能够有效解决单组播在交叉开关内部的带宽冲突问题,采用简单的MFDR调度策略就可以获得良好的性能。针对单组播业务对QoS的不同需求,在MFDR的基础上给出了MFS调度策略。MFS除具备良好的可扩展特性外,还具有能够为单组播业务提供不同的带宽保证能力。
■依据ACR的研制需求,针对该路由器的特点,以及综合考虑系统性能、设计成本和工程开发周期的基础上,为ACR设计了一种具有组播支持能力的交换系统工程解决方案,满足了其在可扩展性、组播支持方面的需求。该工程实现方案已在《大规模接入汇聚路由器(ACR)系统性能和关键技术研究》项目的路由器设备实际研发中得到成功应用。
Switching fabrics and scheduling policies are the core technologies of the routing and switching equipment, and their performance has direct effects and even determines the performance of the routing and switching equipment. With the fast development of information technology, Internet has undergone great changes in the overall scale and architecture in the last few years. Traditional switching and scheduling mechanisms have become the bottlenecks for further network developments.
Combined with the research and development of the project "Research on system performance and key technologies of large-scale Access Convergence Router (ACR)" supported by the Major Dedicated Research Project of the High-performance Broadband Information Network under China National Research and Development Program 863 for the Tenth-Five-Year Plan in the information technology, this dissertation classifies and compares the current switching systems from the perspective of the general model of various switching systems, and summarizes results achieved in this area. Based on the new buffered crossbar switching unit, it comes up with researches into the extensibility and multicast supporting scheme in the high-speed environment, creating a suitable solution to the switching system for ACR. Its main work and contributions are outlined as follows:
Due to the deficiency of theory analysis in switching technology and the lack of system-level support of the switching technology from simulation and experimental evaluation tools, a dedicated switching performance evaluation system (SPES) is designed and implemented by adopting system-level design methods and object-oriented technology. It has good extensibility and follow-on features and provides a basic research platform for technical innovation and scheme design of the switching technology.
The dissertation analyzes the guideline for designing high extensible switching and scheduling algorithms. Based on this guideline, it focuses its research on the design of the scheduling policies for combined input and cross-point queuing switching fabric and comes up with FDR (Fair and Dynamic Round-robin) algorithm, whose complexity is only 0(1). It has excellent dynamic and extensibility. The simulation results of the SPES system show that the FDR algorithm exhibits good throughput, delay and anti-burst performance.
In order to overcome the deficiency in supporting multicast in current switching systems, the dissertation proposes a new switching fabric MCICQ (Multicast supporting CICQ) which supports the uni-/multicast hybrid scheduling, and Scheduling policies MFDR and MFS which support the parallel distributed uni-/multicast are also proposed. With the fanout splitting mechanism, both MFDR and MFS can achieve good performance without speedup, and their complexity is only 0(1). MFS scheduling policy can also provide different bandwidth guarantees for uni-/multicast traffic. Simulation results under SPES show that both MFDR and MFS can achieve good performance.
From the development requirements of the ACR router and oriented toward ACR features, such factors as systematic performance, designing cost and development cycle have been taken into account. A system solution has been provided herein for ACR to support multicast. It meets the requirements in extensibility and multicast supporting. Its engineering implementation scheme has been successfully applied to the actual development of routing and switching equipment under the project of ACR.
论文结合国家“十五”863计划信息技术领域“高性能宽带信息网(3Tnet)”重大专项课题《大规模接入汇聚路由器(ACR)系统性能和关键技术研究》(简称ACR)的研发,从交换系统的普遍模型出发对现有的交换系统进行了分类和比较,对该领域的成果进行了较为全面的总结,并基于带缓存交叉开关这一新型交换单元,在高速环境的可扩展性、组播支持方面进行了研究,为ACR构建了一种合适的交换系统解决方案。本文主要工作如下;
■针对目前交换技术领域理论分析的不足以及仿真实验评价手段缺乏对交换系统性能评估的有力支撑,采用系统级设计方法和面向对象技术设计实现了一种专用的交换技术性能仿真与评价系统—SPES(Switch Performance Evaluation System)。具有良好的可扩展与可继承特性,为交换技术领域的技术创新和方案设计提供了一个基础研究平台。
■分析了具有良好可扩展性交换结构和调度策略设计的基本准则。依据这一准则重点研究了基于联合输入交叉节点排队交换结构调度算法的设计,提出了一种基于份额的动态轮询调度策略FDR,其算法复杂度仅为O(1),具有良好的动态与可扩展特性。SPES系统仿真结果表明FDR具有良好的吞吐量、时延和抗突发性能。
■从传统交换结构支持组播交换方面存在的不足出发,提出了支持单组播混合调度的交换结构—MCICQ(Multicast Supporting CICQ)。该结构能够有效解决单组播在交叉开关内部的带宽冲突问题,采用简单的MFDR调度策略就可以获得良好的性能。针对单组播业务对QoS的不同需求,在MFDR的基础上给出了MFS调度策略。MFS除具备良好的可扩展特性外,还具有能够为单组播业务提供不同的带宽保证能力。
■依据ACR的研制需求,针对该路由器的特点,以及综合考虑系统性能、设计成本和工程开发周期的基础上,为ACR设计了一种具有组播支持能力的交换系统工程解决方案,满足了其在可扩展性、组播支持方面的需求。该工程实现方案已在《大规模接入汇聚路由器(ACR)系统性能和关键技术研究》项目的路由器设备实际研发中得到成功应用。
Switching fabrics and scheduling policies are the core technologies of the routing and switching equipment, and their performance has direct effects and even determines the performance of the routing and switching equipment. With the fast development of information technology, Internet has undergone great changes in the overall scale and architecture in the last few years. Traditional switching and scheduling mechanisms have become the bottlenecks for further network developments.
Combined with the research and development of the project "Research on system performance and key technologies of large-scale Access Convergence Router (ACR)" supported by the Major Dedicated Research Project of the High-performance Broadband Information Network under China National Research and Development Program 863 for the Tenth-Five-Year Plan in the information technology, this dissertation classifies and compares the current switching systems from the perspective of the general model of various switching systems, and summarizes results achieved in this area. Based on the new buffered crossbar switching unit, it comes up with researches into the extensibility and multicast supporting scheme in the high-speed environment, creating a suitable solution to the switching system for ACR. Its main work and contributions are outlined as follows:
Due to the deficiency of theory analysis in switching technology and the lack of system-level support of the switching technology from simulation and experimental evaluation tools, a dedicated switching performance evaluation system (SPES) is designed and implemented by adopting system-level design methods and object-oriented technology. It has good extensibility and follow-on features and provides a basic research platform for technical innovation and scheme design of the switching technology.
The dissertation analyzes the guideline for designing high extensible switching and scheduling algorithms. Based on this guideline, it focuses its research on the design of the scheduling policies for combined input and cross-point queuing switching fabric and comes up with FDR (Fair and Dynamic Round-robin) algorithm, whose complexity is only 0(1). It has excellent dynamic and extensibility. The simulation results of the SPES system show that the FDR algorithm exhibits good throughput, delay and anti-burst performance.
In order to overcome the deficiency in supporting multicast in current switching systems, the dissertation proposes a new switching fabric MCICQ (Multicast supporting CICQ) which supports the uni-/multicast hybrid scheduling, and Scheduling policies MFDR and MFS which support the parallel distributed uni-/multicast are also proposed. With the fanout splitting mechanism, both MFDR and MFS can achieve good performance without speedup, and their complexity is only 0(1). MFS scheduling policy can also provide different bandwidth guarantees for uni-/multicast traffic. Simulation results under SPES show that both MFDR and MFS can achieve good performance.
From the development requirements of the ACR router and oriented toward ACR features, such factors as systematic performance, designing cost and development cycle have been taken into account. A system solution has been provided herein for ACR to support multicast. It meets the requirements in extensibility and multicast supporting. Its engineering implementation scheme has been successfully applied to the actual development of routing and switching equipment under the project of ACR.
引文
[1]M.Odlyzko.Comments on the Larry Roberts and Caspian Networks study of Internet traffic growth[J].The cook Report on the Internet,2001,21(5);12-15.
[2]S.Deering,R.Hinden.Internet Protocol,Version 6(IPv6)Specification.RFC2460[S].IETF,1998.
[3]A.Mekkittikul.Scheduling Non-uniform Traffic in High Speed Packet Switches and Routers[D].California;Stanford University,1998.
[4]N.McKeown.Scheduling Algorithms for Input-queued Cell Switches[D].Berkeley;University of California at Berkeley,1995.
[5]M.Karol,M.Hluchyj,S.Morgan.Input versus Output Queueing on a Space Division Packet Switch[J].IEEE Transactions on Communications,1987,35(12);1347-1356.
[6]V.Singhal,R.Le.High-speed Buffered Crossbar Switch Design Using Virtex-EM Devices[DB/OL].;Xinlinx 公司主页,2007-03-27.
[7]M.Nabeshima.Performance Evaluation of a Combined Input- and Crosspoint-queued Switch[J].IEICE Trans.Commun.,2000,E83-B(3);737-741.
[8]伊鹏.基于带缓存交叉开关的交换技术研究[D].郑州;信息工程大学,2006.
[9]王重钢.高速互联网中的队列调度及DiffServ结构中的流量控制技术[D].北京;北京邮电大学,2002.
[10]A.K.Parekh,R.G.Gallager.A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks;the Single-node Case[J].IEEE/ACM Trans Networking,1993,1(3);344-357.
[11]R.L.Cruz.Quality of Service Guarantees in Virtual Circuit Switched Networks[J].IEEE Journal on Selected Areas in Communications,1995,13(6);1048-1056.
[12]M.Katevenis,S.Sidiropoulos,C.Courcoubetis.Weighted Round-robin Cell Multiplexing in a General-purpose ATM Switch Chip[J].IEEE Journal on selected areas in communications,1991,9(8);1265-1279.
[13]M.Shreedhar,G.Varghese.Efficient Fair Queuing Using Deficit Round-robin[J].IEEE/ACM Transactions on networking,1996,4(3);375-385.
[14]D.C.Stephens,J.Bennett,Zhang Hui.Implementing Scheduling Algorithms in High-speed Networks[J].IEEE Journal on Selected Areas in Communications,1999,17(6);1145-1159.
[15]D.Stiliadis,A.Varma.Rate-proportional Servers;A Design Methodology for Fair Queuing Algorithms[J].IEEE/ACM Trans.on Networking,1998,6(2);164-173.
[16]S.Li,M.Lee.A Study of Traffic Imbalances in a Fast Packet Switch[A].In;Proc.IEEE INFOCOM'89[C],San Francisco,1989;538-547.
[17]Y.Tamir,G.Frazier.High Performance Multi-queue Buffers for VLSI Communications Switches[A].In;15th Annual Symposium on Computer Architectures[C],Hawaii, 1988:343-354.
[18] T. Anderson, S. Owicki, J. Saxe, et al. High-speed Switch Scheduling for Local-area Networks[J]. ACM Transactions on Computer Systems, 1993, 11(4):319-352.
[19] M. Ali, H. Nguyen. A Neural Network Implementation of an Input Access Scheme in a High-speed Packet Switch[A]. In: Proc. IEEE GLOBECOM'89[C], Dallas, 1989:1192-1196.
[20] Cisco Systems. Performing Internet Routing and Switching at Gigabit Speeds. GSR 12000 Tech. Product Description[EB/OL].: Cisco 公司官方网页, 2007-4-6.
[21] J. Hui, E. Arthurs. A Broadband Packet Switch for Integrated Transport[J]. IEEE J. Select. Areas Commun, 1987, 5:1264-1273.
[22] R. O. LaMaire, D. N. Serpanos. Two-dimensional Round-robin Schedulers for Packet Switches with Multiple Input Queues[J]. IEEE/ACM Trans. Networking, 1993,1:471-482.
[23] C. Lund, S. Phillips, N. Reingold. Fair Prioritized Scheduling in an Input-buffered Switch[A]. In: Proc. IFIPIEEE Conf. Broadband Commun'96[C], Montreal, 1996:358-369.
[24] N. McKeown, M. Izzard, A. Mekkittikul, et al. The Tiny Tera: A Small High-bandwidth Packet Switch Core[J]. IEEE Micro, 1997,17:26-33.
[25] Y. Tamir, H. C. Chi. Symmetric Crossbar Arbiters for VLSI Communication Switches[J]. IEEE Trans. Parallel Dist. Syst., 1993, 4:13-27.
[26] J. E. Hopcroft, R. M. Karp. An n~(5/2) Algorithm for Maximum Matching in Bipartite Graphs[J]. SIAM Journal on Computing, 1973, 1(2):225-231.
[27] A. Mekkittikul, N. McKeown. A Practical Scheduling Algorithm for Achieving 100% Throughput in Input-queued Switches[A]. In: Proc. IEEE INFOCOM'98[C], San Francisco, 1998: 792-799.
[28] N. McKeown. The iSLIP Scheduling Algorithm for Input-queued Switches[J]. IEEE/ACM Transactions on Networking, 1999, 7(2):188-201.
[29] D. Serpanos, P. Antoniadis. FIRM: A Class of Distributed Scheduling Algorithms for High-speed ATM Switches with Multiple Input Queues[A]. In: Proc. IEEE INFOCOM'00, Israel, 2000:548-555.
[30] H. J. Chao. Saturn: A Terabit Packet Switch Using Dual Round-robin[J]. IEEE Comm. Magazine, 2000, 38(12):78-84.
[31] H. J. Chao, J. Park. Centralized Contention Resolution Schemes for a Large-capacity Optical ATM Switch[A]. In: IEEE ATM Workshop[C], Fairfax, 1999:79-86.
[32] R. E. Tarjan. Data Structures and Network Algorithms[M]. Philadelphia: Society for Industrial and Applied Mathematics, 1983:112-234.
[33] A. Gupta, N. Georganas. Analysis of a Packet Switch with Input and Output Buffers and Speed Constraints[A]. In: Proc. IEEE INFOCOM'91[C], Bal Harbour, 1991:694-700.
[34] B. Prabhakar, N. McKeown. On the Speedup Required for Combined Input and Output Queued Switching[R]. California: Stanford University, 1997.
[35]N.McKeown,B.Prabhakar,M.Zhu.Matching Output Queueing with Combined Input and Output Queueing[A].In;Proc.35th Allerton Conference on Communication,Control and Computing[C],Illinois,1997;595-603.
[36]P.Krishna,N.Patel,A.Charny,et al.On the Speedup Required for Work-conserving Crossbar Switches[J].IEEE Journal on Selected Areas in Communications,1999,17(6);1057-1066.
[37]I.Stoica,H.Zhang.Exact Emulation of an Output Queueing Switch by a Combined Input Output Queueing Switch[A].In;Proc.IEEE/IFIP International Workshop on Quality of Services'98[C],Napa,1998;218-224.
[38]T.Javidi,R.Magill,T.Hrabik.A High-throughput Scheduling Algorithm for a Buffered Crossbar Switches Fabric[A].In;Proc.IEEE ICC'01[C],Helsinki,2001;1581-1587.
[39]T.Gormen,C.E.Leiserson,R.L.Rivest.Introduction to Algorithms[M].Cambridge;MIT Press,1990;135-140.
[40]Xiao Zhang,L.N.Bhuyan.An Efficient Algorithm for Combined Input-crosspoint-queued(CICQ)Switches[A].In;Proc.IEEE Globecom 2004[C],Dallas,2004;1168-1173.
[41]Lotfi Mhamdi,Mounir Hamdi.MCBF;A High-performance Scheduling Algorithm for Buffered Cossbar Switches[J].IEEE Communications Letters,2003,9;451-453.
[42]R.Rojas-Cessa,E.Oki,Z.Jing,et al.On the Combined Input-crosspoint Buffered Switch with Round-robin Arbitration[J].IEEE Trans.on Commun,2005,11;1945-1951.
[43]Z.J.Luo,Y.Lee,J.Wu.DRR;A Fast High-throughput Scheduling Algorithm for Combined Input-crosspoint-queued(CICQ)Switches[A].In Proc.IEEE MASCOTS'05[C],Atlanta,2005;329-332.
[44]Y.F.Zheng,C.Shao.An Efficient Round-Robin Algorithm for Combined Input-crosspoint-queued Switches[A].In;Proc.IEEE ICAS/ICNS 2005[C],Papeete,2005;23-28.
[45]S.J.Golestani.A Self-clocked Fair Queueing Scheme for Broadband Applications[A].In;Proc.IEEE INFICOM'94[C],Toronto,1994;636-646.
[46]J.C.R.Bennett,H.Zhang.WF2Q;Worst-case Fair Weighted Fair Queueing[A].In;Proc.IEEE INFICOM'9 6[C],San Francisco,1996;120-128.
[47]扈红超,伊鹏,郭云飞.高性能交换与调度仿真平台的设计与实现[J].软件学报,已录用.
[48]Z.Sheng,S.Q.Xie,C.Y.Pan.Probability Theory & Mathematical Statistics[M].Beijing;High Education Press,2004;157-180.
[49]B.Magill,C.Rohrs,R.Stevenson.Output-queued Switch Emulation by Fabrics with Limited Memory[J].IEEE Journal on Selected Areas in Communications,2003,21(4);606-615.
[50]S.Iyer,S.T.Chuang,N.McKeown.Practical Algorithms for Performance Guarantees in Buffered Crossbars[A].In;Proc.IEEE INFOCOM'05[C],Miami,2005;981-991.
[51]M.Lin,N.McKeown.The Throughput of a Buffered Crossbar Switch[J].IEEE Communications letters,2005,9(5);465-467.
[52]L.Mhamdi,M.Hamdi.Scheduling Multicast Traffic in Internally Buffered Crossbar Switches[A].In;Proc.IEEE ICC'04[C],Paris,2004;1103-1107.
[53]S.Sun,S.He,Y.Zheng,et al.Multicast Scheduling in Buffered Crossbar Switches with Multiple Input Queues[A].In Proc.IEEE HPSR'05[C],Hong Kong,2005;73-77.
[54]L.Mhamdi,S.Vassiliadis.Integrating Uni- and Multicast Scheduling in Buffered Crossbar Switches[A].In;Proc.IEEE HPSR'06[C],Poznan,2006;99-1046.
[55]X.Chen,J.F.Hayes.Cell Scheduling in Multicasting Packet Switching[A].In;Proc.IEEE ICC '92[C],New York,1992;895-899.
[56]B.Prabhakar,R.Ahuja,N.McKeown.Multicast Scheduling for Input-queued Switches[J].IEEE Journal on Selected Areas in Communications,1997,15(15);855-866.
[57]S.Gupta,A.Aziz.Multicast Scheduling for Switches with Multiple Queues[A].In;Proc.IEEE Hot Interconnects '02[C],Stanford,2002.
[58]A.Bianco,P.Giaccone,E.Leonardi,et al.On the Number of Input Queues to Efficiently Support Multicast Traffic in Input Queued Switches[A].In;Proc.IEEE HPSR'03[C],Torino,2003;111-116.
[59]张兴明.大规模接入汇聚路由器(ACR)总体技术规范[R].郑州;国家数字交换系统工程技术研究中心,2005.
[60]汪斌强.可扩展到T比特的高性能IPv4/IPv6路由器基础平台及实验系统总体实施方案-系统总体设计[R].郑州;国家数字交换系统工程技术研究中心,2005.
[61]XILINX.Virtex-Ⅱ Pro and Virtex-Ⅱ Pro X Complete Data Sheet[DB/OL].;XILINX官方网页,2007-03-05.
[2]S.Deering,R.Hinden.Internet Protocol,Version 6(IPv6)Specification.RFC2460[S].IETF,1998.
[3]A.Mekkittikul.Scheduling Non-uniform Traffic in High Speed Packet Switches and Routers[D].California;Stanford University,1998.
[4]N.McKeown.Scheduling Algorithms for Input-queued Cell Switches[D].Berkeley;University of California at Berkeley,1995.
[5]M.Karol,M.Hluchyj,S.Morgan.Input versus Output Queueing on a Space Division Packet Switch[J].IEEE Transactions on Communications,1987,35(12);1347-1356.
[6]V.Singhal,R.Le.High-speed Buffered Crossbar Switch Design Using Virtex-EM Devices[DB/OL].;Xinlinx 公司主页,2007-03-27.
[7]M.Nabeshima.Performance Evaluation of a Combined Input- and Crosspoint-queued Switch[J].IEICE Trans.Commun.,2000,E83-B(3);737-741.
[8]伊鹏.基于带缓存交叉开关的交换技术研究[D].郑州;信息工程大学,2006.
[9]王重钢.高速互联网中的队列调度及DiffServ结构中的流量控制技术[D].北京;北京邮电大学,2002.
[10]A.K.Parekh,R.G.Gallager.A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks;the Single-node Case[J].IEEE/ACM Trans Networking,1993,1(3);344-357.
[11]R.L.Cruz.Quality of Service Guarantees in Virtual Circuit Switched Networks[J].IEEE Journal on Selected Areas in Communications,1995,13(6);1048-1056.
[12]M.Katevenis,S.Sidiropoulos,C.Courcoubetis.Weighted Round-robin Cell Multiplexing in a General-purpose ATM Switch Chip[J].IEEE Journal on selected areas in communications,1991,9(8);1265-1279.
[13]M.Shreedhar,G.Varghese.Efficient Fair Queuing Using Deficit Round-robin[J].IEEE/ACM Transactions on networking,1996,4(3);375-385.
[14]D.C.Stephens,J.Bennett,Zhang Hui.Implementing Scheduling Algorithms in High-speed Networks[J].IEEE Journal on Selected Areas in Communications,1999,17(6);1145-1159.
[15]D.Stiliadis,A.Varma.Rate-proportional Servers;A Design Methodology for Fair Queuing Algorithms[J].IEEE/ACM Trans.on Networking,1998,6(2);164-173.
[16]S.Li,M.Lee.A Study of Traffic Imbalances in a Fast Packet Switch[A].In;Proc.IEEE INFOCOM'89[C],San Francisco,1989;538-547.
[17]Y.Tamir,G.Frazier.High Performance Multi-queue Buffers for VLSI Communications Switches[A].In;15th Annual Symposium on Computer Architectures[C],Hawaii, 1988:343-354.
[18] T. Anderson, S. Owicki, J. Saxe, et al. High-speed Switch Scheduling for Local-area Networks[J]. ACM Transactions on Computer Systems, 1993, 11(4):319-352.
[19] M. Ali, H. Nguyen. A Neural Network Implementation of an Input Access Scheme in a High-speed Packet Switch[A]. In: Proc. IEEE GLOBECOM'89[C], Dallas, 1989:1192-1196.
[20] Cisco Systems. Performing Internet Routing and Switching at Gigabit Speeds. GSR 12000 Tech. Product Description[EB/OL].: Cisco 公司官方网页, 2007-4-6.
[21] J. Hui, E. Arthurs. A Broadband Packet Switch for Integrated Transport[J]. IEEE J. Select. Areas Commun, 1987, 5:1264-1273.
[22] R. O. LaMaire, D. N. Serpanos. Two-dimensional Round-robin Schedulers for Packet Switches with Multiple Input Queues[J]. IEEE/ACM Trans. Networking, 1993,1:471-482.
[23] C. Lund, S. Phillips, N. Reingold. Fair Prioritized Scheduling in an Input-buffered Switch[A]. In: Proc. IFIPIEEE Conf. Broadband Commun'96[C], Montreal, 1996:358-369.
[24] N. McKeown, M. Izzard, A. Mekkittikul, et al. The Tiny Tera: A Small High-bandwidth Packet Switch Core[J]. IEEE Micro, 1997,17:26-33.
[25] Y. Tamir, H. C. Chi. Symmetric Crossbar Arbiters for VLSI Communication Switches[J]. IEEE Trans. Parallel Dist. Syst., 1993, 4:13-27.
[26] J. E. Hopcroft, R. M. Karp. An n~(5/2) Algorithm for Maximum Matching in Bipartite Graphs[J]. SIAM Journal on Computing, 1973, 1(2):225-231.
[27] A. Mekkittikul, N. McKeown. A Practical Scheduling Algorithm for Achieving 100% Throughput in Input-queued Switches[A]. In: Proc. IEEE INFOCOM'98[C], San Francisco, 1998: 792-799.
[28] N. McKeown. The iSLIP Scheduling Algorithm for Input-queued Switches[J]. IEEE/ACM Transactions on Networking, 1999, 7(2):188-201.
[29] D. Serpanos, P. Antoniadis. FIRM: A Class of Distributed Scheduling Algorithms for High-speed ATM Switches with Multiple Input Queues[A]. In: Proc. IEEE INFOCOM'00, Israel, 2000:548-555.
[30] H. J. Chao. Saturn: A Terabit Packet Switch Using Dual Round-robin[J]. IEEE Comm. Magazine, 2000, 38(12):78-84.
[31] H. J. Chao, J. Park. Centralized Contention Resolution Schemes for a Large-capacity Optical ATM Switch[A]. In: IEEE ATM Workshop[C], Fairfax, 1999:79-86.
[32] R. E. Tarjan. Data Structures and Network Algorithms[M]. Philadelphia: Society for Industrial and Applied Mathematics, 1983:112-234.
[33] A. Gupta, N. Georganas. Analysis of a Packet Switch with Input and Output Buffers and Speed Constraints[A]. In: Proc. IEEE INFOCOM'91[C], Bal Harbour, 1991:694-700.
[34] B. Prabhakar, N. McKeown. On the Speedup Required for Combined Input and Output Queued Switching[R]. California: Stanford University, 1997.
[35]N.McKeown,B.Prabhakar,M.Zhu.Matching Output Queueing with Combined Input and Output Queueing[A].In;Proc.35th Allerton Conference on Communication,Control and Computing[C],Illinois,1997;595-603.
[36]P.Krishna,N.Patel,A.Charny,et al.On the Speedup Required for Work-conserving Crossbar Switches[J].IEEE Journal on Selected Areas in Communications,1999,17(6);1057-1066.
[37]I.Stoica,H.Zhang.Exact Emulation of an Output Queueing Switch by a Combined Input Output Queueing Switch[A].In;Proc.IEEE/IFIP International Workshop on Quality of Services'98[C],Napa,1998;218-224.
[38]T.Javidi,R.Magill,T.Hrabik.A High-throughput Scheduling Algorithm for a Buffered Crossbar Switches Fabric[A].In;Proc.IEEE ICC'01[C],Helsinki,2001;1581-1587.
[39]T.Gormen,C.E.Leiserson,R.L.Rivest.Introduction to Algorithms[M].Cambridge;MIT Press,1990;135-140.
[40]Xiao Zhang,L.N.Bhuyan.An Efficient Algorithm for Combined Input-crosspoint-queued(CICQ)Switches[A].In;Proc.IEEE Globecom 2004[C],Dallas,2004;1168-1173.
[41]Lotfi Mhamdi,Mounir Hamdi.MCBF;A High-performance Scheduling Algorithm for Buffered Cossbar Switches[J].IEEE Communications Letters,2003,9;451-453.
[42]R.Rojas-Cessa,E.Oki,Z.Jing,et al.On the Combined Input-crosspoint Buffered Switch with Round-robin Arbitration[J].IEEE Trans.on Commun,2005,11;1945-1951.
[43]Z.J.Luo,Y.Lee,J.Wu.DRR;A Fast High-throughput Scheduling Algorithm for Combined Input-crosspoint-queued(CICQ)Switches[A].In Proc.IEEE MASCOTS'05[C],Atlanta,2005;329-332.
[44]Y.F.Zheng,C.Shao.An Efficient Round-Robin Algorithm for Combined Input-crosspoint-queued Switches[A].In;Proc.IEEE ICAS/ICNS 2005[C],Papeete,2005;23-28.
[45]S.J.Golestani.A Self-clocked Fair Queueing Scheme for Broadband Applications[A].In;Proc.IEEE INFICOM'94[C],Toronto,1994;636-646.
[46]J.C.R.Bennett,H.Zhang.WF2Q;Worst-case Fair Weighted Fair Queueing[A].In;Proc.IEEE INFICOM'9 6[C],San Francisco,1996;120-128.
[47]扈红超,伊鹏,郭云飞.高性能交换与调度仿真平台的设计与实现[J].软件学报,已录用.
[48]Z.Sheng,S.Q.Xie,C.Y.Pan.Probability Theory & Mathematical Statistics[M].Beijing;High Education Press,2004;157-180.
[49]B.Magill,C.Rohrs,R.Stevenson.Output-queued Switch Emulation by Fabrics with Limited Memory[J].IEEE Journal on Selected Areas in Communications,2003,21(4);606-615.
[50]S.Iyer,S.T.Chuang,N.McKeown.Practical Algorithms for Performance Guarantees in Buffered Crossbars[A].In;Proc.IEEE INFOCOM'05[C],Miami,2005;981-991.
[51]M.Lin,N.McKeown.The Throughput of a Buffered Crossbar Switch[J].IEEE Communications letters,2005,9(5);465-467.
[52]L.Mhamdi,M.Hamdi.Scheduling Multicast Traffic in Internally Buffered Crossbar Switches[A].In;Proc.IEEE ICC'04[C],Paris,2004;1103-1107.
[53]S.Sun,S.He,Y.Zheng,et al.Multicast Scheduling in Buffered Crossbar Switches with Multiple Input Queues[A].In Proc.IEEE HPSR'05[C],Hong Kong,2005;73-77.
[54]L.Mhamdi,S.Vassiliadis.Integrating Uni- and Multicast Scheduling in Buffered Crossbar Switches[A].In;Proc.IEEE HPSR'06[C],Poznan,2006;99-1046.
[55]X.Chen,J.F.Hayes.Cell Scheduling in Multicasting Packet Switching[A].In;Proc.IEEE ICC '92[C],New York,1992;895-899.
[56]B.Prabhakar,R.Ahuja,N.McKeown.Multicast Scheduling for Input-queued Switches[J].IEEE Journal on Selected Areas in Communications,1997,15(15);855-866.
[57]S.Gupta,A.Aziz.Multicast Scheduling for Switches with Multiple Queues[A].In;Proc.IEEE Hot Interconnects '02[C],Stanford,2002.
[58]A.Bianco,P.Giaccone,E.Leonardi,et al.On the Number of Input Queues to Efficiently Support Multicast Traffic in Input Queued Switches[A].In;Proc.IEEE HPSR'03[C],Torino,2003;111-116.
[59]张兴明.大规模接入汇聚路由器(ACR)总体技术规范[R].郑州;国家数字交换系统工程技术研究中心,2005.
[60]汪斌强.可扩展到T比特的高性能IPv4/IPv6路由器基础平台及实验系统总体实施方案-系统总体设计[R].郑州;国家数字交换系统工程技术研究中心,2005.
[61]XILINX.Virtex-Ⅱ Pro and Virtex-Ⅱ Pro X Complete Data Sheet[DB/OL].;XILINX官方网页,2007-03-05.