第十五讲路由选择协议

1、第 15 次 课 4 学 时 ）一、授课 题目 路由 协 议二、教学目的和要求了解分层路由选择协议，掌握 RIP算法。KEY：IGP、EGP、RIP三、教学重点和难点重点：最短距离算法、报文格式难点：最短距离算法四、教学过程（包含教学内容、教学方法、辅助手段、板书、学时分 配等）课堂讲授五、作业六、主要参考资料 计算机网络原理七、课后记第十五讲路由选择协议一、路由协议的基本概念1. 理想的路由算法正确和完整性：“正确”指能到达目的网络和主机，“完整”指所有真实存在的网络和主机。简单性：不应使网络通信量增加太多的额外开销，且处理延时尽可能小。自适应性：“适应通信量变化”指算法可以实现链路均衡；“

2、适应拓扑变化”指算法可以 及时改变路由。稳定性：通信量、拓扑稳定，算法的解是稳定的。公平性：对所有用户公平，除非特例。最佳性：平均时延最小，吞吐量最大。两点说明：（1） 最佳路由问题：“最佳”的衡量标准，依环境不同而不同。（2）路由算法的适应性静态路由选择策略一一非自适应，特点是简单和开销较小，但不能及时适应网络状态的 变化。动态路由选择策略 自适应，特点是能较好地适应网络状态的变化，但实现起来较为复杂，开销也比较大。2、分层次路由选择协议（1）分层次选择的原因：一是因特网太大，导致路由表过大，处理时延大；二是网络 布局与内部协议的保密性。（2）自治系统 AS（ auto no mous sy

3、stem）: 一种由一个管理实体管理，采用统一的内部选路协议的一组网络所组成的大范围的IP网络。（3）AS路由协议的分类内部网关协议 IGP （Interior Gateway Protocol） : RIP、OSPF外部网关协议 EGP （External Gateway Protocol）： BGP（Border Gateway Protocol）二、RIP（Routing Information Protocol）1、工作原理（1）距离向量从一路由器到直接连接的网络的距离定义为1。从一个路由器到非直接连接的网络的距离定义为所经过的路由器数加1。RIP协议中的“距离”也称为“跳数 ” （h

4、op count）因为每经过一个路由器，跳数就加1。（2）路由表的建立路由器在刚刚开始工作时，只知道到直接连接的网络的距离（此距离定义为1）。以后，每一个路由器也只和数目非常有限的相邻路由器交换并更新路由信息。经过若干次更新后， 所有的路由器最终都会知道到达本自治系统中任何一个网络的最短距离和下一跳路由器的 地址。RIP协议的收敛（con verge nee）过程较快，即在自治系统中所有的结点都得到正确的路由 选择信息的过程。（3）RIP特点一条路径最多只能包含15个路由器，距离”的最大值为16时即相当于不可达。RIP不能在两个网络之间同时使用多条路由。若有多条链路，RIP只选择一个具有最少

5、路由器的路由（即最短路由），哪怕还存在另一条高速（低时延）但路由器较多的路由。仅和相邻路由器交换信息。交换的信息是当前本路由器所知道的全部信息，即自己的路由表。按固定的时间间隔交换路由信息，例如，每隔30秒。2、距离向量算法收到相邻路由器（其地址为X）的一个RIP报文：（1）先修改此 RIP报文中的所有项目：把“下一跳”字段中的地址都改为X,并把所有的“距离”字段的值加1。（2）对修改后的 RIP报文中的每一个项目，重复以下步骤：若项目中的目的网络不在路由表中，则把该项目加到路由表中。否则（即在路由表中有目的网络 N这时就再看下一跳的路由器地址）若下一跳字段给出的路由器地址是同样的，则把收到的

6、项目替换原路由表中的项目。/*原有通过X到达N的跳数，变为现在通过X到达N的跳线*/否则（即原有的到N的下一跳不是通过X，而是通过别的路由器，则要比较这 两条路，看谁最优）若收到项目中的距离小于路由表中的距离，则进行更新。 否则，什么也不做。（3）若3分钟还没有收到相邻路由器的更新路由表，则把此相邻路由器记为不可达路 由器，即将距离置为 16 （距离为16表示不可达）。返回。3、RIPv2报文格式命令：报文的意义，例，1表示请求路由信息，2表示对请求路由信息的响应或未请求 而发出的路由更新报文。版本：即RIP版本号。地址标识符（网络层地址的类别）：例，2表示IP地址，其他值为其他协议地址。路由

7、标记：自治系统号 ASNo注：一个RIP报文，最多可携带 25条路由信息，每条路由信息长度为20字节。则RIP最大报文长度为504字节。4、RIP优缺点RIP存在的一个问题是当网络出现故障时，要经过比较长的时间才能将此信息传送到所有的路由器（好消息传播快，坏消息传播慢）。优点：实现简单，开销较小。缺点：（1）限制网络规模，最大距离为 15（ 16表示不可达）。（2）交换的路由信息是 路由器中的完整路由表，因而随着网络规模的扩大，开销也就增加。（3）坏消息传播慢，导致收敛时间过长。5、RIP安全性攻击者可以伪造 RIP数据包，宣称其主机“熾有最快的连接网络外部的路径。然后， 所有需要从那个网络发

8、出的数据包都会经X转发，而在 X中，这些数据包既可以被检查，也可以被修改。攻击者也可以使用RIP来有效地模仿任何主机，使得所有应该发送到那台主机的通信都被发送到攻击者的计算机中。win2003中的防范：启用身份验证；对等安全性设置（规定接收RIP公告的路由器）；启用路由筛选器（只接符合规则的路由器发来的RIP）。三、OSPF（ Open Shortest Path First）1、OSPF协议特点（1） 适应范围：OSPF支持各种规模的网络，最多可支持几百台路由器。（2） 快速收敛：如果网络的拓扑结构发生变化，OSPF立即发送更新报文，使这一变化在自治系统中同步。（3 ）无自环： 由于OSPF

9、通过收集到的链路状态用最短路径树算法计算路由，故从 算法本身保证了不会生成自环路由。（4）子网掩码 ： 支持VLSM和CIDR（5） 区域划分：OSPF协议允许自治系统的网络被划分成区域来管理，区域间传送的 路由信息被进一步抽象，从而减少了占用网络的带宽。（6）等值路由：OSPF支持到同一目的地址的多条等值路由。（7） 路由分级：OSPF使用4类不同的路由，按优先顺序来说分别是：区域内路由、 区域间路由、第一类外部路由、第二类外部路由。（8）支持验证：它支持基于接口的报文验证以保证路由计算的安全性。（9）组播发送：OSPF在有组播发送能力的链路层上以组播地址发送协议报文，即达 到了广播的作用，

10、又最大程度的减少了对其他网络设备的干扰。2、基本概念（1）链路状态链路状态用于描述网络拓扑，这里的网络拓扑是指链路的连接类型及代价（Cost等。连接类型包括：该接口所连的网段中只有本路由器自己。该接口通过点到点的网络与一台路由器相连。（point-to-point叮）该接口通过广播或 NBMA的网络与多台路由器相连。（broadcast or NBMA networks ）该接口通过点到多点的网络与多台路由器相连。（point-to-multipoint ） 注：NBMA与点到多点的区别在OSPF协议中NBMA和点到多点都是指非广播多点可达的网络，但NBMA网络必须满 足全连通（full me

11、shed）的要求，即任意两点都可以不经转发而使报文直达对端。否则，我 们称该网络是点到多点网络。（2）洪泛法路由器通过所有输出端口向所有相邻的路由器发送信息（与本路由器相邻的所有路由 的链路状态）。而每个相邻路由器又再将此信息发往所有的相邻路由器（但不再发给刚刚发 来信息的那个路由器）。（3）链路状态数据库（Li nk-state Database）所有链路状态以数据库形式进行组织，该数据库描述了全网的拓扑结构图。（4）SPF（ Shortest Path First ）算法及最短路径树SPF算法是OSPF路由协议的基础。SPF算法将每一个路由器作为根（ROOT 来计算其 到每一个目的地路由器

12、的距离，每一个路由器根据一个统一的数据库会计算出路由域的拓扑 结构图， 该结构图类似于一棵树，即最短路径树。在OSPF路由协议中，最短路径树的树干长度，即OSPF路由器至每一个目的地路由器的距离，称为OSPF的Cost，其算法为：Cost=100 x 1/链路带宽 。链路带宽以bps来表示。即 Cost与链路的带宽成反比，带宽越高， Cost越小， 表示 OSPF到目的地的距离越近。 举例来说，FDDI或快速以太网的 Cost为1, 2M串行链路的Cost 为48,10M以太网的 Cost为10等。（5）区域划分为了使 OSPF能够用于规模很大的网络，OSP F将一个自治系统再划分为若干个更小

13、的 范围，叫作区域。每一个区域都有一个 32 位的区域标识符（用点分十进制表示） 。区域也 不能太大，在一个区域内的路由器最好不超过 200 个。划分区域的好处就是将利用洪泛法交换链路状态信息的范围局限于每一个区域而不是 整个的自治系统， 这就减少了整个网络上的通信量。 在一个区域内部的路由器只知道本区域 的完整网络拓扑，而不知道其他区域的网络拓扑的情况。OSPF使用层次结构的区域划分。在上层的区域叫作主干区域（backbone area）。主干区域的标识符规定为 0.0.0.0。主干区域的作用是用来连通其他在下层的区域。区域内部路由：R1, R2, R8, R9。该内路由仅知道它所在区域的网

14、络拓扑。区域边界路由：R3, R4, R7。即知道所在二级区域的网络拓扑，也知道主干区域的网 络拓扑。主干路由：R3，R4，R5, R6, R7。知道主干区域的网络拓扑，若同时扮演边界路由角 度，则知道与其相连的二级区域网络拓扑。自治系统边界路由：R6。知道主干区域的网络拓扑，并负责与其他AS交换路由信息。3、OSPF分组（1）OSPF分组格式（2）OSPF的分组类型类型1，问候（Hello）分组，用来发现和维持邻站的可达性。类型2，数据库描述（Database Description）分组，向邻站给出自己的链路状态数据中的所 有链路状态摘要信息。类型3，链路状态请求（Link State R

15、equest）分组，向对方请求发送某些链路状态项目的详 细信息。类型 4，链路状态更新 （Link State Update） 分组，用洪泛法对全网更新链路状态。用洪泛 法对全网更新链路状态。类型 5，链路状态确认 （Link State Acknowledgment） 分组。对链路更新分组的确认。4、OSPF工作原理1） 链路状态数据库的同步（1） RT1的一个连接到广播类型网络的接口上激活了OSPF协议，并发送了一个 HELLO 报文（使用组播地址 224.0.0.5 ）。由于此时RT1在该网段中还未发现任何邻居，所以 HELLO 报文中的 Neighbor 字段为空。（2） RT2收到R

16、T1发送的HELLO报文后，为RT1创建一个邻居的数据结构。 RT2发送 一个HELLO报文回应 RT1，并且在报文中的 Neighbor字段中填入 RT1的Router id,表示已 收到RT1的HELLO报文，并且将 RT1的邻居状态机置为In it。（3）RT1收到RT2回应的HELLO报文后，为RT2创建一个邻居的数据结构，并将邻居 状态机置为 Exstart 状态。下一步双方开始发送各自的链路状态数据库。RT1首先发送一个 DD报文，宣称自己是 Master（ MS=1），并规定序列号为 X。1=1表示 这是第一个DD报文，报文中并不包含 LSA的摘要，只是为了协商主从关系。 M=1

17、说明这不 是最后一个报文。（4）RT2在收到RT1的DD报文后，将 RT1的邻居状态机改为 Exstart，并且回应了一 个DD报文（该报文中同样不包含 LSA的摘要信息）。由于RT2的Router ID较大，所以在报 文中RT2认为自己是 Master，并且重新规定了序列号为 y。（5）RT1收到报文后，同意了 RT2为Master，并将RT2的邻居状态机改为 Exchange。 RT1使用RT2的序列号y来发送新的DD报文，该报文开始正式地传送 LSA的摘要。在报文 中RT1将MS=0，说明自己是 Slaveo（6） RT2收到报文后，将 RT1的邻居状态机改为 Exchange,并发送新

18、的 DD报文来描述自己的LSA摘要，需要注意的是：此时RT2已将报文的序列号改为y+1 了。(7) 上述过程持续进行，RT1通过重复RT2的序列号来确认已收到RT2的报文。RT2通过将序列号+1来确认已收到 RT1的报文。当RT2发送最后一个 DD报文时，将报文中的 M=0，表示这是最后一个 DD报文了。(8) RT1收到最后一个 DD报文后，发现RT2的数据库中有许多 LSA是自己没有的，将 邻居状态机改为 Loading状态。此时RT2也收到了 RT1的最后一个 DD报文，但RT1的LSA RT2都已经有了，不需要再请求，所以直接将 RT1的邻居状态机改为 Full状态。(9) RT1发送

19、LS Request报文向RT2请求所需要的 LSA RT2用LS Update报文来回应 RT1的请求。RT1收到之后，需要发送 LS Ack报文来确认。上述过程持续到 RT1中的LSA与 RT2的LSA完全同步为止。此时 RT1将RT2的邻居状态机改为 Full状态。当两台路由器之间的状态机都已经达到 Full 状态之后，如果此时网络中再有路由变化 时，就无须重复以上的所有步骤。只由一方发送LS Update报文通知需要更新的内容，另一方发送LS Ack报文予以回应即可。双方的邻居状态机在此过程中不再发生变化。2)链路状态算法 当路由器初始化或当网络结构发生变化(例如增减路由器，链路状态发

20、生变化等)时， 路由器会产生链路状态广播数据包LSA(Link-State Advertisement )，该数据包里包含路由器上所有相连链路，也即为所有端口的状态信息。所有路由器会通过洪泛法来交换链路状态数据，直至稳定。当网络重新稳定下来 (OSPF路由协议收敛下来)，所有的路由器会根据其各自的链路状态信息数据库计算出各自的路由 表。该路由表中包含路由器到每一个可到达目的地的Cost以及到达该目的地所要转发的下一个路由器( next-hop)。6、区域及区域间路由7、DR 与 BDR(1) DR的概念(2) DR的产生过程(3) 稳定压倒一切(4) 快速响应四、BGP(Border Gateway Protocol)1、导入因特网规模太大，路由表项目过多，使得AS之间路由选择非常困难。AS 之间的路由选择必须考虑有关策略。相互连接的网络的性能相差很大，按最小跳数 找出的路径可能并不合适。也有的路径的使用代价很