Queueing networks in discrete-time: Exact results and approximations

We use a direct approach to develop exact results and, in some cases, approximations for discrete-time cyclic queueing networks and a subclass of open networks. We prove directly that the arrival distribution for a single-server network is equal to the steady-state distribution of the network conditional on that node being occupied. In the ample server case, the arrival distribution at a node is equal to the steady-state distribution of the equivalent network with one job less cycling the network. In the intermediate case, the arrival distribution may not be described in product-form in contrast to the single-server and ample-server networks.We also show that in the case of node-independent service rates, steady-state distributions in discrete-time, for the kind of networks we consider here, can be written as a product of the continuous-time steady-state distribution and a factor that approaches one in the limit as service rates go to zero. These limit results allow us to develop approximation algorithms to estimate steady-state probabilities for the queue lengths in intermediate cases. We use this continuous-discrete form of discrete invariant vectors to find the steady-state distribution for a subclass of open networks.