最短路徑樹構(gòu)建的最小動態(tài)更新摘要 - 最短路徑樹（SPT）計算是使用任何鏈路狀態(tài)路由協(xié)議（包括最廣泛使用的OSPF和IS-IS）的路由器的主要開銷。 鏈接狀態(tài)的變化現(xiàn)在常常發(fā)生。 網(wǎng)絡(luò)路由使用傳統(tǒng)的靜態(tài)SPT算法在發(fā)生變化時重新計算整個SPT不是有效和穩(wěn)定的。 在本文中，我們提出了新的動態(tài)算法，以最小的計算開銷來計算和更新SPT。 并且當一些鏈路狀態(tài)改變時，通過在現(xiàn)有SPT的拓撲中具有最小變化來實現(xiàn)路由穩(wěn)定性。 對于作者的了解，我們的算法優(yōu)于文獻中最好的算法。關(guān)鍵詞 - 路由，最短路徑樹，OSPF。1引言互聯(lián)網(wǎng)在大小和流量負載上都在迅速增長。路由域中的路由器數(shù)量正在變大。鏈路故障，恢復或更改也更頻繁出現(xiàn)。在使用基于鏈路狀態(tài)的路由協(xié)議（例如廣泛使用的OSPF和IS-IS）的網(wǎng)絡(luò)中，每個路由器重新計算一個根據(jù)自身根據(jù)變化的新的最短路徑樹（SPT）的鏈接狀態(tài)。今天大多數(shù)商業(yè)路由器通過刪除SPT并使用靜態(tài)SPT算法（如Dijkstra算法1）構(gòu)建新的路由器來進行此計算。結(jié)果，SPT計算成為使用高吞吐量網(wǎng)絡(luò)的瓶頸，并且路由區(qū)域的大小變得不必要地受限制。由于路由表項2，3，4的冗余更新，路由不穩(wěn)定性增加。用于更新SPT的動態(tài)算法有可能提供更好的性能，因為通常每次只有少數(shù)鏈路狀態(tài)更改。這是通過利用原始SPT中的可用信息來實現(xiàn)的。通過降低SPT計算的復雜度，從而消除了這種性能瓶頸，允許高吞吐量網(wǎng)絡(luò)的更大的路由區(qū)域。通過消除更新路由表中的冗余，路由不穩(wěn)定性被控制在一個較低的水平。因此，重要的是研究有效的動態(tài)SPT算法，可以顯著提高計算復雜度并減少更新冗余。動態(tài)更新最短路徑樹的問題可能直接有益于許多研究領(lǐng)域，包括通信網(wǎng)絡(luò)，VLSI設(shè)計，運輸網(wǎng)絡(luò)和制造商店的調(diào)度。 在本文中，我們提出了一種新的算法框架，消除SPT計算中的冗余，并保持SPT的最小更新。我們的算法設(shè)計實現(xiàn)了兩個優(yōu)化目標。 一個是最小化更新SPT的計算復雜度。 另一個是確保SPT的變化是最小的。 第6節(jié)中的復雜性分析表明，與5中的算法相比，我們的算法實現(xiàn)了顯著的改進。 此外，我們的算法可以優(yōu)雅地擴展，以解決具有負權(quán)重邊緣的圖形中的類似問題。本文的剩余部分組織如下。 第二部分介紹了論文中使用的圖論定義和符號。 第三節(jié)描述了我們用于計算新的SPT的算法。 第四節(jié)已經(jīng)給出了一些例子，以便更好地理解動態(tài)算法。 第五節(jié)分析了該算法的漸近計算復雜度的理論界限。 然后我們討論如何通過比較第六部分中的以前的結(jié)果，我們的解決方案如何提高效率。二， 定義和符號A原圖G我們現(xiàn)在定義一些符號在本文的其余部分使用。 讓G=(V,E,w)表示有向圖，其中V是節(jié)點集合，E是圖中的邊集合。 圖G包含非負重環(huán)。 令S(G) V表示G的根節(jié)點或源節(jié)點。圖1的示例如圖1所示。我們使用w（e）來表示每個有向邊eE的邊e的權(quán)重。如果邊e是ij，節(jié)點i和節(jié)點j分別表示e的源節(jié)點和末端節(jié)點。 讓E(e) 作為邊e的終端節(jié)點，而S(e) 作為源節(jié)點。 有向路徑的長度或距離是路徑上邊的權(quán)重之和。根樹T是G的子圖，使得S（G）在T中，并且T中的每個節(jié)點可以通過使用僅在T中的邊緣的唯一定向路徑從S（G）到達。eT 并且從i j，我們說節(jié)點i是j的父節(jié)點。 我們定義一個節(jié)點iT具有以下屬性：P（i）是i的父節(jié)點，D（i）是i的距離屬性。 因為T是樹，所以調(diào)用P（i）遞歸地確定從S（G）到T中的任何節(jié)點的唯一路徑。T中的節(jié)點i的后代都是可由i到達的節(jié)點。 我們使用des（i）表示包含i和樹T中i的所有后代的子集。定義2若i是圖G的V中的一個節(jié)點，des(i)=v|v=i或v是最短路徑樹T的中i的子節(jié)點vVB：權(quán)重變化圖這里我們介紹一個權(quán)重變化圖G*。 該圖將幫助我們了解我們的算法的良好的屬性。 基本算法基于該圖G* 如果我們有一個圖G（V，E，w） 和最短路徑樹T，我們可以得到一個權(quán)重變化圖G*。定義2.2：若G=（V，E，w）則G*=（V，E，w*）對每一條邊eE， i j則權(quán)值變化為w*(e)=w(e) + D(i)-D(j) ( 在最小生成樹的基礎(chǔ)上)根據(jù)II.2的定義，我們可以繪制權(quán)重變化圖G* 在圖2中，其對應(yīng)于圖1中的圖。 兩個圖都具有相同的最短路徑樹（圖1和圖2中用粗線表示SPT）。 在我們的基本算法中的動態(tài)算法中，所有的計算都基于圖G* ，圖G*臨時邊權(quán)值和SPT，直到我們找到最終的SPT。如果我們有一個節(jié)點集Q，我們定義一些與Q有一些關(guān)系的邊集。定義II.3，如果Q是G.*的節(jié)點集合，設(shè)Source_partQ 是G*的邊集合，即Source_partQ = e|S(e)Q ,E(e) Q,eE定義II.4如果Q是G.*的節(jié)點集合，設(shè)End_partQ 是G*的邊集合，即End_partQ = e|E(e)Q ,S(e) Q,eE當一個邊e, i j的權(quán)值增加或減少，我們使用w來表示新的權(quán)值，因為這些改變，如果從S(G)到節(jié)點j的最短路徑（或父節(jié)點）不同于最初的D(j)(或P(j)，當算法結(jié)束時，我們應(yīng)該有節(jié)點j的新值。三算法A. 基本算法我們首先提出一種基本算法，當一個邊緣的權(quán)重發(fā)生變化時，可以將SPT從源節(jié)點S（G）重新計算到圖中的每個其他節(jié)點。 該算法處理權(quán)重變化圖G *。 假設(shè)在原始圖G我們有一個靜態(tài)的最短路徑樹T，可以通過使用靜態(tài)Dijkstra算法導出。 在這棵樹T中，對于每個節(jié)點v，我們從源節(jié)點S（G）獲得其父節(jié)點P（v）及其距離D（v）的信息。 在此算法中，一旦節(jié)點發(fā)生變化，T和P就會更新。 當算法結(jié)束時，由于一個邊緣的變化，我們得到一個新的T和P用于新的SPT。在給出基本算法之前，我們給出一個函數(shù)SELECT MIN（B，T），如圖3所示.B是圖G *的邊集。 T是圖G的最短路徑樹。我們嘗試從邊集B找到最小權(quán)重邊。如果有幾個權(quán)重相同的邊，我們嘗試找到一個最靠近源節(jié)點S（G ）樹T.SELECT MIN（B，T）IFB中包含兩條或兩條以上相等的最小權(quán)值選擇其中最小權(quán)值所在邊e1，它的終節(jié)點或者起點更接近于root節(jié)點從B中移除e1并返回e1Return e1Else 從B中移除e1并返回e1Return e1END基本算法包括兩部分。 一個部分是當一個邊權(quán)值變大時的情況。 另一部分是當一個邊變小時的情況。 在我們執(zhí)行基本算法之前，我們應(yīng)該具有定義II.2的舊的SPT和權(quán)重交換圖G *?；舅惴ǎ篠tep1：等待一條邊e：ii j 的權(quán)值w*(e)變化成w*(e)1. 若w*(e) w*(e)且eT則d= w*(e)- w*(e)進入step2 /case1 一條邊權(quán)值變大/2. Else if w*(e)0 則d= w*(e)進入step3 /case2 一條邊權(quán)值變小/3 else 進入step1Step2：1 初始化 Q des(j) Q是節(jié)點集合，des(j)是j的子節(jié)點的集合 B=e|eEnd_partQ 并且w*(e)d /從j或j的子節(jié)點找到邊，使邊的終節(jié)點為Q而且初節(jié)點不在Q中且w*(e)d2 若B是空集/*改變剩下節(jié)點*/ 3 （else）否則， /* */更新在Q1中節(jié)點的邊權(quán)值Q=Q-Q1，w(e1)=0 /*更新Q*/通過添加權(quán)重小于d的Source_part Q1的邊緣，并刪除屬于End_part Q1的邊來更新B。去到2Step 3：/*當一條邊的權(quán)值減少*/1.初始化/*節(jié)點j的后代更新一次*/ 通過將屬于Source_part Q1的邊加入權(quán)重低于0來更新B1，通過刪除屬于End_part Q1的邊來更新B， 為了使這個算法更容易理解，我們簡要介紹一下它的執(zhí)行方式。 在步驟1中，當一個邊緣的權(quán)重發(fā)生變化時，基本算法決定是否需要更改舊的SPT。 只有在情況1和情況2中，我們需要分別去步驟2和步驟3獲得一個新的樹。 否則，我們?nèi)匀坏却硪粋€權(quán)值變化，同時保持相同的最短路徑樹。步驟2處理一個邊緣的重量增加。 首先，我們初始化一個節(jié)點集Q和一個邊集B.所有可能與S（G）（或新的父節(jié)點）有最短距離的節(jié)點都是Q.B中的所有邊都是可以使最短的 Q節(jié)點距離增加較少。 此時，我們只考慮權(quán)值小于d的邊。 只有從Q中這些邊緣的節(jié)點可以實現(xiàn)比原來的一個加d的距離，這只是跟隨舊的SPT。 對于每個更新步驟，我們從B中選擇最小權(quán)重邊e1，這可以為Q1中的節(jié)點帶來最小的增加。 然后，通過添加w *（e1）來更新這些節(jié)點的新距離。 此外，我們需要改變圖G中連接節(jié)點Q1的重量。 在一個更新步驟結(jié)束時，應(yīng)相應(yīng)更新B和Q。 這個過程不會結(jié)束，直到B =。步驟3處理一個邊緣減少的權(quán)重。 在初始化期間，des（j）中的所有節(jié)點都被更新一次。 B中的邊是可能使節(jié)點des（j）之外的節(jié)點的最短距離更小的潛在元素。 因為我們不知道確定節(jié)點需要更新，所以節(jié)點具有與舊SPT不同的最短路徑被包括在節(jié)點集Q中。首先，我們更新與子樹des（j）相鄰的節(jié)點。 我們稱之為這些節(jié)點Q1。 來自節(jié)點集Q1的所有邊緣形成邊緣集合B1。 我們通過向它們添加w *（e1）-d來更新這些邊。 所有這些負值都在邊集合B1中。 在我們執(zhí)行B中的所有邊之后，我們將B1移動到B，到B1和0到d。 如果B =，更新過程結(jié)束。 否則，我們從更新節(jié)點更新從子樹 des（j）到更多節(jié)點的工作。 更新過程類似于步驟2。B. 多重鏈路權(quán)重變化當一次發(fā)生多個鏈路權(quán)重變化時，最簡單的方法是為每個改變的權(quán)重順序運行算法。 然而，計算開銷的優(yōu)化可以通過將變化組合成兩組來實現(xiàn)：權(quán)重增加邊緣和權(quán)重減少邊緣。 對于算法中的步驟2和步驟3的每個權(quán)重變化，顯然需要單獨的初始化。 首先，我們初始化所有的重量增量。 集Q包括所有需要改變距離（或父母）的節(jié)點。 然后更新循環(huán)體與一個重量增加相同，并產(chǎn)生一個臨時圖G * 1。 其次，對于所有的權(quán)重減量，我們更新圖G * 1。 如前所述，在步驟3的初始化中，我們更新每個權(quán)重減少邊緣的所有后代，并保持一個邊集合B.步驟3中的算法的其余部分類似地執(zhí)行。C. 第二種算法當我們使用基本算法來計算新的SPT時，我們將顯示仍然存在冗余。 例如，如果邊緣（C，G）從0減小到-5，在圖G中為7到2，則在計算基本算法時邊緣（G，D）的權(quán)重會改變兩倍。 一個是更新節(jié)點G及其連接邊，將其重量更改為-1。 另一個是更新節(jié)點D及其連接邊緣，將其權(quán)重更改為0，以獲得最終結(jié)果。 改變邊緣權(quán)重兩次的冗余是由改