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: Sandeep Bhadra , Yingdong Lu , Mark S. Squillante, Optimal capacity planning in stochastic loss networks with time-varying workloads, Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 12-16, 2007, San Diego, California, USA
• 3: Thomas Bonald, The Erlang model with non-poisson call arrivals, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 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: Predrag R. Jelenković , Petar Momčilović , Mark S. Squillante, Scalability of wireless networks, IEEE/ACM Transactions on Networking (TON), v.15 n.2, p.295-308, April 2007 [doi>10.1109/TNET.2007.892846]
• 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: Jean B. Lasserre, Global Optimization with Polynomials and the Problem of Moments, SIAM Journal on Optimization, v.11 n.3, p.796-817, 2000 [doi>10.1137/S1052623400366802]
• 15: J. Little. A proof of the queuing formula L = λW. Oper. Res., 9:383--387, 1961.
• 16: Graham Louth , Michael Mitzenmacher , Frank Kelly, Computational complexity of loss networks, Theoretical Computer Science, v.125 n.1, p.45-59, March 14, 1994 [doi>10.1016/0304-3975(94)90293-3]
• 17: Yingdong Lu , Ana Radovanović , Mark S. Squillante, Optimal capacity planning in stochastic loss networks, ACM SIGMETRICS Performance Evaluation Review, v.35 n.2, September 2007 [doi>10.1145/1330555.1330571]
• 18: Zhi-Quan Luo , Paul Tseng, On the linear convergence of descent methods for convex essentially smooth minimization, SIAM Journal on Control and Optimization, v.30 n.2, p.408-425, March 1992 [doi>10.1137/0330025]
• 19: Debasis Mitra , John A. Morrison , K. G. Ramakrishnan, ATM network design and optimization: a multirate loss network framework, IEEE/ACM Transactions on Networking (TON), v.4 n.4, p.531-543, Aug. 1996 [doi>10.1109/90.532863]
• 21: Debasis Mitra , P. J. Weinberger, Probabilistic Models of Database Locking: Solutions, Computational Algorithms, and Asymptotics, Journal of the ACM (JACM), v.31 n.4, p.855-878, Oct. 1984 [doi>10.1145/1634.2509]
• 22: Keith W. Ross , Peter J. Hancock, Multiservice Loss Models for Broadband Telecommunication Networks, Springer-Verlag New York, Inc., Secaucus, NJ, 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: Jing-Sheng Song , Susan H. Xu , Bin Liu, Order-Fulfillment Performance Measures in An Assemble-To-Order System with Stochastic Leadtimes, Operations Research, v.47 n.1, p.131-149, January 1999 [doi>10.1287/opre.47.1.131]
• 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