TCPIP协议原理英文版课件：Chapter 11 Routing Protocol

2022/10/29TCP/IPProtocolSuite1Chapter11RoutingProtocolsInterior(内部)andexterior(外部)routingRIPOSPFBGP-42022/10/29TCP/IPProtocolSuite2Introduction互联网由许多路由器连接起来的网络组成数据从源站点到目的站点，可能经过多个路由器一个路由器连接多个网络，当路由器收到分组，应该将分组转发到哪个网络？2022/10/29TCP/IPProtocolSuite3Introduction路由选择协议(Routingprotocol)——使得路由器能够找到到达目的地的最佳路径TosharetheknowledgeabouttheinternetTocalculatetheroutingtablebasedonthetopologyorthepolicies（策略）RoutingTableStaticroutemanuallydefineDynamicrouteroutingprotocolTable-drivenrouting（表驱动路由选择）OnerouterMoreroutedprotocolsOneroutedprotocol（例如IP）OneroutingtableOneroutedprotocolMoreroutingprotocolsConvergenceOverheadScalability2022/10/29TCP/IPProtocolSuite4Metric（度量）Metric：用来衡量通过某一网络所需的代价代价是什么？代价的度量取决于RoutingProtocolHopcount（跳数）,bandwidth（带宽）,delay（延迟）,MTU,load（负载）,reliability（可靠性）,…Routingprotocol使用Metric来选择一条bestpath（最优路）forroutingThemetricofaroute=MIN{SUM(Metricn)}Themetricofaroute＝MAX{MIN(Metricn)}64K64K10M10M10MHopcount:ABNetBandwidth:ACDNetADCBNetn∈Pathn∈Path度量取决于所需要的服务类型2022/10/29TCP/IPProtocolSuite5Convergence（收敛）ConvergenceAllroutersinanetworkagreeonthetopologyConvergencetime（收敛时间）Ameasureofhowquicklytorecoverfromnetworkchanges从不一致到一致所经历的时间体现路由算法的效率ABCDest.D2022/10/29TCP/IPProtocolSuite6Convergence（收敛）FactorsaffectingconvergenceTheroutingprotocolusedArouter’sdistancefromthepointofchangeThenumberofroutersinthenetworkBandwidthandtrafficloadoncommunicationslinksArouter’sloadTrafficpatternsinrelationtothetopologychange2022/10/29TCP/IPProtocolSuite7AutonomoussystemAutonomoussystem（自治系统，AS）AgroupofnetworksandroutersundertheauthorityofasingleadministrationEachAStypicallyrepresentsanindependentorganizationandappliesitsownuniqueroutingandsecuritypolicies域内路由和域间路由为什么需要AS？主要原因：Internet网络太大，一种路由协议无法更新所有路由器的路由表引入AS之后，路由分为intra-domainroutinginter-domainrouting2022/10/29TCP/IPProtocolSuite8AutonomoussystemASnumberAnidentifyingnumberthatisassignedbyanInternetregistryoraserviceprovideRange:1~65535（PrivateASnumber:64512~65535）Internet由若干AS互相连接构成每个AS内可能有多个网络存在核心主干网也可以构成一个AS核心主干网提供到所有可能的目的地的

可靠的、统一的、权威的路由ASxASyAS1核心主干网AS3AS22022/10/29TCP/IPProtocolSuite9TypesofAutonomousSystemsSingle-homedAS（残桩AS）OnlyoneexitpointtotheoutsideExample:AS1,AS3数据通信量不能通过残桩ASMulti-homedASMorethanoneexitpointtotheoutsideExample:AS2NontransitAS——例如：大型公司网络notallowtransittraffictopassthroughitTransitAS（转接AS）allowtransittraffictopassthroughitAS1AS2RRRAS3R2022/10/29TCP/IPProtocolSuite10IGPvs.EGPIGP:InteriorGatewayProtocol（内部网关协议/域内路由）TobeusedwithinanautonomoussystemTofindthebestpathtothenetworkIGP具有多样性，AS可自主选择Example：RIP、OSPF、IS-ISEGP:ExteriorGatewayProtocol（外部网关协议/域间路由）TobeusedbetweenautonomoussystemsTofindthebestpathtotheASAS间必须使用统一的EGPExample：BGP-4NoteThestaticroutingoranIGPcouldalsobeusedbetweenautonomoussystemsinsomecaseAS1AS2RREGPIGPIGP2022/10/29TCP/IPProtocolSuite11RoutingProtocolsRoutingprotocolsConceptoftheroutingmethodOperation:discover,topologychange,calculateFeaturesandmessagesQuestionsandsolutionsProtocolTypeRoutingmethodPopularver.RIP(路由信息协议)IGPDistancevectorroutingRIPv1,RIPv2OSPF(开放最短通路优先)IGPLinkstateroutingOSPFv2BGP(边界网关协议)EGPPathvectorroutingBGP42022/10/29TCP/IPProtocolSuite12Chapter11RoutingProtocolsInteriorandexteriorroutingRIPOSPFBGP-42022/10/29TCP/IPProtocolSuite13RIPRoutingInformationProtocol，RIPv1：RFC1058，v2：RFC2453，路由信息协议IPLANsMANsWANsICMPIGMPARPRARPNetworkLayerNetworkAccessLayerTCPUDPTransportLayerRIPApplicationLayer520软件实现层次RIP=RIPv12022/10/29TCP/IPProtocolSuite14什么是DV？一个有序对（v，d）v：目的网络d：到该目的网络的距离准确说：应该是到目的网络的Metric从哪获得DV？邻居节点周期性的路由通告报文中怎么理解DV？假设路由器j从邻居i获得DV＝（v，div），表示邻居i告诉路由器j

：“我可以到达某个目的网络v，我到那儿的距离是div”那么，对于路由器j就可以推出以下结论：“我通过邻居i，可以到达v，且距离是div＋dji”距离向量（DistanceVector，DV）jivdjidivv,divDNext_hopMvidiv＋djiBellman-FordAlgorithmGiventhecostbetweeneachpairofnodes,thealgorithmcanfindtheleastcost(shortestpath)betweenanytwonodes2022/10/29TCP/IPProtocolSuite152022/10/29TCP/IPProtocolSuite16DistanceVector（距离向量）Routing基本原理：每一个路由器周期性地与其邻居路由器分享关于整个网络的路由信息“我可以通过谁到达哪些网络”“分享”What theentireroutingtableWhen atregularintervalsWhere onlywithneighborTocalculatetheroutingtable距离向量算法（Bellman-Ford

或Ford-Fulkerson算法）通过累积distancevectors，

来不断更新路由表2134561121111113465321333112244446552022/10/29TCP/IPProtocolSuite17RIPMessageFormat(<=512bytes)Encapsulation:UDP(port520)采用广播的方式通告路由CommandVersionIPaddressAll0sAll0sAll0sMetric(hopcount)All0sFamilyRepeated2022/10/29TCP/IPProtocolSuite18TypesofMessagesRequest(Command=1):broadcast功能：askforaresponsecontainingallorpartoftherouter‘sroutingtable.（“问路”）AllentriesTobesentbyarouterthathasjustcomeup（当路由器刚接入网络）SpecificentriesTobesentbyarouterthathassometime-outentries（询问超时表项）Response(Command=2)Solicited（询问响应）：响应Request分组UnicasttotheaskerTobesentonlyinanswertoarequestUnsolicited（非询问响应）：regularupdates（周期更新）BroadcasttoeveryneighborTobesentevery30s,containtheentireroutingtable2022/10/29TCP/IPProtocolSuite19ExampleofRIPMessage2022/10/29TCP/IPProtocolSuite20RIPOperationDiscoveryTopologychangeCalculatingRIPupdatingalgorithmInitializetheRTSendtheRTUpdatetheRT收敛?SendtheRTper30sNoYesFindthechangeUpdatetheRTSendtheRTonscheduleLikediscoverySplithorizons&poisonreverseTriggeredupdate阶段1阶段22022/10/29TCP/IPProtocolSuite21InitializingtheRoutingTable初始阶段，路由器的路由表中只有直连网络的路由RFC1058:metric=1Inmostrouters:metric=0Examplesofsomerouter’sroutingtableCiscorouterCisdirectlyconnected,FastEthernet0/0华为routerDst/MaskProtoPrefMetricNexthopInterface/24Direct0

054Ethernet0…………RFC1058:section3.62022/10/29TCP/IPProtocolSuite22Example：InitialroutingtablesinasmallautonomoussystemDst.MetricNexthop2022/10/29TCP/IPProtocolSuite23SendingRIPResponses(RFC1058Section3.5)什么时候会“SendingRIPResponses”？收到了一个RIPRequest对RIP请求作响应bytheregularroutingupdate广播路由表bytriggeredupdates当路由表项的Metric值发生变化时SourceIPaddressTheIPaddressofthesendinginterfaceConsider:multipleIPaddressesonasinglephysicalinterface（RFC1058P29）IneachentryAddress:hostaddr,subnetaddr,networkaddr,Metric:fromtheroutingtablewithoutchange2022/10/29TCP/IPProtocolSuite24RFC1058:

UpdatingtheRoutingTableWhenreceivearesponseRIPmessageFirsttocheckforvalidity（有效性）Portnumber,sourceIPaddressThentoprocesstheentriesinRIPmessageonebyoneIgnoretheentrywhosemetric,addressorunusedfieldsareinvalidUpdatetheentry’smetric=min(metric+1,16)IftheentryaddressisnotintheRT,thenadditElseifthenext-hopintheRTissamewithsourceIPaddress,thenreplacetherouteintheRTwiththisentryElseifthenewmetricislowerthantheoneintheRT,thenreplacetherouteintheRTwiththisentry2022/10/29TCP/IPProtocolSuite251+1UpdatingtheRoutingTableABDNET1NET6CNET3NET4NET5NET2ERA路由表RIPMessagefromRBDst.MetricNET11NET31NET43NET52NET62Dst.MetricNET11NET42NET53NET64Nexthop-RERERENET21-RIPMessagefromRB

afterincrementDst.MetricNET12NET3NET4NET5NET62433NET32RB3RBRA’sRIPMessageDst.MetricNET11NET32NET42NET53NET65NET212022/10/29TCP/IPProtocolSuite26NetworkDiscoveryABCN1N2N3N4121212N3-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)2022/10/29TCP/IPProtocolSuite27TopologyChangeABCN1N2N3N4121212N3-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)∞∞∞∞2022/10/29TCP/IPProtocolSuite28TimersinRIPTimersGarbagecollection120s(foreachroute)Expiration180s(foreachroute)Periodic30s(foreachrouter)收到更新E=180s收到更新E=180sMetric16G=120s30s180s删除路由120s实现中：

P＝25～30sG＝60s控制报文的发送，为防止所有路由器同时更新引起的网络过载，P

值为25~35秒间的一个随机数。管理路由有效性。每收到某条路由的更新，E定时器就要复位；若超时，路由跳数设为16P=30s，发送更新P=30s，发送更新保证邻居路由器能够获知无效路由。无效的路由表项在GTimer内，继续被路由器定期通告，其Metric＝162022/10/29TCP/IPProtocolSuite29ProblemswithRIPCounttoInfinity——Slowconvergence（缓慢收敛）Theproblem:anydecreaseincost(goodnews)propagatesquickly,butanyincreaseincost(badnews)propagatesslowly.RIPneedstotakessometimetomakeeveryotherrouterbeawareofabrokenlink原因：路由器的路由更新是通过周期性的RIPRes.来广播的网内某处发生的变化要传播到网内的其它地方，这个过程比较慢Instability（不稳定性）AninternetrunningRIPcanbecomeunstableroutingloop2022/10/29TCP/IPProtocolSuite30SlowConvergenceNet1Net2Netn+10seconds15secondsn×15secondsSolutionTolimitthehopcountto1516isconsideredinfinityanddesignatesanunreachablenetwork2022/10/29TCP/IPProtocolSuite31RoutingLoopNet1Net2Net3Net1…………RoutingtableNet1A…………RoutingtableABYoucanreachnet1throughmewithlength2Bcanreachnet1!Great!Hopcountchanged!-11623Hopcountchanged!4-B1616B:(net1,2)A:(net1,3)B:(net1,4)2022/10/29TCP/IPProtocolSuite32SomeRemediesforInstabilityTriggeredupdate（触发更新）Splithorizons（分割范围）Poisonreverse（毒性逆转）AvariationofsplithorizonsHold-downtimer（抑制定时器，notinRFC）Noneofthemare100%effective!2022/10/29TCP/IPProtocolSuite33TriggeredUpdateAnattempttospeeduptheconvergenceIftherearenochangesonthenetworkTosendupdatemessagesatusual30-sintervalsIfthereisachangeTosendupdatemessagesalmostimmediatelySpecialhandlingTolimitthefrequencyoftriggeredupdatesSetatimerforarandomtimebetween1and5sAsingleupdateistriggeredwhenthetimerexpiresTolimittheroutesincludedintriggeredupdatesAtleastthosechangedroutes2022/10/29TCP/IPProtocolSuite34SplitHorizons解决RIP的路由不稳定问题基本思路：路由器在发送路由更新时，要根据发送接口，选择性地组织更新分组（通告路由表中的部分路由，而非整个路由表）原则是：通过某个接口获得的路由信息，不再从这个接口回送过去2022/10/29TCP/IPProtocolSuite35SplitHorizonsNet1Net2Net3ABNet2 1Net3 2Net1 1RIPmessagesNet1 2Net2 1Net3 1RIPmessages2022/10/29TCP/IPProtocolSuite36PoisonReverse范围分割策略的缺点：无法更新某些路由表项导致路由被删除基本操作：路由更新仍然是将整个路由表发送出去但是，对于那些从某个接口获得的路由表项在通过同样的接口更新扩散时，要将其Metric值设为16意思是：“不要使用该路由，我所知道的关于这条路由的信息是来自你的”2022/10/29TCP/IPProtocolSuite37PoisonReverseNet1Net2Net3ABNet2 1Net3 2RIPmessagesNet1 16Net2 16Net3 16Net1 1RIPmessagesNet2 16Net3 1Net1 16Net2 1Net3 16Net1 2Disadvantage:Increasingthesizeoftheroutingmessages2022/10/29TCP/IPProtocolSuite38问题还没有结束Net1ABCDENet1unreachable,thenEsendsatriggeredupdatetoitsneighborAThenAknowsNet1isunreachablefromE,thensendsatriggeredupdateonlytoneighborsBandDbecauseofthesplithorizonsBandDknowNetunreachablefromA,thensendatriggeredupdateonlytotheneighborCbecauseofthesplithorizonsAssumethatChasknownaboutNet1fromB,andCsendsaregularupdateaboutNet1isaccessibletoDbeforethetriggeredupdatehasbeenreceived.ThenDthinkNet1canbereachablethroughC,soDupdatesitsroutingtableandinformsA——routingloopX2022/10/29TCP/IPProtocolSuite39Hold-downTimer路由器在收到关于某网络不可达信息后的一段固定时间内，忽略任何关于该网络的路由信息Topreventupdatemessagesfromreinstatinginaccessibleroutes算法：Whenarouterreceivesanupdatethatindicatesanetworkisunreachable,itstartsahold-downtimer(180s)Whilethehold-downtimerisrunning,therouterwillNOT

acceptanyupdateabouttheinaccessiblerouteUNLESS

theupdatecomesfromtheoriginatorofthepreviouslyinaccessibleupdateorfromarouterreportingabettermetrictotheinaccessiblenetwork“好消息传得快，坏消息传得慢”所以，等待足够长的时间，确保所有路由器都收到坏消息2022/10/29TCP/IPProtocolSuite40RIPVersion2MessageformatOperationAuthentication:Family=0xFFFFMulticasting:RIP报文仅对网络中的RIP路由器进行多播Encapsulation:UDP(port520)CommandVersionIPaddressSubnetMaskAll0sNextHopMetricRouteTagFamily2022/10/29TCP/IPProtocolSuite41Chapter11RoutingProtocolsInteriorandexteriorroutingRIPOSPFBGP-42022/10/29TCP/IPProtocolSuite42OSPFOpenShortestPathFirst，OSPFv2：RFC2328，开放最短路径优先IPLANsMANsWANsICMPIGMPARPRARPNetworkLayerNetworkAccessLayerTCPUDPTransportLayerOSPFApplicationLayer89软件实现层次2022/10/29TCP/IPProtocolSuite43LinkStateRoutingDijkstraalgorithm(SPFalgorithm)2022/10/29TCP/IPProtocolSuite44DijkstraAlgorithmCalculatingatreeofshortestpathswiththerouteritselfasrootDividesthenodesinto2setsTentative（临时性节点集合）

ifpassthecriteriaPermanent（永久性节点集合）2022/10/29TCP/IPProtocolSuite45DijkstraAlgorithmBCF72224233HDEG261(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-D11TheassumptionofLink

stateroutingEachnodehaspartialknowledge:itknowsthestate(type,condition,andcost)ofitslinks.Thewholetopologycanbecompiled*fromthepartialknowledgeofeachnode.Compile:whenyoucompilesomethingsuchasareport,book,orprogramme,youproduceitbycollectingandputtingtogethermanypiecesofinformation.柯林斯高阶英语词典2022/10/29TCP/IPProtocolSuite46LinkStateRouting2022/10/29TCP/IPProtocolSuite47Theidea:Everyroutershouldhavethewholepictureoftheinternet2022/10/29TCP/IPProtocolSuite48获取网络拓扑TosharetheknowledgeabouttheinternetWhat thestateofitslinkstates(LSA)Where witheveryotherrouter(flooding)When thereisachange(event-driven)213456435611421022ABIJCDEFG666662022/10/29TCP/IPProtocolSuite49什么是链路状态路由协议什么是路由器的链路状态（Link-state）？链路类型，cost，condition(up/down)通过该链路所连接的邻居——链路标识“邻居”的类型取决于链路的类型关键：链路状态到底如何描述？2022/10/29TCP/IPProtocolSuite50什么是链路状态路由协议链路状态路由协议要求路由器需要建立其所在区域内每台路由器的所有链路状态的完整数据库——所在区域的网络拓扑路由器根据拓扑执行SPF（最短路径优先算法），最终以该路由器为树根，由它出发到其他各个网络的路径为树枝的一棵树2022/10/29TCP/IPProtocolSuite51链路状态路由协议的关键问题如何刻画路由器之间的邻居关系如何建立自己所在区域内每台路由器的所有链路状态的完整数据库——网络拓扑2022/10/29TCP/IPProtocolSuite52路由器间的邻居关系路由器间的邻居关系由连接它们的网络类型决定举例：点到点网络只连接两台路由器可能会有多台路由器连在一个以太网上这种网络被称为转接网络转接网络的路由器间的邻居关系比较多——链路状态开销大转接网络上的路由器只与指定路由器建立邻居关系RARBLAN2RDLAN1LAN4RCLAN3RARBLAN2RDLAN1LAN4RCLAN3222314122022/10/29TCP/IPProtocolSuite53OSPF网络类型点到点网络广播多路访问网络例如：以太网、令牌环网非广播型多路访问（NBMA）网络例如：帧中继，X.25FrameRelayX.25Transitnetwork（转接网络）：该网络上有多个路由器2022/10/29TCP/IPProtocolSuite54OSPFLinkTypesOSPF中一条网络连接就是一条链路点到点链路（Point-to-pointlink）：连接两个路由器邻居——邻居路由器转接链路（Linktotransitnetwork）：转接链路是连接有若干路由器的网络每个路由器可能有多个邻居节点Broadcast（局域网）NBMA（非广播型多路访问）——广域网FrameRelayX.25?2022/10/29TCP/IPProtocolSuite55连接：Transitnetwork存在的问题N个路由器组成的转接网络，每个路由器都有（N－1）个邻居路由器（即N-1条连接）这种邻居连接关系：低效、且不现实解决思路：将转接网络本身也抽象成为一个路由器（节点）具体方案：选择一个指定路由器来充当转接网络抽象成为的路由器节点2022/10/29TCP/IPProtocolSuite56在Transitnetwork中存在：

DR(指定路由器)和BDR(备份指定路由器)Designatedrouter&backupDR(指定路由器&备份指定路由器)在转接网络中，所有一般路由器只与该网络中的DR/BDR建立邻居关系！指定路由器的功能：与该转接网络中的其它路由器建立毗邻关系作为该转接网络的“发言人”通告转接网络的网络地址是转接网络中LSA的集中处理点Purpose：减少Transitnetwork的路由开销ReducethenumberofadjacenciesrequiredonabroadcastorNBMAnetworkReducetheamountofroutingprotocoltrafficandthesizeofthelink-statedatabase2022/10/29TCP/IPProtocolSuite57OSPFLinkTypes转接链路（Linktotransitnetwork）：邻居——指定路由器残桩链路（Linktostubnetwork）：只连接到某一个路由器的网络邻居——网络虚链路（Virtuallink）两个路由器之间链路断开时，人工创建一条更长路径的虚拟链路（经过多个路由器）Area0Area2Area1Area3将网络抽象成1个节点（路由器）指定路由器2022/10/29TCP/IPProtocolSuite58关键：链路状态到底如何描述？2022/10/29TCP/IPProtocolSuite59举例链路类型链路标识链路数据点到点01点到点12残桩2022/10/29TCP/IPProtocolSuite60平面路由VS.分层路由RIP是一种典型的平面路由协议，即AS内的所有路由器的地位都是平等的，执行的路由功能都相同OSPF是一种分层路由：AS划分成若干区域（Area）路由器在路由功能上出现分工Area1Area2Area0(backbone)AutonomousSystemTootherASs2022/10/29TCP/IPProtocolSuite61SplittingtheASintoAreas!分区域理由：大规模的网络会给OSPF路由器带来沉重的负担链路状态的改变，可能会使路由器经常执行SPF（最短路径优先）算法路由表膨胀每个路由器需要保持的完整网络拓扑（链路数据库）OSPF将网络划分成若干较小的区域区域内的路由器执行SPF算法区域间：交换汇总后的路由信息，而不是详细的路由信息2022/10/29TCP/IPProtocolSuite62SplittingtheASintoAreas!AdvantagesReduceLSA(linkstateadvertisements)overheadReducefrequencyofSPFcalculationsSmallerroutingtablesArea1Area0Area22022/10/29TCP/IPProtocolSuite63SplittingtheASintoAreas!AS中存在两种层次的路由Intra-arearouting（区域内路由）区域内路由器执行链路状态路由算法Inter-arearouting（区域间路由）由一些特殊路由器负责将某一区域的路由汇总之后向其它区域更新2022/10/29TCP/IPProtocolSuite64OSPFAreaArea：包含在AS中的一些网络、主机和路由器的集合类型：标准区域、主干区域（Backbonearea）、残桩区域（Stubarea）AutonomousSystemArea1Area2Area0(backbone)TootherASs2022/10/29TCP/IPProtocolSuite65OSPF区域类型区域的类型：决定了该区域内路由器所能接收的路由信息的类型标准区域：区域内路由器能够接收链路状态更新和路由归纳（区间路由）主干区域：具有标准区域的一切属性，特殊之处在于：它需要负责互连其它所有区域残桩区域：这种区域不接收那些自治系统以外的路由信息如果需要发送分组到自治系统之外的网络，区域内路由器将使用默认路由2022/10/29TCP/IPProtocolSuite66Area2Area3Area0Area1Area0BackboneareaBeresponsiblefordistributingroutinginformationbetweennon-backboneareasMustbecontiguousNOTneedbephysicallycontiguousVirtuallinkArea0：BackboneareaArea0Area2Area1Area32022/10/29TCP/IPProtocolSuite67OSPFRouterTypesAutonomousSystemArea1Area2Area0(backbone)TootherASABR，BRIRASBR，BRIR，BRInternalrouter（内部路由器）,IRBackbonerouter（主干路由器）,BRAreaBorderRouter（区域边界路由器）,ABRASBorderRouter（AS边界路由器）,ASBR2022/10/29TCP/IPProtocolSuite68OSPFRouterTypes内部路由器(IR)路由器所有接口都在同一个区域内同一区域IR具有相同的链路状态库主干路由器(BR)该路由器至少有一个接口连接到主干区域(Area0)AutonomousSystemArea1Area2Area0(backbone)IRIR，BRBR，ABR2022/10/29TCP/IPProtocolSuite69OSPFRouterTypes区域边界路由器(ABR)路由器的接口分别连接不同区域ABR为其连接的每个区域维护着单独的链路状态数据库ABR从其连接的区域链路状态数据库中归纳路由，将汇总路由发布到主干区域，而主干区域中的ABR再将其扩散到其它区域AutonomousSystemArea1Area2Area0(backbone)ABR2022/10/29TCP/IPProtocolSuite70OSPFRouterTypesAS边界路由器(ASBR)该路由器至少有1个接口连接另一个自治系统ASBR向自治系统通告自治系统以外的路由AutonomousSystemArea1Area2Area0(backbone)ASBR，BR2022/10/29TCP/IPProtocolSuite71OSPFLSA(linkstateadvertisements)TypesIntra-areaType1:Router–LSAType2:Network–LSAInter-areaType3:Summarylinktonetwork–LSAType4:Summarylinktoboundaryrouter–LSAExternalType5:AS–external–LSA2022/10/29TCP/IPProtocolSuite72LinkstateupdatepacketLSAgeneralheaderLSAgeneralheaderLinkstatetype:type1~type5LinkstateIDType1:路由器IDType2：指定路由器IDType3：网络IPType4：ASBR路由器IDType5：外部网络IP2022/10/29TCP/IPProtocolSuite732022/10/29TCP/IPProtocolSuite74Intra-areaLSAsType1:Router–LSA(路由器链路通告)：在本区域内发布所有邻居及其对应链路的信息OriginatedbyallroutersDescribesthecollectedstatesoftherouter’sinterfacestoanareaFloodedthroughoutasingleareaonlyOSPF链路类型Type1LSA举例PTP链路2022/10/29TCP/IPProtocolSuite75Type1LSA举例Transition链路2022/10/29TCP/IPProtocolSuite762022/10/29TCP/IPProtocolSuite77Intra-areaLSAsType2:Network–LSA(网络链路通告)：由DR在本区域内发布其所在Transitnetwork上其它路由器信息OriginatedforbroadcastandNBMAnetworksbytheDRContainsthelistofroutersconnectedtothenetworkFloodedthroughoutasingleareaonlyType22022/10/29TCP/IPProtocolSuite78Type2LSA举例2022/10/29TCP/IPProtocolSuite792022/10/29TCP/IPProtocolSuite80Inter-areaLSAsType3:Summary–LSA(汇总链路到网络)：由ABR产生，在其所属的每个区域里中发布到达其它区域的路由信息OriginatedbyABRsDescribesroutestonetworksoutsidetheareaFloodedthroughouttheLSA’sassociatedareaType32022/10/29TCP/IPProtocolSuite812022/10/29TCP/IPProtocolSuite82Type3LSA举例当子网1由断开恢复成为连通以后，在子网4中收到的链路状态通告2022/10/29TCP/IPProtocolSuite83Inter-areaLSAsType4:Summary–LSA(汇总链路到ASBR)：由ABR产生，在本AS内的所有区域中发布到达ASBR的路径信息OriginatedbyABRsDescribesroutestoASBRsFloodedthroughouttheLSA’sassociatedareaType42022/10/29TCP/IPProtocolSuite842022/10/29TCP/IPProtocolSuite85Type4LSA举例2022/10/29TCP/IPProtocolSuite86ExternalLSAsType5:AS–external–LSA：由ASBR产生，在本AS内的某些区域中发布到达AS以外网络的路径信息OriginatedbyASBRDescribesaroutetoadestinationinanotherASFloodedthroughouttheASexceptthestubareaType52022/10/29TCP/IPProtocolSuite872022/10/29TCP/IPProtocolSuite88Type5LSA举例2022/10/29TCP/IPProtocolSuite89OSPFLSAExample哪些路由器会发送Router–LSA？SolutionAllroutersadvertiserouterlinkLSAs.R1hastwolinks,Net1andNet2.R2hasonelink,Net2inthisAS.R3hastwolinks,Net2andNet32022/10/29TCP/IPProtocolSuite90OSPFLSAExample哪些路由器发送的LSA中含有网络信息？SolutionAllthreenetworkmustadvertisenetworklinks:R1通告Net1Becauseitistheonlyrouterandthereforethedesignatedrouter.Net2可能由R1,R2,R3中任意一个通告dependingonwhichoneischosenasthedesignatedrouter.R3通告Net3isdonebecauseitistheonlyrouterandthereforethedesignatedrouter.2022/10/29TCP/IPProtocolSuite91LSA的发送方式LSA采用组播发送，所有OSPF路由器的组播地址都是：在转接网络（广播多路访问网络、NBMA）网络中，DR和BDR还具有自己的组播地址：转接网络中，由于一般路由器只与DR/BDR存在邻居关系，所以其LSA将发送到2022/10/29TCP/IPProtocolSuite92OSPFLSAExample1Area1DRArea0Area2(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)2022/10/29TCP/IPProtocolSuite93OSPFLSAExample2两次拓扑变化子网4变为不可达子网4变为可达，R6变为ASBR，并且产生AS外部路由子网1Area1子网35.234.212R1R2R4R5.224.223子网2Area2(stubarea)Area0R6.226AS20/16AS10/16子网4R3子网1＝/24 子网2＝/24子网3＝/24 子网4＝/252022/10/29TCP/IPProtocolSuite94第1次拓扑变化产生的LSA子网1：类型1（路由器链路）LSA，由内部路由器R1始发，在区域1中洪泛内容：R1的链路数目只有1条链路，即连接子网1的链路数目：2个LSA子网2：类型3（汇总链路到网络）LSA，由区域边界路由器R3始发，在区域0中洪泛内容：通告连接子网4的链路，其Metric值“无穷大”数目：2个LSA子网3：类型3（汇总链路到网络）LAS，它由区域边界路由器R4始发，在区域3中洪泛内容：通告连接子网4的链路，其Metric值“无穷大”数目：1个LSA拓扑变化前，R1路由器链路LSA包含两条链路：1）残桩链路，2）转接链路2022/10/29TCP/IPProtocolSuite95第2次拓扑变化产生的LSA子网1：类型1（路由器链路LSA）LSA，由内部路由器R1始发，在区域1中洪泛内容：R1的链路数目有2条链路：连接子网1的链路和连接子网4的链路数目：2个LSA类型4（汇总链路到ASBR）LSA，由区域边界路由器R3始发，在区域1中洪泛内容：本自治系统的自治系统边界路由器R6数目：1个类型5（外部链路）LSA，由R6始发，区域边界路由器R3转发，在区域1中洪泛内容：外部自治系统路由器数目：1个子网2：类型1（路由器链路LSA）LSA，由内部路由器R6始发，在区域0中洪泛内容：R6链路数目有1条：转接链路数目：1个LSA类型3（汇总链路到网络）LAS，由区域边界路由器R3始发，在区域0中洪泛内容：通告连接子网4的链路数目：2个LSA类型5（外部链路）LSA，由R6始发，在区域0中洪泛内容：外部自治系统路由器数目：1个子网3：类型3（汇总链路到网络）LAS，由区域边界路由器R4始发，在区域2中洪泛内容：通告连接子网4的链路数目：1个LSA2022/10/29TCP/IPProtocolSuite96OSPF中的数据库AdjacencydatabaseAlltheneighborstowhicharouterhasestablishedbidirectionalcommunicationUniqueforeachrouterLink-statedatabaseTherelationshipbetweeneachrouteranditsneighborsAllrouterswithinanareahaveidenticallink-statedatabasesForwardingdatabase(routingtable)TheroutesgeneratedwhenanSPFalgorithmisrunonthelink-statedatabaseTheroutingtableoneachrouterisunique通过路由器LSA和网络LSA构成链路状态数据库2022/10/29TCP/IPProtocolSuite97OSPFPacketsFormatMulticasting:,Encapsulation:IP(protocol89)VersionTypeSourceRouterIDAreaIDPacketLengthAuthenticationAuthenticationTypeChecksumHeaderOSPFPacketData2022/10/29TCP/IPProtocolSuite98PacketTypes1: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-oriented2022/10/29TCP/IPProtocolSuite99Hellopacket2022/10/29TCP/IPProtocolSuite100OSPFOperation1.Establishrouteradjacencies(毗邻)DonewiththeexchangeofHellos2.ElecttheDR/BDR(ifnecessary)Doneonmultiaccessnetworkonly3.DiscoverroutesDoneintheExStartandExchangestates4.SelectappropriateroutesDonethroughthecalculationofSPFalgorithm5.MaintainroutinginformationDonethroughtheregularexchangeofHellos2022/10/29TCP/IPProtocolSuite101OSPFStatesDown:NotexchangeinformationwithanyneighborInit:WhenaninterfacereceivesitsfirstHello2-way:Whenitseesitselfinaneighbor’sHelloExStart:TwoneighborsuseHellotonegotiatewhoisthe“master”andwhoisthe“slave”Exchange:NeighborsuseDBDtosendeachotherasummaryoftheirlink-statedatabaseLoading:UsesLSR,LSU,andLSAcktogetcompletelink-stateinformationFull:Neighborsarefullyadjacent2022/10/29TCP/IPProtocolSuite102Step1.EstablishrouteradjacenciesIamrouterID