TCPIP协议课件：第14章 单播路由选择协议

1、1第14章 单播路由选择协议Metric & Convergence内部和外部路由选择距离向量路由选择RIP链路状态路由选择OSPF路径向量路由选择BGP2引言表驱动IP选路一个路由器上可运行多种 Routed Protocols每个Routed Protocol 可以使用多种 Routing Protocols 来获取路由信息设定的路径 Route Table内容：部分选路信息 + 默认路由Internet 中的选路网络拓扑结构管理策略一致性及时性3路由表的构成过程初始化阶段 路由发现推导初始路由直连网络 直连路由无法推导部分手工设置 静态路由路由器间交换选路信息 动态路由维护阶段 路由更新

2、（网络拓扑改变时）手工、静态更新小型、变化缓慢的网络路由协议自动、动态更新大型、迅速变化的网络4静态路由 vs. 动态路由静态路由Static route管理员手工设置管理员手工更新不能保证路由的一致性和及时性管理性强没有路由开销小型、变化缓慢网络动态路由Dynamic route路由协议自动发现路由协议自动更新保证路由的一致性和及时性管理性较弱产生一定的路由开销大型、迅速变化网络514.1 Metric & Convergence选路准则 最短路径Metric （度量）：衡量路径的长短跳数（经过路由器的数目，hop count）带宽（bandwidth）、延迟（delay）、负载（load）

3、、开销（cost）不同的 Metric 产生不同的“最短路径”不同的路由协议采用不同类型的Metric一个路由协议可同时应用多重 MetricADCBNet64K64K10M10M10M跳数：A B Net带宽：A C D Net6Convergence（收敛）收敛采用特定路由协议的所有路由器对整个网络拓扑具有一致性的认识收敛时间从不一致到一致所经历的时间体现路由算法的效率714.2 内部和外部路由选择自治系统（Autonomous System，AS）处于一个管理机构控制下的网络和路由器的集合AS 使管理机构可自主选择其内部路由方式和对外通告部分可达性信息的权利每个AS赋予一个AS编号由负责

4、分配Internet地址的中央管理机构统一分发取值：165535Internet由若干AS互相连接构成每个AS内可能有多个网络存在核心主干网也可以构成一个AS8AS 类型Single-homed AS：只有一个出口如：AS 2、AS 3Multi-homed AS：有多个出口如： AS 1Nontransit AS，Transit ASAS 1RAS 3AS 2RRR9EGP vs. IGP外部网关协议Exterior Gateway Protocol，EGP由AS边界路由器在AS间通告可达性信息目前常用协议：BGP内部网关协议Interior Gateway Protocol，IGPAS内部

5、路由器在AS内通告内部网络细节目前常用协议：RIP、OSPFAS 1AS 2RREGPIGPIGP功能层次：网络层10RIP & OSPF & BGPRIP内部网关协议距离向量路由算法（D-V）RIPv1，RIPv2OSPF内部网关协议链路状态路由算法（L-S）OSPFv2BGP外部网关协议路径向量路由算法（P-V）BGP-4算法原理协议报文操作路由发现路由更新问题1114.3 距离向量路由算法原理（DistanceVector）Bellman-Ford Algorithm发布路由信息Each router passes its whole routing table to neighbor

6、routersWhat：the whole routing tableWhere：to its neighbor routersWhen：periodical or triggered计算路径Accumulate distance vectors1214.4 RIPRouting Information Protocol，RIPv1：RFC 1058，v2：RFC 2453，选路信息协议 IPLANsMANsWANsICMPIGMPARPRARPNetworkLayerNetworkAccess LayerTCPUDPTransportLayerRIPApplicationLayer520协议

7、软件层次13RIP报文格式CommandVersionIP addressAll 0sAll 0sAll 0sMetricAll 0sFamily重复25次（ ）广播发送：255.255.255.255封装在UDP报文中：UDP port = 52014RIP报文域Command Request（Command = 1）路由器刚接入网络，或某些路由表项超时请求所有路由表项（IP address = 0.0.0.0）请求部分路由表项（ IP address = 网络地址）Response（ Command = 2）询问响应：应答RIP Request报文非询问响应：定期发送路由表中的所有路由信息

8、Family - Address Family Identifier2 IP address未定义掩码，只能用于有类地址方式15V-D对实际是交换（IP address，Metric）对V是IP地址格式（4字节）可为A、B、C类网络地址或主机地址如果无二义性解释时，也可发送子网地址存在子网时，网络地址和主机地址存在二义性16RFC1058 初始化17RIP路由发现过程(RFC)ABCN1N2N3N4121212N3-11N4-21N1-11N2-21N2-11N3-21路由表：目的网络下一跳发送接口MetricN3N1N2B122A212B212C122N4A: (N1, 1) (N2, 1)

9、B: (N2, 1) (N3, 1)C: (N3, 1) (N4, 1)B: (N2, 1) (N3, 1)N4B123N1B213A: (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)18RIP路由更新算法IF（IP

10、 address不在路由表中）根据该报文添加新路由表项；ELSEIF（路由表对应表项的下一跳 = = 通告路由器）根据该报文修改路由表中的对应表项；ELSEIF（Metric 路由表对应表项的跳数）根据该报文修改路由表中的对应表项；ELSE不修改路由表中的对应表项；19RFC105820RIP路由发现过程（CISCO）ABCN1N2N3N4121212N3-1-N4-2-N1-1-N2-2-N2-1-N3-2-路由表：目的网络下一跳发送接口MetricN3N1N2B121A211B211C121N4A: (N1, 1) (N2, 1)B: (N2, 1) (N3, 1)C: (N3, 1) (

11、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)21RIP路由更新过程(RFC)ABCN1N2N3N4121212N3-11N4-21N1-

12、11N2-2N2-1N3-21N3N1N2B122A212B212C122N4N4B123N1B213B: (N2,16) (N3,1) (N1,2) (N4,2)A: (N1,1) (N2,16) (N3,2) (N4,3)11C: (N3,1) (N4,1) (N2,16) (N1,3)22RIP路由更新过程(CISCO)ABCN1N2N3N4121212N3-1-N4-2-N1-1-N2-2N2-1N3-2-N3N1N2B121A211B211C121N4N4B122N1B212B: (N2,16) (N3,1) (N1,2) (N4,2)A: (N1,1) (N2,16) (N3,2)

13、 (N4,3)-C: (N3,1) (N4,1) (N2,16) (N1,3)23RIP中的定时器TimersGarbage collection120 secondsExpiration180 secondsPeriodic30 secondsP = 30sE = 180sP = 30sE = 180sE = 180sG = 120s30s180s删除路由120s为防止所有路由器同时更新引起的网络过载，定时器Periodic 值为2530 秒间的一个随机数。24RIP异常处理路由器故障路由器故障邻接路由器受到直接影响（无信息通告）对通过RIP获得的路由表项，设置定时器超时未刷新（180秒，6

14、个广播周期），该表项无效预防RIP报文丢失的措施25问题：二节点循环的不稳定性Net 1Net 2Net 3Net1Routing tableNet1ARouting tableABYou can reach net1 through me with length 2B can reach net1 ! Great !Hop count changed !1234Hop count changed !5-B26解决方法定义无穷大RIP协议中最大跳数为15，而将16定义为无穷大触发更新，Triggered update水平分割，Split horizons毒性逆转，Poison reverse抑

15、制定时器，Hold down timer没有一种方法是100%有效的！27触发更新如果网络中没有变化定时（30s）发送所有路由信息如果网络中有变化立即发送更新的所有路由信息为避免触发广播风暴，随机延时后再通告28水平分割Net 1Net 2Net 3ABNet21Net32Net11RIP messagesNet12Net21Net31RIP messages不回传路由信息，路由信息向远离网络的方向扩散当更新报文从某接口发送出来时，该更新信息中不能包含从该接口接收的更新信息中获取到的网络。29毒性逆转直接连接的路由消失后，在若干（至少一个）广播周期内都保留该路由（距离无限大），并向外通告对分割

16、更新的修正：回传路由信息的距离为无限大当更新信息发送出某接口时，信息中将指定从该接口接收到的更新信息中获取的网络为不可达。毒性逆转能迅速打破较小的环路如两个路由器到目的网络的路由都指向对方30毒性逆转Net 1Net 2Net 3ABNet21Net32RIP messagesNet116Net216Net316Net11RIP messagesNet216Net31Net116Net21Net316Net1231抑制定时器路由器在收到关于某网络不可达信息后的一段固定时间内，忽略任何关于该网络的路由信息“好消息传得快，坏消息传得慢” 等待足够的时间，确保所有路由器都收到坏消息32RIP v2报

17、文格式Route Tag：携带自治系统号信息，能够从域间路由选择协议中接收信息Subnet Mask 和 Next Hop：表示支持无分类编址和CIDR认证：Family = 0 xFFFF组播发送RIPv2报文：224.0.0.9CommandVersionIP addressSubnet MaskAll 0sNext HopMetricRoute TagFamily3314.5 链路状态路由算法原理（LinkState）Dijkstra Algorithm发布路由信息What: the link state advertisement （LSA）packetsWhere: to every

18、 router in the areaWhen: event-driven计算路径SPF algorithm to form a SPF tree洪泛法（flooding）3414.6 OSPFOpen Shortest Path First，OSPFv2：RFC 2328，开放最短路径优先 IPLANsMANsWANsICMPIGMPARPRARPNetworkLayerNetworkAccess LayerTCPUDPTransportLayerOSPFApplicationLayer89协议软件层次35OSPF术语：区域Area包含在AS中的一些网络、主机和路由器的集合类型：标准区域、主

19、干区域、残桩区域Autonomous SystemArea 1Area 2Area 0 (backbone)到其他ASArea typesStandardBackboneStub2022/10/1TCP/IP Protocol Suite（2007 Fall）36OSPF区域类型区域类型决定了该区域内路由器所能接收的路由信息类型标准区域：区域内路由器能够接收链路状态更新和路由归纳（区间路由）主干区域：具有标准区域的一切属性，但需要负责互连其它所有区域残桩区域：该区域不接收自治系统以外的路由信息如果需要发送分组到自治系统之外的网络，区域内路由器将使用默认路由37OSPF术语：OSPF路由器类型内

20、部路由器（ IR ，Internal Router）主干路由器（ BR ，Backbone Router）区域边界路由器（ABR，Area Border Router）AS边界路由器（ASBR，AS Border Router）Autonomous SystemArea 1Area 2Area 0 (backbone)到其他ASABR，BRIRASBR，BRIR，BR2022/10/1TCP/IP Protocol Suite（2007 Fall）38OSPF路由器类型内部路由器（ IR ）路由器所有接口都在同一个区域内同一区域IR具有相同的链路状态库主干路由器（ BR ）该路由器至少有一个接

21、口连接到主干区域区域边界路由器（ ABR ）路由器的接口分别连接不同区域ABR为其连接的每个区域单独维护链路状态数据库ABR从其连接区域链路状态数据库中归纳路由，将汇总路由发布到主干区域，而主干区域中的ABR再将其扩散到其它区域AS边界路由器（ASBR）该路由器至少有一个接口连接另一个ASASBR向自治系统通告自治系统以外的路由39OSPF术语：链路Link：与邻居路由器之间的网络点到点链路（Point-to-point link）点到点网络过渡链路（Link to transit network）多路访问网络残桩链路（Link to stub network）残桩网络虚链路（Virtual

22、link）Frame RelayX.25Area 0Area 2Area 1Area 340OSPF术语：DR和BDR定义DR：Designated Router，指定路由器BDR：Backup DR，备份指定路由器作用：减少过渡链路上的路由开销例：过渡链路上有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）条LS41OSPF LSA发送方式封装在IP分组中：IP Protocol = 89组播发送：224.0.0.5，224.0.0.6所有OS

23、PF路由器的组播地址都是224.0.0.5但在过渡网络中，DR/BDR还具有自己的组播地址224.0.0.6过渡网络中，由于一般路由器只与DR/BDR存在邻居关系，所以其LSA将发送到224.0.0.642OSPF 分组格式VersionTypeRouter IDArea IDPacket LengthAuthenticationAuthenticationAuthentication TypeChecksum首部OSPF Packet Data43OSPF 分组类型1：Hello packet用来建立并维护OSPF邻接关系。在建立了邻接关系后，OSPF路由器会定期发送Hello报文来测试邻站

24、的可达性2：DBD ( Database Description )描述OSPF路由器的链路状态数据库的概要信息，即数据库中每一行的标题，它在两台相邻路由器彼此建立邻接关系时发送3：LSR ( Link-State Request )由需要若干条特定路由信息的路由器发送出的，它的回答是LSU报文。新接入的路由器在收到DBD报文后，可以使用LSR报文请求关于某些路由的更多信息44OSPF分组类型4：LSU ( Link-State Update，LSA )OSPF的核心。OSPF路由器使用LSU报文通告链路状态更新信息（即链路状态通告，LSA），每一个LSU报文可包含几个LSA。OSPF LSA

25、有5种常用类型，由不同类型的OSPF路由器产生，在特定类型区域内扩散。5： LSAck ( Link-State Acknowledgement )用来确认每一个收到的LSU报文，使得OSPF协议的路由选择更加可靠。2022/10/145OSPF LSA类型域内（Intra-area）Type 1: RouterLSAType 2: NetworkLSA域间（Inter-area）Type 3: Summary link to networkLSAType 4: Summary link to boundary routerLSA外部（External）Type 5: ASexternalLS

26、A46域内LSAType 1：RouterLSA在本区域内发布所有邻居及其所在链路的信息Originated by all routersDescribes the collected states of the routers interfaces to an areaFlooded throughout a single area onlyType 2：NetworkLSA由DR在本区域内发布其所在过渡网络上其他路由器信息Originated for broadcast and NBMA networks by the DRContains the list of routers conn

27、ected to the networkFlooded throughout a single area only47域间LSAType 3：SummaryLSA由ABR产生，在其所属的每个区域里中发布到达其它区域某网络的路径信息Originated by ABRsDescribes routes to networks outside the areaFlooded throughout the LSAs associated areaType 4：SummaryLSA由ABR产生，在本AS内的某些区域中发布到达ASBR的路径信息Originated by ABRsDescribes rou

28、tes to ASBRsFlooded throughout the LSAs associated area48外部LSAType 5：ASexternalLSA由ASBR产生，在本AS内的某些区域中发布到达AS以外网络的路径信息Originated by ASBRDescribes a route to a destination in another ASFlooded throughout the AS except the stub area49OSPF LSA ExampleArea 1DRArea 0Area 2(Stub)AS 10AS 20Type 2Type 2Type 2

29、Type 3(Area 1)Type 5(AS 20)Type 5(AS 20)Type 5(AS 20)Type 5(AS 20)Type 3(Area 1)Type 5(AS 20)Type 3(Area 1)Type 1(Area 1)Type 1(Area 0)Type 1(Area 0)Type 3(Area 0)Type 3(Area 0)Type 3(Area 0)DefaultType 5(AS 20)Type 5(AS 20)Type 1(Area 1)Type 1(Area 1)50OSPF 邻居状态Down：Not exchange information with an

30、y neighborInit：When an interface receives its first Hello2-way：When it sees itself in a neighbors HelloExStart：Two neighbors use Hello to negotiate who is the “master” and who is the “slave”Exchange：Neighbors use DBD to send each other a summary of their link-state databaseLoading：Uses LSR, LSU, and

31、 LSAck to get complete link-state informationFull：Neighbors are fully adjacent51OSPF 操作步骤1. Establish router adjacenciesDone with the exchange of Hellos2. Elect the DR / BDR ( if necessary )Done on multiaccess network only3. Discover routesDone in the ExStart and Exchange states4. Select appropriate

32、 routesDone through the calculation of SPF algorithm5. Maintain routing informationDone through the regular exchange of Hellos52步骤1：建立邻接关系I am router ID 172.68.5.1 and I see no oneDown State172.68.5.1/24E0172.68.5.2/24E1ABRouter B 邻接表172.68.5.1/24, int E1Init StateI am router ID 172.68.5.2, and I se

33、e 172.68.5.1Router A 邻接表172.68.5.2/24, int E0Two-way StateHello3954743907071339547439070713Hello395474390707133954743907071353步骤3：路由发现Hello PacketABExstartExchangeLoadingFullHello PacketDBD PacketDBD PacketLSAck PacketLSAck PacketLSR PacketLSU PacketLSAck Packet54OSPF Tables邻接表（Adjacency Table）存放所有与

34、之建立双向通信的邻居路由器信息链路状态数据库（Link-State DB）存放本区域中的所有链路状态信息同区域内所有路由器的LS DB信息是相同的转发表（Forwarding Table）路由表，存放所有经SPF算法获得的最短路由55SPF 算法BCF72224233HDEG261(2, A)(4, B)(8, B)(5, E)(6, E)(7, F)(9, H)节点Cost路径EBFCGDH27A-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-D1156RIP vs. OSP

35、F对网络拓扑的了解路由计算方法路由更新方式路由更新内容收敛速度适用环境5714.7 BGP-4Border Gateway Protocol，BGPv4：RFC 1771，RFC 1772，边界网关协议 IPLANsMANsWANsICMPIGMPARPRARPNetworkLayerNetworkAccess LayerTCPUDPTransportLayerBGP-4ApplicationLayer179协议软件层次58BGP 特点外部网关协议AS间的可达信息策略路由AS管理策略可靠传输TCP传输路径向量路由选择Path Vector增量更新Incremental updates支持CIDR发送地址和掩码路由聚合Route Summary认证验证BGP对等路由器59BGPBGP是自治系统之间的路由协议DV、LS不适合自治系统之间的路由协议互联网（多个AS组成）规模大，路由计算量大最小跳数的路由不一定优先选择策略路由采