Link Partitioning in Parallel Simulation of Scale-Free Networks

It has been observed that many networks arising in practice have skewed node degree distributions. Scale-free networks are one well-known class of such networks. Achieving efficient parallel simulation of scale-free networks is challenging because large-degree nodes can create bottlenecks that limit performance. To help address this problem we describe an approach called link partitioning where each network link is mapped to a logical process (LP) in contrast to the conventional approach of mapping each network node to an LP. Link partitioning is discussed in the context of packet-level simulations of telecommunication networks. The parallelism of link partitioning relative to node partitioning is examined in terms of an idealized execution using the well-known YAWNS synchronization algorithm. Further, a critical path analysis suggests that there is much more parallelism available in these simulations than can be exploited using the YAWNS algorithm.