动态路由选择协议（二）距离矢量路由选择协议
大多數的路由選擇協議屬于下面二者之一：
距離矢量（distance vector）和鏈路狀態（link state）。
本篇學習的是距離矢量路由選擇協議的基礎。
?
大多數的距離矢量算法是R.E.Bellman、L.R.Ford和D.R.Fulkerson所做的工作為基礎的，所有有時距離矢量算法又稱為Bellman-Ford或者Ford-Fulkerson算法。
值得注意的是EIGRP是一個例外，它是基于J.J.Garcia Luna Aceves開發的算法實現的。
?
距離矢量名稱的由來是因為路由器是以矢量（距離、方向）的方式被通告出去的，其中距離是根據度量定義的，方向是根據下一跳路由器定義的。
?
例如，"目標A在下一跳路由器X的方向，距離5跳之遠"。這個表述隱含了每臺路由器向鄰接路由器學習它們所觀察到的路由器信息，然后在向外通告自己觀察到的路由器的信息，而每臺路由器的信息又是根據鄰接的路由器，所以所有距離矢量路由選擇有時又被認為是"依據傳聞進行路由選擇"。
?
?
下面列舉的都屬于距離矢量路由協議：
IP路由選擇信息協議（RIP）；
Xerox網絡系統的XNS RIP；
Novell的IPX RIP；
Cisco Systems的Internet網關路由選擇協議（IGRP）和增強型Internet網管路由選擇協議（EIGRP）；
DEC的DNA階段4；
Apple Talk的路由選擇表維護協議（RTMP）。
通用屬性
典型的距離矢量路由選擇協議通常會使用一個路由選擇算法，算法中路由器通過廣播整個路由表，定期地向所有鄰居發送路由更新信息（EIGRP不是這樣的）。
?
上面表述包含了大量信息。
?
1. 定期更新
?
2. 鄰居
?
3. 廣播更新
?
4. 全路由選擇表更新
?
?
?
依照傳聞進行路由選擇
?
在圖中正在進行一個距離矢量算法，其中使用跳數作為度量。
?
在T0時刻，路由器A到路由器D正好可用，而且T0時刻4臺路由器所具有的惟一信息就是它們的直連網絡。
路由表標識了這些網絡，并且指明了它們沒有經過下一跳路由器，是直接連接到路由器上的，所以跳數為0。
每臺路由器都將在它所有的鏈路上廣播這些信息。
?
在T1時刻，路由器接受并處理第1個更新信息。
?
查看此時路由器A的路由表，路由器B發給路由器A的更新信息發現路由器B能夠到達網絡10.1.2.0和10.1.3.0，而且距離都為0跳。
如果這些目標網絡距離路由器B為0跳，那么距離路由器A則為1跳。
所以路由器A將跳數增加1，然后檢查自己的路由表。
路由表中顯示網絡10.1.2.0已知，且距離為0跳，小于路由器B通告的跳數，所以路由器A忽略此信息。
?
圖 距離矢量協議逐跳收斂
?
由于網絡10.1.3.0對于路由器A來說是新信息，所以路由器A將其輸入到路由表中。更新數據包的源地址是路由器B的接口地址（10.1.2.2），因此該地址連同計算的跳數一起被保存到路由表中。
?
注意T1時刻，其他路由器也進行了類似操作。
在T2時刻，隨著更新周期的再次到期，另一組更新消息被廣播，路由器C告知路由器B的路由信息。
路由器B發送了最新的路由表，路由器A更新此時的路由信息。
在T3時刻，網絡已經收斂。每臺路由器都已經知道了每個網絡以及達到每個網絡的下一跳路由器的地址和距離跳數。
?
距離矢量算法提供了指向網絡的路標。該算法給出了方向和距離，但沒有給出沿著這條路徑行走的細節。就像交叉路口一樣，很容容易受到意外或故意的誤導。
?
下面給出的是距離矢量算法的困境以及一些改進的措施。
?
路由失效計數器
?
如果網絡已經收斂，那么當部分網絡的拓撲發生變化時，它怎樣處理重新收斂問題呢？
如果網絡10.1.5.0發生故障，答案很簡單——在下一個周期中，路由器D將這個網絡標記為不可達并且發送該信息。
?
如果網絡10.1.5.0沒有發生故障，而是路由器D發生故障了？
路由器A、B、C的路由表中仍然保存著關于網絡10.1.5.0的信息，雖然該信息不再有用，但是卻沒有路由器通知它們。
它們將不知不覺地向一個不可達網絡轉發著數據包——即在網絡中打開了一個黑洞。
?
處理這個問題的方式是為路由表中的每個表項設置一個失效計時器。
例如，當路由器C首次知道10.1.5.0并將其輸入到路由表中時，路由器C將為該路由器設置計時器。
每隔一定時間間隔路由器C都會收到路由器D的更新信息，路由器C在丟棄有關10.1.5.0的信息的同時復位該路由的計時器。
?
如果路由器D發生故障，路由器C將不能接收到關于10.1.5.0的更新信息。這時計時器將會超時，路由器C將把該路由標記為不可達，并將在下一個更新周期時傳遞該信息。
?
路由器超時的典型周期范圍是3~6個更新周期。路由器在丟失單個更新信息之后將不會使路由器無效的，因為數據包的損壞、丟失或者某種網絡延遲都會造成這種事件的發生。但是如果路由失效周期太長，網絡收斂速度將會非常慢。
?
水平分隔
?
目前，每個路由器在每個更新周期都要向每個鄰居發送它的整個路由表。但是并沒有必要，如果路由器A將學自路由器B的網絡再廣播給路由器B，那么這是一種浪費，因為B已經知道這些網絡。
?
路由的指向與數據包流動方向相反的路由被稱為逆向路由（reverse route）。水平分隔（split horizon）是一種在兩臺路由器之間阻止逆向路由的技術。
?
這樣除了不會浪費資源，還因為不會把從路由器學習的可達性信息再返回給這臺路由器。
動態路由選擇協議最重要的功能就是監測和補償拓撲變化——如果網絡的最優路徑不可用，協議必須尋找下一個最優路徑。
?
假設路由器監測到網絡10.1.5.0發生故障，將網絡標記為不可達并且在下一個更新周期通知路由器C。然后在路由器D更新計時器觸發更新之前，意外的事情發生了。路由器C的更新消息到達了路由器D，聲明路由器C可以到達網絡10.1.5.0，距離為1跳！
?
但是路由器D并不知道路由器C通告的下一條最優路徑并不合理，因而路由器D將跳數加1并在路由表中記錄一下信息：通過路由器C的接口（10.1.4.1）可以到達網絡10.1.5.0，距離為2條。
?
這樣路由器D查詢路由表又將數據包轉發給路由器C，路由器C再轉回給路由器D，一直無窮無盡地進行下去，因而導致路由環路的發生。
?
執行水平分隔可以阻止路由環路的發生。有兩類水平分隔方法：簡單水平分隔法和毒性逆轉水平分隔法。
?
簡單水平分隔的規則是：從某接口發送的更新消息不能包含從該接口收到的更新所包含的網絡。
?
簡單水平分隔采用的抑制信息的工作方式。毒性逆轉水平分隔法是一種改進方法，可以提供更積極的信息。
?
毒性逆轉水平分隔法的規則是：當更新信息被發送出某接口時，信息中將指定從該接口的更新信息中獲取的網絡是不可達的。
?
毒性逆轉水平分隔法被認為比簡單水平分隔法更安全更健壯——一種"壞信息總比沒有消息好"的方法。
?
大部分現代距離矢量算法的實現都是用了毒性逆轉水平分隔法。缺點是使路由器更新數據包更大了，可能會加劇鏈路的擁塞問題。
?
計數到無窮大
?
水平分隔法切斷的是鄰居路由器之間的環路，但是它不能隔斷網絡中的環路。可達網絡的距離在不斷地在路由器信息增大的時候會到無窮大。減輕計數到無窮大影響的方法是定義無窮大。大多數距離矢量協議定義無窮大為16跳。
?
隨著更新消息在路由器中轉圈，到某個不可達網絡的跳數會達到16，那時網絡被認為是不可達。
?
這也是路由器如何通告一個網絡不可達的方法。
設置最大跳數15有助于解決計數到無窮大的問題，但是收斂速度仍舊非常慢。假設更新周期為30s，網絡可能花7.5min達到收斂，在這期間容易受到路由錯誤的影響。觸發更新可以用于減少網絡收斂時間。
?
?
觸發更新
?
觸發更新（Triggered Update）又叫快速更新，非常簡單：如果一個度量變好或者變壞，那么路由器將立即發送更新信息，而不等更新計時超時。
?
?
抑制計時器
?
如果到一個目標的距離增加，那么路由器將為該路由設置抑制計時器。直到計時器超時，路由器才可以接受有關此路由的更新信息。
?
?
異步更新
?
?
一組連接在以太骨干網上的路由器，將不會同時廣播更新信息，因為會導致數據包發生碰撞。但是幾個路由器共享一個廣播網絡時可能會發生這種情況。
?
以下兩種方法維持異步更新（Asynchronous Update）：
- 每臺路由器的更新計時器獨立于路由選擇進程，因而不會受到路由器處理負載的影響
- 每個更新周期中加入一個小的隨機時間或定時抖動作為偏移
轉載于:https://www.cnblogs.com/tuhooo/p/7471548.html
總結
以上是生活随笔為你收集整理的动态路由选择协议（二）距离矢量路由选择协议的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Android 四大组件之Activit
- 下一篇： Nginx 作为 WebSockets