Networking Research Laboratory
Director:
Simon S. Lam
(more publications)
Network and operating system support for Quality of Service
We began by studying MPEG video, and presented a traffic model
together with a lossless algorithm to reduce rate fluctuations in
MPEG encoder
output. Subsequently we worked on network protocol and operating system design
to support variable-bit-rate video traffic.
In 1994, we had the following key insight (technical report TR-94-24, October 6, 1994, presented at the 9th IEEE Workshop on Computer Communications, October 1994): Consider a packet flow with a guaranteed throughput rate at a server that uses a Virtual Clock (VC) packet scheduler. While the VC scheduler cannot provide a delay bound for each packet from its actual arrival time to the server, the scheduler can provide a delay guarantee from the expected arrival time of each packet (calculated using the flow's guaranteed rate). Thus if the flow's arrivals are well-behaved, i.e., the difference between each packet's actual and expected arrival times is bounded (e.g., enforced by a source control mechanism), a rate-based VC scheduler can provide a bounded delay service.
The above insight led to an end-to-end delay guarantee for a network of VC schedulers, which was then generalized to an end-to-end delay guarantee for a wide class of rate-based packet schedulers. The generalized guarantee can be instantiated to obtain end-to-end delay bounds for a variety of source control mechanisms; furthermore, different rate-based packet schedulers can be used in different nodes along a path [1995 NOSSDAV, 1996 IEEE INFOCOM]. This result represents a major generalization of the pioneering work of Parekh and Gallagher, which assumed the use of a weighted fair queueing scheduler (also known as PGPS) in every node. One of our papers [1995 NOSSDAV] is cited in RFC 2212 on Guaranteed Quality of Service.
Motivated by variable-bit-rate video which has very large picture-to-picture rate fluctuations, we proposed a new traffic model in which each flow is a sequence of bursts that satisfy a flow specification. We then designed an efficient algorithm, called Burst Scheduling, for scheduling video flows in the presence of other types of traffic (e.g., data and audio) in a packet switch. Burst Scheduling networks provide end-to-end delay guarantees to bursts representing application data units. To further reduce processing overhead, the idea of group priority scheduling was proposed and investigated.
To extend network-level delay guarantees to the ultimate user endpoints
(applications running in workstations), we pioneered the use of an
adaptive rate-controlled scheduler
for CPU scheduling to
support multimedia traffic.
We have also designed an end system architecture to support
QoS guarantees and implemented it as an extension to Solaris. The protocol processing component
of the architecture, called
Migrating Sockets,
has been designed with minimal hidden scheduling to enable accurate
determination of an application's rate requirement, rate-based flow control on the send side for access
to reserved-rate network connections, and a constant overhead active demultiplexing mechanism on the receive side which
can be transparently enabled in wide-area internetworking.
Publications