|
|
|
4-8 距離向量 繞路法
4-8-1 距離向量 繞路簡介 『距離向量路徑選擇法』（Distance Vector Routing，DV Routing）是一種動態的分散式路徑選擇演算法。由此演算法所屬的路由器，路由表是由鄰近相鄰路由器共同建立而成，因此稱之為『分散式』。網路上每一個路由器都必須維護一個二維的『向量表』（Vector Table），向量表格內紀錄本身路由器到每一個路由器的已知的最佳距離。路由器定期和鄰近路由器交換向量表（並不廣播給所有路由器）來建立路由表；當路由器接收到鄰近傳來的向量表時再修正本身的向量表，向量表的內容就一直修正再傳送，整個網路狀況因而能夠漸漸地傳遞到每一個路由器上。隨著時間路由器上之路由表的資料漸漸完備，也逐漸能找出最佳路徑。由於向量表只傳送給相鄰的路由器，對網路的頻寬佔用較少，所以不會造成廣播風暴。 對於向量表中各個欄位，如果使用路由器之間距離的數值，稱之為『距離向量』（Distance Vector）。表示兩個路由器之間相距幾個路由器，向量表又稱為『距離表』（Distance Table）。但目前使用之DV routing並不只估計相鄰之間的距離，而是將各個路由器之間的佇列延遲、頻寬和網路壅塞情況來計算相鄰路由器間的『距離費用』（Distance Cost）。假設路由器已知它相鄰路由器的『距離』，如果距離費用是封包跳躍次數，則其值剛好為 1；如果距離費用為佇列長度，則路由器僅需計算每個佇列；如果距離費用是延遲時間，則路由器可利用一個特殊的 Echo 封包要求鄰近路由器回應，再計算要求和回應之間時間的差距，取它的一半值就是延遲時間。 4-8-2 距離向量演算法的推演 我們以圖 4-13 為範例來說明路由器之間距離向量的傳遞，和路由表建立的過程。在圖中兩個端點（如，A、B）之間的標示值（6），為該兩端點之間的距離費用，其值的來由也許經過：跳躍次數、延遲時間等等因素所計算出來的。並假設距離向量傳遞路徑為：A → B → C → D → E。當距離向量進入某一路由器後，便和本身的路由表搜尋出所有可能到達的路徑，再由新建立的路由表之中尋找出最短路徑。緊接著，又將該最短路徑路由表傳遞給下一個路由器。一直到最後，觀察路由器 E 的路由表的變化結果，便可瞭解距離向量演算法的運作情形。
圖 4-13 距離向量演算法範例 圖 4-14 (a) ~ (e) 為各個路由器的起始距離向量表，並假設所有路由器都未和其他路由器交換訊息。針對每一個向量表，我們記錄了：從該路由器到其他路由器所經由不同相鄰路由器的費用。例如DE(A, B) 是從 E經由 A到 B 的費用。其他空白部份表示沒有訊息，也可說是路徑費用無限大（∞）。
圖 4-14 (a) ~ (c) 路由器的起始路由表
圖 4-14 (d)、(e) 路由器的起始路由表 圖 4-15 為向量表傳遞後，路由器依照進入的向量表和本身路由表，建構新的路由表，其步驟如下： (1) 路由器（如 B）首先登錄自己和進入向量表的路由器（如 A）之間的費用（DB(A, A) = 6）。 (2) 再搜尋向量表（如圖 4-14 (a)）中可能到達的端點（其值不是 ∞），兩個路徑費用的合如小於表中內所紀錄的值，便取代它。 (3) 搜尋索有路徑後，建立新的路由表，再由新的路由向量表找出最短路徑，再將其傳遞給下一個路由器。 我們以圖 4-13 為例子，來推演距離向量演算法建構新路由表的過程，而距離傳遞方向假設只有單一路徑，其方向為： A → B → C → D → E。我們以下列步驟來觀察推演的過程： (1) 路由器 A 沒有收到其他路由器的向量表，依照自己向鄰近路由器查詢之距離費用（如 4-14 (a)）建構出路由表。如圖 4-15 所示，最短路徑是由距離向量表中，查出每列的向量值最低者，並將其建立成路由表。如圖中，它可經由 B 到達 B 的費用是 6（DA(B, B)）為該列最小值；又 DA(E, E) = 1 也是該列最小值。路由器 A 建構路由表後，再將該路由表傳遞給 B（A → B），緊接著下一步驟。
圖 4-15 路由器 A 自行建構路由表 (2) （A → B）：路由器 A 將路由表（圖 4-15）傳遞給路由器 B，B 起始距離向量表如圖 4-14 (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 的欄位內。再由表中的每一列的最小值，找到最短路徑（如第四列），建構出路由表如圖 4-16 所示。並將路由表傳遞給 C（B → C），接下一步驟。
圖 4-16 路由器 B 經過（A → B）後建立新的路由表 (3) （B → C）：路由器 B 將路由表（圖 4-16）傳遞給路由器 C，C 起始距離向量表如圖 4-14 (c) ，再利用這兩個向量表建立出新的距離向量表如圖 4-17 所示。首先 C 由本身路由表中查詢出到達路由器 B 之間的費用（DC(B, B) = 1），在搜尋 B 的向量表可能到達的端點（A、E）。 ● 到達 A（經由 B 到達 A）：DC(B, B) + DB(A, A) = 1 +6 = 7，原向量表中的值為無限大（∞），因而取代為 7。 ● 到達 E（經由 B 到達 E）：DC(B, B) + DB(A, E) = 1 +7 = 8，填入表格。 ● 搜尋完後所建立之向量表，再找出最短路徑，建立出新的路由表，如圖 4-17 所示。並將路由表傳遞給 D（C → D），接下一步驟。 圖 4-17路由器 C 經過（B → C）後建立新的路由表 (4) （C → D）：路由器 C 將路由表（圖 4-17）傳遞給路由器 D。又C 的起始距離向量表如圖 4-14 (d) ，再利用這兩個向量表建立出新的距離向量表。而 D 到 C 的費用是 2（DD(C, C)），另由向量表（圖 4-17）中查詢出可經由 C 到達之端點為 A、B、E。搜尋步驟如下： ● 到達 A：DD(C, A) = DD(C, C) + DC(B, A) = 2 + 7 = 9。 ● 到達 B：DD(C, B) = DD(C, C) + DC(B, B) = 2 + 1 = 3。 ● 到達 E：DD(C, E) = DD(C, C) + DC(B, E) = 2 + 8 = 10。 搜尋完後所建立之向量表及所建構出新的路由表如 4-18 所示。再將它的路由表傳遞給 E，緊接下一步驟（D → E）。
圖 4-18路由器 D 經過（C → D）後建立新的路由表 (5) （D → E）：路由器 D 將路由表（圖 4-18）傳遞給路由器 E。又E 的起始距離向量表如圖 4-14 (e) ，再利用這兩個向量表建立出新的距離向量表。搜尋步驟如下： ● 到達 A：DE(D, A) = DE(D, D) + DD(C, A) = 2 + 9 = 11。 ● 到達 B：DE(D, B) = DE(D, D) + DD(C, C) = 2 + 3 = 5。 ● 到達 C：DE(D, C) = DE(D, D) + DD(C, C) = 2 + 2 = 4。 搜尋完後所建立之向量表及所建構出新的路由表如 4-19 所示。
圖 4-19路由器 E 經過（D → E）後建立新的路由表 以上所推演的過程之中，只有單一路徑（A → B → C → D → E）。當然，在正常情況下，路由器會隨時交換它們之間的距離向量表。假設，它們之間的路徑費用沒有改變，路由器 E 的向量表和路由表將如圖 4-20 (a)、(b) 所示。
圖 4-20 路由器 E 的距離向量表和路由表 但是如何來建立和更新路由表？一般我們會使用圖形理論中的分散式-非同步的最短路徑演算法。較常用的是Bellman-Ford Algorithm。 ## Bellman-Ford algorithm (at node X)
for all adjacent nodes (column) v D(*, v) = ∞ D(v, v) = c(X, v)
Execute distributed topology update procedure Forever ## end of Bellman-Ford algorithm ## Topology Update Algorithm At node X:
/* 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.
/* 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 4-8-3 距離向量的迴路問題 距離向量之路徑選擇法雖然較適合於大網路上使用，但也可能造成兩種異常狀態：『迴路問題』（Looping）和『震盪情形』（Oscillations）。我們先來討論迴路問題，其最主要的現象是：好消息傳的快，壞消息傳的慢。當路由器啟動時會即時計算本身的向量表，並向鄰近路由器通告，使整個網路迅速建立起來。網路使用一段時間後，各個路由器都已尋找出最佳路徑到其他路由器。但當中有任何路徑發生故障，必須再靠路由器之間的傳遞來發現路徑不通，重新計算最短路徑可能必須要一段傳遞時間。如圖 4-21 為好消息傳得快的範例，假設起始狀態之前端點 A 和 B 之間斷線，因此，各端點到 A 之間的跳躍距離為無限大（∞）。當第一次傳遞時，B 到 A 之間距離向量就被設定為 1。經過四次傳遞後，便可以將 A 路徑恢復的消息傳遞給所有端點。
圖 4-21 迴路問題範例（好消息傳得快） 圖 4-22 為壞消息傳得慢的範例，起始狀態是所有路徑都正常，各端點上也都有紀錄前往端點 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 斷線的消息傳遞給所有端點，也許需要無止境的迴路。
圖 4-22 迴路問題範例（壞消息傳得慢） 解決迴路問題在許多文獻中提出各種解決方法，但以下列兩種方法較為常用： (A) 水平分離切口（Split Horizon Hack） 路由器在發送距離向量表時，都先假設某一邊路徑已有斷線的可能，而去試探它。做法如下：如果路由器往某一路徑是最佳路徑，下一次發送向量表時，發送給該端點之路徑費用設定為無限大，而另一方向以正常向量值發送。宛如，水平切開兩邊缺口。如果對方路徑還是正常，下次發送正常向量值；如果已斷線就給無限大的向量值。在圖 4-23 之中，端點 C 送前往 A 端點的向量值無限大給 B，而以正常的向量值 2 給另一邊的 D。 如果當時 A 已斷線，B 找不到最佳路徑，就將該向量值設定為無限大，並以下次傳送給 C。第二次切離時，D 將前往 A 的向量值設定為無限大並傳給 C，另一方面，它以正常向量值 3 傳給 E。端點 C 收到該向量值後，也找不到另一路徑可到達 A，便將該向量值設定為無限大。依此類推，每分離切割一次，就將 A 斷路的訊息往前發佈一個端點。也可以避免產生向量值傳遞迴路的問題。
圖 4-23 水平分離切口法範例 (B) 暫停（Hold Down） 當某一路由器發現路徑故障，首先將故障路徑的費用設定為無限大，通知鄰近路由器。等待一段時間後，接到其他的向量表，再依照當時情況決定最短路徑。 4-8-4 距離向量表震盪情形 當路徑費用是以資料流量大小來評估的情況下，路由器發現某一路徑傳輸流量較低，則將該路徑的向量值設定為最低，並發送給相鄰路由器。因此，所有的傳輸訊息便往該路徑發送，這個路徑費用又變得最高。路由器又將這個訊息告訴相鄰路由器，它們又停止往這個路徑傳送，這條路徑費用又變成最低。依此類推，這條路徑費用就一直震盪（Oscillations）不停。解決方法是： (1) 不要定期的交換路徑資訊。交換訊息的時間加長，以減少震盪的現象。 (2) 減低資料流量對路徑費用的比率。以減少資料流量瞬間改變對整個路由表的影響。
|
翻轉工作室：粘添壽
電腦網路與連結技術：
翻轉電子書系列：
|
