Chapter Four 数据链路层

本章教学提要 教学目标： 教学难点：差错控制，滑动窗口协议 教学时数：4学时 理解数据链路层的功能与作用； 理解常用的成帧方式； 理解差错控制的作用和原理； 了解流量控制的作用和原理； 了解HDLC协议的工作过程； 了解数据链路层的设备与组件。 教学难点：差错控制，滑动窗口协议 教学时数：4学时

问题的引入：为什么需要数据链路层？ 尽管物理层采取了一些必要的措施来减少信号传输过程中的噪声，但是数据在物理传输过程中仍然可能损坏或丢失。 DTE DCE 尽管物理层采取了一些必要的措施来减少信号传输过程中的噪声，但是数据在物理传输过程中仍然可能损坏或丢失。 由于物理层只关心原始比特流的传送，不考虑也不可能考虑所传输信号的意义和信息的结构，从而物理层不可能识别或判断数据在传输过程中是否出现了损坏或丢失，从而也谈不上采取什么方法进行补救。 也就是说，只有物理层的功能是不够的。

数据链路层的功能 数据链路层是为了克服物理层的物理传输质量不足而存在的。 其目的是为了实现两个相邻节点间的无差错传输。 从分层的角度，数据链路层利用了物理层提供的原始比特流传输服务，向网络层提供可靠的数据传输服务。

何为相邻节点？ 相邻节点是指由同一物理链路直接连接的所有节点。

数据链路层要解决的问题 如何识别不同的相邻节点或确定一个接收目标 如何提供一种机制使得接收方能识别数据流的开始与结束 物理编址与寻址； 如何提供一种机制使得接收方能识别数据流的开始与结束 成帧 如何实现可靠的数据传输： 如何提供差错检测与控制机制使得有差错的物理链路对网络层表现为一条无差错的数据链路； 如何提供流量控制机制以保证源和目标之间不会因发送和接收速率不匹配而引起数据丢失。

帧(Frame) 为了实现诸如差错控制、物理寻址和流量控制等功能，数据链路层首先要使自己所看到的数据是有意义的： 除了要传送的用户数据外，还要提供关于寻址、差错控制和流量控制等所必需的控制信息，而不再是物理层的原始比特流。 为此，数据链路层采用了被称为帧(frame)的协议数据单元作为该层的数据传送逻辑单元。 不同的数据链路层协议的核心任务就是根据所要实现的数据链路层功能来规定帧的格式，即语法和语义。

帧的一般示意图 帧的开始 地址 帧类型或长度 数据 帧校验 帧的结束 帧的定界 用于寻址 差错控制 帧中的语法成分被称为域或字段(field)； 上图只是帧的一般组成，不同的数据链路层协议所规定的帧格式可能会与其存在微小的区别。

帧的定界 定界就是标识帧的开始与结束 常用的帧定界方法： 字符计数法 带字符填充的首尾界符法 带位填充的首尾标志法

字符计数法 在帧头中使用一个字段来标明帧内的字符数，通常该字段称为帧长字段。 如果发生传输错误，则可能更改帧长的值，从而导致帧的同步出现问题。 该方法通常与下面介绍的其他方法结合使用。 6 A B C D E 5 U V W X 8 1 2 3 4 4 5 8 三个帧的长度分别为6字节、5字节和8字节。 6 A B C D E 7 U V W X 8 1 2 3 4 4 5 8 ？？？

首尾界符法 每一帧以ASCII字符序列DLE STX开始，以DLE ETX结束。 DLE为“Data Link Escape”的缩写，STX意味着“Start of Text”， ETX代表“ End of Text”。 其缺点是成帧完全依赖于8位字符，而且若数据部分也出现了DLE STX或DLE ETX，则接收端就会错误判断帧边界。 DLE … Data … STX ETX

首尾界符法中的字符填充 在首尾界符法中，由于数据中可能会出现DLE STX或DLE ETX，从而干扰帧的正常定界 字符填充法可用于解决上述问题。即发送端在数据中所遇到的DLE前再插入一个附加的DLE，而接收端则忽略两个连续DLE的前一个。 Data DLE STX … ETX … DLE ETX STX

首尾标记法 每一帧使用一个特殊的位模式“01111110”作为开始和结束标记。 该位模式又称为“flag”。 位模式允许数据帧包含任意个数的比特，也允许每个字符采用任意比特的编码。 … Data … 01111110

首尾标记法中的位填充 在首尾标记法中，由于数据中可能会出现与标记相同的位串，从而干扰帧的正常定界 位填充法可用于解决上述问题。即发送端在数据中若遇到5个连续的“1”时，则在其后自动插队入一个“0”。该技术简称“逢五1插0”；接收端则忽略5个连续的“1”后面的“0”，简称“逢五1删0” 。 Data 01111110 … 111111 111110 01111110 … 1111101 1111100

物理层编码违例法 利用物理层信息编码中未用的电信号来作为帧的边界。 以IEEE802局域网标准为例，其数据编码采用曼彻斯特编码，在传输之前将数据位“1”编码成高-低电平对，数据位“0”编码成低-高电平对，并利用高-高电平对和低-低电平对作为帧边界的特殊编码。 在实际应用中，数据链路层协议多数使用字符计数法与其他方法相结合作为帧定界的方法

帧的地址 帧中的地址属于物理或硬件地址 网卡地址(局域网) 链路标识(广域网) 用于设备或机器的物理寻址

差错控制 差错类型 差错衡量 差错控制

差错类型 要探寻差错控制的机制，首先要了解差错的产生原因及类型。 在物理层的讨论中，我们已经讨论了物理信道中所存在的各类噪声，噪声会引起数据传输中的错误。 根据噪声产生原因的不同，差错分为随机错和突发错。 热噪声→随机错 冲击噪声（如EMI，RFI）→突发错

差错的衡量 差错由误码率来衡量： Pe=错误接收的码元数/接收的码元总数 误码率越低，信道的传输质量越高。

差错控制 由于信道中的噪声是客观存在的，不管信道质量多高，都要进行差错控制。 所谓差错控制就是通过发现传输中的错误，来采取相应的措施。

差错控制的核心 差错控制的核心是对传送的数据信息加上与其满足一定关系的冗余码，形成一个加强的、符合一定规律的发送序列。 接收端利用相同的规律进行检查从而发现错误，所加入的冗余码称校验码。 校验码的分类： 纠错码 检错码

纠错码 纠错码不仅能发现传输中的错误，还能利用纠错码中的信息自动纠正错误。 对应的差错控制措施为自动向前纠错。 汉明码（Hamming code)为典型的纠错码，具有很高的纠错能力。 　　对此编码有兴趣的同学请自行查找有关的参考资料，如Andrew.《计算机网络》（第3版）清华大学出版社。

检错码 检错码用来发现传输中的错误，但不能自动纠正所发现的错误。 对应的差错控制措施为反馈重发纠错 。 常见的检错码有： 奇偶校验码 　奇偶校验码 　循环冗余校验码（CRC）

差错控制措施：反馈重发 由于检错码不能自动纠正所发现的错误，所以当接收方发现错误时，要给发送方反馈信息要求重发。 含义： 常见的实现方法： 停止等待方式 连续工作方式     1）拉回方式(back to n) 2）选择重发方式(selective)

拉回方式 含义： 假定发送方连续发送了m帧，而接收方在对收到的数据帧进行校验后发现第n帧出错，于是接收方给发送方出错信息要求发送方重发第n帧及第n帧以后的所有帧。换言之，一旦接收方发现第n帧出错，则丢弃第n帧及第n帧以后的所有帧。 代价 　 信道的带宽

选择重发方式 含义： 假定发送方连续发送了m帧，而接收方在对收到的数据帧进行校验后发现第n帧出错（n≤m) ，于是接收方给发送方出错信息要求发送方重发第n帧。换言之，一旦接收方发现第n帧出错，则丢弃第n帧，但缓存第n帧以后的所有正确帧。 代价 　 存储空间

奇偶校验 垂直奇偶校验： 　　在面向字符的数据传输中，在每个字符的7位信息码后附加一个校验位0或1，使整个字符中“1”的个数构成奇数个（奇校验）或偶数个（偶校验）。 水平奇偶校验： 　　　在发送字符块的末尾附加一个校验字符，且该字符中的第i位是针对所有字符的第i位所进行的校验。 垂直水平奇偶校验 　　　垂直奇偶校验和水平奇偶校验技术的综合。对每个字符作垂直校验，对整个字符块作水平校验。

奇校验的例子 1 1 1 1 1 1 1 1 1 b1 b2 b3 b4 b5 b6 b7 check 校验字符 字符1 字符2 字符3 1 校验字符 1 字符1 1 字符2 1 字符3 1 字符4 1 字符5 1 字符5 1 字符6 1 字符7 b1 b2 b3 b4 b5 b6 b7 check

循环冗余校验 循环冗余校验 英文全称为Cyclic Redundancy Check ,简称CRC。 工作原理： 　　多项式除法，将余式作为冗余信息传送。 又称多项式校验

数的除法与多项式除法的比较 数的除法： 多项式除法： 被除数=除数*商+余数 被除多项式=除式*商+剩余多项式 　（换言之，被除多项式减去剩余多项式可以用除式整除）

CRC的工作原理（1） P(x)=an-1xn-1 +an-2xn-2 + a1x + a0 将要发送的二进制数序列看成是一个多项式。n位的数据序列对应n-1次多项式。 　　P(x)=an-1xn-1 +an-2xn-2 + a1x + a0 　 选定除式，被选作除式的多项式称为生成多项式，常见的生成多项式有： CRC-12： G(x)=x12 +x11 +x3 + x2 + x + 1 CRC-16： G(x)=x16 +x15 + x2 + 1 CRC-CCITT： G(x)=x16 +x12 + x5 + 1 CRC-32： G(x)=x32 +x26 +x23 + x22 + x16 +x12+ x11 +x10 +x8 + x7 + x5 +x4 + x2 + x + 1

CRC的工作原理（2） 将P(x)乘以 G(x)的最高幂次作为被除式，作多项式除式。除法采用“加法不进位，减法不借位”的规则，即相当于异或操作； 将所得到的余式多项式R(x)重新转换为二进制数，作为冗余码；　　　　 将冗余码加在原传送数据后面，构成发送序列； 接收方收到后，将接收序列用同样的生成多项式去除。若余式为零，则表示无差错；否则，说明传输过程中出现了错误。

CRC的例子（1） 要发送的二进制数序列为“110011”，6位的数据序列对应5次多项式： P(x)=x5+x4+x+1 选定的生成多项式为： 　　G(x)=x4 +x3 + 1 　　（最高次数为4，相当于11001） 被除多项式为： 　　 P(x)x4＝ x9+x8+ x5+ x4　　 　　　 （相当于1100110000）

CRC的例子（2） 1 11001 1 11001 0000 1100110000 11001 10000 1001 多项式除法后得到冗余码为1001(注意：冗余码的位数与G(x)幂次相同，请学生思考为什么？），所以相应的数据发送序列为110011 1001 CRC校验可以由软件或硬件来实现，现多采用超大规模集成电路芯片以硬件方式实现。

CRC的检错能力 全部单个错 全部离散的二位错 全部奇数个错 全部长度小于或等于K的突发错（ K为生成多项式的最高幂次）

流量控制 由于系统性能的不同，如硬件能力（包括CPU，存储器等）和软件功能的差异，会导致发送方与接收方处理数据的能力有所不同。 流量控制的作用是使发送方所发出的数据流量，使其发送速率不要超过接收方所能接收的速率。 流量控制的关键是需要有一种信息反馈机制，使发送方能了解接收方是否能接收到 存在各种不同的流量控制机制。如简单的停等协议，而滑动窗口协议则将关于帧的确认与流量控制巧妙地结合在了一起。

滑动窗口协议 在滑动窗口协议中，每一个要发送的帧都有包含一个序列号，其范围从0到某一个值。若帧中用以表达序列号的字段长度为n，则序列号的最大值为2n-1。 任何时候发送方保持着一组序列号，对应于允许发送的帧，并且这些帧被认为在发送窗口内。 任何时候接收方也保持着一组序列号，对应于允许接收的帧，并且这些帧被认为在接收窗口内。接收窗口的大小等于发送方未收到接收方的确认之前所能发送的最多帧。 发送窗口与接收窗口可以不具有相同的窗口上限与下限，也可以具有不相同的窗口大小。 在某些协议中，窗口大小在传输过程中还可动态调整。

滑动窗口协议的例子1：3位长度的序列号，窗口大小为4帧 1 2 3 4 5 6 7 1 2 3 4 5 6 7 初始状态：发送方等待发送帧，接收方等待接收帧 1 2 3 4 5 6 7 1 2 3 4 5 6 7 状态2：发送方发送帧0和1，接收方等待接收帧 1 2 3 4 5 6 7 1 2 3 4 5 6 7 状态3：接收方正确接收了接收帧0和1，并给发送方确认消息 1 2 3 4 5 6 7 1 2 3 4 5 6 7 状态4：发送方收到了关于0和1的确认消息

滑动窗口协议的例子2：3位长度的序列号，窗口大小为4帧 1 2 3 4 5 6 7 1 2 3 4 5 6 7 初始状态：发送方等待发送帧，接收方等待接收帧。 1 2 3 4 5 6 7 1 2 3 4 5 6 7 状态2：发送方发送帧0、1、2和3，接收方等待接收帧。 1 2 3 4 5 6 7 1 2 3 4 5 6 7 状态3：接收方正确接收了接收帧0、1和2，并给发送方确认。 1 2 3 4 5 6 7 1 2 3 4 5 6 7 状态4：发送方收到了关于0、1和2的确认消息。

成帧与拆帧 引入帧后，在发送方，数据链路层从网络层获得分组（Packet)后，要加上必要的帧头与帧尾后传送给物理层，并通过物理层传送到接收方的数据链路层。 这种加上帧头与帧尾的过程就称为成帧(Framing)。 在接收方，数据链路层则必须去掉发送端数据链路层所加的帧头和帧尾部分，从中分离出网络层所需的分组. 将帧重新拆装成分组的过程称为拆帧。

数据链路层提供的服务 可以将数据链路层设计成提供各种服务，实际的服务因系统的不同而不同。 通常有三种基本的服务可供选择： 无确认的无连接服务 有确认的无连接服务 有确认的面向连接的服务

无确认的无连接服务 源机器向目标机器发送独立的数据帧，而目的机器不对收到的帧作确认。 由于线路上的噪声而造成的帧丢失，数据链路层不作努力去恢复，而将该工作留给上层（通常为传输层）。 事先不存在建立连接，事后也不存在释放 适用于误码率较低的信道，如大多数的局域网中。

有确认的无连接服务 事先不存在建立连接，事后也不存在释放 源机器向目标机器发送独立的数据帧，但目的机器对收到的每一帧作确认。 若某个确定的时间间隔内未能收到确认帧（超时），则发送方自动重发， 适用于无线通信系统之类的不可靠信道。

有确认的面向连接的服务 传送数据前，事先要建立一条连接 在连接上所传送的每一帧都要编上号，数据链路层保证每一帧都收到，且每一帧只被正确接收一次，并保证所有的帧按正确顺序被接收。 真正为网络层提供了可靠的无差错传输服务。 适用于误码率较高的不可靠信道，如某些广域网链路。

数据链路层协议的例子--HDLC HDLC为英文High level data link control 的缩写，称为高能数据链中控制协议，由ISO颁布。前身为IBM开发的SDLC（Synchronous data link control) 面向位的协议（采用Flag和位填充）支持全双工通信，采用位填充的成帧技术，以滑动窗口协议进行流量控制 。

数据字段为任意长，但校验效率随着数据长度的增加而下降。 HDLC的帧 Flag 01111110 8 地址 A 8 控制字段 C 8 数据 I ≥ 0 帧校验 FCS 16 Flag 01111110 8 范围A、C、I 采用CRC-16 首尾标记法 数据字段为任意长，但校验效率随着数据长度的增加而下降。

HDLC的三种帧类型 在HDLC帧中，通过控制字段给出了不同的帧类型，包括信息帧、监控帧和无符号帧。 SEQ （3位序列号） P/F SEQ （3位序列号） P/F NEXT （下一发送序列号） I帧用于发送数据，并具有确认/差错和流量控制 1 0 TYPE （2位） P/F NEXT （下一发送序列号） S帧用于协调双方通信状态，包括差错和流量控制 1 1 TYPE P/F Modifier U帧用于数据链路控制，包括建立连接和拆除连接

HDLC用于有确认的面向连接服务的示意图 A B A发送无符号帧请求建立连接 1 1 Modifier P/F B发送无符号帧确认建立连接 1 1 Modifier P/F A发送编号为0的数据帧 P/F A发送编号为1的数据帧 1 P/F B发送编号为0的数据帧，并对A的第1帧进行确认 P/F 2 A发送无符号帧请求断开连接 1 1 Modifier P/F B发送无符号帧确认断开连接 1 1 Modifier P/F

B发送编号为0的数据帧，并对A的第1帧进行确认 A发送编号为2的数据帧，并对B的第0帧进行确认 B发送监控帧报告第2帧出错，并要求选择重发 HDLC的差错控制示意图 A发送编号为1的数据帧 1 P/F A B B发送编号为0的数据帧，并对A的第1帧进行确认 P/F 2 A发送编号为2的数据帧，并对B的第0帧进行确认 2 P/F 1 A发送编号为3的数据帧 3 P/F 1 B发送监控帧报告第2帧出错，并要求选择重发 1 0 1 1 P/F 2 A重发编号为2的数据帧 2 P/F 1 A继续发送编号为4的数据帧 4 P/F 1 A发送无符号帧请求断开连接 1 1 Modifier P/F B发送无符号帧确认断开连接 1 1 Modifier P/F

问题：数据链路层有设备与组件吗？ 在物理层我们了解了不少的设备与组件，那么在数据链路层是否也有相应的设备与组件？ 若有，这些设备与组件与物理层的设备与组件有什么功能上的区别？ 数据链路层的设备与组件是指那些同时具有物理层和数据链路层功能的设备或组件。 数据链路层的组件有网卡，主要设备包括网桥和交换机。

网卡 局域网中提供各种网络设备与网络通信介质相连的接口，全名是网络接口卡（NIC，Network Interface Card），也叫网络适配器 。 网卡作为一种I/O接口卡插在主机板的扩展槽上，其基本结构包括接口控制电路、数据缓冲器、数据链路控制器、编码解码电路、内收发器、介质接口装置等六大部分。 主要实现数据的发送与接收、帧的封装与拆封、编码与解码、介质访问控制和数据缓存等功能。

用于台式PC机的以太网网卡 用于笔记本电脑的网卡 用于台式PC机无线局域网网卡

网卡的基本结构 AUI 内部总线 介质接口装置 数据缓冲帧的装配与拆卸 MAC层协议 控制电路 编码与解码电路 收发电路

网卡地址 每一网卡在出厂时都被分配了一个全球唯一的地址标识，该标识被称为网卡地址或MAC地址； 网卡地址被固化在网卡上，并被局域网的数据链路层用于识别不同的物理节点即寻址，所以又被称为物理地址或硬件地址。 网卡地址由48bit长度的二进制数组成。其中，前24bit表示生产厂商，后24bit为生产厂商所分配的产品序列号。 若采用12位的十六进制数表示，则前6个十六进制数表示厂商，后6个十六进制数表示该厂商网卡产品的序列号。

网桥 Bridge，也叫桥接器。 工作在数据链路层的一种网络互连设备，其可以实现两个或多个LAN的互联； 主要功能包括： 物理上扩展网络 基于第二层地址的数据过滤功能 逻辑划分网络的功能 数据推进功能 帧格式转换功能

网桥工作原理示意

网桥基于第二层地址进行工作，所以被归为数据链路层设备 网桥与OSI模型 网桥基于第二层地址进行工作，所以被归为数据链路层设备

交换机 Switch ，也是工作在数据链路层的一种网络互连设备。 由网桥发展而来，是一种多端口的网桥，其通过在其内部配备大容量的交换式背板实现了高速数据交换。 根据涉及的第二层技术，分为以太网交换机、FDDI交换机、帧中继交换机、ATM交换机和令牌环交换机等。

交换机工作示意图 LAN1 LAN4 LAN2 LAN3 A001CD201B56 LAN1/PORT1 20017D201B96 …… 79E17D2019B6 LAN4 /PORT12 交换机工作示意图 LAN1 LAN4 LAN2 LAN3

交换机与网桥一样，基于第二层地址进行工作，因此也属于数据链路层设备 交换机与OSI模型 交换机与网桥一样，基于第二层地址进行工作，因此也属于数据链路层设备

APDU PPDU Frame Bits SPDU Packet SPDU Segment Bridge/Switch

交换机与网桥的比较 相同性： 均为OSI第二层的网络互连设备。交换机作为多端口网桥，具备了网桥所拥有的全部功能，如物理上扩展网络、逻辑上划分网络等。 区别： 作为对网桥的改进设备，交换机： 1)可以提供高密度的连接端口； 2)采用的基于交换背板的虚电路连接方式，可为每个交换机端口提供更高的专用带宽； 3)数据转发基于硬件实现，较网桥采用软件实现数据的存储转发具有更高的交换性能。

交换机作为多端口网桥的交换机可以取代多个网桥的作用，且具有更高的带宽