The authors propose synchronous relaxation (SR) as an efficient general-purpose tool to obtain a new parallel algorithm for large circuit-switched communication network simulation (LCSCNS). They compare the efficiency of the simulation results of LCSCNS experiments with that of an analytic approximate analysis from a large mathematical model.

Applied to LCSCNS, the SR method processes large numbers of calls in parallel on a single-instruction multiple-data (SIMD) or multiple-instruction multiple-data (MIMD) computer on which all the processing elements execute the same instruction. The simulation method proceeds in a time-stepped fashion, with a relaxation iterative method applied to process the events at each time step. The system is partitioned into subsystems, and each processing element hosts the simulation of a subsystem. The algorithm belongs to a large class of SR optimistic approaches.

The network considered for simulation has N nodes representing the large circuit-switched communication network switches and L = N ( N - 1 ) &slash; 2 links between nodes, with every link consisting of a fixed number of trunks. The proportionate routing policy is simulated.

Gaining insight into dataflows in SR, the authors consider an oblivious version of proportionate routing for a detailed simple event-coupling model. The model is both randomized and worst-case, with stochastic assumptions about the placement of events and about the behavior of the relaxation algorithm on these events. The focus is on the speed of the algorithm. Insight is given into a mini-rollback or mini-backtrack SR algorithm in which a processing element processes a bounded number of events at each iteration.

It seems that the SR method could be implemented efficiently on SIMD computers for large circuit-switched communication networks under a policy of queueing network simulations, with infinite buffer queues.