Algorithms for Generalized Round Robin routing

This paper presents new algorithms to construct a Generalized Round Robin routing sequence for distributing one stream of traffic to multiple queues. The performance objective is to minimize the expected delay. Given a target allocation in terms of the fraction of jobs that should be routed to each queue, the algorithms scan the queues in order of descending fraction and assign the next job to the first queue with current allocation not exceeding an easily computed threshold. The authors prove that the constructed sequence has properties related to Hajek’s most regular sequence; in particular, it is optimal for the case of two queues. Simulation results show improvement over Itai-Rosberg’s Golden Ratio Rule and come very close to a lower bound obtained by Hajek.