CCNA--距離矢量協定與鍊路狀态路由協定

　　距離矢量算法是以R.E.Bellman,L.R.Ford和D.R.Fulkerson所做的工作為基礎的，鑒于此，我們把距離矢量路由協定稱為Bellman-Ford或者Ford-Fulkerson算法。

　　距離矢量名稱的由來是因為路由是以矢量（距離，方向）的方式被通告出去的，這裡的距離是根據度量來決定的。通俗點就是：往某個方向上的距離。

　　每種路由協定都有自己的算法，路由協定在共享和傳遞路由更新資訊，乃至收斂都因為算法的不同而不同。

　　路由協定根據算法可以分為兩大類（也有說三類的—混合）：距離矢量（Distance Ventor）和鍊路狀态（Link State）。

　　例如：“朝下一個路由器X的方向可以到達網絡A，距此5跳之遠”

　　每台路由器在資訊上都依賴于自己的相鄰路由器，而它的相鄰路由器又是通過自它們自己的相鄰路由器那裡學習路由，依此類推，是以就好象街邊巷尾的小道新聞——一傳十，十傳百，很快就能弄到家喻戶曉了。呵呵。正因為如此，我們一般把距離矢量路由協定稱之為“依照傳聞的路由協定”

　　距離矢量路由算法是動态路由算法。它是這樣工作的：每個路由器維護一張矢量表，表中列出了目前已知的到 每個目标的最佳距離，以及所使用的線路。通過在鄰居之間互相交換資訊，路由器不斷地更新它們内部的表。

　　距離矢量路由算法最常見的是Ford－Fulkerson算法。該算法的核心思想是使用标号的方法不斷尋找一個圖上的 可增廣路徑并且進行調整，直到找不到可增廣路徑為止。距離矢量路由算法号召每個路由器在每次更新時發送它 的整個路由表，但僅僅給它的鄰居。距離矢量路由算法傾向于路由循環，但比鍊路狀态路由算法計算更簡單。

　　算法描述如下：

　　給定帶杈有向圖G和源點s，求從s到G中任意頂點v的最短路徑，該算法通過在一個路由中重申跳數的個數九來尋 找一個最短路徑生成樹。

　　在距離矢量路由選擇算法中，每個路由器維持有一張子網中每一個以其他路由器為索引的路由選擇表，表中的 每一個項目都對應于子網中的每個路由器。此表項包括兩個部分，即希望使用的到目的地的輸出線路和估計到達 目的地所需時間或距離。用度量标準可為站點，估計的時間延遲（ms），該路出排隊的分組估計總數或類似的值。

　　假定路由器知道它到每個相鄰路由器的“距離”。如果度量标準為站點，其距離就為一個站點；如果度量标準是隊列長度，則路由器會簡單地檢查每個隊列；如果度量标準是延遲，路由器可以直接發送一個特别“響應”（ECHO）分組來測出延遲，接收者隻對它加上時間标記後就盡快送回。

　　1、IP路由資訊協定–RIP

　　2、Xerox網絡系統的XNS RIP

　　3、Novell的IPX RIP

　　4、Cisco的Internet網關路由選擇協定–IGRP

　　5、DEC的DNA階段4

　　6、Apple Talk的路由選擇表維護協定–RTMP

距離矢量路由的通用屬性

     1、定期更新（Periodic Updates）

      定期更新意味着每經過特定時間周期就要發送更新資訊。這個時間周期從10S到90S。這裡有一個問題就是，更新周期越長，路由收斂越慢；更新周期越短，就越可能引起因為更新而造成的網絡擁塞。

      2、鄰居（Neighbours）

      鄰居通常是指共享着相同資料鍊路的路由器。距離矢量路由協定向相鄰路由器發送更新資訊（有一些特定的主機也會偵聽路路由更新資訊），并依靠鄰居來幫它傳遞路由更新資訊。因為有人把距離矢量路由協定稱為“傳聞式的路由協定”。

      3、廣播更新（Broadcast Updates）

      當路由器剛開機或者剛啟動路由協定時，它如何尋找其他的路由器呢？它如何向其他路由器宣告自己的存在或者出現呢？大家可以想一下，在現實生活中，我們在一堆人中找某個人時，你會一個一個的去問還是大喊一聲呢？顯而易見，在路由選擇協定的更新中，它使用了廣播的更新方式.

   4、包含整個路由表的更新

      就好象兩個知心好友一樣，推心置腹……把自己知道的什麼玩意兒都掏出來告訴對方。基本上所有的距離矢量路由協定都會采用這種簡便的辦法來向鄰居路由器通告自己所知道的所有資訊——告訴其他路由器自己的整張路由選擇表，鄰居在收到該資訊後，去其糟粕，取其精華……完善自己的路由表。

   5、依照傳聞進行路由選擇。

   6、路由計時器（在後面講解RIP的時候會将到）。講述距離矢量的幾種計時器

 　7、水準分割（Split Horizon）詳見CCNP-BSCI 002距離矢量路由協定–水準分割

　 8、計數到無窮大（在後面講解RIP的時候會将到）

　 9、觸發更新（Triggered Update）

　　觸發更新又名快速更新：當路由收斂後，如果某台路由器得知自己直連的一條鍊路的度量變化了，（無論好或者壞）那麼該路由器将立即發送更新資訊，不必等到更新計時器的到期。

　 10、抑制計時器（Holddown Timer）

　　觸發更新為正在進行收斂的網絡增加了應變能力，為了降低接受錯誤路由資訊的可能性，抑制計時器引入了某種程度的懷疑量

　　如果到一個目标的度量發生改變（無論是增大還是減小），那麼路由器将會将該路由條目置為抑制狀态——即加上一個抑制計時器。直到計時器逾時，路由器才會接受有關此路由的資訊。

　　它雖然降低了錯誤路由的可能性，但是收斂時間卻會是以而變長，因為在對其進行配置的時候，一定要根據全網的情況來配置一個合适的值。

　　11、異步更新（Asynchronous Update）

　　假設有一組連接配接在以太網段上的路由器群，大家都記得，以太網的工作方式。如果每台路由器都共享一個廣播網絡的時候，很可能會出現更新同步的情況——幾台路由器的更新時間同時到期，同時更新。那麼就會造成封包的碰撞，然後根據CSMA/CD，它們會回退，但是，很可能這樣一來影響到整個系統的時延，最終會造成整個網絡的同步。是以，我們通常使用兩種辦法來防止同步保持異步更新：

　　·每台路由器的更新計時器都獨立于路由程序，因為不會受到路由器處理負載的影響

　　·在每個更新周期中加入一個小的随機偏移量。

鍊路狀态路由協定：

一、概述

如果把距離矢量路由選擇協定比作是由路标提供的資訊，那麼鍊路狀态路由選擇協定就是一張交通線路圖；因為它有一張完整的網絡圖，是以它是不容易被欺騙而作出錯誤的路由決策的；鍊路狀态不同于距離矢量依照傳聞進行路由選擇的工作方式，每台路由器都會産生一些關于自己、本地直連鍊路以及這些鍊路的狀态（以此而得名）和所有直接相連鄰居的資訊。這些資訊從一台路由器傳送到另一台路由器，每台路由器都做一份資訊拷貝，但是決不改動這些資訊，最終每台路由器都有一個相同的有關網絡的資訊，并且每台路由器可以獨立地計算各自的最優路徑；

鍊路狀态協定，有時也叫最短路徑優先協定或分布式資料庫協定，是圍繞着圖論中的一個著名算法-E.W.Dijkstra的最短路徑算法設計的；鍊路狀态協定有以下幾種：

IP開放式最短路徑優先OSPF；

CLNS或IP ISO的中間系統到中間系統IS-IS；

DEC的DNA階段5；

Novell的NetWare鍊路服務協定NLSP.

鍊路狀态路由選擇協定的基本步驟如下：

1、每台路由器與它的鄰居之間建立聯系，這種聯系稱為鄰接關系；

2、每台路由器向每個鄰居發送鍊路狀态通告LSA。對每台路由器鍊路都會生成一個LSA，LSA用于辨別這條鍊路、鍊路狀态、路由器接口到鍊路的代價路徑成本以及鍊路所連接配接的所有鄰居。每個鄰居在收到通告後将依次向它的鄰居轉發(泛洪)這些通告；

3、每台路由器要在資料庫中儲存一份它所收到的LSA的備份，如果所有路由器工作正常，那麼它們的鍊路狀态資料庫應該相同；

4、完整的拓撲資料庫，也叫做鍊路狀态資料庫，Dijkstra算法使用它對網絡圖進行計算得出到每台路由器的最短路徑；接着鍊路狀态協定對鍊路狀态資料庫進行查詢找到每台路由器所連接配接的子網，并把這些資訊輸入到路由表中.

二、鄰居

鄰居發現是建立鍊路狀态環境并運轉的第一步，它将使用Hello協定(Hello Protocol)。Hello協定定義了一個Hello資料包的格式和交換資料包并處理資料包資訊的過程；Hello資料包至少應包含一個路由器ID CRID和發送資料包的網絡位址。路由器ID可以将發送該資料包的路由器與其他路由器惟一地區分開，例如，路由器ID可以是路由器一個接口的IP位址。資料包的其他字段可以攜帶子網路遮罩、Hello間隔、線路類型描述符和幫助建立鄰居關系的标記，其中Hello間隔是路由器在宣布鄰居死亡之前等待的最大周期；

當兩台路由器已經互相發現并将對方視為鄰居時，它們要進行資料庫同步過程，即交換和确認資料庫資訊，直到資料庫相同為至；為了執行資料庫同步，鄰居之間必須建立鄰接關系，即這們必須就某些特定的協定參數，如計時器和對可選擇能力的支援，達成一緻意見。通過使用 Hello資料包建立鄰接關系，鍊路狀态協定就可以在受控的方式下交換資訊，與距離矢量相比，這種方式僅在配置了路由選擇協定的接口上廣播更新資訊(多點傳播)！

除建立鄰接關系外，Hello資料包還可作為監視鄰接關系的握手信号。如果在特定的時間内沒有從鄰接路由器收到Hello資料包，那麼就認為鄰居路由器不可達，随即鄰接關系被解除。典型的Hello資料包交換間隔為10s，典型的死亡周期是交換間隔的4倍.

三、鍊路狀态泛洪擴散(Flooding)

在建立了鄰接關系之後，路由器開始發送LSA給每個鄰居，同時，每個鄰居儲存接收到的LSA并依次向它的每個鄰居轉發，除了發送該LSA的鄰居之外，在這裡優于距離矢量的一個特點是：LSA幾乎是立即被轉發的！是以，當網絡拓撲發生變化時，鍊路狀态協定的收斂速度要遠遠快于距離矢量協定；

泛洪擴散過程是鍊路狀态協定中最複雜的一部分，有幾種方式可以使泛洪擴散更高效和更可靠，如使用單點傳播和多點傳播位址、校驗和以及主動确認，其中有兩個過程是極其重要的：排序和老化；

1、序列号

假設這樣一種情況：路由器C先從B收到了A發出的一個LSA并儲存到自己的拓撲資料庫中，接着又通過路由器F收到了同樣的這個由A發出的LSA，路由器C發現資料庫中已經存在了該LSA（知道是從B收到的），那麼路由器C從路由器F接收到的這個LSA是否應該向路由器B轉發？答案是不轉發！因為路由器B已經收到了這個LSA，由于路由器C從路由器F接收到的LSA的序列号與早先從路由器B接受的LSA序列号相同，是以路由器C也知道這一情況，于是将該LSA丢棄；

當路由器A發送LSA時，在每個拷貝中的序列号都是相同的，此序列号和LSA的其他部分一起被儲存在路由器的拓撲資料庫中，當路由器收到資料庫中已存在的LSA且序列号相同時，路由器将丢棄這些資訊；如果資訊相同但序列号更大，那麼接收的資訊和新序列号被儲存到資料庫中，并且泛洪擴散該LSA；

因為序列号被攜帶在LSA中的一個固定字段内，是以序列号一定有上限，那麼當序列号到達上限時會發生什麼呢？

1）線性序列号空間

一種辦法是使用一個非常大的線性序列号以至于根本不可能到達上限，如使用32位長字段(IS-IS就是這樣)；如果一個鍊路狀态路由選擇程序用完了所有序列号，那麼它在重新使用最低序列号之前必須停止（重新啟動），并等待它所發出的LSA在所有資料庫中都不再使用。假如最大的時間是1個小時或者更長，那麼這種方法是不可行的；

在路由器啟動期間會出現一種更常見的困難。如果路由器A重新開機之後，它無法記得上次使用的序列号，必須重新使用1.但是如果路由器A的鄰居仍然在資料庫中保留了路由器A上次的序列号，那麼越小的序列号也就是越舊的序列号，因而會被忽略；

更好的解決辦法是在泛洪擴散行為中添加新的規則：如果一台重新啟動的路由器向鄰居發送LSA的序列号比鄰居儲存的序列号還要老，那麼鄰居會發回自己儲存的LSA和序列号，這樣就台路由器将知道啟動前自己使用的序列号并作出相應的調整；

然而仍需要小心，最近使用過的序列号不能接近上限，否則，重新啟動的路由器将不得不再次重新啟動。必須設定規則限制路由器“跳躍”地使用序列号。例如，規則指明一次序列号增加不能超過整個序列号空間的二分之一(實際公式要複雜，因為要考慮年齡的限制)；

2）循環序列号空間

這種方法數字是循環使用的，在32位空間内緊跟在4 294 967 295後面的是0；它在重新啟動路由器後也可能會遇到同線性序列号一樣的問題！其結構如下：

循環序列号建立了一個不合邏輯的奇特位。如果X是1到4 294 967 295之間的一個數，那麼0<X<0！在運作正常的網絡中通過聲明兩條規則可以維持這種條件，其中聲明的規則來确定什麼時候一個序列号大于或小于另一個序列号。假設序列号空間為n，則兩個序列号a和b，如果滿足以下任意一種條件，則認為a更新(數量更大)：

a<b,且(a-b)<=n/2

a<b,且(b-a)>n/2

假設這樣一種情況：在一個網絡中使用6位序列号空間。現在其中的一台路由器決定離線，當它在離線之間，突然發送了3個相同且序列号為44(101100)的LSA。不幸的是，一個鄰居也發生了故障，丢掉了幾位資料，丢失的資料位是第2個LSA和第3個LSA序列号中的1位，随即該鄰居路由器向外泛洪了這3個LSA，結果造成3個LSA序列号各不相同：

應用循環規則可得：44比40更新，40比8更新，8又比40更新！這個結論使3個LSA都持續擴散下去，資料庫也不斷地被最新的LSA更新，直到資料庫緩存被塞滿，CPU超載為止，最終整個網絡崩潰！

3）棒棒糖序列号空間

這種方法是線性序列号空間和循環序列号空間的綜合，它有一個線性元件和一個圓形元件；性線空間的缺點是不能循環使用序列号，即序列号是有限的，而圓形空間的缺點是不存在一個數小于其他所有的數；其結構如下：

當路由器重新開機時，它将從小于其他所有數的a開始，鄰居将會識别出這個數，這時如果鄰居資料庫中還保留有上次序列号為b的LSA，那麼它們會發送b給路由器A，則路由器A将跳至該序列号。在知道自己重新開機前使用的序列号之前，路由器A可能會發送不止一個LSA，是以，在鄰居通知路由器A上次使用的序列号或上次使用的序列号從所有資料庫中消失之前，必須準備充足的啟動數以便路由器A不會用光所有重新開機序列号；

這些線性重新開機序列号開成了棒棒糖的棒；在這些數用完或鄰居提供了使路由器A跳轉的序列号之後，路由器A進行循環數空間，也就是棒棒糖的糖體部分。棒棒糖序列号空間使用了有符号數，即-k<0<k。從-k到-1的負數形成棒棒，從0到k的正數形成循環空間。其規則如下：

假設給出兩個數a、b及一個序列号空間n，當且僅當：

a < 0 且 a < b, 或

a > 0, a < b, 且 (b-a) < n/2, 或

a > 0, b > 0, a > b, 且 (a-b) > n/2

認為b比a更新！

棒棒糖形序列号空間用在OSPFv1(RFC 1131)中。目前使用的OSPF版本2采用了線性和棒棒糖形序列号空間的最好的特性。OSPFv2像棒棒糖形序列号一樣使用了從0×80000001開始的有符号數空間，但是當序列号數變為正數時，序列号間持續保持線性直至到達最大數0×7FFFFFFF為止。此時，在重新開機之前OSPF程序必須從所有鍊路狀态資料庫中删除LSA。

2、老化(Aging)

LAS包格式中有一個年齡字段，當LSA被建立時，路由器将該字段設定為0,随着資料包的擴散，每台路由器都會增加通告中的年齡。當然，另一個選項是從某個最大年齡開始，然後遞減，OSPF是遞增，IS-IS是遞減；

老化過程為泛洪擴散增加了可靠性，該協定為網絡定義了一個最大年齡差距(MaxAgeDiff)值。路由器可能接收到一個LSA的多個副本，其中序列号相同，年齡不同。如果年齡的差距小于MaxAgeDiff，那麼認為是由于網絡的正常時延造成了年齡的差異，是以資料庫原有的LSA繼續儲存，新收到的LSA(年齡更大)不被擴散；如果年齡差距超過MaxAgeDiff，那麼認為網絡發生異常，因為新被發送的LSA 的序列号值沒有增加。在這種情況下，較新的LSA會被記錄下來，并将資料包擴散出去。典型的MaxAgeDiff值為15min（用于OSPF）；

若LSA駐留在資料庫中，則LSA的年齡會不斷增加。如果鍊路狀态記錄的年齡增加到某個最大值(MaxAge)－由特定的路由選擇協定－那麼一個帶有MaxAge值的LSA被泛洪擴散到所有鄰居，鄰居随即從資料庫中删除相關記錄；

當LSA的年齡到達MaxAge時，将被從所有的資料庫中删除，這需要有一種機制來定期地确認LSA并且在達到最大年齡之前将它的計時器複位。鍊路狀态重新整理計時器(LSRefesh Timer)就是做此用途的；一旦計時器逾時，路由器将向所有鄰居泛洪擴散新的LSA，收到的鄰居會把有關路由器記錄的年齡設定為新接收到的年齡。 OSPF定義MaxAge為1小時，LSRefresh Time為30min。

四、鍊路狀态資料庫

除了鄰居發現和泛洪擴散LSA，鍊路狀态路由選擇協定的第3個主要任務是建立鍊路狀态資料庫。鍊路狀态資料庫，也叫拓撲資料庫把LSA作為一連串記錄儲存下來。LSA包括兩類通用資訊：

路由器鍊路資訊－使用路由器ID、鄰居ID和代價通告路由器的鄰居路由器，這裡的代價是發送LSA路由器到其鄰居的代價；

末梢網絡資訊  －使用路由器ID、網絡ID和代價通告路由器直接連接配接的末梢網絡(沒有鄰居的網絡)；

注意：鍊路代價是按照出站接口的方向計算的！

五、SPF算法-Dijkstra算法

SPF算法的基本過程：

建構最短路徑樹時，路由器首先将它自己作為根，然後使用拓撲資料庫中的資訊，建立所有與它直連的鄰居清單。到一個鄰居的代價最小的路徑将成為樹的一個分枝，該路由器的所有鄰居都被加入清單。檢查該清單，看是否有重複的路徑：如果有，代價高的路徑将從清單中删除，代價低的路由器将被加入樹；路由器的鄰居也被加入清單，再次檢查該清單是否有重複路徑。此過程不斷重複，直到清單中沒有路由器為止！

六、區域

一個區域是構成一個網絡的路由器的一個子集。将網絡劃分為區域是針對鍊路狀态協定的3個不利影響所采取的措施：

必要的資料庫要求記憶體的數量比距離矢量協定更多；

複雜的算法要求CPU時間比距離矢量協定更多；

鍊路狀态泛洪擴散資料包對可用帶寬帶來了不利的影響，特别是不穩定的網絡.

當一個網絡中路由器的數量很多，以至數千台的時候，那麼SPF算法給記憶體、CPU和帶寬帶來的負擔是不可想象的！通過劃分區域可以減小這些影響。當一個網絡被劃分為多個區域時，在一個區域内的路由器僅需要在本區域擴散LSA，因而隻需要維護本區域的鍊路狀态資料庫。資料庫越小，意味着需要記憶體越少，運作SPF算法需要的CPU周期也越少。如果拓撲改變頻繁發生，引起的擴散将被限制在不穩定的區域！

區域邊界路由器是連接配接兩個區域的路由器，它屬于所連接配接的兩個區域，而且必須為每個區域維護各自的拓撲資料庫！

七、距離矢量路由選擇協定與鍊路狀态路由選擇協定的差別

距離矢量路由器發送它的整個路由表，而鍊路狀态路由器僅僅發送有關它直連鍊路(鄰居)的資訊；

距離矢量路由器僅向這的鄰居發送路由資訊，而鍊路狀态路由器向整個網絡中的所有路由器發送鄰居資訊；

距離矢量路由器通過使用不同的Bellman-Ford算法，而後者則通常使用不同的Dijkstra算法。

本文轉自 meiyanaa 51CTO部落格，原文連結：http://blog.51cto.com/justim/221959，如需轉載請自行聯系原作者