一种应用于不对称网络中的生成树拓扑抽象方法

摘要

本发明公开了一种应用于不对称网络中生成树拓扑抽象的方法，将不对称链路状态参数进行拓扑抽象的三角矩阵方法(TM)：通过原拓扑，构建一个边界节点的全连通图抽象拓扑；基于构建无向全连通图抽象拓扑M_u和M_l；计算M_u和M_l的最小生成树拓扑，分别表示为T_u和T_l；基于T_u构建一个有向树形抽象拓扑，将T_u上的每一条无向逻辑链路都替换为一对有向逻辑链路；共得到3个树形抽象拓扑，，T_u和T_l，将这三者发布到网络的其他路由域节点。使所有的不对称信息都被包含在树抽象拓扑中，可有效减少拓扑抽象后的失真。

主权项

1.一种应用于不对称网络中的生成树拓扑抽象方法，通过在原拓扑中的每对边界节点之间构建一条逻辑链路，形成一个边界节点的全连通图抽象拓扑其特征为：所述的生成树拓扑抽象步骤为：步骤[1]，基于所述的全连通图抽象拓扑构建无向全连通图抽象拓扑M_u和无向全连通图抽象拓扑M_l，构建的无向全连通图抽象拓扑M_u和无向全连通图抽象拓扑M_l上只有部分逻辑链路符合的法则为，全连通图抽象拓扑中各条边满足三角形不等式的法则；步骤[2]，构建无向全连通图抽象拓扑M_u和无向全连通图抽象拓扑M_l的最小生成树拓扑，分别表示为最小生成树拓扑T_u和最小生成树拓扑T_l，对于不在这两个最小生成树拓扑上的逻辑链路，可得到它们权值的下界；步骤[3]，基于最小生成树拓扑T_u构建一个有向树形抽象拓扑将最小生成树拓扑T_u上的每一条无向逻辑链路都替换为有向树形抽象拓扑上的一对有向逻辑链路，这是由于无向全连通图抽象拓扑M_u和无向全连通图抽象拓扑M_l上的另一部分逻辑链路不符合全连通图抽象拓扑的各条边满足三角形不等式的法则，这样是为了能得到不在这两个最小生成树拓扑上的逻辑链路权值的上界；步骤[4]，于是得到3个树形抽象拓扑，为有向树形抽象拓扑最小生成树拓扑T_u和最小生成树拓扑T_l，将三者发布到其他路由域节点上。