1、OSPF中的最短路徑算法測試中心陳旭盛現(xiàn)實生活中的網(wǎng)絡(luò)拓?fù)?，可以抽象成由?jié)點（路由器）和邊（路由器之間的鏈路）構(gòu)成 的有向連通圖，鏈路的代價可以抽象成邊的權(quán)函數(shù)。之所以稱圖為有向圖，是因為同一條鏈路（邊）不同方向的權(quán)值可能不一樣。我們知道，對于有向連通圖，以任意一個節(jié)點為起點，利用最短路徑算法可以計算出到其他節(jié)點的最短路徑。 那么，對于能抽象成有向連通圖的網(wǎng)絡(luò)拓?fù)鋪碚f，也可以利用最短路徑算法先計算出以任意一臺路由器為起點，到達(dá)其他路由器的最短路徑，然后根據(jù)各路由器的網(wǎng)絡(luò)連接情況可以得到到各個網(wǎng)絡(luò)的路由路徑。OSPF中用到的Dijkstra算法和RIP中用到的距離向量算法一樣，都是相當(dāng)經(jīng)典的最短

2、路 徑算法。本文將對 Dijkstra算法進行系統(tǒng)的描述，并給出一個簡潔的證明。1 Dijkstra 算法介紹在數(shù)學(xué)上，以某個節(jié)點為起點， 計算到其他節(jié)點的最短路徑的算法，稱為“單源最短路 徑” 算法。求“單源最短路徑”的問題在數(shù)學(xué)上可以精確描述如下：“單源最短路徑”問題：已知一個有n個節(jié)點（V0.n）構(gòu)成的有向連通圖G= （V, E）,以及圖中邊的權(quán)函數(shù) C （E）,其中V代表節(jié)點集合，E表示所有邊的集合，并假設(shè)所有權(quán)非負(fù)， 求由G中指定節(jié)點V0到其他各個節(jié)點的最短路徑。Dijkstra算法是很經(jīng)典的求解上述問題的算法，其基本想法是設(shè)計一種最短路徑樹的構(gòu) 造方法，按非降次序逐條構(gòu)造從 V0到

3、各個節(jié)點的最短路徑，第一步找到和V0相距最短的節(jié)點以及到這個節(jié)點的路徑，第二步找到和V0相距次短的節(jié)點以及到這個節(jié)點的路徑，如此反復(fù)，最后找到V0到所有節(jié)點的最短路徑，構(gòu)造出整棵最短路徑樹。對上述構(gòu)造方法的一個直觀考慮是：和V0相距最短的節(jié)點應(yīng)該在和 V0直接相鄰的節(jié)點中，和V0相距次短的節(jié)點要么在和 V0直接相鄰的節(jié)點中，要么在和這些相鄰節(jié)點相鄰的節(jié) 點中，如此逐步擴散考慮，應(yīng)該就可以找到和V0相距最短、次短、.第n短的節(jié)點以及對應(yīng)的路徑，而且因為是連通圖， 最后肯定所有節(jié)點都能全部考慮到，也就能完成整棵最短路徑樹的構(gòu)造。事實上，上述直觀考慮是對的，Dijkstra算法是對上述過程的一個提煉

4、和優(yōu)化：和V0相/ 8V0直接相距最短的節(jié)點是和 V0直接相連的節(jié)點沒錯；相距次短的節(jié)點范圍可以縮小為，和鄰的節(jié)點，加上跟剛選中的最短節(jié)點直接相鄰的節(jié)點；相距第三短的節(jié)點的范圍可以類推得到，即在上一步考察的節(jié)點的基礎(chǔ)上，加上和次短節(jié)點直接相鄰的節(jié)點。如此逐步構(gòu)造，可 以按非降次序找到到所有節(jié)點的最短路徑。為了從數(shù)學(xué)上精確描述上述構(gòu)造過程，引入了集合的概念對節(jié)點和路徑進行分類。我們把節(jié)點分成兩個集合：A:已經(jīng)選入最短路徑樹的節(jié)點的集合。B:剩余的其他節(jié)點的集合。對于路徑，我們分成三個集合：I:已經(jīng)選入最短路徑樹的路徑的集合:候選路徑集合：下一條加入最短路徑樹的路徑將從這個集合中選入。:剩余的其他

5、路徑的集合（被廢棄的路徑或者還未考慮的路徑）。為了更好的理解，有必要對這里的路徑定義進行一下強調(diào)：路徑是指以V0為起點，其他節(jié)點為終點的由一條或多條邊組成的一個有序集。邊，可以理解為路徑中的一段，只有到和V0直接相鄰的節(jié)點的路徑才直接對應(yīng)一條邊。從V0到所有節(jié)點，都可能存在一條或多條路徑，非最短路徑在計算過程中將會被廢棄，放入集合III。從前面的描述中可以明顯看出，Dijkstra算法是一個遞歸構(gòu)造過程，因為任何遞歸都必須有明確的初始狀態(tài)，所以我們有必要先得到上述Dijkstra算法中定義的集合的初始值：以V0為起點計算最短路徑的話，初始狀態(tài)時顯然有且只有V0在集合A中，所以集合A的初始值為V

6、0。集合B的初始值為剩余節(jié)點。前面提到過，下一個加入集合 A的節(jié)點，一定是和 V0直接有邊相連的節(jié)點，因此， 加入最短路徑樹的第一條路徑也必然在這些和 V0直接相連的邊所代表的路徑中產(chǎn)生，所以集合II的初始值就是和V0直接相連的邊構(gòu)成的路徑。另外，初始狀態(tài)最短路徑樹為空，所以集合I的初始值為空。集合I、II明確了的話，集合III自然明確。下面我們開始展開遞歸構(gòu)造最短路徑樹的過程：第一步：從集合II中選擇一條最短的路徑，放入最短路徑樹，相應(yīng)的，這條路徑的終點對應(yīng)的節(jié)點（這里記為 X）應(yīng)該從集合B移入集合Ao第二步：考察所有從X出發(fā)的邊的終點，考慮其中不屬于集合A的節(jié)點，這里記為Y,計算從V0出發(fā)

7、經(jīng)X到達(dá)丫的路徑值，計算方法為：最短路徑樹中V0到節(jié)點X的2 / 8路徑值加上（X, Y）這條邊的值。為了描述方便，我們把從V0出發(fā)經(jīng)X到達(dá)Y的路徑記為（V0X） Y。接著考察集合II中的候選路徑，如果其中沒有到節(jié)點Y的路徑，則直接把路徑（V0X）Y作為候選路徑加入集合II;如果集合II中已經(jīng)有到節(jié)點Y 的路徑，則進行比較，如果這條路徑值小于或等于路徑（V0X）Y的路徑值，那么路徑（V0X）Y作為被廢棄的路徑放入集合 III,否則原集合II中到Y(jié)的路徑被廢棄放入 集合II , （ V0X ） Y作為候選路徑放入集合II。對于Y節(jié)點有多個的情況，按第二步 的方法一個一個的計算和比較。重復(fù)第一步和

8、第二步，直到集合II和集合B為空。第二步事實上是對候選路徑的一個重新計算過程，因為在集合A中引入了新的節(jié)點后，考察的范圍變大了，很可能在原來節(jié)點范圍內(nèi)認(rèn)為到某個節(jié)點的最短路徑已經(jīng)不再是最短路 徑了，這時候，需要根據(jù)第二步的方法進行調(diào)整。為了讓大家更好的理解這一構(gòu)造過程，這里舉一個較為典型的例子，如下是一個有向圖:計算這個有向連通圖的最短路徑樹的過程如下:候選路徑 集合路徑 長度最短路徑 樹中的節(jié) 點（集合A）最短路徑樹說明V0V1V0V2V0V4501045V0Null在初始狀態(tài)，最矩路徑樹中只有節(jié)點 V0, 候選路彳5就是V0直接相連的邊代表的路 徑。V0V1V0V4V0V2V3504535

9、V0、V2V0V0V0V2V0V2在所有候選路徑中最短， 所以放入 最短路徑樹，V2放入集合Ao考察所有 以剛放入集合A的節(jié)點V2為起點的邊的 終點，對其中不在集合 A中的節(jié)點，這 里只后節(jié)點V3,計算從V0出發(fā)經(jīng)節(jié)點 V2,到達(dá) V3的路徑V0V2V3的值，因 為候選路徑中沒有到 V3的路徑，所以 V0V2V3路徑直接放入候選路徑集合。V0VV0V4V0V2V3V1V0V2V3V450454555V0、 V2、V3V0V0V0V2V0V2V3V0V2V3在所有候選路徑中最矩， 所以放 入最短路徑樹，V3放入集合Ao考察所 有以剛放入集合A的節(jié)點V3為起點的邊 的終點，對其中/、在集合A中的節(jié)

10、點，這里是節(jié)點V1 , V4 ,計算從V0出發(fā)經(jīng) 節(jié)點V3 ,到達(dá)這兩個節(jié)點的路徑 V0V2V3V1 和V0V2V3V4 的路徑值,并 和候選路徑中已有的到達(dá) V1、V4的路徑 值進行比較：V0V2V3V1小于V0V1 ,所 以V0V1從候選路徑中刪除，V0V2V3V1 放入候選路徑集合；V0V2V3V4比V0V4 大，所以 V0V4在候選路徑中保留， V0V2V3V4 路徑廢棄不用。V0V2V3V145V0、 V2、V3、V4V0V0V0V2V0V2V3V0V4V0V4和V0V2V3V1 路徑值相等，任意 選才i V0V4放入最短路徑樹，V4放入集 合Ao考察所有以剛放入集合 A的節(jié)點V4為

11、起點的邊的終點，其中/、在集合A中的節(jié)點沒有（雖然有邊V4V3，但V3已經(jīng)在集合 A中了），所以不進行選擇 和計算。V0、 V2、V3、 V4、V1V0V0V0V2V0V2V3V0V4V0V2V3V1候選路徑V0V2V3V1放入最短路徑樹， 這時候選路徑集合為空，并且所用節(jié)點已 經(jīng)放入了集合Ao計算結(jié)束。2 Dijkstra算法的證明XDijkstra算法進行證明，實際上就是要證明其構(gòu)造過程構(gòu)造的樹一定是最短路徑樹。為了給出證明，我們先分析一下構(gòu)造過程。分析構(gòu)造過程的第二步，可以得出結(jié)論一。結(jié)論一：對一個還沒有選入集合 A的節(jié)點Y,其候選路徑是所有從 V0出發(fā)，中途只經(jīng)過 集合A中的節(jié)點到達(dá)Y

12、的路徑中路徑值最小的。這個結(jié)論根據(jù)第二步候選路徑的構(gòu)造過程，很容易得出：因為在第一次構(gòu)造到Y(jié)的候選路徑時，從V0出發(fā)經(jīng)剛加入集合 A的節(jié)點到Y(jié)的路徑，是被直接放入候選路徑集合中的，這 說明第一次構(gòu)造的到 Y的候選路徑滿足條件“從 V0出發(fā)，中途只經(jīng)過集合 A中的節(jié)點”。另 外，集合A中每加入一個新節(jié)點，都會考慮從V0出發(fā)經(jīng)過這個新節(jié)點到達(dá) Y的路徑，并和原候選路徑比較，選擇兩者中較小的那個，這種過程一直持續(xù)到Y(jié)被選入集合A中為止。這個過程顯然保證了 Y的候選路徑一直保持了特性“從 V0出發(fā)，中途只經(jīng)過集合 A中的節(jié)點”， 而且因為遍歷了所有 A中的節(jié)點，所以是所有這種特性路徑中最短的。有了結(jié)論

13、一，證明Dijkstra算法可以弱化為證明 結(jié)論二。結(jié)論二：假設(shè)構(gòu)造過程中下一步將選擇的是節(jié)點Y,那么這時到達(dá)Y的最短路徑必然是從V0出發(fā)，中途只經(jīng)過集合 A中的節(jié)點到達(dá)Y的路徑。如果“結(jié)論二”成立的話，結(jié)合“結(jié)論一”，說明Y的最短路徑和候選路徑具有相同的 屬性“從V0出發(fā)，只經(jīng)過集合A中的節(jié)點”，而“結(jié)論一”中明確說明，候選路徑是這種屬 性的路徑中的最小者，所以對于下一步即將選入集合A中的節(jié)點Y,其最短路徑值就是候選路徑，也即證明了算法中構(gòu)造最短路徑樹過程的正確性。下面我們證明“結(jié)論二”。證明很簡單，使用反證法：假設(shè)到達(dá)Y的最短路徑中途不只經(jīng)過集合 A,那么必然經(jīng)過一個不在集合A中的節(jié)點W,

14、于是這條路徑中肯定包含一條從 V0到W的路徑，這條路徑顯然 比從V0出發(fā)經(jīng)過W到Y(jié)的路徑更短，而Y是下一步要放入集合 A中的節(jié)點，根據(jù)我們按非降 次序構(gòu)造最短路徑樹的過程（第一條最短，第二條次短.），從V0出發(fā)到W的這條路徑應(yīng)該已經(jīng)在最短路徑樹中了，也即節(jié)點W應(yīng)該已經(jīng)在集合A中，矛盾，得證。3 OSPF協(xié)議中對 Dijkstra 算法的使用從理論上來說，只要描述清楚了節(jié)點之間的連接和邊的屬性，就描述清楚了有向圖， 也就可以使用Dijkstra算法計算出最短路徑樹。對于使用基于Dijkstra算法的路由協(xié)議來說，如果能描述清楚整個網(wǎng)絡(luò)拓?fù)洌▽?yīng)有向 圖），并讓區(qū)域內(nèi)的每臺路由器都清楚的知道整個區(qū)

15、域的網(wǎng)絡(luò)拓?fù)?，則每臺路由器都可以獨立的計算出最短路徑樹。從這個意義上說，對于一個使用Dijkstra算法的路由協(xié)議來說，需要要解決以下問題：網(wǎng)絡(luò)拓?fù)涞拿枋鰡栴}。網(wǎng)絡(luò)拓?fù)涿枋鲂畔⒌膫鞑栴}。效率問題：路由協(xié)議的目的是在耗費最少資源的情況下，在最短時間內(nèi)動態(tài)發(fā)現(xiàn)到其他網(wǎng)段的最優(yōu)路徑。另外，還需要考慮路由協(xié)議的網(wǎng)絡(luò)應(yīng)用位置（ IGP或者EGP,適合于多大網(wǎng)絡(luò) 等）以及和其他路由協(xié)議的互操作等問題。以上幾個問題有一定的關(guān)聯(lián)性，互相影響。例如，網(wǎng)絡(luò)拓?fù)涿枋龅膬?yōu)化可以減少描述信息，從而減輕傳播和計算過程的消耗，提高了效率。本文的著力點是Dijkstra算法及其在OSPF中的應(yīng)用，所以這里只說明與之相關(guān)的網(wǎng)

16、絡(luò)拓 撲的描述和最短路徑計算兩個內(nèi)容，網(wǎng)絡(luò)拓?fù)涞拿枋鲆仓簧婕暗膸最惢綥SA。OSPF對網(wǎng)絡(luò)拓?fù)涞拿枋鯫SPF中使用鏈路狀態(tài)通告（LSA）來描述網(wǎng)絡(luò)拓?fù)洌从邢驁D）。OSPF中，Router LSA被用來描述路由器（節(jié)點）之間的連接和鏈路（邊）的屬性，具 備了理論上計算最短路徑的可能。但是僅僅是理論而已，從實踐的角度，針對特殊的網(wǎng)絡(luò)情況和應(yīng)用場景，需要作一些優(yōu)化工作。先考慮一個有n節(jié)點的廣播網(wǎng)，如果使用Router LSA來描述的話，需要描述n個節(jié)點兩 兩相連的n*（n-1）/2條鏈路，而且n個節(jié)點間需要建立建立n*（n-1）/2個鄰接關(guān)系，描述信息需 要在這些建立了鄰接關(guān)系的節(jié)點間傳播。如果

17、換一種思路，我們把這個廣播網(wǎng)虛構(gòu)成一個偽節(jié)點，其他n個節(jié)點均和偽節(jié)點相連，那么就只要描述n條鏈路，n個節(jié)點只需要和偽節(jié)點建立總共n個鄰接關(guān)系即可，能大大減少了信息描述量和信息傳播量。依據(jù)這種想法，OSPF中針對廣播網(wǎng)的描述進行了優(yōu)化，使用指定路由器DR來承擔(dān)這個偽節(jié)點的角色，并使用6 / 8Network LSA來描述廣播網(wǎng)內(nèi)DR和各個路由器的連接情況。對于NBMA網(wǎng)絡(luò)的描述，處理方式和廣播網(wǎng)基本相同。其次，OSPF的設(shè)計目標(biāo)是為一個較大的內(nèi)部網(wǎng)絡(luò)提供動態(tài)路由能力。如果內(nèi)部網(wǎng)絡(luò)較 大的話，需要描述的鏈路會很多，存儲、傳播和計算這些鏈路信息將耗費大量內(nèi)存和CPU資源。OSPF解決這個問題的辦法是

18、把較大的網(wǎng)絡(luò)劃分成多個Area,每個Area內(nèi)部使用RouterLSA和Network LSA把Area內(nèi)部網(wǎng)絡(luò)拓?fù)涿枋銮宄?，并?jù)此使用Dijkstra算法計算出本Area內(nèi)的最短路徑樹和路由。至于 Area外的網(wǎng)絡(luò)拓?fù)洌瑓^(qū)域邊界路由器ABR并不把相鄰Area的Router LSA和Network LSA傳入本Area,而是把自己在相鄰 Area范圍內(nèi)計算得到的該 Area內(nèi) 各個網(wǎng)段的路由進行匯總，把這些網(wǎng)段當(dāng)做直接連接在自己上面，并生成 Network Summary LSA來對這些網(wǎng)段進行描述，傳入本 Area。這樣，對于一個有n個網(wǎng)段和多臺路由器的相鄰 Area, ABR只需要生成n條

19、網(wǎng)絡(luò)描述信息并傳入本 Area即可，大大減少了進入本 Area的鏈路 描述信息，減少了存儲、傳播和計算消耗。需要注意的是，劃分Area的做法導(dǎo)致了 Area內(nèi)部路由器中的鏈路狀態(tài)數(shù)據(jù)庫描述的Area外部分并不是真實的網(wǎng)絡(luò)拓?fù)洌瑥亩嬎銜r可能出現(xiàn)環(huán)路，為了避免環(huán)路出現(xiàn)，要求所有的Area之間的相連必須經(jīng)過 Backbone區(qū)域即Area 0。另外，OSPF被設(shè)計為一個IGP,所以除了處理本自治系統(tǒng)內(nèi)的路由外，還需要處理自治系統(tǒng)外的路由，這類路由在 ASBR處引入，可以看做是直接連接在 ASBR上，OSPF弓|入AS External LSA來描述這類自治系統(tǒng)外路由。另外，因為 AS Extern

20、al LSA在傳入其他 Area時并 不在ABR上重新生成，所以從計算的角度看， 其他Area還必須知道自治系統(tǒng)外路由從哪個節(jié) 點引入，所以需要引入 ASBR Summary LSA來描述外部路由從哪個節(jié)點引入，ASBRSummary LSA在ABR上生成，從其他 Area看，可以認(rèn)為于 ASBR直接連在ABR上，自治系統(tǒng) 外部路由對應(yīng)的網(wǎng)段又直接連在 ASBR上。3.2 OSPF中最短路徑的計算下面簡單介紹一下 OSPF的最短路徑計算過程，具體的細(xì)節(jié)處理請參考RFC2328 :首先，計算Area內(nèi)部路由。因為 Router LSA和Network LSA精確的描述出了整個 Area內(nèi) 部的網(wǎng)

21、絡(luò)拓?fù)?，所以根?jù) Dijkstra算法，可以計算出到各個節(jié)點（路由器）的最短路徑。然 后根據(jù)Router LSA描述的與路由器相連的網(wǎng)段情況，就得到了到各個網(wǎng)段的最短路徑。注意，計算過程中，如果有多條代價相同的最短路徑，都保留。其次，計算跨Area的路由。因為從一個 Area內(nèi)部看，相鄰Area的路由對應(yīng)的網(wǎng)段就好像 是直接連在ABR上，而到ABR的最短路徑已經(jīng)在上一步算出，所以直接檢查Nerwork7 / 8Summary LSA ,就可以很容易得到這些網(wǎng)段的最短路徑值。另外，ASBR也被看做是直接連接在ABR上，所以到ASBR的最短路徑也可在這一步計算出來。注意：在這一步，如果發(fā)起 計算的路由器是 ABR ,那么很自然，應(yīng)該只考慮骨干區(qū)域的Network Summary LSA ;但是對于啟用了 Virtual Link的拓?fù)鋪碚f，跨Area的路由只是邏輯上通過骨干區(qū)域，而實際是通過 Transit Area到達(dá)的，因為邏輯鏈路可能并不