【正文】 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。 ? 重復上述分割步驟直到每個子列表中只有一個節(jié)點； ? 若源節(jié)點不是 (0,0)，可重新定義排列順序以便源節(jié)點成為第一個節(jié)點 基于樹的多播路由算法： 舉例 ? 考慮一個 4*4網(wǎng)格， (0,0)是源節(jié)點，(1,0),(1,1),(1,2),(1,3),(2,0),(2,1)和 (3,2)是目標節(jié)點。 ? 將列表分成兩個相等的子列表。 ? 先為 2維網(wǎng)格的節(jié)點地址定義一個字典序 (t)，即 若 x1tx2或者 x1=x2,但 y1ty2，則有 (x1,y1)(x2,y2)。 ? 每個多播樹的分支都將繼續(xù)到剩余的 多播集合變空為止 基于樹的多播路由算法： 基于遞歸倍增的啟發(fā)式算法 ? 當使用分割 通過網(wǎng)絡時，可以使用遞歸倍增方法構(gòu)造啟發(fā)式算法。 ? 只有節(jié)點 1110被剩下了，這個節(jié)點可以通過第 3維的鄰居轉(zhuǎn)發(fā)，也可以通過第 4維的鄰居轉(zhuǎn)發(fā)。d ） ? 沿著第 2維的鄰居擁有最受歡迎的維度。 基于樹的多播路由算法： 4維立方中的多播例子 ? 考慮一個 4維立方體 (目標用藍色節(jié)點代表 ) ? 節(jié)點 0010打算向組播集 {0000， 0001， 1001， 1100， 1110} 中的每個節(jié)點發(fā)送消息 ? 所有目標節(jié)點的實際地址和源節(jié)點 0010 的實際地址做異或操作，得到 多播集合的相對地址 {0010， 0011， 1011， 1110， 1100}。 ? 所有在這一位為 1的目標將被轉(zhuǎn)發(fā)到這一維上的那個鄰居 ? 在剩余的目標中，將利用下一個被選中的維度重復上述步驟。 ? 計數(shù)器的內(nèi)容代表相應維度的信息。 ? 若發(fā)現(xiàn)匹配，消息的一個拷貝將被送往本地的處理器 ? 若多播集合非空，當前節(jié)點將決定把目標列表中的地址轉(zhuǎn)發(fā)到哪些鄰居。 ? 依據(jù)路由函數(shù)，可以得到如下路徑： ? 同樣，轉(zhuǎn)發(fā)消息到節(jié)點 10， 13和 18時應使用高信道網(wǎng)絡 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)絡路徑和 具有最小 r值的鄰居 深紫色：高信道網(wǎng)絡路徑和 具有最大 r值的鄰居 基于樹的多播路由算法 ? Lan的貪婪多播算法可以應用于超立方。 紫色：源節(jié)點； 藍色：目標節(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基于路徑的多播路由算法： 舉例（ cont39。 ? v和 d（ r(v)r(d)）分別是中間節(jié)點和目標節(jié)點。 ? 為了將消息沿著最短路徑傳送，定義如下路由函數(shù)。 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ù) ? 目標依據(jù)它們與源的相對位置也分為兩個子集。 ? 在整個順序中，每個節(jié)點 (x,y)都被賦予一個數(shù)字 r： 基于路徑的多播路由算法： 哈密爾頓路徑舉例 ? 例如，一個 4X4的網(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基于路徑的多播路由算法： 哈密爾頓路徑定義 ? 哈密爾頓路徑定義 ? 兩個節(jié)點在路徑中相鄰當且僅當 |r(v)r(u)|=1 ? 例如： ? 4X4網(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)絡和高信道網(wǎng)絡 ? 使用順序定義，整個網(wǎng)格可以分成兩個子網(wǎng)： ? 一個包括從低序節(jié)點到高序節(jié)點的鏈接； ? 另一個包括從高序節(jié)點到低序節(jié)點的鏈接。 基于路徑的多播路由算法： 哈密爾頓路徑 ? 若使用雙向鏈接，則只需一個哈密爾頓路徑(而不是哈密爾頓回路 )即可。 ? 將消息和目標列表傳給一個鄰居。 ? 這個順序起始于源節(jié)點，并包括所有目標節(jié)點。它的解稱為哈密爾頓回路。 1895年，愛爾蘭數(shù)學家哈密爾頓首先提出“環(huán)球周游”問題。 基于路徑的多播路由算法 ? 基本思想： ? 首先建立一個哈密爾頓回路， ? 然后根據(jù)這個回路把多播集合轉(zhuǎn)發(fā)出去。 ? 目前，已有人給出了在使用分割 通過路由技術(shù) (如蟲孔路由 )的網(wǎng)絡中進行最優(yōu)化多播通信的充分條件。d） ? 網(wǎng)格和超立方的多播優(yōu)化問題都是 NP完全問題。 ? 多播樹優(yōu)化問題 ? 一個包含所有目標的給定拓撲的子樹，且樹中每個通向目標的路徑的長度對于給定的拓撲是最小的。 一般的多播路由算法： 多播優(yōu)化問題（ cont39。 一般的多播路由算法： 多播優(yōu)化問題 ? 通常，多播存在下列四個優(yōu)化問題： ? 多播路徑優(yōu)化問題 ? 一個最優(yōu)的多播路徑是一個包括所有目標的最短路徑。 ? 當兩個多播路由算法有相同的時間步數(shù)時，應該選擇具有較小的通信量步數(shù)的那一個。 ? 通信量是以將消息發(fā)送到所有的目標所需的通信鏈接的數(shù)目來衡量的。 ? 多播在數(shù)據(jù)并行編程操作中有一些應用，例如 ? 復制，障礙同步， 對共享存儲器失效以及分布式共享內(nèi)存系統(tǒng)更新的支持等。 因此，上述路徑中有兩條長度為 2，一條長度為 4 ? 路徑 1（紅色）： 000?100?110 ? 路徑 2（藍色）： 000?010?110 ? 路徑 3（綠色）： 000?001?011?111?110 超立方單播路由算法： 超立方多路徑路由的性質(zhì) ? 類似地． 000和 100之間的三條點分離路徑為： ? 路徑 1（紅色）： 000?100 ? 路徑 2（綠色）： 000?001?101?100 ? 路徑 3（藍色）： 000?010?110?100 ? 000和 100之間的海明距離 |000⊕ 100|=1 1 1 0 1 1 11 0 0 1 0 10 1 0 0 1 10 0 0 0 0 1s