计算机网络原理4-数据链路层.ppt

2020 1 5 1 第四章数据链路层及其协议 研究内容 两个相连的节点 机器 在物理层传送 位 的基础上 进行可靠 有效通信的算法 如何向网络层提供无错的透明传送 相连 相邻 两台机器通过通信信道进行物理连接 信道在概念上像一条线路 一条电缆或一条电话线 信道的重要特性是接收到的比特和发送出去的比特顺序完全相同 2020 1 5 2 章节安排 4 1数据链路层设计问题4 2面向比特的链路控制规程 HDLC4 3差错控制4 4流量控制 2020 1 5 3 4 1数据链路层设计问题 一 数据链路层模型及环境数据链路层模型 KP85图4 1 二 为网络层提供的服务数据链路连接成帧差错控制流量控制 2020 1 5 4 无连接无确认的服务由上层完成差错控制 适合于误码率低 实时性要求高的场合 有连接无确认的服务 进行简单的差错控制 正向应答只对正确的信息应答 在网络中最常使用的方式 负向应答只对错误的信息应答 双向应答既对正确的信息应答 也对错误的信息应答 1 数据链路连接 2020 1 5 5 面向连接的服务在发送前需要建立连接 保证了帧的正确按序传输 适合于可靠性要求较高的场合 数据传送的三个阶段原语与协议转换 kp87 面向字符的传输控制字 以一个典型的应用为例 CP133图3 2 解释数据链路协议的作用 2020 1 5 6 字符计数法特点 在帧头使用一个字段用于标明帧内的字符数 缺点 技术值有可能由于传输差错而被 篡改 带填充字符的首位界符法用DLESTX标示帧的开始用DLEETX标示帧的结束字符填充 用DLEDLE标示传送数据信息中的DLE例如 信息DLESTXADLEBDLEETX在网络中传送时表示为 DLESTXADLEDLEBDLEETX缺点 完全依赖于8位字符 特别是ASCII字符 随着网络的发展 这种在帧中嵌入字符的机制越来越少被采用 5 5 5 3 4 3 2 2 4 5 2 1 3 5 5 2 成帧 帧边界划分 2020 1 5 7 3 带填充位的首位标志法 HDLC协议用01111110标示帧的开始用01111110标示帧的结束位填充 在传送的数据信息中每遇到5个连续的1在其后加0例如 0110111111011111001在网络中传送时表示为 01111110011011111010111110001011111104 物理编码违例法只适合于编码法方案中有冗余编码的情况 如曼彻斯特编码 将在将802局域网时详细讨论 2020 1 5 8 3 差错控制 1 差错控制目的主要解决 如何在接收方能够判断接收的数据是否正确 若错误如何恢复错误 2 差错控制的方法检错同时纠错检错加重发机制定时器 序号 主要解决 如何处理发送方的传送能力 接收方 4 流量控制 2020 1 5 9 4 2面向比特的链路控制规程 HDLC广泛应用于X 25及其它网络中 一 面向字符的链路控制规程特点 链路上传送的数据和控制信息都必须是规定的数据集 缺点 所有的通信设备必须使用相同的字符集差错控制和流量控制复杂且功能弱不易扩展 每增加一种控制必须增加一种新的控制字符 2020 1 5 10 二 面向比特的链路控制规程概述 1 发展历史1974年IBM在SNA中采用面向比特的链路控制规程SDLCANSI将SDLC修改为ADCCPISO将SDLC修改为HDLCITU T将HDLC修改为LAP 其变种有LAPD和LAPB等共同特点 面向位的协议 2020 1 5 11 2 HDLC典型链路结构 站主站 负责链路控制 组织数据传送 差错恢复次站 在主站的控制下工作复合站 综合主战和次站的功能3 控制类型命令帧 主帧发给次站响应帧 次站发给主站 2020 1 5 12 三 HDLC帧的结构 1 帧的格式标志 由首尾两个标志字段完成帧同步站址 8比特的次站地址控制 命令和响应类型信息 数据字段校验和 16微循环冗余校验 2020 1 5 13 2 帧的类型和控制字段的含义 信息帧 I 监控帧 S 无序号帧 U 1 信息帧 I 完成信息的传送控制字段的第一位为02 4位N S 发送序号 当前发送信息帧的序号 6 8位N R 应答序号 采用附载应答 为期望接收的帧的序号 即该序号前的所有帧已经正确接收 5位P F位 询问 终止位 控制字段的格式参见KP100表4 2 2020 1 5 14 2 监视帧 S 差错和流量控制控制字段的第1 2位为103 4位表示监视帧的类型 见P102表4 4在上述四种帧中前三种用于全部重发流水线协议 后一种用于选择重发的流水线协议 对差错控制RR相当于正向应答帧SREJ和REJ相当于反向应答帧 否认帧 对流量控制RR表示接收方准备好RNR表示接收方未准备好 2020 1 5 15 3 无编号帧 U 链路管理控制字段的第1 2位为11无编号帧本身不带序号N R 和N S 3 4 6 7 8位表示无编号帧的类型 见P103表4 5 共32重组合 使用了其中的15种 在需要时发出 不影响信息的交换顺序 起链路的管理作用 2020 1 5 16 四 使用HDLC通信规程的通信过程 建立数据链路连接信息传送发送信息帧接收信息帧链路拆除 2020 1 5 17 五 面向比特通信控制规程的特点 对信息无位数限制帧标志位简单有校验位 可靠性增高数据和控制信息格式统一 2020 1 5 18 4 3数据链路层协议及流量控制 一 单工停等协议定义 发送方发送一个帧 不继续发送而是等待一个确认 这种协议成为停 等 stop and wait 协议 包括单工停等协议和连续停等协议 流水线协议 1 信道无错的单工停等协议D0A0D1A1 2020 1 5 19 2 信道有错的单工停等协议 问题的引入 如果信道有差错 帧可能损坏 也可能完全丢失 那么会使接收方处于无限等待状态 D0 A0 D1 A1 D0 A0 D1 A1 丢失数据帧 丢失应答帧 2020 1 5 20 信道有错的单工停等协议特点 常使用正向应答PAR positiveacknowledgementwithretransmission 重发机制来解决差错的控制问题 使用超时重发计时器解决出错重发问题 为判断重复帧 在接受方必须保存下一个接收的帧的序号 1位序列号 0 1 应答帧的两种方式 单帧应答 应答序号为某一个正确帧的序号成批应答 应答序号为下一个期望接收的序号协议效率低 对于单工停等协议 数据帧只能按一个方向进行传输 2020 1 5 21 从网络层取数 成帧 发送帧 帧到否 应答到否 超时否 重复否 正确否 接收帧 送网络层 发应答 发送帧 应答帧 Y N Y N Y N N Y 定时器 信道有错的单工停等协议示意图 2020 1 5 22 二 滑动窗口协议 协议的引入 单工停等协议数据帧只能按一个方向进行传输 而滑动窗口协议允许采用附在应答方式进行数据的双向传输 滑动窗口协议是对连续停等协议的改进 它控制了已发送未确认的帧的个数 即滑动窗口的大小 附载应答 捎带 piggybacking 将应答信息加在数据帧中发送 或数据帧中携带应答帧 2020 1 5 23 1 全双工信道数据流2 单帧停等协议的效率分析 对于信道很长的数据通信 但单帧发送效率很低 因此必须设计为允许连续多帧 3 滑动窗口流量控制发送窗口窗口尺寸 允许连续发送未应答的帧的个数数据允许发送的条件 数据序号落在发送窗口中窗口滑动的条件 收到应答帧接收窗口窗口尺寸 允许连续接收未处理的帧的个数数据允许接收的条件 数据序号落在接收窗口中窗口滑动的条件 发送应答帧 0 2 1 3 4 5 6 7 宽度4 0 2 1 3 4 5 6 7 宽度3 0 2 1 3 4 5 6 7 宽度2 0 2 1 3 4 5 6 7 宽度4 0 2 1 3 4 5 6 7 宽度3 0 2 1 3 4 5 6 7 宽度2 发送窗口 接收窗口 2020 1 5 25 三 流水线协议 连续停等协议 连续停等协议是指不需要等前面帧的应答收到就可连续不断的发下面的帧 全部重发流水线协议 也称退后n帧 当一帧出错时 需重发出错帧之后的所有帧接收方的缓冲区数量只需要一个选择重发流水线协议当一帧出错时 只重发出错帧接收方的缓冲区数量足够多 当接收窗口等于1的流水线帧出错示意图 kp111图4 15前一部分 1 2 3 4 3 2 8 7 6 5 4 8 7 6 5 9 0 1 E 3 2 D D D D D D 5 4 0 7 6 ACK0 ACK1 ACK2 ACK3 ACK4 超时间隔 被数据链路层丢失的帧 出错 时间 ACK5 发送端发送帧序列号 接收端接收帧序列号 1 3 2 8 7 6 5 4 0 E ACK0 ACK1 ACK2 1 2 3 4 3 2 8 7 6 5 4 10 9 6 5 11 0 D D D D 9 ACK3 ACK4 ACK7 ACK8 当接收窗口大于1的选择重发协议 kp111图4 16 超时间隔 被数据链路层存贮的帧 出错 将2 8帧送网络层 丢弃重复帧 发送端发送帧序列号 ACK6 ACK5 ACK8 2020 1 5 28 4 4差错控制参见cp1373 2差错监测和纠正 一 纠错码和校验码 检错码 1 码字codewordn m r 其中m位数据 报文 r位冗余位 或校验位 2 纠错码error correctingcode在数据块中附加足够的冗余信息 使接收方能推导出发出的字符是什么 3 检错码error detectingcode只加入冗余位 使接收方知道有差错发生 但不知道什么差错 然后请求重发 2020 1 5 29 1 海明距离两个编码的海明距离 两个编码不相同的位数的个数1001001和0001101 异或即可得出d 编码方案的海明距离 编码方案中任两个编码海明距离的最小值2 海明定理为检测d位错 编码方案的海明距离应至少为d 1当发生d位错时 不会由一种合法编码变为另一种合法编码为纠正d位错 编码方案的海明距离应至少为2d 1当发生d位错时 出错编码仍然最接近于原始的正确编码 二 纠错码 2020 1 5 30 奇偶校验码 ParityChecking 特点 m位数据位 1位奇偶校验位使海明距离由1变为2 可检测出1位错误 例 原始数据 1100010 采用偶校验 则增加校验位后的数据为11100010若接收方收到的字节奇偶结果不正确 就可以知道传输中发生了错误 奇偶校验只能检测出奇数个比特位错 对偶数个比特位错则无能为力 3 纠错码举例 2020 1 5 31 循环冗余校验 CRC CyclicRedundancyCheck 一种通过多项式除法检测错误的方法 编码思想 将位串看成系数为0或1的多项式 检错思想 收发双方约定一个生成多项式G x 其最高阶和最低阶系数必须为1 发送方在帧的末尾加上校验和 使带校验和的帧的多项式能被G x 整除 接收方收到后 用G x 除多项式 若有余数 则传输有错 二 检错码 2020 1 5 32 校验和计算方法 若G x 为r阶 原帧为m位 其多项式为M x 则在原帧后面添加r个0 帧成为m r位 相应多项式xrM x 按模2除法用对应于G x 的位串去除对应于xrM x 的位串 按