《清华大学计算机网络原理数据链路层1》由会员分享，可在线阅读，更多相关《清华大学计算机网络原理数据链路层1（54页珍藏版）》请在金锄头文库上搜索。
1、第五章 数据链路控制及其协议第五章 数据链路控制及其协议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退后n帧协议 5.4.3选择重传协议 5.5协议说明与验证 5.5.1通信协议中的形式化描述技术 5.5.2有限状态机模型 5.5.3Petri网模型 5.6常用的数据链路
2、层协议 5.6.1高级数据链路控制规程 HDLC 5.6.2X.25 LAPB 5.6.3Internet数据链路层协议5.1 定义和功能（1）5.1.1 定义 要解决的问题：如何在有差错的线路上，进行无 差错传输。 ISO关于数据链路层的定义： 数据链路层的目的是为了提供功能上和规程上 的方法，以便建立、维护和释放网络实体间的数 据链路。 数据链路：从数据发送点到数据接收点所经过的 传输途径。虚拟数据通路，实际数据通路。Fig. 3-15.1 定义和功能（2） 数据链路控制规程：为使数据能迅速、正确、有效 地从发送点到达接收点所采用的控制方式。 数据链路层协议应提供的最基本功能 数据在数据链
3、路上的正常传输（建立、维护和释放） 定界与同步，也处理透明性问题 差错控制 顺序控制 流量控制5.1 定义和功能（3）5.1.2 为网络层提供服务 为网络层提供三种合理的服务 无确认无连接服务 适用于 误码率很低的线路，错误恢复留给高层； 实时业务 大部分局域网 有确认无连接服务适用于不可靠的信道，如无线网。 有确认有连接服务5.1 定义和功能（4）5.1.3 成帧（Framing） 将比特流分成离散的帧，并计算每个帧的校验和。 成帧方法： 字符计数法 在帧头中用一个域来表示整个帧的字符个数 缺点：若计数出错，对本帧和后面的帧有影响。 Fig. 3-3 带字符填充的首尾字符定界法 起始字符 D
4、LE STX，结束字符DLE ETX 字符填充 Fig. 3-4 缺点：局限于8位字符和ASCII字符传送。5.1 定义和功能（5） 带位填充的首尾标记定界法 帧的起始和结束都用一个特殊的位串“01111110”，称为 标记标记 “0”比特插入删除技术 Fig. 3-5 物理层编码违例法 只适用于物理层编码有冗余的网络 注意：在很多数据链路协议中，使用字符计数法和 一种其它方法的组合。5.1 定义和功能（6）5.1.4 差错控制 一般方法：接收方给发送方一个反馈（响应）。 出错情况 帧（包括发送帧和响应帧）出错； 帧（包括发送帧和响应帧）丢失 通过计时器和序号保证每帧最终交给目的网络层仅 一次
5、是数据链路层的一个主要功能。5.1.5 流量控制 基于反馈机制 流量控制主要在传输层实现。5.2 错误检测和纠正（1） 差错出现的特点：随机，连续突发（burst） 处理差错的两种基本策略 使用纠错码：发送方在每个数据块中加入足够的冗余信息， 使得接收方能够判断接收到的数据是否有错，并能纠正错 误。 使用检错码：发送方在每个数据块中加入足够的冗余信息， 使得接收方能够判断接收到的数据是否有错，但不能判断 哪里有错。 5.2.1 纠错码 码字码字（codeword）：一个帧包括m位数据，r个校验 位，n = m + r，则此n比特单元称为n位码字。 海明距离海明距离（Hamming distan
6、ce）：两个码字的不同 比特位数目。5.2 错误检测和纠正（2）例：0000000000 与 0000011111 的海明距离为5 如果两个码字的海明距离为d，则需要d个单比特错 就可以把一个码字转换成另一个码字； 为了检查出d个错（单比特错），需要使用海明距 离为 d + 1 的编码； 为了纠正d个错，需要使用海明距离为 2d + 1 的编 码； 最简单的例子是奇偶校验，在数据后填加一个奇偶 位（parity bit）。 例：使用偶校验（“1”的个数为偶数） 10110101101101011 10110001101100010 奇偶校验可以用来检查单个错误。5.2 错误检测和纠正（3） 设
7、计纠错码 要求：m个信息位，r个校验位，纠正单比特错； 对2m个有效信息中任何一个，有n个与其距离为1的无效码 字，因此有： (n + 1) 2m 2n 利用 n = m + r，得到 (m + r + 1) 2r 给定 m，利用该式可以得出校正单比特误码的校验位数目的 下界。 海明码 码位从左边开始编号； 位号为2的幂的位是校验位，其余是信息位； 每个校验位强迫包括自己在内的一些位的奇偶值为偶数 （或奇数）。 为看清数据位k对哪些校验位有影响，将k写成2的幂的和。 例：11 = 1 + 2 + 85.2 错误检测和纠正（4） 海明码工作过程 每个码字到来前，接收方计数器清零； 接收方检查每个
8、校验位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个的突发性连 续比特错。5.2 错误检测和纠正（5）5.2.2 检错码 使用纠错码传数据，效率低，适用于不可能重传的 场合；大多数情况采用检错码加重传。 循环冗余码（CRC码，多项式编码）11000
9、1，表示成多项式 x5+ x4+ 1 生成多项式G(x) 发方、收方事前商定； 生成多项式的高位和低位必须为1 生成多项式必须比传输信息对应的多项式短。 CRC码基本思想：校验和加在帧尾，使带校验和 （checksum）的帧的多项式能被G(x)除尽；收方接 收时，用G(x)去除它，若有余数，则传输出错。5.2 错误检测和纠正（6） 校验和计算算法 设G(x)为 r 阶，在帧的末尾加 r 个0，使帧为m + r位，相应 多项式为xrM(x)； 按模2除法用对应于G(x)的位串去除对应于xrM(x)的位串； 按模2减法从对应于xrM(x)的位串中减去余数（等于或小于 r位），结果就是要传送的带校验
10、和的多项式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)； 如果有奇数个
11、比特错，即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。5.2 错误检测和纠正（8） 三个多项式已成为国际标准 CRC-
12、12 = x12+ x11+ x3+ x2+ x + 1 CRC-16 = x16+ x15+ x2+ 1 CRC-CCITT = x16+ x12+ x5+ 1 硬件实现CRC校验。5.3 基本的数据链路层协议（1）5.3.1 无约束单工协议（An Unrestricted Simplex Protocol） 工作在理想情况，几个前提： 单工传输 发送方无休止工作（要发送的信息无限多） 接收方无休止工作（缓冲区无限大） 通信线路（信道）不损坏或丢失信息帧 工作过程 发送程序:取数据，构成帧，发送帧； 接收程序：等待，接收帧，送数据给高层 Fig. 3-95.3 基本的数据链路层协议（2）5.
13、3.2 单工停等协议（A Simplex Stop-and-Wait Protocol） 增加约束条件：接收方不能无休止接收。 解决办法：接收方每收到一个帧后，给发送方回送 一个响应。 工作过程 发送程序：取数据，成帧，发送帧，等待响应帧； 接收程序：等待，接收帧，送数据给高层，回送响应帧。 Fig. 3-105.3 基本的数据链路层协议（3）5.3.3 有噪声信道的单工协议（A Simplex Protocol for a Noisy Channel） 增加约束条件：信道（线路）有差错，信息帧可能损 坏或丢失。 解决办法：出错重传。 带来的问题： 什么时候重传 定时 响应帧损坏怎么办（重复帧
14、） 发送帧头中放入序号 为了使帧头精简，序号取多少位 1位 发方在发下一个帧之前等待一个肯定确认的协议叫做 PAR（Positive Acknowledgement with Retransmission） 或ARQ（Automatic Repeat reQuest）5.3 基本的数据链路层协议（4） 工作过程 Fig. 3-11 注意协议3的漏洞 由于确认帧中没有序号，超时时间不能太短，否则 协议失败。因此假设协议3的发送和接收严格交替 进行。发送接收001ACKACK5.4 滑动窗口协议（1） 单工 全双工 捎带（piggybacking）：暂时延迟待发确认，以便附 加在下一个待发数据帧的
15、技术。 优点：充分利用信道带宽，减少帧的数目意味着减少“帧 到达”中断； 带来的问题：复杂。 本节的三个协议统称滑动窗口协议，都能在实际 （非理想）环境下正常工作，区别仅在于效率、复 杂性和对缓冲区的要求。5.4 滑动窗口协议（2） 滑动窗口协议（Sliding Window Protocol）工作原理： 发送的信息帧都有一个序号，从0到某个最大值，0 2n- 1，一 般用n个二进制位表示； 发送端始终保持一个已发送但尚未确认的帧的序号表，称为发 送窗口。发送窗口的上界表示要发送的下一个帧的序号，下界 表示未得到确认的帧的最小编号。发送窗口 = 上界 - 下界，大 小可变； 发送端每发送一个帧，序号取上界值，上界加1；每接收到一个 正确响应帧，下界加1； 接收端有一个接收窗口，大小固定，但不一定与发送窗口相同。 接收窗口的上界表示允许接收的序号最大的帧，下界表示希望 接收的帧； 接收窗口表示允许接收的信息帧，落在窗口外的帧均被丢弃。 序号等于下界的帧被正确接收，并产生一个响应帧，下界加1。 接收窗口大小不变。 Fig. 3-125.4 滑动窗口协议（2）5.4.1 一比特滑动窗口协议（A One Bit Sliding Window Protoc
