Efficient fair queueing for ATM networks using uniform round robin

Abstract

In this paper, we investigate 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. Therefore a 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, their delay bounds achieved by H-WRR are close to those of weighted fair queueing.