Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-16T19:17:40.978Z Has data issue: false hasContentIssue false
  • English
  • Français

Insensitivity of the mean field limit of loss systems under SQ(d) routeing

Part of: Limit theorems Special processes Markov processes Parametric inference

Published online by Cambridge University Press:  15 November 2019

Thirupathaiah Vasantam ,
Arpan Mukhopadhyay  and
Ravi R. Mazumdar
Thirupathaiah Vasantam*
Affiliation:
University of Waterloo
Arpan Mukhopadhyay*
Affiliation:
University of Warwick
Ravi R. Mazumdar*
Affiliation:
University of Waterloo
*
*Postal address: Department of Electrical and Computer Engineering, University of Waterloo, 200 University Avenue West, Waterloo, ON N2L 3G1, Canada.
**Postal address: Department of Computer Science, University of Warwick, Coventry, CV4 7AL, UK.
*Postal address: Department of Electrical and Computer Engineering, University of Waterloo, 200 University Avenue West, Waterloo, ON N2L 3G1, Canada.
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, we study a large multi-server loss model under the SQ(d) routeing scheme when the service time distributions are general with finite mean. Previous works have addressed the exponential service time case when the number of servers goes to infinity, giving rise to a mean field model. The fixed point of the limiting mean field equations (MFEs) was seen to be insensitive to the service time distribution in simulations, but no proof was available. While insensitivity is well known for loss systems, the models, even with state-dependent inputs, belong to the class of linear Markov models. In the context of SQ(d) routeing, the resulting model belongs to the class of nonlinear Markov processes (processes whose generator itself depends on the distribution) for which traditional arguments do not directly apply. Showing insensitivity to the general service time distributions has thus remained an open problem. Obtaining the MFEs in this case poses a challenge due to the resulting Markov description of the system being in positive orthant as opposed to a finite chain in the exponential case. In this paper, we first obtain the MFEs and then show that the MFEs have a unique fixed point that coincides with the fixed point in the exponential case, thus establishing insensitivity. The approach is via a measure-valued Markov process representation and the martingale problem to establish the mean field limit.

Keywords

Erlang loss modelSQ(d)mean fieldfixed pointinsensitivity

MSC classification

Primary: 60K35: Interacting random processes; statistical mechanics type models; percolation theory
Secondary: 60F10: Large deviations 60J10: Markov chains (discrete-time Markov processes on discrete state spaces) 62F15: Bayesian inference
Type
Original Article
Information
Advances in Applied Probability , Volume 51 , Issue 4 , December 2019 , pp. 1027 - 1066
Copyright
© Applied Probability Trust 2019 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aghajani, R. and Ramanan, K. (2019). The hydrodynamic limit of a randomized load balancing network. Ann. Appl. Prob. 27(4), 2114–2174.CrossRefGoogle Scholar
Asmussen, S. (2003). Applied Probability and Queues (Stochastic Modelling and Applied Probability 51). Springer, New York.Google Scholar
Billingsley, P. (1999). Convergence of Probability Measures, 2nd edn (Wiley Series in Probability and Statistics: Probability and Statistics). John Wiley, New York.CrossRefGoogle Scholar
Bonald, T. and Proutière, A. (2002). Insensitivity in processor sharing networks. Performance Evaluation 49, 193–209.CrossRefGoogle Scholar
Bonald, T., Jonckheere, M. and Proutiére, A. (2004). Insensitive load balancing. In Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS ’04/Performance ’04), pp. 367–377. ACM, New York.CrossRefGoogle Scholar
Bramson, M., Lu, Y. and Prabhakar, B. (2010). Randomized load balancing with general service time distributions. In Proceedings of the 2010 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS ’10), pp. 275–286. ACM, New York.CrossRefGoogle Scholar
Brown, L., Gans, N., Mandelbaum, A., Sakov, A., Shen, H., Zeltyn, S. and Zhao, L. (2005). Statistical analysis of a telephone call center. J. Amer. Statist. Assoc. 100, 36–50.CrossRefGoogle Scholar
Brumelle, S. L. (1978). A generalization of Erlang’s loss system to state dependent arrival and service rates. Math. Operat. Res. 3, 10–16.CrossRefGoogle Scholar
Dawson, D. A. (1993). Measure-Valued Markov Processes (École d’Été de Probabilités de Saint-Flour XXI, 1991 1541). Springer, Berlin.Google Scholar
Decreusefond, L. and Moyal, P. (2008). A functional central limit theorem for the M/GI/∞ queue. Ann. Appl. Prob. 18, 2156–2178.CrossRefGoogle Scholar
Decreusefond, L. and Moyal, P. (2012). Stochastic Modeling and Analysis of Telecom Networks. ISTE, London.CrossRefGoogle Scholar
Ethier, S. N. and Kurtz, T. G. (1985). Markov Processes: Characterization and Convergence. John Wiley.Google Scholar
Gärtner, J. (1988). On the McKean–Vlasov limit for interacting diffusions. Math. Nachr. 137, 197–248.CrossRefGoogle Scholar
Graham, C. (2000). Chaoticity on path space for a queueing network with selection of the shortest queue among several. J. Appl. Prob. 37, 198–211.CrossRefGoogle Scholar
Graham, C. (2005). Functional central limit theorems for a large network in which customers join the shortest of several queues. Probab. Theory Relat. Fields 131, 97–120.CrossRefGoogle Scholar
Graham, C. and Méléard, S. (1993). Propagation of chaos for a fully connected loss network with alternate routing. Stoch. Process. Appl. 44, 159–180.CrossRefGoogle Scholar
Graham, C. and Méléard, S. (1997). Stochastic particle approximations for generalized Boltzmann models and convergence estimates. Ann. Prob. 28, 115–132.Google Scholar
Gromoll, H. C., Puha, A. L. and Williams, R. J. (2002). The fluid limit of a heavily loaded processor sharing queue. Ann. Appl. Prob. 12, 797–859.Google Scholar
Gromoll, H. C., Robert, P. and Zwart, B. (2008). Fluid limits for processor-sharing queues with impatience. Math. Operat. Res. 33, 375–402.CrossRefGoogle Scholar
Jakubowski, A. (1986). On the Skorokhod topology. Ann. Inst. H. Poincaré Prob. Statist. 22, 263–285.Google Scholar
Kallenberg, O. (1983). Random Measures. Akademie.Google Scholar
Karpelevich, F. I. and Rybko, A. N. (2000). Thermodynamic limit for the mean field model of simple symmetrical closed queueing network. Markov Process. Relat. Fields 6, 89–105.Google Scholar
Kaspi, H. and Ramanan, K. (2011). Law of large numbers limits for many-server queues. Ann. Appl. Prob. 21, 33–114.CrossRefGoogle Scholar
Kolesar, P. (1984). Stalking the endangered cat: a queueing analysis of congestion at automatic teller machines. Interfaces 14, 16–26.CrossRefGoogle Scholar
Kolokoltsov, V. N. (2010). Nonlinear Markov Processes and Kinetic Equations (Camb. Tracts Math. 182). Cambridge University Press.Google Scholar
Kotelenez, P. M. and Kurtz, T. G. (2008). Macroscopic limits for stochastic partial differential equations of McKean–Vlasov type. Probab. Theory Relat. Fields 146, 189.CrossRefGoogle Scholar
Li, Q.-L. and Lin, C. (2006). The M/G/1 processor-sharing queue with disasters. Comput. Math. Appl. 51, 987–998.CrossRefGoogle Scholar
Mitzenmacher, M. (1996). The power of two choices in randomized load balancing. PhD thesis, Berkeley.Google Scholar
Mukherjee, D., Borst, S., van Leeuwaarden, J. and Whiting, P. (2016). Universality of power-of-d load balancing schemes. SIGMETRICS Perform. Eval. Rev. 44, 36–38.CrossRefGoogle Scholar
Mukhopadhyay, A. and Mazumdar, R. R. (2014). Rate-based randomized routing in large heterogeneous processor sharing systems. In 26th International Teletraffic Congress (ITC 26). IEEE.CrossRefGoogle Scholar
Mukhopadhyay, A. and Mazumdar, R. R. (2016). Analysis of randomized join-the-shortest-queue (JSQ) schemes in large heterogeneous processor sharing systems. IEEE Trans. Control Netw. Syst. 3 (2), 116–126.CrossRefGoogle Scholar
Mukhopadhyayay, A., Karthik, A., Mazumdar, R. R. and Guillemin, F. M. (2015). Mean field and propagation of chaos in multi-class heterogeneous loss models. Performance Evaluation 91, 117–131.CrossRefGoogle Scholar
Mukhopadhyay, A., Mazumdar, R. R. and Guillemin, F. (2015). The power of randomized routing in heterogeneous loss systems. In 27th International Teletraffic Congress (ITC 27). pp. 125–133. IEEE.CrossRefGoogle Scholar
Oelschlager, K. (1984). A martingale approach to the law of large numbers for weakly interacting stochastic processes. Ann. Prob. 12, 458–479.CrossRefGoogle Scholar
Robert, P. (2003). Stochastic Networks and Queues (Applications of Mathematics series). Springer.CrossRefGoogle Scholar
Ross, S. M. (2009). Introduction to Probability Models, 10th edn. Academic Press.Google Scholar
Rudin, W. (1987). Real and Complex Analysis, 3rd edn. McGraw-Hill, New York.Google Scholar
Sevastyanov, B. A. (1957). An ergodic theorem for Markov processes and its application to telephone systems with refusals. Theory Prob. Appl. 2, 104–112.CrossRefGoogle Scholar
Turner, S. R. E. (1996). Resource pooling in stochastic networks. PhD dissertation, University of Cambridge.Google Scholar
Turner, S. R. E. (1998). The effect of increasing routing choice on resource pooling. Probab. Eng. Inform. Sci. 12, 109–124.CrossRefGoogle Scholar
Vasantam, T., Mukhopadhyay, A. and Mazumdar, R. R. (2017). Mean-field analysis of loss models with mixed-Erlang distributions under power-of-d routing. In 29th International Teletraffic Congress (ITC 29). vol. 1, pp. 250–258. IEEE.CrossRefGoogle Scholar
Vvedenskaya, N. D., Dobrushin, R. L. and Karpelevich, F. I. (1996). Queueing system with selection of the shortest of two queues: an asymptotic approach. Probl. Inf. Transm. 32, 20–34.Google Scholar
Xie, Q., Dong, X., Lu, Y. and Srikant, R. (2015). Power of d choices for large-scale bin packing: a loss model. In Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS ’15). pp. 321–334. ACM, New York.CrossRefGoogle Scholar
Zhang, J. (2013). Fluid models of many-server queues with abandonment. Queueing Systems 73, 147–193.CrossRefGoogle Scholar