134-1 第5章 数据链路控制及其协议 134-2 主要内容 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检错码 134-3 主要内容 5.3基本的数据链路层协议 5.3.1无约束单工协议 5.3.2单工停等协议 5.3.3有噪声信道的单工协议 5.4滑动窗口协议 5.4.1一比特滑动窗口协议 5.4.2退后n帧协议 5.4.3选择重传协议 134-4 主要内容 5.5协议说明与验证 5.5.1通信协议中的形式化描述技术 5.5.2有限状态机模型 5.5.3Petri网模型 5.6常用的数据链路层协议 5.6.1高级数据链路控制规程 HDLC 5.6.2X.25的链路层协议LAPB 5.6.3Internet数据链路层协议 5.6.4ATM数据链路层协议 134-5 5.1 定义和功能 5.1.1 定义 要解决的问题 - 如何在有差错的线路上，进行无差错传输 ISO关于数据链路层的定义 - 数据链路层的目的是为了提供功能上和规 程上的方法，以便建立、维护和释放网络 实体间的数据链路。 134-6 5.1 定义和功能 基本概念 - 结点（node）：网络中的主机（host）和路由器（router） 称为结点 - 链路（link）：通信路径上连接相邻结点的通信信道称为链路 数据链路层协议定义了一条链路的两个结点间交换的数据 单元格式，以及结点发送和接收数据单元的动作。 - 端到端（end to end）：从源结点（source node）到目的结 点（destination node）的通信称为端到端通信，通信路径（ path）可能由多个链路组成。 - 点到点（point to point）：在相邻结点间的一条链路上的通 信称为点到点通信。 - 最大传送单元MTU：帧的数据部分的长度上限； 134-7 点到点 链路 端到端 端到端 结点 点到点 134-8 虚拟数据通路 (host1 to host2) 物理层 数据链路层 网络层 运输层 应用层 物理层 网络层 运输层 应用层 数据链路层 host1host2 134-9 实际数据通路(host1 to host2) 物理层 数据链路层 网络层 运输层 应用层 物理层 网络层 运输层 应用层 数据链路层 host1host2 134-10 5.1 定义和功能 数据链路控制规程 - 为使数据能迅速、正确、有效地从发送点到达接 收点所采用的控制方式。 数据链路层协议应提供的最基本功能 - 数据在数据链路上的正常传输（建立、维护和释 放） - 定界与同步，也处理透明性问题 - 差错控制 - 顺序控制 - 流量控制 134-11 5.1 定义和功能 5.1.2 为网络层提供服务 为网络层提供三种合理的服务 - 无确认无连接服务，适用于 误码率很低的线路，错误恢复留给高层； 实时业务 大部分局域网 - 有确认无连接服务，适用于不可靠的信道，如无 线网。 - 有确认有连接服务 134-12 5.1 定义和功能 5.1.3 成帧（Framing） 将比特流分成离散的帧，并计算每个帧的校验和。 成帧方法（具体定义见后面）： - 字符计数法 - 带字符填充的首尾字符定界法 - 带位填充的首尾标记定界法 - 物理层编码违例法 注意：在很多数据链路协议中，使用字符计数法和一 种其它方法的组合。 134-13 5.1 定义和功能 字符计数法 - 在帧头中用一个域来表示整个帧的字符个数 - 缺点：若计数出错，对本帧和后面的帧有影响 60 1 2 3 40 1 2 3 4 5 6 7965 6 7 8 98 9 0 1 2 3 4 59 帧1帧2帧3帧4 60 1 2 3 40 1 2 3 4 5 6 7975 6 7 8 98 9 0 1 2 3 4 59 帧1帧2 错误 错误的字符计数 134-14 5.1 定义和功能 带字符填充的首尾字符定界法 - 起始字符 DLE STX，结束字符DLE ETX DLE:Data Link Escape STX:Start of Text ETX:End of Text - 字符填充 - 缺点：局限于8位字符和ASCII字符传送。 134-15 ADLEB ADLEB ADLEB 发 送 方 接 收 方 填充DLE DLEDLESTXDLEETX ADLEBDLESTXDLEDLEETX 134-16 5.1 定义和功能 带位填充的首尾标记定界法 - 帧的起始和结束都用一个特殊的位串“01111110” ，称为标记(flag) - “0”比特插入删除技术 011011111111111111110010 发 送 方 接 收 方 011011111 11111 11111 100100111111001111110000 填充“0”比特 011011111 11111 11111 100100111111001111110000 011011111111111111110010 134-17 5.1 定义和功能 物理层编码违例法 - 只适用于物理层编码有冗余的网络，如两个物理 位来编码1位数据。 - 802 LAN：曼彻斯特编码或差分曼彻斯特编码用 high-low pair/low-high pair表示1/0，high- high/low-low不表示数据，可以用来做定界符。 134-18 5.1 定义和功能 5.1.4 差错控制 一般方法：接收方给发送方一个反馈（响应）。 出错情况 - 帧（包括发送帧和响应帧）出错； - 帧（包括发送帧和响应帧）丢失 通过计时器和序号保证每帧最终交给目的网络层仅一 次是数据链路层的一个主要功能。 5.1.5 流量控制 基于反馈机制 流量控制主要在传输层实现 134-19 5.2 错误检测和纠正 差错出现的特点：随机，连续突发（burst） 处理差错的两种基本策略 - 使用纠错码：发送方在每个数据块中加入足够的 冗余信息，使得接收方能够判断接收到的数据是 否有错，并能纠正错误。 - 使用检错码：发送方在每个数据块中加入足够的 冗余信息，使得接收方能够判断接收到的数据是 否有错，但不能判断哪里有错。 134-20 5.2 错误检测和纠正 5.2.1纠错码 码字（codeword）：一个帧包括m个数据位，r个校验位，n = m + r，则此n位单元称为n位码字。 海明距离（Hamming distance）：两个码字之间不同的比特 位数目。 - 例：0000000000 与0000011111的海明距离为5（可以进行 异或运算，然后计算1的个数） - 如果两个码字的海明距离为d，则只要d个1位错就可以把一 个码字转换成另一个码字； - 为了检查出d个错（1位错），需要使用海明距离为 d + 1 的 编码方案（即合法码字列表中，海明距离最小的两个有效码 字之间的海明距离为d+1）； - 为了纠正d个错，需要使用海明距离为 2d + 1 的编码，使得 合法码字之间的距离足够远。 134-21 5.2 错误检测和纠正 检查单个错误最简单的例子是奇偶校验，在数据后添 加一个奇偶位，则海明距离为2. - 例：使用偶校验（“1”的个数为偶数） 10110101101101011 10110001101100010 - 奇偶校验可以用来检查奇数个错误。 用于纠正单个错误所需要的检验位数目的下界 - 设有一种编码方案：m个信息位，r个校验位，能 够纠正单比特错，满足n = m + r ； - 对2m个有效报文中任何一个，有n个与其距离为1 的无效码字，因此有：(n + 1) 2m 2n 134-22 5.2 错误检测和纠正 - 利用 n = m + r，得到 (m + r + 1) 2r。给定m， 利用该式可以得出校正单比特误码的校验位数目 的下界 海明码：1950提出的编码方案可以达到上述要求 - 码位从左边开始编号，从“1”开始； - 位号为2的幂的位（1，2，4，8，16，.）是校验 位，其余是信息位； - 每个校验位使得包括自己在内的一组数据位的奇 偶值为偶数（或奇数）。 - 一个数据位k可能包含在不同组中，为看清数据位 k跟哪些校验位有关系，将k写成2的幂的和。例： 11 = 1 + 2 + 8 134-23 5.2 错误检测和纠正 海明码工作过程 - 每个码字到来前，接收方计数器清零； - 接收方检查每个校验位k (k = 1, 2, 4 )的奇偶值 是否正确； - 若校验位第 k 位奇偶值不对，计数器加 k； - 所有校验位检查完后，若计数器值为0，则码字有 效；若计数器值为m，则第m位出错。例：若校验 位1、2、8出错，则第11位变反。 - 海明码原来设计只能纠正单个错误，但是可以采 用一些技巧来纠正突发性错误。 134-24 5.2 错误检测和纠正 使用海明码纠正突发错误 - 可采用k个码字（n = m + r）组成 k n 矩阵，按 列发送，接收方恢复成 k n 矩阵 - kr个校验位，km个数据位，可纠正最多为k个的 突发性连续比特错。 134-25 1 2 3 4 5 6 7 8 9 10 11 1 1 1 1 1 2 2 2 2 2 4 4 4 8 8 8 Use of a Hamming code to correct burst errors. 134-26 5.2 错误检测和纠正 5.2.2 检错码 使用纠错码传数据，效率低，适用于不可能重传的场 合；大多数情况采用检错码加重传。 循环冗余码（CRC码，多项式编码） - 110001，表示成多项式 x5 + x4 + 1 生成多项式G(x) - 发方、收方事前商定； - 生成多项式的高位和低位必须为1 - 生成多项式必须比传输信息对应的多项式短。 134-27 5.2 错误检测和纠正 CRC码基本思想 - 校验和（checksum）加在帧尾，使带校验和的帧 的多项式能被G(x)除尽；收方接收时，用G(x)去 除它，若有余数，则传输出错。 校验和计算算法 - 设G(x)为 r 阶，在帧的末尾加 r 个0，使帧为m + r 位，相应多项式为xrM(x)； - 按模2除法用对应于G(x)的位串去除对应于xrM(x) 的位串； 134-28 5.2 错误检测和纠正 - 按模2减法从对应于xrM(x)的位串中减去余数(等于 或小于r位)，结果就是要传送的带校验和的多项式 T(x)。 CRC的检错能力 - 发送：T(x)；接收：T(x) + E(x), E(x) 0；其中 E(x) 表示发生了错误。 - 余数(T(x) + E(x) / G(x) = 0 + 余数(E(x) / G(x) - 若余数(E(x) / G(x) = 0，则差错不能发现；否则 ，可以发现。 134-29 5.2 错误检测和纠正 CRC检错能力的几种情况分析(?) - 如果只有单比特错，即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)的倍数就能查出奇数个比特错； 134-30 5.2 错误检测和纠正 - 具有r个校验位的多项式能检查出所有长度 r 的 突发性差错。长度为k的突发性连续差错可表示为 xi (xk-1 + +