【正文】 行分組轉發(fā)的問題 ， 因此有必要先研究網(wǎng)絡的拓撲結構 。 (1) 用圖表示網(wǎng)絡 可以用圖論中的 “ 圖 ” (Graph)表示一個分組交換網(wǎng)絡 ， 圖的 “ 頂點 ” 表示網(wǎng)絡結點 ， 連接頂點的 “ 邊 ”表示網(wǎng)絡鏈路 。 例如 ， 網(wǎng)絡圖 G=(V,E)， 其中 ， V是網(wǎng)絡結點的集合 ， E是鏈路的集合 。 可用一組鏈路的有序集 (l1,l2,… ,ln)來表示網(wǎng)絡的一條有向通路 (Path)， 該通路稱為 “ 分組傳送路徑 ” (Route)。 因此 ， 所謂 “ 路由算法 ” 或 “ 路徑選擇算法 ” ， 就是指確定分組從它的源點到達目的點的有向傳輸通路的法則 。 二、路由選擇算法 交 換 技 術第 5 章分 組 交 換55 路由表的簡化 考慮下圖所示的網(wǎng)絡 ， 網(wǎng)絡圖 G=(V,E)， 其中 ，V={A,B,C,D,E,F} ， E={l1,l2,… l10}。 假設有一分組欲從 A點傳送到 D點 ， 它可以選擇幾條不同的通路 ， 分別表示為 A－ B－ D、 A－ C－ E－ D和 A－ C－ D， 等等 。 用鏈路的有序集表示 ， 則為 ( l1,l3 ) 、 ( l2,l4,l7 )和( l2,l6 )， 等等 。 通路（路徑）的表示 A C E F D B l 6 l 1 l 10 l 4 l 7 l 8 l 5 l 2 l 3 l 9 ? 現(xiàn)在的問題 : ? 1)用什么算法來選擇合適的路徑 ? ? 2)依據(jù)什么信息來做這種選擇 ? ? 3)如何執(zhí)行這種選擇策略 ? ? 4)怎么評價所選路徑的好壞 ? 下面討論路由選擇的一般原理及不同的 路由選擇策略 和 算法 . 交 換 技 術第 5 章分 組 交 換57 一個理想的路由選擇算法應滿足如下要求： 1） 算法必須是 正確 的和 完整 的 。 2） 算法在計算上應盡可能 簡單 。 3） 算法要有 自適應性 。 4） 算法應具有 穩(wěn)定性 。 5）算法應是 公平 的。 6）算法應是 最佳 的。 （ 2） 理想的路由選擇算法 正確完整 每一個節(jié)點交換機中的路由表 ,都必須給出所有可能的目的節(jié)點的下一個節(jié)點 .沿各交換機中的路由表指示的路由分組一定能到達目的計算機所在的哪個交換機 .簡單 為了減少分組轉發(fā)處理時延 .自適應性 網(wǎng)絡某節(jié)點流量過大或故障算法應該能自動適應改變 . ? 穩(wěn)定性是指 :網(wǎng)絡拓撲和通信流量相對穩(wěn)定的情況下 ,算法得出的路由也應該相對固定 . ? 公平是指 :算法應該對所有用戶都是平等的 . ? 最佳是指 :最低的代價來實現(xiàn)路由算法 ,代價是可以有多個因素比如 :鏈路長度 ,數(shù)據(jù)率 ,鏈路容量 ,保密 ,傳輸延時等 .最佳通常是在某種特定要求下得到的較為合理的選擇 . ? 實際的路由算法應該接近理想算法 ,并可能有不同的側重 . 交 換 技 術第 5 章分 組 交 換59 路由選擇算法 是解決如何根據(jù)網(wǎng)絡拓撲和狀態(tài) ， 按照一定的性能準則 ， 計算分組傳送路徑的問題 。 路由策略 是解決路由的選擇能否適應網(wǎng)絡拓撲和狀態(tài)變化的問題 。 路由選擇算法僅是路由策略的一部分 。 從路由的選擇能否隨網(wǎng)絡的變化而自適應地進行調整變化來區(qū)分 ， 路由策略可分為 兩大類 ， 即非自適應路由選擇策略與自適應路由選擇策略 。 非自適應路由選擇 也叫做靜態(tài)路由選擇 ， 其特點是簡單和開銷較小 ， 但不能及時適應網(wǎng)絡狀態(tài)的變化 。 自適應路由選擇 也叫做動態(tài)路由選擇 ， 其特點是能較好地適應網(wǎng)絡狀態(tài)的變化 ， 但實現(xiàn)起來較為復雜 。 三、路由策略的分類 交 換 技 術第 5 章分 組 交 換60 非自適應路由選擇 該方法是在每個結點上保持一張路由表 ， 表上標明去每一個目的結點的分組應從哪條鏈路進行轉發(fā) 。 路由表是在整個系統(tǒng)進行 配置 時生成的 ， 并且在此后的一段相當時間內(nèi)保持固定不變 。 當網(wǎng)絡拓撲固定不變并且通信流量相對穩(wěn)定時 ， 采用該方法是適當?shù)?。 這種路由選擇策略的關鍵是要算出給定網(wǎng)絡中任意兩個結點之間的 最短路徑 ， 然后 制作出 相應的路由表 。 非自適應路由選擇主要有： 固定路由法 、 概率路由法 和 洪泛法 。 一、固定路由法 交 換 技 術第 5 章分 組 交 換61 Dijkstra 算法 Dijkstra算法 是一種常用的求 最短路徑的算法 。已知條件是整個網(wǎng)絡的拓撲和各鏈路的長度 。 給定網(wǎng)絡拓撲和鏈路長度如右圖所示 ， Dijkstra算法即尋找從源結點到網(wǎng)絡中其他各結點的最短路徑 。 假設結點 1為源結點 ， 令 D(v) 表示源結點到結點 v的距 1234 561452113335離 ， 它是沿某一路徑的所有鏈路的長度之和 。 再令l(i,j)為結點 i至結點 j之間的距離 。 Dijkstra算法每次找一個結點到源結點的最短路徑 ， 直到把所有結點都找到為止 。 交 換 技 術第 5 章分 組 交 換62 整個 算法 包括以下兩個部分： ① 初始化 令 N 表示網(wǎng)絡結點的集合 ， 先令 N＝ {1}。 對所有不在 N 中的結點 v， 寫出： ② 尋找一個不在 N中的結點 w， 其 D(w)值為最小 。 把 w加入到 N 中 。 然 后 對 所 有 不 在 N 中的結點 v ， 用[D(v),D(w)+l(w,v)]中的較小的值去更新原有的 D(v)值 ，即： D(v)←Min[D(v),D(w)+l(w,v)] ③ 重復步驟 ② ， 直到所有的網(wǎng)絡結點都在 N中為止 。 Dijkstra 算法 (續(xù) ) 不直接相連 與結點 1 若結點 直接相連 與結點 1 若結點 ) , 1 ( ) ( v v v l v D ? ? ? ? = 交 換 技 術第 5 章分 組 交 換63 用 Dijkstra 算法求出的最短路徑 以 1為根的 最 短 路 徑 樹 611133324556243D4= 1（ c ) N = { 1 , 4 }D2= 4 D3= 51243D4= 1D2= 3D3= 4D5= 2D6= 551243D4= 1D2= 3D3= 3D5= 26D6= 551243D4= 1D2= 3 D3= 3D5= 26D6= 551243D4= 1D2= 3 D3= 3D5= 2( g ) N = { 1 , 4 , 5 , 3 , 2 , 6 }目 的 結 點下 一 結 點3412556124312435124365243( f ) N = { 1 , 4 , 5 , 3 , 2 }6512432345644444（b） 結 點1的 路 由 表（（a） 網(wǎng) 絡 拓 撲 結 構( d ) N = { 1 , 4 , 5 }( e ) N = { 1 , 4 , 5 , 3 }生成結點 1 路由 表 交 換 技 術第 5 章分 組 交 換64 事先在每個結點設置一個路由表 ， 路由表中給出幾個可供選擇的輸出鏈路 ， 并且對每條鏈路賦予一個 概率 。 當一個分組到達該結點時 ， 結點產(chǎn)生一個從 機數(shù) ， 然后按此隨機數(shù)的大小 ， 查表找出相應的輸出鏈路 。 這種方法可使通信流量平衡 ,平均時延小 。 二、概率路由法 結點K中 的路由表目的站 經(jīng)過 概率 概率 概率經(jīng)過 經(jīng)過ABCDELMMNNPNMPNNLPMM… … … …A BCDELM NKP交 換 技 術第 5 章分 組 交 換65 洪泛法是當結點收到一個不是發(fā)給它的分組時 ， 就將該分組轉發(fā)到 所有 與此結點相連的鏈路上 (除過分組剛剛離開的那個結點 )。 洪泛法簡單可靠 ， 當網(wǎng)絡的通信流量很小時 ， 可使分組的傳送時延最小 。 實際應用中很少采用洪泛法 。 這是因為洪泛法會導致網(wǎng)絡出現(xiàn)擁塞 。 當然可以采用多種方法來限制分組的數(shù)目 ， 一種是限制分組在網(wǎng)絡中轉發(fā)的次數(shù) (跳數(shù) )；另一種是建立登記表來限制分組再次通過該結點 。 但這些方法不能根本解決洪泛法引起的多個分組副本占用網(wǎng)絡資源的問題 。 在某些特殊場合 ， 如需要將某種信息迅速擴散到全網(wǎng)各個結點時 ， 洪泛法還是有用的 。 三、洪泛法（ flooding） 交 換 技 術第 5 章分 組 交 換66 自適應路由就是網(wǎng)絡結點定期或不定期地根據(jù)當時的網(wǎng)絡狀態(tài) 調整路由 。 因此網(wǎng)絡拓撲和網(wǎng)絡狀態(tài)信息的獲取就成為自適應路由的關鍵 。 自適應路由選擇 這種路由選擇策略是每個結點定期或不定期地與相鄰結點交換網(wǎng)絡狀態(tài)信息 。 經(jīng)過多次交換 ， 各結點均可掌握全網(wǎng)的情況 ， 從而根據(jù)某種路由算法計算并更新其路由表 。 在分布式路由選擇策略中 ， 最基本的算法有 兩個 ： 距離向量算法 鏈路狀態(tài)算法 一、分布式路由選擇策略 交 換 技 術第 5 章分 組 交 換67 （ 1）距離向量算法 在采用距離向量法的網(wǎng)絡中 ， 每個結點都有一張路由表 。 路由表中包含兩列向量 ， 一個是距離向量 ， 另一個稱為后繼結點 (即下一結點 )向量 。 這里的 “ 距離 ” ，可以用結點間路徑的跳數(shù) 、 時延和排隊隊長等度量 。 例如 ， ARPANET的路由表中擁有如下兩個向量 。 ??????=??????=11,iiiNiiNssiddSD ??其中 ， Di為結點 i的時延向量； dij為結點 i至結點 j的最小時延的當前估值 。 N為網(wǎng)絡中的結點數(shù)； Si為結點 i 的后繼結點向量； sij為后繼結點 ， 即從結點 i到結點 j的當前最小時延路由中結點 i的后繼結點 。 交 換 技 術第 5 章分 組 交 換68 距離向量算法舉例 1234 561452113335Si Di 目的結點 １ ２ ３ ４ ５ ６ 下一結點 － ４ ３ ４ ３ ４ 延遲 ０ ３ ５ １ ６ 9 4 0 3 2 3 6 D2 3 3 0 2 1 4 D3 1 2 2 0 1 4 D4 （ a）網(wǎng)絡拓撲與時延 （ b）結點１的路由表 目的結點 １ ２ ３ ４ ５ ６ 下一結點 － ４ 4 ４ 4 ４ 延遲 ０ ３ 3 １ 2 ５ Si Di （ c）結點１收到的時延向量 （ d）結點１更新后的路由表 交 換 技 術第 5 章分 組 交 換69 距離向量算法的缺陷及解決方法 無窮計算問題 距離向量算法在理論上是能有效工作的 ， 但在實際運用中卻有很大的缺陷 。 特別是它對好