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

TitleDesign and Analysis of a High-Performance Packet Multiplexer for Multiservice Networks with Delay Guarantees
Publication TypeTechnical Report
Year of Publication1994
AuthorsLiebeherr, J., & Wrege D. E.
Other Numbers904
Abstract

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 tradeoff 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 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.

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-94-034.pdf
Bibliographic Notes

ICSI Technical Report TR-94-034

Abbreviated Authors

J. Liebeherr and D. E. Wrege

ICSI Publication Type

Technical Report