Research And Implementation On Topology Partitioning Algorithm In Parallel Network Simulation

With the rapid development of Internet, the network scale become larger and more complex, so researching the large-scale network has become inevitable. Due to lower cost and using easily, so network simulation technology has been used widely. But because the ability of the single machine simulation could not cope with large-scale network simulation, so it makes parallel network simulation become one of the effective tools in network research.Parallel network simulation is a process of multi-machine simulation, so it needs to partition the simulation task. We generally use topology partitioning to partition the simulation task. The essence of topology partitioning is task distribution, but before the simulation the task of the nodes and links could not been known, so topology partitioning firstly estimate the task of the nodes and links, called task estimate stage; then partition the task for the partitioning goal, called task partitioning stage. Reasonable task distribution can improve simulation performance, so the study of topology partitioning is very important.In this paper, WEMS (Weight Estimate Method algorithm on Scanning Mode) in task estimate stage and POMM (Partitioning Optimization algorithm Based on Multi-node Moving) in task partitioning phase are presented and implemented. WEMS bases on the principle that the more task, the bigger weight for every node and link. The specific measure is that firstly the security incident's scanning mode are analyzed, according to the different scanning mode to estimate the attack source and destination, then every attack source and destination are traversed to found the shortest path, at the same time increases nodes and links weights which passed the shortest path including the attack source and destination. When traversal finished, we get the whole topology weight. The work of task partitioning stage use KMETIS to achieve, KMETIS is a method in the graph partitioning tool of METIS.POMM is an improvement in KMETIS optimization. The specific measure is that firstly it defines the premise including load balance and node balance, in the premise condition moves a series of nodes, according to the partition goal, including ecw(the sum of edge cut weight ), subnet number, load balance and node balance, finds the optimal move node place, and at the same time moves the nodes after the optimal move node place to the original position.