分布式系統中的路由算法(編輯修改稿)

　

【文章內容簡介】 P8 3 P1 12 P2 6 P4 4 P5 20 P2 4 P3 6 P5 2?∞ ? ARPA路由算法： 舉例（ cont39。d） P 1P 2P 3P 4 P 54531222 0P2 7 P3 9 P1 11 P3 7 P4 3?5 P1 12 P2 6 P4 4?6 P5 20 P2 4 P3 6 P5 ∞ ? P 1P 2P 3P 4 P 54531222 0P2 7?9 P3 9?11 P1 11 P3 7?9 P4 5 P1 12 P2 6?8 P4 6 P5 20 P2 4?6 P3 6?8 P5 ∞ ? …… ARPA路由算法： 舉例（ cont39。d） ? 上述過程一直持續到達到一個新的穩定點， P1， P2， P3， P4分別用了 20， 19， 17， 20個時間間隔，如下圖所示。 ARPA路由算法（ cont39。d） ? ARPA路由算法中 每個節點對所有鄰居都發送相同消息，對接收節點不做任何標識。 ? 這樣，某些節點就會接收無用消息。 ? 在鏈接節點失效時候，這些消息會導致我們不期望的循環。 ? 例如 ARPA路由算法： 不期望的循環，舉例 ? 例如， P4和 P5鏈接失效時，P4的最短路徑為 4，但是這個 4來自于 P2，而 P2到P5的最短路徑原來就依賴于 P4與 P5的鏈接，由于 P4使用 P2的信息時， P2的信息尚未得到更新，導致出現不期望的循環：P4?P2?P4 P 1P 2P 3P 4 P 54531222 0P2 7 P3 9 P1 11 P3 7 P4 3 P1 12 P2 6 P4 4 P5 20 P2 4 P3 6 P5 2?∞ ? ARPA路由算法： 不期望循環的消除 ? 循環的消除是在路由消息中包含路徑的所有節點，并把這些消息發給鄰居節點。 ? 然而，它的效率較低，因為它的額外開銷太大。 ? Shin和 Chou，提出了一個避免循環算法：只需在路由消息中存儲路徑中最近的 l個節點， l與相應網絡中循環的最大長度有關 特殊類型網絡的單播路由算法 ? 一般類型網絡的路由算法適用于所有拓撲類型的網絡。但是， ? 每個節點需要維持路由延遲表，而且 ? 不適用于特殊類型的網絡，原因是效率太低。 ? 得益于特殊網絡的拓撲特性，可以不使用路由延遲表而構造最短路徑路由算法 ? 本節介紹三種特殊網絡的單播路由算法： ? 雙向環單播路由算法 ? 網格和圓環單播路由算法 ? 超立方單播路由算法 雙向環單播路由算法 ? 在雙向環上進行決定型單播路由非常簡單： ? 消息沿著一個方向被轉發：順時針或者逆時針 ? 由于消息可以沿兩個方向發送，所以由源節點根據目標節點的位置決定發送方向： ? 如果目標離順時針方向近，則用順時針方向； ? 否則選擇逆時針方向。 ? 一個消息通過幾個中間節點按照順時針或逆時針方向傳遞，直到到達目標節點。 雙向環單播路由算法（ cont39。d ） ? 雙向環上的單播路由算法可以使用兩條路徑： ? 一條沿著順時針， ? 另一條沿著逆時針。 ? 消息 ? 也可以被復制，然后每個方向發一個拷貝； ? 也可以分成兩半，每半轉發到一個方向。 雙向環單播路由算法： 算法一般化 ? 雙向環是 k元 1維立方，即只有一維度。 ? 若維度大于 1，例如網格和超立方，就用有序維度路由 ? 每次將每個消息向一個維度路由 ? 圓環：在一個維度中的各點以環的方式連接起來，帶有周邊連接 ? 網格：一個維度中的各點以線性排列的形式連接起來，沒有周邊連接 雙向環單播路由算法： 算法一般化（ cont39。d ） ? 環形路由方法可用于在一個維度中對消息進行路由。 ? 沿著一個線性排列路由是很簡單的。 ? 當消息到達每個維度的對等者時，就使用下一個維度。 ? 通過使經過的各個維度保持一個單調的順序，就可以保證不會發生死鎖。 ? 但這種方法適應性差。 網格和圓環單播路由算法 ? 網格和圓環是 k元 2維立方。 ? 圓環有周邊鄰接， ? 網格沒有周邊連接。 ? 類似地， 3維網格和圓環是 k元 3維立方。 網格和圓環單播路由算法： 2維網格的 XY路由 ? 在 2維網格中，有序維度路由叫 XY路由。 ? 每個節點的地址為 (x,y)。 ? 消息首先沿著 X維度轉發，然后沿著 Y維度路由。 ? 特別地，若源和目標分別為 (sx,sy)和 (dx,dy)，則路由消 息將在 X維度上走 |dx – sx| 步， 然后在 Y維度上走 |dy– sy|步 網格和圓環單播路由算法： 最短且完全適應路由 ? 在最短且完全適應路由中， ? 每個中間節點，包括源節點，都要充分利用所有可行的最短路徑。 ? 在 2維網格中， ? 只要 dx–sx≠0且 dy–sy≠0，每個節點在選擇鄰居時總有兩個選擇。 ? 一個好的適應性路由算法應該能選擇任意－個鄰居并能盡可能地保持 dx –sx≠0且 dy–sy≠0的情況。 ? 顯然 ,XY路由是最不靈活的一個。 網格和圓環單播路由算法： 適應性路由圖示 只要 dx–sx≠0且 dy–sy≠0， 每個節點在選擇鄰居時總有 兩個選擇： X方向或者 Y方向 網格和圓環單播路由算法（ cont39。d ） ? 如果每個鏈接（信道）擁塞的概率是一樣的，那么在最短路由的限制下，哪一個是最好的路由方法呢？ ? 這里的最好是指在這種路由方法下，消息到達目標的延遲最小。 網格和圓環單播路由算法： 折線路由 ? Badr和 Podar提出了一個 2維網格的折線路由方法 ? 首先建立一個包含源和目標的矩形． ? 源 s=(sx,sy)和目標 d=(dx,dy)分別位于矩形的兩個對角 ? 從端點 d=(dx,dy)引出一條線 L，這條線將平分經過點 d的矩形的兩邊所組成的角。 消息將沿著直線 L 路由，但仍在矩 形內部。 即所有的中間節點都是依照它們到 L的距離來選擇的 ——在所有合格 的節點中，總是選擇距離 L 最近的 一個。 直線 L 網格和圓環單播路由算法： 折線路由（ cont39。d ） ? 在 2維圓環中，折線路由可能不是最優的，因為一個中間節點可能有多于兩個的合格鄰居。 ? 特別，對一個 n為偶數的 nxn的圓環，存在一個具有四個合格鄰居的節點。而且，有 2(n2)個節點，它們和源的距離為 n／ 2個行或列，因此，在最短路徑上就有三個方向。 網格和圓環單播路由算法（ cont39。d ） ? 對于最優解， Wu在 k元 M維立方的最短路徑路由算法的基礎上提出了一個最大最短路徑 (MP)路由算法： ? 路由消息總是被轉發到與目標節點存在最大個數的最短路徑的那個鄰居節點。 ? 基于最大最短路徑的路由算法是一個對 2維網格和 M維立方都是最優的路由算法。 ? 然而，關于最大最短路徑對 2維圓環是不是最優的仍然是一個未決的問題。 網格和圓環單播路由算法（ cont39。d ） ? 若源和目標都有四個鄰居， 那么很容易在它們之間建立 四個邊 (或點 )分離的路徑， 如圖。 ? 一般地，設 k(k=8)是源和目 標節點所具有的最小的鄰居 的數目，那么，在源和目標 之間就存在 k個邊 〔 點 〕 分離 的路徑。 超立方單播路由算法 ? 對超立方的單播路由可采用一種相對簡單的方法，不必在每個節點中存儲路由延遲表。 ? 一個 n維超立方（ ncube）可定義為： 1. Q0，是一個只有一個節點的退化圖 2. Qn＝ K2xQn1，這里： K2是具有兩個節