Approximate Sorting of Packet-Scheduling in High-Speed Networks

Fairness, latency and computational complexity are three importantfactors in evaluating the performance of a scheduling algorithm. Fairnessmust be satisfied so that service can be distributed according to thereserved rate. Only when latency is irrelevant to the number ofconnections, is it possible to minimize the end-to-end delay throughcontrolling the reserved rate. Among existing scheduling algorithms,Round Robin is the least complex. However, conventional Round Robin isunable to ensure fairness, and the improved round robin algorithms likeDeficit Round Robin, Weighted Round Robin and Virtual Round Robin areunable to ensure that their latencies are irrelevant to the number ofconnections although they guarantee fairness. Potential Round Robindeveloped for analysis of fairness and latency reduction is thusproposed. It is based on the introduction of a new concept, RoundPotential Function. The function splits service time into a number ofservice round periods to guarantee fairness regardless of the servingprocess used in the period. In the analysis of latency, service roundperiods are re-split into multiple scanning cycles for further servicedistribution with approximate sorting between scanning cycles. As aresult, latency is no longer relevant to the number of connectionswhile the low complexity of round robin is kept.