選路：自治系統(tǒng)內(nèi)選路

第十六章選路：自治系統(tǒng)內(nèi)選路RIPOSPFHELLO2023年10月12日第2頁1引言自治系統(tǒng)的選路：對外EGP：通告可達性信息；典型BGP內(nèi)部IGP：Rs間密切合作，以求獲得更好的路由。內(nèi)部網(wǎng)關(guān)協(xié)議IGP：InteriorGatewayProtocol；多種內(nèi)部路由協(xié)議的統(tǒng)稱；RIP、OSPF、…，；IGP只在AS內(nèi)使用。R4R1R2R3自治系統(tǒng)EGP內(nèi)部路由2023年10月12日第3頁2靜態(tài)路由vs動態(tài)路由靜態(tài)路由：小型網(wǎng)絡(luò)、人工簡單維護；路由及時性困難：出現(xiàn)故障等時，涉及到多個路由器中選路表的修改。路由的一致性困難：下一跳路由與完整的路由。動態(tài)路由：自動選路更新；保證路由的一致性和及時性。R4R1R2R3R52023年10月12日第4頁IGP：動態(tài)路由多種IGP動態(tài)路由：RIP、OSPF、…、。RIP：V-D路由算法；OSPF：OpenSPF，具有開放性的鏈路狀態(tài)路由算法。2023年10月12日第5頁3RIP選路信息協(xié)議RoutingInformationProtocol發(fā)展史：依靠物理網(wǎng)（局域網(wǎng)）廣播功能快速交換選路信息；Unix系統(tǒng)中：routed（routedaemon）進程；形成標(biāo)準(zhǔn)前已流行。標(biāo)準(zhǔn)：RIPv1：RFC1058(STD34,1988)，基本協(xié)議；RIPv2：RFC1723(1994)，增加CIDR支持。2023年10月12日第6頁RIP路由協(xié)議框架使用UDP傳輸RIP報文（520端口）。RIP實體操作IP實體的選路表。IPUDPRIP5202023年10月12日第7頁3.1RIP協(xié)議特點V－D選路算法；選路信息包括一系列（V，D）對，取自內(nèi)部的選路表；主動、被動方式－－路由器和主機都參加，主動：通告和接收選路信息（Router）；被動：只接收選路信息（Host），用于更新自己的選路表。Hopcountmetric，直接相連網(wǎng)絡(luò)距離為1，每經(jīng)過一個R，距離加1。2023年10月12日第8頁3.2RIP路由特點每個路由器關(guān)心：有幾個鄰接的路由器；通過鄰接路由器能到達那些目的網(wǎng)，距離如何。算法特點：路由表項：<目的網(wǎng)，下一節(jié)點，距離>，通告內(nèi)容：<目的網(wǎng)，距離>，更新表項：<目的網(wǎng)，發(fā)送報文的路由器，距離+1>，只依賴于鄰接路由器，逐跳擴散的路由信息。R4R1R2R3R5RRRRRRRRRN4N1N2N3N5<N1,R2,3><N2,R2,2><N3,---,1><N4,---,1><N5,R4,2><N1,R5,3><N2,R5,2><N3,---,1><N4,R3,2><N5,---,1>2023年10月12日第9頁3.3RIP操作路由器定期(30秒)在直連的網(wǎng)絡(luò)上廣播選路信息：網(wǎng)絡(luò)上各路由器廣播時間隨機分布；報文內(nèi)容為自己的選路表項；路由信息逐漸擴散到全網(wǎng)；定期30秒＋小隨機時延；IP的廣播或組播(255.255.255.255)。路由更新規(guī)則：沒有更小距離的路由時，保持原有路由不變。R4R1R2R3R52023年10月12日第10頁3.4RIP異常處理－路由器故障路由器故障：鄰接路由器受到直接影響（無信息通告）；對通過RIP獲得的路由表項，設(shè)置定時器；<Nx,Ry,Dz,T>，用Ry的<Nx,D>刷新T；超時未刷新（180秒，6個廣播周期），刪除該表項；預(yù)防RIP報文丟失的措施。R4R1R2R3R5N1N2R2出現(xiàn)故障：

R3將會在6個周期后，把到N1、N2的下一跳改變?yōu)镽5。2023年10月12日第11頁3.5RIP異常處理－路由環(huán)路RIP是只依據(jù)鄰接路由器的路由算法，沒有掌握網(wǎng)絡(luò)拓撲結(jié)構(gòu)，一旦網(wǎng)絡(luò)故障，容易出現(xiàn)路由不一致的問題。如圖：N6到N1有兩條路徑：出現(xiàn)如圖的故障后，路經(jīng)無法立即切換到另一條上；造成：R4R2的路由環(huán)路；等到R5把N1路由信息通告到R6和R4上時，環(huán)路可得到解決。R5R4R3R2R6R1N1N2N3N4N5N6如果N1到N6經(jīng)過更多的路由器呢？

---需要更長時間，環(huán)路才消失。如果沒有R3，R5的這條路呢？

---環(huán)路無法消失。2023年10月12日第12頁3.5RIP異常處理－－路由環(huán)路分割范圍更新（splithorizonupdate）：不回傳路由信息，即：對表項<Nx,Ry,Dz>，不通知路由器Ry；部分解決環(huán)路問題：R1需6個廣播周期，R2需12個周期、R3需18個周期；路由環(huán)會維持一段時間。R1R2R3N1N2N3<N1,R1,2><N1,R1,4><N1,R1,6><N1,1><N1,R2,3><N1,R2,5><N1,R2,3><N1,R2,5><N1,R2,7>R1R2R3N1N2N3<N1,R1,2>消失<N1,1>消失<N1,R2,3>消失2023年10月12日第13頁3.6RIP異常處理－－慢收斂新路由消息：每個周期傳播一跳，N個周期到達所有路由器。（假定網(wǎng)絡(luò)的直徑為N個路由器）。不可達信息：六個周期傳播一跳；還會被別的過時的路由消息干擾；6*N個周期難以到達所有路由器。R1R2N1N2N4<N1,--,1>故障<N1,R1,2><N1,R3,3>R4<N1,3>R3N3過時路由消息2023年10月12日第14頁3.6.1慢收斂－網(wǎng)絡(luò)大小和通告網(wǎng)絡(luò)大小限定：距離16代表∞(網(wǎng)絡(luò)中的最大跳數(shù)＝15)；用(Nx,16)通告到Nx的路由不可達；路由更新和通告：收到更短路由消息，立即更新選路表項（快）；路由表項超時成為不可達，并向其它R通告（慢）；利用不可達信息可推斷某些路由不可達，改善收斂。R1R2R3N1N2N3<N1,--,1>故障

<N1,∞><N1,R1,2><N1,R2,3><N1,R1,∞><N1,∞><N1,R2,∞>對N1的路由：R1先前告知的D＝1；R1現(xiàn)在告知的D＝∞；R2推斷N1不可達。本來30秒通告一次，現(xiàn)在暫停通告，等超時時直接通告無窮。2023年10月12日第15頁3.6.2慢收斂－更新抑制HoldDown：路由器收到某條路由不可達的消息后，在一段時間內(nèi)（典型60秒），忽略關(guān)于該網(wǎng)絡(luò)的任何路由信息；確保有較大范圍內(nèi)的站點都收到該壞消息，避免過時的路由通告，但抑制期間環(huán)路依然存在。R1R2N1N2N4<N1,--,1>故障

<N1,∞><N1,R1,2><N1,R3,3>R4<N1,3><R1,R4,4>如果不抑制，R2將會接受R4從N4送來的關(guān)于N1的路由，形成錯誤路由表項。R3N32023年10月12日第16頁3.6.3慢收斂－毒性逆轉(zhuǎn)PoisonReverse（毒性逆轉(zhuǎn)）：直接連接的路由消失后，在若干（至少一個）廣播周期內(nèi)都保留該路由（距離無限大），并向外通告；對分割更新的修正：回傳路由信息的距離為無限大；毒性逆轉(zhuǎn)能迅速打破較小的環(huán)路；如兩個路由器到目的網(wǎng)絡(luò)的路由都指向?qū)Ψ?。R1R2R3N1N2N3<N1,--,1><N1,R1,2><N1,R2,3><N1,∞>如果鏈路無故障，R1將忽略該路由；如果鏈路有故障，防止了R1從R2得到N1的路由信息（源于R1）。2023年10月12日第17頁3.6.4慢收斂－觸發(fā)更新觸發(fā)更新－對付較大路由環(huán)：快速的更新來加速收斂過程；一旦R改變了某條路由的度量，立即向鄰接路由器通告更新報文，不必等更新周期；觸發(fā)更新可能觸發(fā)廣播風(fēng)暴－－隨機延時后再通告。2023年10月12日第18頁RIP異常處理小結(jié)異常：路由環(huán)路；慢收斂。處理措施：分割更新－－避免路由環(huán)；抑制－－避免過時路由通告；毒性翻轉(zhuǎn)－－通告不可達路由；觸發(fā)更新－－快速通告新消息。2023年10月12日第19頁4RIP報文格式RIP只定義了有一種報文格式；交換（IPaddress，Metric）對；IPaddress可為A、B、C類網(wǎng)絡(luò)地址或主機地址。08162431CommandVersion＝1Mustbe0AddressFamilyIdentifierMustbe0IPAddressMustbe0Mustbe0MetricVersion1報文格式

可重復(fù)25次2023年10月12日第20頁4.1報文域Command：1=Request請求部分或全部選路信息；2=Response發(fā)送方給出自己選路表內(nèi)的(V，D)；9=更新請求；10=更新響應(yīng)；11=更新確認(rèn)。AddressFamilyIdentifier：2＝IPaddress；未定義掩碼，只能用于有類地址方式。2023年10月12日第21頁4.2V-D對V是IP地址格式（4字節(jié)），可為：網(wǎng)絡(luò)地址，A、B、C類地址；主機地址；存在子網(wǎng)時，網(wǎng)絡(luò)地址和主機地址存在二義性；如果無二義性解釋時，也可發(fā)送子網(wǎng)地址。V＝0.0.0.0表示缺省路由：可通告缺省路由；路由器能根據(jù)距離值供選擇缺省路由。2023年10月12日第22頁4.3RIPv2的擴展RIPv2格式：路由標(biāo)記：路由起點、自治域號等額外信息；RIP2實現(xiàn)對CIDR的擴展。08162431CommandVersion=2Mustbe0AddressFamilyIdentifier目的網(wǎng)的路由標(biāo)記目的網(wǎng)地址（IPAddr）目的網(wǎng)掩碼（Mask）到目的網(wǎng)的下一網(wǎng)關(guān)（NextHop）到目的網(wǎng)的距離（Metric）

可重復(fù)25次2023年10月12日第23頁4.4RIP的討論距離＝16指網(wǎng)絡(luò)的跨度，而不是路由器的數(shù)目；RIP適宜于廣播型、分層結(jié)構(gòu)的網(wǎng)絡(luò)；主干網(wǎng)、二級主干、…。簡單的路由，無法處理時延、容量要求；相對固定的路由，較長時間不變；無法對網(wǎng)絡(luò)性能變化（負載、時延等）做出反應(yīng)（調(diào)整路由）；仍有大量的應(yīng)用。2023年10月12日第24頁5Hello協(xié)議一個使用延時作距離度量的IGP協(xié)議；基本操作：使參與路由協(xié)議的機器在時鐘上同步；通過交換Hello報文估計與鄰接R的時延；用時延為距離度量計算路由和通告路由。主要問題－－協(xié)議非常不穩(wěn)定。時延測量的不穩(wěn)定－－平滑、門限；負載使得時延不穩(wěn)定－－時延變化敏感，容易形成正反饋；不同信道的不可比因素；大容量的衛(wèi)星信道，小容量的串行信道。2023年10月12日第25頁6OSPF－開放的SPF協(xié)議鏈路狀態(tài)選路算法。新成就：規(guī)范公開，免費使用；服務(wù)類型選路；負載均衡選路；易于網(wǎng)絡(luò)擴展和管理；支持多種鑒別機制；支持特定主機、子網(wǎng)、特點網(wǎng)絡(luò)的路由；虛擬網(wǎng)絡(luò)拓撲結(jié)構(gòu)，多點接入網(wǎng)的拓撲圖；包容和通告其它路由信息。顯然，需要對傳統(tǒng)選路算法和選路表動手術(shù)。2023年10月12日第26頁6.1OSPF報文類型共五種報文：Hello報文，用于測試鄰接路由器的可達性。數(shù)據(jù)庫描述報文，交換網(wǎng)絡(luò)拓撲數(shù)據(jù)庫。鏈路狀態(tài)請求，向鄰站請求特定鏈路狀態(tài)。鏈路狀態(tài)更新、確認(rèn)，通告鏈路狀態(tài)的變化信息。2023年10月12日第27頁6.2OSPF拓撲模型每個路由器都掌握網(wǎng)絡(luò)拓撲結(jié)構(gòu)：虛擬網(wǎng)絡(luò)拓撲結(jié)構(gòu)；節(jié)點（路由器）和鏈路（相鄰節(jié)點的信道）；多點訪問網(wǎng)絡(luò)（如廣播型網(wǎng)絡(luò)）會產(chǎn)生N2問題，使用指派路由器減少相鄰關(guān)系。R1R2R3R4R1R3R2R4R5R5多點訪問網(wǎng)絡(luò)（以太網(wǎng)）OPSF虛擬拓撲結(jié)構(gòu)產(chǎn)生N2問題用指派路由器減少相鄰關(guān)系R1R3R2R4R5R1R2R3R4R5ATM/FR/X.252023年10月12日第28頁6.3OSPF域模型多區(qū)域：每個區(qū)域是獨立的OSPF路由協(xié)議范圍，網(wǎng)絡(luò)拓撲數(shù)據(jù)庫只包含域內(nèi)部分；OSPF協(xié)議在域邊界處終止。某些路由器會屬于多個區(qū)域，稱為：區(qū)域邊界路由器；區(qū)域邊界路由器構(gòu)成另一個路由域（主干域）。形成分層路由結(jié)構(gòu)。OSPF域OSPF域OSPF域OSPF域OSPF域OSPF域自治系統(tǒng)RRRRRRRRRRRRRRRRRRRRRRRRR2級路由域內(nèi)路由1級路由（域間路由）2級路由域內(nèi)路由2級路由域內(nèi)路由3級路由3級路由RRR域內(nèi)路由器R域間路由器RAS邊界路由器分級路由結(jié)構(gòu)OSPF多區(qū)域模型2023年10月12日第29頁RRRRRRRRRRRRRRRRRRRRRRRRR6.4OSPF運行環(huán)境IP子網(wǎng)間的OSPF（物理網(wǎng)絡(luò)上的IP子網(wǎng)），相鄰路由器可通過物理網(wǎng)直接通信。IP網(wǎng)絡(luò)間的OSPF（多個IP子網(wǎng)構(gòu)成的IP網(wǎng)絡(luò)），相鄰路由器在物理上不相鄰（存在其它路由器）。IPNet5RIPNet2IPNet4IPNet3RRRIPNet1RRRRRRRRRRROSPF拓撲結(jié)構(gòu)2023年10月12日第30頁6.5OSPF子協(xié)議Hello協(xié)議，檢測鏈路是否可用；指派路由器的選舉。交換協(xié)議，交換拓撲數(shù)據(jù)庫內(nèi)容。擴散協(xié)議，通告鏈路狀態(tài)改變。2023年10月12日第31頁6.6OSPF報文和協(xié)議報文首部：Type，1=Hello,2=DatabaseRequest，3=LinkStatusrequest，4=LinkStatusupdate，5=LinkStatusresponse。08162431VersionTypeLengthSourceRouterIPAddressAreaIDChecksumAuthentypeAuthenticationData2023年10月12日第32頁6.6.1Hello協(xié)議定時與鄰站（路由器）聯(lián)系，并通告本路由器的有效鄰站情況；DeadTimer：鄰站失效的時限。08162431OSPFHeaderNetMaskDeadTimer（Sec）HelloIntervalGWayPrioDesignatedRouterBackDesignatedRouterNeighbor1IPAddressNeighbor2IPAddress……NeighbornIPAddressHello報文2023年10月12日第33頁6.6.2交換協(xié)議交換拓撲數(shù)據(jù)庫報文來初始化網(wǎng)絡(luò)拓撲數(shù)據(jù)庫，數(shù)據(jù)庫序號：發(fā)送報文的序號，用以檢查丟失等。請求特定鏈路狀態(tài)，更新自己的部分信息。08162431OSPFHeaderNetMaskMustbe0IMSDatabasesequencenumberLink1Description……LinknDescriptionLinkTypeL