网络通信与OSI_5.ppt

第四章回顾 停等应答协议连续应答协议数据流控制HDLCInternet中的数据链路层 数据链路层是对物理层传输的原始比特加以编码和控制 以便为网络层提供一条无错 有序和透明的链路 网络层主要功能 支持网络连接的实现和向传输层提供各种服务 路径选择和中继功能 网络连接的建立 支持和释放功能 多路复用 数据单元的交换 其它功能 第五章 网络层及PDN 主要内容 路径和路径选择拥挤控制和死锁公用数据网络数据报和虚电路的实现 一 路径和路径选择 路径选择 在存贮 转发网中 源节点和中间节将信息包引向目的节点而其后继节点进行的选择 案列 某地区由A B C D E F G和H等7个城市组成 各城市节点分别由下列航空 铁路和公路组成交通网 1 航空 AC ED2 铁路 AB BC CD3 公路 AF FE EC CD E G E H 问题1 请绘制该城市的交通网拓扑图 注意标出线路运行方向 问题2 请找出从A到达D的交通线路 问题3 请找出从A到达D的最佳交通线路 问题3 请问G节点是否可达 问题4 请问H节点是否可达 路径选择算法的基本要求 算法必须是正确稳定和公平的算法应该尽量简单算法能够适应网络拓扑和通信量的变化算法应该是最佳的 算法涉及的主要参数 跳数 hopcount 分组从源结点到达目的结点经过的路由器的个数 tracert 带宽 bandwidth 链路的传输速率延时 delay 分组从源结点到达目的结点花费的时间 ping 负载 load 通过路由器或线路的单位时间通信量可靠性 reliability 传输过程中的误码率开销 overhead 传输过程中的耗费 与所使用的链路带宽相关 分组交付方式 直接交付 如果目的主机与源主机A是连接在同一个网络上 间接交付 如果目的主机与源主机A不是连接在同一个网络上 则由路由器按照转发表指出的路由将数据报转发给下一个路由器 直接交付 间接交付 典型的路由器的结构 路由选择 路由选择处理机 路由选择协议 路由表 3 输入端口 3 交换结构 输入端口 输出端口 分组转发 转发表 分组处理 输出端口 1 1 1 3 3 1 2 2 2 2 3 网络层2 数据链路层1 物理层 路由选择模块与路由表 在每个路由器接收到一个IP分组时 路由选择模块必须进行路由查询 路由器查询的顺序是 第一步是判断该IP分组是不是直接转发 如果不是直接转发第二步确定是不是特定主机转发 如果不是特定主机转发第三步确定是不是特定网络转发 如果不是特定网络转发 最后就要确定是不是默认转发 路由动画 路径选择算法的分类 两大类 静态路由选择算法和动态路由选择算法 非适应性适应性 简单路径选择算法 随机路径扩散路径 站计数法 静态路径 第一次登录法 孤立路径 路径选择算法的分类 适应路径选择算法 集中路径分布路径综合路径 区域0 0 0 1 R2 网1 CC 二 拥挤控制 定义 子网内由于出现过量信息包而引起网络性能 向主机递交的信息包数 下降的现象称为拥挤 产生拥挤的原因 节点执行各种管理操作 使接收速度跟不上发送速度 节点输出信息包的能力小于输入能力引起信息包在缓存器排长队 甚至占满了缓存器 使新到的信息包由于得不到缓存器而丢失 根本原因 缓冲器的安排不当 合理分配缓冲器 拥挤控制 缓冲器预定算法 适合于虚电路传输子网方法 在建立虚电路过程 可在呼叫信息包经过的节点上登记路径选择表出入口 同时预定缓冲器 缓冲器的数量同滑容窗尺寸 特点 降低缓冲器和电路利用率 拥挤控制 分配缓冲器算法 每一根输入线分配一个缓冲器 限制一条输出线的信息包队列长度平分法 某节点有 个缓冲器 根输出线 输入线L 每根输出线的缓冲器 则 L 拥挤控制 分配缓冲器算法 最大分配法 令 max是最大队列长则 Ni为队列i的信息包数一般取如10个缓冲器 3根输入线和3根输出线则3个缓冲器用于输入线 拥挤控制 分配缓冲器算法 最小分配法使每根输出线的缓冲器不少于Bmin特点 避免吞吐量退化 不公平性和直接存贮转发死锁 拥挤控制 许可证算法 思想 向网络发放适量的许可证 每个要发送的信息包必须得到一个许可证方可发送特点 1 可保证全局性拥挤 但不完全消除局部拥挤 2 网内许可证会随系统软件故障而减少 降低吞吐量 拥挤控制 阻塞包算法 设计思想 拥挤控制只有在拥挤时起作用 否则不起作用 设变量u fu 输出线的近期利用率0 u 1f 输出线的瞬时利用率f 0 1令 u au 1 a fu af 1 a ua为u的修改速度 拥挤控制 阻塞包算法 拥挤控制方法 设U0为一阈 即拥挤 1 信息包到达时 检查U U0否 若是 转22 发阻塞包给源点 在信息包上记阻塞包标志 3 源节点若收到阻塞包 减少X 发送信息量速度4 若再收到阻塞包 再减少X 若在定时内无阻塞包 增加X 拥挤控制 限制使用输入缓冲器法 区分进入节点的信息包是从主机来的还是转发的信息包 限制输入缓冲器的使用 三 死锁 定义 死锁是指两个节点相互等待 无法发送和接收信息包 类型 存贮转发死锁重排序死锁重装配死锁 死锁 存贮转发死锁 a 直接存贮转发死锁 b 间接存贮转发死锁 死锁 存贮转发死锁 解决方法 缓冲器分级结构和信息包定向传输法 设信息包传送最大路径数为 存贮送给本地主机每个缓冲器的状态存贮待转发信息 死锁 重排序死锁 原因 在虚电路服务子网中采用不按顺序缓冲的流水线协议时 如 传 解决方法 丢弃目的节点未按顺序排列的信息包分配足够缓冲器 死锁 重装配死锁 传输层送给网络层的长信息 类似上一情况 拥挤控制和流控制的差异 拥挤控制必须确保通信子网能传送该传送的数据 这是全局性的问题 涉及到所有主机 所有通信节点及节点中存贮 转发处理的行为 以及所有将导致削减通信子网负荷能力的其它因素 拥挤控制和流控制的差异 流控制只与某发送者与接收者之间的点到点通信具有关系 它的任务是确保快速发送者不能比接收者能承受的速率更高速度传数据 流控制几乎总是涉及到接收者告诉发送者另一端情况如何的一些直接反馈 四 公用数据网络 定义 向计算机用户提供公共的数据通信服务的计算机网络 它由转接结点机和网络中心等组成 公用数据网络 PSTN与PDN的关系 大多数PDN采用PSTN 通过调制解调器 将结点机 网络控制中心和用户入网设备互连起来进行数据通信 1 为 提供信道资源2 通过 开辟更为广阔的应用领域 公用数据网的特性 协议标准 公用数据网是由 接受的国际标准 主要包括 系列和 系列的通信标准及用户数据速率和用户接口的标准 类型 分组交换数据网络 和电路交换数据网络 协议模型 涉及 参考模型的低三层 特性 为传输层以上各层提供透明的数据传输服务 公用数据网 电路交换 定义 通过直接切换通信线路 进行数据交换的方式称为电路交换 公用数据网 电路交换 特点 信道固定 速率固定 传播延迟长 公用数据网 分组交换 P 定义 在源端把分组信息进行编址 源和目的地址 发往转接节点 并存贮 待有空的输出线再转发 直至目的机 公用数据网 分组交换 P 特点 不需占用整个通信信道 传输速率可变 公用数据网 分组交换和电路交换的比较 不提供差错控制及流控制 提供差错控制及流控制 提供的服务种类较多 数据报和虚电路 提供两类服务 数据报和虚电路数据报服务 在数据报服务控制下 子网接收源节点来的独立信息包 经全称编址后 独自地传输到目的节点 服务质量 无序 无差错控制 虚电路服务 虚电路是网络内一对数据终端之间的逻辑连接 数据交换前 要先建立一虚电路 确定数据交换的路径 服务质量 有序 无错 数据报和虚电路 虚电路与逻辑信道的不同点 1 虚电路是动态建立 动态清除 而逻辑信道即是始终存在的 2 虚电路是端一端的 而逻辑信道只具有本地特性 数据报和虚电路 子网内数据服务的实现 每一节点保存一输出线选择表子网内虚电路服务的实现 子网的每一节点保存一张虚电路的输入输出表 一一对应 虚电路的实现 H1 A D C T1H2 A F E D T2H3 F E D C T1 第五章 网络层第五节 互联网的常用路由协议 有关路由选择协议的几个基本概念内部网关协议RIP内部网关协议OSPF 主讲 蔡伟鸿 计算机网络与通信 5 5 1有关路由选择协议的几个基本概念 1 理想的路由算法算法必须是正确的和完整的 算法在计算上应简单 算法应能适应通信量和网络拓扑的变化 这就是说 要有自适应性 算法应具有稳定性 算法应是公平的 算法应是最佳的 2 关于 最佳路由 不存在一种绝对的最佳路由算法 所谓 最佳 只能是相对于某一种特定要求下得出的较为合理的选择而已 实际的路由选择算法 应尽可能接近于理想的算法 路由选择是个非常复杂的问题它是网络中的所有结点共同协调工作的结果 路由选择的环境往往是不断变化的 而这种变化有时无法事先知道 3 路由算法的自适应性 静态路由是由网络管理员在系统安装时根据网络的配置情况预先设定 网络结构发生变化后由网络管理员手工修改路由表 动态路由是随网络运行情况的变化而变化 路由器根据路由协议提供的功能自动计算数据传输的最佳路径 由此得到动态路由表 4 自治系统AS AutonomousSystem 自治系统 AS 一个自治系统就是处于一个管理机构控制之下的路由器和网络群组 它可以是一个路由器直接连接到一个LAN上 同时也连到Internet上 它可以是一个由企业骨干网互连的多个局域网 在一个自治系统中的所有路由器必须相互连接 运行相同的路由协议 同时分配同一个自治系统编号 自治系统内部使用的内部网关协议IGP IRP RIP HELLO OSPF等自治系统之间使用的外部网关协议EGP ERP BGP 自治系统C 自治系统A 自治系统B 图示 H1 H2 H1 H1 A1 A1 A4 A4 A3 B1 B2 A3 B1 B2 H2 自治系统A的路由协议RIP 自治系统B的选路协议OSPF 自治系统间的路由协议BGP C1 A2 C2 C3 B3 B4 A1 5 内部IP路由协议和类型 按路由算法方式的不同又可将内部路由协议分为距离向量路由协议和链路状态路由协议两种 距离向量路由协议主要以已知网络中路由器间的距离 跳数 更新路由表 链路状态路由协议则主要是以相邻路由器的状态更新路由表 5 5 2内部网关协议RIP RoutingInformationProtocol 1 工作原理RIP是一种分布式的基于距离向量的路由选择协议 RIP协议要求网络中的每一个路由器都要维护从它自己到其他每一个目的网络的距离记录 路由信息协议RIP是内部网关协议IGP中最先得到广泛使用的协议 距离 的定义 从一路由器到直接连接的网络的距离定义为1 从一个路由器到非直接连接的网络的距离定义为所经过的路由器数加1 RIP协议中的 距离 也称为 跳数 hopcount 因为每经过一个路由器 跳数就加1 这里的 距离 实际上指的是 最短距离 距离 的定义 RIP认为一个好的路由就是它通过的路由器的数目少 即 距离短 RIP允许一条路径最多只能包含15个路由器 距离 的最大值为16时即相当于不可达 可见RIP只适用于小型互联网 RIP不能在两个网络之间同时使用多条路由 RIP选择一个具有最少路由器的路由 即最短路由 哪怕还存在另一条高速 低时延 但路由器较多的路由 RIP协议的三个要点 仅和相邻路由器交换信息 交换的信息是当前本路由器所知道的全部信息 即自己的路由表 按固定的时间间隔交换路由信息 例如 每隔30秒 路由表的建立 路由器在刚刚开始工作时 只知道到直接连接的网络的距离 此距离定义为1 以后 每一个路由器也只和数目非常有限的相邻路由器交换并更新路由信息 经过若干次更新后 所有的路由器最终都会知道到达本自治系统中任何一个网络的最短距离和下一跳路由器的地址 RIP协议的收敛 convergence 过程较快 即在自治系统中所有的结点都得到正确的路由选择信息的过程 2 距离向量算法 收到相邻路由器 其地址为X 的一个RIP报文 1 先修改此RIP报文中的所有项目 把 下一跳 字段中的地址都改为X 并把所有的 距离 字段的值加1 2 对修改后的RIP报文中的每一个项目 重复以下步骤 若项目中的目的网络不在路由表中 则把该项目加到路由表中 否则若下一跳字段给出的路由器地址是同样的 则把收到的项目替换原路由表中的项目 否则若收到项目中的距离小于路由表中的距离 则进行更新 否则 什么也不做 3 若3分钟还没有收到相邻路由器的更新路由表 则把此相邻路由器记为不可达路由器 即将距离置为16 距离为16表示不可达 4 返回 路由器之间交换信息 RIP协议让互联网中的所有路由器都和自己的相邻路由器不断交换路由信息 并不断更新其路由表 使得从每一个路由器到每一个目的网络的路由都是最短的 即跳数最少 虽然所有的路由器最终都拥有了整个自治系统的全局路由信息 但由于每一个路由器的位置不同 它们的路由表当然也应当是不同的 RIP RoutingInformationProtocol DestinationNetworkNextRouterNum ofhopstodest wA2yB2zB3x 1 w x y z A C D B 路由器D中的路由表 图例 网110 0 0 0 网220 0 0 0 网330 0 0 0 网440 0 0 0 10 0 0 4 R1 20 0 0 7 R2 R3 20 0 0 9 30 0 0 2 30 0 0 1 40 0 0 4 R2中的路由表 R1中的路由表 R3中的路由表 4字节 RIP报文 3 RIP2协议的报文格式 路由信息 20字节 路由 可重复出现最多25个 IP数据报 路由标记 网络地址 地址族标识符 距离 1 16 IP首部 UDP首部 首部 路由部分 必为0 版本 命令 4字节 子网掩码 下一跳路由器地址 UDP用户数据报 课堂交流与互动 假定网络中的路由器B的路由表右表的项目 现在B收到从相邻路由器C发来的信息 这两列分别为目的网络和距离 N2 4N3 8N6 4N8 4N9 5试求出路由器B更新后的路由表 路由器B的路由表 方式 2 4位同学交流时间 2分钟提交 黑板填写 课堂交流与互动 假定网络中的路由器B的路由表右表的项目 现在B收到从相邻路由器C发来的信息 这两列分别为目的网络和距离 N2 4N3 8N6 4N8 4N9 5试求出路由器B更新后的路由表 更新后路由器B的路由表 4 RIP协议的优缺点 RIP存在的一个问题是当网络出现故障时 要经过比较长的时间才能将此信息传送到所有的路由器 RIP协议最大的优点就是实现简单 开销较小 RIP限制了网络的规模 它能使用的最大距离为15 16表示不可达 路由器之间交换的路由信息是路由器中的完整路由表 因而随着网络规模的扩大 开销也就增加 R2 R1 正常情况 11 12R1 R1说 我到网1的距离是1 是直接交付 1 表示 从本路由器到网1 1 表示 距离是1 表示 直接交付 R2 R1 正常情况 11 12R1 R2说 我到网1的距离是2 是经过R1 1 表示 从本路由器到网1 2 表示 距离是2 R1 表示经过R1 R2 R1 正常情况 11 12R1 R1说 我到网1的距离是16 表示无法到达 是直接交付 但R2在收到R1的更新报文之前 还发送原来的报文 因为这时R2并不知道R1出了故障 R2 R1 正常情况 11 12R1 R1收到R2的更新报文后 误认为可经过R2到达网1 于是更新自己的路由表 说 我到网1的距离是3 下一跳经过R2 然后将此更新信息发送给R2 R2 R1 正常情况 11 12R1 R2以后又更新自己的路由表为 1 4 R1 表明 我到网1距离是4 下一跳经过R1 R2 R1 R2 R1 网1出了故障 正常情况 11 116 15R2 12R1 12R1 这样不断更新下去 直到R1和R2到网1的距离都增大到16时 R1和R2才知道网1是不可达的 这就是好消息传播得快 而坏消息传播得慢 网络出故障的传播时间往往需要较长的时间 例如数分钟 这是RIP的一个主要缺点 5 5 3内部网关协议OSPF OpenShortestPathFirst 1 OSPF协议的4个基本特点 开放 表明OSPF协议不是受某一家厂商控制 而是公开发表的 最短路径优先 是因为使用了Dijkstra 狄克斯特拉 提出的最短路径算法SPFOSPF只是一个协议的名字 它并不表示其他的路由选择协议不是 最短路径优先 是分布式的链路状态协议 三个要点 向本自治系统中所有路由器发送信息 这里使用的方法是洪泛法 发送的信息就是与本路由器相邻的所有路由器的链路状态 但这只是路由器所知道的部分信息 链路状态 就是说明本路由器都和哪些路由器相邻 以及该链路的 度量 metric 只有当链路状态发生变化时 路由器才用洪泛法向所有路由器发送此信息 链路状态数据库 link statedatabase 由于各路由器之间频繁地交换链路状态信息 因此所有的路由器最终都能建立一个链路状态数据库 这个数据库实际上就是全网的拓扑结构图 它在全网范围内是一致的 这称为链路状态数据库的同步 OSPF的链路状态数据库能较快地进行更新 使各个路由器能及时更新其路由表 OSPF的更新过程收敛得快是其重要优点 OSPF的区域 area 为了使OSPF能够用于规模很大的网络 OSPF将一个自治系统再划分为若干个更小的范围 叫作区域 每一个区域都有一个32位的区域标识符 用点分十进制表示 区域也不能太大 在一个区域内的路由器最好不超过200个 OSPF划分为两种不同的区域 区域0 0 0 1 区域0 0 0 3 主干区域0 0 0 0 至其他自治系统 R9 R7 R6 R5 R4 R3 R2 R1 网8 网6 网3 网2 网1 网7 区域0 0 0 2 网4 网5 R8 划分区域的特点 划分区域的好处就是将利用洪泛法交换链路状态信息的范围局限于每一个区域而不是整个的自治系统 这就减少了整个网络上的通信量 在一个区域内部的路由器只知道本区域的完整网络拓扑 而不知道其他区域的网络拓扑的情况 OSPF使用层次结构的区域划分 在上层的区域叫作主干区域 backbonearea 主干区域的标识符规定为0 0 0 0 主干区域的作用是用来连通其他在下层的区域 主干路由器 区域0 0 0 1 区域0 0 0 3 主干区域0 0 0 0 至其他自治系统 R9 R7 R6 R