We articulated the inadequacies of packet scheduling disciplines proposed in the literature and formulated the requirements for one suited for integrated services networks. We developed Start-time Fair Queuing (SFQ) and a class of Fair Airport (FA) scheduling disciplines that meet these requirements. FA contains algorithms with different implementation complexity and performance guarantees. In fact, a specific instance of the FA algorithm leads to the first fair scheduling discipline that achieves separation of rate and delay guarantees.

We developed a hierarchical link-sharing discipline based on the SFQ and FA scheduling algorithms and formally analyzed its properties. We proved that SFQ and FA provide fairness guarantees even when the available network bandwidth varies over time, a property essential for hierarchical link-sharing. There are two noteworthy features of our hierarchical link-sharing discipline. First, it allows the network to provide delay, fairness, and throughput guarantees to all applications while achieving high levels of utilization. Second, it allows different schedulers and congestion control algorithms to be employed for different applications.

Representative Publications:

1. P. Goyal and H.M. Vin, Generalized Guaranteed Rate Scheduling Algorithms: A Framework, IEEE/ACM Transactions on Networking, Vol. 5, No. 4, Pages 561-571, August 1997 [ Abstract | Paper ]

2. P. Goyal and H.M. Vin, Fair Airport Scheduling Algorithms, In Proceedings of the 7th International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV'97), Pages 273-282, May 1997 [ Abstract | Paper ]