Title: "A Versatile Packet Multiplexer for Quality-of-Service Networks"
Keywords: Real-time Networks, Bounded Delay Service, Multiplexing,
Quality-of-Service, Packet Scheduling, Admission Control.
Conference: 4th Int. Symposium on High Performance Distributed
Computing (HPDC-4), Pentagon
City, Virginia USA, August 1995
A novel packet multiplexing technique, called Rotating-Priority-Queues
(RPQ), is presented which exploits the tradeoff between high
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 presented and compared to
expressions for an EDF multiplexer.