最短路径树构建的最小动态更新

《最短路径树构建的最小动态更新》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最短路径树构建的最小动态更新摘要-最短路径树（SPT）计算是使用任何链路状态路由协议（包括最广泛使用的OSPF和IS-IS）的路由器的主要开销。链接状态的变化现在常常发生。网络路由使用传统的静态SPT算法在发生变化时重新计算整个SPT不是有效和稳定的。在本文中，我们提出了新的动态算法，以最小的计算开销来计算和更新SPT。并且当一些链路状态改变时，通过在现有SPT的拓扑中具有最小变化来实现路由稳定性。对于作者的了解，我们的算法优于文献中最好的算法。关键词-路由，最短路径树，OSPF。1引言互联网在大小和流量负载上都在迅速增长

2、。路由域中的路由器数量正在变大。链路故障，恢复或更改也更频繁出现。在使用基于链路状态的路由协议（例如广泛使用的OSPF和IS-IS）的网络中，每个路由器重新计算一个根据自身根据变化的新的最短路径树（SPT）的链接状态。今天大多数商业路由器通过删除SPT并使用静态SPT算法（如Dijkstra算法[1]）构建新的路由器来进行此计算。结果，SPT计算成为使用高吞吐量网络的瓶颈，并且路由区域的大小变得不必要地受限制。由于路由表项[2]，[3]，[4]的冗余更新，路由不稳定性增加。用于更新SPT的动态算法有可能提供更好的性能，因为

3、通常每次只有少数链路状态更改。这是通过利用原始SPT中的可用信息来实现的。通过降低SPT计算的复杂度，从而消除了这种性能瓶颈，允许高吞吐量网络的更大的路由区域。通过消除更新路由表中的冗余，路由不稳定性被控制在一个较低的水平。因此，重要的是研究有效的动态SPT算法，可以显着提高计算复杂度并减少更新冗余。动态更新最短路径树的问题可能直接有益于许多研究领域，包括通信网络，VLSI设计，运输网络和制造商店的调度。在本文中，我们提出了一种新的算法框架，消除SPT计算中的冗余，并保持SPT的最小更新。我们的算法设计实现了两个优化目标。

4、一个是最小化更新SPT的计算复杂度。另一个是确保SPT的变化是最小的。第6节中的复杂性分析表明，与[5]中的算法相比，我们的算法实现了显着的改进。此外，我们的算法可以优雅地扩展，以解决具有负权重边缘的图形中的类似问题。本文的剩余部分组织如下。第二部分介绍了论文中使用的图论定义和符号。第三节描述了我们用于计算新的SPT的算法。第四节已经给出了一些例子，以便更好地理解动态算法。第五节分析了该算法的渐近计算复杂度的理论界限。然后我们讨论如何通过比较第六部分中的以前的结果，我们的解决方案如何提高效率。二，定义和符号A．原图G我们现

5、在定义一些符号在本文的其余部分使用。让G=(V,E,w)表示有向图，其中V是节点集合，E是图中的边集合。图G包含非负重环。令S(G)V表示G的根节点或源节点。图1的示例如图1所示。我们使用w（e）来表示每个有向边eE的边e的权重。如果边e是ij，节点i和节点j分别表示e的源节点和末端节点。让E(e)作为边e的终端节点，而S(e)作为源节点。有向路径的长度或距离是路径上边的权重之和。根树T是G的子图，使得S（G）在T中，并且T中的每个节点可以通过使用仅在T中的边缘的唯一定向路径从S（G）到达。eT并且从ij，我们说节点i是j

6、的父节点。我们定义一个节点iT具有以下属性：P（i）是i的父节点，D（i）是i的距离属性。因为T是树，所以调用P（i）递归地确定从S（G）到T中的任何节点的唯一路径。T中的节点i的后代都是可由i到达的节点。我们使用des（i）表示包含i和树T中i的所有后代的子集。定义2若i是图G的V中的一个节点，des(i)={v

7、v=i或v是最短路径树T的中i的子节点vV}B：权重变化图这里我们介绍一个权重变化图G*。该图将帮助我们了解我们的算法的良好的属性。基本算法基于该图G*如果我们有一个图G（V，E，w）和最短路径树T，我们可以得

8、到一个权重变化图G*。定义2.2：若G=（V，E，w）则G*=（V，E，w*）对每一条边eE，ij则权值变化为w*(e)=w(e)+D(i)-D(j)(在最小生成树的基础上)根据II.2的定义，我们可以绘制权重变化图G*在图2中，其对应于图1中的图。两个图都具有相同的最短路径树（图1和图2中用粗线表示SPT）。在我们的基本算法中的动态算法中，所有的计算都基于图G*，图G*临时边权值和SPT，直到我们找到最终的SPT。如果我们有一个节点集Q，我们定义一些与Q有一些关系的边集。定义II.3，如果Q是G.*的节点集合，设Sour

9、ce_part{Q}是G*的边集合，即Source_part{Q}={e

10、S(e)Q,E(e)Q,eE}定义II.4如果Q是G.*的节点集合，设End_part{Q}是G*的边集合，即End_part{Q}={e

11、E(e)Q,S(e)Q,eE}当一个边e,ij的权值增加或减少，我们使用w’来表示新的权值