【正文】 接口 ：控制臺接口 ? 局域網(wǎng)接口：以太網(wǎng)、令牌環(huán)網(wǎng)、光纖網(wǎng) ? 廣域網(wǎng)接口： ATM、 X2 DDN、 FRN、 ISDN ? 邏輯接口： LOOP BACK， NULL， CHANNEL 典型的路由器的結(jié)構(gòu) 路由 選擇 路由選擇處理機(jī) 路由選擇協(xié)議 路由表 3 輸入端口 3 交換結(jié)構(gòu) 輸入端口 輸出端口 分組 轉(zhuǎn)發(fā) 轉(zhuǎn)發(fā)表 分組處理 輸出端口 … … 1 1 1 3 3 1 2 2 2 2 3——網(wǎng)絡(luò)層 2——數(shù)據(jù)鏈路層 1——物理層 分組處理 ? 路由器收到分組后，根據(jù)分組中包含的目的地址，在轉(zhuǎn)發(fā)表中選擇適當(dāng)?shù)妮敵龆丝?，轉(zhuǎn)發(fā)分組。 ? 路由器中的輸入或輸出隊(duì)列產(chǎn)生溢出是造成分組丟失的重要原因。 這會(huì)產(chǎn)生一定的時(shí)延 。數(shù)據(jù)鏈路層處理模塊將分組加上鏈路層的首部和尾部 ， 交給物理層后發(fā)送到外部線路 。 分組到了目標(biāo)網(wǎng)絡(luò)后，由終端路由器將分組 送到目標(biāo)主機(jī)。所以，在網(wǎng)絡(luò)上路由是以目標(biāo) IP地址中的網(wǎng)絡(luò)號為依據(jù)的。 路由表的信息 ? 典型地，路由表包含許多 (N,R) 向量，其中 N是目的網(wǎng)絡(luò)的 IP地址， R是為了到達(dá)相應(yīng)目的網(wǎng)絡(luò)要經(jīng)過的下一個(gè)路由器的 IP地址 (下一跳， next hop)。 網(wǎng) 1 網(wǎng) 4 網(wǎng) 3 網(wǎng) 2 目的主機(jī)所在的網(wǎng)絡(luò) 下一跳路由器的地址 直接交付，接口 1 直接交付，接口 0 路由器 R2 的路由表 鏈路 4 鏈路 3 鏈路 2 鏈路 1 R2 R3 R1 0 1 R2 R3 R1 在路由表中，對每一條路由，最主要的是 （目的網(wǎng)絡(luò)地址，下一跳地址） 基于網(wǎng)絡(luò)的路由選擇 ? 僅僅基于目的網(wǎng)絡(luò)號來選擇路由會(huì)有幾個(gè)后果： 1. 在大多數(shù)實(shí)現(xiàn)方式中，這意味著所有到某個(gè)給定網(wǎng)絡(luò)的通信量都走同一條路徑。 3. A到 B和 B到 A的數(shù)據(jù)報(bào)的路徑可能不同。 ? 算法在計(jì)算上應(yīng)簡單 。 ? 算法應(yīng)具有穩(wěn)定性 。 ? 算法應(yīng)是最佳的 。 ? 這里 “ 代價(jià) ” 并不一定是僅指 “ 錢 ” ， 而是由一個(gè)或幾個(gè)因素綜合決定的一種 度量(metric)， 如鏈路長度 、 數(shù)據(jù)率 、 鏈路容量 、是否要保密 、 傳播時(shí)延等 ， 甚至還可以是一天中某一個(gè)小時(shí)內(nèi)的通信量 、 結(jié)點(diǎn)的緩存被占用的程度 、 鏈路差錯(cuò)率等 。 最佳路由 ? 不存在一種絕對的最佳路由算法 。 ? 實(shí)際的路由選擇算法 ， 應(yīng)盡可能接近于理想的算法 。 ? 路由選擇的環(huán)境往往是不斷變化的 ， 而這種變化有時(shí)無法事先知道 。 最出名的最短路徑算法有兩個(gè)： BellmanFord算法和 Dijkstra算法 。 ? 若將鏈路長度改為鏈路時(shí)延或費(fèi)用 ，就相當(dāng)于求任意兩節(jié)點(diǎn)之間具有最小時(shí)延或最小費(fèi)用的路徑 。 ? 設(shè)某個(gè)節(jié)點(diǎn)為源節(jié)點(diǎn) ， 每次尋找一個(gè)節(jié)點(diǎn)到源節(jié)點(diǎn)的最短路徑 ， 直至找到所有的節(jié)點(diǎn) 。 最短路徑算法－ Dijkstra算法 ? 令 D(v)為源節(jié)點(diǎn)到某個(gè)節(jié)點(diǎn) v的距離 ，即從源節(jié)點(diǎn)沿著某一路徑到節(jié)點(diǎn) v的所有鏈路的長度之和 ， 再令 L(i,j)為節(jié)點(diǎn) i至節(jié)點(diǎn) j的距離 。 對所有不在 N中的節(jié)點(diǎn) ， 有： D(v)＝ L(i,j) ；若節(jié)點(diǎn) v與節(jié)點(diǎn) 1直接相連 D(v)＝ ∞； 若節(jié)點(diǎn) v與節(jié)點(diǎn) 1不直接相連 N中的節(jié)點(diǎn) w， 其 D(w)值 最小 ， 把 w加入到 N中 ， 然后對所有不在 N中的節(jié)點(diǎn) ， 用[ D(v)， D(w)＋ L(w,v)]中較小的值去更新原有的 D(v)值 ， 即 : D(v)← Min[ D(v)， D(w)＋ L(w,v)] 。 Dijkstra算法 1 4 5 6 3 2 5 2 1 1 1 2 2 3 3 5 步驟 N D（ 2） D（ 3） D（ 4） D（ 5） D（ 6） 初始化 { 1 } 2 5 1 ∞ ∞ 1 2 3 4 5 Dijkstra算法 1 4 5 6 3 2 5 2 1 1 1 2 2 3 3 5 步驟 N D（ 2） D（ 3） D（ 4） D（ 5） D（ 6） 初始化 {1} 2 5 1 ∞ ∞ 1 { 1， 4 } 2 4 1 2 ∞ 2 3 4 5 Dijkstra算法 1 4 5 6 3 2 5 2 1 1 1 2 2 3 3 5 步驟 N D（ 2） D（ 3） D（ 4） D（ 5） D（ 6） 初始化 { 1 } 2 5 1 ∞ ∞ 1 { 1， 4 } 2 4 1 2 ∞ 2 { 1， 2， 4 } 2 4 1 2 ∞ 3 4 5 Dijkstra算法 1 4 5 6 3 2 5 2 1 1 1 2 2 3 3 5 步驟 N D（ 2） D（ 3） D（ 4） D（ 5） D（ 6） 初始化 {1} 2 5 1 ∞ ∞ 1 { 1， 4 } 2 4 1 2 ∞ 2 { 1， 2， 4 } 2 4 1 2 ∞ 3 { 1， 2， 4， 5 } 2 3 1 2 4 4 5 Dijkstra算法 1 4 5 6 3 2 5 2 1 1 1 2 2 3 3 5 步驟 N D（ 2） D（ 3） D（ 4） D（ 5） D（ 6） 初始化 {1} 2 5 1 ∞ ∞ 1 { 1， 4 } 2 4 1 2 ∞ 2 { 1， 2， 4 } 2 4 1 2 ∞ 3 { 1， 2， 4， 5 } 2 3 1 2 4 4 { 1， 2， 3， 4， 5 } 2 3 1 2 4 5 Dijkstra算法 1 4 5 6 3 2 5 2 1 1 1 2 2 3 3 5 步驟 N D（ 2） D（ 3） D（ 4） D（ 5） D（ 6） 初始化 {1} 2 5 1 ∞ ∞ 1 { 1， 4 } 2 4 1 2 ∞ 2 { 1， 2， 4 } 2 4 1 2 ∞ 3 { 1， 2， 4， 5 } 2 3 1 2 4 4 { 1， 2， 3， 4， 5 } 2 3 1 2 4 5 { 1， 2， 3， 4， 5， 6 } 2 3 1 2 4 節(jié)點(diǎn)的路由表 1 4 5 6 3 2 2 1 1 1 2 目的節(jié)點(diǎn) 后續(xù)節(jié)點(diǎn) 2 2 3 4 4 4 5 4 6 4 以節(jié)點(diǎn) 1 為根的 最短路徑樹 從路由算法的自適應(yīng)性考慮 ? 根據(jù)路由算法對網(wǎng)絡(luò)變化的適應(yīng)能力 ，主要分為兩種類型： ? 靜態(tài)路由選擇策略 ——即非自適應(yīng)路由選擇 ， 其特點(diǎn)是簡單和開銷較小 ，但不能及時(shí)適應(yīng)網(wǎng)絡(luò)狀態(tài)的變化 。 靜態(tài)路由 ? 靜態(tài)路由是一種特殊的路由 ， 它是由網(wǎng)絡(luò)管理員采用手工方法在路由器上配置而成 。 ? 靜態(tài)路由能夠節(jié)約網(wǎng)絡(luò)控制開銷 ， 適合拓?fù)浣Y(jié)構(gòu)簡單的網(wǎng)絡(luò) 。 默認(rèn)路由 ? 在路由表中，一般還有默認(rèn)路由。 ? 在路由表中該項(xiàng)網(wǎng)絡(luò)號為 。 分層次的路由選擇協(xié)議 ? 因特網(wǎng)采用 分層次的路由選擇協(xié)議 。 如果讓所有的路由器知道所有的網(wǎng)絡(luò)應(yīng)怎樣到達(dá) ， 則這種路由表將非常大 ， 處理起來也太花時(shí)間 。 ? 許多單位不愿意外界了解自己單位網(wǎng)絡(luò)的布局細(xì)節(jié)和本部門所采用的路由選擇協(xié)議 （ 這屬于本部門內(nèi)部的事情 ） ， 但同時(shí)還希望連接到因特網(wǎng)上 。 ? 一個(gè)自治系統(tǒng)是一個(gè)互聯(lián)網(wǎng) ， 其最重要的特點(diǎn)就是自治系統(tǒng)有權(quán)自主地決定在本系統(tǒng)內(nèi)應(yīng)采用何種路由選擇協(xié)議 。 ? 一個(gè)自治系統(tǒng)的所有路由器在本自治系統(tǒng)內(nèi)都必須是連通的 。 目前這類路由選擇協(xié)議使用得最多 ， 如 RIP 和 OSPF 協(xié)議 。 這樣的協(xié)議就是外部網(wǎng)關(guān)協(xié)議 EGP。 R1 H1 H2 內(nèi)部網(wǎng)關(guān)協(xié)議 IGP （例如， RIP） 自治系統(tǒng) A 自治系統(tǒng) B 自治系統(tǒng) C IGP IGP IGP IGP IGP IGP IGP IGP IGP IGP IGP IGP EGP EGP EGP 內(nèi)部網(wǎng)關(guān)協(xié)議 IGP （例如， OSPF） 外部網(wǎng)關(guān)協(xié)議 EGP （例如， BGP4） IGP R3 R2 自治系統(tǒng)和 內(nèi)部網(wǎng)關(guān)協(xié)議、外部網(wǎng)關(guān)協(xié)議 兩點(diǎn)注意 ? 因特網(wǎng)的早期 RFC 文檔中未使用 “ 路由器 ”而是使用 “ 網(wǎng)關(guān) ” 這一名詞 。應(yīng)當(dāng)把這兩個(gè)屬于當(dāng)作同義詞 。 但 RFC 在使用 EGP 這個(gè)名詞時(shí)出現(xiàn)了一點(diǎn)混亂 ，因?yàn)樽钤绲囊粋€(gè)外部網(wǎng)關(guān)協(xié)議的協(xié)議名字正好也是 EGP。 路由信息協(xié)議 RIP (Routing Information Protocol) ? 路由信息協(xié)議 RIP 是內(nèi)部網(wǎng)關(guān)協(xié)議 IGP中最先得到廣泛使用的協(xié)議。 ? RIP 協(xié)議要求網(wǎng)絡(luò)