基于回退的并行网络模拟拓扑划分算法  

Task Partitioning Algorithm based on Rollback for Parallel Network Simulation

作　　者：张慈[1] 张兆心[1] 迟乐军[1] 

机构地区：[1]哈尔滨工业大学(威海)网络与信息安全技术研究中心,威海264209

出　　处：《微计算机信息》2011年第4期150-151,173,共3页Control & Automation

基　　金：基金申请人:张兆心;项目名称:高性能大规模网络行为模拟系统;基金颁发部门:中华人民共和国科学技术部(2007AA010503)

摘　　要：并行网络模拟的一个研究点是如何合理的对模拟任务进行划分,减少模拟所需要的时间,提高模拟的性能。当前并行网络模拟任务的划分一般采用基于图划分工具METIS来划分。鉴于METIS工具在并行模拟划分中的不足,本文通过分析影响并行网络模拟性能的因素,对METIS进行改进,提出了基于回退的优化划分算法。实验表明,回退算法通过对METIS的局部最优进行了改进,使得子网数减少了73.2%,边界路由器减少了28.8%,远程链路条数减少了30.8%,并行模拟的性能提高约14%。One of the research topics on parallel network is how to partition the simulation task more reasonable in order to reduce the simulation time and improve simulation performance. The most commonly used approach for partition task on parallel network simulation is METIS, but it has it shortcomings. In the paper, through analysis on the factors of the performance of parallel network simulation, we improve METIS, and present a new task partitioning algorithm based on rollback. Through improving the local optimum of METIS, the algorithm reduces the number of the remote link by 73.2%, subnet by 28.8%, and the border router by 30.8%, increases the performance of the parallel network simulation by 14%.

关 键 词：并行网络模拟 拓扑划分 METIS 回退划分算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]