第3章 数据链路层 数据链路层(DataLinkLayer,DLL)位于物理层之上。相对于物理 层主要负责0和1在通信信道上的表示和传输,数据链路层主要解决的 问题是如何在相邻的两台机器间实现可靠的数据帧通信。所谓“相邻”并 非指两台并排放置的机器,而是指两台机器通过一条通信信道相互连接。 例如,通过点到点线路直连的两台机器;或者在总线拓扑结构中,通过共 享的信道相连的多台机器。“数据帧”则是数据链路层协议数据单元 (PDU)的专用名称,它被用来描述在两个数据链路层实体之间传输的信 息块。实现“可靠”的通信,是很多网络数据传输应用中极其重要的刚性 需求。可惜“可靠”并非唾手可得,因为信号的衰减、畸变等在真实的通信 信道中普遍存在,也因为传输的时延和噪声的干扰不可避免,这些因素都 让我们的网络变得不那么“可靠”。因此,我们需要设计一系列协议和算 法处理传输中的错误。有了这些协议和算法,对于数据链路层来说,才可 能为其之上的网络层提供“可靠”的通信服务。 本章将首先介绍数据链路层的主要功能;在此之后,将介绍该层的协 议数据单元(数据帧), 如何将物理层传输的二进制流转换为一个个数据 帧,即成帧的方法;然后,将围绕通信中的错误介绍检测错误和纠正错误 的方法;之后将解释如何在可能出错的信道上,实现可靠的数据帧传输, 引入肯定确认与重传技术、窗口技术、回退 n 帧技术、选择性重传技术等; 最后,将介绍一些数据链路层协议的实例。 图3-1中的数字代表其下的主要知识点个数;读者可扫描二维码查 看本章全部知识点的组织思维导图,并根据需要收起和展开。 图3- 1 本章主要内容框架的思维导图上层 106 第3章数据链路层 3.数据链路层的主要功能 1 在网络分层模型中,数据链路层的最终目的是为网络层提供服务,而为了实现这 些服务,特别是当这些服务对数据传输的可靠性有所要求时,就要求数据链路层实现 如下功能。 (1)成帧:把从物理层获得的二进制流拆分为分离的数据帧。 (2)错误处理:检测或纠正传输中发生的错误,以及处理错误。 (3)流量控制:协调发送方与接收方的数据收发速度,以免数据发送太快,超过 接收方的处理能力,而导致接收方缓存溢出被“淹没”;或者是发送太慢,而导致互相等 待浪费时间。 在实现上述功能的基础上,数据链路层为网络层提供三类服务。 (1)无确认的无连接服务。 (2)有确认的无连接服务。 (3)有确认的有连接服务。 确认(acknowledgment)是指接收方在完成一次成功的数据帧接收后,回复信息 给发送方,以表示完成了该数据帧的接收。有连接则是指在通信的过程中,需要在发 送方与接收方之间建立并保持一条物理的或虚拟的链路,一直到数据传输结束之后, 这个连接才被释放。 对于无确认的无连接服务,发送方与接收方之间不需要建立或保持连接,也不需 要接收方对接收到的数据帧进行确认。这就意味着,数据链路层不会对数据帧的丢失 或错误进行任何处理。无确认的无连接服务虽然无法实现可靠的数据传输,但是其实 现简单且快捷。 对于有确认的无连接服务,同样不要求在发送方和接收方之间建立连接,但要求 接收方对已正确接收的数据帧回复确认,类似于我们在日常生活中签收快递。这样可 以使发送方了解每个数据帧是否正确到达目的地,从而决定是否重发该数据帧。相比 无确认的无连接服务,有确认的无连接服务虽然在过程中更复杂,回复和等待确认也 使通信效率更低,但却能实现可靠的数据通信。 对于有确认的有连接服务,则完全采取不一样的策略。在发送数据之前,需要在 发送方与接收方之间建立一个连接,发送方发出的每个数据帧都会被编号,并且沿着 同一个连接发送给接收方,接收方会对已收到的数据帧回复确认,这样数据链路层可 以保证这些数据帧按照被发送的顺序正确地被接收并交给接收方的网络层。这个连 接可以被理解为一个在发送方与接收方之间的管道,为双方网络层实体之间提供可靠 的数据帧通信。 3.成帧的方法 2 前面章节已经反复提到了“数据帧”这个名称,本节就来详细介绍数据帧的概念以 及如何生成数据帧。从发送方的角度来看,当数据链路层从网络层获得数据分组时, 数据链路层的进程会将这些数据分组进行封装,加上帧头和帧尾,得到一个完整的数 3.成帧的方法17 20 据帧。数据链路层的一些协议会定义这些帧头和帧尾的格式以及对应的含义。数据 帧以二进制的形式表示,并交给物理层进行传输,当数据被接收方收到时,接收方的数 据链路层又要负责将从物理层收到的二进制流进行拆分,恢复成原本的数据帧。数据 帧的封装和拆分生成的过程如图3-2所示。 图3- 2 数据帧的封装和拆分生成的过程 在接收方,之所以要将物理层传输的二进制流拆分为离散的数据帧,主要是为 了处理错误。数据帧是数据链路层的协议数据单元,是错误处理的单位;每收到一 个数据帧就进行错误的检测和处理,稍后会详细介绍检错方法和纠错方法(参考 3节)。 3. 将二进制流拆分为离散的数据帧,看起来是一件简单的事,但实际并不简单。比 如发送方发送时在数据帧与数据帧之间插入时间间隔作为一个数据帧开始和结束的 标志,并不是一个可行方法,因为在传输过程中,可能存在时钟漂移,经过一段时间的 传输,这些间隔可能已经消失,接收方根据漂移了的间隔来分隔数据帧,可能偏离原来 数据帧的样子,由此造成错误。数据链路层用来成帧的方法主要有字节计数法、带字 节填充的字节标志法、带位填充的位标志法和物理层编码违例法4种。 3.1 字节计数法 2. 字节计数法利用在帧头的一个字段记录该帧包含的字符数,如图3-3所示。接 收方读到第一个字段时,便可知该数据帧在哪里结束,也因此知道了下一数据帧从 哪里开始。如果一切顺利,则二进制流中的每个数据帧都会被正确地识别出来,如 图3-3(a)所示。 图3- 3 字节计数法示意图 108 第3章数据链路层 但传输中的错误在所难免。一旦包含帧长度的字段出错,则后续所有的数据帧将 被错误分隔,如图3-3(b)所示。第一个数据帧中的首字段本来是“101,(”) 却被错误地 认为是“111,5(”) 字节的数据帧长变为了7字节,从此开始,后续的数据帧都被认错,且 无恢复的可能。所以,虽然字节计数法简单,却存在致命的缺陷,因此很少单独用于真 实的网络传输中。 3.2 带字节填充的字节标志法 2. 带字节填充的字节标志法克服了字节计数法固有的出错无法恢复的缺陷,它采用 一个特殊的字节FLAG 作为帧界的标志,这个特殊的字节FLAG 被称为数据帧的定 界符,一旦出错,可以扫描定界符进行再次同步,也就是可以从错误中恢复,如 图3-4(a)所示。 图3- 4 带字节填充的字节标志法原理和特例 这种方法唯一可能的问题是当作字节标志的特殊字节有可能出现在数据帧所承 载的数据域中;一旦出现这种情况,本是数据的特殊字节被当作帧界了,于是数据帧就 被错误地拆分了。 有一个类似的问题和解决方案出现在编程领域。比如在C+ + 中,我们可以用\n(“) 输(”) 出一个换行符,但是如果用户确实希望输出“\n这(”) 两个字符,而不是一个换行 符,则可用“\\n”表示。“\”被定义为C++的转义符。类似地,我们可以定义一个特殊 的转义字节(ESC), 在数据域中出现特殊字节时,要求在前面填充一个转义字节表示 其仅仅是普通数据,而非数据帧的起始标志。同样地,如果数据域本身恰好包含了转 义字节,则要求在其前也填充一个转义字节表示其为普通数据,不承载转义的特殊 含义。 接收方接收到数据时,需要将数据域中额外填充的转义字节去除,从而使该数据 与发送方发出的原始字节序列保持完全一致。在图3-4(b)所示的4个例子中,A、B 表示普通数据,第一个特例的普通数据中包含了一个FLAG,第二个特例的普通数据 中包含了一个转义字节ESC,第三个特例的普通数据中既包含了FLAG,也包含了 ESC,第四个特例的普通数据中包含了两个ESC,发送方在FLAG 或ESC 前填充ESC 作为转义,如图3-4(b)中左边数据帧中的蓝色框所示;图3-4(b)右边对应的4个数据 3.3 检错和纠错109 帧是接收方收到之后,删除了转义符之后剩下的数据帧,这正是发送方要传输的填充 前原始字节序列。 字节填充的方式要求帧长度必须是8位的整数倍,而且还限定必须使用8位作为 一个字符的表示;这给编码和通信都带来了效率损失。举个极端的例子,假如发送方 待传输的数据全部是FLAG,每个FLAG 前都要添加一个转义字节ESC,这些ESC 都是开销,真正的数据仅占填充ESC 后全部字节数的约50% 。 稍后介绍的PPP 在异步传输时,采用了带字节填充的字节标志法。 3.3 带位填充的位标志法 2. 位填充的方法允许数据帧包含任意长度的位,而且还不限制字符的编码长度。带 位填充的位标志法也要求使用一个特殊的位串作为每个数据帧的起始和终止标志,我 们约定的帧界标志位串为“01111110”。如果在数据中出现了与帧界相同的位模式 “01111110,(”) 也会被误认为是帧界,进而引发错误的帧界分隔。为了解决这个问题,发 送方的数据链路层在发送数据时,一旦发送了5个连续的“1,(”) 则强制在数据中插入一 个“0”。通过这种强制的位填充,“01111110”仅可能作为标志出现在帧头或帧尾。这 种成帧方法也称为零比特填充法。 接收方收到数据帧时,会逐一检查收到的位,一旦发现有5个连续的“1,(”) 则检查 后续紧跟的位是否为“0”:如果是“0,(”) 则自动删除该“0,(”) 从而将位串复原为原始数 据;而“01111110”的位串则是帧界标志。 相比带字节填充的字节标志法,带位填充的位标志法的开销更小,因而信道效率 更高。 PPP 工作在同步模式时,采用了带位填充的位标志法。 3.4 物理层编码违例法 2. 在很多局域网中,在物理层使用两种不同电平的转换表示一个二进制位。比如, 使用“高-低”电平转换表示“1位,(”) 而使用“低-高”电平转换表示“0”位。通过这样的编 码,每个数据位中间的电平突变,将被用来作为发送方和接收方之间的同步。在这种 编码中,连续的高电平或连续的低电平都不是有效的编码。因此,我们可以利用连续 的高电平或连续的低电平表示一个数据帧的开始或者结束,这就是物理层编码违例法 的工作原理。需要注意的是,物理层编码违例法只能使用在物理层编码包含足够冗余 信息的网络中,因为我们需要用两个物理电平位编码一位数据。 在现实的网络中,我们可将字节计数法和其他某种方法结合使用,从而进一步确 保成帧的正确性。数据帧的接收方先利用计数字段定位某帧尾,再检查该位置是否存 在正确的分界标志。比如,在IEEE802.参考4.2节)中,有8字节的前导 3数据帧( 3. 码,相当于帧界;数据帧中还有一个长度字段,指明了数据帧的长度。 3.检错和纠错 3 成帧方法可以让我们准确地识别每个数据帧的起始和结束位置。我们面临的下 一个问题是通信中的干扰和噪声。在数据传输中,由于干扰和噪声造成的错误是困扰 110 第3章数据链路层 数据通信的一个长期问题。即便是物理层使用有屏蔽的传输线路,传输数字信号的是 光纤网络,且由于传输技术的进步,传输错误率已经大大降低,但错误的发生还是存在 一定的概率。尤其是无处不在的无线网络,由于数据传输在开放空间中进行(广播), 信号更容易受到干扰和损坏。因此,错误的处理将是一个需要长期关注的问题。 通信过程中错误的处理有两种策略。一种是错误检测(erordetection),即检错。 检错的工作思路是:由接收方进行错误的检测,一旦发现传输数据中有错误,并不尝 试恢复,而是想办法通知发送方,由发送方重新发送该数据帧。另一种是错误纠正 (erorcorection),即纠错。纠错的处理只由接收方进行,不但需要发现数据帧中的 错误,还要通过算法自动对错误进行纠正,恢复出正确的数据。 两种错误处理的策略,各有适用的场景。直观的感受是,检测到1位的错误,难度 会小于纠正1位的错误。当然,检测到1位的错误所需的冗余信息,也应小于纠正1 位错误所需的冗余信息。但是,检错可能引起数据帧的重发,这又是额外的传输开销。 一般而言,在高质量的通信信道(例如光纤网络等低错误率的信道)中,由于错误 极少发生,采用检错和重发的方式效率更高。而在错误率比较高的网络(例如无线网 络)中,则更倾向使用纠错的方式,尽量减少错误数据帧的重发,以免引起信道的使用 恶化。 不管是检错还是纠错,我们都需要通过设计编码规则在数据中添加冗余信息来实 现。在下文中,我们将介绍较为简单和常见的几种检错码与纠错码的编码方案。 3.1 检错 3. 1.奇偶校验 奇偶校验(paritycheck)是一种较为简单和常见的校验数字传输正确性的方法。 奇偶校验可以通过在数据中添加1位奇偶校验位实现。以奇校验为例,假如采用奇校 验,发送方需要确保在一个数据帧中“1”的个数一定为奇数。接收方对接收到的帧中 “1的(”) 个数进行统计,若统计出“1的(”) 个数为偶数,则意味着传输过程中有错误发生,需 要发送方对该帧进行重传。 以ASCI 中的字母A为例,发送方采用奇偶校验对其进行编码,对应的二进制编 码为1000001 。若按照偶校验规则,校验位设置为0,码字应为10000010,则满足偶数 个1的要求;若使用奇校验,则校验位应该设置为1,码字应该为10000011 。如果采用 偶校验的接收方收到一个码字为10000011,发现其中有3个1,不满足偶数个数的要 求,表明发生了错误,所以,接收方可以告诉发送方重传。 奇偶校验是一种弱检错码,如果发生错误的个数不是1个或者奇数个,而是发生 了偶数个错误,则接收方无法检出错误。 在通信中,如果一个数据帧中的消息位数为 m 位,添加的校验位是 r 位,总长度 为n,则n=m+r,我们称其为一个 n 位的码字(codeword)。两个码字之间的差别, 可以用海明距离(Hammingdistance)表示。海明距离指的是两个码字对应位不同的 位数,若海明距离为d,则表示两个码字之间有 d 位的数值不同。如图3-5所示, 10011100和11001001之间有4位不同,则它们之间的海明距离为4。将两个码字进 行异或(XOR)逻辑运算,然后只需要统计结果中1的数量,就可以得到两个码字之间 的海明距离。因此,利用简单的逻辑电路就可以很容易在硬件上实现海明距离的 3.检错和纠错111 3 计算。 图3- 5 计算两个码字之间的海明距离 现实中的海明距离判断,更多的不是在两个码字之间,而是在所有有效编码的集 合内考虑海明距离。对于码字的集合,其海明距离的定义为,计算集合内每对码字之 间的海明距离,其中最小的海明距离值,被定义为该集合的海明距离。如图3-6所示, 如果有效的码字为11111111 、11110000 、00001111 、00000000,则该码字集合的海明距 离为4。 图3- 6 计算码字集合的海明距离示例 对于1位的奇偶校验来说,码字集合之间的海明距离为2,这意味着,对于任何一 个有效的码字,如果在传输过程中出现了一位的错误,则该码字都不会被误认为另一 个有效的码字。关于检错,更为普适的结论是,海明距离为d+ 1 的编码方案,最多可 以实现 d 位错误的检测。因为对于任何一个码字,如果出现 d 位的错误,必将变成一 个无效的码字。 为了提高奇偶校验的检错能力,在1位奇偶校验的基础上,可采用双向奇偶校验 (owadclaiy)的方案。该方案也称为双向冗余校验,其工作原理是将一维 rnoumnprt 的二进制数据串,作为一个m×n 的矩阵处理,对每行和每列分别添加1位奇偶校验 位。这种编码方案的检错能力更强。 2. 循环冗余校验 循环冗余校验(CyclicRedundancyCheck,CRC)是另一种在现实网络中被广泛使 用的检错编码方案,比如以太网。循环冗余校验检错的基本思想是通过在数据位后添 加若干位的校验和(checksum), 以实现错误的检测。 在循环冗余校验中,二进制串被表示为系数为0或1的多项式,例如二进制串 110011,可以表示为多项式x5+x4+x+1 。假设有 m 个数据位需要被传输,则 m 个 数据位可以表示为多项式 M (x), 添加校验和后的码字则可以表示为多项式 T (x)。 此外,发送方和接收方在传输之前,需要事先确定一个生成多项式G(x)。发送方在 生成校验和时,需要满足T(x)可以被G(x)整除。对于接收方,在收到码字后,只需 检查该码字是否还是能被G(x)整除,即可判断是否出现传输错误。循环冗余校验的 具体步骤如下: 112 第3章数据链路层 第一步:数据传输前,双方确定G(x), 假定其为 r 阶多项式。 第二步:发送方对每个数据帧计算其校验和。 (1)对于数据帧 M (x), 在其尾部添加 r 个0,表示为xrM (x)。 (2)按照模2除法运算规则,将xrM (x)对应的二进制串除以G(x)对应的二进 制串,得到余数c。 x) (3)按照模2减法运算规则,将xrM (对应的二进制串减去余数c,所得的结果 即为需要传输的完整码字,可表达为多项式T(x) 。 第三步:接收方对收到的每个数据帧进行错误检测 。 (1)对于接收到的二进制串按照模2除法,除以G(x)对应的二进制串,若不能整 除,则认为该数据帧存在错误。 (2)若能整除,则表明此传输过程未发生错误。 在上述步骤中,余数 c 就是计算得出的校验和,减去余数后,可以保证得到的 T(x)对应的二进制串能被G(x)对应的二进制串整除。模2减法等效于模2加法操 作,发送方如果用计算得到的校验和(余数c)替换并添加在帧尾的 r 个0,便可得到完 整的码字。 我们以生成多项式x8+x5+x4+1(100110001)为例,来计算1字节(00010001) 的CRC 校验码。 由于该生成多项式最高阶为8,按照CRC 规则,需要在数据位尾部添加8个0进 行升阶,得到的xrM (x), 其对应二进制串为0001000100000000 。 以xrM (x)为被除数,以生成多项式为除数,进行模2除法计算,可得到余数为 01110010,这就是CRC 校验位。以余数替换在数据尾部添加上的8个0,则可得到经 过CRC 编码后的完整码字为0001000101110010 。 接收方只要将收到的码字除以同样的生成多项式,如果余数为0(即能整除), 便 确认传输无误,可以放心接收该数据。 循环冗余校验计算较为简单,只需要进行模2的数学计算,也容易通过简单的硬 件实现。该方案被广泛地应用于以太网等现实网络中进行传输错误的检测。 在实际CRC 中,较为常用的生成多项式有CRC-8、CRC-16 和CRC-32 等。以 CRC-8为例,其对应的标准生成多项式分别 有 CRC-8:x8+x5+x4+1 (100110001) CRC-8:x8+x2+x1+1 (100000111) CRC-8:x8+x6+x4+x3+x2+x1 (101011110) 3. 互联网校验 互联网校验和(Internetchecksum)则是另一种广泛使用的检错算法。互联网校 验的基础是二进制反码求和运算。反码求和的计算过程并不复杂:将二进制数从低 位到高位逐位相加,若产生进位,则需在相邻高位加1;当最高位相加出现进位时,则 需要在结果的最低位加1;将最后计算所得的二进制数取反,就是二进制反码求和的 结果。图3-7描述了对两个二进制数进行反码求和运算的简单示例。 在计算互联网校验和时,数据按照每16 位作为一个单位被划分成一个序列。如 果数据的字节长度为奇数,则在数据尾部填充1字节的0以凑成完整的16 位。发送 3.检错和纠错113 3 图3- 7 二进制反码求和运算示例 方按照反码求和运算规则将所有16 位字的序列进行相加,然后再对相加的结果取反 码,便得到校验和。 接收方进行检错的过程就是将收到的数据(包括校验和), 再次以每16 位作为一 个单位进行反码求和运算。如果运算结果为0,则表明数据在传输过程中没有错误; 如果运算结果为非0,即认为检测到错误,接收方将丢弃该数据。 你知道吗?本书后续章节将陆续介绍的IP 、ICMP 、TCP 、UDP 等重要协议都 使 用了互联网校验进行错误检测。其中,ICMP 校 IP 校验和只是计算IP 报文的头部 , 验和计算则包括了ICMP 头部和ICMP 数据。TCP 和UDP 校验和计算除了包 括 头部和数据,还需要包括伪头部。这些协议的具体格式都将在后续章节进行详 细 介绍 。 3.2 纠错 3. 相对于检错,纠错可以减少重传,但是也意味着对于每个数据帧,都需要额外传输 更多的冗余数据以及更复杂的纠错算法。纠错本身并不神秘,我们在日常生活中经常 不自觉地对所接收到的信息进行纠错处理。比 如一张字迹不清的字条,一块显示不全的屏幕, 一通断断续续的电话。很多情况下,虽然数据不 全或因为干扰产生错误,但在不自觉地进行纠错 之后,我们仍然可以获得数据所包含的信息。最 简单的纠错方式是寻找最相似或最可能的匹配。图3- 8 对一个无法正确显示 例如图3-8显示的电子钟屏幕,由于故障,只能显的数字的推断 示出如左侧所示的图案,但是对于我们来说,可以毫不费力推断出数字8(如右侧显 示)是最可能的数字。生活常识告诉我们,对于错误的信号,可以通过找与之最接近的 正确信号,进行直接且有效的纠错。 结合前文有关海明距离的知识,对于编码的纠错,我们可以得到一个更为普适的 结论:海明距离为2d+ 1 的编码方案,可以实现对 d 位错误的纠错。可见纠错付出的 冗余代价要比检错大得多。下面介绍几种常见的纠错方法。 1. 纠1位错的海明码 纠1位错的海明码是一种经典的自动纠错编码,该编码方案具备1位错误的纠正 能力。整个海明码分为在发送方的编码阶段,以及在接收方的解码阶段(纠错)。对于 需要发送的 m 位数据,首先需要确定所需的校验位 r 的数值,从而确定编码中整个码 字的长度n,且n=m+r。 114 第3章数据链路层 对于 m 位数据,可以组合出2m 个不同的消息。如果只考虑纠正1位错,而该位 错误可能在 n 位中的任何一位出现,因此,对于2m 条数据对应的正确码字和出现1 位错误的码字,其总数为( m 。同时由于码字总长度为 n 位, n+1)×2则这些码字的个 数必须满足( n 。考虑到n= m +1,该不等式可变换为( r 。 n+1)×2m ≤2m +r+1)≤2 例如,当消息位长度 m 为7时,海明码方案中要求校验位的长度 r 必须大于或等于4, 才可实现该编码。 发送方的编码过程按照如下步骤进行。 (1)将码字中的所有位从1到 n 编号,其中编号为2的幂次方的位设置为校验位 (如1,4,其余位( 3,6,为数据位。依次将 m 个数据位按照顺序 2,8,…), 如2,5,7,…) 填入 ( 。 2)校验位的数值,由对某组位使用奇偶校验得到(见图3-9)。具体的规则如下。 图3- 9 海明码进行校验位奇偶校验的规则示意图 ● 将数据位的编号 k 用2的幂次方的和表示,如11=8+2+1 。 ● 所有编号 k 的展开式中出现2r 的位,用来对2r 校验位进行奇偶校验。例如, 编号为2的校验位数值,将由编号为2、3、6、7、10 、11 等位的奇偶校验决定是0 或者1。 (3)完成所有校验位的计算,最终形成该报文的海明码表示。 当接收方收到m+r= n 位的海明码码字后,需要对该码字进行校验和纠错。海 明码纠错过程,实际就是计算出码字中出错的那位,然后对该出错位进行取反操作,便 完成了1位纠错的任务。接收方具体的纠错过程如下。 (1)收到一个码字时,接收方初始化计数器 c 为0。 (2)对每个校验位按照海明码的计算方法进行重新计算,判断其是否满足奇偶校 验的要求。 (3)若校验位 r 不满足奇偶校验条件,则更新计数器c=c+r。 (4)完成所有校验位的计算后,检查计数器 c 的数值。若 c 为0,则表示该码字无 错误,可被正确地接收;若 c 非0,则对码字中的第 c 位进行取反,从而实现海明码的1 位纠错。 以数据01111110 为例,采取偶校验的海明码实现1位纠错。 根据不等式(m+r+1)≤2r ,可以确认对于8位数据最少需要的校验位 r 为4,分 别记为P1、P2、P3 和P4,它们在码字中的位置编号则分别为1、2、4、8,将数据位依次 填入对应的位,对于4个校验位,我们有如下偶校验计算: 3.检错和纠错 3 P1=M3⊕M5⊕M7⊕M9⊕M11=0⊕1⊕1⊕1⊕1=0 P2=M3⊕M6⊕M7⊕M10 ⊕M11=0⊕1⊕1⊕1⊕1=0 P3=M5⊕M6⊕M7⊕M12=1⊕1⊕1⊕0=1 P4=M9⊕M10 ⊕M11 ⊕M12=1⊕1⊕1⊕0=1 因此,最终完成偶校验后海明码的码字为000111111110 。 对于接收方来说,若收到的码字为000111011110,则接收方需要重新计算4位 校验位。对于P1、P2、P3 和P4 分别有如下计算: P1=M3⊕M5⊕M7⊕M9⊕M11=0⊕0⊕1⊕0⊕1⊕1=1 P2=M3⊕M6⊕M7⊕M10 ⊕M11=0⊕0⊕1⊕0⊕1⊕1=1 P3=M5⊕M6⊕M7⊕M12=1⊕1⊕1⊕0⊕0=1 P4=M9⊕M10 ⊕M11 ⊕M12=1⊕1⊕1⊕0=0 在4位校验位中,P1、P2、P3 三位均不符合偶校验的要求,其对应的位置编号1、 2、4累加所得结果为7,即c=1+2+4=7。接收方依此判断第7位出错,需要进行取 反操作,纠正后的码字为000111111110 。 在较为可靠的传输信道中,传输错误只是偶发性的小概率事件,具备1位纠错能 力的海明码方案完全可以胜任纠错的需求。但是对于容易受干扰、可靠性较差的网络 (如无线网络),由于传输错误发生率较高,一个码字中可能出现连续多位的错误,显然 传统的海明码方案无法满足纠错任务。这种连续位的错误,又称为突发错误。 但可以通过一个小改进,让海明码实现 对一个码字中多位连续错误的纠错,即实现 纠正突发错误。简单的改进方案(见图3-10) 就是将 i 个长度为 j 的码字组成一个i×j 的矩阵。发送方在发送这些码字时,并非将 这些码字逐个发送,而是按照矩阵的列逐列 发送。通过这种方式,传输中连续多位的错 误将可能出现在不同行的码字中。当接收 方收到这i×j 个位后,重新将这些数据按 照 i 个码字逐个进行海明码的纠错。如果运气足够好,则连续位的错误都有可能被成 功纠正。 2.里德-所罗门码 里德-所罗门码(简称里所码,Red-Solomoncode)是另一种使用广泛的纠错编码 方案,比如,应用于CD存储、DVD存储、DSL传输、WiMAX传输技术等。里所码是 定义在有限域(也称为伽罗华域,GaloisField,GF)中的。里所码的相关计算也遵从有 限域中的加减乘除运算法则。 里所码与海明码显著的不同在于,海明码以码字中的位为计算对象,而里所码则 以“符号”(symbol)为单位,一个符号可以是1字节,即8位信息。里所码的编码结构 如图3-11所示,一个完整的里所码包含 n 个里所码符号,每个里所码符号由 m 位构 成,通常 m 为2的幂。 n 个里所码符号中,即为真正需要被发送的信 k 个为消息符号, 息,另外的2t 个符号为校验符号(2t=n-k)。里所码具备纠正 t 个任何错误的能力, 这 t 个错误可以是连续的突发性错误,也可以是分布在不同符号中的离散错误。 图3-10实现连续错误纠正 的海明码改进方案 116 第3章数据链路层 图3-11中的一列表示 m 位的符号,记为S1,S2,…。 图3-11 里所码的编码结构 里所码编码原理的数学描述并不复杂,主要分为4个步骤。 (1)以多项式的形式表示 k 个消息符号,记为 M (x)。 (2)将 M (x)升为2t 阶,即 M (x)x2t。 (3)将 M (x)x2t 除以生成多项式 G (x),余下的多项式为校验多项式,记为 P (x)。 (4)计算 M (x)x2t+P(x),即为生成的里所码。 编码过程的本质是将 k 维的信息数据映射到了 n 维空间中,并且保证 n 维空间 中的 k 维数据子空间与2t 维校验空间是正交的。 若在传输过程中没有出现错误,则接收方所收到的里所码保证能被生成多项式 G (x)整除。若传输过程中出现不超过 t 个错误,则接收方可以通过解码确定出错符号 位置,以及所对应的正确数据,从而实现纠错。 接收方收到的编码若以R(x)表示,则R(x)被生成多项式G(x)除后,所得的余 记为S(x),也称为Syndrome 。S(x)就是因为错误产生的,定义一个错误多项式 (erorlocator)E(x)=(1+X1x)(1+X2x)…(1+Xvx),根据Syndrome值,最后可 以计算得到E(x)多项式,其中包含了出错符号的位置以及正确数值的信息。正确的 里所码C(x)可以通过计算R(x)-E(x)获得。 需要强调的是,里所码中提及的所有数学运算,均使用有限域GF(2q )中的模运算 法则。对具体计算过程感兴趣的读者,需要对有限域中的数学运算进行一定的学习。 你知道吗:有限域是数学家伽罗瓦于18世纪30年代研究代数方程根式求解 问题时引入的概念。有限域在密码学、近代编码、计算机理论、组合数学等方面有着 广泛的应用。有限域是指仅含有限个元素的域,在有限域中进行加法、减法、乘法和 除法运算,其结果不会超出域集合。 3.低密度奇偶校验 低密度奇偶校验(LowDensityParityCheck,LDPC)码是另外一种较为常用的纠 错编码,用于存储过程和无线网络通信中。LDPC码的基本思想是通过一个生成矩阵 G 进行编码,通过一个校验矩阵 H 实现译码,即为实现编码的纠错。此时,生成矩阵 G 和校验矩阵 H 之间满足G×HT=0的条件。 3.检错和纠错117 3 在LDPC 码方案中,发送的码字由信息位序列 M 与生成矩阵 G 相乘获得。假设 M 为(110), G 为3×6 的矩阵,如图3-12 所示,则编码得到的码字 C 为(110010 )。 注意,LDPC 码中的元素与元素是进行模二加法(异或)运算。 LDPC 码的译码有硬判决和软判决两种方法。其中,硬判决是指对信道输出位直 接做出是1或0的判决,比特翻转算法是一种典型的硬判决算法;软判决不是直接输 出1或0,而是给出某位是0或1的概率,这个方法也称为和积译码,置信传播算法则 是典型的软判决算法。 我们以位翻转算法为例进行讨论。由于生成矩阵 G 和校验矩阵 H 之间满足 G×HT=0的关系,对应于图3-12 的生成矩阵,有与之对应的校验矩阵 H ,如图3-13 所示。通过HCT,校验矩阵定义了三个校验方程。 图3-12 LDPC 码编码示例图3-13 LDPC 码校验矩阵 H 示例 校验方程1: C1⊕C2⊕C4 校验方程2: C2⊕C3⊕C5 校验方程3: C1⊕C2⊕C3⊕C6 当接收方收到码字 C 后,需要将其与校验矩阵 H 相乘,进行译码操作。若HCT 得到一个零向量,即三个校验方程的结果均为0,则译码成功,接收方已经接收到正确 信息。 假设在传输过程中 C 码字发生一位错误,接收到的码字为(010010), 则校验 方程1和3结果为非0。由于我们只处理一位错误的情况,校验方程1和3中,同时出 现的C1 和C2 均可能出错。但由于校验方程2的结果为0,则证明C2 并未出错,那么可 以判定出错位必然是C1。将C1 进行翻转,则译码得到正确的码字为(110010 )。 你知道吗? 除了LDPC 码之外,涡轮码(Turbocode)和极化码(Polarcode)是 另两种在通信领域得到广泛使用的前向纠错编码技术。其中,极化码由土耳其数学 家ErdalArikan教授于2008 年在国际信息论ISIT 会议上提出,是人类已知的第一 种能够被严格证明达到信道容量的信道编码方法。2016 年,我国的华为公司主推 的极化码方案,成为国际无线标准化机构3GPP 通过的5G 通信控制信道编码 方案。 118 第3章数据链路层 3.可靠传输数据帧的技术 4 为了简化和明确本节所讨论的问题范围,我们先明确如下三点假设。 (1)分层独立假设。本节讨论的数据传输系统严格遵循网络分层模型,网络层和 物理层作为数据链路层相邻的上下层,三者为彼此独立的进程。相邻层的进程之间通 过消息传递实现上下层之间的通信。 (2)可靠服务假设。数据链路层要为网络层提供可靠的传输服务。在接收方,数 据链路层以正确的顺序将正确的数据交给网络层。同时为了简化起见,我们假设在发 送方的数据链路层所需发送的数据随时可以从网络层获得。 (3)通信错误假设。在本节,我们仅处理通信错误,而不考虑由于设备重启、异常 断电、崩溃等产生的数据错误。 就像前文介绍的一样,在进行数据传输的过程中,错误是不可避免的。除了环境 噪声干扰、传输时延、信号衰减等因素造成的错误之外,也可能是由于接收方不能及时 处理所接收的数据,在缓存耗尽之后,不得不丢弃数据。总而言之,数据传输从网络本 身的物理属性来看,是不可靠的。而数据链路层所要实现的基本功能之一,就是要为 网络层提供可靠的数据传输服务。因此,除了上文所说的检错纠错之外,需要发送方 和接收方共同遵循一些重要的协议规则。 前文也提到,在发送方和接收方的数据链路层之间,交换的数据单元是数据帧。 因此,在这部分,我们来讨论如何通过设计协议保证这些数据帧在通信双方的数据链 路层之间正确可靠地传输,并分别把数据帧内的有效载荷数据提交给网络层。 3.1 流量控制 4. 如果数据传输的信道是完美的,接收方的处理速度无限快,或者说接收方拥有无 限大的缓存,则传输的数据帧既不会受损也不会丢失。这种被学者们称为“乌托邦”的 场景不需要我们进行任何错误控制或流量控制,便可实现可靠的数据传输。当然这是 现实中几乎不可能出现的通信场景。真实的通信错误主要来自两方面:一是通信信 道上产生的错误,例如噪声干扰、衰减时延等;二是由于接收方无法及时处理到达的数 据而导致数据的丢弃。 在本节,我们先考虑后者,即在真实的数据通信场景中,接收方处理到达的数据帧 需要一定时间。当处理数据帧的速度低于数据帧到达的速度时,接收的数据帧就只能 存放在接收方的缓存中,而缓存的大小必然是有限的,因此数据帧被丢弃的可能必然 存在。 解决这一问题的基本思想非常简单,就是需要对发送方和接收方之间数据流量进 行控制,避免发送方以超过接收方处理能力的速度发送大量数据帧,最后导致接收方 被“淹没”(overwhelming)。有两种策略可以用来实现发送方和接收方之间的流量控 制:基于固定传输速率的流量控制和基于反馈机制的流量控制。 第一种策略,需要通信双方在进行数据传输之前约定好固定的数据帧传输速度, 确保发送数据帧的速度不超过接收方的处理能力。虽然理论上这种流量控制方式很 容易被实现,但是在现实中,因为接收方可能需要同时与不确定数量的发送方进行通 图3-14停-等机制的流量控制流程 3.4 可靠传输数据帧的技术119 信,接收方的处理能力很难事先被准确地估计。如果通信双方约定一个过低的数据帧 传输速度,会导致低效的传输效率和宽带资源的浪费。 因此,基于反馈机制的流量控制相对来说更合理和可行。反馈机制要求接收方在 完成一个数据帧的接收,并成功提交给网络层 后,向发送方进行反馈,告知其可以进行下一个 数据帧的发送。在实现中,通常由接收方在完 成到达数据帧的处理后,向发送方发送一个空 帧(dummyframe,也称为哑帧)作为成功接收 的反馈确认。 站在发送方的角度来看,这一过程可以表 述为,向接收方发送一个数据帧后即停下(阻 塞), 等待来自接收方的反馈确认到达,空帧到 达后,再开始新一数据帧的发送,并等待新的确 认。因此这种流量控制机制也称为停-等(stopand-wait)协议。 利用停-等机制的流量控制流程如图3-14 所示,数据帧是由发送方到接收方单向传输,作为确认的空帧,则在相反方向传输。为 了实现流量控制,所付出的代价是发送方在每个数据帧发送之后,进行一段时间的 等待。 3.2 肯定确认与重传 4. 传输中导致数据错误或丢失的另一个原因则是传输信道并不总是完美可靠。对 于发生错误的数据帧,利用编码方案进行自动纠错是一种选择。但纠错能力的增强, 也意味着需要传输更多冗余信息和花费更多的计算资源。相对来说,采用错误检测策 略,并要求对方对错误数据帧进行重传,则是一种妥协后更经济的方案。那如何在发 送方和接收方之间进行控制,从而实现错误数据帧和丢失数据帧的重发呢? 借鉴停-等协议的思想,很容易找到如下一个简单的解决方案。 对于发送方,我们只需要再设置一个计时器(timer), 每发送一个数据帧,发送方 timeout) 就开启这个计时器,只要在计时器超时(之前,能收到来自接收方的确认,则 认为该数据帧被正确收到;否则一旦计时器超时,则自动重发当前数据帧。 对于接收方,如果收到的数据帧被检测出错误,则保持沉默。只有到达数据帧是 无误的,接收方才发送确认帧。 该方案的主要思想是,只要发送方超时,即进行当前数据帧的重发。但是,如果我 们考虑超时产生的原因,就会发现该方案可能导致问题。由于当前考虑的是真实的不 可靠的通信信道,数据帧和作为确认的空帧都面临错误或丢失的风险。如果超时是由 于确认帧无法正确到达而产生,则此时被重发的数据帧其实已被接收方正确收到(见 图3-15 )。对于接收方,当重发的数据帧再次到达时,根本无从判断该数据帧是重发 数据帧还是下一个新数据帧。 那接收方能否从数据帧的内容上进行是否为重发数据帧的判断呢? 答案也是否 定的。首先,这破坏了分层独立性,数据帧承载的数据内容对于数据链路层应该是透 120 第3章数据链路层 图3-15 重发帧因为能被识别而被错误接收 明不可见的。其次,即便数据内容一样,也不能确认该数据帧为重传的数据帧,也可能 发送方确实需要连续发送两个相同内容的数据帧。 为了解决确认帧丢失引发的重复接收重复数据帧的问题,我们需要在帧头附加一 个可以标识不同数据帧的字段,称为数据帧的序列号(sequencenumber),或者帧号 ( framenumber)。由于传输采取停-等机制,帧号仅需要用来识别连续的两个数据帧 是否是重传的同一数据帧。因此仅需用一位二进制数,让帧号在0和1之间切换便可 满足要求。当接收方收到帧号连续为0或连续为1的数据帧时,便可判断这是重传的 数据帧,数据需要丢弃,而不是交给自己的网络层。 这种需要收到一个成功接收确认再进行新数据帧发送,否则超时重传的协议,称 为自动重传请求(AutomaticRepeatreQuest,ARQ)协议,或支持重传的肯定确认 (PositiveAcknowledgementwithRetransmision,PAR)协议。该协议在正常和异常 情况下的工作示例分别如图3-16和图3-17所示。 图3-16 在正常情况下PAR 工作流程图3-17 PAR 在出现确认帧丢失时的工作流程 3.可靠传输数据帧的技术121 4 3.3 传输效率评估和提升 4. 让发送方每发送一个数据帧就停下来等待确认或超时,以决定是否开始发送新数 据帧或者重传,这种方法虽然可以实现可靠的传输,但很明显它是极其低效的,因为有 相当多的时间都被用来等待,导致网络带宽的浪费。 如图3-18 所示,假设每个数据帧的长度固定为 f 位,传输信道的带宽为bb/s,则 发送方需要逐位发送完一个数据帧的时间 T =f/bs。而在这之后,发送方被阻塞需 要等待确认帧到达的时间(D)由信号在两端之间来回传输的时延(以及接收方完 r), 成处理该数据帧并生成确认帧的时间(p)决定。表示传输效率的信道利用率(channel utilization)可以计算为T/(T+r+p)。如果忽略数据帧的处理时间p,信道利用率 则可表示为f/(f+rb)。由此可见,传输距离越远,传输时延越大,网络带宽越高,信 道利用率越低,因为大多数的时间都被用来等待确认的到达。 图3-18 信道利用率计算示意图 有效提升信道利用率的方法是不再拘泥于停-等协议的机制,而让发送方可以连 续发送 w 个数据帧。如图3-19 所示,最理想的状态下,当发送方完成第 w 个数据帧 的发送时,第一个数据帧的确认恰好到达,发送方可以立刻进行第 w +1 个数据帧的 发送。这时候的信道利用率理论上可以达到100% 。 图3-19 连续发送 w 个数据帧时信道利用率计算示意图 这就是滑动窗口(slidingwindow)协议的思想。具体实现时,需要在发送方维护 一个发送窗口(sendingwindow), 发送窗口的大小w,即为允许不等待确认而连续发 送数据帧的最大数量。发送窗口装载的是已经发送但其确认尚未到达的数据帧,这些 数据帧都有可能由于传输错误或丢失而被要求重传。当发送窗口被填满时,发送方必 须停止发送,而等待关于这些数据帧的确认帧的到达。当发送窗口内的数据帧被确认 接收后,该数据帧需要被移出窗口,同时发送窗口向前滑动,继续发送后续的数据帧。 122 第3章数据链路层 接收方也需要维护一个接收窗口(receivingwindow), 用来判断哪些数据帧可以 直接交给网络层,哪些数据帧需要暂时缓存,哪些数据帧需要丢弃。接收方需要确保 所有正确接收的数据帧,以正确的顺序交给网络层。在某个数据帧的数据被提取出来 交给网络层后,该数据帧也需要被移出接收窗口,并将接收窗口向前滑动。 由于不再使用单纯的停-等协议工作机制,如果发送窗口的尺寸大于1,意味着可 能有多个数据帧同时到达,或可能同时被确认。为了区分这些数据帧,此时的帧号不 能仅用1位二进制数表示,更普适性的表示方法是用 n 位表示帧号,帧号按照顺序从 0到2n -1之间被循环使用。 其他提升传输效率的思路,是关于确认帧的传输。在停-等协议中,数据帧和作为 确认的空帧都是单向传输的。而在实际的网络通信中,数据的传输通常都是双向进行 的,发送方本身也是数据的接收方,接收方也需要发送数据给发送方。那么,为什么还 要专门发送空帧作为确认的反馈呢? 对收到数据帧的确认帧,完全可以包含在反向传 送的数据帧头中,以一个附加字段的形式发送。这种“搭便车”发送确认帧的方式,称 为捎带确认(piggybacking)。关于“搭便车”,这里又产生如下两个问题。 第一,反向的数据帧并不是时刻发送的。为了搭便车,可能需要等待很长时间才 能被发送,由此也会造成传输效率的下降。解决的方案通常是设定一个计时器,在计 时器超时前,如果未能实现捎带确认,则不得不使用空帧进行确认帧的传输。 第二,在等待“搭便车”的过程中,也可能有新的数据帧到达。由于滑动窗口机制 的采用,发送方可能连续发送多个数据帧。比如帧号为0的数据帧从主机A到达主 机B后,关于0号数据帧的确认帧正在等待“搭便车”。在等待的过程中来自A且帧 号为1、2、3的数据帧也纷纷到来。这时候等到了一个需要由B反向传输到A的数据 帧,那搭便车的应该是关于哪个数据帧的确认帧呢? 解决的方法也很简单,我们只需 要对最后一个成功接收并且交给网络层的数据帧进行确认即可。在上述例子里,主机 B只需要对3号数据帧进行确认即可。当A收到来自B关于3号数据帧的确认帧 时,便可以推断之前的0、1、2号数据帧已经被B成功接收,于是可以将0、1、2、3号数 据帧均移出A的发送窗口,因为已经确保不需要重发它们了。发送窗口向前滑动后, 可以用来发送更多后续的数据帧。这种确认方式,也称为累积确认(cumulative acknowledgement)。 关于捎带确认以及滑动窗口具体的实现,我们将在下一节具体展开说明。 4.滑动窗口协议 3.4 滑动窗口协议允许发送方连续发送 w 个数据帧,而不需要完成每个数据帧的发 送后停下来等待该数据帧的确认帧。这可以对传输效率进行有效提升,但同时也带来 新的问题:如果连续发送的 w 个数据帧中间有一个数据帧被丢失或者发生错误,该 如何处理呢? 滑动窗口协议通常有两种处理错误数据帧或丢失数据帧的策略:回退 n 帧(goback-n)协议或选择性重传(selectiverepeat)协议。 顾名思义,回退 n 帧协议在发送窗口中某个数据帧出错超时时,该数据帧以及其 后续所有数据帧将要重新发送。对于回退 n 帧协议,需要维护一个较大的发送窗口, 以保证传输效率。当接收一个数据帧时,只需要判断该数据帧是否为坏数据帧(数据 3.可靠传输数据帧的技术123 4 帧内容错误,或者并非按顺序到达的数据帧)。若该数据帧无误,则将该数据帧交给网 络层的进程处理,否则就抛弃该数据帧。 图3-20 展示了回退 n 帧协议的一个例子。在该例子中,接收窗口大小为1。数 据帧F0、F1 被成功接收时,将分别发送确认帧,接收窗口相应地往前滑动。当数据帧 F2 出错时,该数据帧将被丢弃,且不会发送任何确认帧。后续的F3、F4 等数据帧虽然 正常到达,由于其并非满足接收窗口的要求,因此也将被丢弃,接收方将再次发送关于 最后一个成功交给网络层的数据帧的确认帧(ACK=1), 此时接收窗口保持不变。 图3-20 回退 n 帧协议工作示意图 当发送窗口中的F2 对应计时器超时后,F2 以及后续的F3、F4 等数据帧将被重 传。如果它们能被正确接收并确认,发送窗口和接收窗口都将继续滑动,直至所有数 据发送完毕。 回退 n 帧协议虽然对到达数据帧的处理简单,但在出错时,要求将发送窗口中发 生错误的数据帧以及后续数据帧全部重传。在错误率比较高的网络中,这将导致大量 的数据要求重传,造成带宽资源的浪费。 选择性重传协议要求只将发送窗口中的错误或超时数据帧进行重传。接收方对 于到达的数据帧,需要分如下两种情况处理。 第一种情况,对于到达的数据帧,若其帧号并非在接收窗口,则直接丢弃该数据 帧,再次发送关于最近成功接收并交给网络层的数据帧的确认帧。 第二种情况,若到达数据帧的帧号落在接收窗口区间内,则需要判断是否需要将 该数据帧的数据提交给网络层。若数据帧并非按正确顺序到达,则需要暂时缓存该数 据帧,发送关于最近成功接收并交给网络层的数据帧的确认帧。在等到缺失数据帧到 达后,才逐次提交给网络层。同时,接收方需要向前滑动接收窗口,并发回确认帧。 图3-21~图3-23 展示了选择性重传协议工作的三种场景。接收方接收窗口大小 为4,当前允许接收的帧号为1、2、3、4。在图3-21 的场景中,到达的数据帧的帧号为 5,接收方判断其不在接收窗口内,因而丢弃该数据帧,并再次发送关于0号数据帧的 确认帧。 在图3-22 的场景中,在1号数据帧到达后,接收窗口向前滑动,窗口中的帧号更 新为2、3、4、5。 在图3-23 的场景中,帧号为3的数据帧到达后,将被缓存,直到1号、2号数据帧 到达,1号、2号和3号数据帧将依次被提交给接收方的网络层,并被确认,同时接收窗 口向前滑动,更新为4、5、6、7。 124 第3章数据链路层 图3-21 选择性重传协议中收到不属于接收窗口帧号的情况 图3-22 选择性重传协议中收到期望帧号后滑动接收窗口 图3-23 选择性重传协议中接收的数据帧被缓存于接收窗口后的情况 3.5 滑动窗口与帧号 4. 滑动窗口协议允许连续发多个数据帧从而提高信道利用率,发送窗口的大小 w 决定了可以不等待确认连续发送数据帧的数量。那么是否是发送窗口越大,信道利用