Efficient fair queueing for ATM networks using uniform round robin

In this paper, we study efficient scheduling algorithms that are suitable f or 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 o f a scheduling algorithm is quite important, Most scheduling algorithms pro posed so far have a complexity of O(logN) per packet, where N denotes the n umber of connections sharing the link. In contrast. weighted round robin (W RR) 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 thi s paper we propose two new variants of WRR, uniform round robin (URR) and i dling uniform round robin (I-URR). Both disciplines provide end-to-end dela y and fairness bounds which are independent of N. Complexity of URR, howeve r, slightly increases as N increases. while I-URR has: complexity of O(1) p er packet. I-URR also works as a traffic shaper, so that it can significant ly alleviate congestion on the network. We also introduce a hierarchical WR R discipline (H-WRR) which consists of different WRR servers using I-URR as the root server. H-WRR efficiently accommodates both guaranteed and best-e ffort connections, while maintaining O(1) complexity per packet. If several connections are reserving the same bandwidth, H-WRR provides them with del ay bounds that are close to those of weighted fair queueing.