最短路徑樹構(gòu)建的最小動(dòng)態(tài)更新.docx

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