路由向量演算法

㈠ 路由演算法

路由演算法是網路層軟體的一部分。子網提供數據報服務，每個包都要做路由選擇；子網提供虛電路服務，只需在建立連接時做一次路由選擇

正確性，簡單性，健壯性（魯棒性，網路出現意外情況時候的解決問題的能力。例如突然某個路由器停電了，使得周邊的路由器都沒法正常工作，如果出現這樣的問題說明路由器的健壯性不夠），穩定性（常規使用是否穩定，數據量增多的時候能否正常工作），公平性（網路資源的使用是否公平，避免有些節點出現特別繁忙的狀態，而有些節點總是處於很閑的狀態），最優性

• 按轉發方式和數據副本數量劃分
1.全路路由（廣播路由）演算法：如洪泛演算法，按照所有路徑廣播轉發（中間轉發節點以及目標節點都會送到很多重復數據。不需要路由表和路由控制功能）
2.多路路由演算法：向所有接近目的節點的路徑轉發（中間轉發節點以及目標節點都會送到很多重復數據。）
3.單路路由演算法：如距離矢量演算法，向目的節點沿著唯一的路徑轉發（中間的轉發節點只轉發一份數據即可）

• 按健壯性和簡單性劃分
1.非自適應演算法（靜態路由演算法）：不能根據網路流量和拓撲結構的變化更新路由表，使用靜態路由表。需要人為的更改和設定。特點是簡單、開銷小、靈活性差。典型演算法為基於流量的路由演算法等
2.自適應演算法（動態路由演算法）：可根據網路流量（網路承載的數據量）和拓撲結構的變化更新路由表。特點是開銷大、健壯性和靈活性好。典型演算法為距離向量路由演算法、鏈路狀態路由演算法等

☆可以靜態路由和動態路由結合起來使用，此時靜態路由的優先順序別較高

測量（獲取）有關路由選擇的網路度量參數（選擇最優，比如是要求傳播距離最短，還是要求傳輸時延短等）。如何測量？選取哪些網路參數？
將路由信息傳送到適當的網路節點。傳送給誰？如何傳送？傳送什麼信息？
計算和更新路由表。更新路由表的演算法
根據新路由表執行分組的轉發

如果路由器J在路由器I到K的最優路由上，那麼從J到K的最優路由一定落在同一路由上

從所有的源節點到一個給定的目的節點的最優路由的集合形成了一個以目的節點為根的樹，稱為匯集樹；路由演算法的目的是找出並使用匯集樹

基本思想：構建子網的拓撲圖，圖中的每個節點代表一個路由器，每條弧代表一條通信線路。為了選擇兩個路由器間的路由，演算法需要在圖中找出節點間的最短路徑

節點數量；地理距離；傳輸延遲；距離、信道帶寬等參數的加權函數

網路規模增大帶來的問題：路由器中的路由表增大；路由器為選擇路由而佔用的內存、CPU時間和網路帶寬增大
分層路由：分而治之的思想；根據需要，將路由器分成區域、聚類、區和組；Fig.6-6，路由表由17項減為7項
分層路由帶來的問題：路由表中的路由不一定是最優路由

☆分層路由功能大部分時候性能是比較好的，可以選擇最優路徑，但是有時也會選擇到非最優路徑。比如上圖中如果想從1A到5C，應該是1A→1B→2A→2B→2D→5C是比較優的選擇，但是按照1A的分層路由表顯示，從區域1到區域5出口線路為1C，因此選擇的路線為1A→1C→3B→4A→5A→5B→5C，這時就相對繞遠了

DVR - Distance Vector Routing
動態路由演算法，也稱Bellman - Ford路由演算法或Ford - Fulkerson演算法，最初用於ARPANET（Internet的前身），被RIP協議所採用

每個路由器維護一張路由表，表中給出了到每個目的地的已知最佳距離和線路，並通過與相鄰路由器交換距離信息來更新表；每隔一段時間，路由器向所有鄰居節點發送它到每個目的節點的距離表，同時它也接收每個鄰居節點發來的距離表；鄰居節點X發來的表中，X到路由器I的距離為Xi，本路由器到X的距離為m，則路由器經過X到i的距離為Xi + m。根據不同鄰居發來的信息，計算Xi + m，並取最小值，更新本路由器的路由表

圖1：
此時路由A把它的路由表發給路由B，B會綜合從A得來的路由表來更新自己的矢量表↓
根據初始A矢量表和B矢量表得知B到A為6，B到C為1，B到D沒有；兩個表都有到E的距離，直接從B到E為8；如果B經由A再到E就要計算A到B的距離加上A到E的距離即可，即6+1=7

圖2：
B把路由表發給C之後↓
從C的初始矢量表可得知C到B為1，C到D為2，C無法直接到A，但是通過B的路由表得知B到A為6，再加上C到B的距離1，得出C到A距離為7，同理可得到E距離為7+1=8

圖3：
C把路由表發給D之後↓

圖4：
D把路由表發給E之後↓

J的相鄰節點為4個，分別為A，I，H，K，因此可以選擇的路線也為4種
現在要求J的最新路由表。以J到E為例，J到A為8，A到E為14，和為22；J到I為10，I到E為7，和為17；J到H為12，H到E為30，和為42；J到K為6，K到E為22，和為28。從而得出，經由I的時候得到的和17最小，因此在新生成的J到E的位置記錄17

無限計算問題：對好消息反應迅速，對壞消息反應遲鈍

比如從E到A，E剛開始連通的時候是不知道如何才能到A的，只有通過B與A交互，C與B交互這樣最終E通過與D交互才知道如何能到A，這就是好消息。可能需要花些時間，但是結果都是無論目的節點是哪裡總會找到路徑

壞消息例子：A，B，C之間通信。B到A的距離為1（A，1），C到A的距離為2（B（經B），2）。各個節點都會有一個刷新周期，到了這個周期的時候每個節點會把自己的路由信息發給其相鄰節點。例如A路由斷開連接，這個時候B到A的線路斷開。也就是B到A的距離為無窮大了（A，∞）。如果在B把這個信息反饋給C之前，C先把路由信息告訴B了，那麼B收到的信息就為（C，3）。因為A已經不存在，而B從C處得知通過C有路徑可以到達A，這時B的路由表就變成（C，3），同樣的這時B再告訴C，C就會變成（B，4），就會這樣無窮計算下去。如果一開始是B先把信息發給C就不會發生這樣的問題

• 觸發式更新：節點不等到刷新周期的到來，只要有突發情況馬上就會把情況通知相鄰路由
• 水平分割：因為一開始C是從B得知經過B可以到達A的，所以用了這種方法之後，C就不會再向B發送如何到A，而只等著B給C發如何到A了。這樣就不會有無窮計算問題
• 定義一個最大值：壞消息例子當中，括弧里後面的數會一直循環增長下去，如果把這個數字設置一個最大值，那麼當循環到這個最大值的時候雙方就不會再就怎麼到A的信息進行交互了，就不會發生無窮計算的情況
• 掛起計數器：壞消息例子當中，B收到了C的路由最新信息（C，3）的時候這個不會馬上生效刷新，（A，∞）會保留兩個周期，在這兩個周期裡面，B肯定有機會給C發送（A，∞），
而因為C沒有通往A的路徑，所以當C到刷新周期的時候給B發的就為（B，∞）。B前後收到的信息不一致，但是第二次收到的信息和B發給C的信息是一致的，所以B就會認為第一次收到的（C，3）是無效的。但是如果C真的有了一條通往A的線路，這時兩次發的信息一定是一致的，那麼B就會相信C的信息，從而把（A，∞）刷新成C給B的信息

❉距離向量路由演算法只適用於小規模網路，每個節點不清楚整個網路的拓撲結構

發現鄰居節點，並學習它們的網路地址，測量到每個鄰居節點的延遲或開銷，將所有學習到的內容封裝成一個鏈路狀態包（包以發送方的標識符開頭，後面是序號、年齡和一個鄰居節點列表；鏈路狀態包定期創建或發生重大事件時創建）。將鏈路狀態包廣播發送給所有其他路由器【洪泛方式：狀態包包含一個序號，每次發送新包時加1。路由器記錄信息對（源路由器，序號），當一個鏈路狀態包到達時，若是新的則分發，若是重復的則丟棄，若序號比路由記錄中的最大序號小則認為過時而丟棄】。計算到每個其他路由器的最短路徑

☆鏈路狀態路由演算法適用於大規模網路。每個節點都會了解其他節點的局部拓撲，因此就會了解整個網路的拓撲結構，這時當前節點就能找到到目的節點的最優路由

• 使用32位序號。
因為序號是循環使用的，如果位數很少，比如只是1~7，那麼7不一定比1大，1有可能是下一輪的第一個數。而32位的時候因為數字特別龐大，不會出現這樣問題
• 增加年齡域，每秒鍾年齡減1，為零則丟棄
比如A發給B （C，4），由於差錯，本來是（C，5）的下一個包，變成了（C，1000）。這之後來的（C，6），（C，7）。。。都沒有（C，1000）大，因此包會被丟棄。但其實後面到的包都是新的。為了避免這樣的問題發生，（C，1000）里的1000就會在每一秒減1，直到年齡比新到的包小，接下來就可以正常接包了。不過這之前到的包都會被丟棄，這也是沒有辦法的事
• 鏈路狀態包到達後，延遲一段時間，並與其它已到達的來自同一路由器的鏈路狀態包比較序號，丟棄重復包，保留新包
• 鏈路狀態包需要應答
為了保證數據傳輸的可靠性

㈡ 計算機網路中的路由器使用距離向量演算法

1、假設路由器使用距離向量演算法，下圖給出了網路拓撲及路由器的初始路由表（只包含部分欄位），假設A給B傳了一次路由信息，B處理後又也給C傳了一次路由信息，請在表中填寫經過路由信息交換之後B和C的路由表（相鄰路由器間距離計為1）。
2、B路由器增加2條：10.3.0.0 s0 1
10.4.0.0 s1 1
3、C路由器增加2條：10.3.0.0 s0 2
10.2.0.0 S0 1

㈢ 路由演算法的類型有

路由演算法有很多種，如果從路由表對網路拓撲和通信量變化的自適應能力的角度劃分，可以分為靜態路由演算法和動態路由演算法兩大類，這兩大類又可細分為幾種小類型，比較典型常見的有以下幾種：

一、靜態路由演算法

1.Dijkstra演算法（最短路徑演算法）

Dijkstra(迪傑斯特拉)演算法是典型的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法是很有代表性的最短路徑演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN,CLOSE表的方式，這里均採用永久和臨時標號的方式。注意該演算法要求圖中不存在負權迴路。

Dijkstra演算法執行步驟如下：

步驟一：路由器建立一張網路圖，並且確定源節點和目的節點，在這個例子里我們設為V1和V2。然後路由器建立一個矩陣，稱為「鄰接矩陣」。在這個矩陣中，各矩陣元素表示權值。例如，[i,j]是節點Vi與Vj之間的鏈路權值。如果節點Vi與Vj之間沒有鏈路直接相連，它們的權值設為「無窮大」。

步驟二：路由器為網路中的每一個節點建立一組狀態記錄。此記錄包括三個欄位：

前序欄位———表示當前節點之前的節點。

長度欄位———表示從源節點到當前節點的權值之和。

標號欄位———表示節點的狀態。每個節點都處於一個狀態模式：「永久」或「暫時」。

步驟三：路由器初始化（所有節點的）狀態記錄集參數，將它們的長度設為「無窮大」，標號設為「暫時」。

步驟四：路由器設置一個T節點。例如，如果設V1是源T節點，路由器將V1的標號更改為「永久」。當一個標號更改為「永久」後，它將不再改變。一個T節點僅僅是一個代理而已。

步驟五：路由器更新與源T節點直接相連的所有暫時性節點的狀態記錄集。

步驟六：路由器在所有的暫時性節點中選擇距離V1的權值最低的節點。這個節點將是新的T節點。

步驟七：如果這個節點不是V2（目的節點），路由器則返回到步驟5。

步驟八：如果節點是V2，路由器則向前回溯，將它的前序節點從狀態記錄集中提取出來，如此循環，直到提取到V1為止。這個節點列表便是從V1到V2的最佳路由。

2.擴散法
事先不需要任何網路信息；路由器把收到的每一個分組，向除了該分組到來的線路外的所有輸出線路發送。將來會有多個分組的副本到達目的地端，最先到達的，可能是走了「最優」的路徑常見的擴散法是選擇性擴散演算法。

3.LS演算法

採用LS演算法時，每個路由器必須遵循以下步驟：

步驟一：確認在物理上與之相連的路由器並獲得它們的IP地址。當一個路由器開始工作後，它首先向整個網路發送一個「HELLO」分組數據包。每個接收到數據包的路由器都將返回一條消息，其中包含它自身的IP地址。

步驟二：測量相鄰路由器的延時（或者其他重要的網路參數，比如平均流量）。為做到這一點，路由器向整個網路發送響應分組數據包。每個接收到數據包的路由器返回一個應答分組數據包。將路程往返時間除以2，路由器便可以計算出延時。（路程往返時間是網路當前延遲的量度，通過一個分組數據包從遠程主機返回的時間來測量。）該時間包括了傳輸和處理兩部分的時間——也就是將分組數據包發送到目的地的時間以及接收方處理分組數據包和應答的時間。

步驟三：向網路中的其他路由器廣播自己的信息，同時也接收其他路由器的信息。

在這一步中，所有的路由器共享它們的知識並且將自身的信息廣播給其他每一個路由器。這樣，每一個路由器都能夠知道網路的結構以及狀態。

步驟四：使用一個合適的演算法，確定網路中兩個節點之間的最佳路由。

路由演算法有哪些類型？路由演算法與路由協議的區別

在這一步中，路由器選擇通往每一個節點的最佳路由。它們使用一個演算法來實現這一點，如Dijkstra最短路徑演算法。在這個演算法中，一個路由器通過收集到的其他路由器的信息，建立一個網路圖。這個圖描述網路中的路由器的位置以及它們之間的鏈接關系。每個鏈接都有一個數字標注，稱為權值或成本。這個數字是延時和平均流量的函數，有時它僅僅表示節點間的躍點數。例如，如果一個節點與目的地之間有兩條鏈路，路由器將選擇權值最低的鏈路。

二、動態路由演算法

1.距離向量路由演算法

距離向量路由演算法，也叫做最大流量演演算法，其被距離向量協議作為一個演算法，如RIP、BGP、ISO IDRP、NOVELL IPX。使用這個演算法的路由器必須掌握這個距離表(它是一個一維排列-「一個向量」)，它告訴在網路中每個節點的最遠和最近距離。在距離表中的這個信息是根據臨近接點信息的改變而時時更新的。表中數據的量和在網路中的所有的接點(除了它自己本身)是等同的。這個表中的列代表直接和它相連的鄰居，行代表在網路中的所有目的地。每個數據包括傳送數據包到每個在網上的目的地的路徑和距離/或時間在那個路徑上來傳輸(我們叫這個為「成本」)。這個在那個演算法中的度量公式是跳躍的次數，等待時間，流出數據包的數量，等等。在距離向量路由演算法中，相鄰路由器之間周期性地相互交換各自的路由表備份。當網路拓撲結構發生變化時，路由器之間也將及時地相互通知有關變更信息。其優點是演算法簡單容易實現。缺點是慢收斂問題，路由器的路徑變化需要像波浪一樣從相鄰路由器傳播出去，過程緩慢。

每一個相鄰路由器發送過來的路由表都要經過以下步驟：

步驟一：對地址為X的路由器發過來的路由表，先修改此路由表中的所有項目：把」下一跳」欄位中的地址改為X，並把所有」距離」欄位都加1。

步驟二：對修改後的路由表中的每一個項目，進行以下步驟：

（1）將X的路由表(修改過的)，與S的路由表的目的網路進行對比。若在X中出現，在S中沒出現，則將X路由表中的這一條項目添加到S的路由表中。

（2）對於目的網路在S和X路由表中都有的項目進行下面步驟：

1）在S的路由表中，若下一跳地址是x，則直接用X路由表中這條項目替換S路由表中的項目。

2）在S的路由表中，若下一跳地址不是x，若X路由表項目中的距離d小於S路由表中的距離，則進行更新。

步驟三：若3分鍾還沒有收到相鄰路由器的更新表，則把此相鄰路由器記為不可到達路由器，即把距離設置為16。

2.鏈路狀態最短路由優先演算法SPF

1）發現鄰居結點，並學習它們的網路地址；

2）測量到各鄰居節點的延遲或者開銷；

3）創建鏈路狀態分組；

4）使用擴散法發布鏈路狀態分組；

5）計算到每個其它路由器的最短路徑。

㈣ 距離矢量協議的路由演算法

距離矢量路由演算法是動態路由演算法。它是這樣工作的：每個路由器維護一張矢量表，表中列出了當前已知的到 每個目標的最佳距離，以及所使用的線路。通過在鄰居之間相互交換信息，路由器不斷地更新它們內部的表。
距離矢量路由演算法最常見的是Ford－Fulkerson演算法。該演算法的核心思想是使用標號的方法不斷尋找一個圖上的 可增廣路徑並且進行調整，直到找不到可增廣路徑為止。距離矢量路由演算法號召每個路由器在每次更新時發送它 的整個路由表，但僅僅給它的鄰居。距離矢量路由演算法傾向於路由循環，但比鏈路狀態路由演算法計算更簡單。
演算法描述如下：
給定帶杈有向圖G和源點s，求從s到G中任意頂點v的最短路徑，該演算法通過在一個路由中重申跳數的個數九來尋 找一個最短路徑生成樹。
在距離矢量路由選擇演算法中，每個路由器維持有一張子網中每一個以其他路由器為索引的路由選擇表，表中的 每一個項目都對應於子網中的每個路由器。此表項包括兩個部分，即希望使用的到目的地的輸出線路和估計到達 目的地所需時間或距離。用度量標准可為站點，估計的時間延遲（ms），該路出排隊的分組估計總數或類似的值。
假定路由器知道它到每個相鄰路由器的「距離」。如果度量標准為站點，其距離就為一個站點；如果度量標準是隊列長度，則路由器會簡單地檢查每個隊列；如果度量標準是延遲，路由器可以直接發送一個特別「響應」（ECHO）分組來測出延遲，接收者只對它加上時間標記後就盡快送回。

㈤ 距離矢量路由演算法 （計算機網路題

通過B到個點的距離為：(11，6，14，18，12，8)，因為B到A的距離為5，C到B的距離為6所以C到A的距離更新為5+6=11，C到B的距離沒變為6，C通過B到C的距離為6+8=14，C通過B到D的距離為6+12=18，C通過B到E距離6+6=12，C通過B到F距離為6+2=8。

通過D到個點的距離為：(19，15，9，3，12，13)，通過D到A的距離為3+16=19，通過D到B的距離為3+12=15，通過D到C的距離為6+3=9，通過D到D的距離為3，通過D到E的距離為3+9=12，通過D到F的距離為3+10=13。

通過E到個點的距離為：(12，11，8，14，5，9)，通過E到A的距離為5+7=12，通過E到B的距離為5+6=11，通過E到C的距離為5+3=8，通過E到D的距離為5+9=14，通過E到Eden距離為5，通過E到F的距離為9。

取到達每一目的地的最小值(C除外)得到: (11， 6，0，3, 5，8)就得出了新的路由表。輸出的路線輸出線路是: (B,，B， -，D，E， B)。

(5)路由向量演算法擴展閱讀：

路由演算法的度量標准：

路由演算法使用了許多種不同的度量標准去決定最佳路徑。復雜的路由演算法可能採用多種度量來選擇路由，通過一定的加權運算，將它們合並為單個的復合度量、再填入路由表中，作為尋徑的標准。

通常所使用的度量有：路徑長度、可靠性、時延、帶寬、負載、通信成本等。

路徑長度：

路徑長度是最常用的路由。一些路由協議允許網管給每個網路連接人工賦以代價值，這種情況下，路由長度是所經過各個鏈接的代價總和。

可靠性：

可靠性，在路由演算法中指網路連接的可依賴性（通常以位誤率描述），有些網路連接可能比其它的失效更多，網路失效後，一些網路連接可能比其它的更易或更快修復。

路由延遲：

路由延遲指分組從源通過網路到達目的所花時間。很多因素影響到延遲，包括中間的網路連接的帶寬、經過的每個路由器的埠隊列、所有中間網路連接的擁塞程度以及物理距離。

帶寬

帶寬指連接可用的流通容量。在其它所有條件都相等時，10Mbps的乙太網鏈接比64kbps的專線更可取。雖然帶寬是鏈接可獲得的最大吞吐量，但是通過具有較大帶寬的鏈接做路由不一定比經過較慢鏈接路由更好。

負載：

負載指網路資源，如路由器的繁忙程度。負載可以用很多方面計算，包括CPU使用情況和每秒處理分組數。持續地監視這些參數本身也是很耗費資源的。

通信代價：

通信代價是另一種重要的metric，尤其是有一些公司可能關心運作費用甚於關心性能。即使線路延遲可能較長，他們也寧願通過自己的線路發送數據而不採用昂貴的公用線路。

參考資料來源：網路-路由演算法

㈥ 路由演算法的度量標准

路由演算法使用了許多種不同的度量標准去決定最佳路徑。復雜的路由演算法可能採用多種度量來選擇路由，通過一定的加權運算，將它們合並為單個的復合度量、再填入路由表中，作為尋徑的標准。
通常所使用的度量有：路徑長度、可靠性、時延、帶寬、負載、通信成本等。 採用LS演算法時，每個路由器必須遵循以下步驟：
1、確認在物理上與之相連的路由器並獲得它們的IP地址。當一個路由器開始工作後，它首先向整個網路發送一個「HELLO」分組數據包。每個接收到數據包的路由器都將返回一條消息，其中包含它自身的IP地址。
2、測量相鄰路由器的延時（或者其他重要的網路參數，比如平均流量）。為做到這一點，路由器向整個網路發送響應分組數據包。每個接收到數據包的路由器返回一個應答分組數據包。將路程往返時間除以2，路由器便可以計算出延時。（路程往返時間是網路當前延遲的量度，通過一個分組數據包從遠程主機返回的時間來測量。）該時間包括了傳輸和處理兩部分的時間——也就是將分組數據包發送到目的地的時間以及接收方處理分組數據包和應答的時間。
3、向網路中的其他路由器廣播自己的信息，同時也接收其他路由器的信息。
在這一步中，所有的路由器共享它們的知識並且將自身的信息廣播給其他每一個路由器。這樣，每一個路由器都能夠知道網路的結構以及狀態。
4、使用一個合適的演算法，確定網路中兩個節點之間的最佳路由。
在這一步中，路由器選擇通往每一個節點的最佳路由。它們使用一個演算法來實現這一點，如Dijkstra最短路徑演算法。在這個演算法中，一個路由器通過收集到的其他路由器的信息，建立一個網路圖。這個圖描述網路中的路由器的位置以及它們之間的鏈接關系。每個鏈接都有一個數字標注，稱為權值或成本。這個數字是延時和平均流量的函數，有時它僅僅表示節點間的躍點數。例如，如果一個節點與目的地之間有兩條鏈路，路由器將選擇權值最低的鏈路。 Dijkstra演算法執行下列步驟：1、路由器建立一張網路圖，並且確定源節點和目的節點，在這個例子里我們設為V1和V2。然後路由器建立一個矩陣，稱為「鄰接矩陣」。在這個矩陣中，各矩陣元素表示權值。例如，[i, j]是節點Vi與Vj之間的鏈路權值。如果節點Vi與Vj之間沒有鏈路直接相連，它們的權值設為「無窮大」。
2、路由器為網路中的每一個節點建立一組狀態記錄。此記錄包括三個欄位：
前序欄位——表示當前節點之前的節點。
長度欄位——表示從源節點到當前節點的權值之和。
標號欄位——表示節點的狀態。每個節點都處於一個狀態模式：「永久」或「暫時」。
3、路由器初始化（所有節點的）狀態記錄集參數，將它們的長度設為「無窮大」，標號設為「暫時」。
4、路由器設置一個T節點。例如，如果設V1是源T節點，路由器將V1的標號更改為「永久」。當一個標號更改為「永久」後，它將不再改變。一個T節點僅僅是一個代理而已。
5、路由器更新與源T節點直接相連的所有暫時性節點的狀態記錄集。
6、路由器在所有的暫時性節點中選擇距離V1的權值最低的節點。這個節點將是新的T節點。
7、如果這個節點不是V2（目的節點），路由器則返回到步驟5。
8、如果節點是V2，路由器則向前回溯，將它的前序節點從狀態記錄集中提取出來，如此循環，直到提取到V1為止。這個節點列表便是從V1到V2的最佳路由。 距離向量演算法（也稱為Bellman-Ford演算法）則要求每個路由器發送其路由表全部或部分信息，但僅發送到鄰近結點上。從本質上來說，鏈路狀態演算法將少量更新信息發送至網路各處，而距離向量演算法發送大量更新信息至鄰接路由器。 ——由於鏈路狀態演算法收斂更快，因此它在一定程度上比距離向量演算法更不易產生路由循環。但另一方面，鏈路狀態演算法要求比距離向量演算法有更強的CPU能力和更多的內存空間，因此鏈路狀態演算法將會在實現時顯得更昂貴一些。

㈦ 距離向量路由演算法的路由表

有三個路由器，A，B和C。路由器A的兩個網路介面F0和S0
分別連接在 10.1.0.0和10.2.0.0網段上；路由器B的兩個網路介面S0和S1
分別連接在 10.2.0.0和10.3.0.0網段上；路由器C的兩個網路介面S0和E0
分別連接在 10.3.0.0和10.4.0.0網段上；
如上圖中各路由表的前兩行所示，通過路由表的網路介面到與之直接相連的網
絡的網路連接，其向量距離設置為0。這即是最初的路由表。
當路由器B和A以及B和C之間相互交換路由信息後，它們會更新各自的路由表。
例如，路由器B通過網路埠S1收到路由器C的路由信息（10.3.0.0,S0,0）和(10.4.0.0,E0,0)後，在自己的路由表中增加一條(10.4.0.0,S1,1)路由信息。該信息表示：通過路由器B的網路接
口S1可以訪問到10.4.0.0網段，其向量距離為1,該向量距離是在路由器C的基礎上加1獲得的。
同樣道理，路由器B還會產生一條(10.1.0.0,S0,1)路由，這條路由是通過網路埠S0從路由器A
獲得的。如此反復，直到最終收斂，形成圖中所示的路由表。
概括地說，距離向量演算法要求每一個路由器把它的整個路由表發送給與它直接連接的其它路由
器。路由表中的每一條記錄都包括目標邏輯地址、相應的網路介面和該條路由的向量距離。當一個路
由器從它的相鄰處收到更新信息時，它會將更新信息與本身的路由表相比較。如果該路由器比較出一條
新路由或是找到一條比當前路由更好的路由時，它會對路由表進行更新：將從該路由器到鄰居之間的
向量距離與更新信息中的向量距離相加作為新路由的向量距離。