计算机网络技术 第4章 数据链路层.pdf

66计算机网络技术第4章数据链路层上一章我们已经学习了物理层的有关知识，本章我们将介绍数据链路层的相关知识，包括数据链路层的功能以及实现这些功能的相应机制。本章建议学时数为6-8学时，本章 的学习导航参见表4.1o表4.1第4章学习导航驱动问题涉及的知识点学习要求为什么在物理层之上要有数据链路层？数据链路层的必要性 数据链路层需要解决的主要问题理解理解相邻结点的含义是什么？相邻结点的概念了解数据链路层的协议数据单元“帧”有什么作 用，它通常包括哪几部分？帧的作用及一般格式 HDLC帧的格式了解了解为什么要进行“成帧”和“拆帧”？如何区 分不同的帧？成帧与拆帧 帧的定界方法了解了解数据链路层如何识别不同的结点？物理寻址理解如何得知帧”在传输过程中出错了？校验码的概念 常见检错码理解 了解为什么要进行差错控制？有哪些常用的机 制？差错控制的作用 反馈重发机制理解理解为什么要进行流量控制？如何实现？流量控制的作用 滑动窗口协议理解了解数据链路层有相应的组件吗？网卡及其作用 网卡地址及其组成理解理解数据链路层有哪些网络互连设备？网桥及其工作原理 交换机及其与网桥的比较理解 理解4.1 数据链路层概述4.1.1 为什么需要数据链路层“链路”和“数据链路”是两个不同的概念。“链路”是指一条无源的点到点物理线路,第4章数据链路层67中间没有任何其他的交换结点。网络上两台计算机在通信时，所传送的数据往往要经过许 多中间交换结点，因而一条从源结点到目标结点的通路往往是由许多链路串接而成的，也 就是说，一条链路往往只是一条通路的一部分。“数据链路”则是一条物理通路加上必要的 数据传输规程或协议后所形成的逻辑连接。这种规程或协议控制着数据在链路上的传输。至少有两个理由可用来说明数据链路层存在的必要性。首先是数据传输过程中的损坏 与丢失问题。尽管物理层采取了一些必要的措施来减少信号传输过程中的噪声，但是数据 在物理传输过程中仍然可能被损坏或丢失。由于物理层只关心原始比特流的传送，不考虑 也不可能考虑所传输信号的意义和信息的结构，所以物理层不可能识别或判断数据在传输 过程中是否出现了损坏或丢失，从而也谈不上采取相应的机制或方法进行补救。其次是收 发双方的接收和发送速率不匹配引发的数据丢失问题。当数据发送方的发送能力大于接收 方的数据接收能力时一，接收方会因为来不及处理而产生数据溢出并导致数据丢失。然而，物理层并不考虑当发送站点的发送速度过快而接收站点接收的速度过慢时，应采取何种策 略来控制发送站点的发送速度，以避免接收站点来不及处理而丢失数据。可见只有物理层 的功能是不够的，位于物理层之上的数据链路层就是为了克服物理层的这些不足而建立的。数据链路层旨在实现网络上两个相邻节点之间的无差错传输。它利用了物理层提供的 原始比特流传输服务，检测并校正物理层的传输差错，控制数据的传输流量，使在相邻节 点之间构成一条无差错的链路，从而向网络层提供可靠的数据传输服务。4.1.2 相邻节点的概念那么何为相邻节点呢？所谓相邻节点是指那些位于同一物理网段中的节点。因此，不 仅图4.1(a)所示的点到点(point to point)网络环境中的两个节点属于相邻节点，图4.1(b)中的 那些由同一物理线路连接的共享介质环境中的节点属于相邻节点，图4.1(c)中的那些位于不 同物理线路上，但由第一层网络设备(中继器或集线器)互连的节点也属于相邻节点。相 邻节点的最主要特征是节点之间的数据通信不需要经过其他交换设备的转发。(a)点到点的连接(b)共享介质环境中的节点(c)第一层网络设备互连的网络图4.1相邻节点的示例(图已修改)4.1.3数据链路层需要解决的主要问题为实现相邻节点之间的可靠传输，数据链路层必须解决下面的一系列问题：物理寻址。如何提供有效的物理编址与寻址功能，以能够在众多的相邻结点之间确 定一个接收目标，从而保证每一帧都能送到目的结点，同样也要保证接收方知道所收的帧 来自何处。数据链路的建立、维持和释放。如何为相邻结点之间的可靠数据传输提供必要的数 68计算机网络技术据链路建立、维持和释放机制。数据流的定界。如何提供一种机制使得接收方能识别数据流的开始与结束。差错控制。如何提供相应的差错检测与控制机制使得有差错的物理链路对网络层表 现为一条无差错的数据链路。流量控制。如何提供流量控制机制以保证源和目标结点之间不会因发送和接收速率 不匹配而引起数据丢失。也就是当接收方来不及接收或处理到来的数据时，必须有相应的 机制来通知发送方降低发送速率。帧的构造。如何将那些与实现相邻节点可靠传输相关的机制，有机地统一在数据链 路层协议中，以数据链路层协议数据单元“帧”的形式来提供与实现。帧的同步。引入帧后，如何确保接收方能够从收到的比特流中准确地区分出一个帧 的开始和结束。帧类型的区分。帧通常有数据帧与控制帧之分，如何提供相应的措施来区分不同的 帧类型，以便接收方能做出正确的处理。下面我们分儿个小节来介绍数据链路层解决这些问题的一些相关机制。4.2帧与成帧为了实现上述诸如差错控制、物理寻址和流量控制等一系列功能，数据链路层必须要 使自己所看到的数据是有意义的，其中除了要传送的用户数据外，还要提供关于寻址、差 错控制和流量控制所必需的信息，而不再是物理层所谓的原始比特流。为此，数据链路层 采用了被称为帧(frame)的协议数据单元作为数据链路层的数据传送逻辑单元。不同的数据 链路层协议的核心任务就是根据它所要实现的数据链路层功能来规定帧的格式。4.2.1 帧的基本格式及其作用尽管不同的数据链路层协议给出的帧格式存在一定的差异，但它们的基本格式还是大 同小异的。帧的基本格式包括了与帧结构相关的语法与语义，图4.2给出了帧的基本格式。组成帧的那些具有特定意义的部分被称为域或字段(field),其中有关字段的说明如下：帧开始：用以指示一个帧的开始。地址：用于设备或机器的物理寻址，使得能够在多个相邻结点之间确定一个接收 目标。帧的长度/类型/控制：这个字段在不同的数据链路层协议中可以有不同的规定。或 给出帧的长度信息，或给出帧的类型信息，或表明该帧为控制帧。长度通常以字 节为单位；帧的类型主要包括提供数据传输的数据帧和提供链路控制与传输管理 功能的控制帧。数据：承载的来自高层(网络层)的数据分组(packet)。F CS：表示帧检验序列(F rame Check Sequence),该字段提供与差错检测有关的信 息。第4章数据链路层69 帧结束：用以指示一个帧的结束。该字段与帧开始字段一起提供了数据流的定界。使得接收方可以正确识别数据流的开始与结束。通常，“数据”字段之前的那些字段被统称为帧头(head)部分，而“数据”字段之后的 所有字段被称为帧尾(trailer)部分。图4.2帧的基本格式帧开始地址长度/类型/控制数据F CS帧结束从图4.2中帧的基本结构中可以看出，帧浓缩了与数据链路层功能实现相关的各种机 制，如寻址、差错控制、数据流定界等。可以说数据链路层协议将其要实现的数据链路层 功能集中体现在其所规定的帧格式中。引入帧机制不仅可以实现相邻节点之间的可靠传输,还有助于提高数据传输的效率。例如，若发现接收到的某一个(或儿个)比特出错时，可 以只对这些出错比特所对应的帧进行特殊处理(如请求重发等)，而不需要对其他未出错的 帧进行这种处理；如果发现某一帧被丢失，也只要请求发送方重传所丢失的帧，从而大大 提高了数据处理和传输的效率。4.2.2 成帧与拆帧引入帧概念以后，在发送方，数据链路层必须提供将从网络层接收的分组(Packet)封 装成帧的功能，即为来自上层的分组加上必要的帧头和帧尾,通常称此过程为成帧(framing)。在成帧时，如果上层的分组大小超出下层帧的大小限制时，上层的分组还要被划分成多个 帧之后才能被发送出去。在接收方，数据链路层必须提供将所接收到的帧重新拆装成网络 层分组的功能，即去掉发送端数据链路层所加的帧头和帧尾部分，从中分离出网络层所需 的分组，这样的过程被称为拆帧。帧在发送端和接收端数据链路层之间的传输过程大致如下：发送端的数据链路层接收 到网络层的发送请求之后，便从网络层与数据链路层之间的接口处取下待发送的分组，并 封装成帧，然后经过它下面的物理层送入物理信道；这样不断地将帧送入物理传输信道就 形成了连续的比特流；接收端的数据链路层通过自己与物理层的接口，接收来自物理层的 原始比特流，并从中识别出一个一个的独立帧，确认自己是帧的正确接收者后，利用帧中 的F CS字段对每一个帧进行校验，判断是否有错误。如果有错误，就采取收发双方约定的 差错控制方法进行处理。如果没有错误，就对所接收的帧实施拆封，并将其中的数据部分 通过数据链路层与网络层之间的接口上交给网络层，从而完成了相邻节点之间的帧传输任 务。70计算机网络技术4.2.3 帧的定界引入帧后，数据链路层必须提供关于帧边界的识别功能，即所谓帧定界(frame boundary)o帧定界就是标识帧的开始与结束。有四种常见的定界方法，即字符计数法、带 字符填充的首尾界符法、带位填充的首尾标志法和物理层编码违例法。下面分别予以简单 的介绍。1.字符计数法此方法是在帧头部中使用一个字符计数字段来标明帧内字符数。接收端根据这个计数 值来确定该帧的结束位置和下一帧的开始位置。例如，发送序列“6ABCDE5U VWX8 1 2 3 4 4 5 8”表示一共有三个帧，且三个帧的长度分别为6字节、5字节和8字节。但是这种方法很容易出现定界错误。仍以刚才的发送序列为例，当计数值出现传输差 错，如接收端收到的序列为“6ABCDE7UVWX8 1 23445 8”时，则接收端会将第二 帧解释为“7UVWX8 1，从而导致因发收双方对帧大小理解的不一致而出错。2.带字符填充的首尾界符法此方法是在每一帧的开头用ASCII字符DLE STX,在帧末尾用ASCII字符DLE ETX。但是，如果在帧的数据部分也出现了 DLE STX或DLEETX,那么接收端就会错误判断帧 边界。为了不影响接收方对帧边界的正确判断，采用了填充字符DLE的方法。即如果发送 方在帧的数据部分遇到DLE,就在其前面再插入一个DLE。这样数据部分的DLE就会成对 出现。在接收方，若遇到两个连续的DLE,则认为是数据部分，并删除一个DLE。例如，待发送的数据是(注：每个连续的下划线上的内容代表一个ASCH 字符，下同)，则在数据链路层封装的帧为DLE STX A DLE DLE C B DLE ETX其中DLE STX是帧首标记，斜体DLE是填充的DLE字符，DLE ETX则是帧尾标记。通过这种DLE字符的填充法，接收方就能保证帧边界字符的唯一性。因为DLE是一个字符，发送方每次在数据部分中遇到一个DLE字符时，就必须插入一 个8bit长的DLE o如果待传送的数据中有很多DLE字符，那么帧中就会包含大量的冗余 DLE o这也是带字符填充的首尾界符法的一个不足之处。3.带位填充的首尾标志法与字符填充技术类似，带位填充的首尾标志法也是一种填充技术，但是它一次只填充 一个比特“0”而不是一个字符“DLE”。另外，带位填充的首尾标志法用一个特殊的位模 式式1111110”作为帧的开始和结束标志,而不是分别用“DLE STX”和“DLE ETX”作 帧的首标志和帧的尾标志。当发送方在数据部分遇到5个连续的“1”时一，就自动在其后插入一个“0”，即所谓的“逢五个1插0”。例如，若原始数据为第4章数据链路层71011100111111111111111010则经过填充后就变为011100111110111110111110010其中三个黑体“0”为填充的位。当接收方遇到5个连续的“1”之后是一个“0”时,，就删除该“0”，即所谓的“逢五 个1删0”。这样就保证了在帧的数据部分不会出现“01111110”位串，从而使接收方能准 确地判断出帧边界。与上述字符填充法相比，这种位填充技术存在明显的优势。其在位模式基础上引入了“逢五个1删0”和“逢五个1插0”机制，保证了帧边界标志“01111110”的唯一性。带 位填充的首尾标志法是比较常用的成帧方法，本章后面介绍的数据链路层协议HDLC就使 用了这种帧定界方法。4.物理层编码违例法物理层编码违例法就是利用物理层信息编码中未用的电信号来作为帧的边界。例如曼 彻斯特编码，在传输之前将数据位“1”编码成高-低电平对，数据位“0”编码成低-高电平 对，因此可以利用高-高电平对和低-低电平对作为帧边界的特殊编码。这种方法在IEEE802.5 局域网标准中用到。实际上，很多数据链路层协议使用字符计数法与其他方法相结合作为其成帧的方法。这里不再赘述。4.3差错控制4.3.1 差错原因与类型所谓差错是指接收端收到的数据与发送端实际发出的数据出现不一致的现象。之所以 产生差错，主要是因为在通信线路上噪声干扰的结果。根据噪声类型不同，可将差错分为 随机错和突发错。热噪声所产生的差错称为随机错，热噪声由线路上的电子随机热运动产 生的；冲击噪声所产生的错误称为突发错，电磁干扰、无线电干扰等都属于冲击噪声。差错的严重程度由误码率Pe来衡量。在上一章中，我们已经介绍了不同传输介质的误码 率，并指出光纤信道的误码率是最低的。显然，误码率越低，信道的传输质量越高，但是 由于信道中的噪声是客观存在的，所以不管信道质量多高，误码率都不可能是零。因此，无论通过哪种类型传输介质或信道进行数据传输，差错控制都是不可少的。4.3.2 差错控制的作用与机制差错控制的主要作用是通过发现数据传输中的错误，以便采取相应的措施减少数据传 72计算机网络技术输错误。差错控制的核心是对传送的数据信息加上与其满足一定关系的冗余码，形成一个 加强的、符合一定规律的发送序列。所加入的冗余码被称为校验码或帧校验序列(F rame Check Sequence,简称F CS)。关于F CS在帧中的一般位置参见图4.2。现在举一个形象的 例子以帮助同学们理解冗余码的作用。假定有朋友托张三给你捎来一个水果篮，里面放了 五只苹果和一盒巧克力，为你捎该水果篮的张三在途中禁不住这盒巧克力的诱惑将它吃掉 了，然后将剩下的五只苹果交给了你，你没有任何察觉地将这五只苹果收了下来，因为你 还以为本来就只有五.只苹果呢。但是，假如你的朋友在水果篮里同时放上了一张卡片或纸 条，上面写着赠送五只苹果和一盒巧克力的信息，那么你就可以发现该水果篮在捎带过程 中是否出了问题。显然，这张卡片或纸条不是真正要送给你的礼物，但它却是保证礼物被 正确送给你所必需的额外信息，或称冗余信息。校验码在帧传输中的作用就相当于该例子 中的卡片或纸条。校验码按校验错误能力的不同被分为纠错码和检错码。纠错码不仅能发 现传输中的错误，还能利用纠错码中的信息自动纠正错误，其对应的差错控制措施为自动 前向纠错。汉明编码(Hamming code)是一种典型的纠错码，具有很高的纠错能力。检错 码只能用来发现传输中的错误，但不能自动纠正所发现的错误，需要通过反馈重发来纠错。常见的检错码有奇偶校验码和循环冗余校验码。由于目前计算机网络通信中大多采用检错 码方案，因此下面着重介绍检错码方案，然后简单介绍汉明码。4.3.3 常见检错码1.奇偶校验码奇偶校验的规则是在原数据位后附加一个校验位，将其值置为“o”或“1”，使附加该 位后的整个数据码中“1”的个数成为奇数或偶数。使用奇数个“1”进行校验的方案被称 为奇校验；对应于偶数个“1”的校验方案被称为偶校验。奇偶校验有三种使用方式，即水 平奇偶校验、垂直奇偶校验和水平垂直奇偶校验。下面以奇校验为例进行介绍。水平奇校验码是指在面向字符的数据传输中，在每个字符的7位信息码后附加一个校 验位“0”或“1”，使整个字符中二进制位“1”的个数为奇数。例如，设待传送字符的比特序列为iioooor;则采用奇校验码后的比特序列形式为“11000010”。接收方在收到所传送的比特序列后，通过检查序列中的“1”的个数是否仍 为奇数来判断传输是否发生了错误。若比特在传送过程中发生错误，就可能会出现“1”的 个数不为奇数的情况。图4.3(a)给出了发送序列“1100001”采用水平奇校验后可能会出现 的三种典型情况。显然，水平奇校验只能发现字符传输中的奇数位错，而不能发现偶数位 错。例如上述发送序列“nooooio”,若接收端收到“11001010”,则可以校验出错误，因 为有一位“0”变成了“1”；但是若收到“11011010”，则不能识别出错误；因为有两位“0”变成了“1”。不难理解，水平偶校验也存在同样的问题。为了提高奇偶校验码的检错能力，我们引入了水平垂直奇偶校验，即由水平奇偶校验 和垂直奇偶校验综合构成。垂直奇偶校验也称为组校验，是将所发送的若干个字符组成字符组或字符块，形式上第4章数据链路层73看相当于是一个矩阵，如图4.3(b)所示，每行为一个字符，每列为所有字符对应的相同位。在这一组字符的末尾即最后一行附加上一个校验字符，该校验字符中的第i位分别是对应组 中所有字符第i位的校验位。显然，如果单独采用垂直奇偶校验，则只能检出字符块中某一 列中的1位或奇数位错。但是，如果我们同时采用了水平奇偶校验和垂直奇偶校验，即既对每个字符作水平校 验，同时也对整个字符块作垂直校验，则奇偶校验码的检错能力可以明显提高。这种方式 的奇偶校验被称为水平垂直奇偶校验。图4.3(c)给出了一个水平垂直奇偶校验的例子。但是 从总体上讲，奇偶校验方法的检错能力仍较差，虽然其实现方法简单。故这种校验一般只 用于通信质量要求较低的环境。发送方传输信道11000010-A11000010-A11000010-接收方110000101100101011011010接收的编码无差错。接收的编码中1的个数为偶 数，所以出现差错。接收的编码中1的个数为奇数，所以判断为“无差错”，但实 际上出现差错。因此不能检测 出偶数个错。(a)水平奇校验示例字母前7行为对应字母的ASCII码，最后 一行是垂直奇校验编码(粗体)a1100001b1100010c1100011d1100100e1100101f1100110g1100111校验位0011111(b)垂直奇校验字母最后行是垂直奇校验编码，最后 一列是水平奇校验编码(均为粗体)a11000010b1 1 000 1 00c11000111d11001000e1100101174计算机网络技术(c)水平垂直奇校验f11001101g11001110校验位00111110图4.3奇偶校验码的示例2.循环冗余校验码CRC循环冗余校验码(Cycle Redundancy Check,简称CRC)是一种被广泛采用的多项式编 码。CRC码由两部分组成，前一部分是k+1个比特的待发送信息，后一部分是r个比特的 冗余码。由于前一部分是实际要传送的内容，因此是固定不变的，CRC码的产生关键在于 后一部分冗余码的计算。冗余码的计算中要用到两个多项式：f(x)和G(x)。其中，f(x)是 一个k阶多项式，其系数是待发送的k+1个比特序列；G(x)是一个r阶的生成多项式，由 发收双方预先约定。CRC校验基本工作原理如图4.4所示。下面举例说明。假设实际要发送的信息序列是 1010001101,收发双方预先约定了一个5阶(r=5)的生成多项式G(x)=x5+x+x2+l,那么可 参照下面步骤来计算相应的CRC码：1)发送的信息序列1010001101(十个比特),以它们作为f(x)的系数,得到对应的 f(x)为9阶多项式：f(x)=l x9+0 x8+l x7+0 x6+0 x5+0 x4+l x3+l x2+0 x+12)获得f(x)的表达式x5 f(x)=x%x，x8+x7+x5,该表达式对应的二进制序列为 101000110100000,相当于信息序列向左移动r(=5)位，低位补0。3)计算f(x)/G(x),得至卜个比特的冗余序列：x5 f(x)/G(x)=(101000110100000)/(110101),得余数为 OHIO,也就是冗余序列。该冗余序列对应的余式R(x)=0.x4+x3+x2+x+0.x0(注意：若G(x)为i阶，则R(x)对应的比特 序列长度为r)。另外，由于模2除法在做减法时不借位，故相当于在进行异或运算。上述多项式的除 法过程如下：110 10 10 1101 1 0 1 0 1)1010001101 0000011010101110111 10 10 10011101011010100111110110101第4章数据链路层750010110011010101100101101010 1110余数，即校验序列(r=5位，I也是G(x)的阶)。4)得到带CRC校验的发送序列：即将f(x)x+R(x)作为带CRC校验的发送序列。实际运算时，也可用模2减法进行 f(x)x-R(x)运算来得到。如x,f(x)-R(x)=101000110101H0。从形式上看，也就是简单 地在原信息序列后面附加上冗余码。5)在接收端，对收到的序列进行校验：对接收数据多项式f(x)用同样的生成多项式G(x)进行同样的求余运算，即,=Q(x)+幺旦 若R/(x)=R(x),则表示数据传输无误，否则说明数据传输过程出 G(x)G(x)现错误。例如，若收到的序列是1010001101011收,则用它除以同样的生成多项式G(x)=x5+x4+x2+l(即110101)后，因所得余数为0,所以收到的序列无差错。76计算机网络技术发送方接收方发送数据多项式f(x)生成多项式G(x)/(%)/3G(%)G(%)实际发送f(x)x 1+R(x),即发送-A 接收的数据f(x)生成多项式G(x)4需若W(%)=砥%)，则接收正确若W(%)wR(%),则接收出错数据字段冗余字段发送图4.4 CRC校验基本原理CRC校验方法是由多个数学公式、定理和推论得出的。CRC中的生成多项式对于CRC的 检错能力会产生很大的影响。生成多项式G(x)的结构及检错效果是在经过严格的数学分 析和实验后才确定的，有着相应的国际标准。常见的标准生成多项式有：CRC-12：G(x)=xl2+x+x3+x2+lCRC-16：G(x)=x6+x15+x2+lCRC-32：G(x)=x32+x26+x23+x22+x16+x12+x11+xl0+x8+x7+x5+x4+x2+x+lCRC校验具有很强的检错能力，理论证明，CRC能够检验出下列差错：全部的奇数个错；全部的二位错；全部长度小于或等于r位的突发错。其中，r是冗余码的长度。可以看出，只要选择足够的冗余位，就可以使得漏检率减少到任意小的程度。由于CRC 码的检错能力强，且容易实现，因此是目前应用最广泛的检错码编码方法之一。CRC码的生 成和校验过程可以用软件或硬件方法来实现，如可以用移位寄存器和半加法器方便地实现。第4章数据链路层 774.3.4反馈重发机制由于检错码本身不提供自动错误纠正的能力，所以需要提供一种与之相配套的错误纠 正机制。目前常用的是一种被称为反馈重发的机制：当接收方检出错误的帧时，首先将该 帧丢弃，然后接收方给发送方反馈信息请求对方重发相应的帧。反馈重发也被称为自动请 求重传（Automatic Repeat Request,简称ARQ）。反馈重发有两种常见的实现方法，即停 止-等待方式和连续方式。1.停止-等待方式在停止-等待方式（stop-and-wait）中，发送端在发出一帧之后必须停下来等待接收端的 对发送帧的确认（ucknowlcdgcmcnl）。若确认提示对方已经正确收到，则发送方继续发送下 一个帧；否则，发送方就重发该帧。对帧的确认有肯定和否定之分，表示正确接收的被称 为确认帧（acknowledgement,简称ACK）,表示错误接收的被称为否认帧（negative acknowledgement,简称NAK）。在理想情况下，帧在线路上不会损坏，也不会丢失。图4.5表明了发送方和接收方在正 常情况下的一次帧传送。发送方发送一个帧，接收方在正确接收后，反馈一个确认帧。好送产 网络层数据链路物理层接收方图4.5正常情况下的停止等待在这种理想的情况下，发送站点的动作为：1）将从网络层下来的分组装配成帧；2）将帧送到数据链路层的发送缓冲区；3）将发送缓冲区中的帧发送出去；4）等待对方的确认；5）收到接收站点的ACK帧，转到1）。接收站点的动作为：1）等待；2）若收到由发送站点发过来的帧，将其放入数据链路层的接收缓冲区;78计算机网络技术3)将接收缓冲区中的帧进行拆封处理，将其中的分组交给网络层；4)发送一个确认帧ACK给发送站点，表示帧已正确接收；5)转到1)。然而，任何信道都可能存在噪声。在有噪声的情况下，帧可能被损坏，也可能完全丢 失。有三种典型的帧丢失或损坏情况：一是接收方收到了被损坏的数据帧，二是发送端所 发送的数据帧在传输过程被丢失，三是接收端发送给发送方的确认帧被丢失。在第一种情 况下，接收方会发送一个否认帧，发送方在收到该否认帧后将会重传这个被损坏的帧。后 两种情况则可能造成发送方无限制地等待下去。图4.6和图4.7分别给出了后两种情况的 示意。在图4.6(a)中，由于接收方没有收到相应的帧，因此也就不会发送一个ACK。在 图4.6(b)中，尽管接收方正确收到一个帧且为此发送了一个确认帧，但是该确认帧在传输过 程中被丢失。所以，这两种情况都会造成发送方因收不到确认帧而无限等下去。解决上述无限等待的有效方法是引入超时重发机制。在发送方设置一个计时器，当发 送一个帧之后，就开始计时；如果在规定的时间内确认帧还未到达，就默认为帧在传输过 程中被丢失，于是重新启动帧的发送。分单方 网络层数据链路层数据帧接网络层数据链路层物理层物理层图4.6(a)数据帧丢失的情况特送方接收方网络层网络层数据帧数据链路数据链路物理层确认帧物理层图4.6(b)确认帧丢失的情况第4章数据链路层79但是，简单的超时重发会引发帧被重复接收的问题。例如，在图4.6(b)中，数据帧已 经被接收端正确接收，但接收端反馈的确认帧却在传输过程中丢失了，发送端因此启动了 超时重发机制，从而造成接收端收到重复的帧。解决帧重复接收问题的一个简单方法就是 对待发送的帧进行编号。接收端一旦在某段时间内收到两个序列号相同的帧，就可以判断 出是它们是重复帧，然后丢弃重复的帧。停止等待方式实现简单，但是这种发送一帧等待 一个确认的方式使得通信效率很低。为此，人们提出了连续ARQ协议。2.连续ARQ协议连续ARQ协议的特点是发送端在发送一个帧后，不是停下来等待确认帧的到来，而是 可以连续再发送多个帧，帧的个数取决于发送方的发送能力和接收端的接收能力。对于连 续ARQ方式，必须要为不同的帧编上序列号以作为帧的标识。在连续发送的多个帧中，可能会有一个或多个帧出现传输差错。针对这种情况，连续 ARQ分别采用了两种不同的处理方式，即拉回(back to n)方式和选择性重传(selective repeat)方式。图4.7(a)和图4.7(b)分别是这两种方式的示意图。在拉回方式中，假设发送方连续发送了 m帧，而接收方在对收到的数据帧进行校验后 发现第n帧出错(nWm),则接收方给发送方发送出错信息并要求发送方重发第n帧及第n 帧以后的所有帧。换言之，一旦接收方发现第n帧出错，则丢弃第n帧及第n帧以后的所 有帧。例如，图4.7(a)中2号帧出错，接收端将丢弃3、4、5和6号帧，不论它们是否 正确到达。然后，发送端再从2号帧开始按帧的序号的顺序连续发送。显然这种方式对信 道带宽有很大的需求。然而，在选择重传方式中，假定发送方连续发送了 m帧，而接收方在对收到的数据帧 进行校验后发现第n帧出错(nWm),则接收方给发送方发送出错信息并只要求发送方重发 第n帧。换言之，一旦接收方发现第n帧出错，则丢弃第n帧，但缓存第n帧以后的所有 正确的帧。例如，图4.7(b)中，接收方只请求发送方重传2号帧，而将正确到达的3、4、5和6号帧缓存下来。不过，选择性重传方式需要在接收方提供足够大小的存储缓冲来暂时 保存那些已经被正确接收的帧。图4.7(a)和(b)分别给出了拉回方式的连续ARQ与选择性重发方式的连续ARQ的例子。在该例子中，每次连续发送七帧。图中的数字表示帧的编号，实线箭头表示发送端发送的 数据帧，虚线箭头表示接收端发送的确认帧，字母E，表示收到出错帧，夕表示接收端 丢弃对应的数据帧。图4.7(a)拉回方式的连续ARQ80计算机网络技术图4.7(b)选择性重传方式的连续ARQ4.4 流量控制4.4.1 流量控制的作用由于系统性能的不同，如硬件能力(包括CPU,存储器等)和软件功能的差异，会导 致发送方与接收方处理数据的速度有所不同。若一个发送能力较强的发送方给一个接收能 力相对较弱的接收方发送数据，则接收方会因无能力处理所有收到的帧而不得不丢弃一些 帧。如果发送方持续高速地发送，则接收方最终还会被“淹没”。也就是说，在数据链路层 只有差错控制机制还是不够的，其不能解决因发送方和接收方速率不匹配所造成的帧丢失。为此，在数据链路层引入了流量控制机制。流量控制的作用就是使发送方所发出的数据流量不要超过接收方所能接收的速率。流 量控制的关键是需要有一种信息反馈机制，使发送方能了解接收方是否具备足够的接收及 处理能力。存在各种不同的流量控制机制。如上面所提到的简单停等协议就可以实现流量 控制功能，但其实现效率太低。下面所介绍的滑动窗口协议可以将流量控制机制与帧确认 机制巧妙地结合在一起。442滑动窗口协议滑动窗口协议(slide window)是指一种采用滑动窗口机制进行流量控制的方法。通过限 制已经发送但还未得到确认的数据帧数量，滑动窗口协议可以调整发送方的发送速度。许 多使用位填充技术的数据链路层协议(如4.6中将要介绍的HDLC协议)都使用滑动窗口协 议进行流量控制。下面介绍滑动窗口协议的工作机制。帧序列号在滑动窗口协议中，每一个要发送的帧都被赋予一个序列号。假如在帧字段中用以表 达序列号的字段长度为n个比特，那么帧的序号范围是从0到2n-l之间的一个数，最多有 MAX_Seq=2n个编号可供选择。例如，若在帧字段中序列号采用了三个比特位表示，即n=3,则MAX_Seq=23=8,帧编号可以从0、1、2、3、4、5、6和7中这8个数中进行选择。序列 第4章数据链路层81号是循环使用的，若当前帧的序号已达到最大编号（即211）时，则下一个待发送的帧序列 号将重新为0,此后再依次递增。也就是说，若当前帧的编号为i,则下一个帧的编号为：（i+1）mod MAX_Seq 发送窗口在发送方，要维持一个发送窗口（sending window）Q在发送窗口内所保持着的一组序 列号，对应于允许发送的帧，我们形象地称这些帧落在发送窗口内。如果发送窗口的大小 为Ws,则表明已经发送出去但仍未得到确认的帧总数不能超过Ws。以图4.8为例，Ws=4 表示已经发送出去但仍未得到确认的帧总数不能超过4。显然，在初始状态下，发送窗口内允许发送的帧数目为Ws,而每发出一个帧，允许发 送的帧数目就减1。一般情况下，发送窗口的下限对应当前已经发送出去但未被确认的最后 一帧，一旦这个帧的确认帧到达后，发送窗口的下限和上限各自加1,同时一个新的序列号 落在窗口，表明该帧允许发送。我们将之形象地称为窗口向前滑动一个位置（按顺时针方 向），新序列号的计算公式为：（当前上限值或下限值+1）mod MAX_Seq若发送窗口内已经有Ws个没有得到确认的帧，则不允许再发送新帧，需要发送的帧必 须等待接收方传来的确认帧并使窗口向前滑动，直至其序列号落入发送窗口内才能被发送。接收窗口在接收方，则要维持一个接收窗口（receiving window）o在接收窗口中也保持着一组 序列号，但其对应于允许接收的帧，只有发送序列号落在窗口内的帧才能被接收，落在窗 口之外的帧将被丢弃。若帧被正确接收，则接收窗口向前滑动一个位置，即窗口的上下限各加1（计算方法同 发送窗口），使一个新序列号落入窗口内，同时给发送方返回一个确认帧。由于发送方与接 收方的数据处理能力有所不同，接收窗口和发送窗口可以不具有相同的窗口大小，甚至两 者可以不具有相同的窗口上限与下限。在滑动窗口协议中，当发送窗口和接收窗口的大小嘉度都为1时，就变成简单的停-等 协议。图4.8给出了一个3位长度的序列号，发送与接收窗口大小均为4的滑动窗口协议的工 作实例。3位长度序列号所对应的帧编号范围为0、1、2、3、4、5、6和7。图中，双向箭 头表示滑动窗口的上下限。初始状态时，发送与接收窗口的上下限均分别对应于编号为0 与3的帧。从图4.8例子中可以看出，只有在接收窗口向前滑动时，发送窗口才有可能向前滑动。例如，在发送方发送了 0号和1号帧而未收到关于该两帧的确认之前，发送窗口仍停留在 原位，也就是说，此时发送方至多只能发送2号和3号帧，因为它们已经落在发送窗口内。只有当发送方收到关于。号和1号帧的确认之后，发送窗口才能向前滑动两格而使4号和5 号帧落到发送窗口内，继而发送方才能发送4号和5号帧，从而达到了流量控制的目的。滑动窗口协议在实现流量控制的同时，还可以实现差错控制功能。在上例中，假设在 82计算机网络技术状态3,接收方只正确接收了 0号帧，1号帧出错，那么发送方在下一个状态就只能收到关 于0号帧的确认，于是发送方将根据双方的约定，采用有选择重发或拉回方式来重新发送1 号帧，从而达到了差错控制的目的。发送窗口初始状态：发送方等待发送帧，可以发送0、1、2 和3号帧；接收方等待接收帧，可以接收0、1、2和 3号帧。接收窗口状态2：发送方发送帧0和1,接收方等待接收帧状态3：接收方正确接收了帧0和1,并给 发送方确认消息。接收窗口向前滑动，表 明可以接收帧2、帧3、帧4和帧5。状态4：发送方收到了关于0和1的确认消息，发送窗口向前滑动，表明可以发送帧2、帧3、帧4和帧5。图4.8滑动窗口协议的工作实例(3位序列号，窗口大小为4)该图已修改显然，滑动窗口协议在提供流量控制机制的同时，还可以同时实现帧的确认和差错控 制。正是滑动窗口协议这种集确认、差错控制、流量控制为一体的良好特性才使得该协议 不仅被广泛地应用于数据链路层中，还被作为传输层实现相应功能的重要机制。4.5 数据链路层所提供的基本服务上面我们已经对数据链路层功能及其复杂的实现机制进行了较详细的讨论，那么是否 所有系统的数据链路层都要被设计得如此复杂而完善呢？事实并非如此。在数据链路层，有三种基本服务可供选择。它们分别是无确认的无连接服务(Unacknowledged connectionless service)有确认的无连接服务(Acknowledged connectionless service)有确认的面向连接服 务(Acknowledged connection-oriented service)o在无确认的无连接服务方式下，两个相邻结 点在传输数据时一，事先不需要建立连接，从而事后也不存在释放连接的问题；源机器向目 标机器发送独立的数据帧，而目的机器不对收到的帧作确认；由于线路上的噪声而造成的 帧丢失，数据链路层将不作努力去恢复，而是将该工作留给上层(通常为传输层)去完成。这类服务通常适用于误码率很低的信道，如大多数局域网都使用这种无确认的无连接服务 方式。用于实现这类服务的数据链路层协议往往比较简单。第4章数据链路层83在有确认的无连接服务方式下，仍然不需要在传输数据之前建立连接，源机器向目标 机器发送独立的数据帧。但是，接收站点要对收到的每一帧作确认，即在收到数据帧之后 回送一个确认帧，而发送站点在收到确认之后才会发送后续的帧。当在一个确定的时间段 内没有收到确认帧时，发送方就认为所发送的数据帧丢失并自动重发此帧。自动重发可能 会产生数据帧被重复接收的问题。有确认的无连接服务方式适用于像无线网之类的不可靠 信道。在协议设计上通常要比无确认的无连接服务复杂。有确认的面向连接的服务方式分三个阶段：链路建立阶段、数据传输阶段和链路拆除 阶段：发送数据时，需要事先建立连接，之后才能启动帧的传送；在数据发送阶段，要