動態路由協議簡介
路由和路由協議
顧名思義，動態路由協議是一些動態生成(或學習到)路由信息的協議。在計算機網絡互聯技術領域，我們可以把路由定義如下，路由是指導IP報文發送的一些路徑信息。動態路由協議是網絡設備如路由器" title="路由器">路由器(Router)學習網絡中路由信息的方法之一，這些協議使路由器能動態地隨著網絡拓撲中產生(如某些路徑的失效或新路由的產生等)的變化，更新其保存的路由表，使網絡中的路由器在較短的時間內，無需網絡管理員介入自動地維持一致的路由信息，使整個網絡達到路由收斂狀態，從而保持網絡的快速收斂和高可用性。
路由器學習路由信息、生成并維護路由表的方法包括直連路由(Direct)、靜態路由(Static)和動態路由(Dynamic)。直連路由是由鏈路層協議發現的，一般指去往路由器的接口地址所在網段的路徑，該路徑信息不需要網絡管理員維護，也不需要路由器通過某種算法進行計算獲得，只要該接口處于活動狀態(Active)，路由器就會把通向該網段的路由信息填寫到路由表中去，直連路由無法使路由器獲取與其不直接相連的路由信息。靜態路由是由網絡規劃者根據網絡拓撲，使用命令在路由器上配置的路由信息，這些靜態路由信息指導報文發送，靜態路由方式也不需要路由器進行計算，但是它完全依賴于網絡規劃者，當網絡規模較大或網絡拓撲經常發生改變時，網絡管理員需要做的工作將會非常復雜并且容易產生錯誤。而動態路由的方式使路由器能夠按照特定的算法自動計算新的路由信息，適應網絡拓撲結構的變化。
動態路由協議的分類
按照區域(指自治系統)，動態路由協議可分為內部網關協議IGP(Interior Gateway Protocol)和外部網關協議EGP(Exterior Gateway Protocol)，按照所執行的算法，動態路由協議可分為距離向量路由協議(Distance Vector)、鏈路狀態路由協議(Link State)，以及思科公司開發的混合型路由協議，如圖1所示。
本文著重討論自治系統內部的鏈路狀態協議OSPF的原理，并結合距離向量協議作一些簡單的比較。
OSPF協議的特點
OSPF全稱為開放最短路徑優先。“開放”表明它是一個公開的協議，由標準協議組織制定，各廠商都可以得到協議的細節。“最短路徑優先”是該協議在進行路由計算時執行的算法。OSPF是目前內部網關協議中使用最為廣泛、性能最優的一個協議，它具有以下特點：
◆ 可適應大規模的網絡；
◆ 路由變化收斂速度快；
◆ 無路由自環；
◆ 支持變長子網掩碼(VLSM)；
◆ 支持等值路由；
◆ 支持區域劃分；
◆ 提供路由分級管理；
◆ 支持驗證；
◆ 支持以組播地址發送協議報文。
采用OSPF協議的自治系統，經過合理的規劃可支持超過1000臺路由器，這一性能是距離向量協議如RIP等無法比擬的。距離向量路由協議采用周期性地發送整張路由表來使網絡中路由器的路由信息保持一致，這個機制浪費了網絡帶寬并引發了一系列的問題，下面對此將作簡單的介紹。
路由變化收斂速度是衡量一個路由協議好壞的一個關鍵因素。在網絡拓撲發生變化時，網絡中的路由器能否在很短的時間內相互通告所產生的變化并進行路由的重新計算，是網絡可用性的一個重要的表現方面。
OSPF采用一些技術手段(如SPF算法、鄰接關系等)避免了路由自環的產生。在網絡中，路由自環的產生將導致網絡帶寬資源的極大耗費，甚至使網絡不可用。OSPF協議從根本(算法本身)上避免了自環的產生。采用距離向量協議的RIP等協議，路由自環是不可避免的。為了完善這些協議，只能采取若干措施，在自環發生前，降低其發生的概率，在自環發生后，減小其影響范圍和時間。
在IP(IPV4)地址日益匱乏的今天，能否支持變長子網掩碼(VLSM)來節省IP地址資源，對一個路由協議來說是非常重要的，OSPF能夠滿足這一要求。
在采用OSPF協議的網絡中，如果通過OSPF計算出到同一目的地有兩條以上代價(Metric)相等的路由，該協議可以將這些等值路由同時添加到路由表中。這樣，在進行轉發時可以實現負載分擔或負載均衡。
在支持區域劃分和路由分級管理上，OSPF協議能夠適合在大規模的網絡中使用。
在協議本身的安全性上，OSPF使用驗證，在鄰接路由器間進行路由信息通告時可以指定密碼，從而確定鄰接路由器的合法性。
與廣播方式相比，用組播地址來發送協議報文可以節省網絡帶寬資源。
從衡量路由協議性能的角度，我們可以看出，OSPF協議確實是一個比較先進的動態路由協議，這也是它得到廣泛采用的主要原因。
OSPF協議的工作原理
網絡拓撲結構
上文提到，OSPF協議是一種鏈路狀態協議，那么OSPF是如何來描述鏈路連接狀況呢？
抽象模型Model 1表示路由器的一個以太網接口不連接其他路由器，只連接了一個以太網段。此時，對于運行 OSPF的路由器R1，只能識別本身，無法識別該網段上的設備(主機等)；抽象模型Model 2表示路由器R1通過點對點鏈路(如PPP、HDLC等)連接一臺路由器R2；抽象模型Model 3表示路由器R1通過點對多點(如Frame Relay、X.25等)鏈路連接多臺路由器R3、R4等，此時路由器R5、R6之間不進行互聯；抽象模型Model 4表示路由器R1通過點對多點(如Frame Relay、X.25等)鏈路連接多臺路由器R5、R6等，此時路由器R5、R6之間互聯。以上抽象模型著重于各類鏈路層協議的特點，而不涉及具體的鏈路層協議細節。該模型基本表達了當前網絡鏈路的連接種類。
在OSPF協議中，分別對以上四種鏈路狀態類型作了描述：
對于抽象模型Model 1(以太網鏈路)，使用Link ID(連接的網段)、Data(掩碼)、Type(類型)和Metric(代價)來描述。此時的Link ID即為路由器R1接口所在網段，Data為所用掩碼，Type為3(Stubnet)，Metric為代價值。
對于抽象模型Model 2(點對點鏈路)，先使用Link ID(連接的網段)、Data(掩碼)、Type(類型)和Metric(代價)來描述接口路由，以上各參數與Model 1相似。接下來描述對端路由器R2，四個參數名不變，但其含義有所不同。此時Link ID為路由器R2的Router ID，Data為路由器R2的接口地址，Type為1(Router)，Metric仍為代價值。
對于抽象模型Model 3(點對多點鏈路，不全連通)，先使用Link ID(連接的網段)、Data(掩碼)、Type(類型)和Metric(代價)來描述接口路由，以上各參數與Model 1相似。接下來分別描述對端路由器R3、R4的方法，與在Model 2中描述R2類似。
對于抽象模型Model 4(點對多點鏈路，全連通)，先使用Link ID(網段中DR的接口地址)、Data(本接口的地址)、Type(類型)和Metric(代價)來描述接口路由。此時Type值為2(Transnet)，然后是本網段中DR(指定路由器)描述的連接通告。
路由器在通報其獲知的鏈路狀態(即上面所述的參數)前，加上LSA頭(Link State Advertisement Head)，從而生成LSA(鏈路狀態廣播)。到此，路由器通過LSA完成周邊網絡的拓撲結構描述，并發送給網絡中的其他路由器。
計算路由
路由器完成周邊網絡的拓撲結構的描述(生成LSA)后，發送給網絡中的其他路由器，每臺路由器生成鏈路狀態數據庫(LSDB)。路由器開始執行SPF(最短路徑優先)算法計算路由，路由器以自己為根節點，把LSDB中的條目與LSA進行對比，經過若干次的遞歸和回溯，直至路由器把所有LSA中包含的網段都找到路徑(把該路由填入路由表中)，此時意味著所到達的該段鏈路的類型標識為3(Stubnet)。
確保LSA在路由器間傳送的可靠性
從上文可以知道，作為鏈路狀態協議的OSPF的工作機制，與RIP等距離向量的路由協議是不一樣的。距離向量路由協議是通過周期性地發送整張路由表，來使網絡中的路由器的路由信息保持一致。這種機制存在著上文提到的一些弊病。而OSPF協議將包含路由信息的部分與只包含路由器間鄰接關系的部分分開，它使用一種被稱作Hello的數據包來確認鄰接關系，這個數據包非常小，它僅被用來發現和維持鄰接關系。
在路由器R1初始化完成后，它將向路由器R2發送Hello數據包。此時R1并不知道R2的存在，因此在數據包中不包含R2的信息(參數seen=0)。而R2在接收到該數據包后，將向R1發送Hello包。此時，Hello包中將表明它已知道存在R1這個鄰居。R1收到這個回應包后就會知道鄰居R2的存在，并且鄰居R2也知道了自己的存在(參數seen=R1)。此時在路由器R1和R2之間就建立了鄰接關系，它們就可以把LSA發送給對方。當然，在發送時OSPF考慮到要盡量減少占用的帶寬，它采用了一些技巧，我們將在下一節簡單介紹這些內容。
眾所周知，IP協議是一種不可靠的、面向無連接的協議，它本身沒有確認和錯誤重傳機制。那么，在這種協議基礎之上，要做到數據包丟失或出錯后進行重傳，上層協議必須本身具備這種可靠的機制。OSPF采取了與TCP類似的確認和超時重傳機制。在機制中，R1和R2將進行一種被稱作鏈路狀態數據庫描述(DD)的數據包的互傳。首先進行協商，從而確定兩者之間的主從關系(根據路由器ID號，ID號大的將作為Master)。鏈路狀態數據庫描述(DD)數據包中包含了一些參數，序列號(seq)、報文號(I)、結尾標識(M)及主從標志(MS)。從屬路由器將使用主路由器發出的DD包中的序列號(seq)，作為自己的第一個DD包的序列號。當主路由器收到從屬路由器的DD包時，就能確認鄰接路由器已收到自己的數據包(如果沒有收到或收到的DD包的序列號不是自己一個DD包的序列號，主路由器將重傳上一個DD包)，主路由器將序列號加1(只有主路由器才有權改變序列號，而從屬路由器沒有)，并發送下一個DD包，該過程的重復保證了在OSPF協議中數據包傳輸的準確性，從而為OSPF協議成為一個準確的路由協議打下了基礎。
高效率地進行LSA的交換
在RIP等距離向量路由協議中，路由信息的交互是通過周期性地傳送整張路由表的機制來完成的，該機制使距離向量路由協議無法高效地進行路由信息的交換。在OSPF協議中，為了提高傳輸效率，在進行鏈路狀態通告(LSA)數據包傳輸時，使用包含LSA頭(Head)的鏈路狀態數據庫描述數據包進行傳輸，因為每個LSA頭中不包含具體的鏈路狀態信息，它只含有各LSA的標識(該標識唯一代表一個LSA)，所以，該報文非常小。鄰接路由器間使用這種字節數很小的數據包，首先確認在相互之間哪些LSA是對方沒有的，而哪些LSA在對方路由器中也存在，鄰接路由器間只會傳輸對方沒有的LSA。對于自己沒有的LSA，路由器會發送一個LS Request報文給鄰接路由器來請求對方發送該LSA，鄰接路由器在收到LS Request報文后，回應一個LS Update報文(包含該整條LSA信息)，在得到對方確認后(接收到對方發出的LS ACK報文)，這兩臺路由器完成了本條LSA信息的同步。
由此可見，OSPF協議采用增量傳輸的方法來使鄰接路由器保持一致的鏈路狀態數據庫(LSDB)。
小結
綜上所述，我們可以歸納出在OSPF協議中使用到的五種協議報文，并簡單介紹了它們的作用，我們作個簡單的小結：
◆ Hello報文，通過周期性地發送來發現和維護鄰接關系；
◆ DD(鏈路狀態數據庫描述)報文，描述本地路由器保存的LSDB(鏈路狀態數據庫)；
◆ LSR(LS Request)報文，向鄰居請求本地沒有的LSA；
◆ LSU(LS Update)報文，向鄰居發送其請求或更新的LSA；
◆ LSAck(LS ACK)報文，收到鄰居發送的LSA后發送的確認報文。
OSPF協議采用的特殊機制
指定路由器和備份指定路由器
在OSPF協議中，路由器通過發送Hello報文來確定鄰接關系，每一臺路由器都會與其他路由器建立鄰接關系，這就要求路由器之間兩兩建立鄰接關系，每臺路由器都必須與其他路由器建立鄰接關系，以達到同步鏈路狀態數據庫的目的，在網絡中就會建立起n×(n-1)/2條鄰接關系(n為網絡中OSPF路由器的數量)，這樣，在進行數據庫同步時需要占用一定的帶寬。
為了解決這個問題，OSPF采用了一個特殊的機制：選舉一臺指定路由器(DR)，使網絡中的其他路由器都和它建立鄰接關系，而其他路由器彼此之間不用保持鄰接。路由器間鏈路狀態數據庫的同步，都通過與指定路由器交互信息完成。這樣，在網絡中僅需建立n-1條鄰接關系。備份指定路由器(BDR)是指定路由器在網絡中的備份路由器，它會在指定路由器關機或產生問題后自動接替它的工作。這時，網絡中的其他路由器就會和備份指定路由器交互信息來實現數據庫的同步。
要被選舉為指定路由器，該路由器應符合以下要求：
◆ 該路由器是本網段內的OSPF路由器；
◆ 該OSPF路由器在本網段內的優先級(Priority)>0；
◆ 該OSPF路由器的優先級最大，如果所有路由器的優先級相等，路由器號(Router ID)最大的路由器(每臺路由器的Router ID是唯一的)被選舉為指定路由器。
滿足以上條件的路由器被選舉為指定路由器，而第二個滿足條件的路由器則當選為備份指定路由器。
指定路由器和備份指定路由器的選舉，是由路由器通過發送Hello數據報文來完成的。
OSPF協議中的區域劃分
OSPF協議在大規模網絡的使用中，鏈路狀態數據庫比較龐大，它占用了很大的存儲空間。在執行最小生成數算法時，要耗費較長的時間和很大的CPU資源，網絡拓撲變化的概率也大大增加。這些因素的存在，不僅耗費了路由器大量的存儲空間，加重了路由器CPU的負擔，而且，整個網絡會因為拓撲結構的經常變化，長期處于“動蕩”的不可用的狀態。
OSPF協議之所以能夠支持大規模的網絡，進行區域劃分是一個重要的原因。
OSPF協議允許網絡方案設計人員根據需要把路由器放在不同的區域(Area)中，兩個不同的區域通過區域邊界路由器(ABR)相連。在區域內部的路由信息同步，采取的方法與上文提到的方法相同。在兩個不同區域之間的路由信息傳遞，由區域邊界路由器(ABR)完成。它把相連兩個區域內生成的路由，以類型3的LSA向對方區域發送。此時，一個區域內的OSPF路由器只保留本區域內的鏈路狀態信息，沒有其他區域的鏈路狀態信息。這樣，在兩個區域之間減小了鏈路狀態數據庫，降低了生成數算法的計算量。同時，當一個區域中的拓撲結構發生變化時，其他區域中的路由器不需要重新進行計算。OSPF協議中的區域劃分機制，有效地解決了OSPF在大規模網絡中應用時產生的問題。
OSPF協議使用區域號(Area ID)來區分不同的區域，其中，區域0為骨干區域(根區域)。因為在區域間不再進行鏈路狀態信息的交互(實際上，在區域間傳遞路由信息采用了可能導致路由自環的遞歸算法)，OSPF協議依靠維護整個網絡鏈路狀態來實現無路由自環的能力，在區域間無法實現。所以，路由自環可能會發生在OSPF的區域之間。解決這一問題的辦法是，使所有其他的區域都連接在骨干區域(Area 0)周圍，即所有非骨干區域都與骨干區域鄰接。對于一些無法與骨干區域鄰接的區域，在它們與骨干區域之間建立虛連接。
結束語
本文對OSPF動態路由協議" title="OSPF動態路由協議">OSPF動態路由協議的主要原理和特性作了簡單的介紹，沒有涉及到自治系統(AS)以外的路由及路由聚合。
OSPF協議采用路由器間建立和維護鄰接關系，維護鏈路狀態信息數據庫，采用最短生成樹算法，避免了路由自環。同時，又采用了一些特殊的機制，保證了它在大規模網絡中的可用性。