【正文】 d特殊類型網(wǎng)絡(luò)的多播路由算法 ? 多播（一到多）是指從一個源向任意多個目標(biāo)節(jié)點傳送同樣的消息。 在這 n條路徑中，有 k個路徑長度為 k， 其余 nk個路徑長度為 k+2。 n維在最后； 超立方單播路由算法： 一個 3維立方路由的例子 ? 例中：源節(jié)點 u=000目標(biāo)節(jié)點 w＝ 110。 ? 如果遵循一個預(yù)定的順序，這種算法就是決定性的，叫做 e立方路由。d ） ? 在上述算法中， i的選擇是隨機的， 這意味著可能有不止一條最短路徑。d ） ? 在下面的算法中，節(jié)點 u是當(dāng)前節(jié)點 (可以是源節(jié)點 )，節(jié)點 w是目標(biāo)節(jié)點。 ? 在每個跳步，相對距離都會通過將 u⊕ w中的一個 1替換而進行更新。 ? u(i)表示改變 u的第 i位 (也叫維 )．例如 1101(3)=1001。 如果 ui≠wi， 則 ri＝ 1,1=i=n。 ? Qn中的一個節(jié)點的地址可以表示為 u=unun1…u 1（ ui＝ 0或 1， 1=i=n） 超立方單播路由算法： 海明距離 ? 兩個節(jié)點 u=unun1…u 1和 w =wnwn1…w 1間最短路徑長度就是 u和 w間的海明距離，表示為 H(u,w)。 超立方單播路由算法 ? 對超立方的單播路由可采用一種相對簡單的方法，不必在每個節(jié)點中存儲路由延遲表。d ） ? 若源和目標(biāo)都有四個鄰居， 那么很容易在它們之間建立 四個邊 (或點 )分離的路徑， 如圖。 ? 然而，關(guān)于最大最短路徑對 2維圓環(huán)是不是最優(yōu)的仍然是一個未決的問題。d ） ? 對于最優(yōu)解， Wu在 k元 M維立方的最短路徑路由算法的基礎(chǔ)上提出了一個最大最短路徑 (MP)路由算法： ? 路由消息總是被轉(zhuǎn)發(fā)到與目標(biāo)節(jié)點存在最大個數(shù)的最短路徑的那個鄰居節(jié)點。而且，有 2(n2)個節(jié)點，它們和源的距離為 n／ 2個行或列，因此，在最短路徑上就有三個方向。d ） ? 在 2維圓環(huán)中，折線路由可能不是最優(yōu)的，因為一個中間節(jié)點可能有多于兩個的合格鄰居。 即所有的中間節(jié)點都是依照它們到 L的距離來選擇的 ——在所有合格 的節(jié)點中，總是選擇距離 L 最近的 一個。 網(wǎng)格和圓環(huán)單播路由算法： 折線路由 ? Badr和 Podar提出了一個 2維網(wǎng)格的折線路由方法 ? 首先建立一個包含源和目標(biāo)的矩形． ? 源 s=(sx,sy)和目標(biāo) d=(dx,dy)分別位于矩形的兩個對角 ? 從端點 d=(dx,dy)引出一條線 L，這條線將平分經(jīng)過點 d的矩形的兩邊所組成的角。 網(wǎng)格和圓環(huán)單播路由算法： 適應(yīng)性路由圖示 只要 dx–sx≠0且 dy–sy≠0， 每個節(jié)點在選擇鄰居時總有 兩個選擇： X方向或者 Y方向 網(wǎng)格和圓環(huán)單播路由算法（ cont39。 ? 一個好的適應(yīng)性路由算法應(yīng)該能選擇任意－個鄰居并能盡可能地保持 dx –sx≠0且 dy–sy≠0的情況。 ? 特別地，若源和目標(biāo)分別為 (sx,sy)和 (dx,dy)，則路由消 息將在 X維度上走 |dx – sx| 步， 然后在 Y維度上走 |dy– sy|步 網(wǎng)格和圓環(huán)單播路由算法： 最短且完全適應(yīng)路由 ? 在最短且完全適應(yīng)路由中， ? 每個中間節(jié)點，包括源節(jié)點，都要充分利用所有可行的最短路徑。 ? 每個節(jié)點的地址為 (x,y)。 ? 類似地， 3維網(wǎng)格和圓環(huán)是 k元 3維立方。 網(wǎng)格和圓環(huán)單播路由算法 ? 網(wǎng)格和圓環(huán)是 k元 2維立方。 ? 通過使經(jīng)過的各個維度保持一個單調(diào)的順序，就可以保證不會發(fā)生死鎖。 ? 沿著一個線性排列路由是很簡單的。 ? 若維度大于 1，例如網(wǎng)格和超立方，就用有序維度路由 ? 每次將每個消息向一個維度路由 ? 圓環(huán)：在一個維度中的各點以環(huán)的方式連接起來，帶有周邊連接 ? 網(wǎng)格：一個維度中的各點以線性排列的形式連接起來，沒有周邊連接 雙向環(huán)單播路由算法： 算法一般化（ cont39。 ? 消息 ? 也可以被復(fù)制，然后每個方向發(fā)一個拷貝； ? 也可以分成兩半，每半轉(zhuǎn)發(fā)到一個方向。 雙向環(huán)單播路由算法（ cont39。 ? 得益于特殊網(wǎng)絡(luò)的拓?fù)涮匦?，可以不使用路由延遲表而構(gòu)造最短路徑路由算法 ? 本節(jié)介紹三種特殊網(wǎng)絡(luò)的單播路由算法： ? 雙向環(huán)單播路由算法 ? 網(wǎng)格和圓環(huán)單播路由算法 ? 超立方單播路由算法 雙向環(huán)單播路由算法 ? 在雙向環(huán)上進行決定型單播路由非常簡單： ? 消息沿著一個方向被轉(zhuǎn)發(fā)：順時針或者逆時針 ? 由于消息可以沿兩個方向發(fā)送，所以由源節(jié)點根據(jù)目標(biāo)節(jié)點的位置決定發(fā)送方向： ? 如果目標(biāo)離順時針方向近，則用順時針方向； ? 否則選擇逆時針方向。 ? Shin和 Chou，提出了一個避免循環(huán)算法：只需在路由消息中存儲路徑中最近的 l個節(jié)點， l與相應(yīng)網(wǎng)絡(luò)中循環(huán)的最大長度有關(guān) 特殊類型網(wǎng)絡(luò)的單播路由算法 ? 一般類型網(wǎng)絡(luò)的路由算法適用于所有拓?fù)漕愋偷木W(wǎng)絡(luò)。 ? 例如 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é)點。 ? 這樣，某些節(jié)點就會接收無用消息。 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。 ARPA路由算法： 舉例 ? 舉例說明：用 ARPA路由算法時， P1， P2，P3， P4的一般路由表，仍以 P5為目標(biāo)節(jié)點 ? 每個表格都包含通過每個鄰居到達 P5的最短距離 ? 假設(shè)在時刻 0前已經(jīng)達到了一個穩(wěn)定點 ? 即網(wǎng)絡(luò)延遲表如右圖 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路由算法： 舉例（ cont39。 ? 這個路由表包含從這個節(jié)點到所有其它節(jié)點的最優(yōu)路徑的延遲。 ARPA路由算法 ? ARPA的路由算法是一個可靠、實用的分布式路由算法，也是今天流行的 Inter 路由算法的前身。 P 1P 2P 3P 4 P 54531222 0( . , 0 )( P5, 2 0 )( . , ∞ )( . , ∞ )( . , ∞ )( P5, 2 )( . , ∞ )( . , ∞ )( . , ∞ ) Ford分布式算法： 舉例：第二輪 ? 對于 P1， ? 鄰節(jié)點為 P2,P3，由當(dāng)前標(biāo)記可知