【正文】 , 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ù)它們與源的相對位置也分為兩個子集。 ? 依據(jù)路由函數(shù)，可以得到如下路徑： ? 同樣，轉(zhuǎn)發(fā)消息到節(jié)點 10， 13和 14時應(yīng)使用高信道網(wǎng)絡(luò) 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ò)路徑和 具有最小 r值的鄰居 深紫色：高信道網(wǎng)絡(luò)路徑和 具有最大 r值的鄰居 ? Lan的貪婪多播算法可以應(yīng)用于 超立方 。 ： 4維立方中的多播例子 ? 考慮一個 4維立方體（目標用藍色節(jié)點代表） ? 節(jié)點 0010打算向組播集 {0000， 0001， 1001， 1100， 1110} 中的每個節(jié)點發(fā)送消息 ? 所有目標節(jié)點的實際地址和源節(jié)點 0010 的實際地址做異或操作，得到 多播集合的相對地址 {0010， 0011， 1011， 1110， 1100}。 ? 先為 2維網(wǎng)格的節(jié)點地址定義一個字典序 (t)，即 若 x1tx2或者 x1=x2,但 y1ty2，則有 (x1,y1)(x2,y2)。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。 ? 每個多播樹的分支都將繼續(xù)到剩余的 多播集合變空為止 ： 基于遞歸倍增的啟發(fā)式算法 ? 當使用分割 通過網(wǎng)絡(luò)時，可以使用遞歸倍增方法構(gòu)造啟發(fā)式算法。 ? 所有在這一位為 1的目標將被轉(zhuǎn)發(fā)到這一維上的那個鄰居 ? 在剩余的目標中，將利用下一個被選中的維度重復(fù)上述步驟。 紫色：源節(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。 ? 在整個順序中，每個節(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é)點在路徑中相鄰當且僅當 |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é)點的鏈接。它的解稱為哈密爾頓回路。d） ? 不幸的是，對網(wǎng)格和超立方的多播優(yōu)化問題都是 NP完全問題。 ? 當兩個多播路由算法有相同的時間步數(shù)時，應(yīng)該選擇具有較小的通信量步數(shù)的那一個。 在這 n條路徑中，有 k個路徑長度為 k， 其余 nk個路徑長度為 k+2。d ） ? 在下面的算法中，節(jié)點 u是當前節(jié)點 (可以是源節(jié)點 )，節(jié)點 w是目標節(jié)點。 ? 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)。d ） ? 對于最優(yōu)解， Wu在 k元 M維立方 的最短路徑路由算法的基礎(chǔ)上提出了一個最大最短路徑 (MP)路由算法： ? 路由消息總是被轉(zhuǎn)發(fā)到與目標節(jié)點存在最大個數(shù)的最短路徑的那個鄰居節(jié)點。 網(wǎng)格和圓環(huán)單播路由算法： 折線路由 ? Badr和 Podar提出了一個 2維網(wǎng)格的折線路由方法 ? 首先建立一個包含源和目標的矩形． ? 源 s=(sx, sy)和目標 d=(dx, dy)分別位于矩形的兩個對角 ? 從目標 d=(dx,dy)引出一條線 L，這條線將平分經(jīng)過點 d的矩形的兩邊所組成的角。 ? 每個節(jié)點的地址為 (x,y)。 ? 沿著一個線性排列路由是很簡單的。 ? 得益于特殊網(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ā)送方向： ? 如果目標離順時針方向近，則用順時針方向； ? 否則選擇逆時針方向。 ARPA路由算法（ cont39。 ARPA路由算法 ? ARPA的路由算法是一個可靠、實用的分布式路由算法，也是今天流行的 Inter 路由算法的前身。 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é)點