Characterization of the departure process from an ME/ME/1 queue

Kumaran, Jayesh; Mitchell, Kenneth; Van de Liefvoort, Appie

doi:10.1051/ro:2004018

Kumaran, Jayesh ; Mitchell, Kenneth ; Van de Liefvoort, Appie

RAIRO - Operations Research - Recherche Opérationnelle, Tome 38 (2004) no. 2, pp. 173-191.

Résumé

In this paper we propose a family of finite approximations for the departure process of an ME/ME/1 queue indexed by a parameter $k$ defined as the system size of the finite approximation. The approximations capture the interdeparture times from an ME/ME/1 queue exactly and preserve the lag correlations of inter-event times of the departures from an ME/ME/1 queue up to lag $(k - 1)$ .

MR Zbl

DOI : 10.1051/ro:2004018

@article{RO_2004__38_2_173_0,
     author = {Kumaran, Jayesh and Mitchell, Kenneth and Van de Liefvoort, Appie},
     title = {Characterization of the departure process from an {ME/ME/1} queue},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {173--191},
     publisher = {EDP-Sciences},
     volume = {38},
     number = {2},
     year = {2004},
     doi = {10.1051/ro:2004018},
     mrnumber = {2081836},
     zbl = {1092.90015},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro:2004018/}
}

TY  - JOUR
AU  - Kumaran, Jayesh
AU  - Mitchell, Kenneth
AU  - Van de Liefvoort, Appie
TI  - Characterization of the departure process from an ME/ME/1 queue
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2004
SP  - 173
EP  - 191
VL  - 38
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro:2004018/
DO  - 10.1051/ro:2004018
LA  - en
ID  - RO_2004__38_2_173_0
ER  -

%0 Journal Article
%A Kumaran, Jayesh
%A Mitchell, Kenneth
%A Van de Liefvoort, Appie
%T Characterization of the departure process from an ME/ME/1 queue
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2004
%P 173-191
%V 38
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro:2004018/
%R 10.1051/ro:2004018
%G en
%F RO_2004__38_2_173_0

Kumaran, Jayesh; Mitchell, Kenneth; Van de Liefvoort, Appie. Characterization of the departure process from an ME/ME/1 queue. RAIRO - Operations Research - Recherche Opérationnelle, Tome 38 (2004) no. 2, pp. 173-191. doi : 10.1051/ro:2004018. http://www.numdam.org/articles/10.1051/ro:2004018/

Bibliographie
Cité par

[1] N. Akar, N. Oguz and K. Sohraby, A novel computational method for solving finite QBD processes. Commun. Stat. Stochastic Models 16 (2000) 273-311. | MR | Zbl

[2] S. Asmussen and J. Møller, Calculation of the steady state waiting time distribution in GI/PH/c and MAP/PH/c queues. Queue. Syst. Theory Appl. 37 (2001) 9-29. | MR | Zbl

[3] S. Asmussen and C. O'Cinneide, Representations for matrix-geometric and matrix exponential steady-state distributions with applications to many-server queues. Commun. Statist. Stochastic Models 14 (1998) 369-387. | Zbl

[4] J. Beran, R. Sherman, M. Taqqu and W. Willinger, Long-range dependence in variable bit rate video traffic. IEEE Trans. Commun. 43 (1995) 1566-1579.

[5] D. Berstimas and D. Nakazato, The departure process from a GI/GI/1 queue and its applications to the analysis of tandem queues. Tech. Rep. 3725-91, Sloan School of Management (1990). Working paper.

[6] G. Bolch, S. Greiner, H. De Meer and K. Trivedi, Queuing Networks and Markov Chains. A Wiley-Interscience Publication, New York, John Wiley & Sons (1998). | MR | Zbl

[7] P. Burke, The output of queueing systems. Oper. Res. 699 (1956) 699-704. | MR

[8] D. Daley, The correlation structure of the output process of some single server queueing systems. Ann. Math. Stat. 39 (1968) 1007-1019. | MR | Zbl

[9] R. Disney and P. deMorais, Covariance properties for the departure process of M/ $E_{k}$ /1//N queues. AIIE Transactions 8 (1976) 169-175. | MR

[10] E. Gelenbe, On approximate computer system models. J. ACM 22 (1975) 261-269. | MR | Zbl

[11] E. Gelenbe, X. Mang and Y. Feng, Diffusion cell loss estimate for ATM with multiclass bursty traffic. Int. J. Comput. Syst. Sci. Engin. 11 (1996) 325-333.

[12] E. Gelenbe and I. Mitrani, Analysis and Synthesis of Computer Systems. Academic press, London, New York (1980). | MR | Zbl

[13] E. Gelenbe and G. Pujolle, The behaviour of a single queue in a general queueing network. Acta Informatica 7 (1976/77) 123-136. | MR | Zbl

[14] E. Gelenbe and G. Pujolle, A diffusion model for multiple class queueing networks, in Measuring, Modelling and Evaluating Computer Systems, Proc. of the Third International Symposium, Bonn - Bad Godesberg, Germany, edited by H. Beilner and H. Gelenbe. North-Holland (1977) 189-199

[15] M. Girish and J.-Q. Hu, Approximations for the departure process of a GI/GI/1 queue with Markov-modulated arrivals. Eur. J. Oper. Res. 134 (2001) 540-556. | MR | Zbl

[16] D. Green, Departure Process from MAP/PH/1 Queues. Ph.D. Thesis, The University of Adelaide, Department of Applied Mathematics (1999).

[17] A. Heindl, Traffic-Based Decomposition of General Queueing Networks with Correlated Input Processes. Ph.D. Thesis, Technical University, Berlin (2001). | Zbl

[18] J.-Q. Hu, The departure process of a GI/GI/1 queue and its MacLaurin series. Oper. Res. 44 (1996) 810-815. | Zbl

[19] A. Ishikawa, On the joint distribution of the departure intervals in an M/G/1//N queue. J. Oper. Res. Soc. Japan 34 (1991) 422-435. | MR | Zbl

[20] R. King, The covariance structure of the departure process from M/G/1 queues with finite waiting lines. J. R. Stat. Soc. 33 (1982) 401-405. | MR | Zbl

[21] P. Kühn, Approximation analysis of general queueing networks by decomposition. IEEE Trans. Commun. COM-27 (1979) 113-126.

[22] J. Kumaran, Ph.D. Thesis, University of Missouri-Kansas city, School of Computing Engineering. Forthcoming.

[23] G. Latouche and V. Ramaswami, A logarithmic reduction algorithm for quasi-birth-death process. J. Appl. Probab. 30 (1993) 650-674. | MR | Zbl

[24] Y. Lee, A. Van De Liefvoort and V. Wallace, Modeling correlated traffic with a generalized IPP. Perform. Eval. 40 (2000) 99-114. | Zbl

[25] A. Van De Liefvoort, The waiting time distribution and its moments of the PH/PH/1 queue. Oper. Res. Lett. 9 (1990) 261-269. | MR | Zbl

[26] M. Linvy, B. Melamed and A. Tsiolis, The impact of autocorrelation on queueing systems. Manage. Sci. 39 (1993) 332-339. | Zbl

[27] L. Lipsky, Queueing Theory: A Linear Algebraic Approach. New York, MacMillan (1992).

[28] L. Lipsky, P. Fiorini, W. Hsin and A. Van De Liefvoort, Auto-correlation of lag-k for customers departing from semi-Markov processes. Tech. Rep. TUM-19506, Technical University Munich (1995).

[29] K. Mitchell and A. Van De Liefvoort, Approximation models of feed-forward queueing networks with correlated arrivals. Perform. Eval. 51 (2003) 137-152.

[30] K. Mitchell, A. Van De Liefvoort and J. Place, Second-order statistics of an isolated departure stream from a shared buffer with correlated sources, in Proc. of the Eighth International Conference on Telecommunication Systems Modeling and Analysis, March (2000) 565-574.

[31] P. Pancha and M. Zarki, Variable bit rate video transmission. IEEE Communications 32 (1994) 54-66.

[32] B. Patuwo, R. Disney and D. Mcnickle, The effect of correlated arrivals on queues. IIE Transactions 25 (1993) 105-110.

[33] D. Reininger, B. Melamed and D. Raychaudhuri, Variable bit rate MPEG video: Characteristics, modeling and multiplexing, in Proc. of the Fourteenth International Teletraffic Congress 1 (1994) 295-306.

[34] R. Sadre and B. Haverkort, Characterising traffic streams in networks of MAP/MAP/1 queues, in Proc. of the Eleventh GI/ITG, Conference on Measuring Modelling and Evaluation of Computer Communication Systems (2001) 195-208.

[35] W. Whitt, Approximating a point process by a renewal process I: Two basic methods. Oper. Res. 30 (1982) 125-147. | MR | Zbl

[36] W. Whitt, The queueing network analyzer. Bell System Technical J. 62 (1983) 2799-2815.

[37] W. Whitt, Approximations for departure processes and queues in series. Naval Research Logistics Quarterly 31 (1984) 499-521. | MR | Zbl

Cité par Sources :