第3章 基于超节点的覆盖网络拓扑构建算法

3.1 研究背景

为改善现有IP网络的可靠性和效率，路由覆盖网作为一种有效的方法得到了深入研究和广泛应用。一方面，路由覆盖网可以通过弹性路由解决IP网络链路断裂或拥塞引起的丢包问题，提高IP网络的可靠性；另一方面，通过优选覆盖路径，可以降低通信时延，提高IP网络的效率。覆盖网络拓扑是保障其性能的前提和基础。通过分析已有覆盖网络拓扑存在的问题，本章提出了基于超节点的覆盖网络拓扑构建算法SR-KMST。该算法研究了超节点的选取以及K最小生成树拓扑生成的问题，并针对物理链路故障引发的覆盖网备份路径与物理路径同时失效的问题，提出了快速恢复机制。

已有的路由覆盖网拓扑可归纳为网状、树状和混合状态3种类型。最具代表性的是全网状（Full Mesh overlay Topology, FM）[23]、多树状（K-Minimum Spanning Tree overlay topology, KMST）[63]、混合状（Mesh-Tree overlay topology, MT[136], Adjacent-Connection overlay topology, AC[25]）。下面介绍已有覆盖网拓扑及其存在的问题。

1．Full Mesh overlay topology

全网状覆盖网拓扑中，可以优选中继节点进行覆盖路由，所以其性能较好。假定共有M个覆盖节点，每个节点需与其他M-1节点建立覆盖链路，如图3-1所示，所以FM的复杂度是O（M2），可扩展性差，研究表明全网状覆盖拓扑的规模最大为50个节点[23]。

图3-1 全网状覆盖网络拓扑

2．K-Minimum Spanning Tree overlay topology

KMST是在相同的覆盖网节点间形成K个最小生成树，使得任意两点间存在K条不同的覆盖路径，其中覆盖网链路的权重为两点间时延或该链路对应的物理路径所包含的物理链路的数量（即跳数）。由于链路的时延与链路当前的负载有关，很难实时检测，在一定程度上，链路的跳数可以近似地反映链路的时延的大小关系。其中，K的值由节点度的约束条件决定，如图3-2表示2-MST覆盖网拓扑结构。最小生成树是连接所有节点的最低代价的结构，可以降低覆盖网的维护代价；另一方面，KMST确保源和目的节点间存在K条不同的传输路径，这样，当一条路径出现故障时，可以快速切换到另一条路径，提高传输的可靠性。与FM相比较，KMST中每个节点最多需维护2K个邻居节点的关系，可扩展性好。但KMST仅考虑了覆盖节点间的连接关系，没有考虑覆盖网节点的选择问题。

图3-2 2-MST覆盖网拓扑

3．Mesh-Tree overlay topology

MT是在已建立的覆盖网最小生成树的基础上，在祖孙或叔侄关系的节点间增加链路，如图3-3所示。与KMST类似，虽然MT提高了网络的可靠性，但没有考虑覆盖节点的选择问题。

图3-3 Mesh-Tree覆盖网拓扑

4．Adjacent-Connection overlay topology

AC拓扑的构建方法如下：对于任何覆盖网节点对（m, n），如果没有其他覆盖网节点连接到节点m和n形成的物理路径上的任何覆盖网节点，则建立一条m和n之间的覆盖链路，如图3-4所示。虽然在构建AC拓扑时，用到了节点间的物理路径，但没有考虑节点间的最短路径，即没有考虑时延等参数。

图3-4 AC覆盖网拓扑

以上的覆盖网拓扑在构建过程中着重考虑了节点间的连接关系，而忽略选择合理的覆盖网节点，这必然影响路由覆盖网的性能，因为一些节点在数据通信中起着关键的作用，如果在建立覆盖网拓扑时加入这些节点，能够提高覆盖路由的性能，例如降低时延。