优化树形拓扑覆盖网络路由的方法

摘要

本发明公开了一种优化树形拓扑覆盖网络路由的方法，它是在由主干边组成的覆盖网络中，动态的在不相邻的节点间建立传输路径即优化边，使节点间除原有树形拓扑的边外还有可选的路由路径，减少数据传输时在覆盖网络中的转发跳数。具体地说，本发明依据计算出来的反映优化边效益的util值建立优化边，对优化边进行更新，使优化边数量保持在一定数量内，以保持覆盖网络的树形结构。由于本发明通过向树形拓扑网络结构中不断地添加、更新优化边，增加可选的、最佳的数据路由路径，所以，本发明大大降低了高层节点的负载，有效地改善了网络负载不平衡的状况；进而降低了网络中高层节点单点失效风险；同时，还降低了网络的平均时延，提高了数据传输效率。

主权项

1、一种优化树形拓扑覆盖网络路由的方法，其特征在于：(1)、在节点进行数据交换时，系统服务器累计节点之间的数据交换次数；(2)、当节点之间的数据交换次数达到设定的阈值时，在由主干边组成的覆盖网络中，动态的在不相邻的节点间建立传输路径即优化边，使节点间除原有树形拓扑的边外还有能够选择的路由路径，减少数据传输时在覆盖网络中的转发跳数；(3)、路由选择方法是：(3a)、以目的节点为当前目标节点，查询路由表，看是否存在与当前目标节点直连的优化边，如果存在，则返回当前目标节点作为路由结果；(3b)、如果不存在，则以当前目标节点的父节点为当前目标节点，查询路由表，当找到与当前目标节点直连的优化边，则返回当前目标节点作为路由结果；当没有找到与当前目标节点直连的优化边，则继续递归将当前目标节点的父节点作为当前目标节点来查询路由表，直到当前目标节点的父节点为整棵树的根节点停止；(3c)、如果整个过程都未找到能够使用的优化边，则以原树形拓扑路由算法的结果作为路由结果；所述优化边的建立是依据计算出来的反映优化边效益的util值建立的；定义优化边(u，v)在缩短数据转发路径方面的收益为util(u，v)，计算公式为：其中，N为整个网络中节点的数量，其中N_u和N_v分别表示以u和v为根的子树的节点数；S_u表示以u为根节点的子树的节点集合，S_v表示以v为根节点的子树的节点集合；D(u，v)为u，v两点间的在覆盖网络中的距离；定义在覆盖网络中相邻的节点距离为零，不相邻的节点之间的距离为两点间路径上节点的数量；在建立优化边时，依据网络中所有潜在的优化边util值的大小，优先加入util值大的优化边；依据计算出来的反映优化边效益的util值建立优化边，其步骤如下：A、对于每一个潜在的目标节点，进行util值的计算；B、将潜在目标节点按util值由大到小排序，舍去util值为0的潜在目标节点；C、按照util值由大到小的顺序依次建立优化边，将信息存入路由表；D、当建立的优化边数量达到预先设定的上限时结束。