計算機互連網(wǎng)絡ppt課件(參考版)
2025-05-06 07:08本頁面
【正文】 習題： P446，題 3，題 10，題 26(1)～ (2)，題 27(3)。教材 P427采用了Cube Cube Cube0、 Cube2的發(fā)送順序，如下圖所示，時間 =4，總流量 =10。 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)絡貪婪算法的簡單例子2022/5/31 計算機系統(tǒng)結構 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)絡貪婪算法的復雜例子 再看教材 P426圖 (b)的例子。 先看一個簡單的例子 （ 下圖 ） ：已知 N=4， 維數(shù) n=2， 源結點是 0， 目的結點是 1和 3。 小圖 (a)指出廣播算法的時間是 4， 流量是 15。只要每步遵守貪婪算法的規(guī)則，最后形成的不同路徑樹的時間和流量都是相同的。 2022/5/31 計算機系統(tǒng)結構 35 (1)單級網(wǎng)格網(wǎng)（ Mash網(wǎng)）貪婪算法 算法： 以教材 P426圖 ，小圖 (a)指出總共有 1個源結點 S和 5個目的結點。 不論對何種網(wǎng)絡，貪婪算法總是重復使用一個固定的操作規(guī)則：從當前擁有數(shù)據(jù)的結點出發(fā)，向需要數(shù)據(jù)的結點數(shù)最多的方向并行傳送一步，如此循環(huán)，直至傳遍所有需要數(shù)據(jù)的結點。 選播流量最少算法是最小成本生成樹算法，具體操作順序既可以是先短邊后長邊“長樹”，也可以是先長邊后短邊“砍樹” （ 教材 P426圖(c)）。 時間 流量 Nn 2lo g??????????101122nini N2022/5/31 計算機系統(tǒng)結構 32 2 3 0 1 6 7 4 5 單級立方體網(wǎng)絡廣播算法實例 從節(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)結構 33 單級立方體網(wǎng)絡廣播算法 實例 0 0 0 0 C u b e3 0 0 0 0 1 0 0 0 C u b e2 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 C u b e1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0
教學課件相關推薦
鄂ICP備17016276號-1