第3章数据链路 层 本章将介绍网络模型中的第二层———数据链路层的设计原则。本章内容涉及两台相邻 计算机实现可靠、有效的完整信息单元(称为帧)通信的一些算法,而不像物理层那样只关注 单个比特传输。这里的相邻是指两台计算机通过一条通信信道连接起来,通信信道在概念 上就像一条线路(比如同轴电缆、电话线或者无线信道)。信道像一条线路的本质之处在于 信道上传递的比特顺序与发送顺序完全相同。 刚开始,你可能认为这个问题非常简单,似乎没有什么内容需要学习———计算机A把 比特放到线路上,然后计算机B将这些比特取下来。不幸的是,通信信道偶尔会出错。而 且,它们只有有限的数据传输率,并且在比特的发送时间和接收时间之间存在一个非零延 迟。这些限制对数据传输的效率有非常重要的影响。通信采用的协议必须考虑所有这些因 素。这些协议正是本章的主题。 在介绍了数据链路层的关键设计问题以后,本章将通过考察错误的本质以及如何检测 和纠正这些错误来开始数据链路层协议的学习。然后,本章将学习一系列复杂性逐步递增 的例子协议,每个协议解决了本层中越来越多的问题。最后,本章将给出一些数据链路层协 议的例子。 3.数据链路层的设计问题 1 数据链路层使用其下面的物理层提供的服务在通信信道(可能是不可靠的)上发送和接 收比特。它要实现以下功能: 3.1节)。 (1)向网络层提供一个定义良好的服务接口(1. (2)将字节序列组成帧,3.3节)。 3.2节)。 成为自包含的数据段(1. (3)检测和纠正传输错误(1. (4)调节数据流, 3.4节)。 确保慢速的接收方不会被快速的发送方淹没(1. 为了实现这些目标,数据链路层从网络层获得数据包,然后将这些数据包封装成帧 (frame)以便传输。每个帧包含一个帧头、一个有效载荷(用于存放数据包)以及一个帧尾, 如图3-1所示。帧的管理构成了数据链路层工作的核心。在后面的几节中将详细地讨论上 面提到的所有问题。而且,当使用了不可靠的无线网络时,使用协议增强数据链路层通常也 会提高性能。 图3- 1 数据包和帧的关系 第3章数据链路层157 虽然本章主要讨论数据链路层及其协议,但是,本章中介绍的许多原理,比如错误控制 和流量控制等,同样可以在传输层和其他协议中寻觅到类似的踪迹。这是因为可靠性是一 个总目标,这个目标的实现需要各层的紧密配合。实际上,在许多网络中,这些功能最常出 现的地方是上层,数据链路层只做最少的一点“足够好”的工作。然而,不管它们出现在哪 里,其原理是一致的。在数据链路层中,它们通常表现出最为简单和纯粹的形式,因此,数据 链路层是详细学习这些原理的绝佳之地。 3.1 提供给网络层的服务 1. 数据链路层的功能是为网络层提供服务。数据链路层最主要的服务是将数据从源主机 的网络层传输到目标主机的网络层。在源主机的网络层有一个实体(称为进程), 它将一些 数据包交给数据链路层,要求传输到目标主机。数据链路层的任务是将这些数据传输给目 标主机,然后这些数据再被进一步交付给网络层,如图3-2(a)所示。实际的传输过程则是沿 着图3-2(b)所示的路径进行的,但很容易将这个过程想象成两个数据链路层的进程使用一 个数据链路层协议进行通信。基于这个原因,在本章中将隐式使用图3-2(a)的模型。 图3- 2 数据路径 数据链路层可以设计成提供各种不同的服务。实际提供的服务因具体协议的不同而有 所差异。下面依次考虑3种合理的可能性: (1)无确认的无连接服务。 (2)有确认的无连接服务。 (3)有确认的面向连接服务。 无确认的无连接服务是指源主机向目标主机发送独立的帧,目标主机并不对这些帧进 行确认。以太网就是一个提供此类服务的数据链路层的绝佳实例。事先不需要建立逻辑连 接,事后也不用释放逻辑连接。若由于线路的噪声造成某一帧的丢失,数据链路层并不会试 图检测这样的丢帧情况,也不会试图恢复丢失的帧。当错误率很低时,这类服务是非常合适 的,此时差错恢复过程可以留给上面的层完成。对于实时流量,比如语音或者视频,这类服 务也是合适的,因为在实时流量的情况下数据迟到比数据受损更糟糕。 158 计算机网络(第6版) 从可靠性角度而言,下一步是有确认的无连接服务。当提供这类服务时,仍然没有使用 逻辑连接,但发送的每一帧都单独进行确认。这样,发送方可知道一个帧是已经正确地到达 目的地还是丢失了。如果一个帧在指定的时间间隔内还没有到达,则发送方将再次发送该 帧。这类服务在不可靠的信道上非常有用,比如无线系统。IEEE802.就是此类 服务的一个典型例子。 11(WiFi) 或许有一点值得强调,那就是在数据链路层提供确认只是一种优化。它永远不是一种 需求。网络层总是可以发送一个数据包,然后等待该数据包被远程机主机上的对等体确认。 如果在重传计时器超时以前确认还没有收到,那么发送方只要再次发送整条消息即可。这 一策略的麻烦在于它可能是非常低效的。数据链路层通常对帧长度有严格的限制,这是由 硬件强加的;此外还有传播延迟。网络层并不知道这些参数。网络层可能发出了一个很大 的数据包,该数据包被拆分到(比如说)10 个帧中,而且平均20% 的帧会被丢失。这个数据 包可能需要花很长时间才能完成传输。但是,如果每个帧都单独确认和重传,那么差错就能 更直接并且更快地被纠正。在可靠信道(比如光纤)上,重量级的数据链路层协议的开销可 能是不必要的;但在无线信道(具有内在的不可靠性)上,这种开销通常还是非常值得的。 我们再回到有关服务的话题上,数据链路层向网络层提供的最复杂的服务是面向连接 的服务。通过这种服务,源主机和目标主机在传输任何数据以前都要建立一个连接。在连 接上发送的每一帧都被编号,数据链路层确保发出的每一帧都会真正被接收到,而且它还保 证每一帧只被接收一次,并且所有的帧都按正确的顺序被接收。因此,面向连接的服务相当 于为网络层进程提供了一个可靠的比特流。它适用于长距离且不可靠的链路,比如卫星信 道或者长途电话电路。如果采用有确认的无连接服务,可以想象,如果确认丢失,会导致一 个帧被收发多次,因而浪费带宽。 当使用面向连接的服务时,数据传输要经过3个阶段。在第一个阶段,要建立连接,双 方初始化各种变量和计数器,这些变量和计数器记录了哪些帧已经接收到,哪些帧还没有接 收到。在第二个阶段,才真正传输一个或者多个帧。在第三个也是最后一个阶段,连接被释 放,所有的变量、缓冲区以及其他用于维护该连接的资源也随之被释放。 3.2 成帧 1. 为了向网络层提供服务,数据链路层必须使用物理层提供给它的服务。物理层接收一 个原始比特流,并试图将它传递给目的地。如果信道上存在噪声,就像大多数无线链路和某 些有线链路那样,物理层就会在它的信号中添加一些冗余,以便将误码率降到一个可容忍的 程度。然而,数据链路层接收到的比特流不能保证没有错误。某些比特的值可能已经发生 变化,接收到的比特个数可能少于、等于或者多于传送的比特个数。检测错误和纠正错误 (如果有必要)的工作正是数据链路层该做的。 对于数据链路层来说,通常的做法是将比特流拆分成离散的帧,为每一帧计算一个名为 校验和的短令牌(本章后面将讨论校验和算法), 并将该校验和放在帧中一起传输。当一帧 到达目标主机时,要基于收到的帧重新计算校验和。如果重新计算的校验和与该帧中包含 的校验和不同,则数据链路层知道发生了错误,它就会采取措施来处理错误(比如丢弃坏帧, 可能还会发回一个错误报告)。 拆分比特流成帧的实际工作比初看上去的要困难得多。一个好的设计必须使接收方很 第3章数据链路层159 容易发现新帧的开始,同时使用极少的信道带宽。下面将考察4种成帧方法: (1)字节计数法。 (2)字节填充的标志字节法。 (3)比特填充的标志比特法。 (4)物理层编码例外法。 第一种成帧方法利用帧头中的一个字段标识该帧中的字符数。当目标方的数据链路层 看到字节计数值时,它就知道后面跟着多少字节,因此也就知道了该帧在哪里结束。这项技 术如图3-3(a)所示,其中4个样例帧的大小分别为5字节、5字节、8字节和8字节。 这个方法的麻烦之处在于,字节计数值有可能因为一个传输错误而出错。比如,如果图 3-3(b)中第2帧的字节计数值5由于一个比特反转而变成了7,那么目标方就会失去同步, 然后它再也不能找到下一帧的正确起始位置。即使校验和不正确,目标方知道该帧已经被 损坏,它也无法知道下一帧从哪里开始。在这种情况下,给源方发回一帧要求重传也无济于 事,因为目标方并不知道应该跳过多少字节才能到达重传的开始处。正是由于这个原因,字 节计数法很少被使用。 图3- 3 字节计数 第二种成帧方法考虑了出错之后的重新同步问题,它让每一帧用一些特殊的字节作为 开始和结束。通常同样的字节被用作帧的开始和结束分界符,它被称为标志字节(flagbyte),如图3-4(a)中的FLAG所示。两个连续的标志字节代表了一帧的结束和下一帧的 开始。因此,如果接收方失去同步,它只需搜索两个标志字节就能找到当前帧的结束和下一 帧的开始位置。 然而,这里仍然有问题。有可能标志字节碰巧出现在数据中,尤其是当传输二进制数据 (比如照片或歌曲)时。这种情况将会干扰到帧的分界。解决这个问题的一种方法是,发送 方的数据链路层在数据中“偶尔”出现的每个标志字节的前面插入一个特殊的转义字节 (ESC )。因此,只要看数据中标志字节的前面有没有转义字节,就可以把作为帧分界符的标 志字节与数据中出现的标志字节区分开。接收方的数据链路层在将数据传递给网络层之前 必须删除转义字节。这种技术就称为字节填充(bytestufing)。 当然,接下来的问题就是:如果转义字节也出现在数据的中间,那该怎么办? 答案是同 样用一个转义字节填充。在接收方,第一个转义字节被删除,留下紧跟在它后面的数据字节 160 计算机网络(第6版) (或许是另一个转义字节或者标志字节)。图3-4(b)给出了一些例子。在所有情况下,去掉 填充字节之后递交的字节序列与原始的字节序列完全一致。仍然可以通过搜索并列的两个 填充字节定位一个帧的边界,无须顾虑删除转义字节的事。 图3- 4 字节填充 图3-4中描述的字节填充方案是PPP(Point-to-PointProtocol,点到点协议)中实际使 用的方案经过略微简化后的形式,该协议被用于在通信链路上传送数据包,在Internet上很 常见。在3.1节将讨论PPP 。 5. 第三种成帧方法考虑了字节填充的缺点,即只能使用8比特的字节。帧的划分也可以 在比特级完成,因而帧可以包含由任意大小的单元组成的任意数量的比特。这种方法是为 曾经非常流行的HDLC(High-levelDataLinkControl,高级数据链路控制)协议而开发的。 每个帧的开始和结束由一个特殊的比特模式———01111110 或十六进制0x7E 进行标记。这 一模式是一个标志字节。每当发送方的数据链路层在数据中遇到连续5个1时,它便自动 在输出的比特流中填入一个比特0。这种比特填充类似于字节填充,在数据中的标志字节 之前插入一个转义字节到输出字符流中。比特填充还确保了转换的最小密度,这将有助于 物理层保持同步。正是由于这个原因,USB(UniversalSerialBus,通用串行总线)采用了比 特填充技术。 当接收方看到5个连续到达的比特1,并且后面紧跟一个比特0,它就自动剔除(即删 除)比特0。比特填充和字节填充一样,对两台主机上的网络层是完全透明的。如果用户数 据中包含了标志模式01111110,那么,这个标志传输 出去的是011111010,但在接收方内存中存储的还是 01111110 。上面的层完全不知道传输过程中使用了 比特填充。图3-5给出了一个比特填充的例子。 有了比特填充技术,两帧之间的边界可以由标志 模式毫无歧义地进行区分。因此,如果接收方失去了 它的接收轨迹,它所要做的只是扫描输入比特流,找 出其中的标志序列,因为这些标志只可能出现在帧的 图3-5比特填充 第3章数据链路层161 边界,而绝不会出现在数据中。 采用比特填充和字节填充的一个副作用是一帧的长度现在要取决于它携带的数据内 容。比如,如果数据中没有标记字节,那么,100 字节数据或许被一个大约长为100 字节的 帧所携带。然而,如果数据完全由标志字节组成,那么,每个标志字节都要被转义,帧的长度 将变成大约200 字节。采用比特填充技术,帧的长度增幅大约为12.因为一字节增加一 比特。 5%, 成帧的最后一种方法是使用物理层的一条“近道”。从第2章看到,将比特编码成信号 通常包括一些冗余比特,以便帮助接收器进行同步。这种冗余意味着一些信号将不会出现 在常规数据中。比如,在4B/5B 线路编码模式下,4个数据位被映射成5个信号比特,以确 保信号有足够的比特跳变。这意味着32 个可能的信号中有16 个是不会被使用的。可以利 用这些保留的信号来指示帧的开始和结束,这就是使用“编码例外”(无效字符)来区分帧的 边界。这种方案的优点在于:因为它们是保留的信号,所以很容易找到帧的开始和结束,而 且不需要填充数据。 许多数据链路协议为安全起见组合使用了这些方法。以太网和IEEE802. 11 使用的一 种公共模式是,用一个定义良好的比特模式标识一帧的开始,该比特模式称为前导码 (preamble)。这种模式可能很长(在IEEE802.以便让接收方准备接收到 11 中使用72 位), 达的数据包。前导码之后是帧头的长度字段(即计数), 这个字段将被用来定位帧的结束处。 3.3 错误控制 1. 解决了如何标识每一帧的开始和结束位置以后,现在看下一个问题:如何确保所有的 帧最终都被按照正确的顺序传递了给目的地的网络层? 现在假设接收方可以知道它收到的 帧包含了正确的或者错误的信息(将在3. 2节考察用于检测和纠正传输错误的编码)。对于 无确认的无连接服务,不管发出去的帧是否正确到达,发送方只要把输出的帧留存就可以 了。但是对于可靠的面向连接的服务,这样做肯定还远远不够。 确保可靠传递的常用方法是向发送方提供一些有关线路另一端状况的反馈信息。典型 情况下,协议要求接收方发回一些特殊的控制帧,在这些控制帧中对于它接收到的帧进行肯 定或者否定的确认。如果发送方收到了关于某一帧的肯定确认,那么它就知道这一帧已经 安全地到达了;而否定的确认意味着传输过程中产生了错误,所以这一帧必须重传。 更为复杂的情况是存在这样的可能性:由于硬件的问题导致一个帧被完全丢失了(比 如一个突发噪声)。在这种情况下,接收方根本不会有任何反应,因为它没有理由做出反应。 类似地,如果确认帧丢失,发送方也不知道该如何处理。很显然,如果在一个协议中发送方 发出了一帧以后就等待肯定的或者否定的确认,那么,若由于硬件故障或通信信道出错等原 因而丢失了某一帧,则发送方将永远等待下去。 这种可能性可以通过在数据链路层中引入计时器来解决。当发送方发出一帧时,它通 常还要启动一个计时器。该计时器的超时值要设置得足够长,以便该帧能够到达目的地,并 且在目的地被处理后再将确认传回发送方。一般情况下,在计时器超时前,该帧被正确地接 收,并且确认也被传了回来。在这种情况下,计时器被取消。 然而,如果原始帧或者确认被丢失,则计时器将被触发,从而警告发送方存在一个潜在 的问题。一种显然的解决方案是重新发送该帧。然而,当有的帧被发送了多次时,就会存在 162 计算机网络(第6版) 这样的危险:接收方将两次或者多次接收到同一帧,并且多次将它传递给网络层。为了避 免发生这样的情形,有必要给发送出去的帧分配序号,这样接收方就可以区分原始帧和重 传帧。 管理好计时器和序号,以便保证每一帧最终都恰好被传递给目的地的网络层一次,这是 数据链路层(以及上层)工作的重要组成部分。在本章后面,将通过一系列复杂性逐渐增加 的例子考察这一管理工作是如何完成的。 3.4 流量控制 1. 在数据链路层(以及上层)中,另一个重要的设计问题是:如果发送方总体发送帧的速 度超过了接收方能够接收这些帧的速度,则发送方该如何处理? 当发送方运行在一台高速 并且能力强大的计算机上,而接收方运行在一台慢速并且低端计算机上时,这种情况就可能 发生。一种常见的场景是,一个智能手机向一个服务器请求一个Web页面。这就像突然打 开了消防水阀一样,大量的数据涌向可怜无助的手机,直到它被彻底淹没。即使传输过程不 会出错,接收方也可能无法以数据到来的速度那样快地处理帧,导致一些帧丢失。 很显然,必须采取某种措施阻止这种情况的发生。常用的方法有两种。第一种方法是 基于反馈的流量控制(fedback-basedflowcontrol),接收方给发送方返回信息,允许它发送 更多的数据,或者至少告诉发送方接收方进行得怎么样。第二种方法是基于速率的流量控 制(aebsdfowcnrl), 它能限制发送方传输 rt-aeloto使用这种方法的协议有一种内置的机制, 数据的速率,而无须利用接收方的反馈。 在本章中,将介绍基于反馈的流量控制方案,这主要是因为基于速率的流量控制方案仅 在传输层(第5章)的一部分中可以看到。而基于反馈的流量控制方案则可同时出现在链路 层和更高层上。后者在近来更为常见,在当前情况下,链路层硬件的运行速度足够快,不会 造成丢帧。比如,作为链路层硬件实现的NIC(NetworkInterfaceCard,网络接口卡)有时 能以“线速”运行,这意味着它们能以帧到达链路的速度处理帧。因而,任何过载都不是链路 问题,所以它们必须由高层处理。 基于反馈的流量控制方案有许多种,但是绝大多数使用了同样的基本原理。协议包含 了许多定义良好的规则,这些规则涉及发送方什么时候可以发送下一帧。这些规则通常禁 止发送帧,直到接收方授予许可(隐式或者显式)。比如,当建立一个连接时,接收方可能会 这样说:“你现在可以给我发送 n 个帧,但是在发送完这 n 个帧以后就别再发送,直到我告 诉你可以继续发送。”稍后将讨论这些细节。 3.错误检测和纠正 2 在第2章中介绍了,通信信道有许多不同的特征。有些信道,比如电信网络中的光纤, 其错误率很低,因而很少发生传输错误。但是其他信道,尤其是无线链路和老化的本地回 路,错误率要高出几个数量级。对于这些链路而言,传输错误是常态。从性能的角度来看, 这些错误不能在合理的成本开销内避免。结论是,传输错误非常普遍。我们必须知道如何 处理传输错误。 第3章数据链路层163 网络设计者针对错误处理已经研究出两种基本策略。这两种策略都在发送的数据中加 入冗余信息。一种策略是包含足够多的冗余信息,以便接收方能推断出被发送的数据一定 是什么。另一种策略是包含恰好足够的冗余信息,使得接收方推断出是否发生了错误(而推 断不出是哪个错误),然后接收方可以请求重传。前一种策略使用了纠错码(erorcorectingcode),后一种策略使用了检错码(eror-detectingcode)。使用纠错码的技术通常 也称为前向纠错(ForwardErorCorection,FEC )。 这里的每一项技术都占据着不同的生态位置。在高度可靠的信道上(比如光纤),较为 合算的做法是使用检错码,当偶尔发生错误时只需重传整个数据块。然而,在错误很多的信 道上(比如无线链路),更好的做法是在每一个数据块中加入冗余信息,以便接收方能够计算 出原始的数据块是什么。FEC被用在有噪声的信道上,因为重传的数据块本身也可能像第 一次传输那样出错。 这些编码的一个关键考虑是可能发生的错误类型。无论是纠错码还是检错码都无法处 理所有可能的传输错误,因为提供保护措施的冗余比特很可能像数据比特一样出现错误(从 而削弱了它们的保护作用)。如果对于信道而言冗余比特不同于数据比特,那当然好;但事 实并非如此,对信道而言,它们都是同样的比特。这意味着为了避免未检测到错误,编码必 须强大到足以应付预期的错误。 一种模型是偶尔出现的极端热噪声快速淹没了信号,引起孤立的单个比特错误。另一 种模型是错误往往呈现突发性而不以单个形式出现。这种错误源自产生错误的物理过程, 比如无线信道上的一个深衰减,或者有线信道上的瞬态电气干扰。 两种模型在实践中都很重要,并且有不同的权衡。突发的错误相比孤立的单个比特错 误既有优势也有不足。从优势方面来看,计算机数据总是成块发送的。假设数据块大小为 1000比特,误差率为每比特0.大多数块将包含一个错误。但如果 001 。如果错误是独立的, 错误以100比特的突发形式出现,则平均来说100块中只有一块会受到影响。突发错误的 缺点在于当它们发生时比孤立的单个比特错误更难以纠正。 同时还存在着其他类型的错误。有时候,一个错误的位置可以知道,或许因为物理层接 收到的一个模拟信号远离了0或1的预期值,因而可以声明该比特已丢失。这种情形称为 擦除信道(erasurechannel)。擦除信道中的错误比那些把比特值翻转的信道中的错误更易 于纠正,因为即使某一比特的值被丢失,至少可以知道哪一比特出了错。然而,我们往往不 能从信道的擦除性质上受益。 下面同时考察纠错码和检错码。请记住两点。 首先,在数据链路层讨论这些编码,因为这里是我们面临着可靠传输比特组相关问题的 首要之地。然而,这些编码方案是被广泛使用的,因为可靠性是一个整体要关注的问题。纠 错码在物理层往往也会看到,特别是有噪声的信道,同时还会出现在更高的层上,特别是针 对实时流媒体和内容分发。检错码经常被用在链路层、网络层和传输层。 其次,错误编码是应用数学。除非你特别熟悉伽罗瓦(Galois)领域或稀疏矩阵的性质, 否则,你应该从可靠的来源获得性质优良的编码方法,而不是自己设计编码方法。事实上, 这正是很多协议标准所做的,它们一次又一次采用了同样的编码方法。在下面的内容中,将 详细地介绍一个简单的编码,然后再简要描述先进的编码。这样,就可以从简单编码理解如 何权衡,并且通过先进编码讨论实际使用的编码。 164 计算机网络(第6版) 3.1 纠错码 2. 本节将考察以下4种不同的纠错码: (1)海明码。 (2)二进制卷积码。 (3)里德-所罗门码。 (4)低密度奇偶校验码。 上述所有编码都将冗余信息加入到待发送的信息中。一帧由 m 个数据位(即消息)和 r 个冗余位(即校验位) bokcd中, 组成。在块编码(lcoe) r 个校验位是通过与之相关的 m 个 数据位的函数计算获得的,就好像在一张大表中找到 m 个数据位对应的 r 个校验位。在系 统码(systematiccode)中,直接发送 m 个数据位,然后发出校验位,而不是在发送前对它们 进行编码。在线性码(liecd中, noe) r 个校验位是通过 m 个数据位的线性函数计算出来的。 异或(XOR)运算或模2加是一种很流行的函数,这意味着编码过程可以用诸如矩阵乘法或 简单的逻辑电路完成。除非另有说明,本节中考察的是线性码、系统块编码。 令数据块的总长度为n(即n= m +r)。我们将此描述为(n,m)码。一个包含了数据 位和校验位的 n 位单元称为 n 位码字(codeword)。码率(coderate), 或者简单地称为速率, 则定义为码字中不包含冗余部分所占的比例,或者用m/ n 表示。在实践中码率变化很大。 在一个有噪声信道上码率或许是1/2,在这种情况下接收方收到的信息中有一半是冗余位; 而在高质量的信道上码率接近1,只有少量的校验位被添加到一个大的消息中。 为了理解错误是如何被处理的,有必要先仔细看一看错误到底是什么样的。给定两个 被发送或接收的码字,比如10001001 和10110001,完全可以确定这两个码字中有多少个对 应位是不同的。在这种情况下,有3位不同。为确定有多少个不同的位,只需对两个码字进 行异或运算,并且计算结果中1的个数。比如: 10001001 10110001 00111000 两个码字中不同的位的个数称为海明距离(Hammingdistance)。它的意义在于,如果两个 码字的海明距离为d,则需要 d 个一位错误才能将一个码字转变成另一个码字。 给定计算校验位的算法,完全可以构建一个完整的合法码字列表,然后从这个列表中找 出两个具有最小海明距离的码字。这个距离就是整个编码的海明距离。 在大多数数据传输应用中,所有2m 种可能的数据消息都是合法的;但是,根据校验位 的计算方法,并非所有2n 种可能的码字都会被用到。事实上,当有 r 个校验位时,可能的报 文中只有很少一部分(2m/2n 或1/2r)是合法的码字。正是这种空间稀疏特性,即消息被嵌 入码字空间中,使得接收方能检测并纠正错误。 块编码的检错和纠错特性取决于它的海明距离。为了可靠地检测 d 个错误,需要一个 海明距离为d+1 的编码,因为在这样的编码中, d 个一位错误不可能将一个有效码字改变 成另一个有效码字。当接收方看到一个非法的码字时,它就能判断是发生了传输错误。类 似地,为了纠正 d 个错误,需要一个距离为2d+1 的编码,因为在这样的编码中,合法码字 之间的距离足够远,即使发生了 d 位变化,原来的码字也比任何其他的码字都离错误码字 第3章数据链路层165 最近。这意味着在不太可能有更多错误的假设下,原来的码字就可以唯一确定下来。 看一个纠错码的简单例子,考虑一个只有下列4个有效码字的编码: 0000000000,0000011111,1111100000,1111111111 该编码的距离是5,这意味着它可以纠正2个错误或者检测4个错误。如果接收到码字 0000000111并且期望只有1个或者2个错误,则接收方知道原始的码字一定是 0000011111 。然而,如果发生了3个错误,0000000000变成了0000000111,则以上编码就无 法正确地纠正错误了。另外,如果预期所有这些错误都会发生,那么也可以检测出它们。只 要没有收到合法的码字,就必然发生了错误。很明显,在这个例子中,不能同时纠正2个错 误和检测4个错误,因为这需要以两种不同的方式解释接收到的码字。 在上面的例子中,解码的任务就是找出最接近接收到的码字的合法码字,这可以通过查 找来完成。不幸的是,大多数情况下全部码字都将作为候选被评估,这是一件非常耗时的搜 索。相反,实际的代码通常被设计成允许使用快捷方式找出最有可能的原始码字。 设想要设计一种编码,每个码字有 m 条消息位和 r 个校验位,并且能够纠正所有的单 个错误。对于2m 条合法消息,任何一条消息都对应 n 个距离为1的非法码字。这些非法 码字可以这样构成:将该消息对应的合法码字的 n 位逐个取反,可以得到 n 个距离为1的 非法码字。因此,每2m 条合法消息需要n+1个位模式标识它们。由于总共只有2n 个位模 式,所以,必须有( n 。由于n=m+r,这个要求变成了 n+1)2m ≤2 r ( m +r+1)≤2(3-1) 在给定 m 的情况下,这个条件给出了纠正单个错误所需的校验位数的下界。 事实上,这个理论下限可使用海明方法获得。在海明码(Hammingcodes)中,码字的位 被连续编号,从最左端的位1开始,紧跟在右边的那一位是2,依次从左到右编号。编号为2 的幂(16等)的位是校验位,其余位(9等)用来填充 m 个数据位。这种模 1,2,4,8,3,5,6,7, 式如图3-6所示,其中有7个数据位和4个校验位。每一个校验位强制进行模2加,或对某 些位的集合,包括其本身进行偶(或奇)校验。一位可能被包括在几个校验位的计算中。若 要查看在数据 k 位上的校验位,必须将 k 改写成2的幂之和。比如,11=1+2+8和29= 1+4+8+16 。校验某一位时,只需要检查那些覆盖了该位的校验位(比如,校验1、2和8位 就可确定11位是否出错)。在图3-6所示的例子中,采用偶校验计算一个只包含ASCI 码 字母A的消息的校验和。 图3- 6 纠正一位错误的(11,7)海明码示例 这种结构给出了海明距离为3的编码,意味着它可以纠正单个错误(或检测两个错误)。 针对消息位和校验位小心编号的原因在解码的处理过程中表现得非常明显。当接收到一个 码字时,接收方重新计算其校验位,包括接收到的校验位的值。得到的计算结果称为校验结 166 计算机网络(第6版) 果。如果校验位是正确的,对于偶校验和而言,每个校验结果应该是0。在这种情况下,码 字才被认为是有效的,从而可以被接受。 然而,如果校验结果不是全0,则意味着检测到一个错误。校验结果的集合形成的错误 综合集,可用来查明和纠正错误。在图3-6中,信道上发生了一位错误,因此分别针对k= 8、4、2、1的校验结果是0、1、0和1。由此得出的综合集为0101或4+1=5。按照设计方 案,这意味着第5位是错误的。把不正确的位(这可能是一个校验位或数据位)取反,并丢弃 校验位,就得到正确的消息———ASCI 码字符A。 海明距离对理解块编码是有价值的,而且海明码还被用在纠错内存中。然而,大多数网 络使用了更强大的编码。本节考察的第二个编码是卷积码(convolutionalcode),这是本节 讨论的编码方法中唯一不属于块编码的编码。在卷积码中,编码器处理一个输入位序列,并 生成一个输出位序列。它不像块编码,没有自然消息大小或编码边界,输出取决于当前的输 入和以前的输入,也就是说编码器有内存。决定当前输出的以前的输入位数称为该编码的 约束长度(constraintlength)。卷积码由它们的速率和约束长度标识。 卷积码已被广泛应用于实际部署的网络中。比如,它已经成为GSM移动电话系统的 一部分,在卫星通信和IEEE802.图37给出了一个流行 11中都得到应用。作为一个例子, k= 的卷积码。其r=1/2,7。这个代码称为NASA(美国航天局)卷积码,因为它是第一个 被用在1977年的旅行者号航天飞行任务中的编码。从那以后,它被随意重用于许多其他地 方,比如, 11的一部分。 它已成为IEEE802. 图3- 7 应用于IEEE802. 11的NASA 卷积码 在图3-7中,左边的每个输入位产生右边的两个输出位,输出位是输入位和内部状态的 异或之和。由于它处理的是比特并执行线性运算,因此是二进制的线性卷积码。又因为它 的一个输入产生两个输出,因此其码率为1/2。这里的输出位不是简单的输入位,从而它不 属于系统码。 NASA卷积码的内部状态保存在6个内存寄存器中。每当输入一位时,寄存器的值就 右移一位。比如,如果输入序列为111,初始状态是全0,则在输入第一、第二和第三位后从 左到右的内部状态变成100000 、110000和111000,对应的输出位分别是11 、10和01 。这个 过程需要7次移位才能完全清空输入,从而不影响输出,因此该卷积码的约束长度是k=7。 卷积码的解码过程是找出最有可能产生观察到的输出位序列(包括任何错误)的输入位 序列。对于较小值的k,一种广泛使用的算法是由Viterbi开发的(Forney,1973 )。该算法 逐个检查观察到的序列,记住每一步和输入序列的每个可能内部状态,即以最少的错误产生 观察到的序列对应的输入序列。最终,那个具有最少错误的输入序列就是最有可能的消息。 卷积码在实践中已经非常流行,因为它很容易将一位为0或1的不确定性化解成解码 第3章数据链路层167 过程。比如,假设-1V表示逻辑0,+1V表示逻辑1,接收方可能接收到的2位分别是 0.0.而是把0.很可 9V和-1V 。卷积码不是简单地将这些信号映射成逻辑1和0, 9V看成“ 能是1”把-1V看成“”从而整体上纠正这一序列。Vieb , 0.很可能是0, tri算法的扩展可以 处理这些不确定因素,因而能提供更强的纠错功能。这种带有一位不确定性的工作方法称 为软判决解码(soft-decisiondecoding);相反,在执行纠错之前就决定了每一位是0或1的 工作方法称为硬判决解码(hard-decisiondecoding)。 本节将描述的第三种纠错码是里德-所罗门码(Red-Solomoncode)。像海明码一样, 里德-所罗门码是线性块编码,而且往往也是系统码。但与海明码不同的是,里德-所罗门码 对 m 位符号进行操作,而不是针对单独的位进行操作。当然,这里涉及更多的数学内容,因 此下面将用类比的方式描述它们的操作。 里德-所罗门码基于这样的事实:每一个 n 次多项式是由n+1个点唯一确定的。比 如,一条具有ax+ b 形式的线由两个点决定。同一条线上的额外点都是冗余的,这将有助 于纠错。可以想象用两个数据点代表一条线,并且发送这两个点,再加上这条线上的额外两 个校验点。如果收到的其中一个点出现错误,仍然可以通过接收点的拟合线恢复这个数据 点。其中3个点将处在同一条线上,而出错的那个点不在这条线上。只要找到这条线,就可 以纠正错误。 里德-所罗门码实际上被定义成一个在有限域上操作的多项式,但工作方式类似。对 于 m 位符号而言,码字长是2m -1个符号。一种流行的选择是 m =8,这样符号就是字节。 因此,一个码字为255字节长。(255,233)码被广泛使用,它在233个数据符号上增加了22 个冗余符号。带有纠错功能的解码算法由Berlekamp和Masey开发,它能有效地执行中 等长度的解码任务(Masey,1969 )。 里德-所罗门码在实践中得到了广泛的应用,这是由于其具有强大的纠错性能,尤其是 针对突发错误。它们被用在DSL 、线缆上的数据通信、卫星通信以及可能无处不在的CD 、 DVD和蓝光光盘。因为它们基于 m 位符号,因此一位错误和 m 位突发错误都只是作为一 个出错的符号对待。当加入2t 个冗余符号后,里德-所罗门码能够纠正传输符号中的任意 t 个错误。比如,在(255,233)码中,由于有32个冗余符号,因此可以纠正多达16个符号错 误。因为符号是连续的,并且每个8位长,所以可以纠正高达128位的突发错误。如果错误 模型是擦除的(比如,一张CD上的划痕消除了一些符号),则情况更好。在这种情况下,高 达2t 个错误可以得到纠正。 里德-所罗门码通常与其他编码(如卷积码)结合在一起使用。这种想法的依据在于: 卷积码在处理孤立的比特错误时很有效;但如果接收到的比特流中有太多的错误,可能与突 发错误类似,那么,卷积码就无法处理了。通过在卷积码内加入里德-所罗门码,里德-所罗 门码可以纠正突发错误,因此两者的结合就能将纠错任务完成得非常好。综合起来的编码 对单个错误和突发错误都有很好的处理效果。 本节考察的最后一个纠错码是LDPC(Low-DensityParityCheck,低密度奇偶校验)码。 LDPC码是线性块编码,由RobertGalagher在他的博士论文中首次提出(Galagher, 1962 )。像大多数学位论文一样,它很快被人遗忘了,直到1995年计算能力的进步使得它可 以实用化的时候才被重新发明并进入实际应用。 在LDPC码中,每个输出位由一小部分的输入位形成。这使得编码可以用一个1的密 168 计算机网络(第6版) 度很低的矩阵来表示,这也是该编码名称的由来。接收到的码字通过一个近似算法解码,该 算法通过迭代不断改进接收到的数据与合法码字的最佳匹配,以此纠正错误。 LDPC 码比较适用于大块数据,而且具有出色的纠错能力,因而性能优于其他许多实践 中的编码(包括本节前面考察过的那些)。正是基于这个原因,它迅速被包含到新的协议中, 成为数字视频广播、10Gb/电力线网络以及最新版本IEEE802. s以太网、11 标准的一部分。 期待在未来的网络中看到更多的LDPC 码。 3.2 检错码 2. 纠错码被广泛应用于无线链路。众所周知,相比光纤,无线链路嘈杂不堪而且容易出 错。如果没有纠错码,将很难从无线链路获得任何信息。然而,对于光纤或高质量铜线,错 误率要低得多,所以,对于偶尔出现的错误,采用错误检测和重传的处理方式通常更加有效。 本节将考察3种检错码。这些检错码都是线性的系统块编码: (1)奇偶校验位。 (2)校验和。 (3)循环冗余校验码。 为了看清楚检错码如何比纠错码更有效,考虑第一种检错码———把单个奇偶校验位 (paritybit)附加到数据上。奇偶校验位的选择原则是使得码字中比特1的数目是偶数(或 奇数)。这样处理等同于对数据位进行模2加或异或运算来计算奇偶校验位。比如,当以偶 校验方式发送1011010 时,在数据末尾添加一位,成为10110100;当以奇校验方式发送 1011010 时,则结果为10110101 。具有单个校验位的编码具有码距2,因为任何一位错误都 将使得码字的奇偶校验位出错。这意味着奇偶校验码可以检测出一位错误。 考虑这样的信道:其上发生的错误都是孤立的,并且每一比特的错误率是10-6。这个 看似微小的错误率对长距离的线缆已经是最好的条件了。典型的LAN 链路的比特错误率 大约为10-10 。令数据块大小为1000b 。为了针对1000b 的数据块提供纠错功能,根据 式(3-1)可知需要10 个校验位。因此1Mb 的数据块将需要10000 个校验位。如果只为检 测出该块数据中存在的一位错误,那么,每个数据块仅一个校验位就足够了。如此一来,每 1000 个数据块中才有一块出现错误,只需要重传额外的一块(1001 位)即可修复错误,每 1Mb 数据用于错误检测和重传的总开销只有2001 位。相比之下,海明码需要10000 位。 这种方案的一个困难在于单个校验位只能可靠地检测出数据块中的一位错误。如果数 据块因一个长的突发错误造成严重乱码,那么这种错误被检测出来的概率只有0.这显然 5, 是令人难以接受的。如果将发送的每个数据块视为一个 n 位宽和 k 位高的矩阵,则检测出 错误的概率可望得到很大提高。现在,如果为每一行计算和发送一个奇偶校验位,那么,只 要每一行最多只有一个错误发生,就能可靠地检测出最多 k 位错误。 然而,还可以用以下方法提高针对突发错误的更好保护:可以以不同的顺序计算数据 的校验位,即以不同于通信信道上数据位发送的顺序计算校验位。这种处理方式称为交错 校验(g)。在这种情况下,将为 n 列中的每一列计算校验位,按 k 行发送全部的 interleavin 数据位。发送顺序是:从上到下发送每一行,行内数据位通常按从左到右的顺序发送。在 最后一行,发送 n 个校验位。这种校验的示例如图38所示, 7,7。 -其中n=k= 交错校验是一种将检测(或纠正)孤立错误的编码转换成能检测(或纠正)突发错误的编 第3章数据链路层169 图3- 8 检测一个突发错误的交错校验 码的通用技术。在图3-8中,当发生一个长度为n=7的突发错误时,出错的位恰好分散在 不同的列(突发错误并不隐含着所有的位都出错;它只意味着至少第一位和最后一位错误。 图3-8所示的4个奇偶校验位错误分布在7位范围内)。 n 列中的每一列至多只有一位受 到影响,因此这些列中的校验位将能检测到该错误。这种方法对于kn 位的数据块使用 n 个奇偶校验位就能检测出一个长度小于或等于 n 的突发错误。 然而,如果第一位和最后一位被反转,所有其他位都正确,那么,这样一个长度为n+1 的突发错误将被遗漏。如果数据块被一个长突发错误或多个短突发错误扰乱,那么,这 n 列中任何一列偶尔有正确校验位的概率是0.所以一个不该接受而被接受的坏块的概率 5, 是2- n 。 第二种检错码称为校验和(checksum), 它与一组奇偶校验位密切相关。校验和这个词 通常用来指与一条消息相关联的一组校验位,不管这些校验位是如何计算出来的。一组奇 偶校验位是校验和的一个例子。然而,还有其他更强的校验和,它们以利用消息中的数据位 进行求和计算为基础。校验和通常放置在消息的末尾,作为求和函数的补充。这样一来,通 过对整个接收到的码字(包含了数据位和校验和)进行求和计算就能够检测出错误。如果计 算结果是0,则没有检测出错误。 校验和的一个例子是16 位的Internet校验和,它作为IP 协议的一部分用在所有 Internet数据包中(Braden等,1988 )。该校验和是把消息的位分成16 位字的求和结果。由 于此方法针对字而不是像奇偶校验那样针对位进行操作,所以,不改变奇偶性的错误此时仍 然会影响求和值,从而能被检测出来。比如,如果两个不同字的最低位都从0错误地翻转为 1,跨越这些位的奇偶校验将无法检测到这个错误;然而,两个1增加到16 位校验和中将产 生不同的结果,于是这个错误就能被检测出来。 Internet校验和是以1的补码运算而非216 模加运算得到的。在1的补码运算中,负数 是其正数的按位补。现代计算机正常采用的是2的补码运算,负数是1的补码加1。在一 台采用2的补码运算的计算机中,1的补码和等价于模216 求和,并且将高阶位的任何溢出 加到低阶位上。该算法为校验和位提供了更均匀的数据覆盖面。否则,两个高阶位可能因 相加、溢出而被丢失,没有改变求和结果。该算法还有另一个好处。对于0、1的补码有两种 表示方法:全0和全1。这就允许用一个值(比如全0)表示没有校验和,而不需要用另外一 个字段。 几十年来,人们一直有这样的假设,即计算校验和时针对的帧包含了随机的位。校验和 170 计算机网络(第6版) 算法的所有分析都是基于这样的假设进行的。由Partridge等(1995)检查的真实数据表明 这种假设是十分错误的。因此,在有些情况下未检测到的错误比以前想象得更多。 尤其是Internet校验和,它有效而简单,但在有些情况下提供的保护很弱,正是因为它 只是一个简单的求和。它检测不出0数据的增加或删除,也检测不出消息中被交换的那部 分,而且对于由两个数据包中的部分拼接起来的消息只有弱保护作用。这些错误在随机过 程中似乎不太可能发生,但恰恰是有可能发生在有缺陷的硬件上的错误。 一个更好的选择是Fletcher校验和(Fletcher,1982 )。它包括一个位置,将数据和其位 置的乘积添加到校验和中。这样能对数据位置的变化提供更强的检测作用。 尽管前面两种检错码对高层而言有时候可能已经足够,但实际上,链路层广泛使用的是 第三种更强的检错码———CRC(CyclicRedundancyCheck,循环冗余校验)码,也称为多项式 编码(polynomialcode)。其基本思想是将位串看成系数为0或1的多项式。一个 k 位帧看 作一个 k 项多项式的系数列表,此 k 项从xk-1到x0。这样的多项式被看作k-1阶多项式。 最高(最左边的)位是xk-1项的系数,接下来的位是xk-2项的系数,以此类推。比如,110001 有6位,因此代表一个有6项的多项式,其系数分别为1、1、0、0、0和1,即1x5+1x4+0x3+ 0x2+0x1+1x0。 多项式的运算遵守代数域理论的规则,以2为模完成。加法没有进位,减法没有借位。 加法和减法都等同于异或运算。比如: 10011011 00110011 11110000 01010101 -11001010 +11001101 -10100110 -10101111 01010001 11111110 01010110 11111010 长除法与二进制中的除法运算一样进行,只不过减法按模2进行。如果被除数与除数有一 样多的位,则该除数要“进入”被除数中。 当使用多项式编码时,发送方和接收方必须预先商定一个生成多项式(generator polynomial)记为G(x)。生成多项式的最高位和最低位必须是1。假设一帧有 m 位,它对 应于多项式 M (x), 为了计算它的循环冗余校验码,该帧必须比生成多项式长。基本思想 是,在帧的尾部附加一个校验和,使得附加校验之后的帧代表的多项式能够被G(x)除尽。 当接收方收到了带校验和的帧以后,它试着用G(x)去除它。如果有余数,则表明存在传输 错误。 计算循环冗余校验码的算法如下: (1)假设G(x)的阶为r。在帧的低位端加上 r 个0,使得该帧现在包含m+ r 位,对应 的多项式为xrM ()。 (2)利用模2 法,用对应于G(x)的位串去除对应于xrM (x)的位串。除(x) (3)利用模2减法,从对应于xrM (x)的位串中减去余数(总是小于或等于 r 位)。结 果就是将被传输的带校验和的帧。称它的多项式为T(x)。 图3-9显示了采用生成多项式为 G (x)=x4+x+1 计算帧1101011111 校验和的 情形。 T(x) x) 显然,可以被G(除尽(模2)。在任何除法问题中,如果将被除数减掉余数,则 剩下的差值一定可以被除数除尽。比如,在十进制中,如果210278 被10941 除,则余数为 2399 。于是,如果从210278 中减去2399,则得到的207879 可以被10941 除尽。 第3章数据链路层171 图3- 9 循环冗余校验码计算示例 现在分析这种方法的能力。什么样的错误能被检测出来? 想象一下发生了一个传输错 误,因此接收方收到的不是T(x), 而是T(x)+E(x)。E(x)中对应的每个1都变反了。 如果E(x)中有 k 个1,则表明发生了 k 个一位错误。单个突发错误可以这样描述:初始位 是1,然后是k-2个0和1,最后一位也是1,所有其他位都是0。 接收方在收到了带校验和的帧以后,用G(x)除它;也就是说,接收方计算[ T (x)+ E(xx) x)/G(是0, x)/G()。如果这些错误对应的多 x)]/G()。T(x) 因此计算结果简化为E( x 项式恰好以G(为因子,那么,这些错误就会被遗漏;所有其他的错误都可以被捕捉到。 如果只有一位发生错误,即E(x)=xi,这里 i 决定了哪一位发生了错误。如果G(x) 包含两项或者更多项,则它永远也不会除尽E(x), 所以,所有的一位错误都将被检测到。 如果有两个独立的一位错误,则E(x)=xi+xj ,这里i>j。换一种写法,E(x)可以写 成E(x)=xj(xi- j +1 )。如果假定G(x)不能被 x 除尽,则所有的两位错误都能够检测出 来的充分条件是:对于任何小于或等于i- j 最大值(即小于或等于最大帧长)的 k 值, G(x)都不能除尽xk +1 。简单地说,保护长帧的低阶多项式是已知的。比如,对于任何 k<32768,x15+x14+1 都不能除尽xk +1 。 如果有奇数个位发生了错误,则E(x)包含奇数项(比如x5+x2+1,但不能是x2+1 )。 有趣的是,在模2系统中,没有一个奇数项多项式有x+1 因子。通过将x+1 作为G(x)的 一个因子,就可以捕捉到所有包含奇数个位变反的错误。从统计学角度,这样就可以捕捉到 一半的错误。 最后,也是最重要的,带 r 个校验位的多项式编码可以检测到所有长度小于或等于 r 的 突发错误。长度为 k 的突发错误可以用xi(xk-1+xk-2+…+1)表示,这里 i 决定了突发错 误的位置离帧的最右端的距离。如果G(x)包含一个x0 项,则它不可能有xi 因子,所以, 如果括号内表达式的阶小于G(x)的阶,则余数永远不可能为0。 172 计算机网络(第6版) 如果突发错误的长度为r+1,则当且仅当突发错误与G(x)一致时,错误多项式除以 G(x)的余数才为0。根据突发错误的定义,第一位和最后一位必须为1,所以它是否与 G(x)匹配取决于其他r-1个中间位。如果所有的组合被认为是等概率的,则这样一个不 正确的帧被当作有效帧接受的概率是1/2r-1。 同样可以证明,当一个长度大于r+1 位的突发错误或者几个短突发错误发生时,一个 坏帧通过检测的概率为1/2r ,这里假设所有的位模式都是等概率的。 一些特定的多项式已经成为国际标准。其中一个作为以太网的例子被用于IEEE802 中,该多项式为 x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1 除了其他期望的特性以外,循环冗余检验码还有一个特性:能检测到长度小于或等于 32 的所有突发错误以及影响到奇数个位的全部突发错误。20 世纪80 年代以后它已被广泛 使用。但是,这并不意味着它是最好的选择。Castagnoli等(1993)和Koopman(2002)采用 穷尽计算搜索,发现了更好的一些循环冗余检验码。这些循环冗余检验码针对典型消息长 度的海明距离为6,而IEEE 标准的CRC-32 的海明距离只有4。 虽然计算循环冗余检验码所需的运算看似很复杂,但在硬件上通过简单的移位寄存器 电路很容易计算和验证循环冗余检验码(Peterson等,1961 )。更新、更快的实现也被提出了 (Mitra等,2017 )。在实践中,几乎总是会用到硬件。数十种网络标准包含了各种各样的循 环冗余检验码,包括几乎所有的LAN(如以太网、IEEE802.和点到点链路(如SONET 上的数据包)。 11) 3.基本数据链路层协议 3 为了引入关于协议的主题,本节先从3个复杂性逐渐增加的协议开始。在考察这些协 议以前,先对底层的通信模型做一些假设是非常有用的。 3.1 初始的简化假设 3. 独立进程。首先,假设物理层、数据链路层和网络层都是独立的进程,它们通过来回传 递消息进行通信。图3-10 给出了这3层的通用实 现。物理层进程和数据链路层进程的一部分运行在 一个称为NIC(NetworkInterfaceCard,网络接口 卡)的专用硬件上。数据链路层进程的其他部分和 网络层进程作为操作系统的一部分运行在主CPU 上。数据链路层进程的软件通常以设备驱动程序的 形式存在。然而,其他的实现也是有可能的(比如, 把3个进程卸载到一个称为网络加速器的专用硬件 上运行,或者3个进程基于一个软件定义的无线电设 施运行在主CPU 上)。实际上,首选的实现方式随 着以大约10 年为周期的技术演变而发生变化。无论如何,将这3层作为独立的进程,可以 图3-10物理层、数据链路层和 网络层的通用实现 第3章数据链路层173 在讨论中使概念更加清晰,同时也有助于强调这些层的独立性。 单向通信。第二个关键的假设是主机A希望用一个可靠的、面向连接的服务向主机B 发送一个长数据流。以后再考虑B同时也想向A发送数据的情形。假定A有无限的数据 已经准备好要发送,不必等待这些数据被生成出来。或者说,当A的数据链路层请求数据 时,网络层总能够立即满足(这个限制后面也将被去掉)。 可靠的机器和进程。第三个假设是主机不会崩溃。也就是说,这些协议只处理通信错 误,不处理因为主机崩溃和重新启动而引起的问题。 在涉及数据链路层时,从网络层通过接口传递到数据链路层的数据包是纯粹的数据,它 的每一位都将被递交到目标主机的网络层。目标主机的网络层可能会将数据包的一部分解 释为一个头,这样的操作不属于数据链路层的考虑范围。 3.2 基本的传输和接收 3. 在发送方,当数据链路层从网络层接收了一个数据包,它就在数据包前后增加一个数据 链路层头和尾,把数据包封装到一个帧中(见图3-1)。因此,一个帧由一个内嵌的数据包、 一些控制信息(在帧头)和一个校验和(在帧尾)组成。然后,该帧被传输到另一台主机上的 数据链路层。假设有一个现成合适的代码库,其中过程t_phyialefrom_ osclar发送一帧, physical_layer接收一帧。这些过程负责计算和附加校验和,并检查校(_) y 验和(这部分工作通 常由硬件完成),所以我们无须关心本节数据链路层协议的这部分内容。比如,它们或许会 用到3.2节讨论的CRC算法。 2. 刚开始时,接收方什么也不做。它只是静静地等待着某些事情的发生。在本章给出的 示例协议中,用过程调用waitforevent(&event)指示数据链路层正在等待事情发生。只 有当确实发生了什么事情(比如(_) 一个(_) 帧到达),该过程才返回。该过程返回时,变量event说 明究竟发生了什么。对于本节要讲述的各个协议,可能的事件集合有所不同,后面将会对每 个协议单独进行定义。请注意,在一个更加实际的环境中,数据链路层不会像上面所说的那 样在一个严格的循环中等待事件,而是会接收一个中断;中断将使它终止当前正在做的无论 什么工作,转而处理进来的帧。然而,为了简便起见,这里忽略数据链路层内部所有并发进 行的活动细节,假定它全部时间都在处理本节讨论的这条信道。 当一帧到达接收方,接收方计算校验和。如果帧内的校验和不正确(即发生了传输错 误),则数据链路层会收到通知(event=cksum_er);如果到达的帧没有受到任何损坏,数 据链路层也会收到通知(event=framearival),因此它可以利用from_physicallayer过程 得到该帧,并对其进行处理。只要接收方(_) 的数据链路层获得了一个完好无损的帧,(_) 它就检查 头部的控制信息。如果一切都没有问题,它就将数据包部分传递给网络层。无论在什么情 况下,帧头部分的信息都不会被交给网络层。 为什么网络层永远得不到任何帧头的信息? 这里有一个很好的理由:要保持网络层和 数据链路层完全分离。只要网络层对数据链路层协议或者帧格式一无所知,那么,数据链路 层协议和帧格式可以在网络层软件不作任何改变的情况下发生变化。每当一块新NIC被 安装到计算机上时这种情况就会发生。在网络层和数据链路层之间提供一个严格的接口可 以极大地简化设计任务,因为不同层上的通信协议可以独立地进化。 图3-11给出了后面要讨论的许多协议公用的声明(C语言)。这里定义了5个数据结 174 计算机网络(第6版) 构:boolean、seq_nr、packet、frame_kind和frame 。boolean是一个枚举类型,可以取值true 和false。seqnr是一个小整数,用来对帧进行编号,以便可以区分不同的帧。这些序号从0 开始,一直到((_) 含)MAX_SEQ,每个需要用到序号的协议都要定义MAX_SEQ 。packet是同 一台主机上网络层和数据链路层之间或者网络层对等体之间交换的信息单元。在本节的模 型中,它总是包含MAX_PKT 字节;但在实际的环境中,它应该是可变长度的。 图3本书许多协议公用的声明,位于ph文件中 -11 rotocol. 一个frame 由4个字段组成:kind、seq、ack和info,其中前3个包含了控制信息,最后 一个可能包含了要被传输的实际数据。这些控制字段合起来称为帧头(r)。 frameheade kind字段指明了帧中是否有数据,因为有些协议区分只有控制信息的帧以及同时包含 控制信息和数据的帧。seq和ack分别用作序号和确认,后面还会详细描述它们的用法。数 据帧的info字段包含了一个数据包;控制帧的info字段没有用到。一个更加实际的协议实 现将会使用一个可变长度的info字段,而对于控制帧则完全忽略。 再次强调,理解数据包和帧之间的关系非常重要(见图3-1)。网络层从传输层获得一 第3章数据链路层175 条消息,然后在该消息前面增加一个网络层头,就构建了一个数据包。该数据包被传递给数 据链路层,被包含在输出帧的info字段中。当该帧到达目标主机时,数据链路层从帧中提 取出数据包,将数据包传递给网络层。以这样的工作方式,网络层就好像机器一样可以直接 交换数据包。 图3-11 还列出了许多过程。这些过程的细节与具体实现有关,它们的内部工作机制 不是接下来的讨论中需要关心的。前面已经提过,wait_forevent() 是一个严格的循环过 程,它等待有事情发生。tonetworklayer() 和from_network(_) layer() 被数据链路层分别用来向网络层传递数据包以(_) 及从网(_) 络层接收数据包。注意,f(_) rom_physicallayer() 和 to_physical_layer() 在数据链路层和物理层之间传递帧。换句话说,to_network(_) layer() 和 from_network_layer() 处理第二层和第三层之间的接口,而from_physical_la(_) yer() 和 to_physical_layer() 则处理第一层和第二层之间的接口。 在大多数协议中,假设信道是不可靠的,并且偶尔会丢失整个帧。为了能够从这种灾难 中恢复过来,发送方的数据链路层每发出一帧就必须启动一个内部计时器或者时钟。如果 在预设的特定时间间隔内没有收到应答,则计时器超时,数据链路层会收到一个中断信号。 在本节讨论的协议中,这个过程是这样处理的:让过程wait_for_event() 返回event= timeout。过程start_timer() 和stop_timer() 分别打开和关闭计时器。只有当计时器在运 行时,也就是在调用stop_timer() 之前,超时事件才有可能发生。在一个计时器运行的同 时,允许显式地调用starttimer(); 这样的调用只是重置计时器,等到再经过一个完整的时 钟间隔之后引发下一次超时(_) 事件(除非它再次被重置或者被关闭)。 过程startacktimer() 和stop_ack_timer() 控制一个辅助计时器,该计时器被用于在特定条件下产生(_) 确认。(_) 过程enablenetworklayer() 和disablenetworklayer() 用在更为复杂的协议中,在这 样的协议中,不再(_) 假设网络(_) 层总是有数据包要(_) 发送。当(_) 数据链路层启用了网络层时,网络层 才允许在有数据包要发送时中断数据链路层,用event=network_layer_ready指示这一点。 当网络层被禁用时,它不会引发这样的事件。通过非常谨慎地设置何时启用网络层以及何 时禁用网络层,数据链路层就能防止网络层用大量的数据包把自己淹没,避免耗尽所有的缓 冲区空间。 帧序号总是落在从0到MAX_SEQ(含)的范围内,对于不同的协议,MAX_SEQ 不相 同。通常有必要对序号递增(加1)并按循环进行处理(即MAX_SEQ 之后是0)。宏inc可 以执行这项序号递增操作。它之所以被定义成宏,是因为在关键路径上它可以被内联使用。 正如后面将会看到的那样,限制网络性能的因素通常在于协议处理过程,所以把这种简单操 作定义成宏(相对于定义成过程)并不会影响代码的可读性,却能够提高性能。 图3-11 中的声明是下面将要讨论的每个协议的一部分。为了节省空间和方便引用,它 们被提取出来列在一起,但从概念上讲,它们应该与协议本身合并在一起。在C语言中,这 一合并过程是这样完成的:把这些定义放在一个特殊的头文件中,这里是pooo.然后 在协议文件中使用C语言预处理器的#include功能将这些定义包含进来。 rtclh, 3.3 简单的数据链路层协议 3. 本节将介绍3个简单的协议,后两个协议都比上一个协议能够处理一种更加实际的