【正文】 （ cont39。 從點 000到點 110有下列三個點分離路徑： ? 路徑 1（紅色）： 000?100?110 ? 路徑 2（藍色）： 000?010?110 ? 路徑 3（綠色）： 000?001?011?111?110 1 1 0 1 1 11 0 0 1 0 10 1 0 0 1 10 0 0 0 0 1sd 超立方單播路由算法： 超立方多路徑路由的性質(zhì) ? 超立方多路徑路由具有如下性質(zhì)： ? 若兩個節(jié)點 u和 w在 n維立方中的海明距離是 k． 則，在 u和 w之間就有 n個點分離路徑。 ? 一個 n維超立方（ ncube）可定義為： 1. Q0，是一個只有一個節(jié)點的退化圖 2. Qn＝ K2 Qn1，這里： K2是具有兩個節(jié)點的完全圖； 是兩個圖的笛卡爾乘積。d ） ? 如果每個鏈接（信道）擁塞的概率是一樣的，那么在最短路由的限制下，哪一個是最好的路由方法呢？ ? 這里的最好是指在這種路由方法下，消息到達目標(biāo)的延遲最小。d ） ? 環(huán)形路由方法 可用于在一個維度中對消息進行路由。d） ? 上述過程一直持續(xù)到達到一個新的穩(wěn)定點， P1， P2， P3， P4分別用了 20， 19， 17， 20個時間間隔，如下圖所示。d） 5. 取 D(1)中具有最小值的對應(yīng)節(jié)點 P1加入到集合 N中 , N= { P5,P4,P2,P3,P1}, 此時，節(jié)點都在 N中，算法結(jié)束。 ? 必須保證有且只有一個拷貝被接收 ? 非冗余型路由算法 ? 對每個目標(biāo)只需轉(zhuǎn)發(fā)消息的一個拷貝。高級操作系統(tǒng) Advanced Operating System 陳香蘭（代） 0551_360686483 中國科學(xué)技術(shù)大學(xué)計算機系 第四章 分布式路由算法 主要內(nèi)容 ? 分布式路由算法導(dǎo)論 ? 一般類型網(wǎng)絡(luò)的最短路徑路由算法 ? 特殊類型網(wǎng)絡(luò)的單播算法 ? 特殊類型網(wǎng)絡(luò)中的多播算法 ? 虛信道和虛網(wǎng)絡(luò) ? 完全自適應(yīng)和無死鎖路由算法 第四章 分布式路由算法 主要內(nèi)容（ cont39。 7）死鎖避免型路由和非死鎖避免型路由 ? 死鎖避免型路由算法 ? 通過仔細設(shè)計的路由算法，保證不發(fā)生死鎖。 P 1P 2P 3P 4 P 54531222 0 Dijkstra集中式算法： 連續(xù)的步驟，如下表： P 1P 2P 3P 4 P 54531222 0輪 N D(1) D(2) D(3) D(4) 初始 1 2 3 4 {P5} {P5, P4} {P5, P4 , P2} {P5, P4 , P2 , P3} {P5, P4 , P2 , P3 , P1} ∞ ∞ 7 7 7 ∞ 3 3 3 3 20 4 4 4 4 2 2 2 2 2 ? 第二種類型的路由算法采用分散式的方法進行路由 ? 分布式算法 ? 每個節(jié)點在交互式的基礎(chǔ)上和其鄰節(jié)點交換代價和路由信息，直到這些節(jié)點的路由表到達最短路徑的要求為止 （ cont‘d） ? Ford分布式算法也包括兩個部分： ? 一個初始步驟 ? 一個最短距離計算的步驟 ? 這里，最短距離指一個給定節(jié)點和目標(biāo)節(jié)點之間的距離 ? 當(dāng)所有節(jié)點都帶有下面兩個標(biāo)記時，算法結(jié)束 ? 一個表示它們到目標(biāo)節(jié)點 距離 的標(biāo)記 ? 以及，一個沿著最短路徑到達目標(biāo)節(jié)點要經(jīng)過的 下一個節(jié)點 的標(biāo)記 ： 算法描述 ? 每個節(jié)點 v，都有 (next, D(v))的標(biāo)記。 ARPA路由算法（ cont39。 ? 沿著一個線性排列路由是很簡單的。 網(wǎng)格和圓環(huán)單播路由算法： 折線路由 ? Badr和 Podar提出了一個 2維網(wǎng)格的折線路由方法 ? 首先建立一個包含源和目標(biāo)的矩形． ? 源 s=(sx, sy)和目標(biāo) d=(dx, dy)分別位于矩形的兩個對角 ? 從目標(biāo) d=(dx,dy)引出一條線 L，這條線將平分經(jīng)過點 d的矩形的兩邊所組成的角。 ? 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)。 在這 n條路徑中，有 k個路徑長度為 k， 其余 nk個路徑長度為 k+2。d） ? 不幸的是，對網(wǎng)格和超立方的多播優(yōu)化問題都是 NP完全問題。 ? 在整個順序中，每個節(jié)點 (x, y)都被賦予一個數(shù)字 r： ： 哈密爾頓路徑舉例 ? 例如，一個 4 4的網(wǎng)格上每個節(jié)點具有的 r值如圖所示： ? n=4 ? 若 y是偶數(shù)， r值沿 X方向遞增 ? r(x, y)=yn+x ? 若 y是奇數(shù)， r值沿 X方向遞減 ? r(x, y)=yn+nx1 =yn+(n1)x 0 , 0 0 , 1 0 , 2 0 , 31 , 0 1 , 1 1 , 2 1 , 32 , 0 2 , 1 2 , 2 2 , 33 , 0 3 , 1 3 , 2 3 , 3xy01237654891 01 11 51 41 31 2偶數(shù) 奇數(shù) ： 哈密爾頓路徑定義 ? 哈密爾頓路徑定義 ? 兩個節(jié)點在路徑中相鄰當(dāng)且僅當(dāng) |r(v)r(u)|=1 ? 例如： ? 4 4網(wǎng)格中，使用紅粗線連接兩個節(jié)點相鄰 0 , 0 0 , 1 0 , 2 0 , 31 , 0 1 , 1 1 , 2 1 , 32 , 0 2 , 1 2 , 2 2 , 33 , 0 3 , 1 3 , 2 3 , 3xy01237654891 01 11 51 41 31 2： 低信道網(wǎng)絡(luò)和高信道網(wǎng)絡(luò) ? 使用順序定義，整個網(wǎng)格可以分成兩個子網(wǎng)： ? 一個包括從低序節(jié)點到高序節(jié)點的鏈接； ? 另一個包括從高序節(jié)點到低序節(jié)點的鏈接。 ? 所有在這一位為 1的目標(biāo)將被轉(zhuǎn)發(fā)到這一維上的那個鄰居 ? 在剩余的目標(biāo)中，將利用下一個被選中的維度重復(fù)上述步驟。d ） ? 第一步，這個列表被分成兩個子列表{(0,0),(1,0),(1,1),(1,2)}和{(1,3),(2,0),(2,1),(3,2)} ? 源 (0,0)將信息發(fā)送到第二個子列表的第一個節(jié)點 (1,3) ? 使用 XY路由建立 (0,0)到 (1,3)的路由路徑 0 , 0 0 , 1 0 , 2 0 , 31 , 0 1 , 1 1 , 2 1 , 32 , 0 2 , 1 2 , 2 2 , 33 , 0 3 , 1 3 , 2 3 , 3： 舉例（ cont39。 ： 4維立方中的多播例子 ? 考慮一個 4維立方體（目標(biāo)用藍色節(jié)點代表） ? 節(jié)點 0010打算向組播集 {0000， 0001， 1001， 1100， 1110} 中的每個節(jié)點發(fā)送消息 ? 所有目標(biāo)節(jié)點的實際地址和源節(jié)點 0010 的實際地址做異或操作，得到 多播集合的相對地址 {0010， 0011， 1011， 1110， 1100}。 0 , 0 0 , 1 0 , 2 0 , 31 , 0 1 , 1 1 , 2 1 , 32 , 0 2 , 1 2 , 2 2 , 33 , 0 3 , 1 3 , 2 3 , 3xy01237654891 01 11 51 41 31 20 , 0 0 , 1 0 , 2 0 , 31 , 0 1 , 1 1 , 2 1 , 32 , 0 2 , 1 2 , 2 2 , 33 , 0 3 , 1 3 , 2 3 , 3xy01237654891 01 11 51 41 31 2： 最短路徑路由函數(shù) ? 目標(biāo)依據(jù)它們與源的相對位置也分為兩個子集。 ? 目前，已有人給出了在使用分割 通過路由技