基于OSPF协议的增量最短路径树计算方法

摘要

本发明提出一种基于OSPF协议的增量最短路径树计算方法，包括以下步骤：路由器收到一条新的链路状态通告，判断变化链路的权值是否增大；根据所述变化链路的权值增大或减小，分别执行不同的最短路径树更新操作，将更新元素保存在优先级队列中；依次更新所述优先级队列中的队首节点，搜索所述队首节点的所有出边，判断能否为末节点提供更优的路径。本发明通过判断变化链路权值增大或减小以及其是否在原最短路径树上，找出受影响节点，采取增量方法更新原最短路径树，减少了最短路径树重计算的时间，从而减少了故障收敛时间，同时，通过对路由表作出最小的改变，提高了路由的稳定性。