OSPF動(dòng)態(tài)路由技術(shù)的研究與實(shí)現(xiàn)

責(zé)任編輯:xdong

2012-02-20 10:03:13

摘自:比特網(wǎng)

本文在分析OSPF動(dòng)態(tài)路由協(xié)議基本工作原理的基礎(chǔ)上,提出了Dijkstra算法和OSPF路由表計(jì)算的實(shí)現(xiàn)方法。

隨著Internet技術(shù)在全球范圍內(nèi)的飛速發(fā)展,IP網(wǎng)絡(luò)作為一種最有前景的網(wǎng)絡(luò)技術(shù),受到了人們的普遍關(guān)注。而作為IP網(wǎng)絡(luò)生存、運(yùn)作、組織的核心——IP路由技術(shù)提供了解決IP網(wǎng)絡(luò)動(dòng)態(tài)可變性、實(shí)時(shí)性、QoS等關(guān)鍵技術(shù)的一種可能。在眾多的路由技術(shù)中,OSPF協(xié)議已成為目前Internet廣域網(wǎng)和Intranet企業(yè)網(wǎng)采用最多、應(yīng)用最廣泛的路由技術(shù)之一。本文在分析OSPF動(dòng)態(tài)路由協(xié)議基本工作原理的基礎(chǔ)上,提出了Dijkstra算法和OSPF路由表計(jì)算的實(shí)現(xiàn)方法。

目前應(yīng)用較多的路由協(xié)議有RIP和OSPF,它們同屬于內(nèi)部網(wǎng)關(guān)協(xié)議,但RIP基于距離矢量算法,而OSPF基于鏈路狀態(tài)的最短路徑優(yōu)先算法。它們?cè)诰W(wǎng)絡(luò)中利用的傳輸技術(shù)也不同。

RIP是利用UDP的520號(hào)端口進(jìn)行傳輸,實(shí)現(xiàn)中利用套接口編程,而OSPF則直接在IP上進(jìn)行傳輸,它的協(xié)議號(hào)為89。在RIP當(dāng)中,所有的路由都由跳數(shù)來(lái)描述,到達(dá)目的地的路由最大不超過16跳,且只保留唯一的一條路由,這就限制了RIP的服務(wù)半徑,即其只適用于小型的簡(jiǎn)單網(wǎng)絡(luò)。同時(shí),運(yùn)行RIP的路由器需要定期地(一般30s)將自己的路由表廣播到網(wǎng)絡(luò)當(dāng)中,達(dá)到對(duì)網(wǎng)絡(luò)拓?fù)涞木酆?,這樣不但聚合的速度慢而且極容易引起廣播風(fēng)暴、累加到無(wú)窮、路由環(huán)致命等問題。為此,OSPF應(yīng)運(yùn)而生。OSPF是基于鏈路狀態(tài)的路由協(xié)議,它克服了RIP的許多缺陷:

第一,OSPF不再采用跳數(shù)的概念,而是根據(jù)接口的吞吐率、擁塞狀況、往返時(shí)間、可靠性等實(shí)際鏈路的負(fù)載能力定出路由的代價(jià),同時(shí)選擇最短、最優(yōu)路由并允許保持到達(dá)同一目標(biāo)地址的多條路由,從而平衡網(wǎng)絡(luò)負(fù)荷;

第二,OSPF支持不同服務(wù)類型的不同代價(jià),從而實(shí)現(xiàn)不同QoS的路由服務(wù);

第三,OSPF路由器不再交換路由表,而是同步各路由器對(duì)網(wǎng)絡(luò)狀態(tài)的認(rèn)識(shí),即鏈路狀態(tài)數(shù)據(jù)庫(kù),然后通過Dijkstra最短路徑算法計(jì)算出網(wǎng)絡(luò)中各目的地址的最優(yōu)路由。這樣OSPF路由器間不需要定期地交換大量數(shù)據(jù),而只是保持著一種連接,一旦有鏈路狀態(tài)發(fā)生變化時(shí),才通過組播方式對(duì)這一變化做出反應(yīng),這樣不但減輕了不參與系統(tǒng)的負(fù)荷而且達(dá)到了對(duì)網(wǎng)絡(luò)拓?fù)涞目焖倬蹠?huì)。而這些正是OSPF強(qiáng)大生命力和應(yīng)用潛力的根本所在。

一、OSPF工作原理分析

OSPF是一種分層次的路由協(xié)議,其層次中最大的實(shí)體是AS(自治系統(tǒng)),即遵循共同路由策略管理下的一部分網(wǎng)絡(luò)實(shí)體。在每個(gè)AS中,將網(wǎng)絡(luò)劃分為不同的區(qū)域。每個(gè)區(qū)域都有自己特定的標(biāo)識(shí)號(hào)。對(duì)于主干(backbone)區(qū)域,負(fù)責(zé)在區(qū)域之間分發(fā)鏈路狀態(tài)信息。這種分層次的網(wǎng)絡(luò)結(jié)構(gòu)是根據(jù)OSPF的實(shí)際提出來(lái)的。當(dāng)網(wǎng)絡(luò)中自治系統(tǒng)非常大時(shí),網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)庫(kù)的內(nèi)容就更多,所以如果不分層次的話,一方面容易造成數(shù)據(jù)庫(kù)溢出,另一方面當(dāng)網(wǎng)絡(luò)中某一鏈路狀態(tài)發(fā)生變化時(shí),會(huì)引起整個(gè)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都重新計(jì)算一遍自己的路由表,既浪費(fèi)資源與時(shí)間,又會(huì)影響路由協(xié)議的性能(如聚合速度、穩(wěn)定性、靈活性等)。因此,需要把自治系統(tǒng)劃分為多個(gè)域,每個(gè)域內(nèi)部維持本域一張唯一的拓?fù)浣Y(jié)構(gòu)圖,且各域根據(jù)自己的拓?fù)鋱D各自計(jì)算路由,域邊界路由器把各個(gè)域的內(nèi)部路由總結(jié)后在域間擴(kuò)散。這樣,當(dāng)網(wǎng)絡(luò)中的某條鏈路狀態(tài)發(fā)生變化時(shí),此鏈路所在的域中的每個(gè)路由器重新計(jì)算本域路由表,而其它域中路由器只需修改其路由表中的相應(yīng)條目而無(wú)須重新計(jì)算整個(gè)路由表,節(jié)省了計(jì)算路由表的時(shí)間。

OSPF由兩個(gè)互相關(guān)聯(lián)的主要部分組成:“呼叫”協(xié)議和“可靠泛洪”機(jī)制。呼叫協(xié)議檢測(cè)鄰居并維護(hù)鄰接關(guān)系,可靠泛洪算法可以確保統(tǒng)一域中的所有的OSPF路由器始終具有一致的鏈路狀態(tài)數(shù)據(jù)庫(kù),而該數(shù)據(jù)庫(kù)構(gòu)成了對(duì)域的網(wǎng)絡(luò)拓?fù)浜玩溌窢顟B(tài)的映射。鏈路狀態(tài)數(shù)據(jù)庫(kù)中每個(gè)條目稱為L(zhǎng)SA(鏈路狀態(tài)通告),共有5種不同類型的LSA,路由器間交換信息時(shí)就是交換這些LSA。每個(gè)路由器都維護(hù)一個(gè)用于跟蹤網(wǎng)絡(luò)鏈路狀態(tài)的數(shù)據(jù)庫(kù),然后各路由器的路由選擇就是基于鏈路狀態(tài),通過Dijkastra算法建立起來(lái)最短路徑樹,用該樹跟蹤系統(tǒng)中的每個(gè)目標(biāo)的最短路徑。最后再通過計(jì)算域間路由、自治系統(tǒng)外部路由確定完整的路由表。與此同時(shí),OSPF動(dòng)態(tài)監(jiān)視網(wǎng)絡(luò)狀態(tài),一旦發(fā)生變化則迅速擴(kuò)散達(dá)到對(duì)網(wǎng)絡(luò)拓?fù)涞目焖倬酆?,從而確定出新的網(wǎng)絡(luò)路由表。

OSPF的設(shè)計(jì)實(shí)現(xiàn)要涉及到指定路由器、備份指定路由器的選舉、協(xié)議包的接收、發(fā)送、泛洪機(jī)制、路由表計(jì)算等一系列問題。本文僅就Dijkstra算法與路由表的計(jì)算進(jìn)行討論。 二、Dijkstra算法

Dijkstra算法是路由表計(jì)算的依據(jù),通過Dijkstra算法可以得到有關(guān)網(wǎng)絡(luò)節(jié)點(diǎn)的最短路徑樹,然后由最短路徑優(yōu)先樹得到路由表。

1.Dijkstra算法的描述如下:

(1)初始化集合E,使之只包含源節(jié)點(diǎn)S,并初始化集合R,使之包含所有其它節(jié)點(diǎn)。初始化路徑列O,使其包含一段從S起始的路徑。這些路徑的長(zhǎng)度值等于相應(yīng)鏈路的量度值,并以遞增順序排列列表O。

(2)若列表O為空,或者O中第1個(gè)路徑長(zhǎng)度為無(wú)窮大,則將R中所有剩余節(jié)點(diǎn)標(biāo)注為不可達(dá),并終止算法。

(3)首先尋找列表O中的最短路徑P,從O中刪除P。設(shè)V為P的最終節(jié)點(diǎn)。若V已在集合E中,繼續(xù)執(zhí)行步驟2。否則,P為通往V的最短路徑。將V從R移至E。

(4)建立一個(gè)與P相連并從V開始的所有鏈路構(gòu)成的侯選路徑集合。這些路徑的長(zhǎng)度是P的長(zhǎng)度加上與P相連的長(zhǎng)度。將這些新的鏈路插入有序表O中,并放置在其長(zhǎng)度所對(duì)應(yīng)的等級(jí)上。繼續(xù)執(zhí)行步驟2。

2.Dijkstra算法舉例:

下面我們以路由器A為例,來(lái)說(shuō)明最短路徑樹的建立過程:

(1)路由器A找到了路由器B、C,將它們列入候選列表{B:1;C:2}。

(2)從候選列表中找出最小代價(jià)項(xiàng)B,將B加入最短路徑樹并從候選列表中刪除。接著從B開始尋找,找到了D,將其放入候選列表{C:2;D:2}。

(3)從列表中找出C,再由C又找到了D。但此時(shí)D的代價(jià)為4,所以不再加入候選列表。最后將D加入到最短路徑樹。此時(shí)候選列表為空,完成了最短路徑樹的計(jì)算。

三、OSPF路由表的計(jì)算與實(shí)現(xiàn)

有關(guān)路由表的計(jì)算是OSPF的核心內(nèi)容,它是動(dòng)態(tài)生成路由器內(nèi)核路由表的基礎(chǔ)。在路由表?xiàng)l目中,應(yīng)包括有目標(biāo)地址、目標(biāo)地址類型、鏈路的代價(jià)、鏈路的存活時(shí)間、鏈路的類型以及下一跳等內(nèi)容。關(guān)于整個(gè)計(jì)算的過程,主要由以下五個(gè)步驟來(lái)完成:

(1)保存當(dāng)前路由表,當(dāng)前存在的路由表為無(wú)效的,必須從頭開始重新建立路由表;

(2)域內(nèi)路由的計(jì)算,通過Dijkstra算法建立最短路徑樹,從而計(jì)算域內(nèi)路由;

(3)域間路由的計(jì)算,通過檢查Summary-LSA來(lái)計(jì)算域間路由,若該路由器連到多個(gè)域,則只檢查主干域的Summary-LSA;

(4)查看Summary-LSA:在連到一個(gè)或多個(gè)傳輸域的域邊界路由器中,通過檢查該域內(nèi)的Summary-LSA來(lái)檢查是否有比第(2)(3)步更好的路徑;

(5)AS外部路由的計(jì)算,通過查看AS-External-LSA來(lái)計(jì)算目的地在AS外的路由。

通過以上步驟,OSPF生成了路由表。但這里的路由表還不同于路由器中實(shí)現(xiàn)路由轉(zhuǎn)發(fā)功能時(shí)用到的內(nèi)核路由表,它只是OSPF本身的內(nèi)部路由表。因此,完成上述工作后,往往還要通過路由增強(qiáng)功能與內(nèi)核路由表交互,從而實(shí)現(xiàn)多種路由協(xié)議的學(xué)習(xí)。

OPSF作為一種重要的內(nèi)部網(wǎng)關(guān)協(xié)協(xié)議的普遍應(yīng)用,極大地增強(qiáng)了網(wǎng)絡(luò)的可擴(kuò)展性和穩(wěn)定性,同時(shí)也反映出了動(dòng)態(tài)路由協(xié)議的強(qiáng)大功能。但是,在有關(guān)OSPF協(xié)議的研究、實(shí)現(xiàn)中尚存在一些問題,如數(shù)據(jù)庫(kù)的溢出、度量的刻畫、以及MTU協(xié)商等等。同時(shí),在IPv6中,OSPFv3基于鏈路的處理機(jī)制、IP地址的變化、泛洪范圍的增加、包格式、LSA的變化以及鄰居的識(shí)別等技術(shù)都將是我們共同探討的課題。

鏈接已復(fù)制,快去分享吧

企業(yè)網(wǎng)版權(quán)所有?2010-2024 京ICP備09108050號(hào)-6京公網(wǎng)安備 11010502049343號(hào)