A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms

Demetres D.  Kouvatsos; Jumma S. Alanazi; Kevin Smith

doi:10.3934/naco.2011.1.781

Article Contents

2011, Volume 1, Issue 4: 781-816. Doi: 10.3934/naco.2011.1.781

This issue Previous Article Markovian characterization of node lifetime in a time-driven wireless sensor network Next Article

A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms

1.
Networks and Performance Engineering Research Group, Informatics Research Institute, University of Bradford, Bradford, BD7 1DP

Received: June 2011

Revised: September 2011

Published: October 2011

Abstract Related Papers Cited by

Abstract

A generic maximum entropy (ME) product-form approximation is proposed for arbitrary single class open first-come-first-served (FCFS) queueing network models with blocking (QNMs-B), subject to bursty GE-type interarrival and service times and the mixed blocking mechanisms (BMs) of Blocking-After-Service (BAS), Blocking-Before-Service (BBS) and Repetitive-Service (RS) Blocking with Random (RS-RD) and Fixed (RS-FD) destinations. A new GE-type analytic framework is devised, based on the ME analysis of a virtual multiple class GE/GE/1/N+U queueing system with finite capacity, $N (N>1)$ augmented by $U (U\geq1)$ auxiliary-waiting lines, to determine the first two moments of BAS- and BBS-dependent effective service times towards a node-by-node decomposition of the entire network. In this context, a unified ME algorithm is devised for the approximate analysis of arbitrary open FCFS QNMs-B with a mixture of the BMs of BAS, BBS, RS-RD and RS-FD. Typical numerical tests are carried out to assess the credibility of the unified ME algorithm against discrete event simulation and also establish GE-type experimental performance bounds. A critique on the feasibility of ME formalism for QNMs-B and suggested extensions are included.

Keywords:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Related Papers

Cited by

References

[1]	I. F Akyildiz and C. C Huang, Exact analysis of multi-job class networks of queues with blocking-after-sevice, in ''Proc. of the 2nd Inter. WS on Queueing Networks with Finite Capacity" (eds. R. O Onvural and I. F Akyildiz), Res. Tringle Park, (1992), 258-271.
[2]	J. S. Alanazi and D. D. Kouvatsos, On the experimentation with the unified ME algorithm for arbitrary open QNMs-B, Technical Report TR7-NetPEn-April 11, University of Bradford, 2011.
[3]	J. S. Alanazi and D. D. Kouvatsos, A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms, in ''Proc. of the IEEE/IPSJ Workshop WS-8: Future Internet Engineering of the SAINT 2011 International Symposium on Applications and the Internet", Munich, (2011), 292-296.doi: 10.1109/SAINT.2011.91.
[4]	T. Altiok and H. G. Perros, Approximate analysis of arbitrary configurations of queueing networks with blocking, Ann. Oper. Res., 9 (1987), 481-509.doi: 10.1007/BF02054751.
[5]	S. A. Assi, D. D. Kouvatsos, I. M. Mkwawa and K. Smith, A unified ME decomposition algorithm of open queueing network modes with blocking, in ''Tech. Proc. of HET-NETs 08 International Working Conference on Performance Modelling and Evaluation of Heterogeneous Networks", Blekinge Institute of Technology, (2008), A19.1-A19.10.
[6]	S. Balsamo, V. D. Nitto Persone and R. Onvural, "Analysis of Queueing Networks with Blocking," Kluwer Academic publishers, Dordrecht, 2001.
[7]	S. Balsamo, Queueing networks with blocking: snalysis, solution algorithms and properties, in ''Network Performance Engineering, A Handbook on Convergent Multi-Service Networks and Next Generation Internet, Lecture Notes in Computer Science" (ed. D.D. Kouvatsos), 5233 (2011), 233-257.doi: 10.1007/978-3-642-02742-0.
[8]	F. Baskett, K. M. Chandy, R. R. Muntz and F. G. Palacios, Open, closed and mixed networks of queues with different classes of customers, J. ACM, 22 (1975), 248-260.doi: 10.1145/321879.321887.
[9]	V. E. Benes, "Mathematical Theory of Connecting Networks and Telephone Traffic," Academic Press, New York, 1965.
[10]	J. Beran, "Statistics for Long-Memory Processes," Chapman and Hall, Boca Raton, 1994.
[11]	R. M. Bryant, A. E. Krzesinski, M. S. Lakshmi and K. M. Chandy, The MVA priority approximation, T.O.C.S., 2 (1984), 335-359.
[12]	C. G. Chakrabarti and D. E. Kajal, Boltzmann-Gibbs entropy: axiomatic characterisation and application, Internat. J. Math. Math. Sci., 23 (2000), 243-251.doi: 10.1155/S0161171200000375.
[13]	K. M. Chandy, U. Herzog and L. Woo, Approximate analysis of general queuing networks, IBM J. of Res. Dev., 19 (1975), 43-49.doi: 10.1147/rd.191.0043.
[14]	Y. L. Chen and C. Chen, Performance analysis of non-preemptive HOL GE/G/1 queue with two priority classes of SIP-T signaling system in carrier grade VoIP network, J. Chin. Inst. Eng., 33 (2010), 191-206.doi: 10.1080/02533839.2010.9671610.
[15]	P. J. Courtois, U. Herzog and L. Woo, "Decomposability: Queueing and Computer System Applications," Academic Press, New York, 1977.
[16]	M. A El-Affendi and D. D Kouvatsos, A maximum entropy analysis of the M/G/1 and G/M/1 queueing systems at equilibrium, Acta info., 19 (1983), 339-355.
[17]	A. Ferdinand, A statistical mechanical approach to systems analysis, IBM J. Res. Dev., 14 (1970), 539-547.doi: 10.1147/rd.145.0539.
[18]	C. H. Foh, B. Meini, B. Wydrowski and M. Zuerman, Modelling and performance evaluation of GPRS, in ''Proc. Of IEEE VTC", (2001), 2108-2112.
[19]	E. Gelenbe and G. Pujolle, The behaviour of a single queue in a general queueing network, Acta info., 7 (1974), 123-136.
[20]	E. Gelenbe and I. Mitrani, "Analysis and Synthesis of Computer Systems," Academic Press, London, 1980.
[21]	J. H. Havrda and F. Charvat, Quantification methods of classificatory processes: concept of structural entropy, Kybernatica, 3 (1967), 30-35.
[22]	H. E. Hurst, Long-term storage capacity of reservoirs, Transactions of the American Society of Civil Engineers, 116 (1951), 770-808.
[23]	E. T. Jaynes, Information theory and statistical mechanics, Phys. Rev., 106 (1957), 620-630.doi: 10.1103/PhysRev.106.620.
[24]	E. T. Jaynes, Information theory and statistical mechanics II, Phys. Rev., 108 (1957), 171-190.doi: 10.1103/PhysRev.108.171.
[25]	R. Johnson, Properties of cross-entropy minimization, IEEE Trans. Info. Theory, 27 (1981), 472-482.doi: 10.1109/TIT.1981.1056373.
[26]	J. N. Kapur, "Maximum-entropy Models in Science and Engineering," John Wiley, New York, 1989.
[27]	J. N. Kapur and H. K. Kesavan, "Entropy Optimization Principles with Applications," Academic Press, New York, 1992.
[28]	F. P. Kelly, "Reversibility and Stochastic Networks," Wiley, New York, 1979.
[29]	D. D. Kouvatsos, Maximum entropy methods for general queueing networks, in ''Modelling Techniques and Tools for Performance Analysis" (ed. D. Potier), North-Holland, (1985), 589-609.
[30]	D. D. Kouvatsos, Maximum entropy and the G/G/1/N queue, Acta info., 23 (1986), 545-565.
[31]	D. D. Kouvatsos, A universal maximum entropy algorithm for the analysis of general closed networks, in ''Computer Networks and Performance Evaluation" (eds. T. Hasegawa et al.), North-Holland, (1986), 113-124.
[32]	D. D. Kouvatsos, A maximum entropy analysis of the G/G/1 queue at equilibrium, J. Opl. Res. Soc., 39 (1988), 183-200.
[33]	D. D. Kouvatsos and N. P. Xenios, MEM for arbitrary queueing networks with multiple general servers and repetitive service blocking, Performance Evaluation, 10 (1989), 169-195.doi: 10.1016/0166-5316(89)90009-6.
[34]	D. D. Kouvatsos, P. H. Georgatsos and N. Tabet-Aouel, A universal maximum entropy algorithm for general multiple class open networks with mixed service disciplines, in ''Modelling Techniques and Tools for Computer Performance Evaluation" (eds. R. Puigjaner and D. Potier), Plenum, (1989), 397-419.doi: 10.1007/978-1-4613-0533-0_26.
[35]	D. D. Kouvatsos and N. M. Tabet-Aouel, A maximum entropy priority approximation for a stable G/G/1 queue, Acta info., 27 (1989), 247-286.
[36]	D. D. Kouvatsos and N. M. Tabet-Aouel, Product-form approximations for an extended class of general closed queueing networks, in ''Performance '90' " (eds. P. J. B. King et al.), North-Holland, (1990), 301-315.
[37]	D. D. Kouvatsos and S. G. Denazis, Entropy maximised queueing networks with blocking and multiple job classes, Performance Evaluation, 17 (1993), 189-205.doi: 10.1016/0166-5316(93)90041-R.
[38]	D. D. Kouvatsos, Entropy maximisation and queueing network models, Annals of Oper. Res., 48 (1994), 63-126.doi: 10.1007/BF02023095.
[39]	D. D. Kouvatsos and I. U. Awan, MEM for arbitrary closed queueing networks with RS-blocking and multiple job classes, Annals of Oper. Res., 79 (1998), 231-269.doi: 10.1023/A:1018922705462.
[40]	D. D. Kouvatsos and I. U. Awan, Entropy maximisation and open queueing networks with priorities and blocking, Performance Evaluation, 51 (2003), 191-227.doi: 10.1016/S0166-5316(02)00092-5.
[41]	D. D. Kouvatsos, I. U. Awan, R. J. Fretwell and R. Dimakopoulos, G. A cost-effective approximation for SRD traffic in arbitrary multi-buffered networks, Computer Networks, 34 (2000), 97-113.doi: 10.1016/S1389-1286(00)00099-2.
[42]	D. D. Kouvatsos, Y. Li and W. Xi, Performance modelling and analysis of a 4G handoff priority scheme for cellular networks, in ''Performance Modelling and Analysis of Heterogeneous Networks" (ed. D.D. Kouvatsos), River Publishers, (2009), 215-243.
[43]	D. D. Kouvatsos and S. A. Assi, Generalised entropy maximisation and queues with bursty and/or heavy tails, in ''Network Performance Engineering, A Handbook on Convergent Multi-Service Networks and Next Generation Internet, Lecture Notes in Computer Science," 5233 (2011), 357-392.doi: 10.1007/978-3-642-02742-0.
[44]	D. D. Kouvatsos and S. A. Assi, On the analysis of queues with heavy tails: a non-extensive maximum entropy formalism and a generalisation of the Zipf-mandelbrot distribution, in ''Special IFIP LNCS issue in Honour of Guenter Haring," University of Vienna, 2011, to appear.
[45]	R. A. Marie, An approximate analytical method for general queueing networks, IEEE Trans. Software Eng., 5 (1979), 530-538.doi: 10.1109/TSE.1979.234214.
[46]	B. B. Mandelbrot, "The Fractal Geometry of Nature," W. H. Freeman, New York, 1982.
[47]	R. O. Onvural and I. F. Akyildiz, "Queueing Networks with Finite Capacity," Elsevier Science publishers, Amsterdam, 1993.
[48]	R. O. Onvural, Survey of closed queueing networks with blocking, ACM Comput. Surv., 22 (1990), 83-121.doi: 10.1145/78919.78920.
[49]	H. G. Perros and T. Altiok, "Queueing Networks with Blocking," Elsevier Science publishers, Amsterdam, 1989.
[50]	H. G. Perros, Approximate algorithms for open queueing networks with blocking, in ''Stochastic Analysis of Computer and Communication Systems" (ed. H. Takagi), North-Holland, (1990), 451-494.
[51]	H. G. Perros, "Queueing Networks with Blocking," Oxford University Press, New York, 1994.
[52]	E. Pinsky and Y. Yemini, A statistical mechanics of some interconnection networks, in ''Performance '48' " (ed. E. Gelenbe), North-Holand, (1984), 147-158.
[53]	E. Pinsky and Y. Yemini, The canonical approximation in performance analysis, in ''Computer Networking and Performance Evaluation" (eds. T. Hasegawa et al.), North-Holand, (1986), 125-137.
[54]	M. Reiser and H. Kobayashi, Accuracy of the diffusion approximation for some queuing systems, IBM J. Res. Dev., 18 (1974), 110-124.doi: 10.1147/rd.182.0110.
[55]	K. C. Sevcik, A. I. Levy, S. Tripathi and J. L. Zahorjan, Improving approximations of aggregated queuing network subsystems, in ''Computer Performance" (eds. K. M. Chandy and M. Reiser), North-Holland, (1977), 1-22.
[56]	C. E. Shannon and W. Weaver, A mathematical theory of communication, Bell Syst. Tech. J., 27 (1948), 379-423, 623-656.
[57]	J. Shore and R. Johnson, Axiomatic derivation of the principle of maximum entropy and the principle of minimum cross-entropy, IEEE Trans. Info. Theory, 26 (1980), 26-37.doi: 10.1109/TIT.1980.1056144.
[58]	J. E. Shore, Information theoretic approximations for M/G/1 and G/G/1 queuing systems, Acta info., 17 (1982), 43-61.
[59]	K. Smith and D. D. Kouvatsos, "Entropy Maximisation and QNM with Blocking after Service," Research report RS-08-01, University of Bradford, 2001.
[60]	K. Smith and D.D. Kouvatsos, Entropy maximisation and QNM with blocking before service, in ''Proc. of the 2nd Annual Postgraduate Symposium on Convergence of Telecommunications, Networking and Broadcasting PG Net 2001" (eds. M. Merabti and R. Pereira), Liverpool John Moores University Publishers, (2001), 78-83.
[61]	Y. Takahashi and H. Miyahara, An approximation method for open restricted queueing networks, Oper. Res., 28 (1980), 594-602.doi: 10.1287/opre.28.3.594.
[62]	C. Tsallis, Possible generalisation of boltzmann-gibbs statistics, Journal of Statistical Physics, 52 (1988), 479-487.doi: 10.1007/BF01016429.
[63]	M. Tribus, "Rational Descriptions, Decisions and Designs," Pergamon, New York, 1969.
[64]	B. R. Walstra, "Iterative Analysis of Networks of Queues," Ph.D thesis, Toronto University, Canada, 1984.
[65]	D. Yao and J. A Buzacott, Modelling a class of state dependent routing in flexible manufacturing systems, Annals of Oper. Res., 3 (1985), 153-167.doi: 10.1007/BF02024744.
[66]	"Tsallis Statistics, Statistical Mechanics for Non-extensive Systems and Long-Range Interactions,", Notebook, (2007).