示例演示“距離矢量路由算法”工作原理

     以下內容摘自剛剛上市，已被納入全國高校教材系統，并在全國熱銷、好評如潮的《深入理解計算機網絡》新書。

7.5.3  距離矢量路由算法

    現代計算機網絡通常使用動態路由算法，因為這類算法能夠適應網絡的拓撲和流量變化，其中最流行的兩種動態路由算法是“距離矢量路由算法”和“鏈路狀態路由算法”。

    距離矢量路由算法（Distance Vector Routing，DV）是ARPANET網絡上最早使用的路由算法，也稱Bellman-Ford路由算法和Ford-Fulkerson算法，主要在RIP（Route Information Protocol）協議中使用。Cisco的IGRP和EIGRP路由協議也是采用DV這種路由算法的。

    “距離矢量路由算法”的基本思想如下：每個路由器維護一個距離矢量（通常是以延時是作變量的）表，然后通過相鄰路由器之間的距離矢量通告進行距離矢量表的更新。每個距離矢量表項包括兩部分：到達目的結點的最佳輸出線路，和到達目的結點所需時間或距離，通信子網中的其它每個路由器在表中占據一個表項，并作為該表項的索引。每隔一段時間，路由器會向所有鄰居結點發送它到每個目的結點的距離表，同時它也接收每個鄰居結點發來的距離表。這樣以此類推，經過一段時間后便可將網絡中各路由器所獲得的距離矢量信息在各路由器上統一起來，這樣各路由器只需要查看這個距離矢量表就可以為不同來源分組找到一條最佳的路由。

    現假定用延時作為距離的度量，舉一個簡單的例子，如圖7-37所示。假設某個時候路由器Y收到其鄰居路由器X的距離矢量，其中m是Y估計到達路由器X的延時。若Y路由器知道它到鄰居Z的延時為n，那么它可以得知Z通過Y到達X需要花費時間m+n。如果Z路由器還有其他相鄰路由器，則對于從其他每個鄰居那兒收到的距離矢量，該路由器執行同樣的計算，最后從中選擇費時最小的路由作為Z去往X的最佳路由，然后更新其路由表，并通告給其鄰居路由器。

圖7-37  距離矢量路由算法簡單實例

    現以一個如圖7-38所示的示例介紹距離矢量算法中的路由的確定流程，各段鏈路的延時均已在圖中標注。A、B、C、D、E代表五個路由器，假設路由表的傳遞方向為：A → B → C → D → E（這與路由器啟動的先后次序有關）。下面具體的流程。 

   （1）初始狀態下，各路由器都只收集直接相連的鏈路的延時信息，各路由器結點得出各自的初始矢量表如圖7-39所示。因為各結點間還沒有交換路由信息，所以它們的初始狀態的路由表也如它們的矢量表。　

圖7-38 距離矢量算法路由確定示例

圖7-39 初始狀態下各結點的矢量表

   （2） 現在路由器A把它的路由表發給路由器B。此時它會綜合從A路由器發來的路由表和它自己的初始路由表，更新為一個新的矢量表，如圖7-40左圖所示（最終的矢量表如圖中深顏色部分）。從圖中可以看出，從B結點到達E結點此時存在兩條路徑，一條是直達的，一條是通過A結點到達的。而且這兩條線的開銷不同，經過A結點到達E結點的開銷（7）比直達線路的開銷（8）更低，所以最終在形成的路由表中，把到達E結點的線路改為經由A結點這條線路，如圖7-40右圖所示。

圖7-40  B結點新的矢量表和路由表

   （3）B再把最終形成的路由表發給路由器C。同樣，路由器C也要把它原來的初始路由表與從B路由器發來的路由表進行綜合，形成新的矢量表，如圖7-41左圖所示（最終的矢量表如圖中深顏色部分）。在新的矢量表中，除了最初的直接連接的B和D結點間的矢量外，還新收集了到達A和E結點的矢量信息。因為C結點沒有與A和E結點的直接連接，在初始路由表中并沒有到達這兩個結點的路由信息，所以現在只有采用從B路由器發來的路由表中，經過B結點到達A、E結點的路徑。

    這里要注意一點，因為在B結點路由表中就已識別了直接通過B結點到達E結點的開銷（8）還比依次通過B、A結點到達E結點的開銷（7）大，所以在C結點路由表中是采用依次通過B、A結點到達E結點這條路徑。最終形成的路由表如圖7-41右圖所示。

圖7-41  C結點新的矢量表和路由表

  （4）路由器 C再把它的最終路由表發給路由器D。同樣，路由器D也要把它原來的初始路由表與從C路由器發來的路由表進行綜合，形成新的矢量表，如圖7-42左圖所示（最終的矢量表如圖中深顏色部分）。在新的矢量表中，除了最初的直接連接的C和E結點間的矢量信息外，還新收集了到達A和B結點的矢量信息。因為D結點沒有與A和B結點的直接連接，所以在其最初的路由表中并沒有到達這兩個結點的矢量信息，此時仍采用經過C結點到達A和B結點的路徑。

   在這里同樣要注意一點，從D結點到達E結點也有兩條路徑：一是直接到達，二是依次通過C、B、A結點到達，經過比較發現直接連接到達的開銷（2）要比通過C、B、A結點到達E結點路徑的開銷（10）要小，所以在D結點中，到達E結點是采用直接連接這條線路。最終形成的路由表如圖7-42右圖所示。

   （5）路由器 D再把它的最終路由表發給路由器E。同樣，路由器E也要把它原來的初始路由表與從D路由器發來的路由表進行綜合，形成新的矢量表，如圖7-43左圖所示（最終的矢量表如圖中深顏色部分）。在新的矢量表中，除了最初的直接連接的A、B和D結點間的矢量外，還新收集了到達C結點的矢量信息，因為E結點沒有與C結點的直接連接。此時仍采用經過D結點到達C結點的路徑。

圖7-42  D結點新的矢量表和路由表

   在這里有兩個要注意的地方：一是從E結點到達A結點的路徑問題，因為此時E結點與A結點是直接連接的，而且其開銷（1）要比原來從D路由口器發來的路由表中提供的通過D、C、B結點到達A結點路徑開銷（11）要小，所以在最終的E結點路由表中，到達A結點是采用直接連接這條線路。二是E結點雖然也是與B結點直接連接，但它的開銷（8）還要比原來從D路由器發來的路由表中提供的依次經過D、C這兩個結點到達B結點的開銷（5）大，所以在最終的E結點路由表中，到達B結點是采用依次經過D、C兩個結點這條路徑。最終形成的路由表如圖7-43右圖所示。

圖7-43  E結點新的矢量表和路由表

    通過以上步驟，網絡中各路由器就完整了整個路由表的確定，當然在拓撲結構發生變化時，各路由器的路由表又會發生變化，重新進行更新。