1st International ICST Conference on Simulation Tools and Techniques for Communications, Networks and Systems

Research Article

Importance Sampling in Rate-Sharing Networks

Download541 downloads
  • @INPROCEEDINGS{10.4108/ICST.SIMUTOOLS2008.2948,
        author={P. Lieshout and M. Mandjes},
        title={Importance Sampling in Rate-Sharing Networks},
        proceedings={1st International ICST Conference on Simulation Tools and Techniques for Communications, Networks and Systems},
        publisher={ICST},
        proceedings_a={SIMUTOOLS},
        year={2010},
        month={5},
        keywords={Alpha-fair sharing Importance sampling Rare events},
        doi={10.4108/ICST.SIMUTOOLS2008.2948}
    }
    
  • P. Lieshout
    M. Mandjes
    Year: 2010
    Importance Sampling in Rate-Sharing Networks
    SIMUTOOLS
    ICST
    DOI: 10.4108/ICST.SIMUTOOLS2008.2948
P. Lieshout1,*, M. Mandjes2,3,4,*
  • 1: CWI, P.O. Box 94079 1090 GB Amsterdam, the Netherlands
  • 2: Kortweg-de Vries Institute, University of Amsterdam, Plantage Muidergracht 24 1018 TV Amsterdam, the Netherlands
  • 3: CWI, Amsterdam, the Netherlands.
  • 4: EURANDOM, Eindhoven, the Netherlands.
*Contact email: lieshout@cwi.nl, mmandjes@science.uva.nl

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 n0 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.