Multimedia Networks with Deterministic Quality-of-Service Guarantees

Future integrated-services networks are expected to support applications with a wide range of service requirements. The most demanding applications require a bounded-delay service that provides deterministic (i.e., worst-case) bounds on network latencies for all packets. To provide such delay guarantees, a network must allocate network resources such as bandwidth and buffer space to individual connections. However, since resource availability is limited, the network must carefully manage its resources in order to ensure a high achievable network utilization.

Two components are central to the design of a network with a bounded-delay service: the traffic characterization method used to specify traffic on a connection, and the packet scheduling discipline at network switches that determines the transmission order of packets queued at output buffers. The choice of each component determines a trade off between achievable network utilization and implementation overhead. In particular, a
traffic characterization should accurately describe the actual arrivals on a connection so that a large number of connections can be supported, but it must also conform to a simple parameterized model that the network can easily monitor and enforce. Similarly, a packet scheduling discipline should be sophisticated enough to support tight delay constraints at high loads, but it must also have a simple implementation so that packets can be processed at the speed of the transmission link.

This dissertation presents novel methods for traffic characterization and packet scheduling that are practical for implementation yet yield a high network utilization in a bounded delay service. The first problem considered is the characterization of compressed digital video, an important traffic type that is both high in bandwidth usage and has a variable bit rate (VBR). A novel traffic characterization method is presented that is shown to accurately specify the
traffic of VBR video sources. This characterization method is based on approximating an optimal traffic characterization that is itself impractical because of two significant drawbacks: (1) the need for a large number of parameters that are computationally expensive to produce, and (2) the inability of the network to monitor or enforce the optimal traffic characterization. Our characterization method addresses both of these problems by determining a subset of its parameters that can be computed quickly and using these parameters to determine a traffic characterization that can be easily enforced by simple traffic policing mechanisms.

A novel packet scheduling discipline, referred to as Rotating-Priority-Queues+ (RPQ+), is developed that is near-optimal in the sense that it can approximate the optimal Earliest-Deadline-First (EDF) discipline with arbitrary precision. The advantage of the RPQ+scheduler over EDF is in its computational overhead: while an implementation of EDF requires the sorting of packets which is impractical for high-speed networks, RPQ+ avoids the need for sorting by using a set of prioritized FIFO queues whose priorities are rearranged (rotated) periodically to increase the priority of waiting packets. For
shared- memory architectures, it is demonstrated that RPQ+ can be implemented with little computational overhead. Analysis of the RPQ+ scheduler shows that it has the following desirable properties: its implementation requires operations independent of the number of queued packets; it can provide worst-case delay guarantees; it is always superior to a Static-Priority (SP) scheduler; and its achievable network utilization increases with the frequency of queue rotations, approaching that of EDF in the limit.