一种合理共享空闲带宽的分组调度算法

随着计算机网络技术的发展，分组调度算法越来越受到广泛重视。提出了一种能够在交换机和路由器中合理共享输出链路空闲带宽的分组调度算法。该算法克服了目前分组调度算法对链路空闲带宽使用不合理的现象。它能够动态地寻找系统中存在的空闲带宽，并根据各个连接的实际需要公平合理地分配空闲带宽，从而能够在确保满足网络中所有业务时延的要求的同时有效地改善突发强度高的业务和尽力传送业务的时延性能。在衡量调度算法的各项指标（包括时延、公平性、复杂度）中，该算法都接近或达到了目前已知的最佳性能，理论分析和仿真结果表明，该算法是一种综合性能较理想的分组调度算法。

A Fair Packet Scheduling Algorithm Based on Reasonably Sharing the Free Bandwidth

With the rapid development of computer networks, the packet scheduling algorithm plays a key role in guaranteeing the quality of service for different traffic. So it attracts more and more attentions. However in most scheduling algorithms, the excess bandwidth in the system is not reasonably used which make the resource of network be wasted and the delay performance of bursty traffic be decreased. A new packet scheduling algorithm is proposed in this paper to overcome such shortcoming.This new algorithm can find dynamic excess bandwidth in the system. It is proved when there is excess bandwidth in the system there must be free slots. Free slots appears when all connections' basic delay requirements are met. Free slots are used to distribute excess bandwidth. Two servers are used in this algorithm. One works in the normal case to guarantee the connections' basic requirements, the other works when free slots appears to distribute excess bandwidth. In order to prevent one connection from occupying the whole excess bandwidth, a notation named previous wait time is introduced. The role of previous wait time is to make excess bandwidth be fairly shared by all the connections sharing the output link.The main advantage of this algorithm is that it can guarantee the delay requirements of all kinds of traffic and improve the delay property of bursty traffic and best effort traffic. Other main properties of this algorithm including delay, fairness and complexity are almost optimal compared with the algorithms known . Theoretical and simulation results show this algorithm has ideal performance.