路由算法詳解

引言

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

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

路由器基礎(chǔ)知識(shí)

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

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

LS算法

采用LS算法時(shí)，每個(gè)路由器必須遵循以下步驟：

1. 確認(rèn)在物理上與之相連的路由器并獲得它們的IP地址。
   當(dāng)一個(gè)路由器開(kāi)始工作后，它首先向整個(gè)網(wǎng)絡(luò)發(fā)送一個(gè)“HELLO”分組數(shù)據(jù)包。每個(gè)接收到數(shù)據(jù)包的路由器都將返回一條消息，其中包含它自身的IP地址。
   
2. 測(cè)量相鄰路由器的延時(shí)（或者其他重要的網(wǎng)絡(luò)參數(shù)，比如平均流量）。
   為做到這一點(diǎn)，路由器向整個(gè)網(wǎng)絡(luò)發(fā)送響應(yīng)分組數(shù)據(jù)包。每個(gè)接收到數(shù)據(jù)包的路由器返回一個(gè)應(yīng)答分組數(shù)據(jù)包。將路程往返時(shí)間除以2，路由器便可以計(jì)算出延時(shí)。（路程往返時(shí)間是網(wǎng)絡(luò)當(dāng)前延遲的量度，通過(guò)一個(gè)分組數(shù)據(jù)包從遠(yuǎn)程主機(jī)返回的時(shí)間來(lái)測(cè)量。）請(qǐng)注意，該時(shí)間包括了傳輸和處理兩部分的時(shí)間——也就是將分組數(shù)據(jù)包發(fā)送到目的地的時(shí)間以及接收方處理分組數(shù)據(jù)包和應(yīng)答的時(shí)間。

3. 向網(wǎng)絡(luò)中的其他路由器廣播自己的信息，同時(shí)也接收其他路由器的信息。
   在這一步中，所有的路由器共享它們的知識(shí)并且將自身的信息廣播給其他每一個(gè)路由器。這樣，每一個(gè)路由器都能夠知道網(wǎng)絡(luò)的結(jié)構(gòu)以及狀態(tài)。

4. 使用一個(gè)合適的算法，確定網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間的最佳路由。
   在這一步中，路由器選擇通往每一個(gè)節(jié)點(diǎn)的最佳路由。它們使用一個(gè)算法來(lái)實(shí)現(xiàn)這一點(diǎn)，如Dijkstra最短路徑算法。在這個(gè)算法中，一個(gè)路由器通過(guò)收集到的其他路由器的信息，建立一個(gè)網(wǎng)絡(luò)圖。這個(gè)圖描述網(wǎng)絡(luò)中的路由器的位置以及它們之間的鏈接關(guān)系。每個(gè)鏈接都有一個(gè)數(shù)字標(biāo)注，稱為權(quán)值或成本。這個(gè)數(shù)字是延時(shí)和平均流量的函數(shù)，有時(shí)它僅僅表示節(jié)點(diǎn)間的躍點(diǎn)數(shù)。例如，如果一個(gè)節(jié)點(diǎn)與目的地之間有兩條鏈路，路由器將選擇權(quán)值最低的鏈路。

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

1. 路由器建立一張網(wǎng)絡(luò)圖，并且確定源節(jié)點(diǎn)和目的節(jié)點(diǎn)，在這個(gè)例子里我們?cè)O(shè)為V1和V2。然后路由器建立一個(gè)矩陣，稱為“鄰接矩陣”。在這個(gè)矩陣中，各矩陣元素表示權(quán)值。例如，[i, j]是節(jié)點(diǎn)Vi與Vj之間的鏈路權(quán)值。如果節(jié)點(diǎn)Vi與Vj之間沒(méi)有鏈路直接相連，它們的權(quán)值設(shè)為“無(wú)窮大”。

2. 路由器為網(wǎng)路中的每一個(gè)節(jié)點(diǎn)建立一組狀態(tài)記錄。此記錄包括三個(gè)字段：
   • 前序字段——表示當(dāng)前節(jié)點(diǎn)之前的節(jié)點(diǎn)。
   • 長(zhǎng)度字段——表示從源節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的權(quán)值之和。
   • 標(biāo)號(hào)字段——表示節(jié)點(diǎn)的狀態(tài)。每個(gè)節(jié)點(diǎn)都處于一個(gè)狀態(tài)模式：“永久”或“暫時(shí)”。

3. 路由器初始化（所有節(jié)點(diǎn)的）狀態(tài)記錄集參數(shù)，將它們的長(zhǎng)度設(shè)為“無(wú)窮大”，標(biāo)號(hào)設(shè)為“暫時(shí)”。

4. 路由器設(shè)置一個(gè)T節(jié)點(diǎn)。例如，如果設(shè)V1是源T節(jié)點(diǎn)，路由器將V1的標(biāo)號(hào)更改為“永久”。當(dāng)一個(gè)標(biāo)號(hào)更改為“永久”后，它將不再改變。一個(gè)T節(jié)點(diǎn)僅僅是一個(gè)代理而已。

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

6. 路由器在所有的暫時(shí)性節(jié)點(diǎn)中選擇距離V1的權(quán)值最低的節(jié)點(diǎn)。這個(gè)節(jié)點(diǎn)將是新的T節(jié)點(diǎn)。

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

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

這些步驟的流程圖如下：

在下一頁(yè)中我們將使用這個(gè)算法具體分析一個(gè)示例。

示例：Dijkstra算法

我們想找到A與E（下圖）之間的最佳路由。可以看到A與E之間有六條可能路徑（ABE、ACE、ABDE、ACDE、ABDCE、ACDBE），很明顯ABDE是最佳路由，因?yàn)樗臋?quán)值最小。但是實(shí)際情況并非總是如此簡(jiǎn)單，有很多復(fù)雜的情形需要使用算法來(lái)找到最佳路由。

1. 如下圖所示，源節(jié)點(diǎn)(A)被選為T(mén)節(jié)點(diǎn)，所以它的標(biāo)號(hào)是永久（我們將永久性節(jié)點(diǎn)以實(shí)圈標(biāo)注，T節(jié)點(diǎn)以-->符號(hào)標(biāo)注）。

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

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

4. 在這一步中，已經(jīng)沒(méi)有任何暫時(shí)性節(jié)點(diǎn)，所以我們僅僅需要確認(rèn)下一個(gè)T節(jié)點(diǎn)。因?yàn)镋有最小權(quán)值，所以它被選作T節(jié)點(diǎn)。

5. E是目的節(jié)點(diǎn)，所以我們?cè)谶@里停止。

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

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

#define MAX_NODES 1024        /*最大節(jié)點(diǎn)數(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 {                          /*當(dāng)前計(jì)算的路徑 */
int predecessor ;                     /*前序節(jié)點(diǎn) */
int length                                /*從源節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的長(zhǎng)度*/
enum {permanent, tentative} label    /*標(biāo)號(hào)狀態(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é)點(diǎn) */
do{                                                            /*是從 k 開(kāi)始的一條更好路徑么？*/
for I=0; I < n; I++)                                       /*圖有 n 個(gè)節(jié)點(diǎn) */
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]
      }
}
/*找到具有最小權(quán)值的暫時(shí)性節(jié)點(diǎn)。*/
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);
/*將路徑復(fù)制到輸出數(shù)組*/
I=0;k=0
Do{path[I++]=k;k=state[k].predecessor;} while (k > =0);
}

DV算法

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

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

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

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

DV算法的一個(gè)最主要的問(wèn)題是“無(wú)窮計(jì)數(shù)”。讓我們通過(guò)一個(gè)例子來(lái)研究一下這個(gè)問(wèn)題：

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

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

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

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

“無(wú)窮計(jì)數(shù)”問(wèn)題

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

分級(jí)路由

可以看到，在LS和DV算法中，每個(gè)路由器都需要保存其他路由器的一些信息。隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，網(wǎng)絡(luò)中的路由器也將增加。因此，路由表的規(guī)模也將增大，從而使路由器不能有效地處理網(wǎng)絡(luò)流量。使用分級(jí)路由可以解決這個(gè)問(wèn)題。讓我們通過(guò)一個(gè)例子來(lái)說(shuō)明一下。

我們使用DV算法來(lái)查找節(jié)點(diǎn)間的最佳路由。在下述情形中，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)保存了一個(gè)有17個(gè)記錄的路由表。下面是A的一個(gè)典型網(wǎng)絡(luò)圖和路由表。

在分級(jí)路由中，路由器被分成很多組，稱為區(qū)域。每個(gè)路由器都只有自己所在區(qū)域路由器的信息，而沒(méi)有其他區(qū)域路由器的信息。所以在其路由表中，路由器只需要存儲(chǔ)其他每個(gè)區(qū)域的一條記錄。在這個(gè)例子中，我們將網(wǎng)絡(luò)分為5個(gè)區(qū)域（如下圖）。

如果A想發(fā)送分組數(shù)據(jù)包到在區(qū)域2中的一個(gè)路由器（D、E、F或G），它就將分組數(shù)據(jù)包先發(fā)送到B，依此類推。可以看到，在這種類型的路由中，可以對(duì)路由表進(jìn)行概括，因此網(wǎng)絡(luò)效率提高了。上面的例子描述了一個(gè)兩級(jí)的分級(jí)路由。同樣我們也可以采用三級(jí)或者四級(jí)的分級(jí)路由。

在一個(gè)三級(jí)的分級(jí)路由中，網(wǎng)絡(luò)被分為很多簇。每個(gè)簇由很多個(gè)區(qū)域組成，每個(gè)區(qū)域包含很多個(gè)路由器。分級(jí)路由廣泛應(yīng)用于互聯(lián)網(wǎng)路由中，并且使用了多種路由協(xié)議。