Revisiting stochastic loss networks: structures and algorithms

ABSTRACT

This paper considers structural and algorithmic problems in stochastic loss networks. The very popular Erlang approximation can be shown to provide relatively poor performance estimates, especially for loss networks in the critically loaded regime. This paper proposes a novel algorithm for estimating the stationary loss probabilities in stochastic loss networks based on structural properties of the exact stationary distribution, which is shown to always converge, exponentially fast, to the asymptotically exact results. Using a variational characterization of the stationary distribution, an alternative proof is provided for an important result due to Kelly, which is simpler and may be of interest in its own right. This paper also determines structural properties of the inverse Erlang function characterizing the region of capacities that ensures offered traffic is served within a set of loss probabilities. Numerical experiments investigate various issues of both theoretical and practical interest.

REFERENCES

• 1: S. Berezner, A. Krzesinski, P. Taylor. On the inverse of Erlang's formula. J. Appl. Prob., 35:246-252, 1998.
• 2: S. Bhadra, Y. Lu, M. Squillante. Optimal capacity planning in stochastic loss networks with time-varying workloads. In Proc. ACM SIGMETRICS, 227--238, 2007.
• 3: T. Bonald. The Erlang model with non-Poisson call arrivals. In Proc. SIGMETRICS-Performance, 276--286, 2006.
• 4: D. Burman, J. Lehoczky, Y. Lim. Insensitivity of blocking probabilities in a circuit-switching network. J. Appl. Prob., 21:850--859, 1984.
• 5: A. Erlang. Solution of some problems in the theory of probabilities of significance in automatic telephone exchanges. In E. Brockmeyer, H. Halstrom, A. Jensen, eds., The Life and Works of A. K. Erlang, Denmark, 1948.
• 6: P. Hunt, F. Kelly. On critically loaded loss networks. Adv. Appl. Prob., 21:831--841, 1989.
• 7: P. Jelenkovic, P. Momcilovic, M. Squillante. Scalability of wireless networks. IEEE/ACM Trans. Networking, 15:295--308, 2007.
• 8: K. Jung, Y. Lu, D. Shah, M. Sharma, M. Squillante. Revisiting stochastic loss networks: Structures and algorithms. Research Report, IBM Research, Nov. 2007.
• 9: F. Kelly. Reversibility and Stochastic Networks. John Wiley & Sons, New York, 1979.
• 10: F. Kelly. Stochastic models of computer communication systems. J. Royal Stat. Soc., B, 47:379--395, 1985.
• 11: F. Kelly. Blocking probabilities in large circuit-switched networks. Adv. Appl. Prob., 18:473--505, 1986.
• 12: F. Kelly. Routing in circuit-switched networks: Optimization, shadow prices and decentralization. Adv. Appl. Prob., 20:112--144, 1988.
• 13: F. Kelly. Loss networks. Ann. Appl. Prob., 1:319--378, 1991.
• 14: J. Lasserre. Global optimization with polynomials and the problems of moments. SIAM J. Opt., 11:796--817, 2001.
• 15: J. Little. A proof of the queuing formula L = λW. Oper. Res., 9:383--387, 1961.
• 16: G. Louth, M. Mitzenmacher, F. Kelly. Computational complexity of loss networks. Theor. Comp. Sci., 125:45--59, 1994.
• 17: Y. Lu, A. Radovanović, M. Squillante. Optimal capacity planning in stochastic loss networks. Perf. Eval. Rev., 35, 2007.
• 18: Z. Luo, P. Tseng. On the linear convergence of descent methods for convex essentially smooth minimization. SIAM J. Cont. Opt., 30:408--425, 1992.
• 19: D. Mitra, J. Morrison, K. Ramakrishnan. ATM network design and optimization: A multirate loss network framework. IEEE/ACMTrans. Networking, 4:531--543, 1996.
• 21: D. Mitra, P.Weinberger. Probabilistic models of database locking: Solutions, computational algorithms and asymptotics. J. ACM, 31:855--878, 1984.
• 22: K. Ross. Multiservice Loss Models for Broadband Telecommunication Networks. Springer-Verlag, 1995.
• 23: A. Saleh, J. Simmons. Evolution toward next-generation core optical network. J. Lightwave Tech., 24:3303--3321, 2006.
• 24: B. Sevastyanov. An ergodic theorem for Markov processes and its application to telephone systems with refusals. Theor. Prob. Appl., 2:104--112, 1957.
• 25: L. Valiant. The complexity of computing the permanent. Theor. Comp. Sci., 8:189--201, 1979.
• 26: W. Whitt. Blocking when service is required from several facilities simultaneously. AT&T Bell Lab. Tech. J., 64:1807--1856, 1985.
• 27: S. Xu, J. Song, B. Liu. Order fulfillment performance measures in an assemble-to-order system with stochastic leadtime. Oper. Res., 47:131--149, 1999.
• 28: I. Ziedins, F. Kelly. Limit theorems for loss networks with diverse routing. Adv. Appl. Prob., 21:804--830, 1989.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations; Computations on discrete structures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Nonlinear programming
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes; Queueing theory

General Terms:
Algorithms, Performance, Theory

Keywords:
erlang loss formula and fixed-point approximation, loss networks, multidimensional stochastic processes, stochastic approximations