数据通信与计算机网络--08分组交换.ppt

第8讲分组交换与路由选择 课时授课计划课程内容 内容 电路交换和分组交换虚电路和数据报路由选择策略目的与要求 掌握电路交换和分组交换的基本工作原理 掌握网络提供的服务方式 虚电路和数据报服务 理解路由选择算法 重点与难点 重点 分组交换的工作原理 路由选择算法 难点 路由选择算法 课堂讨论 分组交换的工作原理 网络层提供的基本服务之一 路由选择 现代教学方法与手段 投影PowerPoint幻灯课件复习 提问 IEEE体系结构 CSMA CD和Tokenring 第5章网络层 5 1电路交换和分组交换5 2虚电路和数据报5 3路由选择 网络层 讨论 为什么需要网络层 网络层提供哪些服务 为什么网络互连中需要路由器等路由设备 OSI RM 为什么需要网络层 主机A 主机B 结点1 结点2 结点3 网络连接 数据链路连接 数据链路连接 传输层 数据链路层 网络层 网络层是通信子网的最高层 对上层用户屏蔽了子网通信的细节 如子网类型 拓扑结构 子网数目 向上层提供一致的服务 统一的地址 交换通信网的数据交换方式 电路交换 circuitswitching 分组交换 packetswitching 电路交换 电路交换的数据传输过程电路的建立数据传输电路释放电路交换的特点 时延小 适合于实时性强的交互式通信 对突发性通信不适应 信道利用率低 不具备存储数据或差错控制能力 电路交换 返回 分组交换 分组交换的数据传输过程仍基于存储转发原理 但对数据传输单位的作了划分 将长报文或大的数据块分割成小段 为每小段附上地址 分组编号 校验等信息构成一个数据分组 数据包 作为存储转发的逻辑数据单元 电路交换的特点 固定大小的分组单位较小 可充分利用线路空闲 从而减少了传输延时 出错重传的数据量也大大减少 分组交换 虚电路 VirtualCircuit 数据报 Datagram A C B D E A C D H1 H2 H4 H3 H5 H6 a 数据报服务 b 虚电路服务 虚电路 含义 通信子网借以实现面向连接服务的工作方式 需要源与目标之间建立一条逻辑上的通信链路 涉及虚电路逻辑连接的三个阶段 虚电路对立 数据传输 虚电路拆除在建立连接时 将从源端机器到目标机器的路由作为连接建立的一部分加以保存 在虚电路上传送的分组总是取相同的路径 路由 通过通信子网 虚电路 A E D C B H2 H3 H1 H4 H5 依次建立5条VC VC1 A B EVC2 A B DVC3 B D EVC4 C E DVC5 A B C D 入口 出口 H1 H1 H1 1 2 5 0 1 2 B 0 1 2 B B 入口 出口 A A H2 3 0 1 0 E 0 0 1 D D 入口 出口 B B E 0 1 0 H4 0 0 1 E H4 入口 出口 H3 B 4 0 0 0 E 0 0 2 D 入口 出口 B D C 0 0 0 H5 0 1 0 D A B C D E A 2 C 0 H5 C H4 虚电路路由表建立过程示例 虚电路 特点 包传输路径相同 不需要源地址与目标地址信息 除了建立连接时需要路由 在数据传送过程中不需要作路由 无路由信息 只有虚电路连接信息 包的传输不会出现丢失 重复和乱序现象 分类 永久虚电路 PVC 呼叫虚电路 SVC 数据报 通信子网借以实现面向无连接服务的工作方式 为每个分组选择独立的路由 即不同的分组可以走不同的路由 数据报 A E D C B H2 H3 H1 H4 H5 1 2 目的站 输出线 B C D E 1 2 1 2 结点A的路由表 数据报的路由表 每个分组都需要携带完整的目的地址 每个结点保存一个到网内其他结点的输出线选择表 虚电路与数据报的比较 路由选择 理想路由算法的基本特性正确性 Correctness 简单性 Simplicity 健壮性 robustness 稳定性 stability 公平性 fairness 优越性 optimality 高效性 efficiency 路由选择 静态路由策略扩散法固定路由选择随机路由选择基于流量的路由选择动态路由策略在网络互联中讲解 扩散法 洪泛 基本思想把收到的每一个包 向除了该包到来的线路外的所有输出线路发送 主要问题洪泛要产生大量重复包 解决措施每个包头包含站点计数器 每经过一站计数器减1 为0时则丢弃该包 记录包经过的路径 扩散法 洪泛 选择性洪泛算法 selectiveflooding 洪泛法的一种改进 将进来的每个包仅发送到与正确方向接近的线路上 应用情况路由器和线路的资源过于浪费 实际很少直接采用 具有极好的健壮性 可用于军事应用 作为衡量标准评价其它路由算法 固定路由选择 固定路由选择在每个节点上保持一张路由表 表上标明对每一个目的地址应走哪条链路进行转发 路由表是在整个系统进行配置时生成的 配置时根据事先计算好的 网络中任意两个节点之间最短路径 将这些最短通路制成路由表 存放在各个节点中 每一个分组都可在所到达的节点中查找下一步应转发到哪一个节点 下一站节点或后继节点 经典的求最短路径算法是Dijkstra算法 它的条件是已知网络的拓扑和各链路长度 主要是通过计算任意两节点间的最小链路长度 求得从源节点到目的节点间最短通路 固定路由选择 Dijkstra算法对于一个无向图G V E 其中V表示网络中所有节点的集合 E表示网络中所有链路的集合 D v 为源节点到节点v的距离 l i j 为节点i至节点j之间的距离 1 初始化任选一个节点作为源节点 不妨令V 1 对所有不在V中的节点v 写出 图求最短路径算法的网络拓扑 实际编程时一般取D v 1000代替 源节点 固定路由选择 2 寻找一个不在V中的节点w 其D w 值为最小 把w加入到V中 然后对所有不在V中的节点 用 D v D w l w v 中较小的值去更新原有的D v 值 即 D v Min D v D w l w v 3 重复步骤 2 直到所有的网络节点都在V中为止 由Dijkstra算法可知 若将已知的各链路长度改为链路时延 跳数 带宽或费用 就相当于求任意两节点之间具有最小时延 最少跳数 最大带宽或最小费用的通路 所以 求最短路径算法具有普遍的应用价值 固定路由选择 基于左图的网络拓扑结构 采用Dijkstra算法 计算以节点1为源节点的最短通路的过程 表中带圆圈的数字表示的是 在每一次执行步骤 2 时 所寻找到的具有最小值的D w 值 固定路由选择 上述路由表仅是以节点1为源节点 由Dijkstra算法计算得到节点1为根的通路树 然后生成节点1内存中的路由表这样的路由表每个节点都有一个 只需分别以这些节点为源点 重新执行算法即可 图基于Dijkstra算法生成的最短通路树 图依据最短通路树生成节点1的路由表 随机路由选择 当分组到达某个节点时就随机地选择一条链路作为转发的路由 当网络中的节点或链路发生故障时 采用随机走动法是最有效的 它使得路由算法具有较好的稳健性 基于流量的路由选择 基本思想既考虑拓扑结构 又兼顾网络负荷 前提 每对结点间平均数据流是相对稳定和可预测的 根据网络带宽和平均流量 可得出平均包延迟 因此路由选择问题归结为找产生网络最小延迟的路由选择算法 提前离线 off line 计算 基于流量的