Design and Analysis of a High-Performance Packet Multiplexer for Multiservice Networks with Delay Guarantees

Authors:Liebeherr, Jorg, Department of Computer ScienceUniversity of Virginia Wrege, Dallas, Department of Computer ScienceUniversity of Virginia

A major challenge for the design of multiservice networks with quality of service guarantees is an efficient implementation of a bounded delay service, that is, a service that guarantees maximum end-to-end delays for every packet from a single traffic stream. A crucial component of a bounded delay service is the packet multiplexing technique employed at network switches that must keep the variable statistical multiplexing delays below a predetermined threshold. To achieve a high utilization of network resources, the multiplexing technique must be sufficiently sophisticated to support a variable set of delay bounds for a large number of traffic streams. On the other hand, since multiplexing of packets is to be performed at the data rate of the network links, the complexity of the multiplexer should be strictly limited. A novel packet multiplexing technique, called Rotating Priority Queues (RPQ), is presented which exploits the tradeofl'
between efficiency, i.e., the ability to support many connections with delay bounds, and low complexity. The operations required by the RPQ multiplexer are similar to those of the simple, but inefficient, Static Priority (SP) multiplexer. The overhead of RPQ, as compared to SP, consists of a periodic rearrangement (rotation) of the priority queues. It is shown that queue rotations can be implemented by updating a set of pointers. The efficiency of RPQ can be made arbitrarily close to the highly efficient, yet complex, Earliest Deadline First (EDF) multiplexer. Exact expressions for the worst case delays in an RPQ multiplexer are derived and compared to expressions for an EDF multiplexer.
Note: Abstract extracted from PDF file via OCR

All rights reserved (no additional license for public reuse)
Source Citation:

Liebeherr, Jorg, and Dallas Wrege. "Design and Analysis of a High-Performance Packet Multiplexer for Multiservice Networks with Delay Guarantees." University of Virginia Dept. of Computer Science Tech Report (1994).

University of Virginia, Department of Computer Science
Published Date: