
For FullText 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
Publication
IEICE TRANSACTIONS on Communications
Vol.E83B
No.6
pp.13301341 Publication Date: 2000/06/25 Online ISSN:
DOI: Print ISSN: 09168516 Type of Manuscript: PAPER Category: Switching Keyword: ATM switch, weighted round robin, slot assignment algorithm, hierarchical scheduling discipline,
Full Text: PDF>>
Summary:
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 (IURR). Both disciplines provide endtoend delay and fairness bounds which are independent of N. Complexity of URR, however, slightly increases as N increases, while IURR has complexity of O(1) per packet. IURR also works as a traffic shaper, so that it can significantly alleviate congestion on the network. We also introduce a hierarchical WRR discipline (HWRR) which consists of different WRR servers using IURR as the root server. HWRR efficiently accommodates both guaranteed and besteffort connections, while maintaining O(1) complexity per packet. If several connections are reserving the same bandwidth, HWRR provides them with delay bounds that are close to those of weighted fair queueing.

