第4章数据链路层 第4章数据链路层 本章基本要求：掌握数据链路层的功能与作用，掌握差错控制的作用和原理，掌握数 据链路层的设备与组件：理解常用的成顿方式，理解流量控制的作用和原理，理解HDLC 协议的主要内容。 本章难点：差错控制，滑动窗口协议 数学时数与实验：4.5学时，无实哈 上一章我们己经学习了物理层的有关知识，本章我们将介绍数据链路层的相关知识， 包括数据链路层的功能以及实现这些功能的若干重要机制。 4.1数据链路层概述 4.1.1为什么需要数据链路层 至少有两个理由可用来说明数据链路层存在的必要性。首先，尽管物理层采取了一些 必要的措施来减少信号传输过程中的噪声，但是数据在物理传输过程中仍然可能损坏或丢 失。由于物理层只关心原始比特流的传送，所以物理层不考虑也不可能考虑所传输信号的 意义和信息的结构，也就是说物理层不可能识别或判断数据在传输过程中是否出现了损坏 或丢失，从而也谈不上采取什么方法进行补救。其次，物理层也不考虑当发送站点的发送 速度过快而接收站点接收的速度过慢时，应采取何种策略来控制发送站点的发送速度，以 避免接收站点来不及处理而丢失数据。可见只有物理层的功能是不够的，位于物理层之上 的数据链路层就是为了克服物理层的这些不足而建立的。 数据链路层旨在实现网络上两个相邻节点之间的无差错传输。它利用了物理层提供的 原始比特流传输服务，检测并校正物理层的传输差错，使在相邻节点之间构成一条无差错 的链路，从而向网络层提供可靠的数据传输服务。 4.1.2相邻节点的概念 那么何为相邻节点呢？所谓相邻节点是指由同一物理链路连接的所有节点。因此，不 仅图4.1(a)所示的网络环境中的两个节点属于相邻节点，图4.1(b)中的四个由同一物理线路 连接的节点也属于相邻节点。相邻节点的最主要特征是节点之间的数据通信不需要经过其
第 4 章 数据链路层 1 第 4 章 数据链路层 本章基本要求：掌握数据链路层的功能与作用，掌握差错控制的作用和原理，掌握数 据链路层的设备与组件；理解常用的成帧方式，理解流量控制的作用和原理，理解 HDLC 协议的主要内容。 本章难点：差错控制，滑动窗口协议 教学时数与实验：4-5 学时，无实验。 上一章我们已经学习了物理层的有关知识，本章我们将介绍数据链路层的相关知识， 包括数据链路层的功能以及实现这些功能的若干重要机制。 4.1 数据链路层概述 4.1.1 为什么需要数据链路层 至少有两个理由可用来说明数据链路层存在的必要性。首先，尽管物理层采取了一些 必要的措施来减少信号传输过程中的噪声，但是数据在物理传输过程中仍然可能损坏或丢 失。由于物理层只关心原始比特流的传送，所以物理层不考虑也不可能考虑所传输信号的 意义和信息的结构，也就是说物理层不可能识别或判断数据在传输过程中是否出现了损坏 或丢失，从而也谈不上采取什么方法进行补救。其次，物理层也不考虑当发送站点的发送 速度过快而接收站点接收的速度过慢时，应采取何种策略来控制发送站点的发送速度，以 避免接收站点来不及处理而丢失数据。可见只有物理层的功能是不够的，位于物理层之上 的数据链路层就是为了克服物理层的这些不足而建立的。 数据链路层旨在实现网络上两个相邻节点之间的无差错传输。它利用了物理层提供的 原始比特流传输服务，检测并校正物理层的传输差错，使在相邻节点之间构成一条无差错 的链路，从而向网络层提供可靠的数据传输服务。 4.1.2 相邻节点的概念 那么何为相邻节点呢？所谓相邻节点是指由同一物理链路连接的所有节点。因此，不 仅图 4.1 (a)所示的网络环境中的两个节点属于相邻节点，图 4.1(b)中的四个由同一物理线路 连接的节点也属于相邻节点。相邻节点的最主要特征是节点之间的数据通信不需要经过其
2 计算机网络技术 他交换设备的转发。 a b 图4.1相邻节点的示例 4.1.3数据链路层需要解决的主要问题 为实现相邻节点之间的可靠传输，数据链路层必须要解决以下问题：在相邻的节点之 间确定一个接收目标，即实现物理寻址：提供一种机制使得接收方能识别数据流的开始与 结束：提供相应的差错检测与控制机制以使有差错的物理链路对网络层表现为一条无差错 的数据链路：提供流量控制机制以保证源和目标之间不会因发送和接收速率不匹配而引起 数据丢失。 下面我们分几个小节来介绍数据链路层解决这些问题的相关机制。 4.2帧与成帧 为了实现上述诸如差错控制、物理寻址和流量控制等一系列功能，数据链路层必须要 使自己所看到的数据是有意义的，其中除了要传送的用户数据外，还要提供关于寻址、差 错控制和流量控制所必需的信息，而不再是物理层所谓的原始比特流。为此，数据链路层 采用了被称为帧(am)的协议数据单元作为数据链路层的数据传送逻辑单元。不同的数据 链路层协议的核心任务就是根据所要实现的数据链路层功能来规定帧的格式。 4.2.1帧的基本格式 尽管不同的数据链路层协议给出的帧格式都存在一定的差异，但它们的基本格式还是 大同小异的。图42给出了帧的基本格式，组成帧的那些具有特定意义的部分被称为域或宁 段(field)。 帧开始 地址 长度/类型控制 数据FCS 帧结束 图4.2帧的基本格式 其中，帧开始字段和帧结束字段分别用以指示顿或数据流的开始和结束。地址字段给 出节点的物理地址信息，物理地址可以是局域网网卡地址，也可以是广域网中的数据链路
2 计算机网络技术 他交换设备的转发。 (a) (b) 图 4.1 相邻节点的示例 4.1.3 数据链路层需要解决的主要问题 为实现相邻节点之间的可靠传输，数据链路层必须要解决以下问题：在相邻的节点之 间确定一个接收目标，即实现物理寻址；提供一种机制使得接收方能识别数据流的开始与 结束；提供相应的差错检测与控制机制以使有差错的物理链路对网络层表现为一条无差错 的数据链路；提供流量控制机制以保证源和目标之间不会因发送和接收速率不匹配而引起 数据丢失。 下面我们分几个小节来介绍数据链路层解决这些问题的相关机制。 4.2 帧与成帧 为了实现上述诸如差错控制、物理寻址和流量控制等一系列功能，数据链路层必须要 使自己所看到的数据是有意义的，其中除了要传送的用户数据外，还要提供关于寻址、差 错控制和流量控制所必需的信息，而不再是物理层所谓的原始比特流。为此，数据链路层 采用了被称为帧(frame)的协议数据单元作为数据链路层的数据传送逻辑单元。不同的数据 链路层协议的核心任务就是根据所要实现的数据链路层功能来规定帧的格式。 4.2.1 帧的基本格式 尽管不同的数据链路层协议给出的帧格式都存在一定的差异，但它们的基本格式还是 大同小异的。图 4.2 给出了帧的基本格式，组成帧的那些具有特定意义的部分被称为域或字 段(field)。 帧开始 地址 长度/类型/控制 数据 FCS 帧结束 图 4.2 帧的基本格式 其中，帧开始字段和帧结束字段分别用以指示帧或数据流的开始和结束。地址字段给 出节点的物理地址信息，物理地址可以是局域网网卡地址，也可以是广域网中的数据链路
第4章数据链路层 3 标识，地址字段用于设备或机器的物理寻址。第三个字段则提供有关帧的长度或类型的信 息，也可能是其他一些控制信息。数据字段承载的是来自高层即网络层的数据分组(packet)。 帧检验序列FCS(Frame Check Sequence)字段提供与差错检测有关的信息。通常数据字段之 前的所有字段被统称为帧头部分，而数据字段之后的所有字段被称为帧尾部分。 4.2.2成帧与拆帧 从顺的基本格式可以看出，帧提供了与数据链路层功能实现相关的各种机制，如寻址 差错控制、数据流定界等。可以说数据链路层协议将其要实现的数据链路层功能集中体现 在其所规定的帧格式中。引入帧机制不仅可以实现相邻节点之间的可靠传输，还有助于提 高数据传输的效率。例如，若发现接收到的某一个（或几个）比特出错时，可以只对相应 的姊讲行特殊处理（如请求重发等），而不需要对其他未出错的城讲行这种处理：如果发现 某一帧被丢失，也只要请求发送方重传所丢失的帧，从而大大提高了数据处理和传输的效 率。但是，引入顺机制后，发送方的数据链路层必须提供将从网路层接收的分组(Packet) 封装成帧的功能，即为来自上层的分组加上必要的帧头和帧尾部分，通常称此为成顿 (阳g):而接收方数据链路层则必须提供将帧重新拆装成分组的拆帧功能，即去掉发关瑞 数据链路层所加的顿头和帧尾部分，从中分离出网络层所需的分组。在成帧过程中，如果 上层的分组大小超出下层帧的大小限制，则上层的分组还要被划分成若干个帧才能被传输， 发送端和接收端数据链路层所发生的帧发送和接收过程大致如下：发送端的数据链路 层接收到网络层的发送请求之后，便从网络层与数据链路层之间的接口处取下待发送的分 组，并封装成顺，然后经过其下层物理层送入传输信道：这样不断地将顿送入传输信道就 形成了连续的比特流：接收端的数据链路层从来自其物理层的比特流中识别出一个一个的 独立帧，然后利用帧中的CS字段对每一个帧进行校验，判断是否有错误。如果有错误， 就采取收发双方约定的差错控制方法进行处理。如果没有错误，就对帧实施拆封，并将其 中的数据部分即分组通过数据链路层与网络层之间的接口上交给网络层，从而完成了相邻 节点的数据链路层关于该帧的传输任务。 4.2.3帧的定界 引入帧后，数据链路层必须提供关于帧边界的识别功能，即所谓帧定界(fram boundary.)。帧定界就是标识帧的开始与结束。有四种常见的定界方法，即字符计数法、带 字符填充的首尾界符法、带位填充的首尾标志法和物理层编码违例法。下面分别予以简单 的介绍。 1.字符计数法 此方法是在颜头部中使用一个字符计数字段来标明顺内字符数。接收瑞根据这个计数 值来确定该帧的结束位置和下一帧的开始位置。例如，发送序列“6 ABCDE5LYWX8 1234458”表示一共有三个帧，且三个帧的长度分别为6字节、5字节和8字节
第 4 章 数据链路层 3 标识，地址字段用于设备或机器的物理寻址。第三个字段则提供有关帧的长度或类型的信 息，也可能是其他一些控制信息。数据字段承载的是来自高层即网络层的数据分组(packet)。 帧检验序列 FCS (Frame Check Sequence)字段提供与差错检测有关的信息。通常数据字段之 前的所有字段被统称为帧头部分，而数据字段之后的所有字段被称为帧尾部分。 4.2.2 成帧与拆帧 从帧的基本格式可以看出，帧提供了与数据链路层功能实现相关的各种机制，如寻址、 差错控制、数据流定界等。可以说数据链路层协议将其要实现的数据链路层功能集中体现 在其所规定的帧格式中。引入帧机制不仅可以实现相邻节点之间的可靠传输，还有助于提 高数据传输的效率。例如，若发现接收到的某一个（或几个）比特出错时，可以只对相应 的帧进行特殊处理（如请求重发等），而不需要对其他未出错的帧进行这种处理；如果发现 某一帧被丢失，也只要请求发送方重传所丢失的帧，从而大大提高了数据处理和传输的效 率。但是，引入帧机制后，发送方的数据链路层必须提供将从网络层接收的分组（Packet） 封装成帧的功能，即为来自上层的分组加上必要的帧头和帧尾部分，通常称此为成帧 (framing)；而接收方数据链路层则必须提供将帧重新拆装成分组的拆帧功能，即去掉发送端 数据链路层所加的帧头和帧尾部分，从中分离出网络层所需的分组。在成帧过程中，如果 上层的分组大小超出下层帧的大小限制，则上层的分组还要被划分成若干个帧才能被传输。 发送端和接收端数据链路层所发生的帧发送和接收过程大致如下：发送端的数据链路 层接收到网络层的发送请求之后，便从网络层与数据链路层之间的接口处取下待发送的分 组，并封装成帧，然后经过其下层物理层送入传输信道；这样不断地将帧送入传输信道就 形成了连续的比特流；接收端的数据链路层从来自其物理层的比特流中识别出一个一个的 独立帧，然后利用帧中的 FCS 字段对每一个帧进行校验，判断是否有错误。如果有错误， 就采取收发双方约定的差错控制方法进行处理。如果没有错误，就对帧实施拆封，并将其 中的数据部分即分组通过数据链路层与网络层之间的接口上交给网络层，从而完成了相邻 节点的数据链路层关于该帧的传输任务。 4.2.3 帧的定界 引入帧后，数据链路层必须提供关于帧边界的识别功能，即所谓帧定界（frame boundary）。帧定界就是标识帧的开始与结束。有四种常见的定界方法，即字符计数法、带 字符填充的首尾界符法、带位填充的首尾标志法和物理层编码违例法。下面分别予以简单 的介绍。 1. 字符计数法 此方法是在帧头部中使用一个字符计数字段来标明帧内字符数。接收端根据这个计数 值来确定该帧的结束位置和下一帧的开始位置。例如，发送序列“6 A B C D E 5 U V W X 8 1 2 3 4 4 5 8”表示一共有三个帧，且三个帧的长度分别为 6 字节、5 字节和 8 字节
4 计算机网络技术 但是这种方法很容易出现定界错误。仍以刚才的发送序列为例，当计数值出现传输差 错，如接收端收到的序列为“6 ABCDE7八YWX81234458”时，则接收端会将第 二帧解释为“UVWX81”,从而导致因发收双方对帧大小理解的不一致而出错。 2.带字符填充的首尾界符法 此方法是在每一帧的开头用ASCII字符DLE STX,在帧末尾用ASCI字符DLE ETX。 但是，如果在帧的数据部分也出现了DLE STX或DLE ETX,那么接收端就会错误判断帧 边界。为了不影响接收方对帧边界的正确判断，采用了填充字符DLE的方法。即如果发送 方在帧的数据部分遇到DLE,就在其前面再插入一个DLE。这样数据部分的DLE就会成对 出现。在接收方，若遇到两个连续的DLE,则认为是数据部分，并删除一个DLE。 例如，待发送的数据是A DLECB，则在数据链路层封装的帧为 DLE STX ADLEDLECBDLE ETX 其中DLE STX是帧首标记，斜体DLE是填充的DLE字符，DLEETX则是帧尾标记。 通过这种DLE字符的填充法，接收方就能保证帧边界字符的唯一性。 因为DLE是一个字符，发送方每次在数据部分中遇到一个DLE字符时，就必须插入 个8bt长的DLE。如果待传送的数据中有很多DLE字符，那么帧中就会包含大量的沉余 DLE。这也是带字符填充的首尾界符法的一个不足之处。 3.带位填充的首尾标志法 与字符填充技术类似，带位填充的首尾标志法也是一种填充技术，但是它一次只填充 一个比特“0”而不是一个字符“DLE”。另外，带位填充的首尾标志法用一个特殊的位模 式“O111I0”作为帧的开始和结束标志，而不是分别用“DLE STX”和“DLE ETX”作 帧的首标志和帧的尾标志。 当发送方在数据部分遇到5个连续的“1”时，就自动在其后插入一个“0”，即所谓的 “逢五个1插0”。例如，若原始数据为 011100111111111111111010 则经过填充后就变为 011100111110111110111110010 其中三个里体“0”为填充的位。 当接收方遇到5个连续的“1”之后是一个“0”时，就删除该“0”，即所谓的“逢五 个1删0”。这样就保证了在帧的数据部分不会出现“01111110”位串，从而使接收方能准 确地判断出帧边界。 与上述字符填充法相比，这种位填充技术存在明显的优势。其在位模式基础上入了 “逢五个1删0”和“逢五个1插0”机制，保证了帧边界标志“01111110”的唯一性。带 位填充的首尾标志法是比较常用的成帧方法，本章后面介绍的数据链路层协议HDLC就使 用了这种帧定界方法
4 计算机网络技术 但是这种方法很容易出现定界错误。仍以刚才的发送序列为例，当计数值出现传输差 错，如接收端收到的序列为“6 A B C D E 7 U V W X 8 1 2 3 4 4 5 8”时，则接收端会将第 二帧解释为“7 U V W X 8 1”，从而导致因发收双方对帧大小理解的不一致而出错。 2．带字符填充的首尾界符法 此方法是在每一帧的开头用 ASCII 字符 DLE STX，在帧末尾用 ASCII 字符 DLE ETX。 但是，如果在帧的数据部分也出现了 DLE STX 或 DLE ETX，那么接收端就会错误判断帧 边界。为了不影响接收方对帧边界的正确判断，采用了填充字符 DLE 的方法。即如果发送 方在帧的数据部分遇到 DLE，就在其前面再插入一个 DLE。这样数据部分的 DLE 就会成对 出现。在接收方，若遇到两个连续的 DLE，则认为是数据部分，并删除一个 DLE。 例如，待发送的数据是 A DLE C B ，则在数据链路层封装的帧为 DLE STX A DLE DLE C B DLE ETX 其中 DLE STX 是帧首标记，斜体 DLE 是填充的 DLE 字符，DLE ETX 则是帧尾标记。 通过这种 DLE 字符的填充法，接收方就能保证帧边界字符的唯一性。 因为 DLE 是一个字符，发送方每次在数据部分中遇到一个 DLE 字符时，就必须插入一 个 8bit 长的 DLE。如果待传送的数据中有很多 DLE 字符，那么帧中就会包含大量的冗余 DLE。这也是带字符填充的首尾界符法的一个不足之处。 3．带位填充的首尾标志法 与字符填充技术类似，带位填充的首尾标志法也是一种填充技术，但是它一次只填充 一个比特“0”而不是一个字符“DLE”。另外，带位填充的首尾标志法用一个特殊的位模 式“01111110”作为帧的开始和结束标志，而不是分别用“DLE STX”和“DLE ETX”作 帧的首标志和帧的尾标志。 当发送方在数据部分遇到 5 个连续的“1”时，就自动在其后插入一个“0”，即所谓的 “逢五个 1 插 0”。例如，若原始数据为 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 则经过填充后就变为 0 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 0 1 0 其中三个黑体“0”为填充的位。 当接收方遇到 5 个连续的“1”之后是一个“0”时，就删除该“0”，即所谓的“逢五 个 1 删 0”。这样就保证了在帧的数据部分不会出现“01111110”位串，从而使接收方能准 确地判断出帧边界。 与上述字符填充法相比，这种位填充技术存在明显的优势。其在位模式基础上引入了 “逢五个 1 删 0”和“逢五个 1 插 0”机制，保证了帧边界标志“01111110”的唯一性。带 位填充的首尾标志法是比较常用的成帧方法，本章后面介绍的数据链路层协议 HDLC 就使 用了这种帧定界方法
第4章数据链路层 4.物理层编码违例法 物理层编码违例法就是利用物理层信息编码中未用的电信号来作为帧的边界。例如曼 彻斯特编码，在传输之前将数据位“1”编码成高-低电平对，数据位“0”编码成低高电平 对，因此可以利用高-高电平对和低-低电平对作为帧边界的特殊编码。这种方法在EEE802 局域网标准中用到。 实际上，很多数据链路层协议使用字符计数法与其他方法相结合作为其成帧的方法。 这里不再赘述。 4.3差错控制 4.3.1差错原因与类型 所谓差错是指接收端收到的数据与发送端实际发出的数据出现不一致的现象。之所以 产生差错，主要是因为在通信线路上噪声干扰的结果。根据噪声类型不同，可将差错分为 随机错和突发错。热噪声所产生的差错称为随机错，冲击噪声所产生的错误称为突发错， 电磁干扰、无线电干扰等都属于冲击噪声。 差错的严重程度由误码率来衡量，误码率P等于错误接收的码元数与所接收的码元总 数之比。显然，误码率越低，信道的传输质量越高，但是由于信道中的噪声是客观存在的， 所以不管信道质量多高，都要进行差错控制。 4.3.2差错控制的作用与机制 差错控制的主要作用是通过发现数据传输中的错误，以便采取相应的措施减少数据传 输错误。差错控制的核心是对传送的数据信息加上与其满足一定关系的冗余码，形成一个 加强的、符合一定规律的发送序列。所加入的冗余码称为校验码(Frame Check Sequence, 简称FCS)。举一个形象的例子同学们就可以理解冗余码的作用。假定有朋友托人给你捎来 一个水果篮，里面放了五只苹果和一盒巧克力。结果为你挡该水果篮的人禁不住这盒巧克 力的诱惑将其吃掉了，然后将剩下的五只苹果交给了你，而你还以为原来就只有五只苹果。 但假如你的朋友在水果蓝里同时放上了一张卡片或纸条，上面写若五只苹果和一盒巧克力 的传送信息，则你就可以发现该水果篮在捎带过程中出了问题。显然，这张卡片或纸条不 是真正要送给你的礼物，但却是保证礼物被正确送给你所必需的额外信息，即冗余信息。 校验码在顿传输中的作用就相当于该例子中的卡片或纸条。校验码按功能的不同被分为纠 错码和检错码。纠错码不仅能发现传输中的错误，还能利用纠错码中的信息自动纠正错误， 其对应的差错控制措施为自动前向纠错。汉明编码(Hamming code)为典型的纠错码，具 有很高的纠错能力。检错码只能用来发现传输中的错误，但不能自动纠正所发现的错误， 需要通过反馈重发来纠错。常见的检错码有奇偶校验码和循环冗余校验码。由于目前计算
第 4 章 数据链路层 5 4．物理层编码违例法 物理层编码违例法就是利用物理层信息编码中未用的电信号来作为帧的边界。例如曼 彻斯特编码，在传输之前将数据位“1”编码成高-低电平对，数据位“0”编码成低-高电平 对，因此可以利用高-高电平对和低-低电平对作为帧边界的特殊编码。这种方法在 IEEE802 局域网标准中用到。 实际上，很多数据链路层协议使用字符计数法与其他方法相结合作为其成帧的方法。 这里不再赘述。 4.3 差错控制 4.3.1 差错原因与类型 所谓差错是指接收端收到的数据与发送端实际发出的数据出现不一致的现象。之所以 产生差错，主要是因为在通信线路上噪声干扰的结果。根据噪声类型不同，可将差错分为 随机错和突发错。热噪声所产生的差错称为随机错，冲击噪声所产生的错误称为突发错， 电磁干扰、无线电干扰等都属于冲击噪声。 差错的严重程度由误码率来衡量，误码率 Pe 等于错误接收的码元数与所接收的码元总 数之比。显然，误码率越低，信道的传输质量越高，但是由于信道中的噪声是客观存在的， 所以不管信道质量多高，都要进行差错控制。 4.3.2 差错控制的作用与机制 差错控制的主要作用是通过发现数据传输中的错误，以便采取相应的措施减少数据传 输错误。差错控制的核心是对传送的数据信息加上与其满足一定关系的冗余码，形成一个 加强的、符合一定规律的发送序列。所加入的冗余码称为校验码(Frame Check Sequence ， 简称 FCS)。举一个形象的例子同学们就可以理解冗余码的作用。假定有朋友托人给你捎来 一个水果篮，里面放了五只苹果和一盒巧克力。结果为你捎该水果篮的人禁不住这盒巧克 力的诱惑将其吃掉了，然后将剩下的五只苹果交给了你，而你还以为原来就只有五只苹果。 但假如你的朋友在水果篮里同时放上了一张卡片或纸条，上面写着五只苹果和一盒巧克力 的传送信息，则你就可以发现该水果篮在捎带过程中出了问题。显然，这张卡片或纸条不 是真正要送给你的礼物，但却是保证礼物被正确送给你所必需的额外信息，即冗余信息。 校验码在帧传输中的作用就相当于该例子中的卡片或纸条。校验码按功能的不同被分为纠 错码和检错码。纠错码不仅能发现传输中的错误，还能利用纠错码中的信息自动纠正错误， 其对应的差错控制措施为自动前向纠错。汉明编码（Hamming code）为典型的纠错码，具 有很高的纠错能力。检错码只能用来发现传输中的错误，但不能自动纠正所发现的错误， 需要通过反馈重发来纠错。常见的检错码有奇偶校验码和循环冗余校验码。由于目前计算
6 计算机网络技术 机网络通信中大多采用检错码方案，因此下面着重介绍检错码方案。 4.3.3常见检错码 1.奇偶校验码 奇偶校验的规则是在原数据位后附加一个校验位，将其值置为“0”或“1”，使附加该 位后的整个数据码中“1”的个数成为奇数或偶数。使用奇数个“1”进行校验的方案被称 为奇校验：对应于偶数个“1”的校验方案被称为偶校验。奇偶校验有三种使用方式，即水 平奇偶校验、垂直奇偶校验和水平垂直奇偶校验。下面以奇校验为例进行介绍。 水平奇校验码是指在面向字符的数据传输中，在每个字符的7位信息码后附加一个校 验位“0”或“1”，使整个字符中二进制位“1”的个数为奇数。 例如，设待传送字符的比特序列为“1100001”，则采用奇校验码后的比特序列形式为 “11000010”。接收方在收到所传送的比特序列后，通过检查序列中的“1”的个数是否仍 为奇数来判断传输是否发生了错误。若比特在传送过程中发生错误，就可能会出现“1”的 个数不为奇数的情况。图4.3()给出了发送序列“1100001”采用水平奇校验后可能会出现 的三种典型情况。显然，水平奇校验只能发现字符传输中的奇数位错，而不能发现偶数位 错。例如上述发送序列“11000010”，若接收端牧到“11001010”，则可以校验出错误，因 为有一位“0”变成了“1”：但是若收到“11011010”，则不能识别出错误：因为有两位“0” 变成了“1”。不难理解，水平偶校验也存在同样的问题 为了提高奇偶校验码的检错能力，我们引入了水平垂直奇偶校验，即由水平奇偶校验 和垂直奇偶校验综合构成。 垂直奇偶校验也称为组校验，是将所发送的若干个字符组成字符组或字符块，形式上 看相当于是一个矩阵，如图4.3b)所示，每行为一个字符，每列为所有字符对应的相同位。 在这一组字符的末尾即最后一行附加上一个校验字符，该校验字符中的第ⅰ位分别是对应组 中所有字符第ⅰ位的校验位。显然，如果单独采用垂直奇偶校验，则只能检出字符块中某 列中的1位或奇数位错。 但是，如果我们同时采用了水平奇偶校验和垂直奇偶校验，即既对每个字符作水平校 验，同时也对整个字符块作垂直校验，则奇偶校验码的检错能力可以明显提高。这种方式 的奇偶校验被称为水平垂直奇偶校验。图4.3©)给出了一个水平垂直奇偶校验的例子。但是 从总体上讲，奇偶校验方法的检错能力仍较差，虽然其实现方法简单。故这种校验一般只 用于通信质量要求较低的环境
6 计算机网络技术 机网络通信中大多采用检错码方案，因此下面着重介绍检错码方案。 4.3.3 常见检错码 1．奇偶校验码 奇偶校验的规则是在原数据位后附加一个校验位，将其值置为“0”或“1”，使附加该 位后的整个数据码中“1”的个数成为奇数或偶数。使用奇数个“1”进行校验的方案被称 为奇校验；对应于偶数个“1”的校验方案被称为偶校验。奇偶校验有三种使用方式，即水 平奇偶校验、垂直奇偶校验和水平垂直奇偶校验。下面以奇校验为例进行介绍。 水平奇校验码是指在面向字符的数据传输中，在每个字符的 7 位信息码后附加一个校 验位“0”或“1”，使整个字符中二进制位“1”的个数为奇数。 例如，设待传送字符的比特序列为“1100001”，则采用奇校验码后的比特序列形式为 “11000010”。接收方在收到所传送的比特序列后，通过检查序列中的“1”的个数是否仍 为奇数来判断传输是否发生了错误。若比特在传送过程中发生错误，就可能会出现“1”的 个数不为奇数的情况。图 4.3(a)给出了发送序列“1100001”采用水平奇校验后可能会出现 的三种典型情况。显然，水平奇校验只能发现字符传输中的奇数位错，而不能发现偶数位 错。例如上述发送序列“11000010”，若接收端收到“11001010”，则可以校验出错误，因 为有一位“0”变成了“1”；但是若收到“11011010”，则不能识别出错误；因为有两位“0” 变成了“1”。不难理解，水平偶校验也存在同样的问题。 为了提高奇偶校验码的检错能力，我们引入了水平垂直奇偶校验，即由水平奇偶校验 和垂直奇偶校验综合构成。 垂直奇偶校验也称为组校验，是将所发送的若干个字符组成字符组或字符块，形式上 看相当于是一个矩阵，如图 4.3(b)所示，每行为一个字符，每列为所有字符对应的相同位。 在这一组字符的末尾即最后一行附加上一个校验字符，该校验字符中的第 i 位分别是对应组 中所有字符第 i 位的校验位。显然，如果单独采用垂直奇偶校验，则只能检出字符块中某一 列中的 1 位或奇数位错。 但是，如果我们同时采用了水平奇偶校验和垂直奇偶校验，即既对每个字符作水平校 验，同时也对整个字符块作垂直校验，则奇偶校验码的检错能力可以明显提高。这种方式 的奇偶校验被称为水平垂直奇偶校验。图 4.3(c)给出了一个水平垂直奇偶校验的例子。但是 从总体上讲，奇偶校验方法的检错能力仍较差，虽然其实现方法简单。故这种校验一般只 用于通信质量要求较低的环境
第4章数据链路层 发送方 接收方 传输信道 11000010 ◆11000010接收的编码无差错。 11000010 →1001010数收期镀盈宽个数为锅 11000010 →101010的集男中的数为奇整 出闽载界着储。因此不能检 (a)水平奇校验示例 前7行为对应字母的ASCI码，最后 字母一行是垂直奇校验编码（粗体） a 1100001 b 1100010 c 1100011 d 1100100 e 1100101 1100110 g 1100111 校验位 0011111 (b)垂直奇校验 最后一行是垂直奇校验编码，最后 字母 列是水平奇校验编码（均为粗体） a 11000010 b 11000100 c 11000111 d 11001000 e 11001011 11001101 g 11001110 校验位 00111110 (C)水平垂直奇校验 图4.3奇偶校验码的示例
第 4 章 数据链路层 7 发送方 11000010 11000010 传输信道 接收的编码无差错。 11000010 11001010 接收的编码中1的个数为偶 数，所以出现差错。 11000010 11011010 接收的编码中1的个数为奇数， 所以判断为“无差错”，但实 际上出现差错。因此不能检测 出偶数个错。 接收方 (a) 水平奇校验示例 字母 前 7 行为对应字母的 ASCII 码，最后 一行是垂直奇校验编码（粗体） a b c d e f g 校验位 1 1 0 0 0 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 1 1 1 (b) 垂直奇校验 字母 最后一行是垂直奇校验编码，最后 一列是水平奇校验编码（均为粗体） a b c d e f g 校验位 1 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 1 1 1 1 0 0 1 0 0 0 1 1 0 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 (c) 水平垂直奇校验 图 4.3 奇偶校验码的示例
8 计算机网络技术 2.循环冗余校验码CRC 循环冗余校验码(Cycle Redundancy Check,简称CRC)是一种被广泛采用的多项式编 码。CC码由两部分组成，前一部分是k+1个比特的待发送信息，后一部分是r个比特的 冗余码。由于前一部分是实际要传送的内容，因此是固定不变的，CC码的产生关键在于 后一部分冗余码的计算。 计算中主要用到两个多项式：f(x)和G(x)。其中，f(x)是一个k阶多项式，其系数是 待发送的k+1个比特序列：G(x)是一个r阶的生成多项式，由发收双方预先约定。 例如，设实际要发送的信息序列是1010001101（十个比特，k=9),则以它们作为f(x) 的系数，得到对应的9阶多项式为 f(x)=1·x40x+1·x2+0x+0x+0x+1x+1·x40x1 =x+x2+x3+x2+1。 再假设发收双方预先约定了一个5阶(5)的生成多项式 G(x)=x+x+x2+1=1·x+1·x+0·x+1·x2+0·x+1,则其系数序列为110101。 CRC码的产生方法如下： a)生成r个比特的冗余码 用模2除法进行xf(x)/G(x)运算，得余式R(x),其系数即是冗余码。 例如，x5f(x)=x+x+x+x'+x5,对应的二进制序列为101000110100000，也就是f(x) 信息序列向左移动r=5位，低位补0。 x5f(x)/G(x)=(101000110100000)/(110101),得余数为01110，也就是冗余码， 对应的余式R(x)=0·x+x+x2+x+0·x°（注意：若G(x)为r阶，则R(x)对应的比特序列长 度为r)。 注意，模2除法在做减法时不借位，相当于在进行异或运算。上述多项式的除法过程 如下： 1101010110 110101)101000110100000 110101 0111011 110101 00111010 110101 00111110 110101 00101100 110101 0110010 110101 01110余数，即校验序列(=5位，r也是Gx) 的阶)
8 计算机网络技术 2. 循环冗余校验码 CRC 循环冗余校验码（Cycle Redundancy Check，简称 CRC）是一种被广泛采用的多项式编 码。CRC 码由两部分组成，前一部分是 k+1 个比特的待发送信息，后一部分是 r 个比特的 冗余码。由于前一部分是实际要传送的内容，因此是固定不变的，CRC 码的产生关键在于 后一部分冗余码的计算。 计算中主要用到两个多项式：f(x)和 G(x)。其中，f(x)是一个 k 阶多项式，其系数是 待发送的 k+1 个比特序列；G(x)是一个 r 阶的生成多项式，由发收双方预先约定。 例如，设实际要发送的信息序列是 1010001101（十个比特，k=9），则以它们作为 f(x) 的系数，得到对应的 9 阶多项式为 f(x)=1·x 9 +0·x 8 +1·x 7 +0·x 6 +0·x 5 +0·x 4 +1·x 3 +1·x 2 +0·x+1 =x9 + x7 + x3 + x2 +1。 再假设发收双方预先约定了一个 5 阶 （ r=5 ）的生成多项式 G(x)=x5 +x4 +x2 +1=1·x 5 +1·x 4 +0·x 3 +1·x 2 +0·x+1,则其系数序列为 110101。 CRC 码的产生方法如下： a) 生成 r 个比特的冗余码 用模 2 除法进行 x r f(x)/G(x)运算,得余式 R(x)，其系数即是冗余码。 例如，x 5 f(x)=x14+x12+x8 +x7 +x5 ，对应的二进制序列为 101000110100000，也就是 f(x) 信息序列向左移动 r=5 位，低位补 0。 x 5 f(x)/ G(x)= （101000110100000）/（110101），得余数为 01110，也就是冗余码， 对应的余式 R(x)=0﹒x 4 +x3 +x2 +x+0﹒x 0 (注意：若 G(x)为 r 阶，则 R(x)对应的比特序列长 度为 r)。 注意，模 2 除法在做减法时不借位，相当于在进行异或运算。上述多项式的除法过程 如下： 1 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 ）1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 0 1 1 1 1 0 1 0 1 0 0 1 1 1 0 1 0 1 1 0 1 0 1 0 0 1 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 余数，即校验序列（r=5 位，r 也是 G(x) 的阶）
第4章数据链路层 9 b)得到带CRC校验的发送序列 用模2减法进行xr(x)-R(x)运算得到带CRC校验的发送序列，即 xf(x)-R(x)=101000110101110。从形式上看，也就是简单地在原信息序列后面附加上冗余 码。 在接收方，用同样的生成多项式G(x)除所收到的序列。若余数为O,则表示传输无差 错，否则说明传输过程出现差错。例如，若收到的序列是101000110101110，则用它除以同 样的生成多项式G(x)=x+x+x+1(即110101)。因为所得余数为0，所以收到的序列无差 销。 CRC校验方法是由多个数学公式、定理和推论得出的，尤其是CRC中的生成多项式对于 CC的检错能力会产生很大的影响。生成多项式G(x)的结构及检错效果是在经过严格的 数学分析和实验后才确定的，有其国际标准。常见的标准生成多项式有： CRC-12.G(x)=x2+x1+x3+x2+1 CRC-16:G(x)=x+x+x2+1 CRC-32:G(x)=x+x26+x8+x2+x6+x2+x1+x0+x8+x7+x3+x1+x2+x+1 理论证明，CRC能够检验出下列差错： ●全部的奇数个错： ●全部的二位错： ●全部长度小于或等于r位的突发错。其中，r是冗余码的长度 可以看出，只要选择足够的冗余位，就可以使得漏检率减少到任意小的程度。由于CC 码的检错能力强，且容易实现，因此是目前应用最广泛的检错码编码方法之一。CC码的生 成和校验过程可以用软件或硬件方法来实现，如可以用移位寄存器和半加法器方便地实现。 4.3.4反馈重发机制 由于检错码本身不提供自动的错误纠正能力，所以需要提供一种与之相配套的错误纠 正机制，即反馈重发。通常当接收方检出错误的帧时，首先将该帧丢弃，然后给发送方反 馈信息请求发送方重发相应的帧，反馈重发又被称为自动请求重传ARQ(Automatic Repeat request)。反馈重发有两种常见的实现方法，即停止等待方式和连续ARQ方式 在停止等待方式（简称停-等方式）中，发送端在发出一帧之后必须停下来等待接收端 的确认帧，若确认(Acknowledgement)帧提示正确收到，则发送方继续发送下一个帧。否则 发送方就重发那个帧。停-等协议虽然实现简单，但这种发送一帧等待一个确认的方式使得 通信效率很低。为此，人们提出了连续ARQ协议。 连续ARQ协议的特点是发送端在发送一个帧后，不是停下来等待确认帧的到来，而是 可以连续再发送N个帧(N的大小取决于发送方的发送能力和接收端的接收能力)。对于连 续ARQ方式，必须要为帧编上序列号以作为帧的标识。 在连续发送的多个帧中，可能会有一个或多个顿出现传输差错。针对这种情况，连续 ARQ分别采用了两种不同的处理方式，即拉回(back to n)方式和选择重传(selective)方式。在 拉回方式中，假定发送方连续发送了顿，而接收方在对收到的数据帧进行校验后发现第 n帧出错(n≤m),则接收方给发送方发送出错信息并要求发送方重发第n帧及第n帧以后
第 4 章 数据链路层 9 b) 得到带 CRC 校验的发送序列 用 模 2 减法进行 x 5 f(x)-R(x) 运算得到带 CRC 校验的发送序列，即 x 5 f(x)-R(x)=101000110101110。从形式上看，也就是简单地在原信息序列后面附加上冗余 码。 在接收方，用同样的生成多项式 G(x)除所收到的序列。若余数为 0，则表示传输无差 错，否则说明传输过程出现差错。例如，若收到的序列是 101000110101110，则用它除以同 样的生成多项式 G(x)= x5 + x4 +x2 +1（即 110101）。因为所得余数为 0，所以收到的序列无差 错。 CRC 校验方法是由多个数学公式、定理和推论得出的，尤其是 CRC 中的生成多项式对于 CRC 的检错能力会产生很大的影响。生成多项式 G（x）的结构及检错效果是在经过严格的 数学分析和实验后才确定的，有其国际标准。常见的标准生成多项式有： CRC-12：G（x）=x12+x11+x3 +x2 +1 CRC-16：G（x）=x16+x15+x2 +1 CRC-32：G（x）=x32+x26+x23+x22+x16+x12+x11+x10+x8 +x7 +x5 +x4 +x2 +x+1 理论证明，CRC 能够检验出下列差错： ●全部的奇数个错； ●全部的二位错； ●全部长度小于或等于 r 位的突发错。其中，r 是冗余码的长度。 可以看出，只要选择足够的冗余位，就可以使得漏检率减少到任意小的程度。由于 CRC 码的检错能力强，且容易实现，因此是目前应用最广泛的检错码编码方法之一。CRC 码的生 成和校验过程可以用软件或硬件方法来实现，如可以用移位寄存器和半加法器方便地实现。 4.3.4 反馈重发机制 由于检错码本身不提供自动的错误纠正能力，所以需要提供一种与之相配套的错误纠 正机制，即反馈重发。通常当接收方检出错误的帧时，首先将该帧丢弃，然后给发送方反 馈信息请求发送方重发相应的帧。反馈重发又被称为自动请求重传 ARQ（Automatic Repeat request）。反馈重发有两种常见的实现方法，即停止等待方式和连续 ARQ 方式。 在停止等待方式（简称停-等方式）中，发送端在发出一帧之后必须停下来等待接收端 的确认帧，若确认(Acknowledgement)帧提示正确收到，则发送方继续发送下一个帧。否则， 发送方就重发那个帧。停-等协议虽然实现简单，但这种发送一帧等待一个确认的方式使得 通信效率很低。为此，人们提出了连续 ARQ 协议。 连续 ARQ 协议的特点是发送端在发送一个帧后，不是停下来等待确认帧的到来，而是 可以连续再发送 N 个帧（N 的大小取决于发送方的发送能力和接收端的接收能力）。对于连 续 ARQ 方式，必须要为帧编上序列号以作为帧的标识。 在连续发送的多个帧中，可能会有一个或多个帧出现传输差错。针对这种情况，连续 ARQ 分别采用了两种不同的处理方式，即拉回(back to n)方式和选择重传(selective)方式。在 拉回方式中，假定发送方连续发送了 m 帧，而接收方在对收到的数据帧进行校验后发现第 n 帧出错（n≤m），则接收方给发送方发送出错信息并要求发送方重发第 n 帧及第 n 帧以后
10 计算机网络技术 的所有帧。换言之，一旦接收方发现第n帧出错，则丢弃第n帧及第n帧以后的所有帧。 显然这种方式对信道带宽有很大的需求。而在选择重传方式中，假定发送方连续发送了m 帧，而接收方在对收到的数据帧进行校验后发现第n帧出错(n≤m),则接收方给发送方 出错信息并只要求发送方重发第n帧。换言之，一旦接收方发现第n帧出错，则丢弃第n 顿，但缓存第黄以后的所有正确顾。也就是说，这种方式椿要在接收方提供足够大小的 存储缓冲来暂时保存那些己经被正确接收的帧。 细心的读者会发现，在上面的讨论中并没有考虑到顺在传输喻途中手失的情况。丢失有 两种可能， “是发送端所发送的数据帧在传输过程中被丢失，二是接收端发送给发送方的 确认帧被丢失。因此，要在发送端设置一个计时器，当计时器的值达到一定值时确认帧还 未到达，则发送端就认为它所发送的数据帧己已经丢失，将重发此数据帧，这种机制被称为 铝时重发。旧是，简单的铝时重发会带来蜻被重复接收的问颗。例如若数据航已经被接收 端正确接收，而接收端反馈的确认帧却丢失了，从而发送端通过超时重发机制又重新发送 了相同的帧。解决帧重复接收的一个简单方法就是采用帧编号，接收端一旦收到两个序列 号相同的帧，就可以判断出是重复帧，从而丢弃多余的顿。 4.4流量控制 4.4.1流量控制的作用 由于系统性能的不同，如硬件能力（包括CPU,存储器等）和软件功能的差异，会导 致发送方与接收方处理数据的速度有所不同。若一个发送能力较强的发送方给一个接收能 力相对较弱的接收方发送数据，则接收方会因无能力处理所有收到的顿而不得不手弃一些 帧。如果发送方持续高速地发送，则接收方最终还会被“淹没”。也就是说，在数据链路层 只有差错控制机制还是不够的，其不能解决因发送方和接收方辣率不匹配所告成的咖手失」 为此，在数据链路层引入了流量控制机制。流量控制的作用就是使发送方所发出的数据流 量不要超过接收方所能接收的速率。流量控制的关键是需要有一种信息反馈机制，使发送 方能了解接收方是否具备足够的接收及处理能力。存在各种不同的流量控制机制。如上面 所提到的简单停等协议就可以实现流量控制功能，但其实现效率太低。下面所介绍的滑动 窗口协议则可以将确认机制与流量控制机制巧妙地结合在一起。 4.4.2滑动窗口协议 滑动窗口协议是指一种采用滑动窗口机制进行流量控制的方法。通过限制己经发送但 还未得到确认的数据帧的数量，滑动窗口协议可以调整发送方的发送速度。许多使用位填 充技术的数据链路层协议（如4.6中将要介绍的DLC协议）都使用滑动窗口协议进行流量 控制。下面简单介绍滑动窗口协议的工作机制。 在滑动窗口协议中，每一个要发送的顿都要被赋予一个序列号，其范围从0到某一个
10 计算机网络技术 的所有帧。换言之，一旦接收方发现第 n 帧出错，则丢弃第 n 帧及第 n 帧以后的所有帧。 显然这种方式对信道带宽有很大的需求。而在选择重传方式中，假定发送方连续发送了 m 帧，而接收方在对收到的数据帧进行校验后发现第 n 帧出错（n≤m） ，则接收方给发送方 出错信息并只要求发送方重发第 n 帧。换言之，一旦接收方发现第 n 帧出错，则丢弃第 n 帧，但缓存第 n 帧以后的所有正确帧。也就是说，这种方式需要在接收方提供足够大小的 存储缓冲来暂时保存那些已经被正确接收的帧。 细心的读者会发现，在上面的讨论中并没有考虑到帧在传输途中丢失的情况。丢失有 两种可能，一是发送端所发送的数据帧在传输过程中被丢失，二是接收端发送给发送方的 确认帧被丢失。因此，要在发送端设置一个计时器，当计时器的值达到一定值时确认帧还 未到达，则发送端就认为它所发送的数据帧已经丢失，将重发此数据帧，这种机制被称为 超时重发。但是，简单的超时重发会带来帧被重复接收的问题。例如若数据帧已经被接收 端正确接收，而接收端反馈的确认帧却丢失了，从而发送端通过超时重发机制又重新发送 了相同的帧。解决帧重复接收的一个简单方法就是采用帧编号，接收端一旦收到两个序列 号相同的帧，就可以判断出是重复帧，从而丢弃多余的帧。 4.4 流量控制 4.4.1 流量控制的作用 由于系统性能的不同，如硬件能力（包括 CPU，存储器等）和软件功能的差异，会导 致发送方与接收方处理数据的速度有所不同。若一个发送能力较强的发送方给一个接收能 力相对较弱的接收方发送数据，则接收方会因无能力处理所有收到的帧而不得不丢弃一些 帧。如果发送方持续高速地发送，则接收方最终还会被“淹没”。也就是说，在数据链路层 只有差错控制机制还是不够的，其不能解决因发送方和接收方速率不匹配所造成的帧丢失。 为此，在数据链路层引入了流量控制机制。流量控制的作用就是使发送方所发出的数据流 量不要超过接收方所能接收的速率。流量控制的关键是需要有一种信息反馈机制，使发送 方能了解接收方是否具备足够的接收及处理能力。存在各种不同的流量控制机制。如上面 所提到的简单停等协议就可以实现流量控制功能，但其实现效率太低。下面所介绍的滑动 窗口协议则可以将确认机制与流量控制机制巧妙地结合在一起。 4.4.2 滑动窗口协议 滑动窗口协议是指一种采用滑动窗口机制进行流量控制的方法。通过限制已经发送但 还未得到确认的数据帧的数量，滑动窗口协议可以调整发送方的发送速度。许多使用位填 充技术的数据链路层协议（如 4.6 中将要介绍的 HDLC 协议）都使用滑动窗口协议进行流量 控制。下面简单介绍滑动窗口协议的工作机制。 在滑动窗口协议中，每一个要发送的帧都要被赋予一个序列号，其范围从 0 到某一个