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