OSP中最短路徑算法

OSPF中的最短路徑算測試中心陳盛現(xiàn)實(shí)生活中的網(wǎng)絡(luò)拓?fù)?，可以抽象成由?jié)點(diǎn)（路由器）和邊（路由器之間的鏈路）構(gòu)成的有向連通圖鏈路的代價(jià)可以象成邊的權(quán)函數(shù)之所以稱圖為有向圖是為同一條鏈路（邊）不同方向的權(quán)值可能不一樣。我們知道對有向連通圖以任意一個(gè)節(jié)點(diǎn)為起點(diǎn)利用最短路徑算法可以計(jì)算出到其他節(jié)點(diǎn)的最短路徑那么對能抽象成有向連通圖的網(wǎng)絡(luò)拓?fù)鋪碚f可利用最短路徑算法先計(jì)算出以任意一臺路由器為起點(diǎn)達(dá)他路由器的最短路徑后據(jù)各路由器的網(wǎng)絡(luò)連接情況可以得到到各個(gè)網(wǎng)絡(luò)的路由路徑。OSPF中用到的ijkstra法和IP用到的距離向量算法一樣，都是相當(dāng)經(jīng)典的最短路徑算法。本文將ijkstra算法進(jìn)行系統(tǒng)的描述，并給出一個(gè)簡潔的證明。1Dijkstra算法介紹在數(shù)學(xué)上以個(gè)節(jié)點(diǎn)為起點(diǎn)計(jì)算到其他節(jié)點(diǎn)的最短路徑的算法，稱為“單源最短路徑”算法求“單源最短路徑”的問題在數(shù)學(xué)上可以精確描述如下：“源短徑問題已知一個(gè)有個(gè)節(jié)點(diǎn)(構(gòu)的向連通圖G＝（V，E），以及圖中邊的權(quán)函數(shù)C其中代表節(jié)點(diǎn)集合E表示所有邊的集合并設(shè)所有權(quán)非負(fù)，求由G中指定節(jié)V到其他各個(gè)節(jié)點(diǎn)最短路徑。算是很經(jīng)典的求解上述問題的算法，其基本想法是設(shè)計(jì)一種最短路徑樹的構(gòu)造方法，按非降次序逐條構(gòu)造V到各個(gè)節(jié)點(diǎn)的最短路徑，第一步找到V0距最短的節(jié)點(diǎn)以及到這個(gè)節(jié)點(diǎn)的路徑，第二步找到V相距次短的節(jié)點(diǎn)以及到這個(gè)節(jié)點(diǎn)的路徑，如此反復(fù)，最后找到V0到所有節(jié)點(diǎn)的最短路徑，構(gòu)造出整棵最短路樹。對上述構(gòu)造方法的一個(gè)直觀考慮是：V0相距最短的節(jié)點(diǎn)應(yīng)該在V直接相鄰的節(jié)點(diǎn)中，和V相距次短的節(jié)點(diǎn)要么在和V0接相鄰的節(jié)點(diǎn)中，要么在和這些相節(jié)點(diǎn)相鄰的節(jié)點(diǎn)中，如此逐步擴(kuò)散考慮，應(yīng)該就可以找到V0相距最短、次短…第n短的節(jié)點(diǎn)以及對應(yīng)的路徑而因?yàn)槭沁B通圖最后肯定所有節(jié)點(diǎn)都能全部考慮到也就能完成整棵最短路徑樹的構(gòu)造。事實(shí)上，上述直觀考慮是對的算是對上述過程的一個(gè)提煉和優(yōu)化：V0/

距最短的節(jié)點(diǎn)是V0直相連的節(jié)點(diǎn)沒錯(cuò)相距次短的節(jié)點(diǎn)范圍可以縮小為，V0直接相鄰的節(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)造過程，引入了集合的概念對節(jié)點(diǎn)和路徑進(jìn)行分類。我們把節(jié)點(diǎn)分成兩個(gè)集合：A：經(jīng)選入最短路徑樹的節(jié)點(diǎn)的集合。：余的其他節(jié)點(diǎn)的集合。對于路徑，我們分成三個(gè)集合：I：經(jīng)選入最短路徑樹的路徑的集合II：選路徑集合：下一條加入最短路徑樹的路徑將從這個(gè)合中選入。III：余的其他路徑的集合（被廢棄的路徑或者還未考慮的路徑）。為了更好的理解，有必要對這里的路徑定義進(jìn)行一下強(qiáng)調(diào)：路徑是指V0為起點(diǎn)，其他節(jié)點(diǎn)為終點(diǎn)的由一條或多條邊組成的一個(gè)有序集可理解為路徑中的一段只有到和V0直接相鄰的節(jié)點(diǎn)的路徑才直接對應(yīng)一條邊。到所有節(jié)點(diǎn)，都可能存在一條或多條路徑，非最短路徑在計(jì)算過程中將會被廢棄，放入集III。從前面的描述中可以明顯看出算是一個(gè)遞歸構(gòu)造過程，因?yàn)槿魏芜f歸都必須有明確的初始狀態(tài)，所以我們有必要先得到上算中定義的集合的初始值：

以V0起點(diǎn)計(jì)算最短路徑的話，初始狀態(tài)時(shí)顯然有且只V0在集合A中所以集合A的初始值V。B的初始值為剩余節(jié)點(diǎn)。前面提到過，下一個(gè)加入集合A的點(diǎn)，一定是V0接有邊相連的節(jié)點(diǎn)，因此，加入最短路徑樹的第一條路徑也必然在這些V0接相連的邊所代表的路徑中產(chǎn)生，所以集II的初始值就是V直接相連的邊構(gòu)成的路徑。另外始狀態(tài)最短路徑樹為空，所以集I的初始值為。集III確了的話，集III自明確。下面我們開始展開遞歸構(gòu)造最短路徑樹的過程：

第一步：從集合I中選擇一條最短路徑，放入最短路徑樹，相應(yīng)的，這條路徑的終點(diǎn)對應(yīng)的節(jié)點(diǎn)（這里記X）應(yīng)該從集合移集A。第二步：考察所有從出發(fā)的邊的終點(diǎn)，考慮其中不屬于集A的節(jié)點(diǎn)，這里記為Y計(jì)算V出經(jīng)到達(dá)Y的路徑值，計(jì)算方法為：最短路徑樹V0到節(jié)X/

路徑值加上（X，Y）這條邊的值。為描述方便，我們把V0發(fā)X達(dá)Y路徑記為（V0XY接著考察集II的候選路徑，如果其中沒有到節(jié)Y路徑，則直接把路徑作為候選路徑加入集II；如果集合II中已經(jīng)有到節(jié)Y的路徑，則進(jìn)行比較，如果這條路徑值小于或等于路徑(V0X)Y的徑值，那么路徑作為被廢棄的路放入集III，否則集合II中Y的路徑被廢放入集合I，V0X）Y作候選路徑放入集I。對于Y點(diǎn)有多個(gè)的情況，按第二步的方法一個(gè)一個(gè)的計(jì)算和比較。重復(fù)第一步和第二步，直到集I和集合為空。第二步事實(shí)上是對候選路徑的一個(gè)重新計(jì)算過程，因?yàn)樵诩疉中引入了新的節(jié)點(diǎn)后，考察的范圍變大了能原節(jié)點(diǎn)范圍內(nèi)認(rèn)為到某個(gè)節(jié)點(diǎn)的最短路徑已經(jīng)不再是最短路徑了，這時(shí)候，需要根據(jù)第二步的方法進(jìn)行調(diào)整。為了讓大家更好的理解這一構(gòu)造過程舉一個(gè)較為典型的例子是一個(gè)有向圖：V0

V1

V4

V2

V3計(jì)算這個(gè)有向連通圖的最短路徑樹的過程如下：候選路徑集合

路徑長度

最短路徑樹中的節(jié)

最短路徑樹

說明點(diǎn)(集合A)/

V0V1V0V2V0V4

501045

V0Null

在初始狀態(tài)路樹中只有節(jié)點(diǎn)V0，候選路徑就是V0直相的邊代表的路徑。V0V1V0V4V0V2V3

504535

V0、V2V0V0V0V2

V0V2在所有候選路徑中最短以入最短路徑樹V2放入集合A?？疾焖幸詣偡湃爰螦的點(diǎn)V2為點(diǎn)的邊的終點(diǎn)，對其中不在集合A中的節(jié)點(diǎn)，這里只有節(jié)點(diǎn)V3，計(jì)算從V0出發(fā)經(jīng)節(jié)點(diǎn)V2到達(dá)V3的徑V0V2V3的，因?yàn)楹蜻x路徑中沒有到的路徑，所以V0V2V3路直接放入候選路徑集合。V0V1V0V4V0V2V3V1V0V2V3V4

50454555

V0、V2、V3

V0V0V0V2V0V2V3

V0V2V3在有候選路徑中最短以放入最短路徑樹，放集合?？疾焖幸詣偡湃爰螦的點(diǎn)V3為點(diǎn)的邊的終點(diǎn)，對其中不在集合中節(jié)點(diǎn)，V0V2V3V145、V2、V3、V4V0、V2、V3、V4、V1

V0V0V0V2V0V2V3V0V4V0V0V0V2V0V2V3V0V4V0V2V3V1

這里是節(jié)點(diǎn)V1V4，計(jì)算從V0發(fā)經(jīng)節(jié)點(diǎn)到達(dá)這兩個(gè)節(jié)點(diǎn)的路徑V0V2V3V1和V0V2V3V4的徑值，并和候選路徑中已有的到達(dá)V1的徑值進(jìn)行比較V0V2V3V1小于V0V1所以從選路徑中刪除V0V2V3V1放入候選路徑集合V0V2V3V4比V0V4大，所以V0V4在候選路徑中保留，V0V2V3V4路廢棄不用。V0V4和V0V2V3V1路徑值相等，任意選擇放最短路徑樹V4放集合?？疾焖幸詣偡湃爰螦的點(diǎn)V4為點(diǎn)的邊的終點(diǎn)，其中不在合A中的節(jié)點(diǎn)沒有（雖然有邊，但V3已經(jīng)在集合A中），所以不行選擇和計(jì)算。候選路徑放最短路徑樹，這時(shí)候選路徑集合為空所節(jié)點(diǎn)已經(jīng)放入了集合A計(jì)算結(jié)束。/

2Dijkstra算法的證明對算進(jìn)行證明，實(shí)際上就是要證明其構(gòu)造過程構(gòu)造的樹一定是最短路徑樹。為了給出證明，我們先分析一下構(gòu)造過程。分析構(gòu)造過程的第二步，可以得結(jié)論。結(jié)一對一還有入合A節(jié)Y，候路徑所從V出，途經(jīng)集A中節(jié)到Y(jié)的徑路值小的這個(gè)結(jié)論根據(jù)第二步候選路徑的構(gòu)造過程，很容易得出：因?yàn)樵诘谝淮螛?gòu)造的候選路徑時(shí)，從V出經(jīng)剛加入集A節(jié)點(diǎn)Y的路徑，是被直接放入候選徑集合中的，這說明第一次構(gòu)造的到的候選路徑滿足條件“V出發(fā)，中途只經(jīng)過集A的節(jié)點(diǎn)”。另外，集A中每加入一個(gè)新節(jié)點(diǎn)，都會考慮V0發(fā)經(jīng)過這個(gè)新節(jié)點(diǎn)到Y(jié)路徑，并和原候選路徑比較，選擇兩者中較小的那個(gè)，這種過程一直持續(xù)Y選入集A中為止。這個(gè)過程顯然保證了Y的候選路徑一直保持了特性V0發(fā)，中途只經(jīng)過集A中的節(jié)點(diǎn)，而且因?yàn)楸闅v了所有中的節(jié)點(diǎn)，所以是所有這種特性路徑中最短的。有了結(jié)一證明算可以弱化為證結(jié)論。結(jié)二假設(shè)造程下步選擇是點(diǎn)，那么時(shí)達(dá)Y的短徑然從V出，途經(jīng)集A的節(jié)到Y(jié)路徑如“論”立的話，結(jié)“論”說Y的最短路徑和候選路徑具有相同的屬性“V0發(fā)，只經(jīng)過集A中節(jié)點(diǎn)”，“結(jié)一中明確說明，候選路是這種屬性的路徑中的最小者，所以對于下一步即將選入集A中的節(jié)點(diǎn)Y其最短路徑值就是候選路徑，也即證明了算法中構(gòu)造最短路徑樹過程的正確性。下面我們證明“論”證明很簡單，使用反證法：假設(shè)到Y(jié)的最短路徑中途不只經(jīng)過集A，那么必然過一個(gè)不在集A中的節(jié)點(diǎn)于是這條路徑中肯定包含一條V0到W路徑條路徑顯然比從V0發(fā)經(jīng)過到Y(jié)的徑更短，而Y是一步要放入集A的節(jié)點(diǎn)，根據(jù)我們按非降次序構(gòu)造最短路徑樹的過程（第一條最短，第二條次…），從V出發(fā)到的這條路徑應(yīng)該已經(jīng)在最短路徑樹中了，也即節(jié)應(yīng)該已經(jīng)在集合A中矛盾，得證。/

3OSPF議對法的使從理論上來說只描述清楚了點(diǎn)之間的連接和邊的屬性描述清楚了有向圖也就可以使用算法計(jì)算出最短路徑樹。對于使用基于D算的路由協(xié)議來說，如果能描述清楚整個(gè)網(wǎng)絡(luò)拓?fù)洌▽?yīng)有向圖并區(qū)域內(nèi)的每臺路由器清楚的知道整個(gè)區(qū)域的網(wǎng)絡(luò)拓?fù)涿柯酚善鞫伎梢元?dú)立的計(jì)算出最短路徑樹。從這個(gè)意義上說，對于一個(gè)使法的路由協(xié)議來說，需要要解決以下問題：

網(wǎng)絡(luò)拓?fù)涞拿枋鰡栴}。網(wǎng)絡(luò)拓?fù)涿枋鲂畔⒌膫鞑栴}。效率問題路由協(xié)議的目的是在費(fèi)最少資源的情況下最短時(shí)間內(nèi)動(dòng)態(tài)發(fā)現(xiàn)到其他網(wǎng)段的最優(yōu)路徑。另外，還需要考慮路由協(xié)議的網(wǎng)絡(luò)應(yīng)用位置或者GP，適合于多大絡(luò)等）以及和其他路由協(xié)議的互操作等問題。以上幾個(gè)問題有一定的關(guān)聯(lián)性互相影響例如絡(luò)拓?fù)涿枋龅膬?yōu)化可以減少描述信息，從而減輕傳播和計(jì)算過程的消耗，提高了效率。本文的著力點(diǎn)是ijkstra算法其O中應(yīng)用，所以這里只說明與之相關(guān)的網(wǎng)絡(luò)拓?fù)涞拿枋龊妥疃搪窂接?jì)算兩個(gè)內(nèi)容，網(wǎng)絡(luò)拓?fù)涞拿枋鲆仓簧婕暗膸最惢?.1OSPF對網(wǎng)絡(luò)拓?fù)涞拿枋鯫SPF中使用鏈路狀態(tài)通來描述網(wǎng)絡(luò)拓?fù)洌从邢驁D）。OSPF中，LSA被用來描述路由器（節(jié)點(diǎn)）之間的連接和鏈路（邊）的屬性具備了理論上計(jì)算最短路徑的可能是僅僅是理論而已從實(shí)踐的角度針特殊的網(wǎng)絡(luò)情況和應(yīng)用場景，需要作一些優(yōu)化工作。先考慮一個(gè)個(gè)節(jié)點(diǎn)的廣播網(wǎng)如果使RLSA描述的話需要描述n個(gè)節(jié)點(diǎn)兩兩相連的n*(n-1)/2鏈路，而且個(gè)點(diǎn)間需要建立建*(n-1)/2鄰接關(guān)系，描述信息需要在這些建立了鄰接關(guān)系的節(jié)點(diǎn)間傳播果一種思路們把這個(gè)廣播網(wǎng)虛構(gòu)成一個(gè)偽節(jié)點(diǎn)，其他n個(gè)節(jié)點(diǎn)均和偽節(jié)點(diǎn)相連，那么就只要描條鏈路n節(jié)點(diǎn)只需要和偽節(jié)點(diǎn)建立總共n個(gè)鄰接關(guān)系即可，能大大減少了信息描述量和信息傳播量。依據(jù)這種想法OSPF中針對廣播網(wǎng)的描述進(jìn)行了優(yōu)化，使用指定路由DR來承擔(dān)這個(gè)偽點(diǎn)的角色，并使用/

LSA描述廣播網(wǎng)R各個(gè)路由器的連接情況。對于網(wǎng)絡(luò)的描述，處理方式和廣播網(wǎng)基本相同。其次，的設(shè)計(jì)目標(biāo)是為一個(gè)較大的內(nèi)部網(wǎng)絡(luò)提供動(dòng)態(tài)路由能力。如果內(nèi)部網(wǎng)絡(luò)較大的話，需要描述的鏈路會很多，存儲、傳播和計(jì)算這些鏈路信息將耗費(fèi)大量內(nèi)存資源解決這個(gè)問題的辦法是把較大的網(wǎng)絡(luò)劃分成多每A內(nèi)部使用和把Area內(nèi)部網(wǎng)絡(luò)拓?fù)涿枋銮宄?，并?jù)此使算計(jì)算出Area內(nèi)的最短路徑樹和路由。至Area的網(wǎng)絡(luò)拓?fù)?，區(qū)域邊界路由器ABR并把相鄰A的LSAN傳入本A，而是把自己在相鄰rea圍內(nèi)計(jì)算得到的該A內(nèi)各個(gè)網(wǎng)段的路由進(jìn)行匯總，把這些網(wǎng)段當(dāng)做直接連接在自己上面，并生NetworkSummary來這些網(wǎng)進(jìn)行描述，傳入A。這樣，對于一個(gè)n網(wǎng)段和多臺路由器的相鄰，ABR只需生成n網(wǎng)絡(luò)描述信息并傳入A即可，大大減少了進(jìn)入Area鏈路描述信息，減少了存儲、傳播和計(jì)算消耗。需要注意的是，劃的法導(dǎo)致了A內(nèi)部路由器中的鏈路狀態(tài)數(shù)據(jù)庫描述A外分并不是真實(shí)的絡(luò)拓?fù)溆?jì)算時(shí)可能出現(xiàn)環(huán)路，為了避免環(huán)路出現(xiàn)，要求所有A之的相連必須經(jīng)B區(qū)域即A0。另外OSPF被計(jì)為一IGP所以除了處理本自治系統(tǒng)內(nèi)的路由外需要處理自治系統(tǒng)外的路由，這類路由A處引入，可以看做是直接連接ASBR，OSPF引入AExternalLSA描述這類自治系統(tǒng)外路由。另外，因AS在傳入其他A時(shí)不在ABR重新生成所以從計(jì)算的角度看他Area必須知道自治系統(tǒng)外路由從哪個(gè)節(jié)點(diǎn)引入，所以需要引A來述外部路由哪個(gè)節(jié)點(diǎn)引入ASBRSummary在ABR上生成，從其A看，可以認(rèn)A直接連ABR，自治系統(tǒng)外部路由對應(yīng)的網(wǎng)段又直接連A上。3.2OSPF中短路徑的計(jì)算下面簡單介紹一OSPF的最短路徑計(jì)過程，具體的細(xì)節(jié)處理請參RFC2328首先，計(jì)算rea內(nèi)部路由。因?yàn)镽outer和NLSA確的描述出了整A內(nèi)部的網(wǎng)絡(luò)拓?fù)?，所以根?jù)Dijkstra算，可以計(jì)算到各個(gè)節(jié)點(diǎn)（路由器）的最短路徑。然后根據(jù)描的與路由器相連的網(wǎng)情況到了到各個(gè)網(wǎng)段的最短路徑，計(jì)算過程中，如果有多條代價(jià)相同的最短路徑，都保留。其次，計(jì)算的由。因?yàn)閺囊粌?nèi)部看，相Area的路由對應(yīng)的網(wǎng)段就好像是直接連在A上，而到ABR最短路徑已經(jīng)在上一步算出，所以直接檢Nerwork/

Summary，可很易得到這些網(wǎng)段的最短路徑值。另外ASBR被看做是直接連接在ABR，所以ASBR的最短路徑也可在這一步計(jì)算出來。注意：在這一步，如果發(fā)起計(jì)算的路由器是A，那么自然，應(yīng)該只考慮骨干區(qū)域NetworkSummaryLSA；但是于啟用VirtualLin