3.2 基于超节点的覆盖网拓扑构建

3.2.1 问题的描述

构建路由覆盖网络拓扑，使得网络的总时延最小，因此，问题可以定义如下：用图Gu（Vu, Eu）表示IP网络拓扑，其中，Vu和Eu分别表示物理网络的节点集合和链路（即边）集合。相应地Go（Vo, Eo）表示一个覆盖网拓扑，Vo表示覆盖网络节点集且Vo∈Vu, Eo是覆盖网链路的集合。N=|Vu|和M=|Vo|分别表示物理网络和覆盖网络的规模。对于m, n, i, j∈Gu，布尔变量是一个物理链路指示器，当节点m和n之间的物理路径包含物理链路ij 时，=1，否则=0；而对于x, y, m, n∈Go, 表示一个覆盖网链路指示器，当覆盖网路径xy包含覆盖链路mn时，=1，否则=0。Dij表示物理链路ij的时延。路由覆盖网拓扑构建问题可以表述为：构建一个覆盖网络拓扑，使得网络的总时延最小，用公式表示如下：

3.2.2 超节点的选取

实现上述目标的第一步就是要选择尽量少的能提供最短路由的节点作为路由覆盖网的核心节点。研究表明在物理网络中有少量具有较高介数中心的节点频繁出现在最短路径上[7][17]；也就是说，少量中继节点可以为大多数的端到端通信节点提供最优的路由，这些中继节点具有较高的介数中心。我们称这些中继节点为超节点（Super-Relay nodes）。节点的介数中心[143]定义为网络中所有最短路径中经过该节点的路径的数目占最短路径总数比例，用公式表示如下：

其中V表示节点集，σst是节点s和t间的最短路径的数目，σst（v）表示节点s和t间的最短路径中经过节点v的路径数目。

综上所述，要提高路由覆盖网络的性能，选择并合理连接超节点是至关重要的。为了验证超节点在路由中的重要性，我们以一个真实的物理网络CN070[137]为例，统计了节点的介数中心分布情况，结果如图3-5所示。CN070反映了2006年中国大陆互联网中核心路由器的连接情况。网络中链路的权重直接影响节点间最短路径的选择，进而影响节点的介数中心的计算。因此，我们在区间[40-240]Mb/s随机为CN070中每条链路进行赋值，该值代表链路的可用带宽；而链路的权重设置为该链路可用带宽的倒数。为链路赋值不同的权重可以产生不同加权网络拓扑。如图3-5所示，横坐标是按介数中心降序排列的节点的ID，纵坐标是介数中心；图中的星型线是CN070加权网络中节点的介数中心，圆圈线是相应的无权网络中节点的介数中心。图3-5中，加权网络中每个节点的介数中心是对链路赋值2000次后所得的平均值。由图可以看出，只有少数节点具有较高的介数中心，且加权网络中节点的介数中心与相应的无权网络中节点的介数中心具有相同的分布。这表明，我们可以根据无权网络计算节点的介数中心，并选择少量具有较高介数中心的节点作为覆盖网络的超节点。而加权网络的链路权重是动态变化的，很难精确测量。

根据上面的分析，我们从无权网络中选取一定数量的具有较高介数中心的节点作为超节点。只有当物理网络拓扑发生变化时，才重新计算超节点，这样的选取方法简单，复杂度小。超节点的数量取决于物理网络的规模，实验结果表明，选取10%左右的超节点便可以提供较好的性能。

3.2.3 K最小生成树覆盖网拓扑

我们构造的覆盖网拓扑由超节点（Super-Relay nodes）和普通节点（Ordinary-Relay nodes）构成，其中超节点是按照3.2.2节中所述方法从无权物理网络中选取一定数量的具有较高介数中心的节点；而普通节点是根据端系统或用户的需求选择的主机节点。因此，超节点相对稳定，服务周期长，是物理网络中选取的介数中心较高的路由器节点，或者是连接到该路由器的服务器；而普通节点则是根据用户的需求选择的主机节点并将其映射到物理网络中，如图3-6所示，节点A、B、E、F、G和I是普通节点，节点C、D和H代表超节点。

我们提出的覆盖网络拓扑构建算法是基于超节点的K最小生树（K Minimum Spanning Tree based on Super-Relay nodes, SR-KMST）。构建过程中，首先将所有覆盖网节点（包括超节点和普通节点）连接形成K最小生成树（K-MST），假如，超节点间没有形成全网状结构，则在超节点之间增加覆盖网链路，使之形成全网状结构。K值的选取依据节点的度约束来决定。构建K最小生成树时，设置覆盖网链路的权重为该链路对应的IP路径所包含的物理链路的跳数。众所周知，最小生成树是连接所有节点的代价最小的树；而构建K最小生成树可以确保两个覆盖网节点间存在K条相对独立的覆盖路径，这可以提高可靠性和容错性。另一方面，超节点之间形成全网状结构，可以减少路径长度，降低路由代价（如时延）；且同一个超节点集可以服务于不同的普通节点集，形成多个不同的覆盖网络。

图3-6显示了基于超节点的2最小生成树（SR-2MST）覆盖网络的构建过程，在覆盖网络（Overlay Network）中，黑色实线和黑色虚线分别表示两个最少重叠的最小生成树；为了在超节点C、D和H之间形成全网状结构，在节点C和H之间增加一条覆盖链路CH（红色虚线所示）。

算法SR-KMST的具体描述如下：

SR-KMST算法

Gu（Vu, Eu）和G′u（V′u, E′u）分别表示一个加权物理网络和对应的无权网络。VSR和VOR分别表示组成覆盖网络的超节点集和普通节点集。N r=|V SR|为超节点的数量。MST（G）表示图G的最小生成树中边的集合，假如G是一个非连通图，则MST（G）表示G中各部分所形成的森林。

输入：G′u（V′u, E′u）和VOR

输出：覆盖网络拓扑GO

① 计算G′u（V′u, E′u）中所有节点的介数中心，记为BCs。

② 从BCs中选取介数中心最高的Nr个节点作为超节点，记为VSR。

③ 连接No=|VSR∪VOR|个覆盖网节点形成一个全网状拓扑GTO。

④ 初始化GTO中每条覆盖网链路的权重为其对应的物理路径的跳数。

⑤ 在拓扑GTO中应用下列方法计算K最小生成树Fk：

G0=GTO；

F0=null；

For j=1…k do

Tj=MST（Gj-1）；

Fj=Fj-1∪Tj；

Gj=Gj-1\Tj；

End For

⑥ 连接Nr个超节点形成全网状结构G relay，其中每条链路的权重为其对应的IP路径的跳数。

⑦GO=F k∪Grelay。

表3-1显示了算法SR-KMST与已有覆盖网络拓扑构建算法FM[23]、KMST[63]、MT[136]和AC[25]。在计算复杂度和节点度方面的对比分析，其中N和M 分别表示物理网络和覆盖网络中节点数目，No是由算法SR-KMST构造的覆盖网络中节点的数目，Nr是超节点的数目，LP表示物理网络中路由路径的平均跳数。计算复杂度体现了构造覆盖网拓扑的代价，而节点度的大小决定了覆盖网络中节点需维护的邻居节点的个数，在一定程度上反映了覆盖网络的维护代价。

从表3-1中可以看出，FM具有最小的计算复杂度。由于K的值远小于M 的值，因此KMST与FM的复杂度相同，而SR-KMST的复杂度略大于KMST的复杂度（No≥M）。在SR-KMST中，虽然超节点之间形成全网状结构，但与FM算法相比较，SR-KMST中节点度非常小（M≫Nr, M-1≫K），这表明SR-KMST具有一定的可扩展性。