第三讲 数据链路层

1、12本讲要求本讲要求1 理解数据链路层解决的基本问题理解数据链路层解决的基本问题2 掌握数据帧的基本原理和方法掌握数据帧的基本原理和方法3 掌握出错处理的几种方式掌握出错处理的几种方式4 掌握数据链路层的基本协议掌握数据链路层的基本协议5 掌握数据链路层的滑动窗口协议掌握数据链路层的滑动窗口协议6 了解典型的数据链路协议了解典型的数据链路协议3基本问题基本问题 如何利用物理层的0-1比特流传输能力在相邻机器相邻机器间进行数据传输？问题分析问题分析 信道问题广播信道广播信道点对点信道每对连接对应一对机器4问题分析（续问题分析（续1） 地址问题地址问题通信主机标识问题（*） 面向连接还是非连接？面

2、向连接还是非连接？ 面向连接是基于电话系统模型是基于电话系统模型。也就是说，在数据传输前，有一个连接建立的过程，通信结束后，有一个连接断开的过程。（服务质量高） 面向非连接是基于邮政系统模型是基于邮政系统模型。也就是说，任何时候数据都可以直接发送。（服务质量低）5问题分析（续问题分析（续2） 数据封装问题数据封装问题帧格式帧格式 开始、结束标志 通信地址：面向连接时，建立连接过程需要地址；面向非连接时，数据传输时需要地址。 数据及编码 递交对象数据链路是数据传输服务层，到达目的机器后，数据必须递交给其他功能函数来处理。 流量控制问题流量控制问题发送者、接收者能力不对等问题 出错处理出错处理什么

3、是错？纠错？检错？不管？ 结论：数据传输需要协调双方的行为结论：数据传输需要协调双方的行为协议协议6数据链路层的地址问题数据链路层的地址问题 随机分配随机分配管理员分配配置 固化设置固化设置将地址固化到物理器械中如令牌环网等如以太网卡 一般来说，通信主体都应该拥有一个标识一般来说，通信主体都应该拥有一个标识 称为地址。称为地址。小探索：查看以太网卡的物理地址，并修改它。7数据封装问题数据封装问题帧格式（帧格式（1） 问题分析：什么是一个好的帧格式？（1）容易生成（2）重新实现帧同步的难度（3）普遍的适应性 将要传输的数据分成很多小段数据发送出去。8数据封装问题数据封装问题帧格式（帧格式（2）

4、字符计数法字符计数法 原理：在头部中的一个域指定该帧中的字符数。5个字符5个字符8个字符8个字符5 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 8 79 0 1 2 3第一帧8第二帧第三帧第四帧8字符计数 问题：出错后的帧无法同步5 1 2 3 4 7 6 7 8 90 1 2 3 4 5 6 8 79 0 1 2 3第一帧8第二帧8字符计数？9数据封装问题数据封装问题帧格式（帧格式（3） 字节填充法字节填充法 分析：字符计数法失去帧同步后，恢复很难。原因是很难区分计数的字符和数据字符。 原理：使用特殊的字符作为帧的开始和结束标志payloadFLAGFLAGheadertr

5、ailer 新的问题：如果负载重出现了FLAG了怎么办？AFLAGBFLAGFLAG10数据封装问题数据封装问题帧格式（帧格式（4） 字节填充法字节填充法 转义字节技术stuffing“ESC”ESCSame with flagFLAGAFLAGBFLAGFLAGAFLAGBFLAG 新问题：数据中包含了ESC怎么办？11数据封装问题数据封装问题帧格式（帧格式（5） 字节填充法字节填充法 转义字节技术data“ESC”stuffing“ESC”ESCFLAGAESCBFLAGFLAGA ESCBFLAG 其他问题？遇到第一个ESC，表示后面的是正常数据，不是特殊字符12数据封装问题数据封装问题

6、帧格式（帧格式（6） 字节填充法字节填充法 字节填充法存在什么问题？ 必须紧紧依赖于8位字符模式 不是所有的字符都是8位字符模式，如Unicode使用16位字符。结论：非结论：非8位字符模式，需要转换为位字符模式，需要转换为8位字位字符模式才能顺利传输符模式才能顺利传输 字符填充法分析13数据封装问题数据封装问题帧格式（帧格式（7） 位填充法位填充法 原理：帧开始和结束都有一个特殊的位模式01111110 问题：当传输数据中有01111110如何处理？ 解决办法：碰到连续5连续的位“1”的时候，自动填充一位00 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 1

7、 1 0 1 1 1 1 1 1 01 2 3 4 5 61 2 3 4 5 6 7 81 2 3 4 5 60 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 01 2 3 4 56 7 8 位填充法分析14数据封装问题数据封装问题帧格式（帧格式（8） 物理层编码违例法物理层编码违例法 原理：使用非数据编码信号来表示帧的边界。如以太网（MAC子层中介绍）曼彻斯特编码方式传输数据“1”的编码“0”的编码 其他编码方式，可以用作帧的边界 物理层编码违例法分析15流控制问题流控制问题 问题描述问题描述发送方的速度超过了接受方能

8、够接受这些帧的速度 基本处理方法基本处理方法 基于反馈的流控制 基于速率的流控制定义规则，规范发送者什么时候可以发送帧。（具体协议中介绍）限制发送方的速率。（后面章节中详细介绍）16出错处理（出错处理（1） 定义定义什么是错误？ 严格意义：凡是接收到的数据和发送的数据不一致 不一致：错误数据*、丢失数据、数据乱序 基本措施基本措施 纠错（错误纠正）：就是将不一致的数据恢复到一致 检错（错误发现）：检查数据中是否存在不一致 不作为先看看错误数据的基本措施，丢失先看看错误数据的基本措施，丢失和乱序问题在协议中介绍和乱序问题在协议中介绍17出错处理（出错处理（2） 纠错纠错纠错码纠错码 原理：在发送

9、的数据中包含冗余信息，以便接收者可以推断出数据中肯定有哪些内容。包含m个数据位和r个校验位的n-位单元，通常称为n位码字（n=m+r）。0 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0m bitsData bitsr bitsCheck bitsn bits codeword（ n = m + r ）有这么神奇的事情吗？18出错处理（出错处理（3） 纠错码纠错码 海明距离两个码字不相同的位的个数1 0 0 0 1 0 0 1 （码字1）1 0 1 1 0 0 0 1 （码字2）XORXOR0 0 1 1 1 0 0 0海

10、明距离d=3 含义理解：如果码字1出错后，变为码字2，则至少要3位数据发生错误 海明距离用来度量最少出错的位数19 海明距离用来度量最少出错的位数出错处理（出错处理（4） 纠错码纠错码 纠正d位错误的基本原理即假设传输过程中，最多d位出错。（1）对于传输数据m位，合法的报文有2m种情况；（2）对于传输的n位码字，可能的码字有2n种情况（n=m+r）；（3）从2n中选择2m个n位码字来表示合法的传输数据，并且保证每两个n位码间的距离至少为2d+1;（4）接收到数据A时，与所有的n位合法码字求解海明距离，海明距离小于d的，就是传输的数据。20出错处理（出错处理（5） 纠错码纠错码0 0 0 0 0

11、 0 0 0 0 0 （码字1）0 0 0 0 0 1 1 1 1 1 （码字2）1 1 1 1 1 0 0 0 0 0 （码字3）1 1 1 1 1 1 1 1 1 1 （码字4） 例子编码距离为5，因此2d+1=5，可得d=2，该方案可以纠错2位以下的错误。接收到数据00000 00111，与上面的码字计算海明距离，和码字2距离最小，为2，因此该数据有两位出错了，原始数据应该是00000 1111121出错处理（出错处理（6） 检错检错检错码检错码 原理：在发送的数据中包含冗余信息，以便接收者可以推断出数据中是否发生了错误。 奇偶检错方案检测单个错误 检错原理：在数据后面加上一个奇偶位，如

12、果码字中的“1”的位为偶数，则填0，如果是奇数，则填1。22出错处理（出错处理（7） 000001010011100101110111数据位数据位校验位校验位01101001校验位校验位00110010数据位数据位校验位校验位01senderreceivererror 奇偶校验例子 针对突发性长错误，可采用交错奇偶校验位来处理。23出错处理（出错处理（8） 循环冗余校验（Cyclic Redundancy Check, CRC）也称多项式编码（Polynomial Code） 基本思想 前提条件（1）将位串看成是系数为0或1的多项式。如如 10001011*x6 +0*x5+ 0*x4 + 0

13、*x3 +1*x2 +1*x1（2）发送方和接收在数据传输前商定一个生成多项式G(x).如如 G(x) = x4 + x + 1-10011（3）传输帧有m位，对应的多项式为M(x)。 校验和（Checksum） TCP/IP协议中使用的一种校验方法。24出错处理（出错处理（9） CRC校验和计算算法（1）假设G(x)的阶为r。在帧的低位端加上r个0，此时帧长为m+r，对应多项式为xrM(x)；（2）利用模2除法，用对应的G(x)的位串去除xrM(x)对应的位串，余数记为P(x) ；（3）利用模2减法， xrM(x)-除法运算中的余数P(x) ，结果记为T(x)就是带校验和的帧。25出错处理（

14、出错处理（10） CRC校验和计算例子校验和计算例子问题：发送数据帧 11 0101 1011m=10， M(x)为(m 1=9)阶多项式M(x) x9 + x8 + x6 + x4 + x3 + x + 1第一步：选择生成多项式G(x) = x4 + x + 1r=4，10011 第二步：形成多项式xrM(x) n=m+r=10+4=14， xrM(x) 为13阶多项式x4M(x) x13 + x12 + x10 + x8 + x7 + x5 + x411 0101 1011 000026出错处理（出错处理（11） CRC校验和计算例子校验和计算例子第三步：用以2为模的除法求余数 余数110

15、10110110000 /10011 = 1110第四步：用以2为模的减法计算校验和 发送帧T(x) 1101011011111027出错处理（出错处理（12） CRC检错能力说明检错能力说明（1）如果传输过程出错了，即有一些位的0或1发生了变化。把发生变化的位记录为1，其他位置为0，它对应一个多项式E(x)。（2）接收者的信息则为T(x)+E(x)；（3）校验时候计算为T(x)+E(x)/G(x)=E(x)/G(x) CRC校验和验证校验和验证 接收者接收到T(X)后，用T(x)/G(x)，余数应该为0，否则就判定为有错误。T(X)= xrM(x)-P(x)如果如果E(x)不被不被G(x)除

16、尽，则可以检测到传输过除尽，则可以检测到传输过程中出错了，如果刚好被除尽了，则该错误没程中出错了，如果刚好被除尽了，则该错误没有被检测到。所以有被检测到。所以G(x)很重要。很重要。28基本数据链路协议（基本数据链路协议（1） 应用情况应用情况 点到点信道，也就是只有一个发送者和接收者。 几个重要功能函数几个重要功能函数 from_network_layer to_network_layer from_physical_layer to_physical_layer29基本数据链路协议（基本数据链路协议（2） 无限制的单工协议无限制的单工协议 前提条件： 单方向数据传输（即只有一个发送者和接收

17、者） 理想信道（信道不出错，传输速度极快） 通信双方能力无穷（发送者不停发送，接收者不停接收） 发送者基本过程第一步：从网络层获得数据第二步：发送到物理层。 接收者基本过程第一步：等待数据到达第二步：从物理层提取数据第三步：把数据递交给网络层30基本数据链路协议（基本数据链路协议（3）SENDER:from_network_layerframingto_physical_layerto_network_layerRECEIVER:wait_for_eventfrom_physical_layer31基本数据链路协议（基本数据链路协议（4） 什么是协议？什么是协议？通信双方关于如何进行通信的一种

18、约定 什么是服务？什么是服务？实体为它的用户提供的功能。如无限制单工协议规范双方的行为来完成数据的传输如数据链路层为网络层提供传输数据的功能如物理层为数据链路层提供0-1比特流传输功能 什么是接口？什么是接口？定义调用服务的原语操作如from_physical_layer和to_physical_layer等 服务是用户的功能需求（该层要解决的问题）服务是用户的功能需求（该层要解决的问题） 协议是完成服务功能的实现过程（解决问题的程序）协议是完成服务功能的实现过程（解决问题的程序） 接口是程序的交互界面（用户操作界面）接口是程序的交互界面（用户操作界面）32基本数据链路协议（基本数据链路协议（

19、5） 无限制的单工协议分析无限制的单工协议分析现实问题：接收方的接收能力是有限制的。 无限制的单工协议改进无限制的单工协议改进 问题分析：假设接收者处理一帧的时间是t，则希望发送者在t时间后，再发送下一帧。 t t如何确定？如何知道接收者的如何确定？如何知道接收者的 t t？（很难估计）？（很难估计） 解决办法：因为信道是理想信道，速度很快的，让接收者在处理完毕一帧后，反馈一个信息告诉发送继续发送数据（基于反馈的流控制机制基于反馈的流控制机制）单工停单工停- -等协议等协议 关键问题：如何避免大量数据淹没接收方？关键问题：如何避免大量数据淹没接收方？流控制流控制33基本数据链路协议（基本数据链

20、路协议（6） 单工的停单工的停-等协议等协议 前提条件： 单方向数据传输（即只有一个发送者和接收者） 理想信道（信道不出错，传输速度极快） 接收者能力有限34A Bf1ack 发送者基本过程第一步：从网络层获得数据第二步：发送到物理层第三步：等待对方的反馈第一步：等待数据到达第二步：从物理层提取数据第三步：把数据递交给网络层第四步：发送反馈帧 接收者基本过程基本数据链路协议（基本数据链路协议（7）等待时间等待时间35基本数据链路协议（基本数据链路协议（8）SENDER:from_network_layerframingto_physical_layerRECEIVER:wait_for_eve

21、ntto_network_layerwait_for_eventfrom_physical_layerto_physical_layerWait for acksend ack36基本数据链路协议（基本数据链路协议（9） 单工的停单工的停-等协议分析等协议分析 问题1：理想信道是不存在的，信道有噪声，即传输过程中，帧可能会出错。 错误类型：（1）数据位出错；（2）数据丢失 处理错误方式分析：（1）数据位出错：纠错，检错检错+重传重传（如何选择？如何选择？）（2）数据丢失：将丢失的数据重传（解决问题效果如何？）解决问题效果如何？）37基本数据链路协议（基本数据链路协议（10） 单工的停单工的停-

22、等协议分析等协议分析 问题2：发送方如何知道数据丢失？没有接收到对方的反馈帧，则认为数据丢失！没有接收到对方的反馈帧，则认为数据丢失！ 后续问题：如果数据并没有丢失，而是反馈帧丢失了呢？接收到两个接收到两个A帧，都递帧，都递交给了上层协议数据重交给了上层协议数据重复，协议出错了。复，协议出错了。发送者接收者AA反馈帧丢失BAA解决办法：每一帧都带上一个编号，称为序列号解决办法：每一帧都带上一个编号，称为序列号定时器！定时器！38 单工的停单工的停-等协议分析等协议分析基本数据链路协议（基本数据链路协议（11） 序列号几位合适？发送者接收者ABCBBCQ 发送B帧时，A帧以及之前的帧已经发送并正

23、确接收。 如果要重传，则发送B帧，否则发送C帧。 对于接收到的Q帧，它可能是B帧或C帧。结论：对于停结论：对于停-等协议接收者而言，可能引起混淆的等协议接收者而言，可能引起混淆的帧最多是帧最多是2帧，因此需要帧，因此需要1位的序列号。位的序列号。39基本数据链路协议（基本数据链路协议（12） 有噪声的单工协议有噪声的单工协议 前提条件： 单方向数据传输（即只有一个发送者和接收者） 噪声信道（信道会出错：数据位错或丢失） 接收者能力有限 基本思想 在停-等协议的基础上，增加出错处理机制（超时重传输机制）40基本数据链路协议（基本数据链路协议（13） 有噪声的单工协议有噪声的单工协议 发送者基本过

24、程第一步：从网络层获得数据第二步：将帧编号，发送到物理层，启动超时定时器第三步：等待对方的反馈第四步：如果当前帧的确认帧到达，则跳到第一步第五步：如果超时定时器超时，则重传当前帧，并跳到第三步。第一步：等待数据到达第二步：从物理层提取数据，查看帧编号，确定是否是新的数据帧，如果不是，则跳到第一步，否则第三步，第三步：把数据递交给网络层第四步：发送反馈帧 接收者基本过程41next_frame_to send=0from_network_layerframingto_physical_layerstart_timerstop_timer(next_frame_to_send +1)mod2tim

25、eoutframe_arrivalwaitfrom_network_layer SENDERSENDER42frame_expected=0waitfrom_physical_layerexpected?to_network_layer(frame_expected+1)mod2send ackYNframe_arrivalCksum_err RECEIVERRECEIVER43基本数据链路协议（基本数据链路协议（14） 基本数据链路协议分析基本数据链路协议分析 问题问题：单工或半双工（即任何时候，线路上只有一个传输者和一个接收者），造成带宽浪费。 需求需求：单工协议的双工改造，即支持双向数据

26、传输 方法方法1：双独立信道+2单工协议信道1（A数据信道/B确认信道）信道2（B数据信道/A确认信道）主机A主机B带宽浪费！带宽浪费！主机主机A租用两条信道，实租用两条信道，实际使用的只有一条的容量际使用的只有一条的容量44基本数据链路协议（基本数据链路协议（15） 方法2：一条线路+2逻辑信道+2单工协议主机A主机B 方法分析：对于主机A，发送两种独立数据： 主机A数据帧 主机B确认帧帧结构很相似，如目的地址、源地址等。 改进思路：将数据帧和确认帧合并一起发送？也就是发送数据的同时，将确认信息附到外发的数据帧上。捎带确认技术（Piggybacking） 新的问题：如果主机暂时没有数据帧发送

27、呢？等待一段时间后，独立确认45基本数据链路协议（基本数据链路协议（16） 方法3一条线路+2逻辑信道+（2单工协议+捎带技术）双工协议 数据帧和确认帧使用同一种格式（捎带技术） 收到数据帧后，等待一段时间后，发送独立确认帧 方法3分析发送方接收方分组1分组1ACK1分组2分组2ACK2分组3确认机制发送方接收方分组1定时器分组1ACK1分组1定时器分组1ACK1分组2定时器重传机制任何时候，任何时候，线路上只线路上只有一个方有一个方向的数据。向的数据。效率低！效率低！46滑动窗口协议（滑动窗口协议（1）发送方接收方数据帧1数据帧1ACK1数据帧2数据帧2ACK2数据帧3数据帧3ACK3 基本

28、思想基本思想 在等待确认的时候，继续发送数据帧 一次最多能发送多少帧数据？窗口值如上例中，窗口值为347滑动窗口协议（滑动窗口协议（2） 数据传输的基本过程1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16数据帧数据帧WindowSize=8已发并已发并得到确认得到确认不能发送不能发送已发未已发未得到确认得到确认未发但未发但可以发可以发滑动窗口的来由！48滑动窗口协议（滑动窗口协议（3） 1位滑动窗口协议位滑动窗口协议滑动窗口大小为1 基本过程: 发送一帧，等待确认，然后下一帧（停-等协议）一切一切OK？next_frame_to_send=0;frame_expec

29、ted=0;from_network_layer(&buffer);=buffer;s.seq=next_frame_to_send;s.ack=1-frame_expected;to_physical_layer(&s);start_timer(s.seq);while(true)49 问题1：如果通信双方同时发送数据呢？A发送（0，1，A0）B发送（0，1，B0）B得到（0，1，A0）*B发送（0，0，B0）*A得到（0，1，B0）A发送（0，0，A0）B得到（0，0，A0）B发送（1，0，B1）B发送（0，0，B0）A发送（1，0，A1）即使没有传输错误，也会

30、有一半的帧是重复即使没有传输错误，也会有一半的帧是重复的！如果提前超时，也会出现类型情况！的！如果提前超时，也会出现类型情况！HOW？滑动窗口协议（滑动窗口协议（4）u1 1位滑动窗口协议分析位滑动窗口协议分析50滑动窗口协议（滑动窗口协议（5） 1位滑动窗口协议分析位滑动窗口协议分析 问题2：效率低下 卫星通信的例子 卫星信道50kbps 往返延时500ms（单程时间为250ms） 数据帧长度为1000bits发送数据时间=1000b/50kbps=20ms确认帧收到时间=500+20=520ms带宽利用率=20/520=3.85% 太浪费了！太浪费了！51滑动窗口协议（滑动窗口协议（6）

31、那么窗口大小为多少帧合适呢？ 理想状态：当窗口数据全部发送完毕时，正好第一帧的确认到达！发送者接收者1帧2帧收到1帧，ACK1收到2帧，ACK2n-1帧n帧收到n-1帧，ACKn-1收到n帧，ACKn发送窗口值为nn+1帧n+2帧管道化技术管道化技术 滑动窗口协议改进滑动窗口协议改进52滑动窗口协议（滑动窗口协议（7） 理想的窗口值 假设信道带宽为b 位/秒、往返时间为r秒、帧长为m位发送完窗口中n帧的时间=(m*n)/b 第一帧确认的时间=m/b+r(m(m* *n)/b=m/b+rn)/b=m/b+rn=1+rb/mn=1+rb/m如卫星通信例子中，理想窗口值n=1+rb/m=1+0.5*

32、50K/1000=26 管道技术分析管道技术分析53滑动窗口协议（滑动窗口协议（8） 管道技术分析管道技术分析 问题 如果在一个很长的帧流中有一帧出错了，如何对待后续的正确帧？ 两种基本方法 方法1(回退n帧方法） 接收方丢弃所有后续的帧，并且不为丢弃的帧发送确认帧。 方法2(选择性重传） 给所有正确接收的帧发送确认帧，给检查到错误的帧发送否定的确认。54滑动窗口协议（滑动窗口协议（9） 回退回退n帧技术帧技术errordiscardacksendtimeout0 1 E D D D D D D 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 res

33、end55滑动窗口协议（滑动窗口协议（10） 使用回退使用回退n帧技术的协议帧技术的协议 情况情况1：发送上层数据第一步：组装帧，捎带确认；第二步：发送数据；第三步：启动定时器； 情况情况3：定时器超时第一步：将超时间数据帧重新发送一次。第二步：重新启动定时器 情况情况2：接收到一帧第一步：检查数据是否是新鲜的，如果是，则将数据递交给上层；第二步：检查确认信息，如果是已经发送数据的确认，将有关的定时器终止，发送窗口前移动一格；通信进程基本过程：56滑动窗口协议（滑动窗口协议（11） 选择性重传技术选择性重传技术数据发送方数据接收方1帧2帧3帧4帧ACK1ACK3ACK4NAK257滑动窗口协议

34、（滑动窗口协议（12） 使用选择性重传技术的协议使用选择性重传技术的协议通信进程基本过程： 情况情况1：发送上层数据第一步：组装帧，捎带确认；第二步：发送数据；第三步：启动定时器； 情况情况2：接收到一帧第一步：检查数据是否是新鲜的，如果是，则将数据递交给上层；如果数据出错，则发送否定确认。第二步：检查确认信息，如果是已经发送数据的确认，将有关的定时器终止，发送窗口前移动一格；第三步：如果是否定确认，则将否定确认对应的帧重发； 情况情况3：定时器超时第一步：将超时间数据帧重新发送一次。第二步：重新启动定时器58滑动窗口协议（滑动窗口协议（13） 其他关键问题：如何确定数据的新鲜性?数据序列号 接收方接收方 0 1 2 3 4 5 6 发送方发送方 0 1 2 3 4 5 6 发送帧发送帧06等待确认。等待确认。帧帧06上交网络层，回送上交网络层，回送确认，接收窗口滑动。确认，接收窗口滑动。帧帧06的确认丢失！的确认丢失！以选择性重以选择性重传为例说明传为例说明假设滑动窗口值是8，数据帧序列号为0-759滑动窗口协议（滑动窗口协议（14