Time-parallel algorithms for simulation of multiple access protocols

We present time-parallel algorithms for parallel simulation of multiple access protocols for medium access - In particular, slotted Aloha and slotted p-persistent CSMA. Two mechanisms are presented-regeneration point-based and fix up-based. Aloha is simulated using both mechanisms and CSMA is simulated using only the first mechanism. An analytical technique is developed to predict speedup for the regeneration point-based scheme for slotted Aloha. Speedup values obtained from the analytical technique are found to be in good agreement with those obtained from simulations. In general, it is observed that any mechanism that reduces the number of backlogged packets has good parallel performance regardless of the protocol simulated or the mechanism used to parallelize the simulation.