最短路徑樹構建的最小動態更新摘要 - 最短路徑樹（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，以獲得最終結果。 改變邊緣權重兩次的冗余是由改