基于iSLIP算法的FIFO特性研究
|
摘要
交换结构是路由器和交换机中的关键部分,在如何保证服务质量QoS (Quality of Service)的前提下进行高速转发,是近年来网络研究的一个热点。相关的调度算法负责将输入端口的信元通过交换内核发送至输出端口,所以它在提高交换设备的带宽利用率和服务质量方面起着关键性作用。iSLIP算法是一个经典的调度算法,主要用来解决路由器交换结构调度问题,它具有高的吞吐率,良好的时延特性,并且易于在硬件上实现,在实际中广泛应用,同时也是当今学者研究的热点。
论文首先对交换机的交换结构和排队结构进行了介绍,主要是对输入排队结构和交叉开关(Crossbar)交换结构进行了重点阐述。接下来对现有的典型分组调度算法PIM、RRM和iSLIP等算法进行阐述,揭示了每种算法的调度过程和优缺点,特别是iSLIP算法,将对其性能进行深入分析。
先来先出机制FIFO (First In First Out)在很多场合是一种基本要求,可以看作是一个最基本的QoS指标。比如同一优先级的数据,一般要求先来先服务。我们通过深入分析iSLIP算法的调度过程,揭示该算法不能保证FIFO要求,因此提出了改进算法：FIFO-iSLIP算法。此改进算法在保持iSLIP算法原有优先级调度机制的同时又能保证FIFO特性,确保业务实时有序的传输,而不会过多地增加原算法的复杂性。文章对FIFO-iSLIP算法进行构想设计,并对性能进行分析计算,尤其是传输时延等指标。同时把性能与纯粹的iSLIP算法进行对比。从理论上分析了许多时候FIFO-iSLIP算法可以进一步降低业务的时延。当然,对FIFO-iSLIP算法的不足也进行了探求。
为了验证FIFO-iSLIP算法,我们花大力气剖析了由斯坦福大学开发的网络仿真软件SIM。利用SIM仿真软件对上述算法进行仿真实现,通过对不同流量模型和不同端口数目的交换机进行模拟仿真,同时对iSLIP算法也进行仿真,得到一系列的数据。仿真结果表明了理论分析的正确性。
A switching structure is a crucial element of routers and switches. How to obtain a high transmitting speed while guaranteeing QoS (Quality of Service) is a hot topic of network research in recent years. The scheduling algorithms of switch fabric are responsible for transferring the cells from input port to output port, therefore it plays a crucial role in improving the bandwidth utilization and quality of service of switch devices. The iSLIP algorithm, a classical scheduling algorithm used to solve the scheduling problems of high-speed router and switch fabric, has a high throughput, good latency characteristics, easy in hardware implementation, and being used widely in practice. it is also a hot spot of today's researches.
This paper first describes the switch fabric and queuing structure, focusing on describing the practical application of a broader structure of the input queue and cross-switch fabric, then describes some existing packet scheduling algorithms such as PIM, RRM, and iSLIP, revealing their scheduling processes, advantages and disadvantages. An in-depth analysis for the performance of iSLIP is especially made.
FIFO(First In First Out)is a basic requirement can be seen as a basic QoS requirement on many occasions. For example, businesses with same priority generally require FIFO services. Through the in-depth analysis in the scheduling process of the iSLIP algorithm, it is found that the algorithm can not guarantee the FIFO requirement and therefore a new FIFO-iSLIP algorithm is proposed. This improved algorithm maintains the original iSLIP priority scheduling mechanism and at the same time ensures the FIFO feature, ensuring an orderly transfer for real-time businesses, without too much increase in the complexity of the original algorithm. This article provides the design of the FIFO-iSLIP algorithm and the analyses of performances (especially the transmission delay), and compares them with the iSLIP algorithm. Through theoretical analysis it is found that the FIFO-iSLIP algorithm can further reduce the latency on many occasions, especially for light-load businesses. Of course, the disadvantages of FIFO-iSLIP algorithm are also explored.
In order to verify the FIFO-iSLIP algorithm, we spent a great effort on analyzing the network simulation software SIM developed by the Stanford University. With different flow models and different number of ports, we use this simulation tool to simulate the FIFO-iSLIP algorithm and the iSLIP algorithm.The simulation results prove the above theoretical analysis.
论文首先对交换机的交换结构和排队结构进行了介绍,主要是对输入排队结构和交叉开关(Crossbar)交换结构进行了重点阐述。接下来对现有的典型分组调度算法PIM、RRM和iSLIP等算法进行阐述,揭示了每种算法的调度过程和优缺点,特别是iSLIP算法,将对其性能进行深入分析。
先来先出机制FIFO (First In First Out)在很多场合是一种基本要求,可以看作是一个最基本的QoS指标。比如同一优先级的数据,一般要求先来先服务。我们通过深入分析iSLIP算法的调度过程,揭示该算法不能保证FIFO要求,因此提出了改进算法：FIFO-iSLIP算法。此改进算法在保持iSLIP算法原有优先级调度机制的同时又能保证FIFO特性,确保业务实时有序的传输,而不会过多地增加原算法的复杂性。文章对FIFO-iSLIP算法进行构想设计,并对性能进行分析计算,尤其是传输时延等指标。同时把性能与纯粹的iSLIP算法进行对比。从理论上分析了许多时候FIFO-iSLIP算法可以进一步降低业务的时延。当然,对FIFO-iSLIP算法的不足也进行了探求。
为了验证FIFO-iSLIP算法,我们花大力气剖析了由斯坦福大学开发的网络仿真软件SIM。利用SIM仿真软件对上述算法进行仿真实现,通过对不同流量模型和不同端口数目的交换机进行模拟仿真,同时对iSLIP算法也进行仿真,得到一系列的数据。仿真结果表明了理论分析的正确性。
A switching structure is a crucial element of routers and switches. How to obtain a high transmitting speed while guaranteeing QoS (Quality of Service) is a hot topic of network research in recent years. The scheduling algorithms of switch fabric are responsible for transferring the cells from input port to output port, therefore it plays a crucial role in improving the bandwidth utilization and quality of service of switch devices. The iSLIP algorithm, a classical scheduling algorithm used to solve the scheduling problems of high-speed router and switch fabric, has a high throughput, good latency characteristics, easy in hardware implementation, and being used widely in practice. it is also a hot spot of today's researches.
This paper first describes the switch fabric and queuing structure, focusing on describing the practical application of a broader structure of the input queue and cross-switch fabric, then describes some existing packet scheduling algorithms such as PIM, RRM, and iSLIP, revealing their scheduling processes, advantages and disadvantages. An in-depth analysis for the performance of iSLIP is especially made.
FIFO(First In First Out)is a basic requirement can be seen as a basic QoS requirement on many occasions. For example, businesses with same priority generally require FIFO services. Through the in-depth analysis in the scheduling process of the iSLIP algorithm, it is found that the algorithm can not guarantee the FIFO requirement and therefore a new FIFO-iSLIP algorithm is proposed. This improved algorithm maintains the original iSLIP priority scheduling mechanism and at the same time ensures the FIFO feature, ensuring an orderly transfer for real-time businesses, without too much increase in the complexity of the original algorithm. This article provides the design of the FIFO-iSLIP algorithm and the analyses of performances (especially the transmission delay), and compares them with the iSLIP algorithm. Through theoretical analysis it is found that the FIFO-iSLIP algorithm can further reduce the latency on many occasions, especially for light-load businesses. Of course, the disadvantages of FIFO-iSLIP algorithm are also explored.
In order to verify the FIFO-iSLIP algorithm, we spent a great effort on analyzing the network simulation software SIM developed by the Stanford University. With different flow models and different number of ports, we use this simulation tool to simulate the FIFO-iSLIP algorithm and the iSLIP algorithm.The simulation results prove the above theoretical analysis.
引文
[1]MCKEOWN,N. Scheduling algorithm for input-queued cell switches [D]. USA:UC Berkeley,1995:56-58.
[2]刘东钢,候紫峰.一种基于输入队列的交换机快速会聚调度算法[J].计算机工程与应用,2002(6)：150-153.
[3]Yuanyuang Yang&Deng Pan.Hardware Efficient Two Step Iterative Matching Algorithms for VOQ Swtiches[J].Proceedings of 12th International Conference on Parallel and Distributed Systems, 2006,(1):431-438.
[4]McKeown,N.The iSLIP Scheduling Algorithm for Input-Queued Switches [J]. IEEE/ACM Transactions on Networking,1999,7(2): 21-23.
[5]江勇,吴建平,徐恪.高性能交换体系结构及其调度算法分析[J].电子学报,2000(2)：4-8.
[6]Karol,M.J.&M.G.Hluchy.Morgan.Input vs.output queuing on a space division packet switch[J].IEEETrans.Communication,1988,35(12): 1347-1356.
[7]Dinic E.A. Algorithm for a solution of a problem of maximum flow in a network with power estimation[J]. Soviet Math Dokl,1970, (11):1277-1280.
[8]Floyd S.Random Early Detection Gateways for Congestion Avidance[J]..IEEE/ACM Transaction on Networking,1998,1(11): 397-413.
[9]Dinic E.A. Algorithm for a solution of a problem of maximum flow in a network with power estimation[J]. Soviet Math Dokl, 1970,(11):1456-1462.
[10]Kelly F.P. Effective bandwidths at multiclass queues[J]. Queuing Systems Theory and Applications,1991,(9):5-15.
[11]Keshav S. On the efficient implementation of fair queueing[J]. Internet working: Research and Experience,1991,(3):157-173.
[12]Kesidis GEffective bandwidths for multiclass Markov fluids and other ATM sources [J]. IEEE/ACM Transactions on Networking, 1993, (4):424-428.
[13]Zhang H. Comparison of rate-based service disciplines[J]. Computer local-area networks,1993,(11):319-352.
[14]Zhang L. A New Traffic Control Algorithm for Packet Swithing Networks [J]. ACM Transactions on Computer Systems,1991, (9): 101-124.
[15]Hreedhar.M. S & G. Varghese. Efficient fair queuing using deficit round robin[J]. IEEE/ACM Transaction on Networking,1996, (4): 375-385.
[16]吴建平,熊勇强,徐恪.宽带IP路由器的体系结构分析[J].软件学报,2000,11(2)：179-186.
[17]谢希仁.计算机网络(第四版)[M].北京：电子工业出版社,2003：170-174.
[18]Shimonishi H& M Yoshida. An improvement of weighted round robin cell scheduling in ATM networks [A]. In D.Freeman and J.C.Richards (eds.). Proc of IEEE Globecom'97[C].Urbana: University of Illinois Press,1997,pp.1119-1123.
[19]Shreedhar M, & G Varghese. Efficient fair queuing using deficit round-robin[J]. IEEE Trasactions on Networking,1996,4(3):375-385.
[20]Chiopalkatti R. Scheduling policies for real-time and non-real-time traffic in a statistical multiplexer [A].In:IEEE INFOCOM'89[C]. New York:Cambridge University Press.1989,pp.74-78.
[21]Parekh, Gallager R. A generalized processor sharing approach to flow control in integrated services networks. The single node case[A]. IEEE INFOCOM'92[C], New York:Cambridge University Press,1993,pp:344-357.
[22]Liu, Lay land J. Scheduling algorithms for multiprogramming in a hard real-time environment[J]. Journal of ACM,1973,20(1):46-61.
[23]杨强.基于最高优先级调度的iSLIP算法[D].长沙：湖南师范大学,2009：15-16.
[24]孙志刚.路由器高速交换开关调度算法的研究与实现[D].长沙：国防科学技术大学研究生院,2000：14-20.
[25]林闯,单志广,盛立杰,吴建平.区分服务及其几个热点问题的研究[J].计算机学报,2000(4)：419-433.
[26]Gee Nong, Jogrsh K. Analysis of non-blocking ATM switches with multiple input queues[J].IEEE/ACM Transactions on Networking, 1999,7(1):60-63.
[27]Anderson, T. High-speed switch scheduling for local-area networks [J]. ACM Transactions on Computer Systems,1993,(13):319-352.
[28]刘尉悦.高性能交换技术的研究[D].合肥：中国科学技术大学,2002：49-64.
[29]McKeown,N. The iSLIP Scheduling Algorithm for Input-Queued Switches [J]. IEEE/ACM Transactions on Networking,1999,7(2): 21-23.
[30]钱光明.一个实时与尽力服务并存的队列调度方案[J].计算机工程与应用,2007,43(17)：143-145.
[31]SIM manual[EB/OL]. http://klamath.stanford.edu/tools/SIM.
[32]The Chaos Router Simulator[EB/OL]. http://www.cs.washington.edu/research/projects/lis/chaos/www/simul ator.html.
[33]Sicosys simulator for communication systems[EB/OL]. http://www.atc.unican.es/SICOSYS.
[34]Mitko Gospodinov, Evgeniya Gospodinova. Analysis of iSLIP scheduling algorithm for input-queuing switches [A]. International Conference on Computer Systems and Technologies - CompSys Tech' 2004 [C]. Urbana: University of Illinois Press,1991, pp.201-213.
[2]刘东钢,候紫峰.一种基于输入队列的交换机快速会聚调度算法[J].计算机工程与应用,2002(6)：150-153.
[3]Yuanyuang Yang&Deng Pan.Hardware Efficient Two Step Iterative Matching Algorithms for VOQ Swtiches[J].Proceedings of 12th International Conference on Parallel and Distributed Systems, 2006,(1):431-438.
[4]McKeown,N.The iSLIP Scheduling Algorithm for Input-Queued Switches [J]. IEEE/ACM Transactions on Networking,1999,7(2): 21-23.
[5]江勇,吴建平,徐恪.高性能交换体系结构及其调度算法分析[J].电子学报,2000(2)：4-8.
[6]Karol,M.J.&M.G.Hluchy.Morgan.Input vs.output queuing on a space division packet switch[J].IEEETrans.Communication,1988,35(12): 1347-1356.
[7]Dinic E.A. Algorithm for a solution of a problem of maximum flow in a network with power estimation[J]. Soviet Math Dokl,1970, (11):1277-1280.
[8]Floyd S.Random Early Detection Gateways for Congestion Avidance[J]..IEEE/ACM Transaction on Networking,1998,1(11): 397-413.
[9]Dinic E.A. Algorithm for a solution of a problem of maximum flow in a network with power estimation[J]. Soviet Math Dokl, 1970,(11):1456-1462.
[10]Kelly F.P. Effective bandwidths at multiclass queues[J]. Queuing Systems Theory and Applications,1991,(9):5-15.
[11]Keshav S. On the efficient implementation of fair queueing[J]. Internet working: Research and Experience,1991,(3):157-173.
[12]Kesidis GEffective bandwidths for multiclass Markov fluids and other ATM sources [J]. IEEE/ACM Transactions on Networking, 1993, (4):424-428.
[13]Zhang H. Comparison of rate-based service disciplines[J]. Computer local-area networks,1993,(11):319-352.
[14]Zhang L. A New Traffic Control Algorithm for Packet Swithing Networks [J]. ACM Transactions on Computer Systems,1991, (9): 101-124.
[15]Hreedhar.M. S & G. Varghese. Efficient fair queuing using deficit round robin[J]. IEEE/ACM Transaction on Networking,1996, (4): 375-385.
[16]吴建平,熊勇强,徐恪.宽带IP路由器的体系结构分析[J].软件学报,2000,11(2)：179-186.
[17]谢希仁.计算机网络(第四版)[M].北京：电子工业出版社,2003：170-174.
[18]Shimonishi H& M Yoshida. An improvement of weighted round robin cell scheduling in ATM networks [A]. In D.Freeman and J.C.Richards (eds.). Proc of IEEE Globecom'97[C].Urbana: University of Illinois Press,1997,pp.1119-1123.
[19]Shreedhar M, & G Varghese. Efficient fair queuing using deficit round-robin[J]. IEEE Trasactions on Networking,1996,4(3):375-385.
[20]Chiopalkatti R. Scheduling policies for real-time and non-real-time traffic in a statistical multiplexer [A].In:IEEE INFOCOM'89[C]. New York:Cambridge University Press.1989,pp.74-78.
[21]Parekh, Gallager R. A generalized processor sharing approach to flow control in integrated services networks. The single node case[A]. IEEE INFOCOM'92[C], New York:Cambridge University Press,1993,pp:344-357.
[22]Liu, Lay land J. Scheduling algorithms for multiprogramming in a hard real-time environment[J]. Journal of ACM,1973,20(1):46-61.
[23]杨强.基于最高优先级调度的iSLIP算法[D].长沙：湖南师范大学,2009：15-16.
[24]孙志刚.路由器高速交换开关调度算法的研究与实现[D].长沙：国防科学技术大学研究生院,2000：14-20.
[25]林闯,单志广,盛立杰,吴建平.区分服务及其几个热点问题的研究[J].计算机学报,2000(4)：419-433.
[26]Gee Nong, Jogrsh K. Analysis of non-blocking ATM switches with multiple input queues[J].IEEE/ACM Transactions on Networking, 1999,7(1):60-63.
[27]Anderson, T. High-speed switch scheduling for local-area networks [J]. ACM Transactions on Computer Systems,1993,(13):319-352.
[28]刘尉悦.高性能交换技术的研究[D].合肥：中国科学技术大学,2002：49-64.
[29]McKeown,N. The iSLIP Scheduling Algorithm for Input-Queued Switches [J]. IEEE/ACM Transactions on Networking,1999,7(2): 21-23.
[30]钱光明.一个实时与尽力服务并存的队列调度方案[J].计算机工程与应用,2007,43(17)：143-145.
[31]SIM manual[EB/OL]. http://klamath.stanford.edu/tools/SIM.
[32]The Chaos Router Simulator[EB/OL]. http://www.cs.washington.edu/research/projects/lis/chaos/www/simul ator.html.
[33]Sicosys simulator for communication systems[EB/OL]. http://www.atc.unican.es/SICOSYS.
[34]Mitko Gospodinov, Evgeniya Gospodinova. Analysis of iSLIP scheduling algorithm for input-queuing switches [A]. International Conference on Computer Systems and Technologies - CompSys Tech' 2004 [C]. Urbana: University of Illinois Press,1991, pp.201-213.