Efficient Fair Queueing for ATM Network Using Uniform Round Robin

概要

論文の詳細を見る
In this paper, we study efficient scheduling algorithms that are suitable for ATM networks.In ATM networks, all packets have a fixed small length of 53 bytes and they are transmitted at very high rate. Thus time complexity of a scheduling algorithm is quite important. Most scheduling algorithms proposed so far have a complexity of O(log N)per packet, where N denotes the number of connections sharing the link. In contrast, weighted round robin(WRR)has the advantage of having O(1)complexity; however, it is known that its delay property gets worse as N increases. To solve this problem, in this paper we propose two new variants of WRR, uniform round robin(URR)and idling uniform round robin(I-URR).Both disciplines provide end-to-end delay and fairness bounds which are independent of N. Complexity of URR, however, slightly increases as N increases, while I-URR has complexity of O(1)per packet. I-URR also works as a traffic shaper, so that it can significantly alleviate congestion on the network. We also introduce a hierarchical WRR discipline(H-WRR)which consists of different WRR servers using I-URR as the root server. H-WRR efficiently accommodates both guaranteed and best-effort connections, while maintaining O(1)complexity per packet. If several connections are reserving the same bandwidth, H-WRR provides them with delay bounds that are close to those of weighted fair queueing.
社団法人電子情報通信学会の論文
2000-06-25