A Topology Partition Algorithm based on Link Coarsening in Parallel Network Simulation

摘要：

Todays networks are facing more and more serious large-scale network attack such as worm and botnet. While such attacks cant and shouldnt be reproduced in the real network, network simulation is become more and more popular during the research. As the prerequisite of network simulation, topology partition influences the performance of simulation significantly. We suggest a new topology partition algorithm in parallel network simulation. This algorithm is a kind of agglomerative hierarchical clustering methods based on link coarsening. The experiment shows that our algorithm can finish partition on current computers in acceptable time for even around millions of vertices. Furthermore, the links between different sub-domains are fewer and the connectivity in each sub-domain is also guaranteed. Compared with the results of KMETIS, the new algorithm can reduce the edgecut more than 90% in general.

关键词： network parallel simulation topology partition link coarsening

作者: Xianqing Yang Hui He Hongli Zhang Kexin Zheng Xing Wang

作者单位: Department of Computer Science and Engineering Harbin Institute of Technology Harbin, China Network Information Center, Harbin Institute of Technology Harbin, China

会议类型: 国际会议

会议名称: Second International Symposium on Information Science and Engineering(第二届信息科学与工程国际会议)

会议地点: 上海

会议语种:英文

页码: 514-518

在线出版日期: 2009-12-26（万方平台首次上网日期，不代表论文的发表时间）