Bounds for the tail distribution in a queue with a superposition of general periodic Markov sources: theory and application

An efficient yet accurate estimation of the tail distribution of the queue length has been considered as one of the most important issues in call admi ssion and congestion controls in ATM networks. The arrival process in ATM n etworks is essentially a superposition of sources which are typically burst y and periodic either due to their origin or their periodic slot occupation after traffic shaping. In this paper, we consider a discrete-time queue wh ere the arrival process is a superposition of general periodic Markov sourc es. The general periodic Markov source is rather general since it is assume d only to be irreducible, stationary and periodic. Note also that the sourc e model can represent multiple time-scale correlations in arrivals. For thi s queue, we obtain upper and lower bounds for the asymptotic tail distribut ion of the queue length by bounding the asymptotic decay constant. The form ulas can be applied to a queue having a huge number of states describing th e arrival process. To show this, we consider an MPEG-like source which is a special case of general periodic Markov sources. The MPEG-like source has three time-scale correlations: peak rate, frame length and a group of pictu res. We then apply our bound formulas to a queue with a superposition of MP EG-like sources, and provide some numerical examples to show the numerical feasibility of our bounds. Note that the number of states in a Markov chain describing the superposed arrival process is more than 1.4 x 10(88). Even for such a queue, the numerical examples show that the order of the magnitu de of the tail distribution can be readily obtained.