12-IP路由协议.ppt

IP路由协议 回答两个问题 路由表中应该包含一些什么信息 路由器如何获得这些信息 路由表的创建包含两个方面 初始化路由表和更新路由表 初始化路由表取决于操作系统 可能有如下几种情况 路由器在启动时从二级存储器中读取一个初始路由表 并驻留在主存中 初始路由表为空 在启动后通过执行外部命令来填充 从它所连接的本地网络的地址集推出一个初始的路由 并与相邻的路由器联系以获得更多的路由信息 初始的路由表建立之后 就需要根据网络路由的变化进行更新 对于较小的 变化较慢的网络可以由管理员手工来做 而对于大的 变化较复杂的网络则很难能由手工完成迅速的更新 就需要一些自动的方法 下一跳路由表的问题 由于下一跳路由表中只包含了到下一个网络 对于中间路由器而言 下一个网络不是目的网络 的路径 如果所有网络都是互通的 那么可以断定的是 除非进入了某个循环路径 数据最终总能到达目的网络 但问题在于 所走的路径是否是到达目的网络的最短路径 例如 一个方案是把网络中的路由器分为两类 一类路由器成为核心路由器 其中保有所有网络路径完整 可靠 一致的信息 这一类的路由器数目较少 由专门的组织负责维护 另一类是非核心的路由器 自治地维护本地路径 示意图 两种核心路由结构系统具有单一骨干网络 上图 具有对等骨干网络 上图 在核心路由系统中 通过把所有可能路径的完备信息在核心路由器之间不断传播 更新而使核心路由系统能保有完整 一致 可靠的路由信息 其中的一个关键是路由传播和更新的算法 两种核心路由协议 1988年以前 Internet核心路由系统使用DECLSI 11计算机运行GGP gateway to gateway 协议 此协议采用的路由信息传播和更新的算法为矢量距离 Vector Distance 算法 目前 大部分使用SPREAD协议 RFC中目前还没有其详细内容 其中路由信息传播和更新采用了基于链路状态的最短路径优先 Shortest Path First 算法 VD算法 1 初始化 路由器在启动时初始化一张路由表 表中只包含与其直接相连的网络条目 如下表所示 表中包含三列 第一列为目标网络 在初始化时只有与该路由器直接相连的网络 表中设该路由器只与网络1和网络2直接相连第二列为从该路由器到目标网络中间所需经过的其他路由器的数目 hop值 来计算 和目标网络直接相连 则中间路由器个数为0第三列为为到达目标网络下一步应向那一个路由器转发 若直接相连 则为直接转发 2 每个路由器都把它的路由表发送一个拷贝给与它直接相邻的路由器 路由器利用这些信息来更新自己的路由表 一般在以下几种情况下需要更新 设路由器1收到路由器2发来的路由表信息 如果路由器2中包含路由器1中所没有的目的网络 那么 路由器1应在路由表中加入一行包含此项如果路由器2的路由表中包含一个达到某个目的网络的更短的路径 具有更小的Hop值 则路由器1应该在路由表中更新对应的行如果在路由器1的路由表中包含要通过路由器2的目的网络 若路由器2达到此目的网络的距离已改变 则路由器1的路由表要更新例 设表1为路由器1的已有路由表 表2为由路由器2发送来的包含VD 目的矢量 距离 的消息 路由器1在收到此信息时 需要作三个更新 表2中的网络21是在表1中没有的 应加上 网络214 1路由器2 从表2可知到网络4有更短路径 应更新该行 网络43 1路由器2 从表2可知通过路由器2到网络42的Hop值已变为3 需更新 3 1 表1 表2 VD算法易于执行 但是当路由变化较快时 由于路由信息传播的延迟 会导致某一时期路由信息的不一致以及慢收敛问题 见后面RIP部分 算法需要大量的消息交换 其交换量与路由器数目成正比 因此在网络规模大时 不利于扩展 替代该算法的一个算法为 最短路径优先 ShortestPathFirst 算法 该算法利用网络拓扑结构 基于链路状态 作如下抽象 把网络中的每个路由器看成一个节点 若两个路由器之间存在直接的连接 就认为它们之间存在一条边这样整个网络拓扑就可抽象为一个只含有节点和边的图参与SPF算法的路由器执行如下两个任务以获得网络拓扑结构 周期性地测试与相邻路由器的连接状态周期性地把连接状态广播给其他路由器每个路由器在获得整个网络的拓扑结构后 就可以各自独立地使用Dijkstra最短路径算法来计算从本路由到其他路由的最短路 SPF与VD的比较 SPF中 各路由器独立确认路由 而在VD中 各路由器需要依靠其他路由器SPF中 确认路由只需依靠网络拓扑 而在VD中 确认路由需要各个路由器相互交换路由信息一般SPF要比VD收敛得快 即路由发生变化时 SPF能更快达到新的稳定状态 GGP 在核心路由系统中各路由器相互交换路由信息的协议 采用VD算法 利用GGP报文来交换路由信息 GGP报文有三种类型 每种类型都有一定的格式 头一个八位组标识报文类型 路由更新报文 类型 12 更新确认 出错 报文 类型 2或10 路由器在收到路由更新报文后 若更新被接受 则回应以确认报文 若报文有错 则回应以出错报文 报文格式为 回波请求 响应 报文 类型 0或8 一个路由器发出回波请求报文测试另一个路由器是否在工作 若接收方正常 则发回回波响应报文 报文格式为 路由更新报文格式 路由更新报文格式说明 类型 字段为12标识为路由更新报文 序列号 字段被发送端和接收端用来作同一性确认 更新 字段指明发送方是否需要接收端的更新 NUMDISTANCES 字段指明本次更新有多少个距离组 相同距离为一组 报文的后面部分就是按距离分组的一些网络集合 每个集合前面是两个8位的字段 DISTANCED字段和NUM NETSATD 分别指明一个距离值和具有此距离的网络数目 然后紧接着就是指定每一个网络的IP地址中的网络id FirstNETATDISTANCED字段 SecondNETATDISTANCED字段 上述协议解决了核心路由之间交换路由信息的问题 利用该协议 各核心路由器可以寻找最优路径 两个遗留问题 对于非核心路由器 由于非核心路由器不能与核心路由器相互交换路由信息 一般需要指定某个核心路由器来转发它所不能直接转发的数据 这时就有可能出现不能获得最优路径的问题 例如 其中R1 R2为核心路由器 R3为非核心路由器 设路由器R3指定R1来转发它不能直接转发的数据 对于要发往网络1的数据 路由器R3通过骨干网络传给R1 再由R1转发 可取得最优路径 而对于要发往网络2的数据 路由器R3同样首先通过骨干网络传给R1 而R1根据路由信息转发给R2 由R2进行最后转发 这时的路由并不是最优的 最优情况是直接由R3转发到R2 无需R1这一跳 出现非最优情况的原因在于非核心路由器R3不能与核心路由系统交换路由信息 而只能固定地向预先指定的某个核心路由器转发数据 不论预先指定那一个路由器 都可能出现非最优的情况 简单地把R3也纳入核心路由器系统并不可取 因为这样会急剧增大核心路由器的数目 因此 一个问题是 需要建立一种机制 使得非核心路由器能从核心路由器中获得路由信息 另一方面 考虑如下例子 其中 R1是核心路由器 而R2 R3 R4是非核心路由器 一个问题是 R1只能向其他核心路由器报告能直接到达网络1 而不知道其他几个间接连接的网络 由于R2 R3 R4均为非核心路由器 不能与核心路由系统交换信息 因而 对于核心路由而言 这些网络是不可知的 这样 一旦与别的核心路由器相连的其他网络中的主机要与这几个网络中的主机进行通信时 就不知道数据转发的路径了 因此 第二个问题是 需要建立一种机制 使得核心路由系统能从非核心路由器获得更多的路由信息 这两个问题的可以综合为 核心路由系统与非核心路由器之间如何交换路由信息 为解决此问题 需要引进一个概念 自治系统 自治系统 为了进行路由而实行单一控制的一组网络和路由器称之为一个自治系统 在自治系统内部 可以自由地选择一种机制来传播路由 检验路由的一致性 显然 核心路由系统就是一个自治系统 根据流量传送 可以把自治系统分为三类 残桩自治系统 与其他自治系统只有单个连接 只有本地流量 起始或终止于本自治系统的流量 其他则称为通过流量 多接口自治系统 与其他自治系统有多个连接 但拒绝通过流量转送自治系统 与其他自治系统有多个连接 在策略允许下 可以传送本地或通过流量 例如 可以把与每个核心路由器相连的骨干网络外部的一组网络和路由器规定为一个自治系统 如下页图 在每一个自治系统中 都指定一个或多个路由器负责收集并向与此自治系统相连接的核心路由器发送本自治系统中各个网络的可达性信息 这样 要解决的非核心路由器与核心路由器的信息交换问题就转化为一个管理问题 即进行如下的几个步骤 划分自治系统在自治系统内部自由选择路由传播和收集的机制指定对此自治系统路由信息进行收集的路由器此路由器将所获得的该自治系统的路由信息报告给某个核心路由器 为进一步的介绍 先引入几个术语 两个路由器称为是外邻 如果它们分属两个不同的自治系统两个路由器称为是内邻 如果它们属于同一个自治系统外部网关协议 ExteriorGatewayProtocol 称为网关的原因是早期路由器也称为IP网关 用于外邻之间广播网络可达性的协议称为EGP 使用它的路由器称为外部路由器 如下图 其中 路由器1收集自治系统1中的路由信息并使用EGP把信息报告给路由器2 而路由器2收集自治系统2中的路由信息并使用EGP把信息报告给路由器1 如果把自治系统2看成是核心路由系统 路由器2就是某个核心路由器 自治系统1就是一个与核心路由器2相连的一个自治系统 则前述的四个步骤就是 确定自治系统1在自治系统1选择一个路由信息传播和收集的机制确定路由器1对此自治系统中的路由信息进行收集路由器1利用EGP把自治系统1的路由信息报告给核心路由器2这样就利用EGP解决了非核心路由器与核心路由器的信息交换问题 下面详细介绍EGP EGP EGP的三个主要功能 支持 相邻获得 机制 即允许一个路由器请求另一个路由器同意二者应该交流可达性信息 这也称一个路由器获得一个EGP对等或EGP邻居 EGP对等称为相邻的当且仅当它们要交换路由信息 而与地理位置的远近无关 路由器需持续测试其EGP邻居是否在响应 EGP邻居通过发送路由更新报文周期性交换网络可达性信息 EGP报文首部格式 版本 字段为EGP版本号 类型 字段标识报文类型 代码 字段标识报文类型的子类型 状态 字段包含与报文相关的状态信息 检校和 字段为EGP报文的检校和 自治系统编号 字段为发送报文的路由器所在的自治系统的编号 预先分配 序列号 字段关联发送和接收 EGP报文类型 EGP邻居获得报文 一个路由器利用EGP邻居获得报文与另一个路由器建立EGP通信 注意 为何选择另一个路由器来建立EGP通信由管理员确定而非协议 报文格式 Hello时间长度 用于测试邻居是否在工作的时间长度查询时间长度 控制路由更新的频率 最大更新周期 单位 秒 可更改 非对称 对等双方的更新频率不同 依据 代码 字段的不同可分为四种 共同完成对等获得的任务 EGP邻居可达性报文 报文格式 只含报文首部 代码为0 Hello报文代码为1 IHeardYou报文为防止单个报文丢失而导致的错判 采用n中取k的表决方式 连续发送n个报文 若收到k个或以上响应 则认为对方可达 EGP查询请求和响应报文 路由器利用此报文获得网络可达性信息 报文格式 一个路由器通常和多个网络相连 在此 IP源网络 字段 指定与两个路由器都相连的两个自治系统共有的网络 以便明确EGP报文应该发给那个网络路由器 同时也就指明了一个自治系统的流量入口 如下图所示 EGP路由更新报文 外部路由通过此报文向其对等路由器发送它的可达网络信息 这些可达性报文包括两类 是在它所在的自治系统中可达的目标网络是它从别的路由器获得的 学习 在其自治系统以外的目的网络一般规定 不允许在非核心路由器之间广播第二类信息 因此在一个自治系统 除核心路由系统 内部的非核心路由是不知道外部自治系统的路由信息 这也保证了各自治系统的相对独立性 这一规定也称为 EGP第三方限制 路由更新报文格式 说明 报文中的距离值为255时表示网络不可达 这些距离值并不具有比较意义 除非两个网络位于同一个自治系统中 本质上 这些距离值只表示网络通过该路由器是可达的 报文中外部路由器和内部路由器 无论内部或外部都应是与指定的IP源网络直接相连的 而其他不相连的不列出 一般是分开传送的 因为在报文内部无法仅通过IP来区分内部路由和外部路由 而在进行选路时又必须区分 因为外部路由和内部路由没有距离上的可比性 一个外部的hop值与一个内部hop值差别很大 可见由EGP提供的路径之间无法进行比较 因此EGP不能用于路由算法 但可得到一个可达路径 这些路径形成一个以核心路由器为根的可达树 不包括任何循环 报文中 和GGP一样 对于每个路由器的可达网络 路由信息也是按距离分组排列 报文中距离的测量不是以某个路由器为准 而是以指定的IP源网络为基准 因此 在自治网络中 指定不同的路由器进行路由信息的搜集所得的结果是一致的 新的EGP为边界网关协议 BGP 3 RFC 1267 RFC 1268 1991 BGP 4 RFC 1467 BGP允许使用基于策略的选路 通过执行管理员预先指定的策略 BGP可以实现进行路径选择 BGP使用TCP 两个运行BGP的系统之间建立一条TCP连接 交换所有的BGP路由表 BGP基于距离向量 但不是仅保留目的地址和跳数 而且还保留了中间路由 EGP BGP 提供了不同自治系统之间交换各自系统中网络可达性的方式 但由于距离尺度的差别 并不能用来实现路由选择 而在同一自治系统之中则可以进行路径比较 进行路由选择 前面已介绍了在一类特殊的自治系统中 核心路由系统 的路由传播和进行选路的GGP 路由算法为VD 以下将针对一般自治系统介绍在同一自治系统中如何进行路由传播进而进行路由选择 简单情况下 若一个自治系统较小 变化较慢 则可以为其中的所有路由器和主机都手工配置一个路由表 很显然 当系统较大 系统变化较快时 手工配置是不现实的 因此需要自动方法 在同一自治系统中实现路由器之间自动传播可达信息 进行路由选择的协议称为内部网关协议 IGP 实际上 与EGP不同 并不存在一个确定的IGP 能够实现上述功能的协议都可称之为是一种IGP 目前有多个 RIP OSPF等 不同的自治系统可以利用不同的IGP 如图所示 路由信息协议 RouteInformationProtocol 版本1 首个RIP RIP1RFC1058 1988 标准发布于1988年六月 在此之前由于包含在Berkeley的UNIX系统中已经得到广泛使用 RIP把网络中的节点分为活动的和被动的 活动节点可以广播路由信息 也可以接收 更新信息 被动节点只能接收广播并更新自己的路由信息 只有路由器可以作为活动节点 而主机只能作为被动节点 活动节点每隔30秒广播一轮其当前路由表中的路由信息 RIP使用 跳数 来计算到目的网络的距离 通过一个网络为一跳 可以人为地把某些慢速网络设置为多跳数 以更精确 RIP规定最大跳数为15 若跳数为16则表示不可达 RIP路由信息中只包含两项 目的网络和达到目的网络的跳数 RIP中活动的和被动的节点通过执行VD路由算法来更新路由表 RIP提出了一些规则来提供性能和可靠性 例如 一旦路由器从别的路由器学习到一个路由 那么它将一致保留直到学到了另一个更好的 最优 又避免振荡 被动节点在学到一个路由后要立即开始计时 在180秒之内 如果一直没有再次得到关于此路由的广播 则放弃此路由 宁缺勿错 RIP中的问题 慢收敛问题 VD算法所致 问题的描述 如下图 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的流量仍被引导到这个不可能的方向 称之为慢收敛问题 解决方案 水平切割 splithorizon 路由器计录每个接口收到的路由信息 禁止把一条路由信息从收到它的接口再广播出去 如上例 可以解决问题 但有些拓扑结构也不行 保持 holddown 一旦某个路由器在收到一个网络变为不可达的消息后 它将在一个规定时间区间内保持此消息而忽略其他路由器发给它的其他消息 坏消息优先 针对网上 好消息传的快 坏消息传的慢 这样就确保坏消息能先传播出去 而不会在传出去之前就被更新 但会造成一个较长的保持时间 特别对广域网 即使此时有好消息 也不可传播 触发更新 triggeredupdate poisonreverse 一旦收到消息报告网络不可达 就立即广播 不必等下一个广播周期到 同时 在广播中保留此目的网络 只是加一个很大的代价值 但在某些结构中 如多个路由器同时连在某个网络上 此时会造成突然的流量激增 都能解决问题 但一定程度又会导致一些新的问题 RIP报文格式 RIP报文封装在用户数据报 UDP 中 默认UDP端口号为520 不同的命令字段值指定不同的操作 路由器和主机可以通过发送请求命令来请求另外的路由器发送路由信息 通常 路由器周期性发送非请求的路由信息 每个报文最多携带25个路由 RIP选路中的距离为hop值 有以下问题 hop值刻画距离并不能十分精确 每一跳并不