數(shù)據(jù)通信與計(jì)算機(jī)網(wǎng)絡(luò)--08分組交換-在線瀏覽
2025-02-05 06:34本頁面
【正文】 由選擇 在每個(gè)節(jié)點(diǎn)上保持一張路由表 ,表上標(biāo)明對(duì)每一個(gè)目的地址應(yīng)走哪條鏈路進(jìn)行轉(zhuǎn)發(fā) .路由表是在整個(gè)系統(tǒng)進(jìn)行配置時(shí)生成的 .配置時(shí)根據(jù)事先計(jì)算好的 “網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間最短路徑 ”,將這些最短通路制成路由表 ,存放在各個(gè)節(jié)點(diǎn)中 .每一個(gè)分組都可在所到達(dá)的節(jié)點(diǎn)中查找下一步應(yīng)轉(zhuǎn)發(fā)到哪一個(gè)節(jié)點(diǎn) (下一站節(jié)點(diǎn)或后繼節(jié)點(diǎn) ). 經(jīng)典的求最短路徑算法是 Dijkstra算法 .它的條件是已知網(wǎng)絡(luò)的拓?fù)浜透麈溌烽L度 , 主要是通過計(jì)算任意兩節(jié)點(diǎn)間的最小鏈路長度 ,求得從源節(jié)點(diǎn)到目的節(jié)點(diǎn)間最短通路 .第 8講 分組交換與路由選擇固定路由選擇固定路由選擇Dijkstra算法 對(duì)于一個(gè)無向圖 G=(V， E),其中 V表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合 ,E表示網(wǎng)絡(luò)中所有鏈路的集合 ,D(v)為源節(jié)點(diǎn)到節(jié)點(diǎn) v的距離 ,l(i, j)為節(jié)點(diǎn) i至節(jié)點(diǎn) j之間的距離 .(1)初始化 任選一個(gè)節(jié)點(diǎn)作為源節(jié)點(diǎn) ,不妨 令 V={1},對(duì)所有不在 V中的節(jié)點(diǎn) v,寫出 :14 56232221113355圖 求最短路徑算法的網(wǎng)絡(luò)拓?fù)鋵?shí)際編程時(shí)一般取 D(v)=1000代替 ∞.源節(jié)點(diǎn)第 8講 分組交換與路由選擇固定路由選擇固定路由選擇(2)尋找一個(gè)不在 V中的節(jié)點(diǎn) w,其 D(w)值為最小 .把 w加入到 V中 .然后對(duì)所有不在 V中的節(jié)點(diǎn) ,用[D(v),D(w)+l(w, v)]中較小的值去更新原有的 D(v)值 ,即 : D(v) ← Min[D(v),D(w)+l(w, v)](3)重復(fù)步驟 (2),直到所有的網(wǎng)絡(luò)節(jié)點(diǎn)都在 V中為止 . 由 Dijkstra算法可知 ,若將已知的各鏈路長度改為 鏈路時(shí)延 ,跳數(shù) ,帶寬或費(fèi)用 ,就相當(dāng)于求任意兩節(jié)點(diǎn)之間具有最小時(shí)延 ,最少跳數(shù) ,最大帶寬或最小費(fèi)用的通路 .所以 , 求最短路徑算法具有普遍的應(yīng)用價(jià)值 .第 8講 分組交換與路由選擇固定路由選擇固定路由選擇基于左圖的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) ,采用 Dijkstra算法 ,計(jì)算以節(jié)點(diǎn) 1為源節(jié)點(diǎn)的最短通路的過程 .表中帶圓圈的數(shù)字表示的是 : 在每一次執(zhí)行步驟 (2)時(shí) , 所尋找到的具有最小值的 D(w)值 .步驟 V D(2) D(3) D(4) D(5) D(6)初始化 {1} 2 5 1 ∞ ∞ 1 {1,4}
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1