For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Efficient Fair Queueing for ATM Networks Using Uniform Round Robin
Norio MATSUFURU Kouji NISHIMURA Reiji AIBARA
IEICE TRANSACTIONS on Communications
Publication Date: 2000/06/25
Print ISSN: 0916-8516
Type of Manuscript: PAPER
ATM switch, weighted round robin, slot assignment algorithm, hierarchical scheduling discipline,
Full Text: PDF>>
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.