优化直径网络构造与d分路由算法

Construct Optimal Diameter Network and D-Partition Routing Algorithm

网络的最大传输延时这个概念可以抽象为网络拓扑图的直径,而网络拓扑图的直径问题由于涉及网络结构设计中的大量应用而备受关注,研究如何构造直径优化的网络结构和高效的路由算法对于提高网络的性能至关重要.本文运用图论的方法,研究在网络节点具有相同度约束的情况下优化直径网络的构造方法以及路由问题,提出了一种简单有效的启发式路由算法并分析了其计算复杂度.目前,基于该算法的P2P蠕虫防御系统已经设计完成.

The maximum delay of network can be denoted by the diameter of the network. The problem of finding topological graphs of optimal diameter receives much attention from researchers due to its possible applications in network structure design. It is highly important to research how to construct an optimal diameter network and design the efficient routing algorithm. In this paper, by using graph-theoretical properties, the authors studied the method of constructing network with an optimal diameter and the routing problem when the degree-constrained was dealt with. The authors also presented an efficient and simple heuristic routing algorithm and analyzed its complexity. At the present time, we have finished the P2P worm defense system based on this algorithm.