Credit based fair scheduling for packet switched networks

With the rapid development of Internet multimedia applications, the next generation of networks is required to schedule not only the best effort traffic but also the traffic with bandwidth and delay guarantees. Currently, there are two types of fair scheduling algorithms in the literature. The time stamp based schedulers achieve very good fairness and delay guarantees but have high O(log N) time complexity, where N is the number of flows. While the round robin based schedulers reach O(1) time complexity, their delay guarantees are O(N). This paper aims at a fair scheduling algorithm with constant time complexity as well as good fairness and delay guarantees. We first present a credit/balance based fair scheduling algorithm called Most Credit First (MCF). We theoretically prove that MCF can provide O(log N) fairness, delay and delay jitter guarantees, and demonstrate experimentally that it actually can achieve O(1) guarantees. In order to reduce the O(log N) time complexity of MCF, we further present a more efficient variant of MCF, called Fast Most Credit First (FMCF). FMCF achieves O(1) time complexity by utilizing approximation and synchronization, and at the same time preserves the O(log N) theoretical fairness, delay and delay jitter guarantees of MCF. We also implemented MCF and FMCF in NS2 simulator to compare the end to end delay performance with other fair scheduling algorithms. Our experimental results demonstrate that MCF outperforms two commonly used fair schedulers, and FMCF is able to closely match the performance of MCF with reduced time complexity.