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

     以下內(nèi)容摘自剛剛上市，已被納入全國高校教材系統(tǒng)，并在全國熱銷、好評如潮的《深入理解計算機網(wǎng)絡(luò)》新書。

7.5.3  距離矢量路由算法

    現(xiàn)代計算機網(wǎng)絡(luò)通常使用動態(tài)路由算法，因為這類算法能夠適應(yīng)網(wǎng)絡(luò)的拓撲和流量變化，其中最流行的兩種動態(tài)路由算法是“距離矢量路由算法”和“鏈路狀態(tài)路由算法”。

    距離矢量路由算法（Distance Vector Routing，DV）是ARPANET網(wǎng)絡(luò)上最早使用的路由算法，也稱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)絡(luò)中各路由器所獲得的距離矢量信息在各路由器上統(tǒng)一起來，這樣各路由器只需要查看這個距離矢量表就可以為不同來源分組找到一條最佳的路由。

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

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

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

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

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

圖7-39 初始狀態(tài)下各結(jié)點的矢量表

   （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右圖所示。

圖7-40  B結(jié)點新的矢量表和路由表

   （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右圖所示。

圖7-41  C結(jié)點新的矢量表和路由表

  （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é)點的路徑。

圖7-42  D結(jié)點新的矢量表和路由表

   在這里有兩個要注意的地方：一是從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右圖所示。

圖7-43  E結(jié)點新的矢量表和路由表

    通過以上步驟，網(wǎng)絡(luò)中各路由器就完整了整個路由表的確定，當(dāng)然在拓撲結(jié)構(gòu)發(fā)生變化時，各路由器的路由表又會發(fā)生變化，重新進行更新。