Approximation of The Queue Length Distribution of General Queues

ETRI Journal

关键词: Approximation of The Queue Length Distribution of General Queues;   

Others  :  1183942
DOI  :  10.4218/etrij.94.0194.0003

【 摘 要 】

In this paper, we develop approximation formalism on the queue length distribution for general queuing models. Our formalism is based on two steps of approximation; the first step is to find a lower bound on the exact formula, and subsequently the Chernoff upper bound technique is applied to this lower bound. We demonstrate that for the M/M1 model our formula is equivalent to the exact solution. For the D/M/1 queue, we find an extremely tight lower bound below the exact formula, On the other hand, our approach shows a tight upper bound on the exact distribution for both the ND/D/1 and M/D/1 queues. We also consider the M+Σ NjDj/D/1 queue and compare our formula with other formulism for the Σ NjDj/D/1 and M+D/D/1 queues.

   

【 参考文献 】

• [1]A.E. Eckberg, Jr., "The single server queue with periodic arrival process and deterministic service time," IEEE Trans. Commun., COM-27, No. 3, pp. 556-562, 1979.
• [2]M. J. Karol and M. G. Hluchyi, "Using a packet switch for circuit-switched traffic: A queuing system with periodic input traffic, in Proc. Int. Conf. Commun. 1987, Seattle, WA, pp. 1677-1682, 1987.
• [3]A. Bhargava, P. A. Humblet, and M. G. Hluchyi, "Queuing analysis of continuous bit-stream transport in packet networks," in Proc. IEEE GLOBECOM 89, Dallas, TX, pp. 903-907, 1989.
• [4]P. Humblet, A. Bhargava, and M. G. Hluchyl, "Ballot theorems applied to the transient analysis of nD/D/1 queues," IEEE/ACM Trans. Network, Vol. 1, No. 1, pp. 81-95, 1993.
• [5]J. W. Roberts and J. T. Virtamo, "The superposition of periodic cell arrival stream in an ATM multiplexer," IEEE Trans. Commun., Vol. 39, No. 2, pp. 298- 303, 1991.
• [6]K. Nakagawa, "Loss and waiting time probability approximation for general queuing," Tech. Rep. JEICE, SSE93-2, pp. 7-12, Apr.1994.
• [7]L. Kleinrock, Queuing Systems, Vol. 1: Theory. Boston, MA: Wiley, 1974.
• [8]F. Guillemin and W. Monin, "Management of cell delay variation in ATM networks," in Proc. IEEE GLOI3ECOM ‘92, pp. 128-132, 1992.