Abstract

A variety of applications with different QoS requirements are supported simultaneously in the high-speed packet-switched networks, packet scheduling algorithms play a critical role in guaranteeing the performance of routing and switching devices. This study presents a simple, fair, efficient and easily implementary scheduling algorithm, called Successive Minimal-weight Round Robin (SMRR). In each round, SMRR provides the same service opportunity, which is equivalent to the minimal weight of the current round, for all active data flows. On the basis of the concept of Latency-Rate (LR) servers, we obtain the upper bound on the latency of SMRR and WRR (Weighted Round Robin) respectively and the results indicate that SMRR makes a significant improvement on the latency bound in comparison to WRR. We also discuss the fairness and implementation complexity of SMRR and the theoretical analysis shows that SMRR preserves the good implementation complexity of O (1) with respect to the number of flows and has better fairness than WRR.

Keywords:

Complexity, high-speed networks, latency bound, minimal weight, packet scheduling, relative fairness, Weighted Round Robin (WRR),

References

1. Bennett, J.C.R. and H. Zhang, 1996. WF2Q: Worst-case fair weighted fair queueing. Proceedings of IEEE 15th Annual Joint Conference of the IEEE Computer Societies. Networking the Next Generation (INFOCOM '96). San Francisco, CA, pp: 120-128.
   
2. Cao, C., Y. Zhang and R. Chen, 2010. UWRR: A novel scheduling algorithm for self-similar multi-services in optical packet switching network. Proceedings of the 2010 Symposium on Photonics and Optoelectronic (SOPO 2010). Chengdu, China, pp: 1-4.
   CrossRef    
3. Demers, A., S. Keshav and S. Shenker, 1998. Design and analysis of a fair queuing algorithm. Proceedings of the ACM SIGCOMM. Austin, pp: 1-12.
   PMid:9512778    
4. Golestani, S.J., 1994. A self-clocked fair queuing scheme for broadband applications. Proceedings of IEEE INFOCOM'94. Toronto, pp: 636-646.
   
5. Goyal, P., H.M. Vin and H. Cheng, 1997. Start-time fair queueing: A scheduling algorithm for integrated services packet switched networks. IEEE T. Network., 5(5): 690-704.
   CrossRef    
6. Guo, C., 2001. SRR: An O (1) time complexity packet scheduler for flows in multi-service packet networks. Proceedings of the 2001 SIGCOMM. San Diego, CA, pp: 211-222.
   PMid:12541798    
7. He, M., D. Zhao and L. Bao, 2012. An energy-efficiency polling access control protocol for wireless sensor networks. CAAI T. Intell. Syst., 7(3): 265-270, (Chinese).
   
8. Hemant, M. and U. Madhow, 2003. Fair scheduling with tunable latency: A round robin approach. IEEE/ACM T. Network., 11(4): 592-601.
   CrossRef    
9. Hu, H., Y. Peng and Y. Guo, 2008. A fair service and dynamic round robin scheduling algorithm. J. Software, 19(7): 1856-1864, (Chinese).
   CrossRef    
10. Lin, D., Y. Jiang and M. Hamdi, 2011. Selective-request round-robin scheduling for VOQ packet switch architecture. Proceedings of the IEEE International Conference on Communications (ICC), pp: 1-5.
    CrossRef    
11. Pan, C. and J. Zhang, 2012. An improved queue scheduling algorithm based on WRR. Telecommun. Inform., 1: 34-37, (Chinese).
    
12. Parekh, A.K. and R.G. Gallager, 1992. A generalized processor sharing approach to flow control the single node case. Proceedings of INFOCOM'92. Florence, pp: 915-924.
    
13. Shreedhar, M. and G. Varghese, 1996. Efficient fair queueing using deficit round-robin. IEEE T. Network., 4(3): 375-385.
    CrossRef    
14. Stiliadis, D. and A. Verma, 1998. Latency-rate servers: A general model for analysis of traffic scheduling algorithms. IEEE-ACM T. Network., 6(5): 611-624.
    CrossRef    
15. Xiong, L. and S. Zhang, 2012. The optimization of the WRR algorithm in multi-class real-time data scheduling. Comput. Eng. Sci., 34(7): 35-38, (Chinese).
    
16. Zhang, L., 1990. Virtual clock: A new traffic control algorithm for packet switching networks. Proceedings of the ACM Symposium on Communications Architectures and Protocols (SIGCOMM '90). Philadelphia, pp: 19-29.
    CrossRef    
17. Zhang, X., G. Ni and F. Jin, 2011. A new WRR algorithm based on ideal packet interval time. Proceedings of the International Conference on Intelligent Computation Technology and Automation (ICICTA). Shenzhen, China, pp: 1039-1042.
    

Competing interests

The authors have no competing interests.

Open Access Policy

This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Copyright

The authors have no competing interests.