現(xiàn)代計算機網(wǎng)絡通常使用動態(tài)路由算法，因為這類算法能夠適應網(wǎng)絡的拓撲和流量變化，其中最流行的兩種動態(tài)路由算法是“距離矢量路由算法”和“鏈路狀態(tài)路由算法”。
距離矢量路由算法（Distance Vector Routing，DV）是ARPANET網(wǎng)絡上最早使用的路由算法，也稱Bellman-Ford路由算法和Ford-Fulkerson算法，主要在RIP（Route Information Protocol）協(xié)議中使用。Cisco的IGRP和EIGRP路由協(xié)議也是采用DV這種路由算法的。
“距離矢量路由算法”的基本思想如下：每個路由器維護一個距離矢量（通常是以延時是作變量的）表，然后通過相鄰路由器之間的距離矢量通告進行距離矢量表的更新。每個距離矢量表項包括兩部分：到達目的結(jié)點的最佳輸出線路，和到達目的結(jié)點所需時間或距離，通信子網(wǎng)中的其它每個路由器在表中占據(jù)一個表項，并作為該表項的索引。每隔一段時間，路由器會向所有鄰居結(jié)點發(fā)送它到每個目的結(jié)點的距離表，同時它也接收每個鄰居結(jié)點發(fā)來的距離表。這樣以此類推，經(jīng)過一段時間后便可將網(wǎng)絡中各路由器所獲得的距離矢量信息在各路由器上統(tǒng)一起來，這樣各路由器只需要查看這個距離矢量表就可以為不同來源分組找到一條最佳的路由。
現(xiàn)假定用延時作為距離的度量，舉一個簡單的例子，如圖7-37所示。假設某個時候路由器Y收到其鄰居路由器X的距離矢量，其中m是Y估計到達路由器X的延時。若Y路由器知道它到鄰居Z的延時為n，那么它可以得知Z通過Y到達X需要花費時間m+n。如果Z路由器還有其他相鄰路由器，則對于從其他每個鄰居那兒收到的距離矢量，該路由器執(zhí)行同樣的計算，最后從中選擇費時最小的路由作為Z去往X的最佳路由，然后更新其路由表，并通告給其鄰居路由器。
現(xiàn)以一個如圖7-38所示的示例介紹距離矢量算法中的路由的確定流程，各段鏈路的延時均已在圖中標注。A、B、C、D、E代表五個路由器，假設路由表的傳遞方向為：A → B → C → D → E（這與路由器啟動的先后次序有關）。下面具體的流程。
（1）初始狀態(tài)下，各路由器都只收集直接相連的鏈路的延時信息，各路由器結(jié)點得出各自的初始矢量表如圖7-39所示。因為各結(jié)點間還沒有交換路由信息，所以它們的初始狀態(tài)的路由表也如它們的矢量表。
（2） 現(xiàn)在路由器A把它的路由表發(fā)給路由器B。此時它會綜合從A路由器發(fā)來的路由表和它自己的初始路由表，更新為一個新的矢量表，如圖7-40左圖所示（最終的矢量表如圖中深顏色部分）。從圖中可以看出，從B結(jié)點到達E結(jié)點此時存在兩條路徑，一條是直達的，一條是通過A結(jié)點到達的。而且這兩條線的開銷不同，經(jīng)過A結(jié)點到達E結(jié)點的開銷（7）比直達線路的開銷（8）更低，所以最終在形成的路由表中，把到達E結(jié)點的線路改為經(jīng)由A結(jié)點這條線路，如圖7-40右圖所示。
（3）B再把最終形成的路由表發(fā)給路由器C。同樣，路由器C也要把它原來的初始路由表與從B路由器發(fā)來的路由表進行綜合，形成新的矢量表，如圖7-41左圖所示（最終的矢量表如圖中深顏色部分）。在新的矢量表中，除了最初的直接連接的B和D結(jié)點間的矢量外，還新收集了到達A和E結(jié)點的矢量信息。因為C結(jié)點沒有與A和E結(jié)點的直接連接，在初始路由表中并沒有到達這兩個結(jié)點的路由信息，所以現(xiàn)在只有采用從B路由器發(fā)來的路由表中，經(jīng)過B結(jié)點到達A、E結(jié)點的路徑。
這里要注意一點，因為在B結(jié)點路由表中就已識別了直接通過B結(jié)點到達E結(jié)點的開銷（8）還比依次通過B、A結(jié)點到達E結(jié)點的開銷（7）大，所以在C結(jié)點路由表中是采用依次通過B、A結(jié)點到達E結(jié)點這條路徑。最終形成的路由表如圖7-41右圖所示。
（4）路由器 C再把它的最終路由表發(fā)給路由器D。同樣，路由器D也要把它原來的初始路由表與從C路由器發(fā)來的路由表進行綜合，形成新的矢量表，如圖7-42左圖所示（最終的矢量表如圖中深顏色部分）。在新的矢量表中，除了最初的直接連接的C和E結(jié)點間的矢量信息外，還新收集了到達A和B結(jié)點的矢量信息。因為D結(jié)點沒有與A和B結(jié)點的直接連接，所以在其最初的路由表中并沒有到達這兩個結(jié)點的矢量信息，此時仍采用經(jīng)過C結(jié)點到達A和B結(jié)點的路徑。
在這里同樣要注意一點，從D結(jié)點到達E結(jié)點也有兩條路徑：一是直接到達，二是依次通過C、B、A結(jié)點到達，經(jīng)過比較發(fā)現(xiàn)直接連接到達的開銷（2）要比通過C、B、A結(jié)點到達E結(jié)點路徑的開銷（10）要小，所以在D結(jié)點中，到達E結(jié)點是采用直接連接這條線路。最終形成的路由表如圖7-42右圖所示。
（5）路由器 D再把它的最終路由表發(fā)給路由器E。同樣，路由器E也要把它原來的初始路由表與從D路由器發(fā)來的路由表進行綜合，形成新的矢量表，如圖7-43左圖所示（最終的矢量表如圖中深顏色部分）。在新的矢量表中，除了最初的直接連接的A、B和D結(jié)點間的矢量外，還新收集了到達C結(jié)點的矢量信息，因為E結(jié)點沒有與C結(jié)點的直接連接。此時仍采用經(jīng)過D結(jié)點到達C結(jié)點的路徑。
[圖片上傳失敗...(image-bff063-1512007535554)]
在這里有兩個要注意的地方：一是從E結(jié)點到達A結(jié)點的路徑問題，因為此時E結(jié)點與A結(jié)點是直接連接的，而且其開銷（1）要比原來從D路由口器發(fā)來的路由表中提供的通過D、C、B結(jié)點到達A結(jié)點路徑開銷（11）要小，所以在最終的E結(jié)點路由表中，到達A結(jié)點是采用直接連接這條線路。二是E結(jié)點雖然也是與B結(jié)點直接連接，但它的開銷（8）還要比原來從D路由器發(fā)來的路由表中提供的依次經(jīng)過D、C這兩個結(jié)點到達B結(jié)點的開銷（5）大，所以在最終的E結(jié)點路由表中，到達B結(jié)點是采用依次經(jīng)過D、C兩個結(jié)點這條路徑。最終形成的路由表如圖7-43右圖所示。
通過以上步驟，網(wǎng)絡中各路由器就完整了整個路由表的確定，當然在拓撲結(jié)構(gòu)發(fā)生變化時，各路由器的路由表又會發(fā)生變化，重新進行更新。
當形成環(huán)路或者有一些路由器連接斷裂時，就會產(chǎn)生無窮計算問題
==為了避免無窮計算，RIP協(xié)議規(guī)定路由的最大METRIC為15跳，大于15跳表示網(wǎng)絡不可達。這種規(guī)定限制的RIP的應用范圍， 它只能適用于中小網(wǎng)絡，網(wǎng)絡規(guī)模太大路由信息就無法到達遠端的路由器了。==
==同時， RIP協(xié)議在實現(xiàn)中還使用了帶毒性逆轉(zhuǎn)的水平分割技術。所謂水平分割是指從某一個鄰居獲得的路由信息不再向這個鄰居發(fā)送回去。而毒性逆轉(zhuǎn)則是將這樣的路由信息METRIC置為無窮大，大于或等于16 在發(fā)送回去。==
這兩種措施都是為了讓路由器不收到從自己發(fā)送出去的循環(huán)路由而產(chǎn)生錯誤路由，保持法，將不可達的路由信息在路由表中保持一段時間，以盡可能的擴展最壞情況
毒性逆轉(zhuǎn)是指發(fā)出一條路由，路由的METRIC為無窮大（16跳），作用是通知別的路由器，這條路由已經(jīng)不可達了。
好處：收到一條壞消息好過沒有收到任何消息，也就是有消息好過沒有消息。可以取代保持機制來加快路由收斂。
壞處：過多地浪費了鏈路的帶寬，增大了路由表的大小。
結(jié)論：通常情況下，不提倡使用，因為會增大路由表，浪費鏈路帶寬。
水平分割也有二種：普通水平分割和帶毒性逆轉(zhuǎn)的水平分割。
普通水平分割：從一個接口收到的路由不會再從這個接口泛洪出去。
帶毒性逆轉(zhuǎn)的水平分割：從一個接口收到的路由，會從這個接口泛洪出去，但這條路由的METRIC是無窮大。
好處：有消息勝過無消息，即使是一條壞消息。
原文地址：http://blog.csdn.net/u013007900/article/details/45565389
