ROUND-ROBIN SCHEDULING FOR MAX MIN FAIRNESS IN DATA-NETWORKS

This paper studies a simple strategy, proposed independently by Gallager [1] and Katevenis [2], for fairly allocating link capacity in a point-to-point packet network with virtual circuit routing. Each link offers its packet transmission slots to its user sessions by polling them in round-robin order. In addition, window flow control is used to prevent excessive packet queues at the network nodes. As the window size increases, the session throughput rates are shown to approach limits that are perfectly fair in the max-min sense. That is, the smallest session rate in the network is as large as possible and, subject to that constraint, the second-smallest session rate is as large as possible, etc. If each session has periodic input (perhaps with jitter) or has such heavy demand that packets are always waiting to enter the network, then a finite window size suffices to produce perfectly fair throughput rates. The round-robin method is considerably simpler than earlier strategies for achieving global fairness. The fair session rates are not explicitly computed, and the only overhead communication is that required for the window acknowledgments. The main drawback is that large windows are needed to achieve even approximately fair throughputs in some (hopefully rare) situations, and large windows permit large crossnetwork delays. Fortunately, the round-robin method offers other throughput guarantees that, while falling short of perfect fairness, do apply even for sessions with small windows. Such sessions are promised reasonable bounds on their crossnetwork packet delay as well.