基于抽象消减和流量估计的并行网络模拟拓扑划分算法

Topology Partition Algorithm Based on Abstract Subtraction and Traffic Estimation for Parallel Network Simulation

大规模并行网络模拟已成为目前研究Internet的主要方法,针对传统网络拓扑划分方法划分不均衡的问题,提出基于抽象消减和流量估计的并行网络模拟拓扑划分算法.采用抽象消减技术,将拓扑中度为1的节点递归抽象到其相连路由器上;采用流量估计技术,首先对拓扑中所有节点和链路利用估计算法进行权值初始化,然后将节点间流量转换为节点间权值,并将相应节点和链路的权值进行叠加.同时为避免权值差距过大,对权值进行规范化处理.实验结果表明,该划分算法相对于传统划分算法,节点压缩率在93.7%以上,缩减子域数约56.9%,减少远程链路数约22.9%,减少模拟时间约12.63%,提高了模拟的规模和效率.

Parallel simulation for large scale network has become the main method of Internet research. Aiming at the imbalance of traditional network topology partition method, a topology partition algorithm for parallel network simulation based on abstract subtraction and traffic estimation is put forward. The node with one degree is reeursively abstracted to conjoint router by abstract subtraction technology. The weights of node and link in the topology are initialized by estimating algorithm, and the traffic between nodes is changed to weight, which will he accumulated to the corresponding node and link. At the same time, the weight should be normalized to avoid weights gap. Experimental results prove that this partition algorithm can abstract node by 93.7 percent and reduce by subdomain by about 56.9 percent, r-link by about 22. 9 percent, and simulation time by about 12.63 percent. Compared with the traditional partition algorithm, the algorithm improves the scale and efficiency of simulation.