OSPF動態路由協議基本工作原理 @ Paris

OSPF動態路由協議基本工作原理
路由技術提供了解決IP網路動態可變性、實時性、QoS等關鍵技術的一種可能。在眾多的路由技術中，OSPF協議已成為目前Internet廣域網和Intranet企業網採用最多、應用最廣泛的路由技術之一。本文在分析OSPF動態路由協議基本工作原理的基礎上，提出了Dijkstra演算法和OSPF路由表計算的實現方法。　　　目前應用較多的路由協議有RIP和OSPF，它們同屬於內部網關協議，但RIP基於距離向量演算法，而OSPF基於鏈路狀態的最短路徑優先演算法。它們在網路中利用的傳輸技術也不同。　　　RIP是利用UDP的520號端口進行傳輸，實現中利用套介面編程，而OSPF則直接在IP上進行傳輸，它的協議號為89.在RIP當中，所有的路由都由跳數來描述，到達目的地的路由最大不超過16跳，且只保留唯一的一條路由，這就限制了RIP的服務半徑，即其只適用於小型的簡單網路。同時，運行RIP的路由器需要定期地（一般30s）將自己的路由表廣播到網路當中，達到對網路拓撲的聚合，這樣不但聚合的速度慢而且極容易引起廣播風暴、累加到無窮、路由環致命等問題。為此，OSPF應運而生。OSPF是基於鏈路狀態的路由協議，它克服了RIP的許多缺陷：　　　第一，OSPF不再採用跳數的概念，而是根據介面的吞吐率、擁塞狀況、往返時間、可靠性等實際鏈路的負載能力定出路由的代價，同時選擇最短、最優路由並允許保持到達同一目標地址的多條路由，從而平衡網路負荷；　　　第二，OSPF支援不同服務類型的不同代價，從而實現不同QoS的路由服務；　　　第三，OSPF路由器不再交換路由表，而是同步各路由器對網路狀態的認識，即鏈路狀態數據庫，然後通過Dijkstra最短路徑演算法計算出網路中各目的地址的最優路由。這樣OSPF路由器間不需要定期地交換大量數據，而只是保持著一種連接，一旦有鏈路狀態發生變化時，才通過組播方式對這一變化做出反應，這樣不但減輕了不參與系統的負荷而且達到了對網路拓撲的快速聚會。而這些正是OSPF強大生命力和應用潛力的根本所在。　　　一、OSPF工作原理分析　　　OSPF是一種分層次的路由協議，其層次中最大的實體是AS（自治系統），即遵循共同路由策略管理下的一部分網路實體。在每個AS中，將網路劃分為不同的區域。每個區域都有自己特定的標識號。對於主幹（backbone）區域，負責在區域之間分發鏈路狀態資訊。這種分層次的網路結構是根據OSPF的實際提出來的。當網路中自治系統非常大時，網路拓撲數據庫的內容就更多，所以如果不分層次的話，一方面容易造成數據庫溢出，另一方面當網路中某一鏈路狀態發生變化時，會引起整個網路中每個節點都重新計算一遍自己的路由表，既浪費資源與時間，又會影響路由協議的性能（如聚合速度、穩定性、靈活性等）。因此，需要把自治系統劃分為多個域，每個域內部維持本域一張唯一的拓撲結構圖，且各域根據自己的拓撲圖各自計算路由，域邊界路由器把各個域的內部路由總結後在域間擴散。這樣，當網路中的某條鏈路狀態發生變化時，此鏈路所在的域中的每個路由器重新計算本域路由表，而其他域中路由器只需修改其路由表中的相應條目而無須重新計算整個路由表，節省了計算路由表的時間。　　　OSPF由兩個互相關聯的主要部分組成：“呼叫”協議和“可靠泛洪”機制。呼叫協議檢測鄰居並維護鄰接關係，可靠泛洪演算法可以確保統一域中的所有的OSPF路由器始終具有一致的鏈路狀態數據庫，而該數據庫構成了對域的網路拓撲和鏈路狀態的映射。鏈路狀態數據庫中每個條目稱為LSA（鏈路狀態通告），共有5種不同類型的LSA，路由器間交換資訊時就是交換這些LSA.每個路由器都維護一個用於跟蹤網路鏈路狀態的數據庫，然後各路由器的路由選擇就是基於鏈路狀態，通過Dijkastra演算法建立起來最短路徑樹，用該樹跟蹤系統中的每個目標的最短路徑。最後再通過計算域間路由、自治系統外部路由確定完整的路由表。與此同時，OSPF動態監視網路狀態，一旦發生變化則迅速擴散達到對網路拓撲的快速聚合，從而確定出新的網路路由表。　　　OSPF的設計實現要涉及到指定路由器、備份指定路由器的選舉、協議包的接收、發送、泛洪機制、路由表計算等一系列問題。本文僅就Dijkstra演算法與路由表的計算進行討論。　　　二、Dijkstra演算法　　　Dijkstra演算法是路由表計算的依據，通過Dijkstra演算法可以得到有關網路節點的最短路徑樹，然後由最短路徑優先樹得到路由表。　　　1.Dijkstra演算法的描述如下：　　　（1）初始化集合E，使之只包含源節點S，並初始化集合R，使之包含所有其他節點。初始化路徑列O，使其包含一段從S起始的路徑。這些路徑的長度值等於相應鏈路的量度值，並以遞增順序排列列表O.　　　（2）若列表O為空，或者O中第1個路徑長度為無窮大，則將R中所有剩餘節點標注為不可達，並終止演算法。　　　（3）首先尋找列表O中的最短路徑P，從O中刪除P.設V為P的最終節點。若V已在集合E中，繼續執行步驟2.否則，P為通往V的最短路徑。將V從R移至E.　　　（4）建立一個與P相連並從V開始的所有鏈路構成的侯選路徑集合。這些路徑的長度是P的長度加上與P相連的長度。將這些新的鏈路插入有序表O中，並放置在其長度所對應的等級上。繼續執行步驟2.　　　2.Dijkstra演算法舉例：　　　下面我們以路由器A為例，來說明最短路徑樹的建立過程：　　　（1）路由器A找到了路由器B、C，將它們列入候選列表{B：1；C：2}.　　　（2）從候選列表中找出最小代價項B，將B加入最短路徑樹並從候選列表中刪除。接著從B開始尋找，找到了D，將其放入候選列表{C：2；D：2}.　　　（3）從列表中找出C，再由C又找到了D.但此時D的代價為4，所以不再加入候選列表。最後將D加入到最短路徑樹。此時候選列表為空，完成了最短路徑樹的計算。　　　三、OSPF路由表的計算與實現　　　有關路由表的計算是OSPF的核心內容，它是動態生成路由器內核路由表的基礎。在路由表條目中，應包括有目標地址、目標地址類型、鏈路的代價、鏈路的存活時間、鏈路的類型以及下一跳等內容。關於整個計算的過程，主要由以下五個步驟來完成：　　　（1）保存當前路由表，當前存在的路由表為無效的，必須從頭開始重新建立路由表；　　　（2）域內路由的計算，通過Dijkstra演算法建立最短路徑樹，從而計算域內路由；　　　（3）域間路由的計算，通過檢查Summary-LSA來計算域間路由，若該路由器連到多個域，則只檢查主幹域的Summary-LSA；　　　（4）查看Summary-LSA：在連到一個或多個傳輸域的域邊界路由器中，通過檢查該域內的Summary-LSA來檢查是否有比第（2）（3）步更好的路徑；　　　（5）AS外部路由的計算，通過查看AS-External-LSA來計算目的地在AS外的路由。　　　通過以上步驟，OSPF生成了路由表。但這裡的路由表還不同於路由器中實現路由轉發功能時用到的內核路由表，它只是OSPF本身的內部路由表。因此，完成上述工作後，往往還要通過路由增強功能與內核路由表交互，從而實現多種路由協議的學習。　　　OPSF作為一種重要的內部網關協協議的普遍應用，極大地增強了網路的可擴展性和穩定性，同時也反映出了動態路由協議的強大功能。但是，在有關OSPF協議的研究、實現中尚存在一些問題，如數據庫的溢出、度量的刻畫、以及MTU協商等等。同時，在IPv6中，OSPFv3基於鏈路的處理機制、IP地址的變化、泛洪範圍的增加、包格式、LSA的變化以及鄰居的識別等技術都將是我們共同探討的課題。

.msgcontent .wsharing ul li { text-indent: 0; }

分享

Facebook
Plurk
YAHOO!

rylrdottqtbt

Paris

rylrdottqtbt 發表在痞客邦留言(0) 人氣()

E-mail轉寄

Paris

Paris

OSPF動態路由協議基本工作原理

歷史上的今天

留言列表

站方公告

活動快報

Bioré...

我的好友

熱門文章

文章分類

最新文章

最新留言

動態訂閱

文章精選

文章搜尋

新聞交換(RSS)

誰來我家

參觀人氣

QR Code

POWERED BY