Discrete-Time Single Server Queues with Correlated Inputs

Several computer systems and networks involve queueing models with single server queues. We consider a discrete-time queueing system, with service time normalized to unity, modeled by the equation bn+i = K - 1 + zn if bn > 1 = zn or equivalently bn+l = if bn = 0 (bn ~ 1)+ + Zn (1) Here bn denotes queue length 1 and the nonnegative integer valued sequence zn is the input. A vast majority of literature in queueing theory deals with the case when zn] is a sequence of independent identically distributed random 1743 variables. In this situation, when the average value Ezn 1,6 = lim n | 00 * bn is a well-defined random variable, and various authors have analyzed the distribution of 6; see Ref. 1. An interesting approach is due to Spitzer 2 who uses a simple consequence of eq. (1): when 60 = 0 then bn+i = max £ Zn-i - r r i=0 r (2)