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