Analysis of Linked in Series Servers with Blocking, Priority Feedback Service and Threshold Policy

Authors: Walenty Oniszczuk

Abstract:

The use of buffer thresholds, blocking and adequate service strategies are well-known techniques for computer networks traffic congestion control. This motivates the study of series queues with blocking, feedback (service under Head of Line (HoL) priority discipline) and finite capacity buffers with thresholds. In this paper, the external traffic is modelled using the Poisson process and the service times have been modelled using the exponential distribution. We consider a three-station network with two finite buffers, for which a set of thresholds (tm1 and tm2) is defined. This computer network behaves as follows. A task, which finishes its service at station B, gets sent back to station A for re-processing with probability o. When the number of tasks in the second buffer exceeds a threshold tm2 and the number of task in the first buffer is less than tm1, the fed back task is served under HoL priority discipline. In opposite case, for fed backed tasks, “no two priority services in succession" procedure (preventing a possible overflow in the first buffer) is applied. Using an open Markovian queuing schema with blocking, priority feedback service and thresholds, a closed form cost-effective analytical solution is obtained. The model of servers linked in series is very accurate. It is derived directly from a twodimensional state graph and a set of steady-state equations, followed by calculations of main measures of effectiveness. Consequently, efficient expressions of the low computational cost are determined. Based on numerical experiments and collected results we conclude that the proposed model with blocking, feedback and thresholds can provide accurate performance estimates of linked in series networks.

Keywords: Blocking, Congestion control, Feedback, Markov chains, Performance evaluation, Threshold-base networks.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1070289

References:

[1] I. Awan, "Analysis of multiple-threshold queues for congestion control of heterogeneous traffic streams", Simulation Modelling Practice and Theory, vol. 14, pp. 712-724, 2006.
[2] S. Balsamo, V. de Nito Persone, R. Onvural, "Analysis of Queueing Networks with Blocking", Boston: Kluwer Academic Publishers, 2001.
[3] S. Balsamo, V. de Nito Persone, P. Inverardi, A review on queueing network models with finite capacity queues for software architectures performance predication, Performance Evaluation, vol. 51, no. 2-4, pp. 269-288, 2003.
[4] A. Badrah, T. Chach├│rski, J. Domanska, J.-M. Fourneau, F. Quessette, "Performance evaluation of multistage interconnection networks with blocking - discrete and continuous time Markov models", Archiwum Informatyki Teoretycznej i Stosowanej, vol. 14, no. 2, pp. 145-162, 2002.
[5] G. Bolch, S. Greiner, H. de Meer, K.S. Trivedi, Queueing Networks and Markov Chains. Modeling and Performance Evaluation with Computer Science Applications, New York: John Wiley, 1998.
[6] A. Bose, X. Jiang, B. Lui, G. Li, "Analysis of manufacturing blocking systems with Network Calculus", Performance Evaluation, vol. 63, pp. 1216-1234, 2006.
[7] R.J. Boucherie, N.M. van Dijk, "On the arrival theorem for product form queueing networks with blocking", Performance Evaluation, vol. 29, no. 3, pp. 155-176, 1997.
[8] S-T. Cheng, Ch-M. Chen, I-R. Chen, "Performance evaluation of an admission control algorithm: dynamic threshold with negotiation", Performance Evaluation, vol. 52, pp. 1-13, 2003.
[9] B.D. Choi, S.H. Choi, B. Kim, D.K. Sung, "Analysis of priority queueing systems based on thresholds and its application to signalling system no. 7 with congestion control", Computer Networks, vol. 32, pp. 149-170, 2000.
[10] A.W. Eckford, F.R. Kschischang, S. Pasupathy, "On Designing Good LDPC Codes for Markov Channels", IEEE Transactions on Information Theory, vol. 53, no.1, pp. 5-21, 2007.
[11] A. Economou, D. Fakinos, "Product form stationary distributions for queueing networks with blocking and rerouting", Queueing Systems, vol. 30, no. 3/4, pp. 251-260, 1998.
[12] A. Gomez-Corral, M.E. Martos, "Performance of two-stage tandem queues with blocking: The impact of several flows of signals", Performance Evaluation, vol. 63, pp. 910-938, 2006.
[13] U.C. Gupta, S.K. Samanta, R.K. Sharma, M.L. Chaudhry, "Discretetime single-server finite-buffer under discrete Markovian arrival process with vacations", Performance Evaluation, vol. 64, pp. 1-19, 2007.
[14] T. Katayama, K. Kobayashi, "Analysis of a nonpreemptive priority queue with exponential timer and server vacations", Performance Evaluation, vol. 64, pp. 495-506, 2007.
[15] C.S. Kim et al. "The BMAP/G/1-> ┬À/PH/1/M tandem queue with feedback and losses", Performance Evaluation, vol. 64, pp. 802-818, 2007.
[16] D. Kouvatsos, I.U. Awan, R.J. Fretwell, G. Dimakopoulos, "A costeffective approximation for SRD traffic in arbitrary multi-buffered networks", Computer Networks, vol. 34, pp. 97-113, 2000.
[17] J.C.S. Lui, L. Golubchik, "Stochastic complement analysis of multiserver threshold queues with hysteresis", Performance Evaluation, vol. 35, pp. 19-48, 1999.
[18] R.D. van der Mei, B.M.M. Gijsen, N., in-t Veld, J.L. van den Berg, "Response times in a two-node queueing network with feedback", Performance Evaluation, vol. 49, pp. 99-110, 2002.
[19] Oniszczuk W. Analysis of an Open Linked Series Three-Station Network with Blocking, in Advances in Information Processing and Protection, J. Pejas, K. Saeed Eds., New York: Springer Science+Business Media, LLC, 2007, pp. 419-429.
[20] R. Onvural, "Survey of closed queuing networks with blocking", Computer Survey, vol. 22, no.2, pp. 83-121, 1990.
[21] Perros H.G. Queuing Networks with Blocking. Exact and Approximate Solution, New York: Oxford University Press, 1994.
[22] W.J. Stewart, Introduction to the Numerical Solution of Markov Chains, New Jersey: Princeton University Press, 1994.
[23] T. Tolio, S.B. Gershwin, "Throughput estimation in cyclic queueing networks with blocking", Annals of Operations Research, vol. 79, pp. 207-229, 1998.
[24] E. Xu, A.S. Alfa, "A vacation model for the non-saturated Readers and Writers system with a threshold policy", Performance Evaluation, vol. 50, pp. 233-244, 2002.
[25] H. Zhang, Z-P. Jiang, Y. Fan, S. Panwar, "Optimization based flow control with improved performance", Communications in Information and Systems, vol.4, no. 3, pp. 235-252, 2004.