Perfect simulation of index based routing queueing networks

ABSTRACT

Markovian queueing networks models are widely used for performance evaluation of computer systems, production lines, communication networks and so on. Routing strategies allocate clients to queues after the end of service. In many situations such as deterministic, probabilistic, or state dependent like Join the shortest queue routing, the routing function could be written in terms of index scheduling functions introduced in [3, 6].

REFERENCES

• 1: Simonetta Balsamo , Vittoria De Nitto Personè , Paola Inverardi, A review on queueing network models with finite capacity queues for software architectures performance prediction, Performance Evaluation, v.51 n.2-4, p.269-288, February 2003 [doi>10.1016/S0166-5316(02)00099-8]
• 2: P. Brémaud. Markov Chains: Gibbs fields, Monte Carlo Simulation and Queues. Springer-Verlag, 1999.
• 3: J. Gittins. Bandit processes and dynamic allocation in dices. J. Roy. Statist. Soc. (B), 41:148--177, 1979.
• 4: Paul Glasserman , David D. Yao, Monotone structure in discrete-event systems, John Wiley & Sons, Inc., New York, NY, 1994
• 5: D. Mattson. On Perfect Simulation of Markovian Queueing Networks with Blocking. PhD thesis, Chalmers Göteborg University, 2002.
• 6: J. Palmer , I. Mitrani, Optimal and heuristic policies for dynamic server allocation, Journal of Parallel and Distributed Computing, v.65 n.10, p.1204-1211, October 2005 [doi>10.1016/j.jpdc.2005.04.010]
• 7: Harry G. Perros, Queueing networks with blocking, Oxford University Press, Inc., New York, NY, 1994
• 8: James Gary Propp , David Bruce Wilson, Exact sampling with coupled Markov chains and applications to statistical mechanics, Random Structures & Algorithms, v.9 n.1-2, p.223-252, Aug./Sept. 1996
• 9: Jean-Marc Vincent, Perfect simulation of monotone systems for rare event probability estimation, Proceedings of the 37th conference on Winter simulation, December 04-07, 2005, Orlando, Florida
• 10: Jean-Marc Vincent, Perfect Simulation of Queueing Networks with Blocking and Rejection, Proceedings of the 2005 Symposium on Applications and the Internet Workshops (SAINT 2005 Workshops), p.268-271, January 31-February 04, 2005
• 11: J.-M. Vincent and C. Marchand. On the exact simulation of functionals of stationary markov chains. Linear Algebra and its Applications, 386:285--310, 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Design, Experimentation, Measurement, Performance