Importance sampling in rate-sharing networks

ABSTRACT

We consider a network supporting elastic traffic, where the service capacity is shared among the various classes according to an alpha-fair sharing policy. Assuming Poisson arrivals and exponentially distributed service requirements for each class, the dynamics of the user population may be described by a Markov process. We focus on the probability that, given that the network is in some state n₀ at time 0, the network is in some set of states A at time T. In particular, we assume that the underlying event is rare, i.e., the probability of interest is small. As in general no explicit expressions are known for this probability, an attractive approach may be to resort to Monte-Carlo (MC) simulation. However, due to the rarity of the event under consideration, MC simulation is infeasible. A natural approach to speed up the simulation is to use Importance Sampling (IS). We present an IS algorithm to accelerate the simulation that is based on large deviations results. With extensive simulation experiments we assess the performance of the algorithm; under rather general conditions a considerable speed-up is achieved.

REFERENCES

• 1: S. Asmussen. Applied probability and queues. Springer-Verlag, New York, USA, 2003.
• 2: U. Ayesta and M. Mandjes. Bandwidth-sharing networks under a diffusion scaling. Accepted for publication in Annals of Operations Research, 2008.
• 3: Forest Baskett , K. Mani Chandy , Richard R. Muntz , Fernando G. Palacios, Open, Closed, and Mixed Networks of Queues with Different Classes of Customers, Journal of the ACM (JACM), v.22 n.2, p.248-260, April 1975 [doi>10.1145/321879.321887]
• 4: Jose Blanchet , Jingchen Liu , Peter Glynn, State-dependent Importance Sampling and large Deviations, Proceedings of the 1st international conference on Performance evaluation methodolgies and tools, October 11-13, 2006, Pisa, Italy [doi>10.1145/1190095.1190120]
• 5: Thomas Bonald , Laurent Massoulié, Impact of fairness on Internet performance, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.82-91, June 2001, Cambridge, Massachusetts, United States
• 6: J. Bucklew. Large deviation techniques in decision, simulation and estimation. Wiley, New York, USA, 1990.
• 7: P. Dupuis and H. Wang. Dynamic importance sampling for uniformly recurrent Markov chains. Annals of Applied Probability, 15:1--38, 2005.
• 8: G. Fayolle , I. Mitrani , R. Iasnogorodski, Sharing a Processor Among Many Job Classes, Journal of the ACM (JACM), v.27 n.3, p.519-532, July 1980 [doi>10.1145/322203.322212]
• 9: Ambuj Goyal , Perwez Shahabuddin , Philip Heidelberger , Victor F. Nicola , Peter W. Glynn, A Unified Framework for Simulating Markovian Models of Highly Dependable Systems, IEEE Transactions on Computers, v.41 n.1, p.36-51, January 1992 [doi>10.1109/12.123381]
• 10: Philip Heidelberger, Fast simulation of rare events in queueing and reliability models, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.5 n.1, p.43-85, Jan. 1995 [doi>10.1145/203091.203094]
• 11: L. Leskelä. Stabilization of an overloaded queueing network using measurement-based admission control. Journal of Applied Probability, 43:231--244, 2006.
• 12: M. Mandjes. Rare event analysis of the state frequencies of a large number of Markov chains. Stochastic Models, 15:577--592, 1999.
• 13: L. Massoulié and J. Roberts. Bandwidth sharing and admission control for elastic traffic. Telecommunication Systems, 15:185--201, 2000.
• 14: Jeonghoon Mo , Jean Walrand, Fair end-to-end window-based congestion control, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.556-567, Oct. 2000 [doi>10.1109/90.879343]
• 15: Jitendra Padhye , Victor Firoiu , Donald F. Towsley , James F. Kurose, Modeling TCP Reno performance: a simple model and its empirical validation, IEEE/ACM Transactions on Networking (TON), v.8 n.2, p.133-145, April 2000 [doi>10.1109/90.842137]
• 16: A. Shwartz and A. Weiss. Large deviations for performance analysis. Chapman & Hall, Londen, UK, 1995.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance

General Terms:
Design, Performance

Keywords:
alpha-fair sharing, importance sampling, rare events