选路：自治系统内选路

第十六章选路：自治系统内选路RIPOSPFHELLO2023年10月12日第2页1引言自治系统的选路：对外EGP：通告可达性信息；典型BGP内部IGP：Rs间密切合作，以求获得更好的路由。内部网关协议IGP：InteriorGatewayProtocol；多种内部路由协议的统称；RIP、OSPF、…，；IGP只在AS内使用。R4R1R2R3自治系统EGP内部路由2023年10月12日第3页2静态路由vs动态路由静态路由：小型网络、人工简单维护；路由及时性困难：出现故障等时，涉及到多个路由器中选路表的修改。路由的一致性困难：下一跳路由与完整的路由。动态路由：自动选路更新；保证路由的一致性和及时性。R4R1R2R3R52023年10月12日第4页IGP：动态路由多种IGP动态路由：RIP、OSPF、…、。RIP：V-D路由算法；OSPF：OpenSPF，具有开放性的链路状态路由算法。2023年10月12日第5页3RIP选路信息协议RoutingInformationProtocol发展史：依靠物理网（局域网）广播功能快速交换选路信息；Unix系统中：routed（routedaemon）进程；形成标准前已流行。标准：RIPv1：RFC1058(STD34,1988)，基本协议；RIPv2：RFC1723(1994)，增加CIDR支持。2023年10月12日第6页RIP路由协议框架使用UDP传输RIP报文（520端口）。RIP实体操作IP实体的选路表。IPUDPRIP5202023年10月12日第7页3.1RIP协议特点V－D选路算法；选路信息包括一系列（V，D）对，取自内部的选路表；主动、被动方式－－路由器和主机都参加，主动：通告和接收选路信息（Router）；被动：只接收选路信息（Host），用于更新自己的选路表。Hopcountmetric，直接相连网络距离为1，每经过一个R，距离加1。2023年10月12日第8页3.2RIP路由特点每个路由器关心：有几个邻接的路由器；通过邻接路由器能到达那些目的网，距离如何。算法特点：路由表项：<目的网，下一节点，距离>，通告内容：<目的网，距离>，更新表项：<目的网，发送报文的路由器，距离+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秒)在直连的网络上广播选路信息：网络上各路由器广播时间随机分布；报文内容为自己的选路表项；路由信息逐渐扩散到全网；定期30秒＋小随机时延；IP的广播或组播(255.255.255.255)。路由更新规则：没有更小距离的路由时，保持原有路由不变。R4R1R2R3R52023年10月12日第10页3.4RIP异常处理－路由器故障路由器故障：邻接路由器受到直接影响（无信息通告）；对通过RIP获得的路由表项，设置定时器；<Nx,Ry,Dz,T>，用Ry的<Nx,D>刷新T；超时未刷新（180秒，6个广播周期），删除该表项；预防RIP报文丢失的措施。R4R1R2R3R5N1N2R2出现故障：

R3将会在6个周期后，把到N1、N2的下一跳改变为R5。2023年10月12日第11页3.5RIP异常处理－路由环路RIP是只依据邻接路由器的路由算法，没有掌握网络拓扑结构，一旦网络故障，容易出现路由不一致的问题。如图：N6到N1有两条路径：出现如图的故障后，路经无法立即切换到另一条上；造成：R4R2的路由环路；等到R5把N1路由信息通告到R6和R4上时，环路可得到解决。R5R4R3R2R6R1N1N2N3N4N5N6如果N1到N6经过更多的路由器呢？

---需要更长时间，环路才消失。如果没有R3，R5的这条路呢？

---环路无法消失。2023年10月12日第12页3.5RIP异常处理－－路由环路分割范围更新（splithorizonupdate）：不回传路由信息，即：对表项<Nx,Ry,Dz>，不通知路由器Ry；部分解决环路问题：R1需6个广播周期，R2需12个周期、R3需18个周期；路由环会维持一段时间。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个周期到达所有路由器。（假定网络的直径为N个路由器）。不可达信息：六个周期传播一跳；还会被别的过时的路由消息干扰；6*N个周期难以到达所有路由器。R1R2N1N2N4<N1,--,1>故障<N1,R1,2><N1,R3,3>R4<N1,3>R3N3过时路由消息2023年10月12日第14页3.6.1慢收敛－网络大小和通告网络大小限定：距离16代表∞(网络中的最大跳数＝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现在告知的D＝∞；R2推断N1不可达。本来30秒通告一次，现在暂停通告，等超时时直接通告无穷。2023年10月12日第15页3.6.2慢收敛－更新抑制HoldDown：路由器收到某条路由不可达的消息后，在一段时间内（典型60秒），忽略关于该网络的任何路由信息；确保有较大范围内的站点都收到该坏消息，避免过时的路由通告，但抑制期间环路依然存在。R1R2N1N2N4<N1,--,1>故障

<N1,∞><N1,R1,2><N1,R3,3>R4<N1,3><R1,R4,4>如果不抑制，R2将会接受R4从N4送来的关于N1的路由，形成错误路由表项。R3N32023年10月12日第16页3.6.3慢收敛－毒性逆转PoisonReverse（毒性逆转）：直接连接的路由消失后，在若干（至少一个）广播周期内都保留该路由（距离无限大），并向外通告；对分割更新的修正：回传路由信息的距离为无限大；毒性逆转能迅速打破较小的环路；如两个路由器到目的网络的路由都指向对方。R1R2R3N1N2N3<N1,--,1><N1,R1,2><N1,R2,3><N1,∞>如果链路无故障，R1将忽略该路由；如果链路有故障，防止了R1从R2得到N1的路由信息（源于R1）。2023年10月12日第17页3.6.4慢收敛－触发更新触发更新－对付较大路由环：快速的更新来加速收敛过程；一旦R改变了某条路由的度量，立即向邻接路由器通告更新报文，不必等更新周期；触发更新可能触发广播风暴－－随机延时后再通告。2023年10月12日第18页RIP异常处理小结异常：路由环路；慢收敛。处理措施：分割更新－－避免路由环；抑制－－避免过时路由通告；毒性翻转－－通告不可达路由；触发更新－－快速通告新消息。2023年10月12日第19页4RIP报文格式RIP只定义了有一种报文格式；交换（IPaddress，Metric）对；IPaddress可为A、B、C类网络地址或主机地址。08162431CommandVersion＝1Mustbe0AddressFamilyIdentifierMustbe0IPAddressMustbe0Mustbe0MetricVersion1报文格式

可重复25次2023年10月12日第20页4.1报文域Command：1=Request请求部分或全部选路信息；2=Response发送方给出自己选路表内的(V，D)；9=更新请求；10=更新响应；11=更新确认。AddressFamilyIdentifier：2＝IPaddress；未定义掩码，只能用于有类地址方式。2023年10月12日第21页4.2V-D对V是IP地址格式（4字节），可为：网络地址，A、B、C类地址；主机地址；存在子网时，网络地址和主机地址存在二义性；如果无二义性解释时，也可发送子网地址。V＝0.0.0.0表示缺省路由：可通告缺省路由；路由器能根据距离值供选择缺省路由。2023年10月12日第22页4.3RIPv2的扩展RIPv2格式：路由标记：路由起点、自治域号等额外信息；RIP2实现对CIDR的扩展。08162431CommandVersion=2Mustbe0AddressFamilyIdentifier目的网的路由标记目的网地址（IPAddr）目的网掩码（Mask）到目的网的下一网关（NextHop）到目的网的距离（Metric）

可重复25次2023年10月12日第23页4.4RIP的讨论距离＝16指网络的跨度，而不是路由器的数目；RIP适宜于广播型、分层结构的网络；主干网、二级主干、…。简单的路由，无法处理时延、容量要求；相对固定的路由，较长时间不变；无法对网络性能变化（负载、时延等）做出反应（调整路由）；仍有大量的应用。2023年10月12日第24页5Hello协议一个使用延时作距离度量的IGP协议；基本操作：使参与路由协议的机器在时钟上同步；通过交换Hello报文估计与邻接R的时延；用时延为距离度量计算路由和通告路由。主要问题－－协议非常不稳定。时延测量的不稳定－－平滑、门限；负载使得时延不稳定－－时延变化敏感，容易形成正反馈；不同信道的不可比因素；大容量的卫星信道，小容量的串行信道。2023年10月12日第25页6OSPF－开放的SPF协议链路状态选路算法。新成就：规范公开，免费使用；服务类型选路；负载均衡选路；易于网络扩展和管理；支持多种鉴别机制；支持特定主机、子网、特点网络的路由；虚拟网络拓扑结构，多点接入网的拓扑图；包容和通告其它路由信息。显然，需要对传统选路算法和选路表动手术。2023年10月12日第26页6.1OSPF报文类型共五种报文：Hello报文，用于测试邻接路由器的可达性。数据库描述报文，交换网络拓扑数据库。链路状态请求，向邻站请求特定链路状态。链路状态更新、确认，通告链路状态的变化信息。2023年10月12日第27页6.2OSPF拓扑模型每个路由器都掌握网络拓扑结构：虚拟网络拓扑结构；节点（路由器）和链路（相邻节点的信道）；多点访问网络（如广播型网络）会产生N2问题，使用指派路由器减少相邻关系。R1R2R3R4R1R3R2R4R5R5多点访问网络（以太网）OPSF虚拟拓扑结构产生N2问题用指派路由器减少相邻关系R1R3R2R4R5R1R2R3R4R5ATM/FR/X.252023年10月12日第28页6.3OSPF域模型多区域：每个区域是独立的OSPF路由协议范围，网络拓扑数据库只包含域内部分；OSPF协议在域边界处终止。某些路由器会属于多个区域，称为：区域边界路由器；区域边界路由器构成另一个路由域（主干域）。形成分层路由结构。OSPF域OSPF域OSPF域OSPF域OSPF域OSPF域自治系统RRRRRRRRRRRRRRRRRRRRRRRRR2级路由域内路由1级路由（域间路由）2级路由域内路由2级路由域内路由3级路由3级路由RRR域内路由器R域间路由器RAS边界路由器分级路由结构OSPF多区域模型2023年10月12日第29页RRRRRRRRRRRRRRRRRRRRRRRRR6.4OSPF运行环境IP子网间的OSPF（物理网络上的IP子网），相邻路由器可通过物理网直接通信。IP网络间的OSPF（多个IP子网构成的IP网络），相邻路由器在物理上不相邻（存在其它路由器）。IPNet5RIPNet2IPNet4IPNet3RRRIPNet1RRRRRRRRRRROSPF拓扑结构2023年10月12日第30页6.5OSPF子协议Hello协议，检测链路是否可用；指派路由器的选举。交换协议，交换拓扑数据库内容。扩散协议，通告链路状态改变。2023年10月12日第31页6.6OSPF报文和协议报文首部：Type，1=Hello,2=DatabaseRequest，3=LinkStatusrequest，4=LinkStatusupdate，5=LinkStatusresponse。08162431VersionTypeLengthSourceRouterIPAddressAreaIDChecksumAuthentypeAuthenticationData2023年10月12日第32页6.6.1Hello协议定时与邻站（路由器）联系，并通告本路由器的有效邻站情况；DeadTimer：邻站失效的时限。08162431OSPFHeaderNetMaskDeadTimer（Sec）HelloIntervalGWayPrioDesignatedRouterBackDesignatedRouterNeighbor1IPAddressNeighbor2IPAddress……NeighbornIPAddressHello报文2023年10月12日第33页6.6.2交换协议交换拓扑数据库报文来初始化网络拓扑数据库，数据库序号：发送报文的序号，用以检查丢失等。请求特定链路状态，更新自己的部分信息。08162431OSPFHeaderNetMaskMustbe0IMSDatabasesequencenumberLink1Description……LinknDescriptionLinkTypeL