BC-GA: A Graph Partitioning Algorithm for Parallel Simulation of Internet Applications

Static task mapping of parallel simulation is studied as a graph partitioning problem (GPP). However, the existing algorithms are primarily designed for partitioning finite element meshes or random graphs which are essentially different from the Internet-like topologies used in the field of large scale network simulation. In this paper, we present a new genetic algorithm, BC-GA, for effectively partitioning Internet-like topologies based on boundary crossing, a quite different principle inspired by the analysis of characteristic of the Internet topology and its related solutions. All operations of this algorithm are novel, such as pizza-cutting and autogamy propagation. We test this algorithm on a large extent of graphs, including the snapshots of the real AS-level Internet, the topologies produced by the Internet model generator and many traditional benchmark graphs. The experiment shows that our algorithm can outperform traditional approaches on partitioning Internet-like topologies and it is also better than or comparable to those on traditional GPP. The experiment also shows that a genetic algorithm can converge quickly if the domain knowledge is fitly combined.