Queueing characteristics for markovian traffic models in packet-oriented networks

Andrzej Chydziński


This monograph presents the author's contribution to the field of performance evaluation of packet buffering processes in network nodes. In particular, a detailed characterization of finite-buffer queues fed by Markovian traffic models is presented by means of theorems and formulas. The Markovian traffic models were chosen due to their ability to mimic a very complex statistical behaviour of the traffic, including the self-similarity and long-range dependence. For analytical purposes, a new powerful method that can be used for all Markovian traffic models is proposed. This method combines the Laplace transform technique with the use of special recurrent sequences to solve large systems of linear equations. The method has several important advantages. Firstly, it enables an analysis of finite-buffer queueing models. This issue is crucial from the practical point of view as in all real devices (routers, switches) the buffering space is limited. On the other hand, most previous studies covered only infinite-buffer queues, less demanding in analysis. Secondly, it makes possible both transient and steady-state characterization of the queueing process. Thirdly, it allows for finding virtually all important performance characteristics and gives results in a closed, easy to use form. The following characteristics are studied by means of this method: the queue size distribution, the queueing delay distribution, the blocking probability, the loss ratio, the buffer overflow period, the time to buffer overflow and the statistical structure of packet losses. For each characteristic a new formula describing its transient and steady-state behaviour is obtained. The analytical results are illustrated by numerical examples, most of them obtained for traffic parameterizations based on IP trace files. The monograph consists of five chapters organized in the following way. In Chapter 1 the potential method is presented. This method permits finding closed-form solutions for large systems of linear equations in a special form. The systems of equations in this form appear frequently in the remaining part of the book and the potential method is used to solve them effectively. Chapters 2, 3 and 4 are the main part of the monograph and they present the queueing characteristics for different Markovian traffic models, with an emphasis on growing complexity of the model in every next chapter. In particular, Chapter 2 is devoted to the simple and compound Poisson processes, Chapter 3 focuses on the Markov-modulated Poisson process (MMPP), while Chapter 4 presents results for the batch Markovian arrival process (BMAP). All these chapters are structured as follows. Firstly, the description and the properties of the traffic model are given. Secondly, the theorems presenting formulas for the queueing characteristics are proven. Thirdly, the numerical examples are presented. Each chapter ends with a bibliographical note. Chapter 5 presents a set of mathematical and numerical tools that enable or make easier obtaining numerical results from formulas proven in the previous chapters. Namely, a set of algorithms for inverting the Laplace transforms and generating functions is shown, the uniformization method for computing coefficient matrices for MMPP and BMAP is presented, the expectation maximization algorithm for MMPP and BMAP parameter fitting is discussed and the continuous version of the total probability formula is recalled.


queueing; Poisson process; MMPP; BMAP; packet-oriented networks

Full Text:

PDF (Polski)


Abate J., Choudhury G. L. and Whitt W. - On the Laguerre method for numerically inverting Laplace transforms. INFORMS Journal on Computing 8, pp. 413-427, (1996).

Abate J., Choudhury G. L. and Whitt W. - An introduction to numerical transform inversion and its application to probability models. Chapter in Computational Probability, pp. 257-323, W. Grassman (ed.), Kluwer, Boston, (2000).

Abbas M. and Ahmad Z. A. - Performance analysis of an ATM statistical multiplexer with batch arrivals. lEE Proceedings: Communications, 141, pp. 190-195, (1994).

El Abdouni Khayari R., Sadre R. and Haverkort B. R. - Fitting world-wide web request traces with the EM-algorithm. Performance Evaluation 52, pp. 175-191, (2003).

Adas A. - Traffic Models in Broadband Networks. IEEE Communications Magazine (7), pp. 82-89, (1997).

Akar N. and Sohraby K. - Matrix geometric solutions in M/G/1 type Markov chains with multiple boundaries: A generalized state-space approach. In Teletraffic contributions for the information age. Eds., V. Ramaswami and P. E. Wirth, pp. 487-96, (1997).

Akar N. and Sohraby K. - An invariant subspace approach in M/G/1 and G/M/1 type Markov chains. Stochastic Models, 13, pp. 381-416, (1997).

Alfa A. S. and Chakravarthy S. - A discrete queue with Markovian arrival process and phase type primary and secondary services. Stochastic Models, 10, pp. 437-451, (1994).

Alfa A. S. and Neuts M. F. - Modelling vehicular traffic using the discrete time Markovian arrival process. Transportation Science, 29, pp. 109-117, (1995).

Alfa A. S. and Frigui I. - Discrete NT-policy single server queue with Markovian arrival process and phase type service. European Journal of Operational Research, 88, pp. 599-613, (1996).

Andersen A. T., Jensen A. and Nielsen B. F. - Modelling and performance study of packet traffic with self-similar characteristics over several time-scales with Markovian Arrival Processes. VTT Symposium (Valtion TekniUinen Tutkimuskeskus), pp. 154-269,(1995).

Andersen A. T. and Nielsen B. F. - Application of superpositions of two state Mar-kovian sources to the modelling of self-similar behaviour. Proceedings IEEE INFO-COM'97, pp. 196-204, (1997).

Andersen A. and Nielsen B. - A Markovian approach for modeling packet traffic with long-range dependence, IEEE Journal on Selected Areas in Communications 16(5), pp. 719-732, (1998).

Appenzeller G., Keslassy I. and McKeown N. - Sizing Router Buffers. Proc. ACM SIGCOMM'04, pp. 281-292, September, (2004).

Asmussen S. and O'Cinneide C. A. - On the tail of the waiting time in a Markov-modulated M/G/1 queue. Operations Research, vol. 50, Issue 3, pp. 559-565, (2002).

Asmussen S. and MoUer J. R. - Calculation of steady state waiting time distribution in GI/PH/c and MAP/PH/c queues. Technical report, Centre for Mathematical Sciences, Lund University, Sweden, (1999).

Asmussen S., Jobmann M. and Schwefel H. P. - Exact Buffer Overflow Calculations for Queues via Martingales. Queueing Systems 42(1): pp. 63-90, (2002).

Baiocchi A., Melazzi N., Listanti M., Roveri A. and Winkler R. - Loss performance analysis of an ATM multiplexer loaded with high-speed ON-OFF sources. IEEE Journal on Selected Areas in Communications, 9, pp. 388-393, (1991).

Baiocchi A. and Blefari-Melazzi N. - Steady-state analysis of the MMPP/G/1/K queue. IEEE Trans. Commun. 41, No.4, pp. 531-534, (1992).

Balay R. I. and Nilsson A. A. - Performance modeling of an ATM multiplexer with heterogeneous speed Hnks. IEEE International Conference on Communications, 2, pp. 778-782, (1995).

Barman D., Smaragdakis G. and Matta I. - The effect of router buffer size on highspeed TCP performance. Proceedings of IEEE GLOBECOM'04, pp. 1617-1621, (2004).

Bean N., Green D. and Taylor P. - Approximations to the output process of MAP/PH/1 queues. In Advances in Matrix-analytic Methods in Stochastic Models, Ed., Alfa A. S. and Chakravarthy S. R. Notable Publications, pp. 151-169, (1998).

Bin L. and Chakravarthy S. - Performance analysis of a resequencing model in telecommunications network. Fifth International Conference on Telecommunication Systems, pp. 633-652, (1997).

Bini D. and Meini B. - On the solution of nonlinear matrix equation arising in queueing problems. SIAM J. Matrix analysis and applications, 17, pp. 906-926, (1996).

Bini D. and Meini B. - On cycHc reduction applied to a class of Toeplitz-like matrices arising in queueing problems. In Computations with Markov chains. Ed., W.J. Stewart, Kluwer Academic publishers, pp. 21-38, (1996).

Bini D. and Meini B. - Improved cyclic reduction for solving queueing problems. Numerical Algorithms, 15, pp. 57-74, (1997).

Bini D. and Meini B. - Inverting block Toeplitz matrices in block Hessenberg form by means of displacement operators: application to queuing problems. Linear Algebra and Applications, 272, pp. 1-16, (1998).

Blondia C. - A Discrete-Time Batch Markovian Arrival Process as B-ISDN Traffic Model. Belgian Journal of Operations Research, Statistics and Computer Science, 32, pp. 3-23, (1992).

Blondia C. and Casals O. - Performance analysis of statistical multiplexing of VBR sources. Proceedings-IEEE INFOCOM, 2, pp. 828-838, (1992).

Blondia C. - The finite Capacity N/G/1 Queue. Communications in Statistics: Stochastic Models, 5(2), pp. 273-294, (1989).

de Boer P. T., Nicola V. F. and van Ommeren J. C. W. - The Remaining Service Time Upon Reaching a High Level in M/G/1 Queues. Queueing Systems 39, pp. 55-78, (2001).

Bratijczuk M., Chydziński A. - Rachunek prawdopodobieństwa. Wydawnictwo Politechniki Śląskiej, Gliwice, (2000).

Bratiychuk M. and Chydziński A. - On the ergodic distribution of oscillating queuing systems. Journal of Applied Mathematics and Stochastic Analysis 16:3, pp. 311-326, (2003).

Breuer L. - An EM algorithm for batch Markovian arrival processes and its comparison to a simpler estimation procedure. Annals of Operations Research, vol. 112, pp. 123-138,(2002).

Buchholz R - An EM-Algorithm for MAP Fitting from Real Traffic Data. In: R Kemper, W. H. Sanders (eds.). Computer Performance Evaluation Modelling Techniques and Tools, Springer LNCS 2794, pp. 218-236, (2003).

Carle G. - Adaptable error control for efficient provision of reliable services in ATM networks. Proc. 1st Workshop ATM Traffic Management, IFIP, WG.6.2 Broadband Communication, Paris, pp. 399-406, (1995).

Carmo R. M. L. R., de Souza e Silva E. and Marie R. - Efficient solutions for an approximation technique for the transient analysis of Markovian models. Technical report, IRISA Publication Internet. N 1067, (1996).

Chakravarthy S. R. - Analysis of a multi-server queue with batch Markovian arrivals and group services. Engineering Simulation, 18, pp. 51-66, (2000).

Chakravarthy S. and Dudin A. N. - A Multi-Server Retrial Queue with BMAP Arrivals and Group Services. Queueing Systems, volume 42, Number 1, pp. 5-31, (2002).

Chakravarthy S. and Dimitrova T. - Service control of queueing system with nonrenewal arrivals and phase type services. In Mathematics with vision, Proceedings of the First International Mathematica Symposium. Eds. V. Keranen, V and P. Mitic, Computational Mechanics Publication, pp. 93-102, (1995).

Chakravarthy S. - Analysis of the MAP/PH/1/K queue with service control. Applied Stochastic Models and Data Analysis 12, pp. 179-181, (1996).

Chakravarthy S., Chukova S. and Dimitrov B. - Analysis of MAP/M/2/K queueing model with infinite resequencing buffer. Performance Evaluation, 31, pp. 211-228, (1998).

Chakravarthy S. - The Batch Markovian Arrival Process: A Review and Future Work. Advances in Probability and Stochastic Processes. Eds., A. Krishnamoorthy, et al., pp. 21-49, (2001).

Choudhury G. L. and Lucantoni D. M. - Numerical computation of the moments of a probability distribution from its transform. Operations Research, 44, pp. 368-381, (1996).

Choudhury G. L., Lucantoni D. M. and Whitt W. - Multi-Dimensional Transform Inversion with Applications to the Transient M/G/1 Queue. Annals of Applied Probability vol. 4, pp. 719-740, (1994).

Chydzinski A. - The oscillating queue with input stream intensity switching. Applied Stochastic Models and Data Analysis 10, pp. 327-331, (2001).

Chydzinski A. - The M/G-G/1 oscillating queueing system. Queueing Systems, vol. 42:3, pp. 255-268, (2002).

Chydzinski A. - The M-M/G/1-type oscillating systems. Cybernetics and Systems Analysis, vol. 39(2), pp. 316-324, (2003).

Chydzinski A. - Diffusion approximation in analysis of ATM traffic control mechanisms. Archiwum Informatyki Teoretycznej i Stosowanej, vol. 15(3), pp. 207-222, (2003).

Chydzinski A. - The oscillating queue with finite buffer. Performance Evaluation, vol. 57(3), pp. 341-355, (2004).

Chydzinski A. - On transient analysis of queues with Poisson input stream. Proceedings of International Workshop in Applied Probability, Piraeus, Greece, pp. 85-89, (2004).

Chydzinski A. - On the remaining service time upon reaching a target level in M/G/1 queues. Queueing Systems, vol. 47, issue 1/2, pp. 71-80, (2004).

Chydzinski A. - On the Transient Remaining Service Time in a Large Buffer Queue. WSEAS Transactions on Communications, vol. 3, issue 4, pp. 958-962, (2004).

Chydzinski A. - On the Statistical Structure of Losses Caused by the Buffer Overflow. Proceedings of TELE-INFO'05, pp. 165-171, Prague, March (2005).

Chydzinski A. - On the Distribution of Consecutive Losses in a Finite Capacity Queue. WSEAS Transactions on Circuits and Systems, vol. 4, issue 3, pp. 117-124, (2005).

Chydzinski A. and Winiarczyk R. - Distribution of the First Buffer Overflow Time in a Deterministic Service Time Queue. Proceedings Of IEEE Symposium on Computers and Communications. La Manga, Spain, June (2005).

Chydzinski A. - Transient Analysis of the MMPP/G/1/K Queue. Telecommunication Systems, vol. 32, n. 4, pp. 247-262, (2006).

Chydzinski A. - Duration of the buffer overflow period in a batch arrival queue. Performance Evaluation, vol. 63:4-5, pp. 493-508, (2006).

Chydzinski A. - On the Overflow Interval in a Poisson Arrival Queue. WSEAS Transactions on Computers, vol. 5, issue 7, pp. 1421-1428, (2006).

Chydzinski A. and Winiarczyk R. - Blocking probabiUty in a BMAP queue. Proceedings of 11-th IEEE Symposium on Computers and Communications, pp. 547-552. Pula, Italy, July (2006). (The best paper award in modeling and simulation).

Chydzinski A. - Queue Size in a BMAP Queue with Finite Buffer. Proceedings of Next Generation Teletraffic and WiredAVireless Advanced Networking '06. Lecture Notes in Computer Science, vol. 4003, pp. 200-210, (2006).

Chydzinski A. - Delay analysis in a BMAP queue. Proceedings of 13-th International Conference on Telecommunications. Funchal, Portugal, May (2006).

Chydzinski A. - Buffer Overfow Period in a Constant Service Rate Queue. Proceedings of TELE-INFO '06, pp. 186-191, Istambuł, May (2006).

Chydzinski A. - On the Queue Length Distribution in BMAP Systems. Journal of Communications Software and Systems, vol. 2, no. 4, pp. 275-282, (2006).

Chydzinski A. - Buffer overflow calculations in a batch arrival queue. ACM SIGME-TRICS Performance Evaluation Review, vol. 34, issue 2, pp. 19-21, (2006).

Chydzinski A., Wójcicki R. and Hryn G. - On the Number of Losses in an MMPP Queue. Proceedings of Next Generation Teletraffic and WiredAVireless Advanced Networking '07. Lecture Notes in Computer Science, vol. 4712, pp. 38-48, (2007).

Chydzinski A. - Time to reach buffer capacity in a BMAP queue. Stochastic Models, vol. 23, pp. 195-209, (2007).

Chydzinski A. - Buffer Overflow Period in an MAP Queue. Mathematical Problems in Engineering, vol. 2007, pp. 1-18, (2007).

Chydzinski A. - Time to Buffer Overflow in an MMPP Queue. Proceedings of Networ-king'07, Atlanta, May 2007. Lecture Notes in Computer Science, vol. 4479, pp. 879-889, (2007).

Chydzinski A. and Winiarczyk R. - On the Blocking Probability in Batch Markovian Arrival Queues. Microprocessors and Microsystems, przyjęto do druku, (2007).

Chydzinski A. - Solving Finite-Buffer Queues with Markovian Arrivals. ACM SIG-METRICS Performance Evaluation Review, przyjęto do druku, (2007).

Chydzinski A. - A new approach to analyzing Markovian queues. Zgłoszono do publikacji, (2007).

Chydzinski A. - Packet loss process in a queue with Markovian arrivals. Zgłoszono do publikacji, (2007).

Cohen J. W. - The Single Server Queue. Revised edition North-Holland Publishing Company, Amsterdam, (1982).

Conolly B. - Lecture Notes on Queueing Systems. Ellis Horwood Limited, Susses, England, (1975).

Cooper R. - Introduction to Queueing Theory. 2nd Edition North Holland, (1981).

Crovella M. and Bestavros A. - Self-similarity in World Wide Web traffic: Evidence and possible causes. IEEE/ACM Transactions on Networking 5(6): pp. 835-846, (1997).

Czachorski T. - Modele kolejkowe w ocenie efektywności sieci i systemów komputerowych. Wydawnictwo Pracowni Komputerowej Jacka Skalmierskiego, Gliwice, (1999).

Davies B. and Martin B. L. - Numerical inversion of the Laplace transform: A survey and comparison of methods. J. Comp. Phys. 33, pp. 1-32, (1979).

Dempster A., Laird N. and Rubin D. - Maximum Hkelihood from incomplete data via the EM algorithm. J. R. Stat. Soc. B, Volume: 39, pp. 1-38, (1997)

Deng L. and Mark J. - Parameter estimation for Markov modulated Poisson processes via the EM algorithm with time discretization. Telecommunication Systems 1, pp. 321-338, (1993).

Dhamdhere A. and DovroUs C. - Open issues in router buifer sizing. ACM SIGCOMM Computer Communication Review 36, pp. 87-92, (2006).

Dhamdhere A., Jiang H. and Dovrolis C. - Buffer Sizing for Congested Internet Links. Proc. of IEEE INFOCOM, Miami PL, pp. 1072-1083, March, (2005).

Dudin A. N. - Optimal multi-threshold control for a BMAP/G/1 queue with N service modes. Queueing Systems: 30, pp. 273-287, (1998).

Dudin A. N. and Nishimura S. - Optimal control for a BMAP/G/1 queue with two service modes. Mathematical Problems in Engineering, 5, pp. 255-273, (1999).

Enachescu M., Ganjali Y., Goel A., McKeown N. and Roughgarden T. - Part III: routers with very small buffers. ACM SIGCOMM Computer Communication Review 35, pp. 83-90, (2005).

Erramilli A., Singh R. P. and Pruthi P. - An application of deterministic chaotic maps to model packet traffic. Queueing Systems, vol. 20, pp. 171-206, (1995).

Fakinos D. - The expected remaining service time in a single server queue. Operations Research, 30, pp. 1014-1018, (1982).

Fiems D., Steyaert B. and Bruneel H. - Performance of a Partially Shared Buffer with Correlated Arrivals. Lecture Notes in Computer Science 4479, pp. 1196-1200, (2007).

Filipowicz B. - Analiza i synteza systemów obsługi i sieci kolejkowych. Modele stochastyczne w badaniach operacyjnych. Wydawnictwa Naukowo-Techniczne, Warszawa, (1996).

Fischer W. and Meier-Hellstem K. - The Markov-modulated Poisson process (MMPP) cookbook. Performance Evaluation 18, No.2, 149-171, (1992).

Fonseca N. L. S. and Silvester J. A. - Modelling the output process of an ATM multiplexer with correlated priorities. IEEE International Conference on Communications, 2, pp. 816-821,(1997).


Gail H. R., Hantler L. and Taylor B. A. - Solutions of the basic matrix equation for M/G/1 and G/M/1 type Markov chains. Stochastic Models, 10, pp. 1^3, (1994).

Gail H. R., Hantler L. and Taylor B. A. - Spectral analysis of M/G/1 and G/M/1 type Markov chains. Adv. Appl. Prob., 28, pp. 114-165, (1996).

Garcia J. and Casals O. - A discrete time queueing model to study the cell delay variation in an ATM queueing network. Performance Evaluation, 21, pp. 3-22, (1994).

Gelenbe E., Mang X. and Onvural R. - Diffusion based statistical call admission control in ATM. Performance Evaluation, 27&28, pp. 411^36, (1996).

Ge H., Harder U. and Harrison P. G. - Parameter estimation for MMPPs using the ME algorithm. Proc. UKPEW, July (2003).

Gorinsky S., Kantawala A. and Turner J. - Link Buffer Sizing: A New Look at the Old Problem, Proc. Of 10-th IEEE Symposium on Computers and Communications. La Manga, Spain, June, (2005).

Gouweleeuw F. N. - Calculating the loss probability in a BMAP/G/l/N+1 queue. Commun. Stat., Stochastic Models 12, No.3, pp. 473-492, (1996).

Grassman W. K. and Heyman D. P. - Equilibrium distribution of block-structured Markov chains with repeating rows. J. Appl. Prob., 27, pp. 557-576, (1993).

Grassman W. K. and Heyman D. P. - Computation of steady-state probabilities for infinite state Markov chains with repeating rows. ORSA J. on Computing, 5, pp. 292-303,(1993).

Gmenfelder R. and Robert S. - Which arrival law parameters are decisive for queueing system performance. Proc. of ITC 14, (1994).

He Q. and Jewkes E. M. - A level crossing analysis of the MAP/G/1 queue. In Matrix-analytic Methods in Stochastic Models, Eds., S. R. Chakravarthy and A. S. Alfa, Marcel Dekker, pp. 107-116, (1996).

Heffes H. and Lucantoni D. M. - A Markov modulated characterization of packetized voice and data traffic and related statistical multiplexer performance. IEEE Journal on Selected Areas in Communication, special issue on Network Performance Evaluation, SAC-4, 6, pp. 856-868, (1986).

Herrmann C. - Correlation effect on per-stream QOS parameters of ATM traffic superpositions relevent to Connection Admission Control. IEEE International Conference on Communications, pp. 1027-1031, (1993).

Hofkens T., Spaey K. and Blondia C. - Transient Analysis of the D-BMAP/G/1 Queue with an Application to the Dimensioning of a Playout Buffer for VBR Video. Proc. of Networking'04. Lecture Notes in Computer Science, Vol. 3042, pp. 1338-1343, (2004).

Hryn G., Jerzak Z. and Chydzinski A. - MMPP-based HTTP traffic generation with multiple emulated sources. Archiwum Informatyki Teoretycznej i Stosowanej, 16(4), pp. 321-335, (2004).

Iyer S., Kompella R. R. and McKeown N. - Analysis of a memory architecture for fast packet buffers. In Proc. of IEEE High Performance Switching and Routing, Dallas, Texas, May, (2001).

Jean-Marie A., Calash Y. and Alemua T. - On the compromise between burstiness and frequency of events. Performance Evaluation, Vol. 62, Issues 1-4, pp. 382-399,

Jedrus S. - The design of multiple correlated multifractal traffic models. Archiwum Informatyki Teoretycznej i Stosowanej, vol. 12, No. 4, (2000).

Kang S. and Sung D. - Two-state MMPP modelHng of ATM superposed traffic streams based on the characterisation of correlated interarrival times, in: Proc. of IEEE GLOBECOM '95;pp. 1422-1426,(1995).

Kang S. H., Kim Y. H., Sung D. K. and Choi B. D. - An application of Markovian arrival process (MAP) to modeling superposed ATM cell streams. IEEE Transactions on Communications 50(4): pp. 633-642, (2002).

Kang K. and Kim C. - Performance analysis of statistical multiplexing of heterogeneous discrete-time Markovian arrival processes in an ATM network. Computer Communications, 20, pp. 970-978, (1997).

Kendall D. G. - Stochastic processes occuring in the theory of queues and their analysis by the method of imbedded Markov chain. American Mathematical Statistics 24, pp. 338-354, (1953).

Kim Y. H. and Un C. K. - Performance analysis of statistical multiplexing for heterogeneous bursty traffic in ATM network. IEEE Trans. Commun. 42(2-4) pp. 745-753, (1994).

Kleinrock L. - Queueing Systems: Theory. John Wiley and Sons New York, (1975).

Klemm A., Lindemann C. and Lohmann M. - Traffic Modeling of IP Networks Using the Batch Markovian Arrival Process. Proc. International Conference on Computer Performance Evaluation, Modelling Techniques and Tools, Lecture Notes In Computer Science 2324, pp. 92-110, (2002).

Klemm A., Lindemann C. and Lohmann M. - Traffic Modeling and Characterization for UMTS Networks, Proc. GLOBECOM 2001, pp. 1741-1746, San Antonio TX, November, (2001).

Klemm A., Lindemann C. and Lohmann M. - Modeling IP traffic using the batch Markovian arrival process. Performance Evaluation, Vol. 54, Issue 2, (2003).

Kofman D. and Korezlioglu H. - Loss probabilities and delay and jitter distributions in a finite buffer queue with heterogeneous batch Markovian arrival processes. IEEE Global Telecommunications Conference, 2, pp. 830-834, (1993).

Korolyuk S. - Granicznyje zadaczi dla słotnychpuassonowskichprocessow. Naukowa Dumka, Kijów, (1975).

Koutsonikolas D, and Hu Y. C. - The Case for FEC-Based Rehable Multicast in Wireless Mesh Networks. Proc. of the 37th lEEE/IFIP International Conference on Dependable Systems and Networks, pp. 491-501, (2007).

Kulkami L. and Li S. Q. - Transient behaviour of queueing systems with correlated traffic. Perform. Eval. 27&28, pp. 117-145, (1996).

Landman J. and Kritzinger P. - Delay analysis of downlink IP traffic on UMTS mobile networks. Performance Evaluation 62, pp. 68-82, (2005).

Latouche G. and Ramaswami V. - A logarithmic reduction algorithm for quasi-birth-deathprocesses.LAppl.Prob., 30, pp. 650-674,(1993). ,

Latouche G. - Algorithms for infinite Markov chains with repeating columns. In Linear algebra, queueing models and Markov chains. Eds., Meyer, CD. and R. J. Plem-mons, pp. 231-265, (1993).

Latouche G. and Stewart G. W. - Numerical methods for M/G/1 type queues. In Computations with Markov chains. Ed., W. J. Stewart, Kluwer Academic pubHshers, pp. 571-581,(1996).

Lee H. W., Park N. I. and Jeon J. - A new approach to the queue length and waiting time of BMAP/G/1 queues. Computers & Operations Research, Vol. 30, pp. 2021-2045, (2003).

Lee H. W., Lee S. W. and Jeon J. - Using Factorization in Analyzing D-BMAP/G/1 Queues. Journal of Applied Mathematics and Stochastic Analysis, Vol. 2005, No. 2, pp. 119-132,(2005).

Lee H. W. and Back J. W. - BMAP/G/1 queue under D-policy: queue length analysis. Stochastic Models, Vol. 21, pp. 484-505, (2005).

Lee H. W., Moon J. M., Kim B. K., Park J. G. and Lee S. W. - A simple eigenvalue method for low-order D-BMAP/G/1 queues. Applied Mathematical Modelling, Vol. 29, pp. 277-288, (2005).

Lee D. S. and Li S. Q. - Transient analysis of multi-server queues with Markov-modulated Poisson arrivals and overload control. Perform. Eval. 16, No. 1-3, pp. 49-66, (1992).

Le Ny L. M. and Sericola B. - Transient Analysis of the BMAP/PH/1 Queue. International Journal of Simulation: Systems, Science & Technology. Special Issue on Analytical & Stochastic Modeling Techniques, 3(3-4), (2002).

Leland W., Taqqu M., Willinger W. and Wilson D. - On the self-similar nature of ether-net traffic (extended version). IEEE/ACM Transactions on Networking 2(1): pp. 1-15, (1994).

Li S. and Hwang C. - On the convergence of traffic measurement and queuing analysis: A statistical match and queuing (SMAQ) tool, IEEE/ACM Transactions on Networking, 95-110, (1997).

Lucantoni D. M. - New results on the single server queue with a batch Markovian arrival process. Commun. Stat., Stochastic Models 7, No.l, pp. 1-46, (1991).

Lucantoni D. M., Choudhury G. L. and Whitt W. - The transient BMAP/G/1 queue. Commun. Stat., Stochastic Models 10, No. 1, pp. 145-182, (1994).

Lucantoni D. - Further transient analysis of the BMAP/G/1 queue. Commun. Stat., Stochastic Models 14, No. 1-2, pp. 461-478, (1998).

Lucantoni D. M., Meier-Hellstem K. S. and Neuts M. F. - A single-server queue with server vacations and a class of non-renewal arrival processes. Advances in Applied Probability 22, pp. 676-705, (1990).

Lucantoni D. M. and Neuts M. F. - Simpler proofs of some properties of the fundamental period of the MAP/G/1 queue. J. Appl. Prob., 31, pp. 235-243, (1994).

Machihara F. - Bridge between preemptive and non-preemptive queueing models. Performance Evaluation, 23, pp. 93-106, (1995).

Machihara F. and Hatoyama-machi H. - A preemptive priority queue with nonrenewal inputs. In Matrix- analytic Methods in Stochastic Models, Eds., S. R. Chakravarthy and A. S. Alfa, Marcel Dekker, pp. 21-42, (1996).

Meier-Hellstem K. - A fitting algorithm for Markov-modulated Poisson process having two arrival rates, European Journal of Operational Research 29, (1987).

Meini B. - New convergence results on functional iteration techniques for the numerical solution of M/G/1 type Markov chains. Numer. Math., 78, pp. 39-58, (1997).

Meini B. - An improved FFT-based version of Ramaswamis formula. Stochastic Models, 13, pp. 223-238, (1997).

Meini B. - Solving M/G/1 type Markov chains: Recent advances and applications. Stochastic Models, 14, pp. 479-496, (1998).

Murthy G. R. Kim M. and Coyle E. J. - Equilibrium analysis of skip free Markov chains: nonlinear matrix equations. Stochastic Models, 7, pp. 547-571, (1991).

Naoumov V., Krieger U. R. and Wagner D. - Analysis of a multiserver delay-loss system with a general Markovian arrival process. In Matrix-analytic Methods in Stochastic Models, Eds., S. R. Chakravarthy and A. S. Alfa, Marcel Dekker, pp. 43-66, (1996).

Neuts M. F. - Renewal processes of phase type. Naval Res. Logist. Quart. 25, pp. 445-454, (1978).

Neuts M. F. - A Versatile Markovian Point Process Journal of Applied Probability 14, pp. 764-779, (1979).

Neuts M. F. - Structured Stochastic Matrices of M/G/1-type and their Applications, Marcel Dekker, New York, NY, (1989).

Neuts M. F. - The fundamental period of the queue with Markov-modulated arrivals. Probability, Statistics and Mathematics: Papers in Honor of Samuel Karlin, Academic Press, pp. 187-200,(1989).

Niu Z., Takahashi Y. and Endo N. - Performance evaluation of SVC-based IP-over-ATM networks. Transactions on Communications, E81-B, pp. 948-957, (1998).


Nogueira A., Salvador P., Valadas R. and Pacheco A. - Modeling self-similar traffic through Markov modulated Poisson processes over multiple time scales. 6-th IEEE International Conference on High Speed Networks and Multimedia Communications (HSNMC'03), Lecture Notes in Computer Science 2720, pp. 550-560, July, (2003).

Nonnenmacher J., Biersack E. and Towsley D. - Parity-based loss recovery for reliable multicast transmission. Proc. SIGCOMM 97, Cannes, France, pp. 289-299, (1997).

Norros I. - A storage model with self-similar input. Queuing Systems vol. 16, pp. 387-396,(1994).

Nunes C. and Pacheco A. - Parametric estimation in MMPP(2) using time discretization. Proc. of the 2nd Internet. Symposium on Semi-Markov Models: Theory and Applications, December, (1998).


Osiowski J. - Zarys rachunku operatorowego. Wydawnictwa Naukowo Techniczne, Warszawa, (1981).

Papir Z. - Ruch telekomunikacyjny i przeciążenia sieci pakietowych. Wydawnictwa Komunikacji i Łączności, Warszawa, (2001).

Paxson V., Floyd S. - Wide-area traffic: the failure of Poisson modeling. IEEE/ACM Trans. Netw., Volume 3, Issue 3, pp. 226-244, (1995).

Podolsky M., Romer C. and McCanne S. - Simulation of FEC-Based Error Control for Packet Audio on the Internet, Proc. of INFOCOM'98, pp. 505-515, (1998).

Puhafito A., Balakrishnan M., Trivedi K. S. and Viniotis I. - Buffer sizing for ABR traffic in an ATM switch. IEEE International Conference on Communications, 1, pp. 316-320, (1995.

Raina G. and Wischik D. - Buffer sizes for large multiplexers: TCP queueing theory and instability analysis. In EuroNGI, (2005).

Ramaswami V. - The N/G/1 queue and its detailed analysis. Adv. Appl. Prob. 12, pp. 222-261, (1980).

Ramaswami V. - Nonlinear matrix equations in applied probability - Solution techniques and open problems. SIAM Review, 30, pp. 256-263, (1988).

Ramaswami V. and Wang J. L. - Discrete time queueing analysis of ATM systems with phasetype distributed talk spurts traffic sources. IEEE International Conference on Communications, 2, pp. 1093-1098, (1996).

Ramaswami V. and Wang J. L. - Discrete time queueing analysis of ATM systems with heterogeneous traffic sources. IEEE Global Telecommunications Conference, 1, pp. 623-628, (1996).

Ramaswami V. - A stable recursion for the steady state vector in Markov chains of M/G/1 type. Stochastic Models, 4, pp. 183-188, (1988).

Ramaswamy V., Cuellar L., Eidenbenz S., Hengartner N., Ambuhl C. and Weber B. - Light-Weight Control of Non-responsive Traffic with Low Buffer Requirements. Lecture Notes in Computer Science 4479, pp. 856-877, (2007).

Rananand N. - Approximating a variable bit rate source by Markov processes. IEEE Global Telecommunications Conference, 2, pp. 1107-1112, (1994).

Rasti S. - Moments of the queue occupancy in an ATM multiplexer loaded with on/off sources. ICCS-Conference Proceedings, pp. 754-759, (1994).

Riedi R., Crouse M., Ribeiro V. and Baraniuk R. - A multifractal wavelet model with application to network traffic. In IEEE Trans, on Information Theory, 45(3), pp. 992-1018,(1999).

Riska A. and Smimi E. - Exact aggregate solutions for M/G/1-type Markov processes. Proc. of ACM SIGMETRICS Conf., Marina del Rey, CA, pp. 86-96, (2002).

Rizzo L. and Visicano L. - RMDP: an FEC-based reliable multicast protocol for wireless environments. Mobile Computing and Communications Review, vol. 2, no. 2, (1998).

Robert S. and Le Boudec J. - New models for self-similar traffic. Performance Evaluation 30(1/2), (1997).

Ryden T. - An EM algorithm for parameter estimation in Markov modulated Poisson processes, Comput. Stat. Data Anal. 21, pp. 431-447, (1996).

Saito H. - Performance evaluation and dimensioning for AAL2 CLAD. Proceedings-IEEE INFOCOM, 1, pp. 153-160, (1999).

Salvador P., Valadas R. and Pacheco A. - Multiscale Fitting Procedure Using Markov Modulated Poisson Processes. Telecommunication Systems 23:1-2, pp. 123-148, (2003).

Salvador P., Pacheco A. and Valadas R. - Modeling IP traffic: joint characterization of packet arrivals and packet sizes using BMAPs. Computer Networks 44, pp. 335-352, (2004).

Salvador P., Nogueira A., Valadas R. and Pacheco A. - Multi-time-Scale Traffic Modeling Using Markovian and L-Systems Models. Proc. ECUMN'04, Lecture Notes on Computer Science 3262, pp. 297-306, (2004).

Sashisekaran T. and Chakravarthy S. - A stochastic model for a hysteresis based priority queueing strategy for ATM networks with batch arrivals - theory. Proceedings of the third IEEE Symposium on Computers and Communications, pp. 530-536, (1998).

Shah-Heydari S. and Le-Ngoc T. - MMPP models for multimedia traffic. Telecommunication Systems 15, No. 3-4, pp. 273-293, (2000).

Shu Y., Jin Z., Wang J. and Yang O. W. - Prediction-based admission control using FARIMA models. Proc. IEEE ICC'OO, vol. 3, New Orleans, pp. 1325-1329, June, (2000).

Singh L. N. and Dattatreya G. R. - A novel approach to parameter estimation in Markov-modulated Poisson processes, 2004 IEEE Emerging Technologies Conference (ETC), Richardson, TX, Oct., (2004).

Skelly P., Schwartz M. and Dixit S. - A histogram-based model for video traffic behavior in an ATM multiplexer. IEEE/ACM Trans. Netw. 1(4), pp. 446-459, (1993).

Sohraby K. and Sidi M. - On the performance of bursty and modulated sources subject to leaky bucket rate-based access control schemes. IEEE Transactions on Communications, 42, pp. 477-487, (1994).

Sridhar R., Rosenberg C. and Kumar A. - Revenue maximisation in ATM networks using the CLP capability and buffer priority management. IEEE Global Telecommunications Conference, 1, pp. 734-738, (1995).

Subramanian V. G. and Srikant R. - Statistical multiplexing with priorities: Tail probabilities of queue lengths and waiting times. Proceedings of the IEEE Conference on Decision and Control, 2, pp. 1780-1785, (1997).

Takagi H. - Queueing analysis - Vacation and Priority System. North-Holland, Amsterdam, (1991).

Takagi H. - Queueing analysis - Finite Systems. North-Holland Amsterdam, (1993).

Takine T, Matsumoto Y, Suda T. and Hasegawa T. - Mean waiting times in nonpre-emptive priority queues with Markovian arrival and i.i.d. service processes. Performance Evaluation, 20, pp. 131-149, (1994).

Takine T, Sengupta B. and Hasegawa T. - Conformance measure for traffic shaping in high speed networks with an application to the leaky bucket. INFOCOM, 2, pp. 474-481,(1994).

Trivedi K. - Probability and Statistics with Reliability Queuing and Computer Science Applications (2nd edition). John Wiley and Sons, New York, (2001).

Tsakiridou S. and Stavrakakis I. - Mean delay analysis of a statistical multiplexer with batch arrival processes - a generalization to Viterbis formula. Performance Evaluation 25, pp. 1-15,(1996).

Van Houdt B. and Blondia C. - Approximated transient queue length and waiting time distributions via steady state analysis. Stochastic Models, 21:2/3, pp. 725-744, (2005).

Villamizar C. and Song C. - High Performance TCP in the ANSNET. ACM SIG-COMM Computer Communication Review, 24(5), pp. 45-60, November, (1994).

Wang S. S. and Silvester J. A. - Discrete-time performance model for integrated service ATM multiplexers. IEEE Global Telecommunications Conference, 2, pp. 757-761,(1993).

Wang S. S. and Silvester J. A. - Estimate the loss and tail probabilities for multimedia communication systems. IEEE Global Telecommunications Conference, 2, pp. 908-912, (1994).

Wei W., Wang B. and Towsley D. - Continuous-time hidden Markov models for network performance evaluation. Performance Evaluation 49, pp. 129-146, (2002).

Willinger W., Taqqu M. S., Sherman R. and Wilson D. V. - Self-Similarity through High Variability: Statistical Analysis of Ethernet LAN Taffic at the Source Level. Proc. ACM SIGCOMM95, pp. 100-113, (1995).

Wischik D. and McKeown N. - Part I: Buffer Sizes for Core Routers. ACM SIG-COMM Computer Communication Review 35, pp. 75-78, (2005).

Wong T. C, Mark J. W. and Chua K. C. - Delay performance of voice and MMPP video traffic in a cellular wireless ATM network. lEE Proceedings Communications, Vol. 148, 302-309, (2001).

Wójcicki R., Hryń G., Chydziński A. - Transmisja danych protokołów TCP/IP w sieciach optycznych. Rozdział w: Sieci komputerowe: aplikacje i zastosowania. Praca zbiór, pod redakcją A. Kwietnia, J. Obera, B. Pochopienia i P. Gaja. Wydawnictwa Komunikacji i Łączności, Warszawa (2007).

Wu G. L. and Mark J. W. - Computational Methods for Performance Evaluation of a Statistical Multiplexer Supporting Bursty Traffic. IEEE/ACM Transactions on Networking, Vol. 4, No. 3, pp. 386-397, (1996).

Ye J. and Li Sanqi. - Analysis of multi-media traffic queues with finite buffer and overload controll: Algorithm. Proceedings-IEEE INFOCOM, 3, pp. 1464-1474, (1991).

Yoshihara T., Kasahara S. and Takahashi Y. - Practical time-scale fitting of self-similar traffic with Markov-modulated Poisson process, Telecommunication Systems 17(1/2), pp. 185-211,(2001).

DOI: http://dx.doi.org/10.21936/si2007_v28.n3B.547