【正文】 徑。 假定從任意源結(jié)點 s = ( X1 Y1 )到任意目的結(jié)點 d = ( X2 Y2 )。 尋徑從 s開始，首先沿著 X方向前進一直到 d所在的第 X2列為止，然后沿 Y方向前進直到 d。 四種模式 ： 東 — 北 ， 東 — 南 ， 西 — 北 ， 西 — 南 。 下面是一個例子： 0,7 1,7 2,7 3,7 4,7 4,6 7,6 1,5 4,5 7,5 1,4 2,4 3,4 4,4 5,4 7,4 1,3 2,3 3,3 4,3 5,3 6,3 7,3 2,2 4,2 7,2 2,1 3,1 4,1 5,1 6,1 7,1 2,0 Y X 東 — 北： ( 2 , 1 ) ? ( 7 , 6 ) 西 — 南： ( 5 , 4 ) ? ( 2 , 0 ) 東 — 南： ( 0 , 7 ) ? ( 4 , 2 ) 西 — 北： ( 6 , 3 ) ? ( 1 , 5 ) 特點 ： 總是先沿 X維方向?qū)?，然后再?Y維方向?qū)?，尋徑不會出現(xiàn)死鎖或循環(huán)等待現(xiàn)象。 可以擴充到 n維網(wǎng)絡(luò)，如 XYZ等等。 可用于存儲轉(zhuǎn)發(fā)或 蟲蝕 尋徑網(wǎng)絡(luò)，在源和目的結(jié)點之間形成一條距離最短的路徑。 （ 2）立方體網(wǎng)絡(luò)中的 E立方體尋徑 ： 假設(shè)有一個 N = 2n個結(jié)點的 n方體。每個結(jié)點的二進制編碼為： b = bn1 bn2 …b 1 b0 s = sn1 sn2 … s1 s0 d = dn1 dn2 … d1 d0 如何確定一條從 s到 d的步數(shù)最小的路徑 ？ 將 n維表示成 i = 1, 2, … n ，其中第 i維對應(yīng)結(jié)點地址中的第 i1位。設(shè) v = vn1 vn2 …v 1 v0 是路徑中的任一結(jié)點。 12 ?? iv方法 ： （ 1） 計算方向位。 R=riri1…r 1 。其中 nidSr iii ?,2,1,11 ??? ?? 使 i = 1 , v = s， 開始下面的步驟。 （ 2） 如果 ri = 1，則從當(dāng)前結(jié)點 v尋徑到下一結(jié)點 ； 如果 ri = 0，則跳過這一步。 （ 3） i = i + 1，如果 i ? n，則轉(zhuǎn)第 （ 2） 步，否則退出。 如下面的例子： 1101 0110 0010 0000 0100 0111 0001 0011 0101 1110 1010 1000 1100 1111 1001 1011 4維立方體網(wǎng)絡(luò) n = 4， s = 0110， d = 1101 尋徑 ： （ 1） 計算方向位。 i = 1， v = s ? 0 1 1 r4 1 1 0 r3 1 0 1 r2 0 1 1 r1 （ R= ） （ 2） r1= 1， 210111000101102 11???????? ?iiss 到（ 3） r2= 1， 310 1 0 10 0 1 00 1 1 120 1 1 1 12????????? ?iivv 到（ 4） r3= 0， 41 ????ii跳過一步（ 5） r4= 1， ，結(jié)束。到5111011000010120221 14?????????? ?iidvv路徑為： 0110 ?0111?0101?1101 0110 0010 0000 0100 0111 0001 0011 0101 1110 1010 1000 1100 1111 1001 1011 1101 特點 ： 尋徑按照從維 1到維 4的順序進行。 如果 s和 d的第 i位相同，則沿維 i的方向不需要尋徑，否則從當(dāng)前結(jié)點沿著這一維方向走向下一結(jié)點（立方體中，每維包括兩個結(jié)點）。重復(fù)這一過程直到到達目的結(jié)點。 采用自適應(yīng)尋徑要特別注意死鎖。 使用 虛擬通道的方法， 使實現(xiàn)自適應(yīng)尋徑更經(jīng)濟和更靈活。 方法 ：網(wǎng)格網(wǎng)絡(luò)中，同一維的所有連接都使用虛擬通道。 如下圖所示： 02 12 22 01 11 21 00 10 20 （ a）沒有虛擬通道的原型網(wǎng)絡(luò) 02 12 22 01 11 21 00 10 20 （ b） Y維方向有兩對虛擬通道 上圖是一個用 XY尋徑的網(wǎng)格網(wǎng)絡(luò)，在 Y維上用了兩對虛擬通道。如圖 b，這樣，就可以生成如下圖的兩個虛擬網(wǎng)絡(luò)， c網(wǎng)絡(luò)可以用來避免消息在向西傳輸出現(xiàn)的死鎖，因為所有想東的X通道都沒有使用。同樣， d中的虛擬網(wǎng)絡(luò)使用另一組 X方向的虛擬通道來支持向東的傳輸，在不同的時刻，使用不同的虛擬網(wǎng)絡(luò)，這樣死鎖就可以自動避免 02 12 22 01 11 21 00 10 20 （ c）向西方向傳遞消息 （ d）向東方向傳遞消息 02 12 22 01 11 21 00 10 20 單播模式（ Unicast）： 一個源結(jié)點 —— 一個目的結(jié)點。 選播模式（ Multicast）： 一個源結(jié)點 ——多個目的結(jié)點。（多播、組播） 廣播模式（ Broadcast）： 一個源結(jié)點 ——全體結(jié)點。 會議模式（ Conference）： 多個源結(jié)點 —— 多個目的結(jié)點。 通信流量（ Channel traffic）： 用傳輸有關(guān)消息所使用的通道數(shù)來表示。 通信時延（ Communication latency）： 用包的最長傳輸時間來表示。 優(yōu)化的尋徑網(wǎng)絡(luò)應(yīng)能以最小的通信流量和最小的通信時延實現(xiàn)有關(guān)的通信模式。但達到最小的流量的同時不一定能達到最小的時延，反之亦然。這與所使用的交換技術(shù)有關(guān)。 在 蟲蝕 尋徑方式下，網(wǎng)絡(luò)流量這個參數(shù)對效率的影響比較大。流量應(yīng)盡可能的小。 在存儲轉(zhuǎn)發(fā)網(wǎng)絡(luò)中，時延是最重要的問題。時延應(yīng)盡可能的短。 下面討論有關(guān)網(wǎng)絡(luò)連接計算機中的選播和廣播 ： 下圖是一個在 3?4網(wǎng)格上實現(xiàn)選播尋徑。源節(jié)點用 S表示，傳送一個包到標(biāo)號為 Di的 5個目的結(jié)點。這里 i=1， 2， 3， 4， 5。目的節(jié)點為 5個的選播可以用5次單播來實現(xiàn)，尋徑流量為 13條通道，而到 D3的路徑為最長，所以時延為 4。 D2 D1 S D3 D4 D5 選播還可以用下述方法實現(xiàn)， 在一個中間結(jié)點上復(fù)制所傳送的包，然后把該包的多個拷貝送到目的結(jié)點，這樣可以減少通道流量。下圖是這種方法的一種實現(xiàn)，流量等于 7，到 D3的距離最遠，等于4，這種方法比較適合存儲轉(zhuǎn)發(fā)交換。 D2 D1 S D3 D4 D5 – 下圖是使用貪婪算法實現(xiàn)選播的示意，是一種上述方法的實現(xiàn)，流量等于 6，時延等于 5，比較適合蟲蝕尋徑。不論對何種網(wǎng)絡(luò)，貪婪算法總是重復(fù)使用一個固定的操作規(guī)則：從當(dāng)前擁有數(shù)據(jù)的結(jié)點出發(fā)，向需要數(shù)據(jù)的距離最近且結(jié)點數(shù)最多的那些方向并行傳送一步，如此循環(huán)，直至傳遍所有需要數(shù)據(jù)的結(jié)點。如果最后發(fā)現(xiàn)某個通道（即一次數(shù)據(jù)發(fā)送操作）不在通往給定目標(biāo)結(jié)點的路徑上，則應(yīng)將其刪去。 – 下圖指出從 S出發(fā)，首先應(yīng)向右鄰結(jié)點發(fā)送數(shù)據(jù)，因為 S的左方只有 1個目的結(jié)點、上方有 3個目的結(jié)點、右方有４個目的結(jié)點；第二步從這２個擁有數(shù)據(jù)的結(jié)點出發(fā)，可以再向右發(fā)送（有 3個目的結(jié)點） …… 。只要每步遵守貪婪算法的規(guī)則，最后形成的不同路徑樹的時間和流量都是相同的。 D2 D1 S D3 D4 D5 流量等于 6，距離等于 5 在 3?4的網(wǎng)格中，使用一棵 4層的生成樹可以把一個包從源節(jié)點 S廣播到所有的網(wǎng)格節(jié)點，如上圖，到達樹第 i層上的節(jié)點的時延為 i。這種廣播樹產(chǎn)生的時延和流量都最小。 3 2 3 2 1 2 1 S 1 4 3 2 下面是超立方體上的廣播和選播 為了在 n立方體上實現(xiàn)廣播，可用類似的生成樹，使用貪婪算法，時延不超過 n就能到達所有的節(jié)點。下圖是一個根節(jié)點為 0000的 4立方體，超立方體廣播樹的流量最小。（紅色帶箭頭的為使用的通道） 0110 0010 0000 0100 0111 0001 0011 0101 1110 1010 1000 1100 1111 1001 1011 4維立方體網(wǎng)絡(luò) 下面討論立方體上的選播。源節(jié)點為 0101，圖中陰影部分的為目的節(jié)點。使用貪婪算法。（紅色帶箭頭的線為使用的通道） 0110 0010 0000 0100 0111 0001 0011 0101 1110 1010 1000 1100 1111 1001 1011 1101 維 3方向 維 2方向 維 1方向 維 4方向 超立方體的維數(shù)方向如上圖所示，由源節(jié)點 S=0101開始，向維 2方向可以到達兩個節(jié)點，向維 4方向可以到達 5個節(jié)點，因此，第一層所使用的通道是 01010111和 01011101。依照貪婪算法，第二層所使用的通道是 11011111， 11011100和 01110110，第三層所使用的通道是 11111110， 11111011， 11001000和 01100010。第四層所使用的通道是 11101010。在尋徑時，應(yīng)該比較所有各維方向的可達性，然后選擇某些維使剩余的目的節(jié)點的集合最小。如果兩維之間有連線，那么選擇哪一維都可以，因此，所生成的樹不是唯一的。 有關(guān)互連網(wǎng)絡(luò)的實例，請自己查閱相關(guān)資料。除此之外，請查閱有關(guān)貪婪算法的相關(guān)資料，下次課希望有同學(xué)能夠結(jié)合實例，講解一下。