OSP中最短路徑算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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