Analysis of Linked in Series Servers with Blocking, Priority Feedback Service and Threshold Policy
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:57197", author = "Walenty Oniszczuk", title = "Analysis of Linked in Series Servers with Blocking, Priority Feedback Service and Threshold Policy", 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.", volume = "3", number = "3", pages = "709-8", }
