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