Internet课程2-IP路由.ppt

4 1 1Internet路由体系结构 核心系统 核心网关 非核心网关 第四章IP路由 4 1IP路由概述 4 1 3路由选择策略 转发模式 静态选择策略 泛洪法 选择泛洪法 固定路由表法 随机法 分散通信量法 4 1 2路由器功能部件 动态选择策略 孤立路由法 集中式路由算法 分布式路由算法 分层式路由算法 混合式路由算法 第四章IP路由 4 1 4最短路径搜索算法 1 距离向量算法 Bellmen Ford 寻找由指定节点到目的节点的最短通路 需要周期性地与相邻节点 路由器 交换路由状态信息 路由状态信息由 V D 序偶对组成表 V代表可到达的目的 D代表到达V的距离 数学描述 V n D m D m 为m经过n到达v的距离 设k为m的邻居 D m min D k l k m n k 2 链路状态 最短路径算法 Dijkstra 寻找由源节点到所有节点的最短通路 需要一张整个网络拓扑结构的无向图 该图可称为Link State图 L S图全局一致 节点需要向所有其他节点广播L S信息 数学描述 N s 对v D v l s v s直接连接v或无穷大 选择D w 最小的w 对其他的v D v min D v D w l w v N s w 直至N包括所有节点 第四章IP路由 4 2 1RIP 特点 采用Bellmen算法 简单 运行开销小 适用于小型网络 RIP使用UDP的520端口传递路由信息 交互的报文 请求报文和响应报文 最大距离为16跳 否则 为不可达 升级 1988年RIPv1 RIPv2增加了认证 路由标签 子网掩码 下一跳 组播 请求与响应等 RIPng针对IPv6 运行过程 启动时 RIP处理模块发出请求报文 然后进入等待 接收到请求报文的路由器发送自己路由信息的响应报文 接收到响应的路由器判断是否更新路由表 定时器 启动后 路由器以30秒 可调 间隔周期发送响应报文 每条路由信息项的无效定时为180秒 默认 超时没有收到对应邻居 下一跳 的响应报文则将该距离值设为无穷大 16 该路由项继续保留120秒 以便可达邻居受到更新信息 计数无穷大 收敛慢问题 由于邻居传递信息时差 存在路由环路问题 会导致距离计算到无穷大 造成一段时间的无序状态 解决办法 简单水平分裂 不向邻居发送从该邻居获取的路由信息 毒性逆转水平分裂 将从邻居获得的路由信息回送时距离设为无穷大 触发更新 一旦发现路由信息变化 立即广播更新报文 不必等待30秒的周期 验证 身份认证 路由标签 传递AS的标号给外部网关路由协议 子网掩码 支持特定的子网路由和超网路由 下一跳 避免分组在传送过程增加不必要的跳数 可直接抵达 组播 增加了使用组播方式传递路由信息 降低通信量 请求与响应 RIPv2可以不对RIPv1的请求作出响应 第四章IP路由 4 2单播路由 4 2 2OSPF 特点 采用Dijkstra算法 协议复杂 适用于大型网络 OSPF直接基于IP设计 路由器维持一个统一的链路状态数据库 构造自己为根的最短路径树 算法收敛时间短 OSPFv3支持IPv6 引入区域概念来隐藏区域内部拓扑结构 减少路由流量 采用分层路由管理机制 数据库同步 初始数据库同步通过数据库交换过程完成 其后 数据库同步 链路状态变化的同步 通过泛洪过程维护 第四章IP路由 Hello 1 发现邻居路由器 2 选举链路代表路由器和备份路由器 路由器周期发送Hello报文 邻居间必须建立双向连接 若超时无Hello消息则认为邻居死亡 一条链路涉及的多个路由器中需选举出一个 优先级最高的 路由器作为代表 另选定一个备份代表 故障时备份代表自动接管工作 4 2 2 1建立邻居关系 邻居数据库同步 1 状态比较 邻居路由器通过可靠地交换数据库描述分组来判断是否更新数据库记录 通过比较 链路状态序号 判断 2 请求更新 对变化的链路 路由器请求最新序号的记录 发送链路状态请求分组 3 修改记录 收到请求的路由器发送被请求记录的链路状态更新分组 4 2 2 2泛洪 广播链路状态通告 一旦链路的状态发生变化 代表该链路的路由器通过泛洪的方法向全网广播发生变化的链路状态更新通告 为保证可靠性 路由器周期性广播通告 直到收到所有 邻居 的确认消息 第四章IP路由 生存时间 该LSA的生成至今的时间 LS类型 表示LSA执行的功能及泛洪的范围 有些LSA信息需要在整个AS内泛洪 有些只在区域内泛洪 不同的类型LSA共同构成OSPF的链路状态数据库 就像数据库系统中不同的表共同构成一个应用数据库 链路状态ID 该字段与类型 通告路由器一起唯一标识数据库中的一个LSA记录 通告路由器 生成该LSA的路由器ID 链路状态序号 N 231 计数从 N 1 0 x80000001 开始至N 1 0 x7FFFFFFF 当计数到N 1 须将对应的LSA老化 重新泛洪 得到确认 计数同步 后从 N 1开始 4 2 2 3链路状态数据库 链路状态通告LSA是OSPF同步数据库信息记录的存在形式 有多种LSA类型 其泛洪的范围不同 但都有标准的20字节LSA报头 第四章IP路由 路由器LSA 域内泛洪 描述路由器连接到某区域的所有接口的状态 网络LSA 域内泛洪 描述多个附接路由器网络构成的链路的状态 域间前缀LSA 由区域边界路由器生成 域内泛洪 描述可达的区域外 AS内的子网集合及状态 域间路由器LSA 域内泛洪 描述到达区域外 AS内目标路由器 边界路由器 的路径的状态 AS外部LSA 由边界路由器产生 AS内泛洪 描述可到达的本AS外部目的网络或路由器的路径状态 链路LSA 链路本地泛洪 描述多个附接路由器链路的非代表链路 域内前缀LSA 域内泛洪 描述域内的相关子网集合 汇总LSA 某个区域的域间前缀LAS和域间路由器LSA统称为汇总LSA 4 2 2 4路由表计算 OSPF路由计算过程较为复杂 路由器在每一步计算中须访问链路状态数据库的不同部分 主要由查找函数完成 计算域内路由 通过对所接入的区域利用Dijkstra算法建立最短路径树生成域内路由表 计算所用图的来源于路由器LSA和网络LSA中的路由器和链路 计算域间路由 通过搜索汇总LSA计算域间路由表 对区域边界路由器使用主干汇总LSA确定区域到区域的路径 对区域内路由器使用区域汇总LSA确定多个区域边界中的合适路径 采用距离矢量算法选择路径 检查传输区域的汇总LSA 对连接非主干区域的区域边界路由器进行传输区域的汇总LSA检查 以便发现是否有比最短路径树计算和域间路由计算所得结果更好的路径 计算AS外部路由 通过查看AS外部LSA 可以计算到达AS外部目的的路径 每个AS外部LSA被依次考虑 当可以通过多个区域到达同一个AS边界路由器 或有多个AS边界路由器可达同一个外部目的时 非主干网的区域路径始终是最高优先级 第四章IP路由 4 2 3IS IS IS IS IntermediateSystemtoIntermediateSystem 是OSI的无连接网络路由协议 ISO规定 一个路由器就是一个IS 一个主机就是一个ES 处理过程 IS IS与OSPF很相似 利用链路状态协议数据单元LSP来同步区域内路由器的链路状态数据库 用Hello报文建立和维护邻居关系 通过交换LSP摘要判断LSP的新旧 并发出更新请求和响应 IS在事件触发下生成新的LSP并向所有邻居扩散 接收到更新LSP的路由器对其进行标记 以便确认 然后继续扩散 分级路由体系 IS IS路由域中 大的路由域被分为若干区域 区域内的路由为一级路由 区域间的路由为二级路由 与之相应 IS分为L1和L2 L1仅了解本区域的拓扑结构 不识别区域外的目标地址 将其转发给区域内的L2处理 L2了解区域间的拓扑结构 OSPF中的区域边界路由器在IS IS中成为L1 L2 L1 L2维护两个路由级别链路状态数据库 分别计算L1和L2拓扑的最短路径树 但是L1 L2不通告L2的路由信息给L1 故L1不知道区域外的路由信息 支持 IS IS对IP路由提供支持 既支持IPv4 也支持IPv6 IETF在RFC3784 IS IS流量工程扩展 和 IS IS支持无特征多协议标签交换扩展 中定义了许多用于IS IS发布流量工程用的新的数据结构 第四章IP路由 BGP4 消息 设置了4种消息进行信息交换 以及维护路由信息状态 利用TCP实现消息的可靠传递 4 2 4BGP 当前Internet核心路由协议是边界网关路由协议BGP4 扩展后的BGP4为BGP4 其支持IPv6 IPX等网络层协议 对等体 两个相互间构成BGP4 路由协议连接的一对或多对路由器 BGP4 又分为外部EBGP4 和内部IBGP4 同一AS内 4 2 4 1基本概念 BGP4 选路原理 采用距离矢量协议 每个节点根据下游节点传送的路由信息进行路由计算 并将结果继续传递给上游节点 利用AS号列表 路径向量 作为距离选择最佳路由 同时 也可以避免路由环路 第四章IP路由 4 2 4 2BGP4 有限状态机 第四章IP路由 4 2 4 3路径属性 路径属性是BGP的重要组成部分 BGP路由器将自己所处AS内的子网 链路状态等参数信息写入UPDATE的路径属性部分 传递给对等体 第四章IP路由 4 2 4 4路由更新 BGP4 路由信息库包含3个部分 其转换过程如下 计算优先级 对本地新的路由和邻居传来的路由计算优先级 并且存入Adj RIB in 策略信息的确切特性和相关计算是本地问题 路由选择 对当前Adj RIB in中的所有路由判断 选择 并且将选定的路由存入Loc RIB 而不用的路由从Loc RIB删除 这需用到路径属性中的多项参数 同时遵循一定的原则 多条相同优先级路径只选其一 路由分发 负责发布Loc RIB中的路由信息到所有的对等体 涉及内容 内部更新 发布信息到对等IBGP4 外部更新 发布信息到对等EBGP4 控制路由流量开销 减少UPDATE占用的带宽及决策占用的CUP能力 路由信息有效组织 路由信息简化 聚合路由信息 路由选择标准 不产生路由环路和稳定可行的路由 有以源为根的树 第四章IP路由 4 2 4 5出错处理 BGP4 路由检测到错误立即发送NOTIFICATION 并关闭BGP连接 4 2 4 6IBGP4 与IGP同步 BGP4 必须在IGP建立了内部路由后 才能向外部通告穿越路径 第四章IP路由 解决方案 在AS内部建立IBGP4 的全连接 或者向AS内部IGP注入BGP4 路由 由于BGP4 路由数量巨大 注入方式会造成内部路由器巨大开销 可有选择地注入 4 2 4 7路由反射器 问题 一个N个IBGP4 网络中 需要N N 1 2个连接来建立全连接 解决方法 在一个AS内指定一个路由器作为IBGP会话中心 路由反射器 其他IBGP路由器只与路由反射器进行对等化 只需 N 1 个连接 4 2 4 8联盟 其作用与路由反射器一样 将一个大的AS划分为若干Sub AS 各个Sub AS之间运行EBGP4 Sub AS内部运行IBGP4 拥有划分了Sub AS的源AS则成为联盟 4 2 4 9路由衰减 只选择性能好的路由对外通告 抑止大量路由信息进入网络占用资源 第四章IP路由 4 3 1概述 特性 实现一对多的传输 非广播 使网络负载减少到最小 小于多次单点传输或泛洪 允许资源发现 组成员自动加入和撤出 4 3 1 1编址 4 3 1 2动态登记 IGMPv1 加入 主机可主动申请 维护 路由器定期查询 脱离 路由器一定时间无回应接收 则删除端口 IGMPv2 增加了主机主动脱离报文 IGMP侦听 交换机检查含有IGMP帧的端口 然后 在过滤表中创建添加记录项 交换机CPU负荷大 GMRP 在网卡驱动中实现 主动向邻居交换机发出GMRP登记消息 告知 发往M组的帧给我 撤销过程类似 第四章IP路由 4 3组播路由 4 3 2组播路由算法 问题描述 根据网络拓扑结构和当前网络状态 构造一棵包含组成员节点的 满足约束条件 时延 带宽 丢失率等 的最优组播树 最短路径树 从源到每个接收节点的路径都是两者之间的最短路径的树 可以解决树约束问题 如Dijkstra Bellman Ford 最小生成树 连接图中的所有节点 并且树枝的全部权值之和最小的树 可以解决树的优化问题 如Prim Kruskal Prim算法的执行非常类似于寻找图的最短通路的Dijkstra算法 在算法的每一步 树中的结点确定了图的一个割集 并且通过该割集的轻边 权值最小的边 被加进树中 第四章IP路由 KMB算法是一种基于最小生成树的启发式算法 1 从网络的拓扑图G中构造组成员节点的完全距离图H 2 计算图H的最小生成树U 3 把U中的边替换成G中的最短路径 得到一个连接子图V 4 对V求最小生成树T 5 删除T中不包含组成员的叶节点 Steiner树 只需求出连接网络中部分节点 组成员 的代价最小的组播树 通常Steiner树问题是NP难度问题 只能求得近似解 约束Steiner树 Steiner树问题可以被扩展包括其他约束条件 如时延 时延抖动等 但仍然属于NP难度问题 有许多启发式方法求解近似最优组播树 最大带宽树 使用类Dijkstra算法计算源到所有接收者的最大带宽路径 然后 构造一个最大带宽树 第四章IP路由 4 3 3组播路由协议 泛洪与剪枝 4 3 3 1域内组播路由协议 DVMRP 距离向量组播路由协议为每个源构造一棵组播树 利用RIP协议实施泛洪和剪枝 需进行反向路径检查 实现容易 但第一个分组需在整个网络中扩散 扩展性不好 不支持QoS MOSPF 最短路径优先多播协议为每个源构造一棵组播树 使用一个新的LSA对OSPF数据库进行补充 利用OSPF协议反向路径检查 实施泛洪和剪枝 当第一个组播分组到达时 路由器本地构造有源树 不需分组扩散到全网 但是计算量相当大 扩展性不好 两层结构只能部分改进路由计算问题 CBT CoreBasedTree 构造一棵所有组成员共享的组播树 路由器只需为每个组播组维护一个状态即可 不采用反响路径检查 使用路由表获得通往核心的下一跳 独立于路由协议 交换RPDU 构造CBT的步骤 1 定位核心 2 新成员利用最短路径向核心发送 Join 经过的路由器记录这一状态 3 核心或CBT成员收到 Join 沿反向路经发回 Join ack 所有经过的路由器生成组播记录 增加一个树的分支 CBT通过Join和Join ack保证不出现环路 允许组播分组不经过核转发 双向共享树 第四章IP路由 计算Steiner树以及选择核心本身就是一个NP难度问题 不支持QoS路由和策略路由 多核心的方案不理想 PIM DM 协议无关的组播密集模式是专门针对具有大量组成员的组播设计的 与DVMRP类似 但独立于路由协议进行反向路径转发检查 直接检查路由表去往源节点的端口是否是接收分组的端口 然后实施转发 剪枝 或者丢弃操作 构造有源树 PIM SM 协议无关的组播稀疏模式是专门针对组成员不集中分布的组播设计的 与CBT类似 但PIM SM中 源发送的分组必须先发给汇聚点RP 核心 如果源节点发送分组速率超过特定阈值 可以使用有源树替代RP共享树 MIP MulticastInternetProtocol中组播树构造既可以从源节点发起 小组播组 也可以从接收方发起 有大量接收者 MIP不需预先配置核心 共享树以源节点或接收节点为根 使用双向共享树 MIP独立于协议 采用扩散机制 发送请求 等待确认 来与邻节点交互构造树 修改树 提出MIP的主要目的是在单播路由表出现短暂不一致时 仍可以构造无环路的组播树 第四章IP路由 4 3 3 2域间组播路由协议 PIM DM PIM SM 利用PIM DM建立有源树进行域内组播路由 利用PIM SM建立共享树进行域间组播路由 该方案适用于企业级网络 不适合应用于Internet 因为发布RP和维护软状态需消耗大量网络资源 且该方案不支持策略路由 MSDP 是一种过渡方案 MulticastSourceDiscoveryProtocol不够造域间共享树 每个域的RP都和某些其他域的RP建立MSDP会话 为自己内部的组成员找到位于其他域的源节点 其特点是实现简单 采用反向路径检查来提高鲁棒性 BGMP 是一种长远方案 可以和任何一种域内组播路由协议协同工作 BGMP使用BGP路由表构造连接各个域内组播树的域间双向共享树 类似于CBT 但根为某个域 域边界路由器即运行BGMP 也运行MIGP MIGP将域内成员的变化通知BGMP 触发加入或剪枝操作 BGMP中 根域的选择对性能很大 EXPRESS EXPlicitRequestedSingleSource是介于网络层组播和应用层组播之间的策略 EXPRESS中 主机向网络发送明确的订阅请求来申请接收组播信道 S E 的数据 而只有组播信道的源可以向信道发送数据 订阅和退订的过程类似于CBT的加入和离开 只是订阅消息向源传播 且可以认证 MSDP操作过程 1 组播源在域内使用PIM SM方式发送组播分组 2 本域的RP向其MSDP对等体发送活动源SA消息 3 收到SA的对等体利用BGP4 路由表反向路径检查 4 收到SA的对等体检查自己域内是否有对应的组成员 如果有 RP触发一个加入消息发往组播源 建立源节点域与本域之间的组播树分支 5 如果SA消息中包含数据 RP在本域组播树中转发数据 6 重复3 5步骤 直到所有MSDP对等体都收到SA消息 以及所有组成员都收到源节点数据为止 问题 只要源节点发送组播数据 对应的RP就要周期性发送SA 这个周期的选择是一个很重要的问题 第四章IP路由 4 3 4可靠组播 4 3 4 1基本概念 可靠性 所有组播数据最终都能够正确传送给每个接收者 评估指标 出错率 误码 失序 丢失率 超时 被丢弃 半可靠性 通常用于可容忍一定数据丢失率的实时组播应用 时间限制可靠性 适用于实时性要求高的组播应用 完全可靠性 适用于正确性要求高 实时性不强的组播应用 可靠性组播需要解决的问题 不再是一对一的端可靠性 而是一对多 多对多的关系 需要不同机制来满足不同应用对可靠性的不同要求 一对多和多对多会导致大量的TCP的Ack数据包 即 Ack 风暴 这给发送者和网络都带来极大的资源消耗 过多的远程差错恢复过程对实时性组播应用的效率 以及网络带宽的占用都产生严重影响 第四章IP路由 4 3 4 2重传情求ARQ 4 3 4 3前向纠错FEC FEC通过在传输中引入冗余码来提高可靠性 传输层FEC利用丢失校正码和已知包数来处理丢失情况 一旦网络传输质量不好 FEC不能保证绝对的可靠性 4 3 4 4ARQ和FEC组合应用 可实现高可靠性 但是具体实现难度和计算复杂度都较大 4 3 4 5差错恢复 通过设置分布式的重传代理来提高重传效率 以及减轻网络流量负荷 第四章IP路由 4 4 1任意播定义 任意播 选播 是指源主机报数据传输给任意播地址表示的一组主机中 最近 的一台主机 4 4 2任意播策略 网络层任意播 IPanycast基于网络拓扑结构信息来确定接收分组的服务器 如最小路由代价 应用层任意播 Applicationlayeranycast基于应用参数确定接收分组的服务器 如处理器能力 响应时间 请求连接数量等 4 4 3优点与作用 1 简化配置 2 提高网络可靠性 3 负载均衡 4 4 4涉及的问题 1 地址空间 4 组成员通告2 路由 5 TCP重定向 3 局域网通信 6 全球IP任意播 第四章IP路由 4 4选播