第七章-网络互连-之-路由协议PPT课件.ppt

路由协议 RIP OSPF和BGP 1 互联网络 internet 是路由器连接而成的多个网络的组合体 当数据报从一个源端传送到一个目标端时 可能需要通过很多个路由器才到达与目标网络连接的路由器 路由器的作用是从一个网络中接收数据包 packet 分组 然后将它传送给另一个网络 一个路由器通常与几个网络连接 这样 当它收到一个数据包时 应该将数据包转发给哪个网络呢 路由器是按最佳化原则进行判定 哪个可用的路径是最佳路径 2 人们用metric来表示通过某个网络时所指定的 成本 cost 代价 一个特定路由的总metric 等于包含了该路由的多个网络的metric之和 路由器根据最短 最小 的metric来选择路由 Metric电信专业n 米制的 量度的计算机专业度量 尺度 公制 3 分配给每个网络的metric取决于协议的类型 某些简单的协议 如 路由信息协议 RIP 将每个网络同等处理 即通过每个网络的cost是一样的 或者说都是一个 跳数 onehopcount 所以如果一个数据包通过10个网络才到达目标端 其总cost就是10个 跳数 其他协议 如 开放最短路径优先协议 OSPF 则允许管理员根据所需的服务类型 为通过一个网络指定cost 通过某个网络的路由可以具有不同的cost metric 例如 如果所需的服务类型是 最大吞吐量 throughput 一条卫星链路就比一条光纤链路具有更低的metric 另一方面 如果所需的服务类型是 最小延迟 一条光纤链路就比一条卫星链路具有更低的metric OSPF允许每个路由器根据所需的服务类型拥有几个路由表 4 其他协议定义metric的方法则完全不同 在 边缘网关协议 BGP 中 评定的标准是可以由管理员设置的所谓 策略 policy 策略 定义了应该选择的是哪个路径 不管metric是如何确定的 路由器在准备转发数据包时 都必须使用路由表 路由表应为数据包规定最佳路径 不过 路由表可以是静态的 也可以是动态的 静态路由表 是那种不经常变化的路由表 动态路由表 是那种当互联网络中的某处出现变化时能自动更新的路由表 今天 互联网络需要的是动态路由表 这种路由表要求互联网络出现变化时即被尽快更新 例如 当某个路由关闭 down 时 需要进行更新 而当一个更好的路由建立后 也需要进行更新 5 各种路由协议都是为了动态路由表的需要而制定的 一个路由协议是一组规则和程序的组合 用于使互联网络中的路由器们相互告知有关的变化情况 它使路由器们共享它们所掌握的互联网络或相邻路由器的情况 这种信息的共享使得武汉的某个路由器可以知道上海的网络出现故障了 路由协议还包含了将从其他路由器接收的信息综合起来的处理程序 什么是路由协议 6 内部和外部路由 今天 一个互联网络可能很大 以致一个路由协议无法完成为所有路由器更新路由表的任务 为此 需要将一个互联网络分为若干 自治系统 autonomoussystems AS 一个 自治系统 是指由同一个管理员管理的一组网络和路由器 自治系统内部的路由称为 内部路由 自治系统之间的路由称为 外部路由 每个自治系统都可以选择一个内部路由协议来处理该自治系统内部的路由 但是 自治系统之间的路由通常只能使用一个外部路由协议来处理 7 路由器R1 R2和R3使用一个内部路由协议和一个外部路由协议 其他路由器只使用内部路由协议 阴影部分表示使用内部路由协议的各自治系统 细实线表示使用内部路由协议的各路由器间的通信连接 粗实线表示使用外部路由协议的各路由器间的通信连接 8 现在使用的内部和外部路由协议很多 本章只介绍最常用的几种 下面讨论两个内部路由协议 RIP和OSPF 和一个外部路由协议 BGP RIP和OSPF可用于自治系统内部路由表的更新 BGP可用于为连接自治系统的各个路由器进行路由表更新 9 动态路由 路由算法 根据网络拓扑计算路由的方法 或路由表的生成方法 两种路由算法 矢量 距离 V D 算法如RIP 路由信息 链路状态 L S 算法如OSPF 开放最短路径优先 10 矢量 距离 V D 算法 路由表中列出所有已知的路由启动时路由器对每个与自己直连的网络生成一个表项每个路由器周期地向直接相连的其他路由器发送自己的路由表每个路由器根据其他路由器发来的路由更新消息 相应修改自己的路由表周期性传送的信息包括 目的网络地址 矢量 V 到达该网络的距离D 这就是矢量 距离算法名称的来源 11 链路状态 L S 算法 不需要传送路由信息 只需 1 检测所有相邻路由器的状态 相邻 通过同一网络连接的两个路由器 周期地向相邻路由器发送 Hello 报文 询问其工作状态2 周期地向其他路由器通告自己了解到的链接状态信息 链路类型 链路标识 通告该链路的路由器地址每个路由器根据其他路由器发来的链路状态报文 相应地更新自己的网络拓扑结构数据库 最终每个路由器都具有同样的网络拓扑结构数据库 即共享一个公共的连接状态数据库 称为收敛路由器使用Dijkstra最短路径算法对网络拓扑图求最短路径 计算到达其他网络的最短路径最后用计算出来的最短路径更新自己的路由表 12 D V和L S算法的比较 D V通过与邻居的信息交换获得网络拓扑知识路由计算是增加路由器之间的站点数 hops 定期刷新路由 收敛慢向相邻站点传送路由表的副本 L S全网获得共同的全局性网络拓扑知识 L S图 计算到达其他站点的最短路径 SPF准则 触发刷新 收敛快向其他站点发送链路状态的动态变化 13 RIP 路由信息协议 路由信息协议是一个用于自治系统内部的 内部路由协议 它是一种非常简单的协议 基于 距离向量路由 技术 14 距离向量路由在 距离向量路由 中 每个路由器都定期地和其相邻的路由器们共享它们对整个互联网络掌握的情况 理解这一算法的工作原理有三个关键 如下 1 共享整个自治系统的情况每个路由器都和其相邻的路由器们共享它们对整个互联网络掌握的情况 开始时 一个路由器掌握的情况可能是很少的 便是它知道多少并不重要 它发送它所知道的所有情况 2 只和相邻的路由器共享每个路由器只向相邻的路由器发送自己掌握的情况 它通过自己的所有端口发送自己知道的所有情况 3 定期地共享每个路由器都定期地 如每隔30秒 向相邻的路由器发送自己掌握的情况 术语 距离向量 起源于定期信息发送 一个报文包含有成对的列表 V D 这里的V表示目的地 叫做向量 D是到达那个目的地的距离 注意距离向量是以第一人称报告路由的 即我们把一个路由器送来的通告看成它在说 我可以到达距离为D的目的地V 15 路由表每个路由器都保持一张路由表 表中为路由器知道的每一个目标网络设置一条记录 该记录由目标网络的IP地址 到达目标的最短距离 用 跳数 表示 和下一跳 为了到达最后目标应将数据包转送给它的下一个路由器 三个部分组成 跳数是指数据包到达最后目标所进入的网络数目 路由表中还含有诸如该记录最后更新时间等其他信息 示例如下 16 RIP更新算法路由表根据收到的RIP响应报文 message 进行更新 以下是RIP所使用的更新算法 接收 一个RIP响应报文1 为每个advertised 被发布 的目标增加一个跳数值 2 对每个advertised的目标重复以下步骤 IF 目标不在路由表中 将advertised的信息添加到路由表中 ELSEIF 下一跳字段相同 用advertised的记录替换表中的记录ELSEIF advertised跳数小于表中的跳数 把它加到路由表中 更新 ELSE什么都不做3 返回 17 动态路由举例 路由信息协议RIP 报文由序偶 IP网络地址 到达该网络的距离 组成用步跳数表示到达目的网络的距离 1 16 1表示直连 16表示不可达 即只要步跳数大于等于16就认为路径为无穷远 路由器收到路由更新报文后应更新自己的路由表例如 R2从R1收到的路由更新报文为 net1 1 net2 2 net3 1 则R2的路由表更新为 net1 R1 2 net2 R1 3 net3 R1 2 18 RIP协议的时钟 路由刷新周期每个路由器每隔30秒刷新和广播自己的路由表 路由失效计时一条路由表项未被更新的时间达3分钟 180秒 则视其为失效信息 将本路由表项的距离置为无穷大 毒性逆转 路由保持计时发现一条路由失效信息后 立即启动保持计时 60秒之后删除此条目 19 RIP的缺点 算法不能明确的检测出循环路由 会产生慢收敛和无限计数问题步跳数不能反映链路的真实开销 例如步跳数为4的LAN路径不一定比步跳数为1的64KDDN链路差 1 R1与网络1直接相连 2 通过周期性路由广播 R1 R2 R3都建立了到网络1的路由 a 3 某时刻 R1到网络1的路由消失 b 4 但是R2对R1的路由通告引起了选路的循环 更新报文会在R1 R2来回传输直到距离值到达RIP规定的上限 网络1 R1 R2 R3 a b 20 R1直接与网络1相连 因此在路由表中具有一个到网络1的路由 跳数为0 在它广播后 R2获得到网络1的路由 跳数为0 1 1 最后R3则通过R2的广播得到到网络1的路由 跳数为1 1 2 同时 R1也会收到R2的广播 但是由于在R1中到网络1的跳数为0 比R2的小 因此不会更新 如果网络1到R1的连接故障 则R1把到网络1的跳数设为16 并广播 使其它路由器更新 但是 由于所有路由器都会周期性广播路由信息 因而可能会出现这种情况 在R1广播跳数16之前 先收到了来自R2的广播 计算到网络1的跳数为1 1 2 比16小 因此在还没有广播之前已经被更新了 等到下一个广播周期时 R2的更新为2 1 3 到下一轮广播 R1又是收到R2的广播跳数变为3 1 4 而后又广播给R2 使R2到网络1的跳数更新为4 1 5 如此 不断增加 要经过一个较长的时间 大于14 30秒 之后 才会发现网络1从这里是不可达的 而这段时间内到网络1的流量仍被引导到这个不可能的方向 这就是慢收敛问题 坏消息传得慢 网络1 R1 R2 R3 21 11 A C B 40 0 0 0down 到达信宿40 0 0 0的路由变化 路径环 RoutingLoop 问题 这条错误的路由信息在C与B之间不断复制和修改 并在网络中传播 殃及A 形成路径传播的环路 22 11 A C B 40 0 0 0down 到达信宿40 0 0 0的路由变化 严重后果 计数至无穷大 23 11 A C B 40 0 0 0down 到达信宿40 0 0 0的路由变化 定义Hop最大值为16 解决办法 定义距离的最大值 收敛 24 解决RIP存在的问题的几种方法 视野分离 水平分割 Split Horizon从一个接口收到的路由信息不会再通过该接口送回去毒性逆转PoisonReverse从一个接口收到的路由信息可以再通过该接口送回去 但距离为16触发更新Triggedupdates路由发生变化时 不必等到30秒 可立即将更新报文广播出去抑制更新Hold Downtimers收到某网络不可达的信息后 在一段时间内 60秒 忽略任何关于该网络的路由信息 25 水平分割方法的思路 11 A C B 40 0 0 0down 分析路径环产生的原因B向C提供了一条过时的 错误的路由信息 能否避免事件发生 B必须经由C方可到达网络40 0 0 0 B不可能向C提供任何有价值的路由信息 修改B对C提供的路由 禁止B向C提供关于此信宿的路由信息 26 水平分割法 SplitHorizons 11 A C B 40 0 0 0down 收敛 到达信宿40 0 0 0的路由变化 水平分割法利用的是路由报文发送的选择性 一个路由器必须识别不同的端口 如果一个路由器已经从某个端口处接收到了路由更新信息 那么这同一个更新信息就不能通过此端口再发送回去 如果一个端口已经发送信息以帮助某个路由器进行更新 这种更新的信息不得回送 它是已知的 所以是不需要的 27 水平分裂不能解决所有的问题 水平分裂虽然广泛使用 但有时候会失败 如右图 开始时 A和B到D的距离都为2 C到D的距离为1 假设CD线路断了 使用水平分裂 A和B都告诉C 它们不能到达D 同时C自己也发现直达D的线路断了 于是C很快认定D不可达了 但是 A认为B有一条通向D长度为2的路径 通过B经过3个结点可到达D 类似 B也这样认为 于是两个结点每交换一次信息 到达D的距离就增加1 直至加大无穷 28 11 A C B 40 0 0 0down 此法是水平分割法的一个变种 在本办法中 路由器收到的信息被用于更新路由表 然后转发到所有端口 但是 从某个端口传来的路由表记录如果通过同一个端口出去 它的跳数值被设为16 反向抑制法 毒性逆转PoisonReverse 29 11 A C B 40 0 0 0down 当C发现网络40 0 0 0发生故障时 不等下一刷新周期到来 立刻更改路由为 信宿不可达 引起全网的连锁反映 迅速刷新 触发刷新法 网络40 0 0 0不可达 网络40 0 0 0不可达 网络40 0 0 0不可达 30 距离向量算法小结 路径选择采用最短路径准则 计算D信宿 距离 下站 每个站点只知道自己和邻居的局部信息 在自己的刷新周期到来时 根据邻居的路由变化重新启动算法 算法的收敛速度慢 特别是对网络崩溃 造成全网信息的不一致 导致产生路径环 使计数至无穷大 当路径环产生时 定义距离的最大值可防止算法进入死循环 解决计数至无穷大问题 各种加速收敛方法的目的在于避免路径环的形成 但不能从根本上杜绝这一现象的发生 在具体的路由协议中 各种加速收敛方法往往综合使用 31 开放最短路径优先 OSPF 协议 32 OSPF协议的基本概念 OpenShortestPathFirst采用链接状态 L S 算法由IETF工作小组研制1990年成为标准 RFC1247 改进RIP协议的问题计数至无穷大收敛速度慢 33 开放最短路径优先 OSPF 协议 使用SPF算法 基于链路状态 ShortestPathFirst 提供路由服务类型 如可要求低延迟或高吞吐量 路由时不仅依据路由目的 还要依据服务类型要求 OSPF将均分负载给各个路径提供网络的 域 划分能力 一个域对外部是透明的 因而可独立管理 这就提供了灵活的网络扩展能力 易于规模化OSPF规定路由器之间的信息交换需要有授权 提高安全性 RIP中任意路由都可广播路由信息 易被利用 支持指向特定主机 特定子网的路由 当然还有对网络的路由 以满足不同需要 支持子网支持CIDR支持虚链路 34 最短路径优先 ShortestPathFirst 算法 该算法利用网络拓扑结构 基于链路状态 作如下抽象 把网络中的每个路由器看成一个节点 若两个路由器之间存在直接的连接 就认为它们之间存在一条边这样整个网络拓扑就可抽象为一个只含有节点和边的图参与SPF算法的路由器执行如下两个任务以获得网络拓扑结构 周期性地测试与相邻路由器的连接状态周期性地把连接状态广播给其他路由器每个路由器在获得整个网络的拓扑结构后 就可以各自独立地使用Dijkstra最短路径算法来计算从本路由到其他路由的最短路 35 A E D C B 2 1 2 1 1 3 Dijkatra最短路径算法 F 3 5 5 2 36 Dijkatra算法计算结果 A E D C B 2 1 2 1 1 3 源点A到所有结点的最短路径 F 3 5 5 2 D F E A B C 1 1 2 1 2 L S图 SPF树 37 每个路由器周期性地收集和发送信息主动测试其到所有邻居的链接状态 度量值 向所有的路由器发送 广播 自己拥有的状态信息得到一个全网的 动态的逻辑链路状态 L S 图每个路由器刷新自己的路由表当L S变化时 用最短路径优先 SPF 算法重新计算本地路由 D C A B 链路状态算法的