在路由協議中，路由選擇協議是一個重點。那么針對這個重點內容我們將要詳細地為大家介紹一下。這個協議包含了很多信息和概念。希望大家從文中能夠找到值得參考的內容。

一、鏈路狀態泛洪擴散(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個小時或者更長，那么這種方法是不可行的。

2）循環序列號空間

這種方法數字是循環使用的，在32位空間內緊跟在4294967295后面的是0；它在重新啟動路由器后也可能會遇到同線性序列號一樣的問題！

3）棒棒糖序列號空間

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

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并且在達到最大年齡之前將它的計時器復位。鏈路狀態刷新計時器(LSRefeshTimer)就是做此用途的；一旦計時器超時，路由器將向所有鄰居泛洪擴散新的LSA，收到的鄰居會把有關路由器記錄的年齡設置為新接收到的年齡。OSPF定義MaxAge為1小時，LSRefreshTime為30min。 #p#

二、鏈路狀態數據庫

除了鄰居發現和泛洪擴散LSA，鏈路狀態路由選擇協議的第3個主要任務是建立鏈路狀態數據庫。鏈路狀態數據庫，也叫拓撲數據庫把LSA作為一連串記錄保存下來。LSA包括兩類通用信息：

路由器鏈路信息－使用路由器ID、鄰居ID和代價通告路由器的鄰居路由器，這里的代價是發送LSA路由器到其鄰居的代價；

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

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

三、SPF算法-Dijkstra算法

SPF算法的基本過程：

構建最短路徑樹時，路由器首先將它自己作為根，然后使用拓撲數據庫中的信息，創建所有與它直連的鄰居列表。到一個鄰居的代價最小的路徑將成為樹的一個分枝，該路由器的所有鄰居都被加入列表。檢查該列表，看是否有重復的路徑：如果有，代價高的路徑將從列表中刪除，代價低的路由器將被加入樹；路由器的鄰居也被加入列表，再次檢查該列表是否有重復路徑。此過程不斷重復，直到列表中沒有路由器為止！

四、區域

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

必要的數據庫要求內存的數量比距離矢量協議更多；

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

鏈路狀態泛洪擴散數據包對可用帶寬帶來了不利的影響，特別是不穩定的網絡.

當一個網絡中路由器的數量很多，以至數千臺的時候，那么SPF算法給內存、CPU和帶寬帶來的負擔是不可想象的！通過劃分區域可以減小這些影響。當一個網絡被劃分為多個區域時，在一個區域內的路由器僅需要在本區域擴散LSA，因而只需要維護本區域的鏈路狀態數據庫。數據庫越小，意味著需要內存越少，運行SPF算法需要的CPU周期也越少。如果拓撲改變頻繁發生，引起的擴散將被限制在不穩定的區域！

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

五、距離矢量路由選擇協議與鏈路狀態路由選擇協議的區別

距離矢量路由器發送它的整個路由表，而鏈路狀態路由器僅僅發送有關它直連鏈路(鄰居)的信息；

距離矢量路由器僅向這的鄰居發送路由信息，而鏈路狀態路由器向整個網絡中的所有路由器發送鄰居信息；

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