计算机网络 第五章网络层.ppt

第五章网络层 网络层设计的有关问题路由选择算法拥塞控制算法网络互联因特网上的网络层 网络层 端到端数据传输的最低层 网络层负责把源计算机发出的信息分组经过适当的路径送到目的计算机 网络层需要了解通信子网的拓扑结构 选择合适的传输路径 网络层要预防和控制通信子网中超量的信息分组造成的拥塞 网络层还要处理不同网络中源端和目的端之间的差异 5 1网络层设计的有关问题 对网络层所提供的服务存在着两种观点 面向连接的服务 复杂的功能放在通信子网中 无连接服务 复杂的功能放在两端主机中 网络层的内部结构 网络层提供的服务是否可靠与有无连接并没有关系 理论上存在四种组合 但最重要的只是其中的两种组合 可靠的面向连接服务 不可靠的无连接服务 针对两种服务 网络层有两种不同的工作方式 虚电路 virtualcircuit 方式 当建立连接时 从信源到信宿的路由就作为连接建立的一部分加以保存 此路由用于传输连接上的所有数据 当释放连接时 虚电路也随之撤消 数据报 datagrams 方式 不预先选择路由 发出的每个分组所选择的路由独立于其前面发出的分组 后续的分组可以走不同的路由 比虚电路方式更健壮 更容易处理传送失败和拥塞 虚电路与数据报的比较 5 2路由选择算法 路由选择是网络层的主要功能 负责为分组选择合适的转发路径 路由选择算法应具有以下几种特征 正确性 correctness 简单性 simplicity 健壮性 robustness 稳定性 stability 公平性 fairness 和最优性 optimality 一个好的路由选择算法是兼顾某几种重要的性能指标 路由选择算法的分类 分为两大类 非自适应算法 non adaptivealgorithm 也叫静态路由选择 staticrouting 预先离线计算好路由表 在网络启动时装入到路由器中 在网络运行过程中不会根据网络流量和拓扑结构的变化而改变 简单 自适应算法 adaptivealgorithm 也叫动态路由选择 dynamicrouting 根据当前网络流量和拓扑结构的变化 动态在线地计算网络的路由 复杂 健壮 网络负担重 最佳原理和接收树 当计算两点之间的最佳路由时 存在一个最佳原理 optimalityprinciple 如果j位于i到k的最佳路由上 则j到k的最佳路由也必定落在该路由上 可通过反证求得 根据最佳原理可以推出 所有源节点到一个给定目的节点的最佳路由的集合组成一棵以该目的节点为根的树 称为该目的节点的接收树 sinktree 接收树并不是唯一的 所有的路由算法都是要试图找出各个目的节点的接收树 并利用这些接收树来转发数据 最短通路路由选择算法 最短通路 shortestpath 路由选择算法属于自适应路由算法 它将一个通信子网抽象成一张图 图中的顶点代表网络节点 路由器 弧线代表通信线路 弧线上的权代表相邻顶点间的 距离 可为物理上的距离 或指分组在其间的传输时间 也可指线路上的通信费用等 任意一对顶点之间的最小权值即为它们的最短通路 求任意一对顶点之间的最短通路可有很多方法 其中迪杰斯特拉 dijkstra 提出了按通路长度递增的次序产生最短通路的算法 基本思想为 首先从起始点出发 找出距起始点最近的结点 然后以此结点为基础找出距起始点次近的结点 如此每次都找出比前一次短的通路 直至某个通路到达给定的目的 这时所得到的通路就是源到目的的最短通路 具体可采用标记方法 利用dijkstra算法求a到d的最短通路 扩散法 flooding 扩散法为静态算法 也称洪泛式 基本思想 路由器将收到的每个分组 从除了分组到来的线路外的所有输出线路上发出 可靠性高 但容易造成网络拥塞 改进办法有 在每个分组头中增加一个站点计数器 hopcounter 每经过一个站点 计数器减1 当计数器减为0时 就扔掉分组 计数器的值可设置为源到目的的长度或子网的直径 记下分组扩散的路径 确保分组只转发一次 可以让源路由器对来自主机的每个分组设置一个序号 每个路由器对应于每个源路由器都有一张表 用来记录已转发过的分组 源路由器和序号 选择扩散法 floodselectively 只转发到与正确方向接近的那些线路上 适用于负荷轻的小规模网络以及特别强调健壮性的网络 基于流量 flow based 的路由选择 一种既考虑拓扑结构又兼顾载荷的静态路由选择算法 基本思想 利用已知的载荷平均流量 计算出该线路上的平均分组延迟 由所有线路的平均延迟 计算出整个网络的平均分组延迟 从而找出具有网络最小延迟的最优路由选择算法 采用这种技术必须预知的几种信息 网络的拓扑结构给出通信量矩阵fij各线路容量的矩阵cij选定一种路由选择算法 从源端i到目的端j的项表示从i到j的通信路由和从i送到j每秒钟的分组数量 基于流量路由选择的示例 线上的数值表示各方向的容量ci 单位为bps 通信量的数学分析 计算每条线路总通信量 i 例 1 ab 9 4 1 14 设分组平均长度为1 在这里假定为800位 则每条线路上分组的容量为 ci 单位为分组 s 例 c1 20kbps 则 c1 20k 800 25分组 s 由队列原理导出每条线路的平均延迟 包括排队时间和服务时间 ti ci i 1如 t1 25 14 1 91ms设每条线路的权值 i i i 即在总通信量中使用该线路的比例 如 1 14 14 12 6 11 13 8 10 8 14 82 0 171则整个网络的平均延迟时间为 i ti 即所有线路的加权延迟和 本例中为86ms 距离矢量路由选择 距离矢量路由选择 distancevectorrouting 算法是现代计算机网络两个最常使用的动态路由选择算法之一 最初用于arpanet decnet novell的ipx以及internet的一种内部网关协议 igp interiorgatewayprotocol 都使用了称作rip routeinformationprotocol 的距离矢量路由选择算法 cisco则开发了一种改进的协议 叫作igrp interiorgatewayroutingprotocol 基本思想 每个路由器维护一张 矢量 表 表中给出到每个目的节点已知的最佳距离和路径 每个路由器还不断测试到达相邻路由器的距离 相邻的路由器之间也不断地相互交换矢量信息 这样每个路由器将测试出的到达相邻路由器的距离加上相邻路由器给出的矢量信息 就可得知通过相邻路由器到达每个目的节点的距离 选择最佳路径更新表的信息 距离矢量路由选择示例 无穷计算 count to infinity 的问题 dvr算法收敛慢 其时间复杂度为o n3 特别是它对好消息的反应迅速 但对坏消息却反应迟钝 其对坏消息的反应迟钝 会造成相互交换的矢量信息错误 最终导致无穷计算的后果 在实际使用中 可通过设置距离的最大值 如设置为网络最长路由加1 来扼制这种无限的增长 x 链路状态路由选择 链路状态路由选择 linkstaterouting 算法1979年出现在arpanet上 作为一种用来取代dvr的动态路由选择算法 之后得到了广泛的应用 基本思想 通过各个节点之间的路由信息交换 每个节点都可获得关于全网的拓扑信息 即所有的节点 各节点间的链路连接和链路的代价 时延或费用等 可将这些拓扑信息抽象成一张带权无向图 然后利用最短通路路由选择算法计算出到各个目的节点的最短通路 链路状态路由选择算法的步骤 找出所有可达的相邻节点及它们的网络地址 测定到这些相邻节点的代价 将以上信息构成链路状态分组 linkstatepacket 向网上所有节点发送链路状态分组 利用收到的链路状态分组计算到各目的节点的最短通路 1 了解相邻节点每个路由器启动后 首先在所有与之相连的点 点线路上发送一个特殊的询问分组 hello分组 线路另一端的路由器收到后必须发回一个响应来告知它是谁 其网络地址 2 测量线路代价 cost 路由器在链路上发送一个要求对方立即响应的特殊回声 echo 分组 将回声分组的来回时间除以2即得到该链路的延迟时间 代价 一般重复若干次 取平均值 3 构造链路状态分组每个链路状态分组包括源节点的网络地址 分组的序号和寿命 然后是一系列相邻节点的网络地址和去往该节点的链路代价 决定何时创建链路状态分组一般有两种方法 定期创建链路状态分组 探测到网络连接发生变化时再创建链路状态分组 4 发送链路状态分组通过改进的扩散法 记录分组扩散路径 每个路由器维护一张带有源节点和最大分组序号的表 对来自于同一个源节点的重复分组 分组序号 表中序号 不转发 向网上所有其它节点发送链路状态分组 所有的链路状态分组都要应答 当线路空闲时 从缓冲区中选择发送一个分组或应答 为了保证高效可靠地发送链路状态分组 需采取如下一些措施 将分组序号长度设为32位可防止序号重叠太快 若每隔1秒发送一个分组 可发137年不重复 为每个分组规定一个寿命 分组在路由器中时 其寿命每隔1秒就减1 直到减为0被抛弃 可解决路由器崩溃及分组序号传输出错等造成新旧分组不分的问题 前图中路由器b的分组缓冲区 包含新近到达还未处理完毕的分组 5 计算新的路由当一个路由器收集齐了所有的链路状态分组后 便可构造出整个网络的拓扑带权图 通过最短通路路由选择算法就可确定到达所有其它节点的最短路径 将此结果存入路由选择表中达到更新目的 链路状态路由选择算法的总结 优点 可靠性极高 因为构造网络拓扑的信息来自于各个节点亲自的探测 最佳的路由 根据当前整网的拓扑信息计算出的 缺点 每个节点需要大的存储空间来存放其它所有节点发来的链路状态分组 路由计算时间较长 以上两点特别在网络规模很大时更加突出 链路状态路由选择算法在实际网络中运行得很好 使用非常广泛internet上广泛使用的ospf openshortestpathfirst 协议为decnet设计的 后被iso采纳的is is intermediatesystemtointermediatesystem 协议 分级路由选择 hierarchicalrouting 将网络分成一些区域 每个区域内的路由器只负责本区域内的分组转发 而不管其它区域的情况 目的地址不在本区域内的分组都发给指定的区域路由器去处理 当网络规模很大时 往往需要分成多级 路由信息的交换只在本区域内进行 路由器内部需存储的路由信息大大减少 节省了路由器的存储空间和网络带宽 缺点是选择的路由可能不是最佳的 分级路由示例 移动主机 mobilehost 的路由选择 移动用户 mobileuser 都有一个不变的永久性主方位 homelocation 用一个永久性的主地址 如手机号码 来确定 用主地址作为动态用户在系统中的路由选择目标 在找到用户后 再将分组发送到用户所在的任何地方 移动主机的定位 世界按地理位置被分成许多小单元 通常是一个lan或无线单元 称作区域 包含有 一个或多个外地代理 foreignagent 用来管理所有来到当地的动态用户 一个本地代理 homeagent 用来管理原本属本区域 但当时正在外地的用户 当一个移动用户进入某区域时 移动主机和外地代理通过广播分组取得联系 移动主机向外地代理登记注册 给出其原来所在地的地址 当前数据链路层地址以及一些安全性信息 外地代理与移动主机的本地代理取得联系 发出诸如外地代理的网络地址 安全信息等信息 本地代理检查安全信息 验证通过后应答外地代理 外地代理得到本地代理确认后 在其表中开设一个表项 通知移动主机已经登录注册 当一个移动用户离开某区域时 应退出登录 移动主机的分组路由传递 广播 broadcast 路由选择 将分组同时发往所有节点称作广播 broadcasting 有多种方法实现广播发送 发送站给每个目的站点都单独发送一个分组 浪费带宽 采用扩散法 产生太多的分组 消耗太大的带宽 多目的路由选择算法 每个分组携带一个欲去往的目的地址列表 每个路由器根据目的地址列表确定一组输出线路 修改目的地址列表转发分组副本 在一条输出线路上只有一个分组 节省带宽 使用以发送站为根的生成树来转发分组 分组副本最少 占用带宽最小 但需每个路由器了解全网的拓扑结构并构造出生成树 逆向路径转发的广播路由 逆向路径转发 reversepathforwarding 的思想 当一个广播分组到达时 路由器检查其源地址和输入线路 若输入线路是从该路由器去往源地址的最佳路径 则将该分组在除输入线路以外的所有输出线路上转发出去 否则将其丢弃 相比前四种方法 既合理有效 又易于实现 多点播送 multicast 路由选择 向处于网络中不同位置的一组 部分 用户广播 称为多点播送或组播 需要路由器知道哪些用户加入哪些组以及用户何时加入或离开这个组 路由器通过计算得到覆盖整个子网的生成树 再根据组的成员修剪出各组的生成树 多点播送分组仅沿相应生成树转发 a 一个子网 b 最左边路由器的生成树 c 小组1的多点播送树 d 小组2的多点播送树 5 3拥塞控制 拥塞当大量分组进入通信子网 超出了网络的处理能力时 就会引起网络局部或整体性能下降 这种现象称为拥塞 拥塞不加控制地发展下去 最终导致网络通信停顿 有效吞吐量为零 即阻塞 拥塞产生的原因短时间内进入网络的分组数量过多 局部问题导致性能下降 多个输入对应一个输出 慢速处理器 低带宽线路 解决办法针对某个因素的解决方案 只能对提高网络性能起到一点点好处 甚至可能仅仅是转移了影响性能的瓶颈 需要全面考虑各个因素 拥塞控制 拥塞控制与流量控制的差别拥塞控制 congestioncontrol 需要确保通信子网能够承载用户提交的通信量 是一个全局性问题 涉及主机 路由器等很多因素 流量控制 flowcontrol 与点到点的通信量有关 主要解决快速发送方与慢速接收方的问题 是局部问题 一般都是基于反馈进行控制的 拥塞引起网络性能下降 拥塞控制的基本原理 根据控制论 拥塞控制方法分为两类开环控制 拥塞预防 通过好的设计来解决问题 避免拥塞发生 拥塞控制时 不考虑网络当前状态 闭环控制 拥塞解决 基于反馈机制 工作过程监控系统 发现何时何地发生拥塞 把发生拥塞的消息传给能采取动作的站点 调整系统操作 解决问题 拥塞控制的基本原理 衡量网络是否拥塞的参数缺乏缓冲区造成的丢包率 平均队列长度 超时重传的包的数目 平均包延迟 包延迟变化 jitter 反馈方法向负载发生源发送一个告警包 包结构中保留一个位或域用来表示发生拥塞 一旦发生拥塞 路由器将所有的输出包置位 向邻居告警 主机或路由器主动地 周期性地发送探报 probe 查询是否发生拥塞 拥塞控制算法 拥塞预防策略开环控制影响拥塞的网络设计策略 通信量整形和通信量管制 通信量整形 trafficshaping 迫使分组按预定的速率进入网中 避免突发性的大通信量造成网络瞬间过载 广泛用于面向连接的工作方式 如atm 通信量管制 trafficpolicing 网络对用户的通信量进行监视 对遵守约定的用户 保证其要求的服务 对违反协议的数据采取惩罚措施 如丢弃 降低优先级 不保证服务质量等 以上方法一般用于以虚电路方式工作的网络层 在建立虚电路的时候由双方协商而定 在数据报子网上实现比较困难 但可应用于传输层的连接中 漏桶 leakybucket 算法 在主机和网络之间接入一个 漏桶 固定长度的分组队列 无论主机以多大的速率发送分组 漏桶 中的分组总是以恒定的速率注入网中 若主机发送过快 当 漏桶 满了以后 多余的分组即被丢弃 令牌桶 tokenbucket 算法 令牌桶算法能较快地响应突发数据的到来 且不会丢失数据 令牌桶中每隔定长的时间产生出一个令牌 计数器 当桶装满后 随后产生的令牌就被丢弃 分组在桶外的缓冲区中等待发送 桶中有多少令牌就允许发送多少个分组 每个令牌用后即销毁 当桶中没有令牌时必须停止发送 为了平滑大量突发数据的出现 可在令牌桶后面增加一个漏桶 使得漏桶的速率大于令牌桶但小于网络的峰值速率 a 漏桶的输入 b 漏桶的输出 c e 一个具有250kb 500kb和750kb容量的令牌桶的输出 f 一个500kb令牌桶接一个10mb s漏桶后的输出 流说明 流说明用于描述通信量的注入模式和服务质量的衡量标准 流说明既可适用于虚电路上传送的分组 也适用于从源端到目的端传送的数据报序列 流说明的例子 拥塞的解决 虚电路子网中采用许可控制 admissioncontrol 的三种策略 一旦出现拥塞的信号 就不再创建任何虚电路 直至拥塞解除 允许建立新的虚电路 但要仔细选择路由 以便所有新的虚电路绕过拥塞的区域 在虚电路建立时 子网与主机对所需服务质量进行协商 若不能满足主机最低要求 则拒绝建立连接 否则就保留连接所需的多种资源 避免拥塞发生 抑制分组 chokepacket 每个路由器监视本节点的资源利用情况 若某个方向的资源利用率超过一定的门限 则该路由器向有关源节点发送抑制分组 源节点相应减少发往该方向的数据量 直至该方向的拥塞解除 为了公平合理地控制引起拥塞的源节点的行为 可采用加权公平队列 weightedfairqueuing 在 高速的 wan中为了及时解脱拥塞 可以上游使用更多的缓存为代价 这种方法称为站到站抑制分组 a 一个仅影响源端的抑制分组 b 一个影响沿途所有站点的抑制分组 负载丢弃 loadshedding 在没有办法消除拥塞时 只能采取极端措施 即丢弃部分的分组来解决拥塞 为了使网络能合理地丢弃分组 应用程序应对各分组标注优先级别 以便有选择依据 延时差控制 为满足音频或视频数据流传输时对延时变化的敏感性 需要对传输延迟进行控制 以保证可接受的最大延时差 通过在沿途经过的路由器中计算分组传输的延迟 与预期的传输平均延迟之差决定其在输出队列中的优先次序 能够有效的减小传输延迟差 多点播送的拥塞控制 多点播送要实现多个源端到多个目的端的分组传输流 其拥塞控制必须适应目的端的不断变换 加入不同的多点播送组造成的带宽需求变化 rsvp资源重复利用协议 根据接收者向上传送至发送者的带宽保留消息 沿途设置从源到目的的多点播送树的带宽预留 接收者可同时声明一个或多个想接收的源并在其中自由切换 各个路由器利用这些信息来优化整体带宽使用计划 a 一个网络 b 主机1的多点播送生成树 c 主机2的多点播送生成树 a 主机3申请一条到主机1的通道 b 主机3申请又一条通道 到主机2 c 主机5申请一条到主机1的通道 5 4网络互联 各种不同标准 不同拓扑 不同体系结构 不同协议的异型网络的互联 连接不同网络的设备统称 网关 gateway 用来在不同网络之间对数据进行转换 网络互联设备 根据其工作层次的不同 分别称为 中继器 repeater 在物理层上再生放大物理信号 网桥 bridge 在数据链路层上 采用存储 转发方式对数据帧进行传递 多协议路由器 multiprotocolrouter 类似网桥 但工作在网络层 转发分组时要进行路由选择 对连接的不同网络还要进行不同协议的转换 传输网关 transportgateway 用来建立两个网络间的传输连接 应用网关 applicationgateway 在应用层上进行协议转换 半网关 网关可从中间分成两部分 每个部分称为一个半网关 每个网络都拥有和管理一个半网关 半网关之间用无源的导线相连 两个半网关的接口处使用相同的中间协议进行网络互连 网络的差异造成互联的问题 不同类型的网络 其差异可能表现在许多方面 完全消除这些差异是不可能的 网络互联只能尽力而为 网络互联的两种形式 面向连接的级联虚电路 concatenatedvirtualcircuits 无连接网络互联 connectionlessinternetworking 级联虚电路 从信源到信宿的虚电路穿越沿途各网络及网关 其建立方式同普通虚电路一样 只是对连接不同协议网络的多协议路由器要求进行协议转换 无连接网络互联 网络层只提供最简单 最基本的数据报传输服务 无连接 独立路由 不可靠 无序 隧道 tunneling 实际上要转换两种不同协议的网络是很困难的 甚至不可能 有一种特殊情况 当信源和信宿都处在同一类型的网络中 而这两个网络又通过另一种类型的网络进行互联 可采用挖隧道方式简单巧妙地解决协议的转换 在挖隧道方式中 实际并没有进行任何的协议转换 只是将被传输的数据分组作为中间网络分组承载的数据 穿越过去 互联网络的路由选择 互联网络的路由选择分成两个层次 单个网络内部的路由选择 其路由选择算法称为内部网关协议igp interiorgatewayprotocol 每个网络都是一个独立的自治系统as autonomoussystem 可使用不同的路由算法 网络间的路由选择 其路由选择算法称为外部网关协议egp exteriorgatewayprotocol 可能涉及到不同网络协议的转换 需要时使用隧道技术 另外在费用 业务类型 服务质量 甚至政治因素等方面都较为复杂 分段 fragmentation 不同的网络的分组长度是不一样的 当一个大分组穿越分组定义较小的网络时 网关必须将一个大分组划分成若干个小的段 fragment 把各段作为单独的分组进行发送 透明分段 在中间网络进出时分别进行分段和重组工作 每个小分组须含有计数字段或分组结束标志以便出口网关重组 所有分组必须经同一网关发出 不透明分段 中间网关不重组各分段 每个分段的分组都作为单独原始的分组独立传递 最后在目的地主机上进行重组 分组的重组 reassembly 分段的编号 头中包含 分组编号 分组中首分段的编号 分组结束标志位 防火墙 firewall 防火墙设有过滤分组的网关 只有检查合格的数据才能进出网络 由两部分组成 两个用作进出分组过滤的路由器和一个用于对数据内容进行检查的应用网关 5 5因特网上的网络层 因特网 在网络层 可以看作是一组由主干连接在一起的多个自治系统 autonomoussystem 子网 ip协议是连接因特网的网络层协议 ip internetprotocol 分组的头 internet网络层协议 ip头包括20个字节的固定部分和变长 最长40字节 的可选部分 从左到右传输 版本域 version ihl ip包头长度 最小为5 最大为15 单位为32 bitword 服务类型域 typeofservice 3个优先级位 3个标志位 d delay t throughput r reliability 2个保留位 目前 很多路由器都忽略服务类型域 总长度域 totallength 标识域 identification df don tfragment 所有机器必须能够接收小于等于576字节的段 mf morefragments 除最后一个段外的所有段都要置mf位 internet网络层协议 段偏移量 fragmentoffset 除最后一个段外的所有段的长度必须是8字节 基本段长 的倍数 onelargedatagrambecomesseveralsmallerdatagrams internet网络层协议 生存期 timetolive 实际实现中 ip包每经过一个路由器ttl减1 为0则丢弃 并给源主机发送一个告警包 协议域 protocol 上层为哪种传输协议 tcp udp 头校验和 headerchecksum 只对ip包头做校验 算法 每16位求反 循环相加 进位加在末尾 和再求反 源地址 sourceaddress 和目的地址 destinationaddress internet网络层协议 选项 options 变长 长度为4字节的倍数 不够则填充 最长为40字节 ip地址 一些特殊的ip地址 ip子网 子网掩码 subnetmask 将ip地址分为子网地址和主机id两部分 例如 掩码255 255 252 0使得一个b类地址包含64个子网 每个子网最多容纳1022个主机 130 50 4 1 130 50 7 254130 50 8 1 130 50 11 254 130 50 64 1 130 50 67 254 因特网控制协议 因特网控制消息协议icmp internetco