第五章 数字链路控制及其协议.docx

本文格式为Word版，下载可任意编辑第五章 数字链路控制及其协议 网络原理 课程讲义 第五章 数据链路操纵及其协议 网络原理 课程讲义 主要内容5.1 定义和功能5.1.1 5.1.2 5.1.3 5.1.4 5.1.5 定义 为网络层供给服务 成帧 过错操纵 流量操纵纠错码 检错码 无约束单工协议 单工停等协议 有噪声信道的单工协议 5.2 错误检测和校正5.2.1 5.2.2 5.3 根本的数据链路层协议5.3.1 5.3.2 5.3.3 网络原理 课程讲义 5.4 滑动窗口协议5.4.1 5.4.2 5.4.3 一比特滑动窗口协议 退后n帧协议 选择重传协议通信协议中的形式化描述技术 有限状态机模型 Petri网模型 高级数据链路操纵规程 HDLC X.25的链路层协议LAPB Internet数据链路层协议 ATM数据链路层协议 5.5 协议说明与验证5.5.1 5.5.2 5.5.3 5.6 常用的数据链路层协议5.6.1 5.6.2 5.6.3 5.6.4 网络原理 课程讲义 5.1 定义和功能(1)5.1.1 定义 要解决的问题- 如何在有过错的线路上，举行无过错传输。

ISO关于数据链路层的定义- 数据链路层的目的是为了供给功能上和规程上的方法 ，以便建立、维护和释放网络实体间的数据链路 数据链路- 从数据发送点到数据接收点(点到点 point to point) 所经过的传输途径 虚拟数据通路，实际数据通路- Fig. 3-14 网络原理 课程讲义 网络原理 课程讲义 5.1 定义和功能(2)数据链路操纵规程- 为使数据能急速、正确、有效地从发送点到达接收点所 采用的操纵方式 数据链路层协议应供给的最根本功能数据在数据链路上的正常传输(建立、维护和释放) 定界与同步，也处理通明性问题 过错操纵 依次操纵 流量操纵 网络原理 课程讲义 5.1 定义和功能(3)5.1.2 为网络层供给服务 为网络层供给三种合理的服务- 无确认无连接服务，适用于 误码率很低的线路，错误恢复留给高层； 实时业务 大片面局域网 - 有确认无连接服务，适用于不成靠的信道，如无线网 - 有确认有连接服务 网络原理 课程讲义 5.1 定义和功能(4)5.1.3 成帧(Framing) 将比特流分成离散的帧，并计算每个帧的校验和。

成帧方法：- 字符计数法 在帧头中用一个域来表示整个帧的字符个数 缺点：若计数出错，对本帧和后面的帧有影响 Fig. 3-3 - 带字符填充的首尾字符定界法 起始字符 DLE STX,终止字符DLE ETX 字符填充 Fig. 3-4 缺点：局限于8位字符和ASCII字符传送8 网络原理 课程讲义 5.1 定义和功能(5)- 带位填充的首尾标记定界法 帧的起始和终止都用一个特殊的位串“01111110”, 称为标记(flag) “0”比特插入删除技术 Fig. 3-5 - 物理层编码违例法 只适用于物理层编码有冗余的网络 802 LAN:Manchester encoding or Differential Manchester encoding 用high-low pair/low-high pair 表示1/0,high-high/low-low不表示数据，可以用来 做定界符 留神：在好多数据链路协议中，使用字符计数法 和一种 其它方法的组合9 网络原理 课程讲义 网络原理 课程讲义 网络原理 课程讲义 网络原理 课程讲义 5.1 定义和功能(6)5.1.4 过错操纵 一般方法：接收方给发送方一个反应(响应)。

出错处境- 帧(包括发送帧和响应帧)出错； - 帧(包括发送帧和响应帧)损失 通过计时器和序号保证每帧最终交给目的网络层 仅一次是数据链路层的一个主要功能 5.1.5 流量操纵 基于反应机制 流量操纵主要在传输层实现13 网络原理 课程讲义 5.2 错误检测和校正(1) 过错展现的特点：随机，连续突发(burst) 处理过错的两种根本策略- 使用纠错码：发送方在每个数据块中参与足够的冗余信息 ，使得接收方能够判断接收到的数据是否有错，并能校正 错误 - 使用检错码：发送方在每个数据块中参与足够的冗余信息 ，使得接收方能够判断接收到的数据是否有错，但不能判 断哪里有错 5.2.1 纠错码 码字(codeword):一个帧包括m个数据位，r个 校验位，n = m + r,那么此n比特单元称为n位码字 海明距离(Hamming distance):两个码字之间 不同的比特位数目14 网络原理 课程讲义 5.2 错误检测和校正(2)- 例：0000000000 与0000011111的海明距离为5 - 假设两个码字的海明距离为d,那么需要d个单比特错就可 以把一个码字转换成另一个码字； - 为了检查出d个错(单比特错),需要使用海明距离为 d + 1 的编码； - 为了校正d个错，需要使用海明距离为 2d + 1 的编码； 最简朴的例子是奇偶校验，在数据后填加一个奇 偶位(parity bit)- 例：使用偶校验(“1”的个数为偶数) 10110101 —— 101101011 10110001 —— 101100010 - 奇偶校验可以用来检查单个错误。

网络原理 课程讲义 5.2 错误检测和校正(3) 设计纠错码- 要求：m个信息位，r个校验位，校正单比特错； - 对2m个有效信息中任何一个，有n个与其距离为1的无效码字，因 此有：(n + 1) 2m 2n 利用 n = m + r,得到 (m + r + 1) 2r 给定m,利用该式可以得出校正单比特误码的校验位数目的下界 海明码- 码位从左边开头编号，从“1”开头； - 位号为2的幂的位是校验位，其余是信息位； - 每个校验位使得包括自己在内的一些位的奇偶值为偶数(或奇数 ) - 为看清数据位k对哪些校验位有影响，将k写成2的幂的和 - 例：11 = 1 + 2 + 816 网络原理 课程讲义 5.2 错误检测和校正(4) 海明码工作过程每个码字到来前，接收方计数器清零； 接收方检查每个校验位k (k = 1, 2, 4 …)的奇偶值是否正确； 若第 k 位奇偶值不对，计数器加 k; 全体校验位检查完后，若计数器值为0,那么码字有效；若计数 器值为m,那么第m位出错 - 若校验位1、2、8出错，那么第11位变反 - Fig. 3-6 - 使用海明码校正突发错误- 可采用k个码字(n = m + r)组成 k n 矩阵，按列发送，接收 方恢复成 k n 矩阵 - kr个校验位，km个数据位，可校正最多为k个的突发性连续比 特错。

17 网络原理 课程讲义 1 2 3 4 5 6 1 1 2 2 4 4 7 8 9 10 11 1 1 1 2 2 2 4 8 8 8 网络原理 课程讲义 5.2 错误检测和校正(5)5.2.2 检错码 使用纠错码传数据，效率低，适用于不成能重传 的场合；大多数处境采用检错码加重传 循环冗余码(CRC码，多项式编码)- 110001,表示成多项式 x5 + x4 + 1 生成多项式G(x)- 发方、收方事前商定； - 生成多项式的高位和低位务必为1 - 生成多项式务必比传输信息对应的多项式短 CRC码根本思想- 校验和(checksum)加在帧尾，使带校验和的帧的多项 式能被G(x)除尽；收方接收时，用G(x)去除它，若有余 数，那么传输出错19 网络原理 课程讲义 5.2 错误检测和校正(6) 校验和计算算法- 设G(x)为 r 阶，在帧的末尾加 r 个0,使帧为m + r位，相应 多项式为xrM(x); - 按模2除法用对应于G(x)的位串去除对应于xrM(x)的位串； - 按模2减法从对应于xrM(x)的位串中减去余数(等于或小于r 位),结果就是要传送的带校验和的多项式T(x)。

- Fig. 3-7 CRC的检错才能- 发送：T(x);接收：T(x) + E(x); - 余数((T(x) + E(x)) / G(x)) = 0 + 余数(E(x) / G(x)) - 若 余数(E(x) / G(x)) = 0,那么过错不能察觉；否那么，可以发 现 网络原理 课程讲义 5.2 错误检测和校正(7)- 假设只有单比特错，即E(x) = xi,而G(x)中至少有两项， 余数(E(x) / G(x)) 0,所以可以查出单比特错； - 假设发生两个孤立单比特错，即E(x) = xi + xj = xj (xi-j + 1),假定G(x)不能被x整除，那么能够察觉两个比特错的 充分条件是：xk + 1不能被G(x)整除 (k i - j); - 假设有奇数个比特错，即E(x)包括奇数个项，G(x)选(x + 1)的倍数就能查稀奇数个比特错； - 具有r个校验位的多项式能检查出全体长度 r 的突发性 过错长度为k的突发性连续过错(并不表示有k个单比 特错)可表示为 xi (xk-1 + … + 1),若G(x)包括x0项，且 k - 1小于G(x)的阶，那么 余数(E(x) / G(x)) 0; - 假设突发过错长度为 r + 1,当且仅当突发过错和G(x)一 样时， 余数(E(x) / G(x)) = 0,概率为1/2r-1; - 长度大于 r + 1的突发过错或几个较短的突发过错发生后 ，坏帧被接收的概率为 1/2r。