Estimation of Network Disordering Effects by In-depth Analysis of the Resequencing Buffer Contents in Steady-state
Treść / Zawartość
The paper is devoted to the analytic analysis of resequencing issue, which is common in packet networks, using queueing-theoretic approach. The authors propose the mathematical model, which describes the simplest setting of packet resequencing, but which allows one to make the first step in the in-depth-analysis of the queues dynamics in the resequencing buffer. Specifically consideration is given to N-server queueing system (N > 3) with single infinite capacity buffer and resequencing, which may serve as a model of packet reordering in packet networks. Customers arrive at the system according to Poisson flow, occupy one place in the buffer and receive service from one of the servers, which is exponentially distributed with the same parameter. The order of customers upon arrival has to be preserved upon departure. Customers, which violated the order are kept in resequencing buffer which also has infinite capacity. It is shown that the resequencing buffer can be considered as consisting of n, 1 ≤ n ≤ N −1, interconnected queues, depending on the number of busy servers, with i-th queue containing customers, which have to wait for i service completions before they can leave the system. Recursive algorithm for computation of the joint stationary distribution of the number of customers in the buffer and servers, and each queue in resequencing buffer are being obtained. Numerical examples, which show the dynamics of the characteristics of the queues in resequencing buffer are given.
Bibliogr. 19 poz., rys.
-  O. Boxma, G. Koole, and Z. Liu, „Queueing-theoretic solution methods for models of parallel and distributed systems", in Performance Evaluation of Parallel and Distributed Systems: Solution Methods. Proceedings of the Third QMIPS Workshop CWI. Tract 105 & 106. Amsterdam, Netherlands: Centrum voor Wiskunde en Informatica, 1994, pp. 1-24.
-  B. Dimitrov, D. Green Jr., V. Rykov, and P. Stanchev, „On performance evaluation and optimization problems in queues with resequencing", in Advances in Stochastic Modelling, J. Artalejo and A. Krishnamoorty, Eds. New Jersey: Notable Publications Inc., 2002, pp. 55-72.
-  K. Leung and V. O. K. Li, „A resequencing model for high-speed packet-switching networks", J. Comp. Commun., vol. 33, no. 4, pp. 443-453, 2010.
-  S. Agrawal and R. Ramaswamy, „Analysis of the resequencing delay for M/M/m systems", in Proc. ACM Sigmetrics Conf. Measur. Model. Comp. Syst, Banff, Alberta, Canada, 1987, vol. 15, pp. 27-35.
-  Y. Xia and D. N. C. Tse, „On the large deviations of resequencing queue size: 2-M/M/1 Case", IEEE Trans. Inform. Theory, vol. 54, no. 9, pp. 4107-4118, 2008.
-  F. Baccelli, E. Gelenbe, and B. Plateau, „An end to end approach to the sequencing problem", Rapports de Recherche, no. RR-0097, INRIA, Nov. 1981 [Online]. Available: https://hal.inria.fr/inria-00076464
-  S. Chowdhury, „Distribution of the total delay of packets in virtual circuits", in Proc. 10th Ann. Joint Conf. IEEE Comp. Commun. Soc. INFOCOM'91, Bal Harbour, FL, USA, 1991, vol. 2. pp. 911-918.
-  S. Chakravarthy, S. Chukova, and B. Dimitrov, „Analysis of MAP/M/2/K queueing model with infinite resequencing buffer", J. Perform. Eval., vol. 31. no. 3-4. pp. 211-228, 1998.
-  C. De Nicola, A. Pechinkin, and R. Razumchik, „Stationary characteristics of homogenous Geo/Geo/2 queue with resequencing in discrete time", in Proc. 27th Eur. Conf. Model. Simul. ECMS 2013, Alesund, Norway, 2013, pp. 594-600.
-  R. Gogate and S. Panwar, „Assigning customers to two parallel servers with resequencing", IEEE Commun. Lett., vol. 3, no. 4, pp. 119-121, 1999.
-  T. Huisman and R. J. Boucherie, „The sojourn time distribution in an infinite server resequencing queue with dependent interarrival and service times", J. Appl. Probab., vol. 39, no. 3, pp. 590-603, 2002.
-  M. Jain and G. C. Sharma, „Nopassing multiserver queue with additional heterogeneous servers and inter-dependent rates", in joint conference 5th Canadian Conf. in Applied Statist. STATISTICS 2011 and 20th Conf. Forum for Interdiscip. Mathem. „Interdisciplinary Mathematical & Statistical Techniques" IMST 2011, Montreal, Quebec, Canada, 2011.
-  M. Lelarge, „Packet reordering in networks with heavy-tailed delays", Mathem. Methods Oper. Res., vol. 67, no. 2, pp. 341-371, 2008.
-  I. Caraccio, A. V. Pechinkin, and R. V. Razumchik, „Stationary characteristics of MAP/PH/2 resequencing queue", in Proc. 1st Eur. Conf. on Queueing Theory ECQT 2014, Ghent, Belgium, 2014, pp. 42-46.
-  T. Takine, J. Ren, and T. Hasegawa, „Analysis of the resequencing buffer in a homogeneous M/M/2 Queue", Perform. Eval., vol. 19, no. 4, pp. 353-366, 1994.
-  A. V. Pechinkin, I. Caraccio, and R. V. Razumchik, „Joint stationary distribution of queues in homogenous M/M/3 queue with resequencing", in Proc. 28th Eur. Conf. Model. Simul. ECMS 2014, Brescia, Italy, 2014, pp. 558-564.
-  I. Caraccio, A. V. Pechinkin, and R. V. Razumchik, „On joint stationary distribution in exponential multiserver reordering queue", in Proc. 12th Int. Conf. Numerical Anal. Appl. Mathem. ICNAAM 2014, Rhodes, Greece, 2014.
-  A. V. Pechinkin and R. V. Razumchik, „Joint stationary distribution of m queues in the n-server queueing system with reordering", Inform. and its Appl., vol. 9, no. 3, pp. 26-32, 2015 (in Russian).
-  J. Riordan, Stochastic Service Systems. New York: Wiley, 1962.
Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.