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

最短路径树构建的最小动态更新摘要 - 最短路径树（SPT）计算是使用任何链路状态路由协议（包括最广泛使用的OSPF和IS-IS）的路由器的主要开销。 链接状态的变化现在常常发生。 网络路由使用传统的静态SPT算法在发生变化时重新计算整个SPT不是有效和稳定的。 在本文中，我们提出了新的动态算法，以最小的计算开销来计算和更新SPT。 并且当一些链路状态改变时，通过在现有SPT的拓扑中具有最小变化来实现路由稳定性。 对于作者的了解，我们的算法优于文献中最好的算法。关键词 - 路由，最短路径树，OSPF。1引言互联网在大小和流量负载上都在迅速增长。路由域中的路由器数量正在变大。链路故障，恢复或更改也更频繁出现。在使用基于链路状态的路由协议（例如广泛使用的OSPF和IS-IS）的网络中，每个路由器重新计算一个根据自身根据变化的新的最短路径树（SPT）的链接状态。今天大多数商业路由器通过删除SPT并使用静态SPT算法（如Dijkstra算法1）构建新的路由器来进行此计算。结果，SPT计算成为使用高吞吐量网络的瓶颈，并且路由区域的大小变得不必要地受限制。由于路由表项2，3，4的冗余更新，路由不稳定性增加。用于更新SPT的动态算法有可能提供更好的性能，因为通常每次只有少数链路状态更改。这是通过利用原始SPT中的可用信息来实现的。通过降低SPT计算的复杂度，从而消除了这种性能瓶颈，允许高吞吐量网络的更大的路由区域。通过消除更新路由表中的冗余，路由不稳定性被控制在一个较低的水平。因此，重要的是研究有效的动态SPT算法，可以显着提高计算复杂度并减少更新冗余。动态更新最短路径树的问题可能直接有益于许多研究领域，包括通信网络，VLSI设计，运输网络和制造商店的调度。 在本文中，我们提出了一种新的算法框架，消除SPT计算中的冗余，并保持SPT的最小更新。我们的算法设计实现了两个优化目标。 一个是最小化更新SPT的计算复杂度。 另一个是确保SPT的变化是最小的。 第6节中的复杂性分析表明，与5中的算法相比，我们的算法实现了显着的改进。 此外，我们的算法可以优雅地扩展，以解决具有负权重边缘的图形中的类似问题。本文的剩余部分组织如下。 第二部分介绍了论文中使用的图论定义和符号。 第三节描述了我们用于计算新的SPT的算法。 第四节已经给出了一些例子，以便更好地理解动态算法。 第五节分析了该算法的渐近计算复杂度的理论界限。 然后我们讨论如何通过比较第六部分中的以前的结果，我们的解决方案如何提高效率。二， 定义和符号A原图G我们现在定义一些符号在本文的其余部分使用。 让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 并且从i j，我们说节点i是j的父节点。 我们定义一个节点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|v=i或v是最短路径树T的中i的子节点vVB：权重变化图这里我们介绍一个权重变化图G*。 该图将帮助我们了解我们的算法的良好的属性。 基本算法基于该图G* 如果我们有一个图G（V，E，w） 和最短路径树T，我们可以得到一个权重变化图G*。定义2.2：若G=（V，E，w）则G*=（V，E，w*）对每一条边eE， i j则权值变化为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.*的节点集合，设Source_partQ 是G*的边集合，即Source_partQ = e|S(e)Q ,E(e) Q,eE定义II.4如果Q是G.*的节点集合，设End_partQ 是G*的边集合，即End_partQ = e|E(e)Q ,S(e) Q,eE当一个边e, i j的权值增加或减少，我们使用w来表示新的权值，因为这些改变，如果从S(G)到节点j的最短路径（或父节点）不同于最初的D(j)(或P(j)，当算法结束时，我们应该有节点j的新值。三算法A. 基本算法我们首先提出一种基本算法，当一个边缘的权重发生变化时，可以将SPT从源节点S（G）重新计算到图中的每个其他节点。 该算法处理权重变化图G *。 假设在原始图G我们有一个静态的最短路径树T，可以通过使用静态Dijkstra算法导出。 在这棵树T中，对于每个节点v，我们从源节点S（G）获得其父节点P（v）及其距离D（v）的信息。 在此算法中，一旦节点发生变化，T和P就会更新。 当算法结束时，由于一个边缘的变化，我们得到一个新的T和P用于新的SPT。在给出基本算法之前，我们给出一个函数SELECT MIN（B，T），如图3所示.B是图G *的边集。 T是图G的最短路径树。我们尝试从边集B找到最小权重边。如果有几个权重相同的边，我们尝试找到一个最靠近源节点S（G ）树T.SELECT MIN（B，T）IFB中包含两条或两条以上相等的最小权值选择其中最小权值所在边e1，它的终节点或者起点更接近于root节点从B中移除e1并返回e1Return e1Else 从B中移除e1并返回e1Return e1END基本算法包括两部分。 一个部分是当一个边权值变大时的情况。 另一部分是当一个边变小时的情况。 在我们执行基本算法之前，我们应该具有定义II.2的旧的SPT和权重交换图G *。基本算法：Step1：等待一条边e：ii j 的权值w*(e)变化成w*(e)1. 若w*(e) w*(e)且eT则d= w*(e)- w*(e)进入step2 /case1 一条边权值变大/2. Else if w*(e)0 则d= w*(e)进入step3 /case2 一条边权值变小/3 else 进入step1Step2：1 初始化 Q des(j) Q是节点集合，des(j)是j的子节点的集合 B=e|eEnd_partQ 并且w*(e)d /从j或j的子节点找到边，使边的终节点为Q而且初节点不在Q中且w*(e)d2 若B是空集/*改变剩下节点*/ 3 （else）否则， /* */更新在Q1中节点的边权值Q=Q-Q1，w(e1)=0 /*更新Q*/通过添加权重小于d的Source_part Q1的边缘，并删除属于End_part Q1的边来更新B。去到2Step 3：/*当一条边的权值减少*/1.初始化/*节点j的后代更新一次*/ 通过将属于Source_part Q1的边加入权重低于0来更新B1，通过删除属于End_part Q1的边来更新B， 为了使这个算法更容易理解，我们简要介绍一下它的执行方式。 在步骤1中，当一个边缘的权重发生变化时，基本算法决定是否需要更改旧的SPT。 只有在情况1和情况2中，我们需要分别去步骤2和步骤3获得一个新的树。 否则，我们仍然等待另一个权值变化，同时保持相同的最短路径树。步骤2处理一个边缘的重量增加。 首先，我们初始化一个节点集Q和一个边集B.所有可能与S（G）（或新的父节点）有最短距离的节点都是Q.B中的所有边都是可以使最短的 Q节点距离增加较少。 此时，我们只考虑权值小于d的边。 只有从Q中这些边缘的节点可以实现比原来的一个加d的距离，这只是跟随旧的SPT。 对于每个更新步骤，我们从B中选择最小权重边e1，这可以为Q1中的节点带来最小的增加。 然后，通过添加w *（e1）来更新这些节点的新距离。 此外，我们需要改变图G中连接节点Q1的重量。 在一个更新步骤结束时，应相应更新B和Q。 这个过程不会结束，直到B =。步骤3处理一个边缘减少的权重。 在初始化期间，des（j）中的所有节点都被更新一次。 B中的边是可能使节点des（j）之外的节点的最短距离更小的潜在元素。 因为我们不知道确定节点需要更新，所以节点具有与旧SPT不同的最短路径被包括在节点集Q中。首先，我们更新与子树des（j）相邻的节点。 我们称之为这些节点Q1。 来自节点集Q1的所有边缘形成边缘集合B1。 我们通过向它们添加w *（e1）-d来更新这些边。 所有这些负值都在边集合B1中。 在我们执行B中的所有边之后，我们将B1移动到B，到B1和0到d。 如果B =，更新过程结束。 否则，我们从更新节点更新从子树 des（j）到更多节点的工作。 更新过程类似于步骤2。B. 多重链路权重变化当一次发生多个链路权重变化时，最简单的方法是为每个改变的权重顺序运行算法。 然而，计算开销的优化可以通过将变化组合成两组来实现：权重增加边缘和权重减少边缘。 对于算法中的步骤2和步骤3的每个权重变化，显然需要单独的初始化。 首先，我们初始化所有的重量增量。 集Q包括所有需要改变距离（或父母）的节点。 然后更新循环体与一个重量增加相同，并产生一个临时图G * 1。 其次，对于所有的权重减量，我们更新图G * 1。 如前所述，在步骤3的初始化中，我们更新每个权重减少边缘的所有后代，并保持一个边集合B.步骤3中的算法的其余部分类似地执行。C. 第二种算法当我们使用基本算法来计算新的SPT时，我们将显示仍然存在冗余。 例如，如果边缘（C，G）从0减小到-5，在图G中为7到2，则在计算基本算法时边缘（G，D）的权重会改变两倍。 一个是更新节点G及其连接边，将其重量更改为-1。 另一个是更新节点D及其连接边缘，将其权重更改为0，以获得最终结果。 改变边缘权重两次的冗余是由改