Monotone Queuing Networks and Time Parallel Simulation

摘要

We show how we can make more efficient the time parallel simulation of some queueing networks. We had previously introduced some improvements of two classical time parallel simulation approaches: the precomputation of states at specific time instants and the fix-up computations. We have proved that we can obtain more parallelism using monotonicity on input sequences or on the initial states of the simulation parts and obtain quickly a bound of the sample-path. Here we apply the fixed up computations approach to the time parallel simulation of queueing networks with general service times and complex routing disciplines. This approach is based on the theory of monotone models of simulation. We establish that our models are monotone and we show how we obtain proved upper or lower bounds of the sample-path of the simulation and bounds of some estimates as well.