第10章路由协议

第十章路由协议Metric&Convergence自治系统和内、外部路由协议RIPOSPFBGP-4xudu@1引言表驱动IP选路一个路由器上可运行多种RoutedProtocols每个RoutedProtocol可以使用多种RoutingProtocols来获取路由信息设定的路径RouteTable内容：部分选路信息+默认路由Internet中的选路网络拓扑结构管理策略一致性及时性xudu@2路由表的构成过程初始化阶段——路由发现推导初始路由直连网络直连路由无法推导部分手工设置静态路由路由器间交换选路信息动态路由维护阶段——路由更新（网络拓扑改变时）手工、静态更新小型、变化缓慢的网络路由协议自动、动态更新大型、迅速变化的网络xudu@3静态路由vs.动态路由静态路由Staticroute管理员手工设置管理员手工更新不能保证路由的一致性和及时性管理性强没有路由开销小型、变化缓慢网络动态路由Dynamicroute路由协议自动发现路由协议自动更新保证路由的一致性和及时性管理性较弱产生一定的路由开销大型、迅速变化网络xudu@410.1Metric&Convergence选路准则——最短路径Metric（度量）：衡量路径的长短跳数（经过路由器的数目，hopcount）带宽（bandwidth）、延迟（delay）、负载（load）、开销（cost）…不同的Metric产生不同的“最短路径”不同的路由协议采用不同类型的Metric一个路由协议可同时应用多重MetricADCBNet64K64K10M10M10M跳数：ABNet带宽：ACDNetxudu@5Convergence（收敛）收敛采用特定路由协议的所有路由器对整个网络拓扑具有一致性的认识收敛时间从不一致到一致所经历的时间体现路由算法的效率xudu@610.2自治系统和内、外部路由协议自治系统（AutonomousSystem，AS）处于一个管理机构控制下的网络和路由器的集合AS使管理机构可自主选择其内部路由方式和对外通告部分可达性信息的权利每个AS赋予一个AS编号由负责分配Internet地址的中央管理机构统一分发取值：1~65535Internet由若干AS互相连接构成每个AS内可能有多个网络存在核心主干网也可以构成一个ASxudu@7AS类型Single-homedAS：只有一个出口如：AS2、AS3Multi-homedAS：有多个出口如：AS1NontransitAS，TransitASAS1RAS3AS2RRRxudu@8EGPvs.IGP外部网关协议ExteriorGatewayProtocol，EGP由AS边界路由器在AS间通告可达性信息目前常用协议：BGP-4内部网关协议InteriorGatewayProtocol，IGPAS内部路由器在AS内通告内部网络细节目前常用协议：RIP、OSPF、IS-ISAS1AS2RREGPIGPIGP功能层次：网络层xudu@9RIP&OSPFRIP内部网关协议距离向量路由算法（D-V）RIP，RIPv2OSPF内部网关协议链路状态路由算法（L-S）OSPFv2算法原理协议报文操作路由发现路由更新问题xudu@1010.3RIPRoutingInformationProtocol，RIPv1：RFC1058，v2：RFC2453，选路信息协议IPLANsMANsWANsICMPIGMPARPRARPNetworkLayerNetworkAccessLayerTCPUDPTransportLayerRIPApplicationLayer520协议软件层次xudu@11距离向量路由算法原理

（Distance–Vector）Bellman-FordAlgorithm发布路由信息EachrouterperiodicallypassesitswholeroutingtabletoneighborroutersWhat：thewholeroutingtableWhere：toitsneighborroutersWhen：atregularintervals计算路径Accumulatedistancevectorsxudu@12RIP报文格式CommandVersionIPaddressAll0sAll0sAll0sMetricAll0sFamily重复25次（）广播发送：55封装在UDP报文中：UDPport=520xudu@13RIP报文类型Request（Command=1）路由器刚接入网络，或某些路由表项超时请求所有路由表项（IPaddress=）请求部分路由表项（IPaddress=网络地址）Response（Command=2）询问响应：应答RIPRequest报文非询问响应：定期发送路由表中的所有路由信息xudu@14RFC1058section3.6RFC1058：直连路由的Metric=1（也可以大于1）现有实现：直连路由的Metric=0（如：Cisco路由器）RFC1058section3：Themetricisthesumofthecostsassociatedwiththenetworksthatwouldbetraversedingettingtothedestination.xudu@15RFC1058：接收时Metric+1现有实现：

发送时Metric+1xudu@16RIP路由发现过程ABCN1N2N3N4121212N3-10N4-20N1-10N2-20N2-10N3-20路由表：目的网络下一跳发送接口MetricN3N1N2B121A211B211C121N4A:(N1,1)(N2,1)B:(N2,1)(N3,1)C:

(N3,1)(N4,1)B:(N2,1)(N3,1)N4B122N1B212A:(N1,1)(N2,1)(N3,2)B:(N2,1)(N3,1)(N1,2)(N4,2)C:

(N3,1)(N4,1)(N2,2)B:(N2,1)(N3,1)(N1,2)(N4,2)A:(N1,1)(N2,1)(N3,2)(N4,3)B:(N2,1)(N3,1)(N1,2)(N4,2)C:(N3,1)(N4,1)(N2,2)(N1,2)B:(N2,1)(N3,1)(N1,2)(N4,2)xudu@17RIP路由更新过程ABCN1N2N3N4121212N3-10N4-20N1-10N2-2N2-1N3-20N3N1N2B121A211B211C121N4N4B122N1B212B:(N2,16)(N3,1)(N1,16)(N4,2)A:(N1,1)(N2,16)(N3,16)(N4,16)00∞∞∞C:(N3,1)(N4,1)(N2,16)(N1,16)∞∞∞∞xudu@18RIP路由更新算法IF（IPaddress不在路由表中）根据该报文添加新路由表项；ELSEIF（路由表对应表项的下一跳==通告路由器）根据该报文修改路由表中的对应表项；ELSEIF（Metric<路由表对应表项的跳数）根据该报文修改路由表中的对应表项；ELSE不修改路由表中的对应表项；xudu@19RIP中的定时器TimersGarbagecollection120secondsExpiration180secondsPeriodic30secondsP=30sE=180sP=30sE=180sE=180sG=120s30s180s删除路由120s为防止所有路由器同时更新引起的网络过载，定时器Periodic

值为25~30

秒间的一个随机数。xudu@20RIP的缓慢收敛

（SlowConvergence）Net1Net2Netn+10seconds15secondsn×15seconds问题路由环路（routingloops）无限计数（countingtoinfinity）xudu@21问题：路由环路&无限计数Net1Net2Net3Net1…………RoutingtableNet1A…………RoutingtableABYoucanreachnet1throughmewithlength2Bcanreachnet1!Great!Hopcountchanged!Limitingthenumberofhopsto15-1∞23Hopcountchanged!4∞∞-B1616xudu@22解决方法触发更新，Triggeredupdate水平分割，Splithorizons毒性逆转，Poisonreverse抑制定时器，Holddowntimer没有一种方法是100%有效的！xudu@23触发更新如果网络中没有变化定时（30s）发送所有路由信息如果网络中有变化立即发送更新后的所有路由信息为避免触发广播风暴，随机延时后再通告xudu@24水平分割Net1Net2Net3ABNet2 1Net3 2Net1 1RIPmessagesNet1 2Net2 1Net3 1RIPmessagesxudu@25毒性逆转Net1Net2Net3ABNet2 1Net3 2RIPmessagesNet1 16Net2 16Net3 16Net1 1RIPmessagesNet2 16Net3 1Net1 16Net2 1Net3 16Net1 2xudu@26抑制定时器路由器在收到关于某网络不可达信息后的一段固定时间内，忽略任何关于该网络的路由信息“好消息传得快，坏消息传得慢”——等待足够的时间，确保所有路由器都收到坏消息xudu@27RIPv2报文格式操作认证：Family=0xFFFF组播发送RIP报文：CommandVersionIPaddressSubnetMaskAll0sNextHopMetricRouteTagFamilyxudu@2810.4OSPFOpenShortestPathFirst，OSPFv2：RFC2328，开放最短路径优先IPLANsMANsWANsICMPIGMPARPRARPNetworkLayerNetworkAccessLayerTCPUDPTransportLayerOSPFApplicationLayer89协议软件层次xudu@29链路状态路由算法原理

（Link–State）DijkstraAlgorithm发布路由信息What:thelinkstateadvertisement（LSA）packetsWhere:toeveryrouterintheareaWhen:event-driven计算路径SPFalgorithmtoformaSPFtree洪泛法（flooding）xudu@30OSPF术语：区域Area包含在AS中的一些网络、主机和路由器的集合类型：标准区域、主干区域、残桩区域AutonomousSystemArea1Area2Area0(backbone)到其他ASAreatypesStandardBackboneStubxudu@31OSPF术语：OSPF路由器类型内部路由器（InternalRouter）主干路由器（BackboneRouter）区域边界路由器（ABR，AreaBorderRouter）AS边界路由器（ASBR，ASBorderRouter）AutonomousSystemArea1Area2Area0(backbone)到其他ASABR，BRIRASBR，BRIR，BRxudu@32OSPF术语：链路Link：与邻居路由器之间的网络点到点链路（Point-to-pointlink）点到点网络过渡链路（Linktotransitnetwork）多路访问网络残桩链路（Linktostubnetwork）残桩网络虚链路（Virtuallink）FrameRelayX.25Area0Area2Area1Area3xudu@33OSPF术语：DR和BDR定义DR：DesignatedRouter，指定路由器BDR：BackupDR，备份指定路由器作用：减少过渡链路上的路由开销例：过渡链路上有N个路由器无DR每个路由器有N-1个邻居，通告N-1条LS有DR非DR仅有1个邻居（即DR），仅通告1条LSDR有N-1个邻居（即非DR），通告N-1条LS总共N*（N-1）条LS总共2*（N-1）条LSxudu@34OSPFTables邻接表（AdjacencyTable）存放所有与之建立双向通信的邻居路由器信息链路状态数据库（Link-StateDB）存放本区域中的所有链路状态信息同区域内所有路由器的LSDB信息是相同的转发表（ForwardingTable）路由表，存放所有经SPF算法获得的最短路由xudu@35OSPF邻居状态Down：NotexchangeinformationwithanyneighborInit：WhenaninterfacereceivesitsfirstHello2-way：Whenitseesitselfinaneighbor’sHelloExStart：TwoneighborsuseHellotonegotiatewhoisthe“master”andwhoisthe“slave”Exchange：NeighborsuseDBDtosendeachotherasummaryoftheirlink-statedatabaseLoading：UsesLSR,LSU,andLSAcktogetcompletelink-stateinformationFull：Neighborsarefullyadjacentxudu@36OSPF分组格式VersionTypeRouterIDAreaIDPacketLengthAuthenticationAuthenticationAuthenticationTypeChecksum首部组播发送：，封装在IP分组中：IPProtocol=89OSPFPacketDataxudu@37OSPF分组类型1：HellopacketA64-bytepacketsentperiodicallytokeepalink“alive”2：DBD(DatabaseDescription)Summarycontentsofarouter’slink-statedatabasesenttoanewlydiscoveredneighbor3：LSR(Link-StateRequest)Requestsmorespecificinformationaboutalinkfromaneighbor’slink-statedatabase4：LSU(Link-StateUpdate，LSA)TransportsLSAstoneighborrouters,areplytoanLSR5：LSAck(Link-StateAcknowledgement)AckreceiptofaLSA;OSPF’sroutingupdatesareconnection-orientedxudu@38OSPF操作步骤1.EstablishrouteradjacenciesDonewiththeexchangeofHellos2.ElecttheDR/BDR(ifnecessary)Doneonmultiaccessnetworkonly3.DiscoverroutesDoneintheExStartandExchangestates4.SelectappropriateroutesDonethroughthecalculationofSPFalgorithm5.MaintainroutinginformationDonethroughtheregularexchangeofHellosxudu@39步骤1：建立邻接关系IamrouterIDandIseenooneDownState/24E0/24E1ABRouterB邻接表/24,intE1InitStateIamrouterID,andIseeRouterA邻接表/24,intE0Two-wayStateHello3954743907071339547439070713Hello3954743907071339547439070713xudu@40步骤3：路由发现HelloPacketABExstartExchangeLoadingFullHelloPacketDBDPacketDBDPacketLSAckPacketLSAckPacketLSRPacketLSUPacketLSAckPacketxudu@41OSPFLSA类型Type1：Router–LSA在本区域内发布所有邻居及其所在链路的信息Type2：Network–LSA由DR在本区域内发布其所在过渡网络上其他路由器信息Type3：Summary–LSA由ABR产生，在本AS内的所有区域中发布到达其他区域某网络的路径信息Type4：Summary–LSA由ABR产生，在本AS内的所有区域中发布到达ASBR的路径信息Type5：AS–external–LSA由ASBR产生，在本AS内的某些区域中发布到达AS以外网络的路径信息xudu@42OSPFLSAExampleArea1DRArea0Area2(Stub)AS10AS20Type2Type2Type2Type3(Area1)Type5(AS20)Type5(AS20)Type5(AS20)Type5(AS20)Type3(Area1)Type5(AS20)Type3(Area1)Type1(Area1)Type1(Area0)Type1(Area0)Type3(Area0)Type3(Area0)Type3(Area0)DefaultType5(AS20)Type5(AS20)Type1(Area1)Type1(Area1)xudu@43SPF算法BCF72224233HDEG261(2,A)(4,B)(8,B)(5,E)(6,E)(7,F)(9,H)节点Cost路径EBFCGDH2∞∞∞∞∞7A-BA-B-EA-G4A-B-C8A-B-E-F5A-B-E-G6A-B-E-F-C8A-B-E-F-H7A-B-E-G-H10A9A-B-E-F-H-DA-B-C-D11xudu@44RIPvs.OSPF对网络拓扑的了解路由计算方法路由更新方式路由更新内容收敛速度适用环境xudu@4510.5BGP-4BorderGatewayProtocol，BGPv4：RFC1771，RFC1772，边界网关协议IPLANsMANsWANsICMPIGMPARPRARPNetworkLayerNetworkAccessLayerTCPUDPTransportLayerBGP-4ApplicationLayer179协议软件层次xudu@46BGP特点外部网关协议AS间的可达信息策略路由AS管理策略可靠传输TCP传输路径向量路由选择PathVector增量更新Incremen