第5章 路由协议.ppt

1、网 络 协 议 分 析（TCP/IP）第五章 路由协议,要求： 1.掌握路由表建立和维护的两种方式; 2.掌握路由体系结构,特别是自治系统AS概念和作用; 3.掌握两种路由更新算法:矢量距离算法和SPF算法。 4.掌握RIP协议特点与用法 5.掌握OSPF协议特点与区域划分思想 6.掌握BGP的原理和流程,一、 路由协议概述,要求： 1掌握路由表建立和维护的两种方式：静态配置和动态交换路由信息； 2掌握Internet的路由体系结构,特别是自治系统AS的概念和作用； 3 掌握两种路由更新算法:矢量距离算法和SPF算法。,（一） 引言,问题： （1）路由器的路由表如何获取？ （2）为什么选择这条

2、路径？ （3）假设两个路由器的连接断掉，如何通知其他路由器？ （4）在Internet中，是否每个路由器都必须了解其它路由器的情况？,（二） 路由表的建立和维护,两种方式：静态配置 和 动态路由交换,1. 静态配置：管理员手工配置和更新路由表 优点：节省路由器的处理时间、存储空间以及网络带宽 缺陷：对于链路故障及拓扑结构变化的响应速度慢,适用环境：拓扑相对稳定，路由器个数较少,利用路由协议交换路由信息，并根据拓扑结构的变化动态更新路由表 优点：自动适应链路故障及拓扑结构的变化 缺陷：耗费路由器的处理时间、存储空间以及网络带宽,适用环境：路由器较多的大规模网络,2. 动态路由信息交换,（三） 选

3、路涉及到的2个关键问题,（1）路径存在性 （2）路径最优性,1. 路径存在性 互联网中的路由器构成一个数据投递系统，每个路由器采用下一跳选路，对每个路由器来说，不是一条完整的目的地路径。 路由表的两个普遍特点： （1）路由表中不包含到达所有目的地的路由。表明:路由器用部分信息选路 （2）路由表中存在默认路由 。说明：当不存在时匹配条目是，用默认路由 要求：（1）单个路由器为连接关系所做的贡献是局部的 （2）所有路由器组成的系统是完备的 2. 路径最优性 问题：如何确保各个路由器维护信息的一致性？ 答案：不同路由器更新路由表的信息是一致的，使得它们对网络拓扑结构有着一致性的认识。 路由表的构造和

4、一致性维护是使用路由协议和路由算法获得。路由算法在构造路由表时，遵循最优化原则。并为每条路径计算度量值。,2. 路由度量,（1）带宽（静态指标） （2）延迟 （3）负载 （4）可靠性 （5）跳数 （6）其它指标，比如代价,理想情况：综合利用以上各指标 缺陷：可能会造成路由震荡 实现：简单的算法仅考虑一个要素，复杂的则综合考虑（如DUAL） 最常用的：基于跳数,问题：如何确定一条路径是最优的？ 解答：选择不同的度量指标,（四） 选路算法,（1）非自适应 （2）自适应,1. 非自适应算法 （1）不考虑当前的拓扑结构和网络流量 （2）设置中心路由器，由管理员预先为每个路由器设置路由表 （3）拓扑发生

5、变化时，由管理员操作中心路由器，更新路由表 （4）适用于规模小，拓扑结构变化少的网络,2. 自适应算法 （1）矢量-距离算法 （2）链路状态算法,（1） 矢量距离路由算法(Bellman、Bellman-Ford和Ford-Fulkerson算法 ) 思想：以跳数作为度量值，通过交换路由表，计算出所有已知的最短路由，更新路由表。,表项格式： 跳数：从源站到目的站间所经过的路由器数目。, 初始化:路由器启动时，对每个直接相连的网络生成一个表项，hop数都为0。 路由交换:路由器周期性向相邻路由器广播自己的整个路由表。(交换信息是) 路由表更新:路由器每收到一个邻站的路由表，即更新自己的路由表。(

6、假设K收到J的路由表) (1) K不知道目的站，则加入 (2)有通过J的更短路，则替换 (3)原下站为J的距离有变化，则修改,仅和相邻交换、广播全部信息、定时 UDP发送,步骤：,思路： 通过交换链路状态，让AS中的每个路由器都有一张该AS的网络拓扑结构图。 使用Dijkstra算法求最短路径，计算该路由器到其它目的站的最短路径，然后更新路由表。 优点： 每个路由器使用相同的原始数据，具有良好的收敛性。 每个路由器的链路状态报文尺寸取决于直连链路的数量，具有较好的规模可扩展性,（2） 链路状态路由算法 - 最短路径优先SPF, 链路状态检测：周期性发测试报文，检查直接相邻的路由器状态，并按“n

7、中取k”原则进行状态检查 。 路由信息广播：路由器周期性广播它的各个链路状态。所有参与SPF的路由器负责转发收到的链路状态 。 路由表更新： 收到链路状态的路由器更新自己的网络拓扑图，并用Dijkstra算法计算最短路径 。,向所有路由器发送、洪泛法发送 IP封装发送，协议字段为89,步骤：,（五） Internet路由体系的发展,路由体系的内容 如何对Internet中的路由器进行划 分、管理和控制，以便有效地交换路由信息 路由体系的重要性 决定了互联网的运行效率 Internet路由体系的发展： （1）最早的核心路由体系 （2）随后的对等主干路由体系 （3）当前的自治系统路由体系,1.核心

8、路由器与核心体系结构,ARPANET主干网,2.选路模式 核心网关:构成核心系统，集中管理,提供到所有目的地的路由。 外围网关:为外出数据报提供默认路由,发往某核心网关;将核心网关传入的数据报投递到直连的物理网络。,2. Internet的对等主干结构,契机：NSFNET的引入,选路模式： 各主干网内部按核心结构方式进行选路 各核心网关拥有对另一部分的默认路由。,两主干间多重接入，造成选路困难。 具有非法目的地址的数据报形成选路回路,问题：,Internet层次结构 Internet的拓扑结构是网状的，但可以从逻辑上分为三个层次,3. 自治系统路由体系,Internet主干网,NAP1,NAP

9、2,NAPn,NSP1,NSP2,NSPN,ISP1,ISP1,ISP1,核心层 网络接入点,分布层 网路服务提供商,接入层 Inter服务提供商,Internet中的自治系统结构 AS(自治系统)：出于选路目的，处于一个管理机构控制之下的一组网络和路由器。,主干网(AS),（1）AS自治的主要内容是选路自治,AS可自由地选择路由算法； （2）AS必须严格界定，并被赋予全局唯一的自治系统号(NIC分配)； （3）主干网络本身也构成一个AS(教育网AS4538)。,说明:,Internet的路由管理模式,（1）AS内部：IGP，比如RIP、OSPF、IS-IS等； （2）AS之间：EGP，最常用

10、的是BGP; （3）EGP通常是一种可达性协议。,要求： 1. 掌握RIP的特点及思想 2. 了解RIP路由信息时效性相关的三个定时器 3. 掌握RIP慢收敛问题的起因及对策 4. 了解RIP1中的额外跳问题 5. 掌握RIP2比RIP1扩展的内容,二、 选路信息协议RIP,（一） RIP的基本思想,(1)基于距离矢量算法 (2)每30秒广播一次报文 (3)与路由器直连的网络跳数设置为1 (4)路由器分为主动型和被动型。只有主动型广播。 (5)一条路由在180秒内无新通告，则变为无效路由 (6)跳数最大为15，16认为不可达 (7)基于UDP，端口520 (8)每跳路由有三个定时器 a. 更新

11、定时器30秒（广播路由） b.路由超时定时器180秒（超时未收到有关更新报文，则宣布路由无效）。 c.路由刷新定时器90秒（某路由超时后90秒，则将相应表项从存储空间中清除）。,RIP工作步骤及过程, 初始化:路由器启动时，对每个直接相连的网络生成一个表项，hop数都为0。 路由交换:路由器周期性向相邻路由器广播自己的整个路由表。(交换信息是) 路由表更新:路由器每收到一个邻站的路由表，即更新自己的路由表。(假设K收到J的路由表) (1) K不知道目的站，则加入 (2)有通过J的更短路，则替换 (3)原下站为J的距离有变化，则修改 .,仅和相邻交换、广播全部信息、定时 UDP发送,（二） RI

12、P1报文格式,说明： 常见命令： “1” = 请求路由信息， “2” = 响应路由请求。 首部后面最多有25个路由条目。若路由信息大于25，则广播多个RIP报文。 每个路由条目20字节，只利用10字节。 用目的地址0.0.0.0通告默认路由。,（三） RIP1的问题,R3：R2-R1 R2：R1 R1到网络1的连接断掉，则会造成选路环路。,1. 不能用于传播变长子网地址或CIDR型地址，因为RIP不广播掩码。 2. 慢收敛问题 网络收敛概念:所有路由器的信息应该是一致的。 收敛时间:网络中某个变化至所有路由器重新达到一致的时间。,a.分割单位更新(split horizon update)：不

13、把关于某路由的信息传回给发送者。 b.抑制法 (hold down)：当收到某网络不可达消息时，在规定时间内（如60秒），忽略任何关于该网络的路由信息。 c.毒性逆转 (poison reverse) :网络断连后，先保持该路由若干周期，但广播路由时置它的距离为无限远，要与触发更新(trigged update,)相结合来提高效率。 此即收到“坏消息”后立即广播=问题：可能会产生广播雪崩。,解决办法,3. 额外跳问题,（四） RIP2 的报文格式,扩展了哪些项? 1. 增加了子网掩码字段，支持VLSM、CIDR编址。 2. 增加了下一站地址，防止选路循环和慢收敛。 3. 增加了路由标记，可传送

14、自治系统号、路由起点等。 4. 增加了验证鉴别机制：占一个序偶的空间。,RIP2验证报文,（五） RIP的限制, 聚合慢：路由更改传播慢。 慢收敛：15 hops。 网络直径小 度量值只是跳数 没有负载均衡 说明：RIP并不是一个优秀的协议，出现较早，随着BSD UNIX流行起来，但是该协议简单，适用于小型网络。,三、 开放式最短路径优先OSPF,要求： 1掌握OSPF的特点； 2掌握OSPF区域划分的思想； 3 掌握OSPF路由汇总的方法； 4 掌握OSPF路由计算的方法； 5 掌握OSPF各种报文的功能。,（一） 回顾SPF思想,通过交换链路状态，让AS中的每个路由器都有一张该AS的网络拓

15、扑结构图。 使用Dijkstra算法求最短路径，计算该路由器到其它目的站的最短路径，然后更新路由表。 （1）优点 每个路由器使用相同的原始数据。 适合大规模的AS。,步骤, 检查直接相邻的路由器状态：周期性发测试报文，并按“n中取k”原则进行状态检查 。(p114) 路由器周期性广播它的各个链路状态。所有参与SPF的路由器负责转发收到的链路状态 。 收到链路状态的路由器更新自己的网络拓扑图，并计算最短路径 ，然后更新路由表。,（二） OSPF的发展,（1）1989.10 ，OSPF1（RFC1131） （2）1998.4， OSPF2（RFC2328） （3）1999.12，OSPF3（RFC

16、2740，用于IPv6）,OSPF的特点,（1）基于SPF，适用于大规模网络，最多可支持数千个路由器 （2）支持VLSM和CIDR （3）具有较强的健壮性和可扩展性 （4）不产生路由循环 （5）收敛速度快 （6）提供服务类型路由和负载均衡功能 （8）提供安全性,（三） OSPF中的区域（Area）,思想：减少参与链路状态交换的路由器群组规模 方法：多区域技术 （1）区域划分：把网络分成较小的块或区域，且只要求同一区域的路由器交换链路状态, 每个区域都有一个编号，每个AS都必须有Area 0 ，称为骨干区域 （2）若干概念 内部路由器：所有接口都在同一区域 如RT1，RT2，RT5，RT6，RT

17、8，RT9，RT12 区域边界路由器（ABR）: 接口属于不同的区域 如RT3，RT4，RT7，RT10，RT11 骨干路由器: 所有的ABR和骨干区域中的内部路由器 AS边界路由器（ASBR）：与其它AS相连 如RT5，RT7,Area 0,Area 1,Area 2,Area 3,Virtual Link,ABR,ABR,ABR,ABR,ABR,ASBR,ASBR,RT5,RT7,同一区域内的路由器交换所有的信息，而对同一 AS中其它区域的路由器隐藏它的详细拓扑结构 骨干区域可能不连续，但可通过定义虚链路实现 互通，如RT10与RT11 骨干区域在区域之间分发路由信息，非骨干区域 不能进行

18、直接的路由信息交互 规定区域内路由器个数200，但最好50 路由汇总采用CIDR技术,（3）说明,（四） OSPF-2报文首部（24字节）,报文类型 HELLO: 发现和维护邻居（测试可达性） 数据库描述: 初始化网络拓扑数据库 链路状态请求: 请求邻站传送链路状态信息 链路状态更新:（对请求的响应）广播链路状态 链路状态确认: 对更新报文的确认,源路由器所在区域,0：不鉴别 1：口令鉴别 OSPF-2支持MD5，还可扩充,OSPF工作过程,当一个路由器刚开始工作时，它只能通过问候分组（hello）得知有哪些相邻的路由器在工作，并确定可达性。 然后，OSPF让每一个路由器用数据库描述分组和相邻

19、路由器交换本数据库中已有的链路状态摘要信息，摘要信息主要指出哪些路由器的链路状态信息已写入数据库。经过与相邻路由器交换数据库描述分组，确定是否有不同链路状态信息。 接下来，路由器使用链路状态请求分组，向对方请求自己缺少的某些链路状态信息。对方通过链路状态更新分组传递链路状态信息。路由器发送链路状态确认信息。通过这系列分组交换，达到全网同步的链路状态数据库。 在网络运行过程中，只有当链路状态发生变化时，该路由器就使用链路状态更新分组，用洪泛法对全网更新。 为确保链路状态数据库与全网的状态保持一致，OSPF还规定，每各30分钟，要刷新一次数据库的链路状态。,1. HELLO报文,（1）发现和维护邻

20、居 a. 路由器R定期在所有接口上广播Hello报文 b. 相邻路由器S收到后，判断R是否在自己的相邻路由器列表中 若没有，则加入，并建立单向关系（S知道，但R还不知道） c. S定期向所有接口广播Hello报文，包含了自己知道的所有邻居 d. R发现自己是S的邻居，则双向关系建立 e. 如果在一段时间内没有收到某个邻居的广播，则邻居关系解除,作用： 发现和维护邻居，检测链路是否可用 选举指定路由器和后备指定路由器 建立邻接关系（双向连通性）,（2）报文格式, 优先级: 选举指定路由器和后备指定路由器，通常优先级高的当选(相同时选IP地址比较大的)，且一经当选，不轻易更换,建立邻居关系的条件

21、(1) 位于相同的区域 (2) 通过安全认证 (3) 相同的Hello和死亡间隔, HELLO间隔(10s): 组播间隔 路由器死亡间隔(Hello的4倍) ：40s内未收到某邻居的Hello报文，邻居关系解除 邻站IP地址: 发送方最近收到Hello报文的所有邻站, 指定路由器（DR）,后备指定路由器: DR的接班人（防止DR失效）,若R1为DR，则只有R1对外发一个网络LSA，通告该处链路状态,在一个连接有多个路由器的网络上，指定其中一个路由器负责向外发送该网络中所有链路状态信息,2. 数据库描述报文：交换协议,若干个LSA首部, 数据库序号：描述报文可能有多个，需编序,序号、I、M结合，

22、 作用类似分片控制, 作用：相邻路由器建立连通性后交换信息来初始化网络拓扑数据库（数据库同步）（该数据库称LSDB：Link State DataBase，存放各种LSA）,3、链路状态请求报文 对没有链路状态记录内容的链路或信息过时的链路，请求邻站发送更新信息,4、链路状态更新报文 定期(至少30分钟)组播链路状态记录内容，以“维护”网络拓扑数据库 对链路状态请求的响应,LSA的个数,类型为3的OSPF首部,类型为4的OSPF首部,5、链路状态确认报文 对链路状态更新报文的确认 发回收到的LSA的首部来确认,6、核心内容：链路状态通告LSA （Link State Advertisement

23、）,（1）首部：20字节, 链路状态序号：使得接收方可以判断收到的对某条链路的描述是否是最新的(一条链路的状态会变化，描述会多次出现，每次赋予不同序号) 链路状态年龄：该LSA产生后经历的秒数 （MaxAge=3600s，此时删除）, 链路状态类型和链路状态ID： 指示LSA的格式与功能,类型1：路由器链路 本区域内如右图所示的链路 路由器R1通告它的所有接口状态,类型2：网络链路 本区域内如左图所示的多点接入网 由指定路由器DR通告该组路由器,类型3：Summary链路（到网络） ABR产生的所连区域内到网络的汇总链路，向骨干通告 骨干区汇总后的到网络的链路，向非骨干区域通告,汇总后,隐藏细

24、节,类型4：Summary链路（到ASBR） ABR产生的到ASBR的汇总链路（类似于类型3）,类型5：外部链路 ASBR通告的到外部系统的链路,同一区域的路由器保持相同的LSDB 包含三方面内容： 本区路由器发出的类型1和类型2的LSA 发自本区ABR的属于骨干区和其它区的类型3和类型4的LSA 发自ASBR的外部LSA（不改变）,Area 0,Area 1,Area 2,Area 3,Virtual Link,ABR,ABR,ABR,ABR,ABR,ASBR,ASBR,RT5,RT7, LSA格式示例, ,LSA首部,Link ID,类型=1,Link Data,如：路由器LSA格式,描述

25、一个Link,有多个ToS时，每个特殊的ToS一项,（路由器的身份） V：Virtual Link E：ASBR B：ABR,Type Description Link ID Link Data 1 Point to point link Neighbor Router ID Interface IP Address 2 Link to a transit network Interface address of DR Interface IP Address 3 Link to a stub network IP network number IP Address mask 4 Virtua

26、l link Neighbor Router ID Interface IP Address,10,1,3,202.196.48.0/24,设R1 是ABR， R1的三个接口： 左：203.19.2.1 右：202.196.48.1 下：198.22.5.1,203.19.2.2/24,198.22.5.2/24（DR）,如：网络LSA格式,由网络掩码和LSA首部中的链路状态ID（DR的接口IP地址）可推出网络号 202.196.48.0,202.196.48.0/20,202.196.48.1,（DR）,DR发出的网络LSA,（五） OSPF路由计算,1、域内路由计算： 运行SPF算法 2、

27、域间路由计算 一个域内的ABR（设为R1）首先产生汇总路由，通告给其它ABR ABR收到这个通告后，在本地路由表中生成新的路由条目，下一跳指向R1，之后把这些信息传递给其它IR 3、AS外部路由计算 ASBR把其它AS的路由扩散到末梢区域外的所有区域 路由器收到ASBR的通告后，把这些路由条目作为ASBR的叶子，添加到以自己为根的最小生成树中 依据最小生成树生成路由表,（六） 说明,1、OSPF-2与OSPF-1相比 路由器地址统一改为路由器ID（为每个路由器唯一分配） 鉴别支持MD5，可进一步扩充 报文中增加了选项字段，携带的信息量增加，控制能力增强 2、 OSPF-3与OSPF-2相比 原

28、理同OSPF-2，用于IPv6 功能更强，通用性和扩展性更好 基本抛弃IP地址概念，侧重于说明拓扑结构 去掉了鉴别功能（由IPv6来保障） 3、接口有限自动机 邻居有限自动机,1、RIP简单（20多页），但限制多，只适用于小网 OSPF复杂（244页），但功能强大，适用于大网 2、RIP基于UDP，OSPF基于IP 3、其它IGP协议 向量距离类：Cisco的IGRP 和EIGRP(增强IGRP),（七） 关于IGP的说明, 链路状态类：ISO的IS-IS协议,跳数可达255，度量是跳数、延迟、带宽、可靠性、负载的复合值,三种定时器时限：90s、270s、630s,结合了RIP、OSPF的优点

29、和分布式更新算法DUAL。 可与OSPF抗衡,EIGRP(增强IGRP),四 边界网关协议BGP,要求： 1掌握BGP的原理和流程； 2理解RIB的三个子库； 3 了解BGP的状态机； 4 掌握BGP报文的分类及各个报文的功能；,（一）BGP概述,BGP在成长过程中经历了4个版本，bgp-1 到bgp-4，他们之中，仅有bgp-4支持CIDR.BGP-4 于1995年发布。 BGP基于TCP,使用端口为179.不需考虑报文的延迟、乱序、丢失等可靠性问题。,通过相邻的AS之间交换路由信息，使得每个AS都拥有一个AS级的Internet联通图。 两个相邻的AS之间交换路由信息时，要选择相邻的BGP

30、路由作为发言人。每个发言人向外通告经过聚类后的可达性路由信息。以隐藏网络拓扑结构。 路由信息可以是AS内部的，也可以是来自其它AS 。 信息格式：,BGP的原理,AS400的BGP路由表信息 10.1.0.0/24 AS500，300，100 10.1.1.0/24 AS500，300， 200 10.2.1.0/24 AS500，300 10.4.1.0/24 AS500 10.5.1.0/24 AS500，600,AS600的BGP路由表信息 10.1.0.0/24 AS500，300，100 10.1.1.0/24 AS500，300， 200 10.2.1.0/24 AS500，300

31、 10.3.1.0/24 AS500，400 10.5.1.0/24 AS500,1、当一个AS的BGP发言人希望与另一个AS的BGP发言人通讯时，先使用三次握手建立TCP连接。 2. 之后，一个AS发言人发送OPEN，另一个回应KEEPALIVE，建立 BGP邻居关系；两位发言人成为对等实体。 3. 对等实体间用UPDATE报文交换完整的RIB（路由信息库）； 4. 随后使用UPDATE报文进行增量更新；仅通过发生变化的信息。 5. 使用KEEPALIVE报文报告活动性，维护邻居关系； 6. 上述过程如果发生错误，使用NOTICATION报文向对方报告。,协议流程,报文类型： 1 OPEN 2 UPDATE 3 NOTIFICATION 4 KEEPALIVE,BGP的路由信息存储在RIB中. RIB分为三