【正文】 計算機網(wǎng)絡(luò) Computer Networks 南京郵電大學(xué)計算機學(xué)院 計算機通信教研室 第七章 因特網(wǎng) IP路由 路由器的功能 ? 網(wǎng)絡(luò)分段，實現(xiàn)子網(wǎng)的劃分 ? 提供不同類型網(wǎng)絡(luò)的互聯(lián) ? 隔離廣播風(fēng)暴 ? 實現(xiàn)子網(wǎng)之間的信息傳輸 ? 提供安全訪問的機制 ? 支持網(wǎng)絡(luò)層的特殊服務(wù) 路由器在網(wǎng)際互連中的作用 ? 當(dāng)主機 A 要向另一個主機 B 發(fā)送數(shù)據(jù)報時 ，先要檢查目的主機 B 是否與源主機 A 連接在同一個網(wǎng)絡(luò)上 。 ? 如果是 ， 就將數(shù)據(jù)報 直接交付 給目的主機 B 而不需要通過路由器 。 ? 如果目的主機與源主機 A 不是連接在同一個網(wǎng)絡(luò)上 ， 則應(yīng)將數(shù)據(jù)報發(fā)送給本網(wǎng)絡(luò)上的某個路由器 ， 由該路由器按照轉(zhuǎn)發(fā)表指出的路由將數(shù)據(jù)報轉(zhuǎn)發(fā)給下一個路由器 。 這就叫作 間接交付 。 直接交付和間接交付 間接交付 間接交付 間接交付 A B C 直接交付 直接交付 直接交付不需要使用路由器 但間接交付就必須使用路由器 路由器組成 ? 路由器 實際上就是一種通信專用的計算機，具有和計算機類似的結(jié)構(gòu)。 ? 處理器 CPU：微處理器或 RISC微處理器 ? 存儲器 ： ROM、 NVRAM FLASH RAM、 RAM ? 接口 ：控制臺接口 ? 局域網(wǎng)接口：以太網(wǎng)、令牌環(huán)網(wǎng)、光纖網(wǎng) ? 廣域網(wǎng)接口： ATM、 X2 DDN、 FRN、 ISDN ? 邏輯接口： LOOP BACK， NULL， CHANNEL 典型的路由器的結(jié)構(gòu) 路由 選擇 路由選擇處理機 路由選擇協(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ù)妮敵龆丝冢D(zhuǎn)發(fā)分組。 ? 若路由器處理分組的速率趕不上分組進入隊列的速率，則隊列的存儲空間最終必定減少到零，這就使后面再進入隊列的分組由于沒有存儲空間而只能被丟棄。 ? 路由器中的輸入或輸出隊列產(chǎn)生溢出是造成分組丟失的重要原因。 輸入端口對線路上 收到的分組的處理 ? 數(shù)據(jù)鏈路層剝?nèi)撞亢臀膊亢?， 將分組送到網(wǎng)絡(luò)層的隊列中排隊等待處理 。 這會產(chǎn)生一定的時延 。 物理層處理 數(shù)據(jù)鏈路層 處理 網(wǎng)絡(luò)層處理 分組排隊 交 換 結(jié) 構(gòu) 輸入端口的處理 從 線 路 接 收 分 組 查表和轉(zhuǎn)發(fā) 輸出端口將交換結(jié)構(gòu)傳送來的分組發(fā)送到線路 ? 當(dāng)交換結(jié)構(gòu)傳送過來的分組先進行緩存 。數(shù)據(jù)鏈路層處理模塊將分組加上鏈路層的首部和尾部 ， 交給物理層后發(fā)送到外部線路 。 物理層處理 數(shù)據(jù)鏈路層 處理 網(wǎng)絡(luò)層處理 分組排隊 輸出端口的處理 向 線 路 發(fā) 送 分 組 緩存管理 交 換 結(jié) 構(gòu) 路由選擇的實現(xiàn) ? 分組投遞時，路由過程分兩個階段： 如何到達目標(biāo)主機的網(wǎng)絡(luò)。 分組到了目標(biāo)網(wǎng)絡(luò)后，由終端路由器將分組 送到目標(biāo)主機。 一般來說，第一個階段才是路由的實質(zhì)階段，它關(guān)系到分組穿越網(wǎng)間網(wǎng)的路徑。所以，在網(wǎng)絡(luò)上路由是以目標(biāo) IP地址中的網(wǎng)絡(luò)號為依據(jù)的。這樣可以只關(guān)心目標(biāo)網(wǎng)絡(luò)的信息，而不用關(guān)心目標(biāo)主機的信息，從而簡化路由表，提高路由效率。 路由表的信息 ? 典型地，路由表包含許多 (N,R) 向量，其中 N是目的網(wǎng)絡(luò)的 IP地址， R是為了到達相應(yīng)目的網(wǎng)絡(luò)要經(jīng)過的下一個路由器的 IP地址 (下一跳， next hop)。 ? 選路表的大小取決于互聯(lián)網(wǎng)中網(wǎng)絡(luò)的數(shù)量，它僅在添加新網(wǎng)絡(luò)時才增大。 網(wǎng) 1 網(wǎng) 4 網(wǎng) 3 網(wǎng) 2 目的主機所在的網(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ò)號來選擇路由會有幾個后果： 1. 在大多數(shù)實現(xiàn)方式中，這意味著所有到某個給定網(wǎng)絡(luò)的通信量都走同一條路徑。 2. 只有路徑上最后一個路由器才和目的主機通信，所以需要考慮一種方法，使該路由器可以向初始源站發(fā)回交付問題的報告。 3. A到 B和 B到 A的數(shù)據(jù)報的路徑可能不同。 因特網(wǎng)的路由選擇協(xié)議 有關(guān)路由選擇算法的幾個基本概念 ? 分層次的路由選擇協(xié)議 ? 內(nèi)部網(wǎng)關(guān)協(xié)議和外部網(wǎng)關(guān)協(xié)議 ? 距離向量算法，鏈路狀態(tài)算法 ? 路由信息協(xié)議 RIP (Routing Information Protocol) ? 開放最短路徑優(yōu)先 OSPF (Open Shortest Path First) ? 外部網(wǎng)關(guān)協(xié)議 EGP， BGP 路由選擇算法的幾個基本概念 理想的路由算法 ? 算法必須是正確的和完整的 。 ? 算法在計算上應(yīng)簡單 。 ? 算法應(yīng)能適應(yīng)通信量和網(wǎng)絡(luò)拓撲的變化 ，這就是說 ， 要有自適應(yīng)性 。 ? 算法應(yīng)具有穩(wěn)定性 。 ? 算法應(yīng)是公平的 。 ? 算法應(yīng)是最佳的 。 費用或代價 ? 在研究路由選擇時 ， 需要給每一條鏈路指明一定的 費用 或 代價 。 ? 這里 “ 代價 ” 并不一定是僅指 “ 錢 ” ， 而是由一個或幾個因素綜合決定的一種 度量(metric)， 如鏈路長度 、 數(shù)據(jù)率 、 鏈路容量 、是否要保密 、 傳播時延等 ， 甚至還可以是一天中某一個小時內(nèi)的通信量 、 結(jié)點的緩存被占用的程度 、 鏈路差錯率等 。 ? 不同的要求下 ， 各種因素的權(quán)值可能不同 。 最佳路由 ? 不存在一種絕對的最佳路由算法 。 ? 所謂 “ 最佳 ” 只能是相對于某一種特定要求下得出的較為合理的選擇而已 。 ? 實際的路由選擇算法 ， 應(yīng)盡可能接近于理想的算法 。 ? 路由選擇是個非常復(fù)雜的問題 ? 它是網(wǎng)絡(luò)中的所有結(jié)點共同協(xié)調(diào)工作的結(jié)果 。 ? 路由選擇的環(huán)境往往是不斷變化的 ， 而這種變化有時無法事先知道 。 最短路徑算法 ? 在路由選擇算法中都要用到求最短路徑算法 。 最出名的最短路徑算法有兩個： BellmanFord算法和 Dijkstra算法 。 ? 兩種算法思路不同 ， 但得出的結(jié)果是相同的 。 ? 若將鏈路長度改為鏈路時延或費用 ，就相當(dāng)于求任意兩節(jié)點之間具有最小時延或最小費用的路徑 。 最短路徑算法－ Dijkstra算法 ? Dijkstra算法是已知網(wǎng)絡(luò)的拓撲結(jié)構(gòu)和各鏈路的長度 ， 尋找從源節(jié)點到網(wǎng)絡(luò)中其他各節(jié)點的最短路徑 。 ? 設(shè)某個節(jié)點為源節(jié)點 ， 每次尋找一個節(jié)點到源節(jié)點的最短路徑 ， 直至找到所有的節(jié)點 。 ? 以網(wǎng)絡(luò)中的每一個節(jié)點作為源節(jié)點 ，分別使用最短路徑算法 ， 得出的結(jié)果就是全網(wǎng)的最短路徑 。 最短路徑算法－ Dijkstra算法 ? 令 D(v)為源節(jié)點到某個節(jié)點 v的距離 ，即從源節(jié)點沿著某一路徑到節(jié)點 v的所有鏈路的長度之和 ， 再令 L(i,j)為節(jié)點 i至節(jié)點 j的距離 。 1 4 5 6 3 2 5 2 1 1 1 2 2 3 3 5 最短路徑算法－ Dijkstra算法 設(shè)節(jié)點 1為源節(jié)點 ， 令 N為已尋找到最短路徑網(wǎng)絡(luò)節(jié)點集合 ， N＝ {1}。 對所有不在 N中的節(jié)點 ， 有： D(v)＝ L(i,j) ；若節(jié)點 v與節(jié)點 1直接相連 D(v)＝ ∞； 若節(jié)點 v與節(jié)點 1不直接相連 N中的節(jié)點 w， 其 D(w)值 最小 ， 把 w加入到 N中 ， 然后對所有不在 N中的節(jié)點 ， 用[ D(v)， D(w)＋ L(w,v)]中較小的值去更新原有的 D(v)值 ， 即 : D(v)← Min[ D(v)， D(w)＋ L(w,v)] 。 2， 直至所有網(wǎng)絡(luò)節(jié)點都在 N中為止 。 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 ∞ ∞