Real-time queueing theory

Abstract

The paper presents an approach to real time system scheduling. The approach, called real time queueing theory, includes customer timing requirements into queueing models. With real time queueing models, one is able to explicitly characterize the dynamic behavior of the customer lead time profile process where lead time=deadline minus current time. In spite of the infinite dimensionality of these processes, in the heavy traffic case, a simple description of lead time profile process is presented, and this description is shown to be very accurate when compared against simulations. Real time queueing theory offers the promise of providing real time system predictability for systems characterized by substantial stochastic behavior (such as ATM networks and multimedia systems). Possible generalizations are discussed.