TCP/IP 協定與 Internet 網路：第六章 IP Routing 協定  上一頁           下一頁

翻轉工作室：粘添壽

6-5 Distance Vector Routing

『距離向量路徑選擇法』（Distance Vector Routing，DV Routing）是一種動態的分散式路徑選擇演算法。由此演算法所實現的通訊協定之下的路由器，它們的路由表是由鄰近相鄰路由器之中共同建立而成，因此稱之為『分散式』。網路上每一個路由器都必須維護一個二維的『向量表』（Vector Table），向量表格內紀錄本身路由器到每一個路由器的已知的最佳距離。路由器定期和鄰近路由器交換向量表（並不廣播給所有路由器）來建立路由表。當路由器接收到鄰近傳來的向量表時再修正本身的向量表，向量表的內容就一直修正再傳送，整個網路狀況也就能漸漸地傳遞到每一個路由器上。隨著時間路由器上之路由表的資料漸漸完備，也漸漸能找出最佳路徑。向量表只傳送給相鄰的路由器，對網路的頻寬也佔用較少，也不會造成廣播風暴。

對於向量表中各個欄位，如果使用路由器之間距離的數值，稱之為『距離向量』（Distance Vector）。表示兩個路由器之間相距幾個路由器，向量表又稱為『距離表』（Distance Table）。但目前使用之DV routing並不只估計相鄰之間的距離，我們會將各個路由器之間的佇列延遲、頻寬和網路壅塞情況來計算成為相鄰之間的『距離費用』（Distance Cost）。假設路由器已知它相鄰路由器之『距離』，如果距離費用是封包跳躍次數，則其值剛好為 1；如果距離費用為佇列長度，則路由器僅需計算每個佇列；如果距離費用是延遲時間，則路由器可利用一個特殊的 Echo 封包要求鄰近路由器回應，再計算要求和回應之間時間的差距，再取它的一半值就是延遲時間。

6-5-1 距離向量演算法的推演

我們以圖 6-7 為範例來說明路由器之間距離向量的傳遞，和路由表建立的過程。在圖中兩個端點（如，A、B）之間的標示值（如，6），為該兩端點之間的距離費用，其值的來由也許經過：跳躍次數、延遲時間等等因素所計算出來的。並假設距離向量傳遞路徑為：A → B → C → D → E。當距離向量進入某一路由器後，便和本身的路由表搜尋出所有可能到達的路徑，再由新建立的路由表之中尋找出最短路徑。緊接著，又將該最短路徑的路由表傳遞給下一個路由器。一直到最後，觀察路由器 E 的路由表的變化結果，便可瞭解距離向量演算法的運作情形。

圖 6-7 距離向量演算法範例

        圖 6-8 (a) ~ (e) 為各個路由器的起始距離向量表，並假設所有路由器都未和其他路由器交換訊息。針對每一個向量表，我們記錄了：從該路由器到其他路由器所經由不同相鄰路由器的費用。例如DE(A, B)是從 E 到 A 經由 B 的費用。其他空白部份表示沒有訊息，也可說是路徑費用無限大（∞）。

圖 6-8 (a) ~ (c) 路由器的起始路由表

圖 6-8 (d)、(e) 路由器的起始路由表

        向量表傳遞後，路由器依照進入的向量表和本身路由表，建構新的路由表，其步驟如下：

(1) 路由器（如 B）首先登錄自己和進入向量表的路由器（如 A）之間的費用（DB(A, A) = 6）。

(2) 再搜尋向量表（如圖 6-8 (a)）中可能到達的端點（其值不是 ∞），兩個路徑費用的合如小於表中內所紀錄的值，便取代它。

(3) 搜尋索有路徑後，建立新的路由表，再由新的路由向量表找出最短路徑，再將其傳遞給下一個路由器。

我們以圖 6-7 為例子，來推演距離向量演算法建構新路由表的過程，而距離傳遞方向假設只有單一路徑，其方向為： A → B → C → D → E。我們以下列步驟來觀察推演的過程：

(A) 路由器 A 建構起始路由表

路由器 A 沒有收到其他路由器的向量表，依照自己向鄰近路由器查詢之距離費用（如 6-8 (a)）建構出路由表。如圖 6-9 所示，其中最短路徑是由距離向量表中，查出每列的向量值最低者，並將其建立成路由表。如圖中，它可經由 B 到達 B 的費用是 6（DA(B, B)）為該列最小值；又 DA(E, E) = 1 也是該列最小值。路由器 A 建構路由表後，再將該路由表傳遞給 B（A → B），緊接著下一步驟。

圖 6-9 路由器 A 自行建構路由表

(B) 路由器 A 傳送給路由器 B（A → B）

路由器 A 將路由表（圖 6-9）傳遞給路由器 B，B 起始距離向量表如圖 6-8 (b)，再利用這兩個向量表建立出新的距離向量表。首先，B 由路由表中查出它自己經由 A 到 A 的費用（DB(A, A) = 6）。再由 A 的向量表中查詢可能到達的端點（B、E），得知可經由 A 到達 E（DA(E, E) = 1）。則將兩個端點路徑費用的和（DB(A, A) + DA(E, E) = 7）填入經由 A 到 E 的欄位內。再由表中的每一列的最小值，找到最短路徑（如第四列），建構出路由表如圖 6-10 所示。並將路由表傳遞給 C（B → C），接下一步驟。

圖 6-10 路由器 B 經過（A → B）後建立新的路由表

(C) 路由器 B 傳送給路由器 C（B → C）

路由器 B 將路由表（圖 6-10）傳遞給路由器 C，C 起始距離向量表如圖 6-8 (c) ，再利用這兩個向量表建立出新的距離向量表如圖 6-11 所示。首先 C 由本身路由表中查詢出到達路由器 B 之間的費用（DC(B, B) = 1），在搜尋 B 的向量表可能到達的端點（A、E）。

(1) 到達 A（經由 B 到達 A）：DC(B, B) + DB(A, A) = 1 +6 = 7，原向量表中的值為無限大（∞），因而取代為 7。

(2) 到達 E（經由 B 到達 E）：DC(B, B) + DB(A, E) = 1 +7 = 8，填入表格。

(3) 搜尋完後所建立之向量表，再找出最短路徑，建立出新的路由表，如圖 6-11 所示。並將路由表傳遞給 D（C → D），接下一步驟。

圖 6-11 路由器 C 經過（B → C）後建立新的路由表

(D) 路由器 C 傳送給路由器 D（C → D）

路由器 C 將路由表（圖 6-11）傳遞給路由器 D。又D 的起始距離向量表如圖 6-8 (d) ，再利用這兩個向量表建立出新的距離向量表。而 D 到 C 的費用是 2（DD(C, C)），另由向量表（圖 6-11）中查詢出可經由 C 到達之端點為 A、B、E。搜尋步驟如下：

(1) 到達 A：DD(C, A) = DD(C, C) + DC(B, A) = 2 + 7 = 9。

(2) 到達 B：DD(C, B) = DD(C, C) + DC(B, B) = 2 + 1 = 3。

(3) 到達 E：DD(C, E) = DD(C, C) + DC(B, E) = 2 + 8 = 10。

(4)  搜尋完後所建立之向量表及所建構出新的路由表如圖 6-12 所示。再將它的路由表傳遞給 E，緊接下一步驟（D → E）。

圖 6-12 路由器 D 經過（C → D）後建立新的路由表

(E) 路由器 D 傳送給路由器 E（D → E）

路由器 D 將路由表（圖 6-12）傳遞給路由器 E。又E 的起始距離向量表如圖 6-8 (e) ，再利用這兩個向量表建立出新的距離向量表。搜尋步驟如下：

(1) 到達 A：DE(D, A) = DE(D, D) + DD(C, A) = 2 + 9 = 11。

(2) 到達 B：DE(D, B) = DE(D, D) + DD(C, C) = 2 + 3 = 5。

(3) 到達 C：DE(D, C) = DE(D, D) + DD(C, C) = 2 + 2 = 4。

(4) 搜尋完後所建立之向量表及所建構出新的路由表如圖 6-13 所示。

圖 6-13 路由器 E 經過（D → E）後建立新的路由表

        以上所推演的過程之中，只有單一路徑（A → B → C → D → E）。當然，在正常情況下，路由器會隨時交換它們之間的距離向量表。假設，它們之間的路徑費用沒有改變，路由器 E 的向量表和路由表將如圖 6-14 (a)、(b) 所示。

圖 6-14 路由器 E 的距離向量表和路由表

但是如何來建立和更新路由表？一般我們會使用圖形理論中的分散式-非同步的最短路徑演算法。較常用的是Bellman-Ford Algorithm，演譯法如下：

## Bellman-Ford algorithm (at node X)

1.     Initialization:

for all adjacent nodes (column) v

                    D(*, v) = ∞

                    D(v, v) = c(X, v)

2.     Loop

Execute distributed topology update procedure

Forever

## end of Bellman-Ford algorithm

## Topology Update Algorithm

At node X:

1.  wait (until I see a link cost change to neighbor Y, or until I receive control message from neighbor W)

2. if (c(X, Y changes by δ)

/* change in cost to my neighbor, Y  */

change all column-Y entries in distance table by δ

if this changes cost of least cost path to some node Z, send control message to neighbors with my new minimum cost to Z.

3. if (control message received from my neighbor W)

/* shortest path via W to some node Z has changed */

DX(Z, W) = c(X, W) + new distance from W to Z

If cost of my least cost path to Z has changed send control message to neighbors with my new minimum cost to Z.

** end of Topology Update Algorithm

6-5-2 迴路問題

距離向量之路徑選擇法雖然較適合於大網路上使用，但也可能造成兩種異常狀態：『迴路問題』（Looping）和『震盪情形』（Oscillations）。我們先來討論迴路問題，其最主要的現象是：好消息傳的快，壞消息傳的慢。當路由器啟動時會即時計算本身的向量表，並向鄰近路由器通告，使整個網路迅速建立起來。網路使用一段時間後，各個路由器都已尋找出最佳路徑到其他路由器。但當中有任何路徑發生故障，必須再靠路由器之間的傳遞來發現路徑不通，重新計算最短路徑可能必須要一段傳遞時間。如圖 6-15 為好消息傳得快的範例，假設起始狀態之前端點 A 和 B 之間斷線，因此，各端點到 A 之間的跳躍距離為無限大（∞）。當第一次傳遞時，B 到 A 之間距離向量就被設定為 1。經過四次傳遞後，便可以將 A 路徑恢復的消息傳遞給所有端點。

圖 6-15 迴路問題範例（好消息傳得快）

        圖 6-16 為壞消息傳得慢的範例，起始狀態是所有路徑都正常，各端點上也都有紀錄前往端點 A 的距離向量（跳躍距離）。當 A 到 B 之間的路徑已斷線第一次傳遞時， B 無法傳送到 A，而將距離設為無限大，但它將這個訊息告訴 C，但 C 的紀錄裡有一路徑可到達 A 其向量值為 2，並將該值傳給 B，B 因而設定其前往 A 的向量值為 3。第二次傳遞，B 告訴 C 經由它那裡到達 A 的路徑為 3，因此，C 又將其到達 A 的向量值改為 4。第三次，C 將它到達 A 的向量值傳遞給 B 和 D，它們又將前往 A 的向量值改為 5 和 5。依此類推，如果要將 A 斷線的消息傳遞給所有端點，也許需要無止境的迴路。

圖 6-16 迴路問題範例（壞消息傳得慢）

        解決迴路問題在許多文獻中提出各種解決方法，但以下列兩種方法較為常用：

(A) 水平分離切口（Split Horizon Hack）

路由器在發送距離向量表時，都先假設某一邊路徑已有斷線的可能，而去試探它。做法如下：如果路由器往某一路徑是最佳路徑，下一次發送向量表時，發送給該端點之路徑費用設定為無限大，而另一方向以正常向量值發送。宛如，水平切開兩邊缺口。如果對方路徑還是正常，下次發送正常向量值；如果已斷線就給無限大的向量值。在圖 6-17 之中，端點 C 送前往 A 端點的向量值無限大給 B，而以正常的向量值 2 給另一邊的 D。如果當時 A 已斷線，B 找不到最佳路徑，就將該向量值設定為無限大，並以下次傳送給 C。第二次切離時，D 將前往 A 的向量值設定為無限大並傳給 C，另一方面，它以正常向量值 3 傳給 E。端點 C 收到該向量值後，也找不到另一路徑可到達 A，便將該向量值設定為無限大。依此類推，每分離切割一次，就將 A 斷路的訊息往前發佈一個端點。也可以避免產生向量值傳遞迴路的問題。

圖 6-17 水平分離切口法範例

(B) 暫停（Hold Down）

當某一路由器發現路徑故障，首先將故障路徑的費用設定為無限大，通知鄰近路由器。等待一段時間後，收到其他的向量表，再依照當時情況決定最短路徑。

6-5-3 向量表震盪情形

當路徑費用是以資料流量大小來評估的情況下，路由器發現某一路徑傳輸流量較低，也將該路徑的向量值設定為最低，並發送給相鄰路由器。因此，所有的傳輸訊息便往該路徑發送，這個路徑費用又變得最高。路由器又將這個訊息告訴相鄰路由器，它們又停止往這個路徑傳送，這條路徑費用又變成最低。依此類推，這條路徑費用就一直震盪（Oscillations）不停。解決方法是：(1) 不要定期的交換路徑資訊。交換訊息的時間加長，以減少震盪的現象。(2) 減低資料流量對路徑費用的比率。以減少資料流量瞬間改變對整個路由表的影響。

以上所介紹的路徑選擇技術，是目前 Internet 網路上的路徑協定普遍所使用的，尤其在動態路徑協定方面，幾乎都是使用 LS Routing 和 DV Routing 兩種技術，我們瞭解這兩種技術原理之後，以下針對 Internet 網路上，各種路徑協定來加以介紹，但不再重複介紹它的運作原理，請讀者自行參考。

<GOTOP>