A Constant Complexity Fair Scheduler with O(log N) Delay Guarantee

摘要

Many Internet multimedia applications require the support of network services with fairness and delay guarantees. Currently, there are two types of fair schedulers in the literature. The time stamp based schedulers achieve good fairness and delay guarantees but have high O(log N) time complexity, where N is the number of incoming flows. While the round robin based schedulers reach O(1) complexity, their delay guarantees are O(N). Aiming at constant time complexity as well as good fairness and delay guarantees, we design a new fair scheduler suitable for variable length packets in this paper. Fast Credit Based (FCB) fair scheduling, the algorithm we propose, provides O(log N) fairness and delay guarantees, by tracking and minimizing the difference between the service a flow reserves and that it actually receives. It reduces the time complexity to O(1) by utilizing approximation and synchronization. To compare FCB with other fair schedulers on their end-to-end delay performance, simulations are conducted in NS2 for various packet lengths, and the results show that FCB achieves short end-to-end delay and handles variable length packets efficiently.