距離矢量協議

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

路由協議根據算法可以分為兩大類（也有説三類的—混合）：距離矢量（Distance Vector）和鏈路狀態（Link State）。

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

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

路由以矢量（距離、方向）的方式被通告出去的，其中距離是根據度量來定義的，方向是根據下一跳路由器定義的。被認為是“依照傳聞進行路由選擇”

距離矢量協議直接傳送各自的路由表信息。網絡中的路由器從自己的鄰居路由器得到路由信息，並將這些路由信息連同自己的本地路由信息發送給其他鄰居，這樣一級級的傳遞下去以達到全網同步。每個路由器都不瞭解整個網絡拓撲，它們只知道與自己直接相連的網絡情況，並根據從鄰居得到的路由信息更新自己的路由。

距離矢量協議無論是實現還是管理都比較簡單，但是它的收斂速度慢，報文量大，佔用較多網絡開銷，並且為避免路由環路得做各種特殊處理。目前基於距離矢量算法的協議包括 RIP、IGRP、BGP。其中 BGP是距離矢量協議變種，它是一種路徑矢量協議。

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

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

算法描述如下：

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

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

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

1、IP路由信息協議–RIP

2、Xerox網絡系統的XNS RIP

3、Novell的IPX RIP

4、Cisco的內部網關路由選擇協議–IGRP

5、DEC的DNA階段4

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

7、增強型內部網關路由選擇協議–EIGRP（Enhanced Interior Gateway Routing Protocol）

RIP(Routing Information Protocols，路由信息協議)是使用最廣泛的距離矢量協議，它是由施樂(Xerox)在70年代開發的。TCP/IP版本的RIP是施樂協議的改進版。RIP最大的特點是，無論實現原理還是配置方法，都非常簡單。RIP基於跳數計算路由，並且定期向鄰居路由器發送更新消息。

IGRP是CISCO專有的協議，只在CISCO路由器中實現。它也屬於距離矢量類協議，所以在很多地方與RIP有共同點，比如廣播更新等等。它和RIP最大的區別表現在度量方法、負載均衡等幾方面。IGRP支持多路徑上的加權負載均衡，這樣網絡的帶寬可以得到更加合理的利用。另外，與RIP僅使用跳數作為度量依據不同，IGRP使用了多種參數，構成複合的度量值，這其中可以包含的因素有：帶寬、延遲、負載、可靠性和MTU(最大傳輸單元)等等。 ^[2] 

EIGRP是IGRP的增強版，它也是CISCO專有的路由協議。EIGRP採用了擴散更新(DUAL)算法，在某種程度上，它和距離向量算法相似，但具有更短的收斂時間和更好的可操作性。作為對IGRP的擴展，EIGRP支持多種可路由的協議，如IP、IPX和AppleTalk等等。運行在IP環境時，EIGRP還可以與IGRP進行平滑的連接，因為它們的度量方法是一致的。 ^[2] 

1、定期更新（Periodic Updates）

既然説到了是定期，那麼它們都會在到達某一個時間點上“同時”發送更新信息，更新信息指的是各路由器各自的直連網絡信息。一般這個時間週期為10S到90S。這個週期依照路由協議的不同而不同，常用的RIP為30S，而IGRP為90S。這裏引發爭議的是如果更新信息在網絡中過於頻繁就會浪費帶寬，造成擁塞，如果更新信息發送太慢頻率不高，收斂時間又會變長。

2、鄰居（Neighbours）

鄰居通常意味着共享相同的數據鏈路的路由器。距離矢量路由協議向鄰居路由器發送更新信息，並依賴鄰居向它的鄰居傳遞更新信息，因此，距離矢量路由協議可以被看成是以“逐跳更新方式”來進行路由更新的協議。

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

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

4、依照傳聞進行路由選擇

5、路由計時器，描述距離矢量的幾種計時器

6、水平分割（Split Horizon）詳見CCNP-BSCI 002距離矢量路由協議–水平分割

7、計數到無窮大

最大15跳，避免產生Loop

8、觸發更新（Triggered Update）

限RIPV2，RipV1僅定期更新，而不支持觸發更新

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

9、抑制計時器（Holddown Timer）

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

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

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

10、異步更新（Asynchronous Update）

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

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

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