基于非对称有向网络的拓扑抽象算法研究

网络规模的扩大导致了路由可扩展性的下降,因此未来的网络将向着分层多域的层次路由体系结构发展.在层次路由中,每个路由域通过拓扑抽象算法对内部拓扑进行汇聚并广播给外部节点,拓扑抽象算法将直接影响到网络的路由性能.本文提出了一种用于非对称有向网络的新型拓扑抽象算法——SHEF算法,该算法结合了面向源的拓扑抽象方法和最小生成树的概念,基于重边优先的准则对非对称的有向网络进行拓扑抽象和汇聚.仿真结果证明,该算法的权值偏差比传统方法减少了75%,较好地解决了路由信息复杂度和准确性之间的矛盾,具有良好的路由性能.

Research on Topology Aggregation in Asymmetric Directed Networks

Routing scalability may degrade due to the increasing network scale. So the global communication network in the future will intend to a hierarchical routing architecture with multiple routing domains and routing layers. In hierarchical routing, each routing domain compact its internal topology by topology aggregation algorithm and propagates the aggregated routing information to outside. So the topology aggregation algorithm will affect the routing performance greatly. In this paper, a novel topology aggregation method--SHEF algorithm is proposed to compact the asymmetric directed graph. Based upon a heavy-edge-first rule, the source-oriented method and minimum spanning tree arc integrated to aggregate the directed graph. Compared with the traditional method, the suggested algorithm can reduce the weight deviation by 75 percent. Simulation results show that SHEF has a good tradeoff between the routing information complexity and routing accuracy, as a result yields outstanding routing performance.