《計算機互連網(wǎng)絡(luò)》ppt課件(文件)
【正文】 網(wǎng)絡(luò)尋徑算法（路由算法） 目的 ：根據(jù)給定的輸入 /輸出對應(yīng)關(guān)系 ， 確定各開關(guān)的狀態(tài) 。 輸入 第 2 級 第 1 級 第 0 級 輸出000 00 000 1 00 10 1 0 0 1 00 11 01 11 00 1 001 0 1 1 0111 0 1 101 11 1 112022/5/31 計算機系統(tǒng)結(jié)構(gòu) 27 Omega網(wǎng)尋徑?jīng)_突 給定傳輸 101B→ 011B， 二者異或結(jié)果為 110B， 路徑 如下圖 紅線 所示 。個）結(jié)點， 1≤N39。向不同方向進行的發(fā)送不能同時進行（具有這種能力的互連網(wǎng)不屬于現(xiàn)在的討論范圍）。 如圖 （ 圖中實線箭頭表示一個數(shù)據(jù)的一次實際傳送 ， 虛線指出上一步已有數(shù)據(jù)的結(jié)點 ） 。 選播流量最少算法是最小成本生成樹算法，具體操作順序既可以是先短邊后長邊“長樹”，也可以是先長邊后短邊“砍樹” （ 教材 P426圖(c)）。 2022/5/31 計算機系統(tǒng)結(jié)構(gòu) 35 (1)單級網(wǎng)格網(wǎng)（ Mash網(wǎng)）貪婪算法 算法： 以教材 P426圖 ，小圖 (a)指出總共有 1個源結(jié)點 S和 5個目的結(jié)點。 小圖 (a)指出廣播算法的時間是 4， 流量是 15。 0 0 0 0 Cu b e0 Cu b e1 0 0 01 0 0 1 0 Cu b e1 Cu b e00 0 1 0 0 1 1 1 0 0 0 1 1 0 1 1 (a) 先傳 Cu b e0方向，流量 = 2 (b ) 先傳 C u b e1方向，流量 =3單級立方體網(wǎng)絡(luò)貪婪算法的簡單例子2022/5/31 計算機系統(tǒng)結(jié)構(gòu) 37 0 1 0 1 Cu b e3 0 1 0 1 1 1 0 1 Cu b e1 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 Cu b e0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 0 Cu b e2 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 5 1 4 0 7 3 6 2 1 3 9 1 2 8 1 5 1 1 1 4 1 0單級立方體網(wǎng)絡(luò)貪婪算法的復(fù)雜例子 再看教材 P426圖 (b)的例子。 習(xí)題： P446，題 3，題 10，題 26(1)～ (2)，題 27(3)。教材 P427采用了Cube Cube Cube0、 Cube2的發(fā)送順序，如下圖所示，時間 =4，總流量 =10。 先看一個簡單的例子 （ 下圖 ） ：已知 N=4， 維數(shù) n=2， 源結(jié)點是 0， 目的結(jié)點是 1和 3。只要每步遵守貪婪算法的規(guī)則，最后形成的不同路徑樹的時間和流量都是相同的。 不論對何種網(wǎng)絡(luò)，貪婪算法總是重復(fù)使用一個固定的操作規(guī)則：從當(dāng)前擁有數(shù)據(jù)的結(jié)點出發(fā)，向需要數(shù)據(jù)的結(jié)點數(shù)最多的方向并行傳送一步，如此循環(huán)，直至傳遍所有需要數(shù)據(jù)的結(jié)點。 時間 流量 Nn 2lo g??????????101122nini N2022/5/31 計算機系統(tǒng)結(jié)構(gòu) 32 2 3 0 1 6 7 4 5 單級立方體網(wǎng)絡(luò)廣播算法實例 從節(jié)點 0開始，順序是 cube0－ cube2 0 4 2 6 1 5 3 7 000 000 000 000 001 011 111 001 011 001 101 010 010 110 100 2022/5/31 計算機系統(tǒng)結(jié)構(gòu) 33 單級立方體網(wǎng)絡(luò)廣播算法 實例 0 0 0 0 C u b e3 0 0 0 0
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1