Large deviations problems for star networks: the min policy. (English) Zbl 1047.60021

Summary: We are interested in analyzing the effect of bandwidth sharing for telecommunication networks. More precisely, we want to calculate which routes are bottlenecks by means of large deviations techniques. The method is illustrated on a star network, where the bandwidth is shared between customers according to the so-called min policy. We prove a sample path large deviation principle for a rescaled process \(n^{-1}Q_{nt}\), where \(Q_t\) represents the joint number of connections at time \(t\). The main result is to compute the rate function explicitly. The major step consists in deriving large deviation bounds for an empirical generator constructed from the joint number of customers and arrivals on each route. The rest of the analysis relies on a suitable change of measure together with a localization procedure. An example shows how this can be used practically.


60F10 Large deviations
60K25 Queueing theory (aspects of probability theory)
60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.)
90B18 Communication networks in operations research
Full Text: DOI arXiv


[1] Atar, R. and Dupuis, P. (1999). Large deviations and queueing networks: Methods for rate function identification. Stochastic Process. Appl. 84 255–296. · Zbl 0996.60036
[2] Baskett, F., Chandy, K. M., Muntz, R. R. and Palacios, F. G. (1975). Open, closed, and mixed networks of queues with different classes of customers. J. Assoc. Comput. Mach. 22 248–260. · Zbl 0313.68055
[3] Delcoigne, F. and de La Fortelle, A. (2001). Large deviations problems for star networks: The min policy. Technical Report 4143, INRIA. · Zbl 1047.60021
[4] Delcoigne, F. and de La Fortelle, A. (2002). Large deviations rate function for polling systems. Queueing Syst. Theory Appl. 41 13–44. · Zbl 1053.60096
[5] Dembo, A. and Zeitouni, O. (1998). Large Deviations Techniques and Applications , 2nd ed. Springer, New York. · Zbl 0896.60013
[6] Deuschel, J.-D. and Stroock, D. W. (1989). Large Deviations . Academic Press, Boston. · Zbl 0705.60029
[7] Dupuis, P. and Ellis, R. S. (1992). Large deviations for Markov processes with discontinuous statistics. II. Random walks. Probab. Theory Related Fields 91 153–194. · Zbl 0746.60025
[8] Dupuis, P. and Ellis, R. S. (1995). The large deviation principle for a general class of queueing systems. I. Trans. Amer. Math. Soc. 347 2689–2751. · Zbl 0869.60022
[9] Dupuis, P., Ellis, R. S. and Weiss, A. (1991). Large deviations for Markov processes with discontinuous statistics. I. General upper bounds. Ann. Probab. 19 1280–1297. JSTOR: · Zbl 0735.60027
[10] Dupuis, P., Ishii, H. and Soner, H. M. (1990). A viscosity solution approach to the asymptotic analysis of queueing systems. Ann. Probab. 18 226–255. JSTOR: · Zbl 0715.60035
[11] Fayolle, G., de La Fortelle, A., Lasgouttes, J. M., Massoulie, L. and Roberts, J. (2001). Best-effort networks: Modeling and performance analysis via large networks asymptotics. In Proc. of IEEE INFOCOM’01 .
[12] Fayolle, G. and Lasgouttes, J.-M. (2001). Partage de bande passante dans un réseau: Approches probabilistes. Technical Report 4202, INRIA.
[13] Fayolle, G., Mitrani, I. and Iasnogorodski, R. (1980). Sharing a processor among many job classes. J. Assoc. Comput. Mach. 27 519–532. · Zbl 0475.68012
[14] Freidlin, M. I. and Wentzell, A. D. (1984). Random Perturbations of Dynamical Systems . Springer, New York. · Zbl 0522.60055
[15] Ignatiouk-Robert, I. (2000). Large deviations of Jackson networks. Ann. Appl. Probab. 10 962–1001. · Zbl 1073.60510
[16] Ignatyuk, I. A., Malyshev, V. A. and Shcherbakov, V. V. (1994). The influence of boundaries in problems on large deviations. Uspekhi Mat. Nauk. 49 43–102. · Zbl 0824.60022
[17] Ioffe, A. D. and Tihomirov, V. M. (1979). Theory of Extremal Problems . North-Holland, Amsterdam. · Zbl 0407.90051
[18] de La Fortelle, A. (2001). Large deviation principle for Markov chains in continuous time. Problemy Peredachi Informatsii 36 120–140. · Zbl 0996.60086
[19] Shwartz, A. and Weiss, A. (1995). Large Deviations for Performance Analysis . Chapman and Hall, London. · Zbl 0871.60021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.