一种基于紧急程度的自时钟开始时间公平排队分组调度算法

刘文波; 郭云飞; 马海龙

doi:10.3724/SP.J.1146.2009.00781

一种基于紧急程度的自时钟开始时间公平排队分组调度算法

doi: 10.3724/SP.J.1146.2009.00781

计量
- 文章访问数: 3417
- HTML全文浏览量: 84
- PDF下载量: 698
- 被引次数: 0
出版历程
- 收稿日期: 2009-05-22
- 修回日期: 2009-10-08
- 刊出日期: 2010-06-19

An Urgency Based Self-clock Start-Time Fair Queuing Packet Scheduling

摘要

摘要: 为了克服目前GPS (Generalized Processor Sharing)类调度算法中实时应用分组的排队时延较大且不稳定的局限性，该文提出一种新的分组排队调度算法，该调度算法在计算分组服务标签时添加了一个紧急程度函数，调整了到达分组间的竞争关系，从而可以按照实时性应用的要求来调整到达分组的转发先优级，由此显著降低了实时性应用分组的排队时延和抖动幅度。分析和仿真实验表明，与GPS类其它调度算法相比，该调度算法对于实时应用的分组能提供较低的、更稳定的排队时延保证，同时还继承了GPS类算法的公平性和排队时延有界等特性，而且对系统虚拟时间的跟踪计算更为简捷高效。
- 分组排队调度; 紧急程度函数; 排队时延; 公平性; 系统虚拟时间
Abstract: In order to get over the limitation of the GPS(Generalized Processor Sharing) like queuing algorithms which the bound of the queuing delay is so long and unstable that is undesirable for the packets of real-time applications, a new packet queuing and scheduling algorithm is proposed. In this algorithm the competitions of the arrival packets are fine-tuned by means of adding a function of flow urgency degree on the computation of their service tags, so the transmitting priorities of the arrival packets can be tuned according to their real-time applications needs, therefore the queuing delay and the bounds of oscillation are cut down significantly. According as the analysis and the simulation, this packet queuing and scheduling algorithm can resolve the long and unstable packet latencies problem for real-time applications, and shares both the bounded-delay and fairness properties of the GPS like algorithms, and the computation of its system virtual time is simple and efficient.

HTML全文

参考文献(1)

Parekh A K. A generalized processor sharing approach to flow control in integrated services networks. [Ph.D. dissertation], Dept. Elec. Eng. Comput. Sci., MIT, 1992.[2]Bennett J C and Zhang H. WF2Q: Worst-case fair weighted fair queueing[J].Proceedings of IEEE INFOCOM96, San Francisco, Mar.1996, Vol. 1:120-128[3]Golestani S J. A self-clocked fair queueing scheme for broadband applications. Proceedings of IEEE INFOCOM94, Toronto, CA, April 1994: 636-646.[4]Goyal P, Vin H M, and Chen H. Start-time fair queuing: A scheduling algorithm for integrated services. Proceedings of the ACM-SIGCOMM96, Palo Alto, CA, August 1996: 157-168.[5]Shreedhar M and Varghese G. Efficient fair queuing using deficit round robin[J].IEEE/ACM Transactions on Networking.1996, 4(3):375-385[6]Kanhere S S and Sethu H. Fair, efficient and low latency packet scheduling using nested deficit round robin. Proceedings of the IEEE Workshop on High Performance Switching and Routing, Dallas, TX, May 2001: 6-10.[7]Zhao Q and Xu J. On the computational complexity of maintaining GPS clock in packet scheduling[J].Proceedings of IEEE INFOCOM04, Hong Kong, Mar.2004, Vol. 4:2383-2392[8]Gebali F. Analysis of Computer and Communication Networks. 1st edition, Berlin: Springer, 2008: 449-467.[9]Akesson B, Steffens L,and Strooisma E,et al.. Real-time scheduling using credit- controlled static-priority arbitration. Proceedings of IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, Kaohsiung, Taiwan, Aug. 2008: 3-14.[10]Bredel M and Fidler M. Understanding fairness and its impact on quality of service in IEEE 802.11. Proceedings of IEEE INFOCOM09, Rio de Janeiro, Brazil, April. 2009: 1669-1677.

施引文献

资源附件(0)

访问统计