第4章6h 路由选择协议.ppt

1、1,第4章 路由选择协议,2,主要内容,路由器的基本概念 路由选择技术 分类寻址路由表 无分类域间路由选择（CIDR） 内部和外部路由协议,3,所谓路由就是指通过相互连接的网络把信息从源地点移动到目标地点的活动。一般来说，在路由过程中，信息至少会经过一个或多个中间节点。,（N,R1,M）,R1,目标网络N,其它网络,路由器基本概念,4,路由表（routing table，也称路径表）： 路由表用于保存各种传输路径的相关数据（路由信息）供数据转发（路由选择）时使用。 路由表中保存着子网的标志信息、网上路由器的个数和下一个路由器的名字等内容。 路由表主要分为两种：静态路由表、动态路由表。,5,1静

2、态路由表：由系统管理员事先设置好固定的路由表称之为静态（static）路由表，一般是在系统安装时就根据网络的配置情况预先设定的，它不会随未来网络结构的改变而改变。,2动态路由表：动态（Dynamic）路由表是路由器根据网络系统的运行情况而自动调整的路径表。路由器根据路由选择协议（Routing Protocol）提供的功能，自动学习和记忆网络运行情况，在需要时自动计算数据传输的最佳路径。,6,静态路由和动态路由的区别,静态路由：是在路由器中设置的固定的路由表，除非网络管理员干预，否则不会发生变化。不能对网络的改变作出反映，一般用于网络规模不大、拓扑结构固定的网络中。 静态路由的优点是简单、高效

3、、可靠。 在所有的路由中，静态路由优先级最高。当动态路由与静态路由发生冲突时，以静态路由为准。,动态路由：网络中的路由器之间相互通信，传递路由信息，利用收到的路由信息更新路由表的过程。 动态路由的优点是能实时地适应网络结构的变化。如果发生了网络变化，就会引起网络中所有路由器重新计算路由，更新各自的路由表以动态地反映网络拓扑变化。 动态路由适用于网络规模大、网络拓扑复杂的网络。当然，各种动态路由协议会不同程度地占用网络带宽和CPU资源。,7,路由选择技术： 就是寻找一条将IP分组从源站传输到目的站的最佳路径的技术，而传输路径往往由一系列路由器组成。 一次交付： IP分组在网络中的一次传递过程。

4、根据一次交付的对象是否是IP分组的目的站，交付方式分为： 直接交付：就是分组的最终目的站与交付者(一般指源站主机或路由器)在同一个网络上实现的交付方式。 间接交付：指分组不能直接到达目的站主机，而只能通过中间的路由器进行转发。一般地，主机到路由器、路由器到路由器的交付就是间接交付。 51页图4-1,4.1 路由选择技术,8,9,标准的路由表举例,10,下一跳路由选择 特定网络路由选择 默认路由选择 特定主机路由选择,构成路由表常用技术,11,4.1.1 下一跳路由选择,在路由表中并不需要保留从源站到目的站的完整路由，而只需要保留转发的下一个路由器地址。 通过各路由表之间的彼此协作，实现IP分组

5、转发的完整路由。,12,针对课本p51页图4-1的例子，下图给出基于下一跳路由选择的各路由器中的路由表的例子。,R2的路由表,R6的路由表,R4的路由表,13,14,4.1.2 特定网络路由选择,在路由表中并不需要为每一个目的站主机保留一个路由表项，而只需对目的网络保留一个路由表项。 减小路由表的大小，简化路由表的查找过程。,15,下图：特定网络路由选择,R2的路由表,R6的路由表,R4的路由表,16,17,4.1.3 默认路由选择,在主机的路由表中可以不必列出整个互联网中所有网络的路由表项，仅需使用一个网络地址为0.0.0.0的默认路由表项表示这些剩余的互联网路由表项。,图：主机A的路由表,

6、18,4.1.4 特定主机路由选择,对单个主机（而不是网络）指定一条特别的路径。在特定主机路由选择中，路由表中给出的是主机的路由表项，而不是目标网络的路由表项。 在检查路由或提供安全措施等的一些特殊情况下，特定主机路由选择就是一种很好的选择。,19,4.2 分类寻址路由表,路由表表项 路由选择流程,20,4.2.1 路由表表项,路由表结构:,路由表中每一行称为一个路由表项，对应一条到目的网络的路由。,21,Windows 路由表,22,路由器中的路由表,在特定主机路由选择中，掩码是255.255.255.255 在默认路由选择中，掩码是0.0.0.0 在不划分子网的网络中，A、B、C类地址的掩

7、码分别是255.0.0.0, 255.255.0.0, 255.255.255.0,23,4.2.2 路由选择流程,从被转发的IP分组首部中提取目的IP地址D。 判断直接交付路由表项。否则就是间接交付，执行3)。 判断特定主机路由表项。若路由表中有目的地址为D的特定主机地址，则将分组传送给该路由表项所指明的下一跳地址，完成分组转发；否则，执行4)。 判断特定网络路由表项。对每一条路由表项：用子网掩码和D逐比特相“与”，若结果与本路由表项中的目的网络地址相同，则将分组传送给该路由表项指明的下一跳地址，完成分组转发；否则，执行5)。 判断默认路由表项。若路由表中有一个默认路由表项，则将分组传送给该

8、路由表项指明的下一跳地址，完成分组转发；否则，执行6)。 报告转发分组出错。,24,4.3 无分类域间路由选择（CIDR）,无分类域间路由选择(CIDR,Classless Inter-Domain Routing)也称为超网(Supernetting)，在RFC1518和RFC1519中进行了具体描述，使防止因特网路由表膨胀的另一种方法。 CIDR的基本思想是：适当分配多个合适的IP地址，使得这些地址能够进行聚合，减少这些地址在路由表中的表项数。 采用CIDR技术可以减缓因特网路由表的增长，但对于现存的路由选择没有任何帮助。,无分类域间路由选择最主要的特点有两个： （1）CIDR消除了传统的

9、A类、B类和C类地址以及划分子网的概 念， 因而可以更加有效地分配IPv4地址空间，并且可以在新的IPv6使用之前容许因特网的规模继续增长。它的记法是： IP地址：,CIDR使用“斜线记法”（slash notation）或CIDR记法，它在IP地址后面加上一个斜线“”，然后写上网络前缀所占的比特数（这个数值对应于三级编址中子网掩码中比特1的个数）。例如: 128.14.46.3420,（2）CIDR将网络前缀都相同的连续的IP地址组成“CIDR地址块”。一个CIDR地址块是由地址块的起始地址（即地址块中地址数值最小的一个）和地址块中的地址数来定义的。这样，地址块也可用斜线记法来表示。,例如，

10、128.14.32.020表示的地址块共有 个地址（因为斜线后面的20是网络前缀的比特数，所以主机号的比特数是12，因而地址数就是 ），而该地址块的起始地址是128.14.32.0。,由于一个CIDR地址块可以表示很多地址，所以在路由表中就利用CIDR地址块来查找目的网络。这种地址的聚合常称为路由聚合（rout aggregation），它使得路由表中的一个项目可以表示很多个（例如上千个）原来传统分类地址的路由。路由聚合也称为构成超网(supernetting）。,28,地址聚合的步骤： 首先把点分十进制表示的网络地址转换成二进制形式； 提取出地址中的相同部分(网络部分)，对剩余不同部分按位数

11、的全排列进行划分，得到多块地址。 对每一块地址聚合成一个地址。掩码值的计算：其中地址的相同部分其掩码中对应的位为1，其余位为0。,29,举例:把下面的4个C类网络地址，实现地址聚合。 200.41.24.0 200.41.25.0 200.41.26.0 200.41.27.0,30,31,地址聚合必须满足的3个特性： 多个IP地址进行聚合时，必须具有相同的高位地址。 路由表和路由选择算法基于32bit的IP地址和32bit的掩码。 路由协议要支持32bit掩码的传输，如动态路由协议OSPF和RIP-2都能够携带32bit的掩码。,32,因特网采用分层次的路由选择协议。 因特网的规模非常大。如

12、果让所有的路由器知道所有的网络应怎样到达，则这种路由表将非常大，处理起来也太花时间。而所有这些路由器之间交换路由信息所需的带宽就会使因特网的通信链路饱和。 许多单位不愿意外界了解自己单位网络的布局细节和本部门所采用的路由选择协议，但同时还希望连接到因特网上。 因特网将整个互联网划分为许多较小的自治系统 AS (Autonomous System)。,4.4 内部和外部路由协议,33,一个自治系统AS通常代表一个独立的组织机构，同时，一个AS是由若干个路由器组成的一个互联网络，并由本组织机构内的管理员进行管理，有权决定在本AS内所采用的路由选择协议。 实现“自治” 每个自治系统有一个16bit的

13、标识符。可用的AS标识符有限，所以一个机构要想获得AS标识符必须要有充分的理由。,34,IGP和EGP,内部网关协议IGP (Interior Gateway Protocol)即在一个自治系统内部使用的路由选择协议。目前这类路由选择协议使用最多的，如 RIP和OSPF协议。 外部网关协议EGP (External Gateway Protocol)：在AS之间使用的路由选择协议。若源站和目的站处在不同的自治系统中，当数据报传到一个自治系统的边界时，就需要使用一种协议将路由选择信息传递到另一个自治系统中。这样的协议就是外部网关协议 EGP。在外部网关协议中目前使用最多的是 BGP-4。,因特网

14、通过划分自治系统，把路由选择协议划分为两大类：,35,图4-10 互联网的路由协议关系,36,路由选择协议的概念：是一些规则和过程的组合，它使得路由器能够共享它们所知道的互联网情况或邻站情况。 路由选择协议的工作：就是依据一定的度量找到一条最佳的分组传送路径。,4.4.1 理想的路由选择算法,37,1.度量(metric)：就是给通过某个网络所指派的代价。表征路径优劣的数值。度量越小，说明路径越好。 度量的计算可以基于路径的一个特征，也可以基于路径的多个特征 跳数(hop count)：IP数据报到达目的地必须经过的路由器个数 带宽(bandwidth)：链路的数据能力 延迟(delay)：将

15、数据从源送到目的地所需的时间 负载(load)：网络中(如路由器中或链路中)信息流的活动数量 可靠性(reliability)：数据传输过程中的差错率 开销(cost)：一个变化的数值，通常可以根据带宽、建设费用、维护费用、使用费用等因素由网络管理员指定,38,2、理想路由选择算法的特点 正确性和完整性 简单性：路由选择的计算不应使网络通信量增加太多的额外开销。 自适应性：算法能适应网络通信量和网络拓扑的变化。 稳定性：在通信量和网络拓扑相对稳定的情况下，路由算法应该收敛于一个可以接受的解，而不应使路由不停的变化。 公平性：除少数优先级高的用户，算法应对所有用户都是平等的。 最佳性：以最低的代

16、价来实现路由算法。,39,路由信息协议RIP（Routing Information Protocol）是一个基于距离向量路由选择的协议。是在同一个自治系统内路由器之间传送路由的最常用协议。目前RIP有两个版本RIPv1和RIPv2。 RIP有两种工作模式 主机采用被动（passive）模式，只接收RIP消息 不会传递自己的路由表中的信息给别的路由器，只是静静地倾听其它RIP路由器广播的路由信息，并且根据收到的路由信息更新自己的路由表。 路由器采用主动（active）模式，发送和接收RIP消息 定期把路由信息传递给其它RIP路由器，并且根据收到的RIP消息来更新自己的路由表。,4.4.2 路由

17、信息协议(RIP),40,距离-向量路由选择算法的基本思想,路由器周期性地向其相邻路由器广播自己知道的路由信息，用于通知相邻路由器自己可以到达的网络以及到达该网络的距离，相邻路由器可以根据收到的路由信息修刷新自己的路由表。,41,“距离”的定义： RIP 协议中的“距离”也称为“跳数”(hop count)，因为每经过一个路由器，跳数就加 1。 从一路由器到直接连接的网络的距离定义为 1。 RIP 认为一个好的路由就是它通过的路由器的数目少，即“距离短”。 RIP 允许一条路径最多只能包含 15 个路由器。 “距离”的最大值为16 时即相当于不可达。可见 RIP 只适用于小型互联网。 RIP

18、不能在两个网络之间同时使用多条路由。RIP 选择一个具有最少路由器的路由（即最短路由），哪怕还存在另一条高速(低时延)但路由器较多的路由。,RIP协议工作原理,42,RIP 协议的三个要点： 仅和邻站路由器交换信息。 （邻站路由器是与其直接相连的所有路由器） 交换的信息是当前本路由器所知道的全部信息，即自己的路由表。 按固定的时间间隔交换路由信息，通常每隔30秒向邻站路由器广播自己的路由表。接到广播的路由器将收到的信息添加至自身的路由表中。每个路由器都如此广播，最终网络上所有的路由器都会得知全部的路由信息。 RIP消息通过广播地址255.255.255.255进行发送，使用UDP 协议的520

19、端口。,43,路由表的建立： 路由器在刚刚开始工作时，只知道到直接连接的网络的距离（此距离定义为1）。 以后每一个路由器只和相邻路由器交换并更新路由信息。 经过若干次更新后，所有的路由器最终都会知道到达本自治系统中任何一个网络的最短距离和下一跳路由器的地址。 RIP 协议的收敛(convergence)过程较快，即在自治系统中所有的结点都得到正确的路由选择信息的过程。,44,RIP路由更新算法,路由器收到其他路由器广播的路由信息后，刷新自己的路由表（假设Ri收到Rj的路由信息报文） 1）Rj列出的某表目Ri中没有： Ri须增加相应表目，其“目的网络”是Rj表目中的“目的网络”，其“距离”为Rj

20、表目中的距离加1，而“路径”为Rj 2)Rj去往某目的地的距离比Ri去往该目的地的距离减1还小： Ri修改本表目，其“目的网络”不变，“距离”为Rj表目中的距离加1，“路径”为Rj 3)Ri去往某目的地经过Rj，而Rj去往该目的地的路径发生变化Rj不再包含去往某目的地的路径： Ri中相应路径须删除 Rj去往某目的地的距离发生变化： Ri中相应表目的“距离”须修改，Rj中的“距离”加1取而代之,45,一个互联网拓扑,46,初始状态路由表,47,邻站A来的路由表,邻站C来的路由表,邻站E来的路由表,路由器B路由表的更新,48,各路由器的最终路由表,49,RIP实现过程中的3个计时器： 定期计时器：

21、用于控制定期发送更新报文。通常间隔为25-35之间的一个随机数。定时器向下计数，到达0时就发送更新报文。 截止期计时器：用来管理路由的有效性，每一条路由表项有它自己的截止期。设置为180s。 无效信息计时器：用来管理无效的路由表项，每一条路由表项有它自己的无效信息计时器。设置为120s。,50,RIP的特点,RIP协议适用于小型网络。 RIP协议是基于距离向量路由选择的协议。不能保证所选择的是最快的路径。 RIP协议定期更新路由表。 RIPv1协议是一个有类别路由协议，在RIP v1报文中不传送掩码地址。 RIPv2协议是一个无类别路由协议。,51,RIP v1报文格式,每个报文由一个命令标识

22、、一个版本号和最大25条的路由条目构成。 每个路由条目包括地址族标识、路由可达的IP地址和路由度量（跳数）。,52,命令：取值1表示请求报文，取值2表示响应报文。 版本：取值1表示RIP-1，取值2表示RIP-2 。,地址族标识：表示地址族。对于IP，该字段值为2.若报文是对路由器整个路由表的请求时，字段值设置0。,53,RIP报文封装（图不完全正确）,54,RIP协议的局限性,增加一个网络Net1,55,删除一个网络Net1,56,RIP协议的局限性,RIP特点：增加一个新网络的好消息传播较快，对删除一个故障网络的坏消息传播很慢。 改正措施： 若网络没有变化，则按通常的30s间隔发送更新报文

23、，一旦有变化，路由器立即发送更新报文。 发送路由更新报文时候，路由器必须区分不同的接口。如果路由器从某个接口已经收到了路由更新报文，则同样的更新报文不能再通过这个接口回送过去。,57,RIP2 是在RIP1的基础上增加了一些扩展特性，以适用于现代网络的路由选择环境。 扩展特性： 1）无类别路由协议。路由条目带子网掩码，所以RIP2可以使用可变长的子网掩码。 2）多播方式更新路由。多播地址是224.0.0.9,RIPv2协议,58,RIPv2报文格式,59,报文中的路由部分由若干个路由信息组成。每个路由信息需要用 20 个字节。 地址族标识符(又称为地址类别)字段用来标志所使用的地址协议。 路由

24、标记填入自治系统的号码，这是考虑使RIP 有可能收到本自治系统以外的路由选择信息。 下一跳：标识一个比通告路由器的地址更好的下一跳地址。即，他指出的下一跳的度量值比在同一个子网上的通告路由器更靠近的目的站。,60,80年代中期，RIP已不能适应大规模异构网络的互连，OSPF随之产生。它是网络工程任务组(IETF)的内部网关协议工作组为IP网络而开发的一种路由协议。 OSPF是一种基于开放标准的链路状态的路由选择协议，每个路由器向其同一管理域的所有其它路由器发送链路状态广播信息。在OSPF的链路状态广播中包括所有接口信息、所有的量度和其它一些变量。 “开放”是指最短路径优先协议不受厂商的限制。

25、“最短路径优先”是指使用了Dijkstra提出的最短路径算法SPF.,4.4.3 开放最短路径优先协议 (OSPF),61,区域是自治系统中网络、主机和路由器的一个集合。 与RIP不同，OSPF将一个自治域再划分为区域，相应地即有两种类型的路由选择方式： 当源和目的地在同一区时，采用区内路由选择； 当源和目的地在不同区时，则采用区间路由选择。这就大大减少了网络开销，并增加了网络的稳定性。,62,自治系统中划分区域,一个自治系统可以划分为多个区域，每个区域由一个区域标识。其中有一个特殊的区域称作主干，区域标识为0，其余所有区域必须连接到主干区域上。,63,OSPF分层的路由,由区域组成 路由更新

26、流量很少,64,OSPF的路由 区域内 区域间,OSPF的路由器 区域内部路由器: 所有接口包含在一个单个的OSPF区域中 区域边界路由器：处在一个区域的边界，把有关本区域的信息汇总起来发给其他区域 主干路由器：在主干区域中的路由器叫主干路由器，一个主干路由器至少有一个接口与区域0相连 自治系统边界路由器：位于运行OSPF协议和其他路由选择协议的两个自治系统的边界上，可以配置ASBR实现非OSPF路由通告到OSPF自治系统中的所有区域,从源端到主干 从主干到目的区域 从目的区域到目的端,在每个区域内至少有一个区域边界路由器将本区域连向主干区域。 每个区域边界路由器维护若干个链路状态数据库。,6

27、5,链路状态路由选择,链路状态路由选择的基本思想：每一个路由器拥有互联网（一个区域范围内）在每一时刻的准确拓扑图，根据拓扑图，路由器计算出到每一个网络的最短路径，即最佳路由。 基本步骤： 发现它的邻站，并知道其网络地址。 测量它到各个邻站的成本，即得到它和各个邻站之间的链路状态。 将测量到的链路状态信息组装成一个分组，发送到区域内所有的路由器(洪泛法) 每个路由器收到区域内所有路由器与其相邻站的有关链路状态信息的分组，构建链路状态数据库，得到本区域的网络拓扑结构。 根据链路状态数据库，采用最短路径优先算法（Dijkstra算法），计算它到区域内其他路由器的最短路径。,66,在链路状态路由选择中

28、，OSPF协议使用了3个数据库： （1）邻站数据库(即邻接表)：对于OSPF路由器要知道哪些是与它直接相连的邻站。 （2）链路状态数据库(即网络拓扑图)：一个区域内的每个路由器从所有其他路由器接受链路状态通告，构成一个链路状态数据库。 （3）转发数据库(即路由表)：采用链路状态数据库形成路由表。,67,OSPF的特点,公开发布了各种规范。它是一个开放标准。 支持服务类型路由。 易于网络扩展和管理。而且降低了协议运行的网络通信量。 提供负载均衡功能。 提供鉴别功能。 支持多播。多播目的地址224.0.0.5用于所有的OSPF路由器，224.0.0.6用于指定路由器/备份指定路由器。 属于无类别路

29、由选择协议。支持变长子网掩码(VLSM)。,68,OSPF协议报文的类型,问候（Hello）报文: OSPF协议周期性地在链路上发送问候报文，以便创建邻站关系，测试邻站的可达性。 数据库描述报文（DBD）：路由器通过交换OSPF数据库描述报文来初始化链路状态数据库。数据库描述报文中只包含链路状态数据库中每一条链路的概要信息，并不包含完整的链路状态信息。 链路状态请求报文(LSR):请求相邻路由器发送其链路状态数据库中的特定项（你有我没有）。 链路状态更新报文（LSU):向邻居路由器发送路由器的链路状态通告，是OSPF的核心。 链路状态确认报文(LSAck):确认收到邻居路由器的LSA,69,O

30、SPF报文传输流程,(2),数据库描述报文,(3),链路状态请求报文,(4),链路状态更新报文,(5),链路状态确认报文,路由器A(主),路由器B(从),70,OSPF报文被封装在IP分组中进行传送，并且数据报文较短。,71, OSPF报文的公共首部格式,版本（Version）:占8bit，定义OSPF协议版本。目前是版本2 类型: 占8bit，定义报文类型，分别用1-5对应5种类型。,OSPF报文公共首部,报文长度:占16bit，定义包含首部在内的报文的总长度。,72, OSPF报文首部格式,区域标识符:占32bit，定义所属区域。 校验和：占16bit，对整个报文进行差错校验，但不包括鉴别

31、类型和鉴别数据两个字段。,OSPF报文首部格式,源路由器IP地址:占32bit，定义发送此报文的路由器的IP地址。,73, OSPF报文首部格式,鉴别类型:占16 bit，定义区域所用的鉴别方法。0表示没有鉴别，1表示口令。 鉴别数据：占64 bit，表示鉴别数据值。鉴别类型为0时，字段值为0；鉴别类型为1时，字段值是8个字符的口令。,OSPF报文首部格式,74,问候报文格式,75,数据库描述报文,76,链路状态请求报文,77,链路状态更新报文,78,链路状态通告的首部格式,取决于链路类型。1是 路由器的IP地址；2是指定路由器的IP地址；3是网络的IP地址；4是自治系统边界路由器的IP地址；

32、5外部网络的IP地址。,79,链路状态确认报文,80,4.4.4 边界网关协议BGP,边界网关协议（Border Gateway Protocol，简称BGP）是自治系统之间的路由选择协议。不使用路由度量值，而是根据网络策略来做路由决定的。 BGP的任务是在自治系统之间交换路由信息，同时确保无环路的路径选择。 BGP实现基于路径向量的路由选择。,81,路径向量路由选择,距离向量路由选择基于最小距离的选择路由，只有跳数，没有确定路径，不适合用在边界网关协议中。 链路状态路由选择不适合自治系统之间的路由选择。（？） 路径向量路由选择的路由表中除了包含目的网络、下一跳路由器外，还包括到达目的站的路径。路径向量路由选择中，各自治系统的自治边界路由器通告在其自治系统中的网络到各相邻自治边界路由器的可达性。 路径定义了分组要到达终点所必须经过的自治系统的有序表。,82,BGP工作原理,在一个BGP网络中有四种不同类型的路由器： BGP发言者路由器：