基于多路由配置的IP快速恢复流量均衡方法

张莉敏，陈晓纯

(广东理工学院 信息工程系，广东 肇庆 526100)

0 引 言

当前，IP网络已经成为一个无处不在的平台，可以应对由于链路或节点故障引起的频繁拓扑变化，互联网可靠性和可用性的需求也相应增加。

最经典的路由方法OSPF(open shortest path first，开放最短路径优先)被广泛用于基于发生故障后改变的拓扑来更新转发信息[1]。但是，由于故障信息必须在中断后发送到每个节点，所以OSPF的恢复速度并不是很高，并且会造成网络拥塞[2]。Kvalbein等提出了一种快速恢复路由方法(多路由配置算法，multiple routing configuration，MRC)来提高网络的可靠性和可用性[3]。它将流量重新路由到备份路由，而无需等待网络故障后完成路由收敛[4]。

MRC的核心算法是预先为网络的物理拓扑运算一系列备份配置，并提前计算相应备份配置的备份路由表。当数据包遇到故障时，备份拓扑ID将附加到数据包头(服务类型，TOS字段)，并且数据包由备份表转发到下一个备份点。并通过链路状态通告(LSA)确认不同拓扑中同一条物理链路下链路状态的链路权值，从而确定哪些链路可用于发送流量。然而基于最小跳数的路由协议有时无法公平分配移动主机间的路由负载。流量分布不均衡可能会导致更高的数据包丢失率和某些移动节点上更快的能量耗尽。

针对这些问题，文献[5-6]提出在备份配置中生成最小生成数，减少路由跳数；文献[7]给出了一种新的备份配置设计方案，将高负荷路径的流量分离到其他可用路径，同时兼顾网络状况，如流量矩阵或网络拓扑。文献[5]的主要思想是在备份配置创建过程中识别关键节点。具有较高的连通度和数据流量的节点被定义为关键节点。源节点或目的节点是关键节点的数据流量将被分配给连接到关键节点的可用链路，链路负载的分配是智能化的。但这种评估方法不具备完整性。一些重要的“关键节点”不一定有很高的连通度，例如仅连接两个链路的“桥节点”。

文中创新性地给出了选取关键节点的新方法。有两种方法可以定义关键节点：第一种是通过网络中某一个节点的最短路径跳数与最短路径总跳数之比，称为关键节点，这是介数中心性(betweenness centrality)方法；第二种方法是根据网络中某一个节点到其他各节点的最短路径总和的倒数，称为紧密度(closeness)方法。

1 多路由配置算法

在本节中，将描述MRC方法[3]和文献[7]中使用的备份配置的特性，然后讨论它们存在的问题。

1.1 备份配置的创建

MRC算法通过循环将网络组件设置为隔离链路或隔离节点来生成一系列备份配置(backup configuration，BC)。在传输包时，源节点在数据包报头中写入原始拓扑的标识。当检测到某一网络设备不可用时，原始拓扑中通过故障组件的流量需要重新计算最短路径以确保连续传输。负责恢复数据包的路由器选择相应的备份配置，并把包头中的标识更改为该备份配置编号，目的是通知其他路由器转发该包时使用哪种备份配置。路由器根据目的地址查找备份路由表中的备份下一跳，然后转发报文。使用MRC方法可以在检测到故障后立即恢复传输路径，避免丢包和路由回路问题。

为了在链路失效后为受影响的数据包提供有效的路径，备份拓扑需要满足以下功能：

(1)各个备份配置含有原始拓扑的每一个节点，并且在任意两个节点间存在可用链路。

(2)在每个BC中，都有一个子拓扑，该子拓扑不包含所有受保护的链路和节点。子拓扑是一个连接图，即任意两个节点间有一条传输线路，那么将子拓扑称之为骨干网。

(3)原始拓扑的每条链路至少受到一个备份配置的保护。

如果备份配置满足上述功能，则确保每条链路至少由一个备份拓扑保护。

1.2 使用备份配置的分组重新路由方法

当链路不可用时，MRC方法根据原始拓扑和备份配置转发数据包。例如，在图1中，假设从节点1到节点2链路不可用，则选用BC1进行重路由。那么从节点1，2，4，5，6到节点8都会经过路径6-8，如此会使链路6-8出现拥塞问题。

为了解决上述问题，文献[7]提出了一种在创建备份配置过程中使用关键节点的方法。 该设计方案通过增加与关键节点相关的可用链接将流量分散到其他可用链接。

在文献[7]中，根据节点的连通程度来选择关键节点。然而，存在一些连通度较小的节点传输较多的数据流量，但这些节点一般不会被选择为关键节点。所以提出了一个新的标准来定义关键节点。该方法不会增加备份配置的数量，并且备份配置的数量与传统方法保持相同。

图1 原始拓扑5和备份配置

图2 连接到关键节点的可用链接

2 改进的备份配置设计方法

2.1 算法思想

改进算法的主要思想是在备份配置中使用关键节点[8-9]。基于网络状况，如流量矩阵，有两种识别关键节点的方案：介数中心性排序方法和紧密度排序方法。

(1)介数中心性排序方法[10-11]。

在这种方法中，基于网络拓扑来定义关键节点。中心节点v(B(v))的中心性表示为通过节点v的所有最短路径与网络中最短路径的总数之比。特别地，σst表示从s到t的最短传输路径的总跳数，σst(v)指从s到t且通过节点v的最短传输路径的总跳数，B(v)定义如下：

(1)

其中，n为网络中的节点个数。

(2)紧密度排序法。

在这种方法中，节点p(C(p))的紧密度是从节点p到网络中其余节点的最短传输路径总和的倒数。C(p)定义如下：

(2)

其中，n为网络中节点的数量；d(pi,pk)为pi到pk的最短路径的跳数。

首先选择关键节点，而后最大化每个备份配置中关键节点的可用链接。链路保护过程分为两部分：一是关键节点的链路保护；二是其他节点的链路保护。链路保护过程完成后，分析此时生成的备份配置是否符合第一节提出的创建规则。如果条件满足，那么程序将继续运行。否则，程序被终止。图2显示了备份拓扑中关键节点可用链路的分布情况。

从以上可以看出，该算法的目的是增加可用链接。关于选择关键节点，采取两种方法：第一种方法是分别选择具有较高的介数值和紧密度的Top K节点(Top K方法);第二种方法是使用与第一种方法相同的方法选择前K个节点，但同时考虑节点的位置信息(Non-adjacent K方法)。换句话说，如果要选择的下一个关键节点与已选取的关键节点连接，则放弃该节点，继续选择下一个节点当作关键节点。

2.2 算法流程

算法的输入变量是关键节点的数量K，输出变量是备份配置的数量N。最初，N初始化为1，该算法从步骤1继续执行至步骤5。

步骤1：由以下两种方法确定关键节点的定义标准：(1)介数中心性方法；(2)紧密度方法。

步骤2：选择K个关键节点，有两种选择方法。

(1)Top K方法：选择拥有较高介数值和紧密度的节点。

(2)Non-adjacent K方法：在这种方法中，基于第一种方法，同时结合了网络中关键节点的位置信息。如果关键节点相互连接，则会减少可用链接的最大数量。因此，如果下一个关键节点与先前选择的关键节点相邻，则跳过当前节点，并顺序选择下一个节点作为关键节点。

步骤3：与关键节点连接的链路的保护过程。必须确保在每个备份拓扑中有一个与关键节点连接的最少链路数量，如图2所示。它确保每个关键节点在每个备份拓扑中都有可用链接的数量。

每个备份拓扑中与关键节点连接的受保护链路的数量定义为P，关键节点的最大连通度定义为D，最大整数值P小于ceil(D/N)+1。例如，如图2所示，最大备份拓扑为3，关键节点最大连通度为3，每个备份拓扑中保护链路数为1。

步骤4：执行其他节点的链路保护过程。链接保护过程是使用文献[3]中的原始MRC算法执行。

步骤5：分析新的备份拓扑是否符合1.2节提出的创建规则。

如果条件满足，算法结束。 否则，N的值加1，然后重新从步骤1执行到步骤5。

3 实验性能分析

在本节中，讨论文中所提的方法对重新路由流量的影响。实验目的是评估单链路故障后的链路负载。

3.1 实验环境

为了测试该方法对单链路(或单节点)失效后路径数据流量分布的影响，仿真在欧洲网络拓扑结构COST 239[12]和COST 266[13]中执行，这两种拓扑连接了欧洲的主要城市。采用Top K方法和Non-adjacent K方法选择关键节点。实验评估参数是当K值发生变化时，单链路故障情况下的最大链路负载。

对于实验环境，网络中任何两个节点之间的流量都是根据它们所代表的国家的人口来估计的。由于仿真的目的是测量网络中流量的分布，因此链路容量设置得足够大以至于不会因拥塞而丢失数据包。一般来说，除了备份拓扑中的受保护链接之外，链接代价也被设置为1。

3.2 路由结果

图3～6给出的评估结果说明了，与传统方法(K的初始值为0)相比，文中提出方法的有效性。图3和图4显示了在两种不同方法下，COST 239模型的最大链路负载随K值的变化情况。图5和图6显示了在两种不同方法下，COST 266模型的最大链路负载随K值的变化情况。COST 239的备份拓扑数量为3，COST 266的备份拓扑数量为4。

图3 COST 239模型的Top K方法的结果

图4 COST 239模型的Non-adjacent K 方法的结果

对于COST 239模型，与传统方法相比，使用介数中心性定义方法的最大链路负载减少量约为71%。每种方法的最大链路负载百分比最小值如下：在Top K方法中，传统方法=3.4，介数中心性=1，紧密度=1.7；在Non-adjacent K方法中，介数中心性=1.8，紧密度=1.1。从结果中可以看出，用于确定备份配置中的关键节点的方法以及关键节点的最大可用链接是可行的。文中提出的方法对减少最大链路负载有更大的影响。当使用Top K方法时，介数中心性方法可以将最大链路负载值降低到高于紧密度方法。在使用Non-adjacent K方法时，紧密度方法更好。

图5 COST 266模型的Top K方法的结果

图6 COST 266模型的Non-adjacent K方法的结果

图5和图6显示了使用这两种方法在COST 266模型中对链路负载的影响，该模型大于COST 239使用Top K方法选择关键节点，最大链路负载的最小值为1.1。其中介数中心性方法为1.5，紧密度方法为1.1。使用Non-adjacent K方法来选择关键节点，介数中心性方法的最大链路负载的最小值为1.4，紧密度方法为1。

在图6中，由于介数中心性的K的最大值为4，COST 266模型有更多的节点，选择邻接点作为关键节点的概率更高。

如果使用考虑节点的位置的Non-adjacent K方法，Closeness方法比Betweenness方法减少得更明显，介数中心性方法的最大链路负载的最小值为1.4，紧密度方法为1。因此，可以得出这样的结论：在使用Closeness方法选择关键节点时，考虑大型网络中关键节点的位置是一个更好的策略。

从实验结果中可知，当关键节点约占整个拓扑的10%时，可以设置一系列符合条件的备份拓扑。在COST 239模型中，当K=2(图3和图4)时，可以生成合适的备份配置。在COST 266模型中，当K=1(图5和图6)时，可以生成合适的备份配置。当进一步增加K的值时，如果移除受保护的链路时，拓扑的连通性不满足创建规则(第1节提出)。因此，在不破坏备份配置的连通性的情况下，必须选择K的最大合适值。

4 结束语

文中提出了一种新的备份配置设计方法，以减少IP快速恢复过程中的网络拥塞。该方法的主要思想是在创建备份配置的过程中引入关键节点的概念，并比较关键节点数量不同时的链路负载。实验结果表明，该方法能够在不增加备份拓扑数量的情况下减少网络拥塞。与传统方法相比，最大链路负载减少约73%，单链路故障时最大减少跳数约为45%。由此可以得出这样的结论：考虑到大型网络的关键节点的位置并使用Closeness算法来选择关键节点是更好的策略。下一步将研究使用新的备份拓扑方法来快速恢复IP网络中双链路故障的方法，并且希望改进的方法能够最小化链路成本。