Efficient parallel simulations and their application to communication networks

Simulation is one of the most important tools for system performance evaluation in communication networks as well as many other areas. However, simulation is computationally intensive. A traditional sequential simulation of a complex model or a rare-event system may require days or even weeks of computer execution time. Therefore, simulation often becomes a bottleneck of a performance study. With the growing availability of multiprocessor computing systems (e.g., tightly-coupled parallel computers or distributed networks of workstations), parallel simulation, which parallelizes a simulation program for execution on multiple processors, becomes an attractive means to reduce simulation execution time.

With few exceptions, existing parallel simulation algorithms can be broadly classified into four methods: multiple replication, time-parallel, parallel regenerative, and space-parallel. Each method is associated with some advantages and limitations. We study these methods and propose a number of parallel simulation algorithms for a class of communication network systems modeled by queueing systems.

In multiple replication simulation, each processor simulates a replication of the target simulation model independently. Due to the lack of a prior: knowledge about the steady state conditions, an arbitrarily selected initial state is often used for each simulation run. This can result in significant bias in the simulation outcome. To reduce this initial transient bias, we propose a polling initialization technique, in which a pilot simulation is used to find 'good' initial states that are representative of the steady-state conditions.

Time-parallel simulation obtains parallelism by partitioning the time domain of the simulation model into a number of batches. Each batch is computed by a processor independently. Time-parallel simulation has not been fully explored by the research community partly because finding the exact initial states for the batches is often challenging and problem dependent. We develop two approximation time-parallel simulation algorithms for acyclic networks of loss G/G/1/K and G/D/1/K queues. These algorithms exploit unbounded parallelism and can achieve near-linear speedup when the number of arrivals is large. Two other time-parallel approaches are also proposed for Markov chains. For more general simulation models, an approximation approach that uses a substate matching technique is presented.

Parallel regenerative simulation exploits parallels in by partitioning the simulation trajectory into a number of regeneration cycles. The amount of parallelism relies on the regeneration frequency of the model. In practice a regeneration state that has a short expected regeneration cycle length often does not exist in the target simulation model. As a result, a sufficient number of observations can not be obtained in a finite simulation interval. To overcome this constraint, we propose a partial regeneration algorithm that uses a substate matching technique to increase the number of observations.

When the memory requirement of the target simulation models exceeds the storage capacity of a single processor, space-parallel simulation is an appropriate method. In space-parallel simulation, the target simulation model is decomposed into a number of components such that each component contains a disjoint subset of the model state variables. Each component is mapped into a logical process which is responsible for computing the trajectory corresponding to the component over the simulation time interval. An important class of space-parallel simulation is the conservative simulation, in which each logical process can proceed processing an event only if the process ensures that no event. will arrive later with a smaller timestamp.

A number of previous experimental studies have suggested that lookahead, a capability that allows a simulation to look into the simulation time future, plays an important role in the performance of the conservative simulation. Although the performance of conservative simulation has been the interest in many previous studies, there has been a lack of formal arguments to quantify the impact of lookahead to conservative simulation performance. To address this question, we develop stochastic models to study the relationship between the amount of lookahead and the simulation performance with respect to different model topologies. We show that for closed simulation models, the simulation execution time is proportional to the amount of lookahead. For open models, on the other hand, lookahead is effectively useless when the simulation length is long.