We derived tight deterministic bounds on the delay and fairness properties of SFQ and FA scheduling disciplines. To accommodate links whose capacity fluctuates over time (for example, flow-controlled and broadcast medium links), we developed techniques for analyzing servers modeled as either Fluctuation Constrained (FC) or Exponentially Bounded Fluctuation (EBF) servers. We analyzed the deadline guarantees of SFQ and FA disciplines when the bandwidth requirement exceeds server capacity. Finally, we defined a class of Guaranteed Rate (GR) scheduling algorithms, that includes most known packet scheduling disciplines, and extended the analyses to the entire class of algorithms.

Statistical analysis of packet scheduling algorithms is an important open research problem. We recently took a step towards addressing this problem by deriving a statistical delay guarantee for the generalized Virtual Clock scheduling algorithm. We defined the concept of an equivalent fluid and packet source, and proved a theorem that relates the departure time of a packet in a fluid FCFS multiplexor to its departure time in a generalized Virtual Clock packet scheduling algorithm. The key contribution of our approach is that it enables fluid flow analysis techniques to be used for statistical analysis of packet systems.

A network of servers is difficult to analyze since each router along the path may employ a different scheduling discipline, packets may be fragmented and reassembled, etc. Yet, we have been able to develop compositional techniques that allow a network of GR servers to be analyzed as a single server. Our approach decouples the guarantees provided by a network from source traffic characterization, and derives tight performance bounds for heterogeneous networks. This framework has provided the theoretical foundation for designing guaranteed services in the Internet.

Representative Publications:

1. P. Goyal and H.M. Vin, Statistical Delay Guarantee of Virtual Clock, In Proceedings of IEEE Real-time Systems Symposium (RTSS), December 1998 [Abstract | Paper]

2. 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 ]

3. P. Goyal, S.S. Lam, and H.M. Vin, Determining End-to-End Delay in Heterogeneous Networks, ACM Multimedia, No. 3, Pages 157-163, 1997 (An earlier version of this paper appeared in proceedings of the 5th International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV'95), Durham, New Hampshire, Pages 287-298, April 1995) [ Abstract | Paper ]