A Discrete Workload Conservation Law with Applications to Discrete-Time Queueing Systems

Abstract

In this article we give a general conservation law for discrete-time systems. For queueing models in discrete-time the law relates the asymptotic average workload in the system to the conditional asymptotic average sojourn time and service times distribution function. The law is valid for multi-server systems, and anticipating and non-anticipating scheduling disciplines. The proof uses a sample-path discrete-time version for the well-known relation . We apply the law to several queueing models and show that for anticipative and non-anticipative scheduling rules, the unconditional delay in a queue is related to the covariance of service times and queueing delays. The results in this article complement similar results for continuous-time models.