Real-time Queueing Theory: A Tutorial Presentation with an Admission Control Application

Author(s)

Rusty O. Baldwin, University of DaytonFollow
Nathaniel J. Davis IV, Virginia Polytechnic Institute and State University
John E. Kobza, Texas Tech University
Scott F. Midkiff, Virginia Polytechnic Institute and State University

Document Type

Article

Publication Date

6-2000

Publication Source

Queueing Systems

Abstract

Real-time scheduling, or scheduling with respect to a deadline, is critical in many application areas such as telecommunications, control systems, and manufacturing. This paper presents a novel approach to real-time scheduling based on a queueing theory model. Using real-time queueing theory (RTQT), one can analytically determine the distribution of the lead-time profile (i.e., the time until the deadline is reached) of customers waiting for service. Emphasis is placed on the development of the equations used to determine the lead-time profile distribution. The development of the GI/G/1 case is presented and confirmed using simulation. Simulation results confirm prior research for the M/M/1 and GI/M/1 case. As a practical application, RTQT is used to implement a packet admission control algorithm for a telecommunications network. Using this algorithm, packet lateness was reduced by up to 31%.

Inclusive pages

1-21

ISBN/ISSN

0257-0130

Comments

Permission documentation on file.

Copyright

Copyright © 2000, Kluwer Academic Publishers

Publisher

Kluwer Academic Publishers

Volume

35

Peer Reviewed

yes

Issue

1-4

eCommons Citation

Baldwin, Rusty O.; Davis, Nathaniel J. IV; Kobza, John E.; and Midkiff, Scott F., "Real-time Queueing Theory: A Tutorial Presentation with an Admission Control Application" (2000). Computer Science Faculty Publications. 93.
https://ecommons.udayton.edu/cps_fac_pub/93