路由算法詳解

路由算法詳解

引言

如果您已經(jīng)閱讀過博聞網(wǎng)中的路由器工作原理一文，您會了解到路由器的作用是管理網(wǎng)絡流量和找到發(fā)送分組數(shù)據(jù)包的最佳路由。但是您是否想過路由器是怎么做到這一點的？路由器需要一些網(wǎng)絡狀態(tài)的信息來決定如何發(fā)送分組數(shù)據(jù)包以及發(fā)往哪里。但是它是怎樣收集這些信息的？

在本篇博聞網(wǎng)文章中，我們將帶您詳細了解路由器需要哪些信息來決定往哪發(fā)送分組數(shù)據(jù)包。

路由器基礎知識

路由器使用路由算法來找到到達目的地的最佳路由。當我們說“最佳路由”時，我們考慮的參數(shù)包括諸如跳躍數(shù)（分組數(shù)據(jù)包在網(wǎng)絡中從一個路由器或中間節(jié)點到另外的節(jié)點的行程）、延時以及分組數(shù)據(jù)包傳輸通信耗時。

關于路由器如何收集網(wǎng)絡的結構信息以及對之進行分析來確定最佳路由，我們有兩種主要的路由算法：總體式路由算法和分散式路由算法。采用分散式路由算法時，每個路由器只有與它直接相連的路由器的信息——而沒有網(wǎng)絡中的每個路由器的信息。這些算法也被稱為DV（距離向量）算法。采用總體式路由算法時，每個路由器都擁有網(wǎng)絡中所有其他路由器的全部信息以及網(wǎng)絡的流量狀態(tài)。這些算法也被稱為LS（鏈路狀態(tài)）算法。我們將在下一節(jié)討論LS算法。

LS算法

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

1. 確認在物理上與之相連的路由器并獲得它們的IP地址。
   當一個路由器開始工作后，它首先向整個網(wǎng)絡發(fā)送一個“HELLO”分組數(shù)據(jù)包。每個接收到數(shù)據(jù)包的路由器都將返回一條消息，其中包含它自身的IP地址。
   
2. 測量相鄰路由器的延時（或者其他重要的網(wǎng)絡參數(shù)，比如平均流量）。
   為做到這一點，路由器向整個網(wǎng)絡發(fā)送響應分組數(shù)據(jù)包。每個接收到數(shù)據(jù)包的路由器返回一個應答分組數(shù)據(jù)包。將路程往返時間除以2，路由器便可以計算出延時。（路程往返時間是網(wǎng)絡當前延遲的量度，通過一個分組數(shù)據(jù)包從遠程主機返回的時間來測量。）請注意，該時間包括了傳輸和處理兩部分的時間——也就是將分組數(shù)據(jù)包發(fā)送到目的地的時間以及接收方處理分組數(shù)據(jù)包和應答的時間。
   
3. 向網(wǎng)絡中的其他路由器廣播自己的信息，同時也接收其他路由器的信息。
   在這一步中，所有的路由器共享它們的知識并且將自身的信息廣播給其他每一個路由器。這樣，每一個路由器都能夠知道網(wǎng)絡的結構以及狀態(tài)。
   
4. 使用一個合適的算法，確定網(wǎng)絡中兩個節(jié)點之間的最佳路由。
   在這一步中，路由器選擇通往每一個節(jié)點的最佳路由。它們使用一個算法來實現(xiàn)這一點，如Dijkstra最短路徑算法。在這個算法中，一個路由器通過收集到的其他路由器的信息，建立一個網(wǎng)絡圖。這個圖描述網(wǎng)絡中的路由器的位置以及它們之間的鏈接關系。每個鏈接都有一個數(shù)字標注，稱為權值或成本。這個數(shù)字是延時和平均流量的函數(shù)，有時它僅僅表示節(jié)點間的躍點數(shù)。例如，如果一個節(jié)點與目的地之間有兩條鏈路，路由器將選擇權值最低的鏈路。

Dijkstra算法執(zhí)行下列步驟：

1. 路由器建立一張網(wǎng)絡圖，并且確定源節(jié)點和目的節(jié)點，在這個例子里我們設為V1和V2。然后路由器建立一個矩陣，稱為“鄰接矩陣”。在這個矩陣中，各矩陣元素表示權值。例如，[i, j]是節(jié)點Vi與Vj之間的鏈路權值。如果節(jié)點Vi與Vj之間沒有鏈路直接相連，它們的權值設為“無窮大”。
   
2. 路由器為網(wǎng)路中的每一個節(jié)點建立一組狀態(tài)記錄。此記錄包括三個字段：
   • 前序字段——表示當前節(jié)點之前的節(jié)點。
   • 長度字段——表示從源節(jié)點到當前節(jié)點的權值之和。
   • 標號字段——表示節(jié)點的狀態(tài)。每個節(jié)點都處于一個狀態(tài)模式：“永久”或“暫時”。

3. 路由器初始化（所有節(jié)點的）狀態(tài)記錄集參數(shù)，將它們的長度設為“無窮大”，標號設為“暫時”。

4. 路由器設置一個T節(jié)點。例如，如果設V1是源T節(jié)點，路由器將V1的標號更改為“永久”。當一個標號更改為“永久”后，它將不再改變。一個T節(jié)點僅僅是一個代理而已。

5. 路由器更新與源T節(jié)點直接相連的所有暫時性節(jié)點的狀態(tài)記錄集。

6. 路由器在所有的暫時性節(jié)點中選擇距離V1的權值最低的節(jié)點。這個節(jié)點將是新的T節(jié)點。

7. 如果這個節(jié)點不是V2（目的節(jié)點），路由器則返回到步驟5。

8. 如果節(jié)點是V2，路由器則向前回溯，將它的前序節(jié)點從狀態(tài)記錄集中提取出來，如此循環(huán)，直到提取到V1為止。這個節(jié)點列表便是從V1到V2的最佳路由。

這些步驟的流程圖如下：

示例：Dijkstra算法

我們想找到A與E（下圖）之間的最佳路由?？梢钥吹紸與E之間有六條可能路徑（ABE、ACE、ABDE、ACDE、ABDCE、ACDBE），很明顯ABDE是最佳路由，因為它的權值最小。但是實際情況并非總是如此簡單，有很多復雜的情形需要使用算法來找到最佳路由。

1. 如下圖所示，源節(jié)點(A)被選為T節(jié)點，所以它的標號是永久（我們將永久性節(jié)點以實圈標注，T節(jié)點以-->符號標注）。

2. 在這一步中，直接鏈接到T節(jié)點的暫時性節(jié)點(B, C)的狀態(tài)記錄集已經(jīng)被修改。同時，由于B有更小的權值，所以它被選作T節(jié)點，其標號被改為永久（如下圖所示）。

3. 與步驟2類似，在這一步中，直接鏈接到T節(jié)點的暫時性節(jié)點(D, E)的狀態(tài)記錄集已經(jīng)被修改。同時，由于D有更小的權值，所以它被選作T節(jié)點，其標號被改為永久（如下圖所示）。

4. 在這一步中，已經(jīng)沒有任何暫時性節(jié)點，所以我們僅僅需要確認下一個T節(jié)點。因為E有最小權值，所以它被選作T節(jié)點。

5. E是目的節(jié)點，所以我們在這里停止。

我們已經(jīng)到達了終點！現(xiàn)在，我們需要確定路由。E的前序節(jié)點是D，D的前序節(jié)點是B，B的前序節(jié)點是A。所以最佳路由是ABDE。在這個案例中，權值和為4(1+2+1)。

雖然這個算法工作良好，但是它非常復雜，以致于路由器需要花費大量時間進行處理，網(wǎng)絡的性能因此下降了。同樣，如果一個路由器將錯誤的信息發(fā)送給其他路由器，那么所有的路由決定都將是無效的。為了更好的理解這個算法，下面給出由C語言編寫的源代碼：

#define MAX_NODES 1024??????? /*最大節(jié)點數(shù) */
#define INFINITY 1000000000????? /*比所有最大路徑都大的數(shù) */
int n,dist[MAX_NODES][MAX_NODES];???? /*dist[I][j] 是從 i 到 j 的距離*/
void shortest_path(int s,int t,int path[ ])
{struct state {????????????????????????? /*當前計算的路徑 */
int predecessor ;???????????????????? /*前序節(jié)點 */
int length??????????????????????????????? /*從源節(jié)點到當前節(jié)點的長度*/
enum {permanent, tentative} label??? /*標號狀態(tài)*/
}state[MAX_NODES];
int I, k, min;
struct state *
???????????????????? p;
for (p=andstate[0];p < andstate[n];p++){?????? /*初始化狀態(tài)*/
p->predecessor=-1
p->length=INFINITY
p->label=tentative;
}
state[t].length=0; state[t].label=permanent ;
k=t ;????????????????????????????????????????????????????????? /* k 是初始工作節(jié)點 */
do{??????????????????????????????????????????????????????????? /*是從 k 開始的一條更好路徑么？*/
for I=0; I < n; I++)?????????????????????????????????????? /*圖有 n 個節(jié)點 */
if (dist[k][I] !=0 andand state[I].label==tentative){
??????????? if (state[k].length+dist[k][I] < state[I].length){
???????? state[I].predecessor=k;
???????? state[I].length=state[k].length + dist[k][I]
????? }
}
/*找到具有最小權值的暫時性節(jié)點。*/
k=0;min=INFINITY;
for (I=0;I < n;I++)
???? if(state[I].label==tentative andand state[I].length <
min)=state[I].length;
???? k=I;
?}
state[k].label=permanent
}while (k!=s);
/*將路徑復制到輸出數(shù)組*/
I=0;k=0
Do{path[I++]=k;k=state[k].predecessor;} while (k > =0);
}

DV算法

DV算法也被稱為Bellman-Ford路由算法和Ford-Fulkerson路由算法。在這些算法中，每個路由器都有一個路由表，用來表示到任何目的地的最佳路由。一個典型的路由器J的網(wǎng)絡圖以及路由表如下所示。

如表格所示，如果路由器J想發(fā)送分組數(shù)據(jù)包到路由器D，它應該將分組數(shù)據(jù)包先發(fā)送到路由器H。分組數(shù)據(jù)包到達路由器H后，它將檢查自己的路由表來決定怎樣將分組數(shù)據(jù)包發(fā)送到路由器D。

在DV算法中，每個路由器遵循以下步驟：

1. 計算所有與本身直接相連的鏈接的權值并且將信息保存到路由器的路由表中。
2. 一段時間后，路由器將其路由表發(fā)送給相鄰路由器（不是所有的路由器），同時也收到每個相鄰路由器的路由表。
3. 根據(jù)其相鄰路由器的路由表信息，路由器更新自己的路由表。

DV算法的一個最主要的問題是“無窮計數(shù)”。讓我們通過一個例子來研究一下這個問題：

假設一個網(wǎng)絡圖如下所示。如圖所示，A與網(wǎng)絡的其他部分只有一條鏈路。所有節(jié)點的路由表以及網(wǎng)絡圖如下所示：

網(wǎng)絡圖和路由表

現(xiàn)在假設A 、 B之間的鏈路被剪斷了。在這個時候，B修正了自己的路由表。經(jīng)過一段時間后，路由器交換它們的路由表，因此B接收到了C的路由表。因為C不知道A 、B之間的鏈路上發(fā)生了什么事，所以它說它有一條權值為2的到A的鏈路（從C到B權值為1，從B到A權值為1——它不知道B已經(jīng)沒有到A的鏈路了）。B接收到路由表之后認為有另外一條鏈路從C到A，所以它修正了自己的路由表，即將無窮大更改為3（C認為，B到C權值為1，C到A權值為2）。路由器然后再一次交換它們的路由表。當C接收到B的路由表后，它發(fā)現(xiàn)B到A的鏈路權值從1更改為3，所以C更新了它的路由表，即將它到A的鏈路權值更改為4（根據(jù)B的描述，C到B權值為1，B到A權值為3）。

這個循環(huán)過程到最后，所有的節(jié)點發(fā)現(xiàn)到A的鏈路權值變成無窮大。這個情形如下表所示。因此，專家稱DV算法具有低收斂率。

“無窮計數(shù)”問題

解決這個問題的一種方法是，路由器只發(fā)送信息給相鄰路由器，且該相鄰路由器不是通往目的地的唯一鏈接。比如在這個例子中，C就不應該發(fā)送任何關于A的信息給B，因為B是通往A的唯一路徑。