多类顾客共享排队系统的信息理论
|
摘要
多类顾客的共享排队系统是排队论中一个既重要又困难的研究方向,它在计算机网络、生产制造系统与交通网络等领域中有着许多重要的实际应用.近年来,国外学者对多类顾客的共享排队系统已经开展了一些关键性的研究工作,给出了稳态联合队长的母函数,由此可以得到稳态联合队长的一阶矩和二阶矩.然而,由这个母函数反演来提供多类顾客共享排队系统的稳态联合队长的直接表达式却是一个多年来的困难问题.基于此,本文利用信息论中的最大熵原理,提供了一个高精度的近似表达式,其中这个近似表达式与它的精确表达式能够保证前三阶矩是相同的.另一方面,针对这个近似表达式,本文实现了它的有效数值计算,并通过数值算例分析了这个近似表达式中的重要因子是如何依赖于系统的原始参数.因此这个近似表达式对于推进多类顾客共享排队系统的实际应用具有重要的理论意义,同时本文的方法与结果不仅为研究多类顾客的共享排队系统提供了一条新的重要途径,而且为如何将信息理论应用于排队系统、排队网络以及更一般的随机模型研究提供了理论依据与技术支撑.
The discriminatory processor sharing queues with multiple classes of customers(abbreviated as DPS queues) are an important but difficult research direction in queueing theory, and it has many important practical applications in the fields of, such as, computer networks, manufacturing systems,transportation networks, and so forth. Recently, researchers have carried out some key work for the DPS queues. They gave the generating function of the steady-state joint queue lengths, which leads to the first two moments of the steady-state joint queue lengths. However, using the generating function to provide explicit expressions for the steady-state joint queue lengths has been a difficult and challenging problem for many years. Based on this, this paper applies the maximum entropy principle in the information theory to providing an approximate expression with high precision, and this approximate expression can have the same first three moments as those of its exact expression. On the other hand, this paper gives efficiently numerical computation by means of this approximate expression, and analyzes how the key variables of this approximate expression depend on the original parameters of this queueing system in terms of some numerical experiments. Therefore, this approximate expression has important theoretical significance to promote practical applications of the DPS queues. At the same time, not only do the methodology and results given in this paper provide a new line in the study of DPS queues, but they also provide the theoretical basis and technical support for how to apply the information theory to the study of queueing systems, queueing networks and more generally, stochastic models.
The discriminatory processor sharing queues with multiple classes of customers(abbreviated as DPS queues) are an important but difficult research direction in queueing theory, and it has many important practical applications in the fields of, such as, computer networks, manufacturing systems,transportation networks, and so forth. Recently, researchers have carried out some key work for the DPS queues. They gave the generating function of the steady-state joint queue lengths, which leads to the first two moments of the steady-state joint queue lengths. However, using the generating function to provide explicit expressions for the steady-state joint queue lengths has been a difficult and challenging problem for many years. Based on this, this paper applies the maximum entropy principle in the information theory to providing an approximate expression with high precision, and this approximate expression can have the same first three moments as those of its exact expression. On the other hand, this paper gives efficiently numerical computation by means of this approximate expression, and analyzes how the key variables of this approximate expression depend on the original parameters of this queueing system in terms of some numerical experiments. Therefore, this approximate expression has important theoretical significance to promote practical applications of the DPS queues. At the same time, not only do the methodology and results given in this paper provide a new line in the study of DPS queues, but they also provide the theoretical basis and technical support for how to apply the information theory to the study of queueing systems, queueing networks and more generally, stochastic models.
引文
[1] YASHKOV S F. Processor-sharing queues:some progress in analysis[J]. Queueing Syst, 1987, 2(1):1-17.
[2] YASHKOV S F. Mathematical problems in the theory of shared-processor systems[J]. J Soviet Math,1992, 58(2):101-147.
[3] YASHKOV S F, YASHKOVA A S. Processor sharing:a survey of the mathematical theory[J]. Autom Remote Control, 2007, 68(9):1662-1731.
[4] HARRISON J M, MANDAYAM C, SHAH D, et al. Resource sharing networks:overview and an open problem[J]. Stoch Syst, 2014, 4(2):524-555.
[5] BONALD T, PROUTIERE A. Insensitivity in processor-sharing networks[J]. Performance Evaluation, 2002, 49(1-4):193-209.
[6] KELLY F P, WILLIAMS R J. Fluid model for a network operating under a fair bandwidth-sharing policy[J]. Ann Appl Probab, 2004, 14(3):1055-1083.
[7] KANG W N, KELLY F P, LEE N H, et al. State space collapse and diffusion approximation for a network operating under a fair bandwidth sharing policy[J]. Ann Appl Probab, 2009, 19(5):1719-1780.
[8] SHAH D, TSITSIKLIS J N, ZHONG Y. Qualitative properties of a-fair policies in bandwidth-sharing networks[J]. Ann Appl Probab, 2014, 24(1):76-113.
[9] FAYOLLE G, MITRANI I, IASNOGORODSKI R. Sharing a processor among many job classes[J].J Assoc Comput Mach, 1980, 27(3):519-532.
[10] ALTMAN E, AVRACHENKOV K,AYESTA U. A survey on discriminatory processor sharing[J].Queueing Syst, 2006, 53(1-2):53-63.
[11] KLEINROCK L. Time-shared systems:a theoretical treatment[J]. J Assoc Comput Mach, 1967,14(2):242-261.
[12] AVRACHENKOV K, AYESTA U, BROWN P, et al. Discriminatory processor sharing revisited[C]//Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies, Vol. 2. 2005:784-795.
[13] REGE K M, SENGUPTA B. Queue-length distribution for the discriminatory processor-sharing queue[J]. Oper Res, 1996, 44(4):653-657.
[14] KIM J, KIM B. Sojourn time distribution in the M/M/1 queue with discriminatory processorsharing[J]. Performance Evaluation, 2004, 58(4):341-365.
[15] VAN KESSEL G, NUNEZ-QUEIJA R, BORST S. Asymptotic regimes and approximations for discriminatory processor sharing[J]. ACM SIGMETRICS Performance Evaluation Review, 2004, 32(2):44-46.
[16] LEINO J, VIRTAMO J. Determining the moments of queue-length distribution of discriminatory processor-sharing systems with phase-type service requirements[C]//2007 Next Generation Internet Networks:3rd EuroNGI Conference on Next Generation Internet Networks Design and Engineering for Heterogeneity. 2007:205-208.
[17] HAVIV M,VAN DER WAL J. Mean sojourn times for phase-type discriminatory processor sharing systems[J]. European J Oper Res, 2008, 189(2):375-386.
[18] MORRISON J A. Asymptotic analysis of a large closed queueing network with discriminatory processor sharing[J]. Queueing Syst, 1991, 9(1-2):191-213.
[19] VERLOOP I M, AYESTA U, NUNEZ-QUEIJA R. Heavy-traffic analysis of a multiple-phase network with discriminatory processor sharing[J]. Oper Res, 2011, 59(3):648-660.
[20] BORST S, VAN OOTEGHEM D, ZWART B. Tail asymptotics for discriminatory processor-sharing queues with heavy-tailed service requirements[J]. Performance Evaluation, 2005, 61(2-3):281-298.
[21] LI Q L. Nonlinear Markov processes in big networks[J]. Spec Matrices, 2016, 4(1):202-217.
[22] JAYNES E T. Information theory and statistical mechanics[J]. Phys Rev, 1957, 106(4):620-630.
[23] JAYNES E T. Information theory and statistical mechanics II[J]. Phys Rev, 1957, 108(2):171-190.
[24] SHORE J E. Information theoretic approximations for M/G/1 and G/G/1 queuing systems[J]. Acta Inform, 1982, 17(1):43-61.
[25] EL-AFFENDI M A, KOUVATSOS D D. A maximum entropy analysis of the M/G/1 and G/M/1queueing systems at equilibrium[J]. Acta Inform, 1983, 19(4):339-355.
[26] KOUVATSOS D D. Maximum entropy and the G/G/1/N queue[J]. Acta Inform, 1986, 23(5):545-565.
[27] KOUVATSOS D, TABET-AOUEL N. A maximum entropy priority approximation for a stable G/G/1queue[J]. Acta Inform, 1989, 27(3):247-286.
[28] TAD J L, HAMDI A. Maximum entropy solution to a quorum queueing system[J]. Math Comput Modelling, 2001, 34(1-2):19-27.
[29] KE J C, LIN C H. Maximum entropy approach for batch-arrival queue under N policy with an un-reliable server and single vacation[J]. J Comput Appl Math, 2008, 221(1):1-15.
[30] WANG K H, HUANG K B. A maximum entropy approach for the(p, N)-policy M/G/1 queue with a removable and unreliable server[J]. Appl Math Model, 2009, 33(4):2024-2034.
[31] FALIN G I, DIAZ M M, ARTALEJO J R. Information theoretic approximations for the M/G/1retrial queue[J]. Acta Inform, 1994, 31(6):559-571.
[32] LOPEZ-HERRERO M J. A maximum entropy approach for the busy period of the M/G/1 retrial queue[J]. Ann Oper Res, 2006, 141(1):271-281.
[33] WHITT W. Stochastic-Process Limits:An Introduction to Stochastic-Process Limits and Their Application to Queues[M]. New York:Springer-Verlag, 2002.
[2] YASHKOV S F. Mathematical problems in the theory of shared-processor systems[J]. J Soviet Math,1992, 58(2):101-147.
[3] YASHKOV S F, YASHKOVA A S. Processor sharing:a survey of the mathematical theory[J]. Autom Remote Control, 2007, 68(9):1662-1731.
[4] HARRISON J M, MANDAYAM C, SHAH D, et al. Resource sharing networks:overview and an open problem[J]. Stoch Syst, 2014, 4(2):524-555.
[5] BONALD T, PROUTIERE A. Insensitivity in processor-sharing networks[J]. Performance Evaluation, 2002, 49(1-4):193-209.
[6] KELLY F P, WILLIAMS R J. Fluid model for a network operating under a fair bandwidth-sharing policy[J]. Ann Appl Probab, 2004, 14(3):1055-1083.
[7] KANG W N, KELLY F P, LEE N H, et al. State space collapse and diffusion approximation for a network operating under a fair bandwidth sharing policy[J]. Ann Appl Probab, 2009, 19(5):1719-1780.
[8] SHAH D, TSITSIKLIS J N, ZHONG Y. Qualitative properties of a-fair policies in bandwidth-sharing networks[J]. Ann Appl Probab, 2014, 24(1):76-113.
[9] FAYOLLE G, MITRANI I, IASNOGORODSKI R. Sharing a processor among many job classes[J].J Assoc Comput Mach, 1980, 27(3):519-532.
[10] ALTMAN E, AVRACHENKOV K,AYESTA U. A survey on discriminatory processor sharing[J].Queueing Syst, 2006, 53(1-2):53-63.
[11] KLEINROCK L. Time-shared systems:a theoretical treatment[J]. J Assoc Comput Mach, 1967,14(2):242-261.
[12] AVRACHENKOV K, AYESTA U, BROWN P, et al. Discriminatory processor sharing revisited[C]//Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies, Vol. 2. 2005:784-795.
[13] REGE K M, SENGUPTA B. Queue-length distribution for the discriminatory processor-sharing queue[J]. Oper Res, 1996, 44(4):653-657.
[14] KIM J, KIM B. Sojourn time distribution in the M/M/1 queue with discriminatory processorsharing[J]. Performance Evaluation, 2004, 58(4):341-365.
[15] VAN KESSEL G, NUNEZ-QUEIJA R, BORST S. Asymptotic regimes and approximations for discriminatory processor sharing[J]. ACM SIGMETRICS Performance Evaluation Review, 2004, 32(2):44-46.
[16] LEINO J, VIRTAMO J. Determining the moments of queue-length distribution of discriminatory processor-sharing systems with phase-type service requirements[C]//2007 Next Generation Internet Networks:3rd EuroNGI Conference on Next Generation Internet Networks Design and Engineering for Heterogeneity. 2007:205-208.
[17] HAVIV M,VAN DER WAL J. Mean sojourn times for phase-type discriminatory processor sharing systems[J]. European J Oper Res, 2008, 189(2):375-386.
[18] MORRISON J A. Asymptotic analysis of a large closed queueing network with discriminatory processor sharing[J]. Queueing Syst, 1991, 9(1-2):191-213.
[19] VERLOOP I M, AYESTA U, NUNEZ-QUEIJA R. Heavy-traffic analysis of a multiple-phase network with discriminatory processor sharing[J]. Oper Res, 2011, 59(3):648-660.
[20] BORST S, VAN OOTEGHEM D, ZWART B. Tail asymptotics for discriminatory processor-sharing queues with heavy-tailed service requirements[J]. Performance Evaluation, 2005, 61(2-3):281-298.
[21] LI Q L. Nonlinear Markov processes in big networks[J]. Spec Matrices, 2016, 4(1):202-217.
[22] JAYNES E T. Information theory and statistical mechanics[J]. Phys Rev, 1957, 106(4):620-630.
[23] JAYNES E T. Information theory and statistical mechanics II[J]. Phys Rev, 1957, 108(2):171-190.
[24] SHORE J E. Information theoretic approximations for M/G/1 and G/G/1 queuing systems[J]. Acta Inform, 1982, 17(1):43-61.
[25] EL-AFFENDI M A, KOUVATSOS D D. A maximum entropy analysis of the M/G/1 and G/M/1queueing systems at equilibrium[J]. Acta Inform, 1983, 19(4):339-355.
[26] KOUVATSOS D D. Maximum entropy and the G/G/1/N queue[J]. Acta Inform, 1986, 23(5):545-565.
[27] KOUVATSOS D, TABET-AOUEL N. A maximum entropy priority approximation for a stable G/G/1queue[J]. Acta Inform, 1989, 27(3):247-286.
[28] TAD J L, HAMDI A. Maximum entropy solution to a quorum queueing system[J]. Math Comput Modelling, 2001, 34(1-2):19-27.
[29] KE J C, LIN C H. Maximum entropy approach for batch-arrival queue under N policy with an un-reliable server and single vacation[J]. J Comput Appl Math, 2008, 221(1):1-15.
[30] WANG K H, HUANG K B. A maximum entropy approach for the(p, N)-policy M/G/1 queue with a removable and unreliable server[J]. Appl Math Model, 2009, 33(4):2024-2034.
[31] FALIN G I, DIAZ M M, ARTALEJO J R. Information theoretic approximations for the M/G/1retrial queue[J]. Acta Inform, 1994, 31(6):559-571.
[32] LOPEZ-HERRERO M J. A maximum entropy approach for the busy period of the M/G/1 retrial queue[J]. Ann Oper Res, 2006, 141(1):271-281.
[33] WHITT W. Stochastic-Process Limits:An Introduction to Stochastic-Process Limits and Their Application to Queues[M]. New York:Springer-Verlag, 2002.