[[122231]]

現(xiàn)代計(jì)算機(jī)網(wǎng)絡(luò)通常使用動(dòng)態(tài)路由算法，因?yàn)檫@類算法能夠適應(yīng)網(wǎng)絡(luò)的拓?fù)浜土髁孔兓渲?**的兩種動(dòng)態(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這種路由算法的。

“距離矢量路由算法”的基本思想如下：每個(gè)路由器維護(hù)一個(gè)距離矢量(通常是以延時(shí)是作變量的)表，然后通過相鄰路由器之間的距離矢量通告進(jìn)行距離矢量表的更新。每個(gè)距離矢量表項(xiàng)包括兩部分：到達(dá)目的結(jié)點(diǎn)的***輸出線路，和到達(dá)目的結(jié)點(diǎn)所需時(shí)間或距離，通信子網(wǎng)中的其它每個(gè)路由器在表中占據(jù)一個(gè)表項(xiàng)，并作為該表項(xiàng)的索引。每隔一段時(shí)間，路由器會(huì)向所有鄰居結(jié)點(diǎn)發(fā)送它到每個(gè)目的結(jié)點(diǎn)的距離表，同時(shí)它也接收每個(gè)鄰居結(jié)點(diǎn)發(fā)來的距離表。這樣以此類推，經(jīng)過一段時(shí)間后便可將網(wǎng)絡(luò)中各路由器所獲得的距離矢量信息在各路由器上統(tǒng)一起來，這樣各路由器只需要查看這個(gè)距離矢量表就可以為不同來源分組找到一條***的路由。

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

距離矢量路由算法簡單實(shí)例

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

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

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

初始狀態(tài)下各結(jié)點(diǎn)的矢量表

(2) 現(xiàn)在路由器A把它的路由表發(fā)給路由器B。此時(shí)它會(huì)綜合從A路由器發(fā)來的路由表和它自己的初始路由表，更新為一個(gè)新的矢量表，如圖7-40左圖所示(最終的矢量表如圖中深顏色部分)。從圖中可以看出，從B結(jié)點(diǎn)到達(dá)E結(jié)點(diǎn)此時(shí)存在兩條路徑，一條是直達(dá)的，一條是通過A結(jié)點(diǎn)到達(dá)的。而且這兩條線的開銷不同，經(jīng)過A結(jié)點(diǎn)到達(dá)E結(jié)點(diǎn)的開銷(7)比直達(dá)線路的開銷(8)更低，所以最終在形成的路由表中，把到達(dá)E結(jié)點(diǎn)的線路改為經(jīng)由A結(jié)點(diǎn)這條線路，如圖7-40右圖所示。

B結(jié)點(diǎn)新的矢量表和路由表

(3)B再把最終形成的路由表發(fā)給路由器C。同樣，路由器C也要把它原來的初始路由表與從B路由器發(fā)來的路由表進(jìn)行綜合，形成新的矢量表，如圖7-41左圖所示(最終的矢量表如圖中深顏色部分)。在新的矢量表中，除了最初的直接連接的B和D結(jié)點(diǎn)間的矢量外，還新收集了到達(dá)A和E結(jié)點(diǎn)的矢量信息。因?yàn)镃結(jié)點(diǎn)沒有與A和E結(jié)點(diǎn)的直接連接，在初始路由表中并沒有到達(dá)這兩個(gè)結(jié)點(diǎn)的路由信息，所以現(xiàn)在只有采用從B路由器發(fā)來的路由表中，經(jīng)過B結(jié)點(diǎn)到達(dá)A、E結(jié)點(diǎn)的路徑。#p#

這里要注意一點(diǎn)，因?yàn)樵贐結(jié)點(diǎn)路由表中就已識(shí)別了直接通過B結(jié)點(diǎn)到達(dá)E結(jié)點(diǎn)的開銷(8)還比依次通過B、A結(jié)點(diǎn)到達(dá)E結(jié)點(diǎn)的開銷(7)大，所以在C結(jié)點(diǎn)路由表中是采用依次通過B、A結(jié)點(diǎn)到達(dá)E結(jié)點(diǎn)這條路徑。最終形成的路由表如圖7-41右圖所示。

C結(jié)點(diǎn)新的矢量表和路由表

(4)路由器 C再把它的最終路由表發(fā)給路由器D。同樣，路由器D也要把它原來的初始路由表與從C路由器發(fā)來的路由表進(jìn)行綜合，形成新的矢量表，如圖7-42左圖所示(最終的矢量表如圖中深顏色部分)。在新的矢量表中，除了最初的直接連接的C和E結(jié)點(diǎn)間的矢量信息外，還新收集了到達(dá)A和B結(jié)點(diǎn)的矢量信息。因?yàn)镈結(jié)點(diǎn)沒有與A和B結(jié)點(diǎn)的直接連接，所以在其最初的路由表中并沒有到達(dá)這兩個(gè)結(jié)點(diǎn)的矢量信息，此時(shí)仍采用經(jīng)過C結(jié)點(diǎn)到達(dá)A和B結(jié)點(diǎn)的路徑。

在這里同樣要注意一點(diǎn)，從D結(jié)點(diǎn)到達(dá)E結(jié)點(diǎn)也有兩條路徑：一是直接到達(dá)，二是依次通過C、B、A結(jié)點(diǎn)到達(dá)，經(jīng)過比較發(fā)現(xiàn)直接連接到達(dá)的開銷(2)要比通過C、B、A結(jié)點(diǎn)到達(dá)E結(jié)點(diǎn)路徑的開銷(10)要小，所以在D結(jié)點(diǎn)中，到達(dá)E結(jié)點(diǎn)是采用直接連接這條線路。最終形成的路由表如圖7-42右圖所示。

(5)路由器 D再把它的最終路由表發(fā)給路由器E。同樣，路由器E也要把它原來的初始路由表與從D路由器發(fā)來的路由表進(jìn)行綜合，形成新的矢量表，如圖7-43左圖所示(最終的矢量表如圖中深顏色部分)。在新的矢量表中，除了最初的直接連接的A、B和D結(jié)點(diǎn)間的矢量外，還新收集了到達(dá)C結(jié)點(diǎn)的矢量信息，因?yàn)镋結(jié)點(diǎn)沒有與C結(jié)點(diǎn)的直接連接。此時(shí)仍采用經(jīng)過D結(jié)點(diǎn)到達(dá)C結(jié)點(diǎn)的路徑。

D結(jié)點(diǎn)新的矢量表和路由表

在這里有兩個(gè)要注意的地方：一是從E結(jié)點(diǎn)到達(dá)A結(jié)點(diǎn)的路徑問題，因?yàn)榇藭r(shí)E結(jié)點(diǎn)與A結(jié)點(diǎn)是直接連接的，而且其開銷(1)要比原來從D路由口器發(fā)來的路由表中提供的通過D、C、B結(jié)點(diǎn)到達(dá)A結(jié)點(diǎn)路徑開銷(11)要小，所以在最終的E結(jié)點(diǎn)路由表中，到達(dá)A結(jié)點(diǎn)是采用直接連接這條線路。二是E結(jié)點(diǎn)雖然也是與B結(jié)點(diǎn)直接連接，但它的開銷(8)還要比原來從D路由器發(fā)來的路由表中提供的依次經(jīng)過D、C這兩個(gè)結(jié)點(diǎn)到達(dá)B結(jié)點(diǎn)的開銷(5)大，所以在最終的E結(jié)點(diǎn)路由表中，到達(dá)B結(jié)點(diǎn)是采用依次經(jīng)過D、C兩個(gè)結(jié)點(diǎn)這條路徑。最終形成的路由表如圖7-43右圖所示。

E結(jié)點(diǎn)新的矢量表和路由表

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