4 5因特網(wǎng)的路由選擇協(xié)議 1 理想的路由算法算法必須是正確的和完整的 算法在計(jì)算上應(yīng)簡(jiǎn)單 算法應(yīng)能適應(yīng)通信量和網(wǎng)絡(luò)拓?fù)涞淖兓?即要有自適應(yīng)性 算法應(yīng)具有穩(wěn)定性 算法應(yīng)是公平的 算法應(yīng)是最佳的 關(guān)于 最佳路由 不存在一種絕對(duì)的最佳路由算法 所謂 最佳 只能是相對(duì)于某一種特定要求下得出的較為合理的選擇而已 實(shí)際的路由選擇算法 應(yīng)盡可能接近于理想的算法 路由選擇是個(gè)非常復(fù)雜的問(wèn)題它是網(wǎng)絡(luò)中的所有結(jié)點(diǎn)共同協(xié)調(diào)工作的結(jié)果 路由選擇的環(huán)境往往是不斷變化的 而這種變化有時(shí)無(wú)法事先知道 從路由算法的自適應(yīng)性考慮 靜態(tài)路由選擇策略 即非自適應(yīng)路由選擇 其特點(diǎn)是簡(jiǎn)單和開(kāi)銷較小 但不能及時(shí)適應(yīng)網(wǎng)絡(luò)狀態(tài)的變化 動(dòng)態(tài)路由選擇策略 即自適應(yīng)路由選擇 其特點(diǎn)是能較好地適應(yīng)網(wǎng)絡(luò)狀態(tài)的變化 但實(shí)現(xiàn)起來(lái)較為復(fù)雜 開(kāi)銷也比較大 2 分層次的路由選擇協(xié)議 因特網(wǎng)采用分層次的路由選擇協(xié)議 因特網(wǎng)的規(guī)模非常大 如果讓所有的路由器知道所有的網(wǎng)絡(luò)應(yīng)怎樣到達(dá) 則這種路由表將非常大 處理起來(lái)也太花時(shí)間 而所有這些路由器之間交換路由信息所需的帶寬就會(huì)使因特網(wǎng)的通信鏈路飽和 許多單位不愿意外界了解自己?jiǎn)挝痪W(wǎng)絡(luò)的布局細(xì)節(jié)和本部門所采用的路由選擇協(xié)議 這屬于本部門內(nèi)部的事情 但同時(shí)還希望連接到因特網(wǎng)上 自治系統(tǒng) Autonomoussystem 一個(gè)自治系統(tǒng) 由同一機(jī)構(gòu)管理 使用統(tǒng)一選路策略的路由器的集合 自治系統(tǒng)內(nèi)部的路由選擇稱為域內(nèi)路由選擇 運(yùn)行內(nèi)部網(wǎng)關(guān)協(xié)議 IGP interiorGatewayProtocol 自治系統(tǒng)之間的路由選擇稱為域間路由選擇 運(yùn)行外部網(wǎng)關(guān)協(xié)議 EGP ExternalGatewayprotocol 將Internet劃分成多個(gè)相對(duì)獨(dú)立的系統(tǒng) 相對(duì)獨(dú)立的系統(tǒng)中各組織可以采用自己的規(guī)則和管理策略 每個(gè)相對(duì)獨(dú)立的系統(tǒng)稱為自治系統(tǒng) 每個(gè)自治系統(tǒng)由Internet注冊(cè)機(jī)構(gòu)分配一個(gè)唯一的數(shù)字編號(hào)來(lái)標(biāo)識(shí) 引入自治系統(tǒng) 的基本思想 通過(guò)不同的編號(hào)來(lái)區(qū)分不同的自治系統(tǒng)通過(guò)采用路由協(xié)議和自治系統(tǒng)編號(hào) 路由器就可以確定彼此間的路徑和路由信息的交換方法 因特網(wǎng)的路由選擇協(xié)議 內(nèi)部網(wǎng)關(guān)協(xié)議IGP 在一個(gè)自治系統(tǒng)內(nèi)部使用的路由選擇協(xié)議 如RIP RoutingInformationProtocal 和OSPF OpenShortestPathFirst 等 外部網(wǎng)關(guān)協(xié)議EGP 在自治系統(tǒng)之間使用的路由選擇協(xié)議 目前使用的協(xié)議就是BGP 自治系統(tǒng)和內(nèi)部網(wǎng)關(guān)協(xié)議 外部網(wǎng)關(guān)協(xié)議 用內(nèi)部網(wǎng)關(guān)協(xié)議 例如 RIP 自治系統(tǒng)B 自治系統(tǒng)A 用外部網(wǎng)關(guān)協(xié)議 例如 BGP 4 R1 R2 用內(nèi)部網(wǎng)關(guān)協(xié)議 例如 OSPF 自治系統(tǒng)之間的路由選擇也叫做域間路由選擇 Interdomainrouting 在自治系統(tǒng)內(nèi)部的路由選擇叫做域內(nèi)路由選擇 Intradomainrouting 動(dòng)態(tài)路由協(xié)議在協(xié)議棧中的位置 內(nèi)部網(wǎng)關(guān)協(xié)議RIP RoutingInformationProtocol 1 工作原理路由信息協(xié)議RIP是內(nèi)部網(wǎng)關(guān)協(xié)議 RIP是一種分布式的基于距離向量的路由選擇協(xié)議 RIP協(xié)議要求網(wǎng)絡(luò)中的每一個(gè)路由器都要維護(hù)從它自己到其他每一個(gè)目的網(wǎng)絡(luò)的距離記錄 距離 的定義 從一路由器到直接連接的網(wǎng)絡(luò)的距離定義為1 從一個(gè)路由器到非直接連接的網(wǎng)絡(luò)的距離定義為所經(jīng)過(guò)的路由器數(shù)加1 RIP協(xié)議中的 距離 也稱為 跳數(shù) hopcount 因?yàn)槊拷?jīng)過(guò)一個(gè)路由器 跳數(shù)就加1 距離 的定義 RIP認(rèn)為一個(gè)好的路由就是它通過(guò)的路由器的數(shù)目少 即 距離短 RIP允許一條路徑最多只能包含15個(gè)路由器 距離 的最大值為16時(shí)即相當(dāng)于不可達(dá) 可見(jiàn)RIP只適用于小型互聯(lián)網(wǎng) RIP不能在兩個(gè)網(wǎng)絡(luò)之間同時(shí)使用多條路由 RIP選擇一個(gè)具有最少路由器的路由 即最短路由 哪怕還存在另一條高速 低時(shí)延 但路由器較多的路由 RIP協(xié)議的三個(gè)要點(diǎn) 僅和相鄰路由器交換信息 交換的信息是當(dāng)前本路由器所知道的全部信息 即自己的路由表 按固定的時(shí)間間隔交換路由信息 例如 每隔30秒 RIP協(xié)議的工作過(guò)程 路由表的建立初始化的路由器的路由表中只有直連路由 距離是1 RIP啟動(dòng)和運(yùn)行過(guò)程路由器剛啟動(dòng)RIP時(shí) 以廣播形式向其相鄰路由器發(fā)送請(qǐng)求報(bào)文 相鄰路由器響應(yīng)該請(qǐng)求 并回送包含本地路由信息的相應(yīng)報(bào)文 路由器周期性地向外發(fā)送路由刷新報(bào)文 路由表信息不斷更新 路由刷新報(bào)文主要內(nèi)容是由若干 V D 組成的表 矢量V標(biāo)識(shí)該路由器可以到達(dá)的目的網(wǎng)絡(luò)或目的主機(jī) D表示該路由器到達(dá)目的網(wǎng)絡(luò)或目的主機(jī)的跳步數(shù) 距離 2 距離向量算法 收到相鄰路由器 其地址為X 的一個(gè)RIP報(bào)文 1 先修改此RIP報(bào)文中的所有項(xiàng)目 把 下一跳 字段中的地址都改為X 并把所有的 距離 字段的值加1 每個(gè)項(xiàng)目構(gòu)成 到目的網(wǎng)絡(luò)N 距離d 下一跳路由器是X 2 對(duì)修改后的RIP報(bào)文中的每一個(gè)項(xiàng)目 重復(fù)以下步驟 若原來(lái)的路由表中沒(méi)有目的網(wǎng)絡(luò)N 則把該項(xiàng)目加到路由表中 否則 即在路由表中有目的網(wǎng)絡(luò)N 這時(shí)查看下一跳路由器地址 若下一跳字段給出的路由器地址x是同樣的 則把收到的項(xiàng)目替換原路由表中的項(xiàng)目 否則 即有到目的的網(wǎng)絡(luò)N 但下一跳路由器不是X 若收到項(xiàng)目中的距離d小于路由表中的距離 則進(jìn)行更新 否則 什么也不做 3 若3分鐘還沒(méi)有收到相鄰路由器的更新路由表 則把此相鄰路由器記為不可達(dá)路由器 即將距離置為16 距離為16表示不可達(dá) 4 返回 例4 5已知路由器R6有表4 9 a 所示的路由表 現(xiàn)在收到路由器相鄰路由器R4發(fā)來(lái)的路由更新信息 如表4 9 b 所示 試更新路由器R6的路由表 表4 9 a 表4 9 b 例4 5已知路由器R6有表4 9 a 所示的路由表 現(xiàn)在收到路由器相鄰路由器R4發(fā)來(lái)的路由更新信息 如表4 9 b 所示 試更新路由器R6的路由表 表4 9 a 表4 9 b 例4 5已知路由器R6有表4 9 a 所示的路由表 現(xiàn)在收到路由器相鄰路由器R4發(fā)來(lái)的路由更新信息 如表4 9 b 所示 試更新路由器R6的路由表 表4 9 a 表4 9 b 例4 5已知路由器R6有表4 9 a 所示的路由表 現(xiàn)在收到路由器相鄰路由器R4發(fā)來(lái)的路由更新信息 如表4 9 b 所示 試更新路由器R6的路由表 表4 9 a 表4 9 b 例4 5已知路由器R6有表4 9 a 所示的路由表 現(xiàn)在收到路由器相鄰路由器R4發(fā)來(lái)的路由更新信息 如表4 9 b 所示 試更新路由器R6的路由表 表4 9 a 表4 9 b RIP路由表的初始化 NET1 NET2 Request Response R1 R2 距離矢量協(xié)議路由發(fā)現(xiàn) 路由更新 R1 R2 R1 R2 A B C 10 1 0 0 10 2 0 0 10 3 0 0 10 4 0 0 E0 S0 S0 S1 S0 E0 RoutingTable 10 2 0 0 10 3 0 0 0 0 RoutingTable 10 3 0 0 S0 0 10 4 0 0 E0 0 RoutingTable 10 1 0 0 10 2 0 0 0 0 路由表的形成過(guò)程 初使?fàn)顟B(tài) 路由表每行條目至少包含三個(gè)字段 目的網(wǎng)絡(luò) 跳數(shù) 下一跳路由器 A B C 10 1 0 0 10 2 0 0 10 3 0 0 10 4 0 0 E0 S0 S0 S1 S0 E0 RoutingTable 10 1 0 0 10 2 0 0 10 3 0 0 RoutingTable 10 2 0 0 10 3 0 0 10 4 0 0 10 1 0 0 0 0 1 1 RoutingTable 10 3 0 0 S0 0 10 4 0 0 E0 0 10 2 0 0 1 1 0 0 路由表的形成過(guò)程 首次交換后 路由表的形成過(guò)程 收斂狀態(tài) A B C 10 1 0 0 10 2 0 0 10 3 0 0 10 4 0 0 E0 S0 S0 S1 S0 E0 RoutingTable 10 1 0 0 10 2 0 0 10 3 0 0 10 4 0 0 RoutingTable 10 2 0 0 10 3 0 0 10 4 0 0 10 1 0 0 0 0 1 1 RoutingTable 10 3 0 0 S0 0 10 4 0 0 E0 0 10 2 0 0 S0 10 1 0 0 1 2 1 2 0 0 4字節(jié) RIP報(bào)文 3 RIP2協(xié)議的報(bào)文格式 路由信息 20字節(jié) 路由 可重復(fù)出現(xiàn)最多25個(gè) IP數(shù)據(jù)報(bào) 路由標(biāo)記 網(wǎng)絡(luò)地址 地址族標(biāo)識(shí)符 距離 1 16 IP首部 UDP首部 首部 路由部分 必為0 版本 命令 4字節(jié) 子網(wǎng)掩碼 下一跳路由器地址 UDP用戶數(shù)據(jù)報(bào) RIP協(xié)議的優(yōu)缺點(diǎn) RIP存在的一個(gè)問(wèn)題是當(dāng)網(wǎng)絡(luò)出現(xiàn)故障時(shí) 要經(jīng)過(guò)比較長(zhǎng)的時(shí)間才能將此信息傳送到所有的路由器 RIP協(xié)議最大的優(yōu)點(diǎn)就是實(shí)現(xiàn)簡(jiǎn)單 開(kāi)銷較小 RIP限制了網(wǎng)絡(luò)的規(guī)模 它能使用的最大距離為15 16表示不可達(dá) 路由器之間交換的路由信息是路由器中的完整路由表 因而隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大 開(kāi)銷也就增加 并且會(huì)產(chǎn)生路由環(huán)路 R2 R1 正常情況 11 12R1 R1說(shuō) 我到網(wǎng)1的距離是1 是直接交付 1 表示 從本路由器到網(wǎng)1 1 表示 距離是1 表示 直接交付 R2 R1 正常情況 11 12R1 R2說(shuō) 我到網(wǎng)1的距離是2 是經(jīng)過(guò)R1 1 表示 從本路由器到網(wǎng)1 2 表示 距離是2 R1 表示經(jīng)過(guò)R1 R2 R1 正常情況 11 12R1 R1說(shuō) 我到網(wǎng)1的距離是16 表示無(wú)法到達(dá) 是直接交付 但R2在收到R1的更新報(bào)文之前 還發(fā)送原來(lái)的報(bào)文 因?yàn)檫@時(shí)R2并不知道R1出了故障 R2 R1 正常情況 11 12R1 R1收到R2的更新報(bào)文后 誤認(rèn)為可經(jīng)過(guò)R2到達(dá)網(wǎng)1 于是更新自己的路由表 說(shuō) 我到網(wǎng)1的距離是3 下一跳經(jīng)過(guò)R2 然后將此更新信息發(fā)送給R2 R2 R1 正常情況 11 12R1 R2以后又更新自己的路由表為 1 4 R1 表明 我到網(wǎng)1距離是4 下一跳經(jīng)過(guò)R1 R2 R1 R2 R1 網(wǎng)1出了故障 正常情況 11 116 15R2 12R1 12R1 這樣不斷更新下去 直到R1和R2到網(wǎng)1的距離都增大到16時(shí) R1和R2才知道網(wǎng)1是不可達(dá)的 這就是好消息傳播得快 而壞消息傳播得慢 網(wǎng)絡(luò)出故障的傳播時(shí)間往往需要較長(zhǎng)的時(shí)間 例如數(shù)分鐘 這是RIP的一個(gè)主要缺點(diǎn) RIP配置 配置RIP時(shí) 必須先啟動(dòng)RIP 才能配置其它特性 而配置與接口相關(guān)的特性不受RIP是否使能的限制 需要注意的是 在關(guān)閉RIP后 與RIP相關(guān)的接口參數(shù)也同時(shí)失效 啟動(dòng)RIP協(xié)議后 路由器具有RIP功能 即可配置與本路由器關(guān)聯(lián)的網(wǎng)絡(luò)了 Router config routerripRouter config norouterrip RIP協(xié)議配置命令 將路由器所在的相應(yīng)網(wǎng)段配置成RIP網(wǎng)絡(luò) 使這些接口可收發(fā)RIP報(bào)文 該地址為直接相連的網(wǎng)絡(luò) 配置命令如下 在指定的網(wǎng)絡(luò)上使能RIPRouter config router networknetwork addressRouter config router nonetworknetwork address 4 5 3內(nèi)部網(wǎng)關(guān)協(xié)議OSPF OpenShortestPathFirst OSPF協(xié)議的基本特點(diǎn) 開(kāi)放最短路徑優(yōu)先是內(nèi)部網(wǎng)關(guān)協(xié)議 IGP 的一種 核心 使用分布式的鏈路狀態(tài)協(xié)議和Dijkstra 迪杰斯特拉 的最短路徑算法SPF 三個(gè)要點(diǎn) 向本自治系統(tǒng)中所有路由器發(fā)送信息 使用的方法是洪泛法 發(fā)送的信息就是與本路由器相鄰的所有路由器的鏈路狀態(tài) 但這只是路由器所知道的部分信息 鏈路狀態(tài) 就是說(shuō)明本路由器都和哪些路由器相鄰 以及該鏈路的 度量 metric 只有當(dāng)鏈路狀態(tài)發(fā)生變化時(shí) 路由器才用洪泛法向所有路由器發(fā)送此信息 鏈路狀態(tài)數(shù)據(jù)庫(kù) link statedatabase 通過(guò)鏈路狀態(tài)協(xié)議 各路由器之間頻繁地交換鏈路狀態(tài)信息 因此所有的路由器最終都能建立一個(gè)鏈路狀態(tài)數(shù)據(jù)庫(kù) 這個(gè)數(shù)據(jù)庫(kù)實(shí)際上就是全網(wǎng)的拓?fù)浣Y(jié)構(gòu)圖 它在全網(wǎng)范圍內(nèi)是一致的 這稱為鏈路狀態(tài)數(shù)據(jù)庫(kù)的同步 每個(gè)路由器應(yīng)用Dijkstra 迪杰斯特拉 算法從該拓?fù)浣Y(jié)構(gòu)圖生成最短路徑樹(shù) 確定自己的路由表 OSPF的鏈路狀態(tài)數(shù)據(jù)庫(kù)能較快地進(jìn)行更新 使各個(gè)路由器能及時(shí)更新其路由表 OSPF的更新過(guò)程收斂得快是其重要優(yōu)點(diǎn) OSPF通過(guò)LSA描述網(wǎng)絡(luò)拓?fù)?節(jié)點(diǎn) 路由器 網(wǎng)絡(luò)邊 連接路由器的點(diǎn)點(diǎn)鏈路 鏈路狀態(tài)路由協(xié)議算法 一 網(wǎng)絡(luò)的拓樸結(jié)構(gòu) 四 每臺(tái)路由器分別以自己為根節(jié)點(diǎn)計(jì)算最小生成樹(shù) 三 由鏈路狀態(tài)數(shù)據(jù)庫(kù)得到的帶權(quán)有向圖 C A B D 1 2 3 5 RTC RTD 3 2 1 5 RTB RTA OSPF的區(qū)域 area 為了使OSPF能夠用于規(guī)模很大的網(wǎng)絡(luò) OSPF將一個(gè)自治系統(tǒng)再劃分為若干個(gè)更小的范圍 叫作區(qū)域 每一個(gè)區(qū)域都有一個(gè)32位的區(qū)域標(biāo)識(shí)符 用點(diǎn)分十進(jìn)制表示 區(qū)域也不能太大 在一個(gè)區(qū)域內(nèi)的路由器最好不超過(guò)200個(gè) OSPF使用層次結(jié)構(gòu)劃分為兩種不同的區(qū)域 區(qū)域0 0 0 1 區(qū)域0 0 0 3 主干區(qū)域0 0 0 0 至其他自治系統(tǒng) R9 R7 R6 R5 R4 R3 R2 R1 網(wǎng)8 網(wǎng)6 網(wǎng)3 網(wǎng)2 網(wǎng)1 網(wǎng)7 區(qū)域0 0 0 2 網(wǎng)4 網(wǎng)5 R8 主干區(qū)域 0 0 0 0 用來(lái)連通其它下層區(qū)域 劃分區(qū)域 劃分區(qū)域的好處就是將利用洪泛法交換鏈路狀態(tài)信息的范圍局限于每一個(gè)區(qū)域而不是整個(gè)的自治系統(tǒng) 這就減少了整個(gè)網(wǎng)絡(luò)上的通信量 在一個(gè)區(qū)域內(nèi)部的路由器只知道本區(qū)域的完整網(wǎng)絡(luò)拓?fù)?而不知道其他區(qū)域的網(wǎng)絡(luò)拓?fù)涞那闆r OSPF使用層次結(jié)構(gòu)的區(qū)域劃分 在上層的區(qū)域叫作主干區(qū)域 backbonearea 主干區(qū)域的標(biāo)識(shí)符規(guī)定為0 0 0 0 主干區(qū)域的作用是用來(lái)連通其他在下層的區(qū)域 主干路由器 主干區(qū)域內(nèi)的路由器 區(qū)域0 0 0 1 區(qū)域0 0 0 3 主干區(qū)域0 0 0 0 至其他自治系統(tǒng) R9 R7 R6 R5 R4 R3 R2 R1 網(wǎng)8 網(wǎng)6 網(wǎng)3 網(wǎng)2 網(wǎng)1 網(wǎng)7 區(qū)域0 0 0 2 網(wǎng)4 網(wǎng)5 R8 自治系統(tǒng)邊界路由器R6 區(qū)域邊界路由器 區(qū)域0 0 0 1 區(qū)域0 0 0 3 主干區(qū)域0 0 0 0 至其他自治系統(tǒng) R9 R7 R6 R5 R4 R3 R2 R1 網(wǎng)8 網(wǎng)6 網(wǎng)3 網(wǎng)2 網(wǎng)1 網(wǎng)7 區(qū)域0 0 0 2 網(wǎng)4 網(wǎng)5 R8 IP數(shù)據(jù)報(bào) OSPF分組 IP數(shù)據(jù)報(bào)首部 OSPF分組 OSPF分組首部 類型1至類型5的OSPF分組 24字節(jié) 0 8 16 31 版本 路由器標(biāo)識(shí)符 類型 分組長(zhǎng)度 檢驗(yàn)和 鑒別 位 鑒別 區(qū)域標(biāo)識(shí)符 鑒別類型 OSPF直接用IP數(shù)據(jù)報(bào)傳送 2 OSPF的五種分組類型 類型1 問(wèn)候 Hello 分組 用于發(fā)現(xiàn)和維護(hù)鄰站的可達(dá)性類型2 數(shù)據(jù)庫(kù)描述 DatabaseDescription 分組 類型3 鏈路狀態(tài)請(qǐng)求 LinkStateRequest 分組 類型4 鏈路狀態(tài)更新 LinkStateUpdate 分組 用洪泛法對(duì)全網(wǎng)更新鏈路狀態(tài) 類型5 鏈路狀態(tài)確認(rèn) LinkStateAcknowledgment 分組 OSPF的基本操作 確定可達(dá)性 OSPF使用的是可靠的洪泛法 更新報(bào)文 ACK報(bào)文 R R R R t1t2t3t4 在網(wǎng)絡(luò)運(yùn)行過(guò)程中 只要有一個(gè)路由器的鏈路狀態(tài)發(fā)生變化 該路由器就要使用鏈路狀態(tài)更新分組 用洪泛法對(duì)全網(wǎng)更新鏈路狀態(tài) OSPF配置 啟動(dòng)OSPF協(xié)議 進(jìn)入OSPF協(xié)議配置視圖Router config routerospf1Router config norouterospf1 發(fā)布OSPF的網(wǎng)絡(luò)號(hào)和指定端口所在區(qū)域號(hào) Router config router networkaddresswildcardarea idRouter config router nonetworkaddresswildcardarea idaddresswildcard 運(yùn)行OSPF端口所在網(wǎng)段地址 子網(wǎng)掩碼的反碼area id OSPF路由器接口所在的區(qū)域號(hào) 邊界網(wǎng)關(guān)協(xié)議BGP 自治系統(tǒng)之間的動(dòng)態(tài)路由協(xié)議 BGP功能 在不同AS的路由器之間交換信息的協(xié)議 采用路徑向量路由選擇協(xié)議 從設(shè)計(jì)上避免了路由環(huán)路的發(fā)生支持CIDR 無(wú)類別域間路由 傳送協(xié)議 TCP BGP發(fā)言人 每一個(gè)自治系統(tǒng)的管理員要選擇至少一個(gè)路由器作為該自治系統(tǒng)的 BGP發(fā)言人 BGP發(fā)言人往往就是BGP邊界路由器 一個(gè)BGP發(fā)言人與其他自治系統(tǒng)中的BGP發(fā)言人要交換路由信息 就要先建立TCP連接 端口號(hào)179 然后在此連接上交換BGP報(bào)文以建立BGP會(huì)話 利