数据链路层

第三章 数据链路层

数据链路层主要解决相邻两个节点间的通信问题，它负责将源节点网络层上的数据传输到目的节点的网络层上。所谓相邻是指两个节点通过一条物理信道直接相连。

1． 数据链路层的设计问题

按照网络的分层模型，每一层都是要利用其下层提供的服务来为其上层提供服务。数据链路层从物理层获得的服务是原始的比特流传输服务，而比特流在传输的过程中是会出错的，因此检测和纠正这些错误使得网络层可以不用关心传输错误，成为数据链路层的一项重要工作。其次较高的发送速度和较低的接收能力的不匹配，也是造成传输出错的一个原因，因此流量控制也是数据链路层的一项重要工作。另外，不同的应用或者传输环境可能要求不同的链路层服务，因此链路层应该有多种服务供上层选择，且每种服务有定义良好的接口供上层调用。

综上所述，数据链路层的主要功能（或者说主要设计问题）包括以下三个方面：

 为网络层提供良定义的服务接口；

 处理传输错误；

 流量控制。

服务类型

可以让数据链路层提供多种不同的服务，但大多提供以下三种服务：

 无确认的无连接服务：源节点向目的节点发送独立的帧，传输前不需要建立逻辑连接，传输后也不要求目的节点进行确认，也就是说不保证每个帧能被正确接收。目的节点可能会将出错的帧丢弃，但不会通知源节点，也不会试图发现是否有帧丢失，传输错误的恢复依靠高层协议去完成。这类服务适用于误码率非常低的传输环境及一些实时业务，大多数局域网使用这一类服务。

 有确认的无连接服务：传输前不需要建立逻辑连接，但目的节点对于收到的每个帧都必须单独进行确认（肯定或否定），出错或丢失的帧需要重发，直到正确接收为止。这类服务适用于误码率较高的传输环境，如无线传输环境。（事实上，要求确认在这儿是一种优化传输服务的选项，而不是必需的。）

 有确认的面向连接的服务：传输前需要建立逻辑连接，为每个发送的帧建立帧编号并按序发送，目的节点对收到的帧进行检错和确认，出错或丢失的帧需要重发直至正确接收为止，目的节点的链路层保证向其网络层递交正确有序的数据流。

通过图 3-3看一下数据链路层协议在路由器中的位置。

组帧

我们考察四种方法

 字符计数法：在帧的第一个字段携带帧的长度。这种方法在帧传输出错后无法恢复同步，因此不能单独使用。

 带有字节填充的标志字节法：使用特殊的字节（标志字节）来表示帧的开始与结束，当失去同步后，只需要搜索特定的标志字节就可以了，如图3-5(a)。为避免在帧的其它部分出现与标志字节相同的比特模式，采用了字节填充的方法，即在与特殊字符具有相同比特模式的字符前插入转义字符ESC，如图3-5(b)。这种方法要依赖于特定的字符编码集，灵活性差，处理开销大。

 带有比特填充的起止标志法：使用一个特殊的比特模式（01111110）作为帧的起始与结束标志。为避免在帧的其它部分出现与此标志相同的比特模式，采用了比特填充的方法，即在5个连续的1后插入一个0，如图3-6。这种方法不依赖于特定的字符编码集，灵活性强，处理简单（使用硬件完成）。

 物理层编码违例法：这种方法只适用于那些在物理层编码中使用冗余技术的网络，例如以太网的物理层采用曼彻斯特编码，它将比特“1”表示成高-低电平对，将比特“0”表示成低-高电平对，而高-高电平对和低-低电平对在编码中没有使用，这样可以用这两种无效的编码标识帧的边界。

差错控制

差错控制的主要内容包括：差错编码、反馈重传、超时重传、重复帧丢弃、定时器管理等。

流量控制

基于反馈的流量控制机制。

2. 差错检测与纠正

出错的类型：单个错（single error）与突发错（burst error）。单个错通常由随机的信道热噪声引起，一次只影响1位，错误之间没有关联。突发错通常由瞬间的脉冲噪声引起，一次影响许多位，用突发长度表示突发错影响的最大数据位数。在实际的通信中，经常发生的错误是突发错。突发错有利于数据传输，但不利于检测和纠正。

差错编码的类型：检错码（error-detecting code）与纠错码（error-correcting code）。检错码只能检测到数据传输发生了错误，但不知道错在哪一位上，因此无法自行纠正错误，需要与反馈重传结合起来使用。纠错码能够知道错误发生在哪一位上，因此能够自行纠正错误。当信道条件允许时，通常采用检错码与反馈重传来检测和纠正错误。

如何检测和纠正错误？

长度为m比特的数据（或称消息）加上r比特的冗余（或称校验位）形成长度为n=m+r比特的码字（codeword）。两个码字的不同位的个数称为这两个码字之间的海明距离d（Hamming Distance），它意味着需要d个位的错误才有可能使一个码字变为另一个码字。在大多数传输应用中，所有2m个可能的数据信息都是有效的，当计算校验位的方法确定后，就可以构造出完整的有效码字表（共2m个有效码字）。但长度为n的码字集中共有2n个码字，显然其中2n-2m个码字是无效的，它们只可能在传输发生错误时出现。因此，判断是否出现传输错误的方法就是判断收到的码字是否是无效码字，而纠错码纠正错误的方法就是将收到的无效码字恢复到距其最近的有效码字，显然任何检错和纠错的方法都有一定的漏检概率。

编码集的检错与纠错能力

编码集的海明距离：编码集中任意两个有效码字间的海明距离的最小值。

编码集的检错和纠错能力与编码集的海明距离有关。为检测出d比特错误，编码集的海明距离至少应为d+1，奇偶校验是能够检测出1比特错误的检错码。为纠正d比特错误，编码集的海明距离至少应为2d+1，海明码是能够纠正1比特错误的纠错码。

循环冗余码（CRC码） 这是一种多项式编码，它将位串看成是系数为0或1的多项式。

信息多项式M(x)：由m个信息比特为系数构成的多项式。

冗余多项式R(x)：由r个冗余比特为系数构成的多项式。

码多项式T(x)：在m个信息比特后加上r个冗余比特构成的码字所对应的多项式，表达式为：T(x) = xr·M(x) + R(x)。

生成多项式G(x)：双方预先确定用来计算R(x)的一个多项式。

编码方法：用对应于G(x)的位串去除对应于xr·M(x)的位串，所得的余数附加到信息比特串的后面一起发送。

检错方法：用对应于G(x)的位串去除对应于T(x)的位串，若余数为0则认为传输正确，否则认为传输错误。

CRC码检错能力强，实现简单快捷，是应用最广泛的检错码。

3. 基本数据链路协议

通过三个由简单到复杂的数据链路协议来介绍该层协议的基本设计思想。在这里假设源主机A与目的主机B通过一条单工信道进行通信，且A使用可靠的面向连接的服务向B传输数据。

当A的数据链路层收到网络层的一个分组后，将其嵌入到一个数据帧中，即加上帧头（控制信息）和帧尾（校验），然后传给B的数据链路层。假设数据链路层可以通过库例程

to_physical_layer和from_physical_layer向/从物理层发送/接收帧，且校验部分（帧尾）由发送硬件自动加上和校验，链路层软件可不用关心。数据链路层还可以通过库例程

to_network_layer和from_network_layer向/从网络层发送/接收分组。数据链路层调用库例程wait_for_event (&event)等待某个事件的发生，事件的类型从变量event中获得。假设帧头包括类型、发送序号、确认序号三个域（仅为示例用）。

协议1

这是一个最简单的单工协议，假设数据只在一个方向上传输，信道不会出错，且网络层和物理层始终处于准备好状态，因此既不需要差错控制也不需要流量控制。过程如下：

发送方 接收方

1) 从网络层接收一个分组； 1) 等待帧到达事件；

2) 将分组装入帧的信息域； 2) 从物理层接收一个帧；

3) 将帧传给物理层； 3) 将分组（帧的信息域）传给网络层；

4) 返回 1) 4) 返回 1)

由于不需要确认，也就不需要帧序号。

协议2

仍然假定是单工通信，且信道不会出错，但是接收端的处理能力有限，需要控制发送方的速度，即流量控制。在这里需要引入反馈，要求接收端在准备好接收下一帧时，向发送方发回一个响应帧；而发送方在收到响应帧后，才能发送下一帧，这称为停-等。过程如下：

发送方 接收方

1) 从网络层接收一个分组； 1) 等待帧到达事件；

2) 将分组装入帧的信息域； 2) 从物理层接收一个帧；

3) 将帧传给物理层； 3) 将分组（帧的信息域）传给网络层；

4) 等待响应帧； 4) 发送响应帧；

5) 响应帧到达，返回 1) 5) 返回 1) 由于每次只发送一个帧，得到响应后再发下一帧，且不会出错，因此不会有重发的需要，也就不需要帧序号。

协议3

仍然假定是单工通信，但是信道可能会出错，接收端处理能力也有限。链路层必须保证每个帧正确到达接收端，且发送端不能以太快的速度发送，因此，在这里既需要差错控制也需要流量控制。

采用协议2中的停-等方式，发送方每次只发送一个帧，当这个帧被正确接收后才能发送下一帧，若该帧未在规定的时间内得到确认（超时），则重发该帧；接收端对每个收到的帧进行校验，对正确收到的帧发回确认，错误的帧丢弃。由于需要区分新、旧两个帧，使用1比特的帧序号。过程如下：

发送方

1) 初始化发送序号（next_frame_to_send = 0）；

2) 从网络层接收一个分组，放入缓冲区；

3) 从缓冲区中取出分组构造一个帧：

 将缓冲区中的分组拷入帧的信息域；

 将next_frame_to_send拷入序号域；

4) 将帧传给物理层；

5) 启动相关的计时器；

6) 等待事件发生（帧到达，收到坏帧，超时）；

7) 事件发生：

① 事件为帧到达：从物理层接收一个帧，检查帧的确认序号域，

 若是对所发帧的确认（ack = next_frame_to_send），终止相关的计时器，从网络层接收下一个分组，放入缓冲区，发送序号加1，返回 3)；

 若不是对所发帧的确认，直接返回 3)；（缓冲区内容和发送序号均不变）

② 事件为其它（收到坏帧，超时）：返回 3)；（缓冲区内容和发送序号均不变）

接收方

1) 初始化期待接收的帧序号（frame_expected = 0）；

2) 等待帧的到达；

3) 从物理层接收一个帧，检查帧的发送序号域（seq），

 如果是期待接收的帧（seq = frame_expected），将帧中携带的分组交给网络层，frame_expected加1，执行4）；

 若不是期待接收的帧（一个重复帧），执行4）；

4) 发回对收到帧的确认（确认帧的ack等于收到帧的seq）；

5) 返回 2)。

4. 滑动窗口协议

前面的协议都假定数据帧沿着一个方向传输，但事实上大多数的通信都是双向的。当双方都有数据发送时，将确认序号携带在数据帧中传输可以减少开销，这称为捎带应答（piggybacking）。捎带应答带来的一个问题是，当需要发送确认时没有要发送的数据帧怎么办？这可以让确认信息推迟一点时间再发送，如果仍然没有数据帧要发送，再用一个单独的帧进行确认。 以下三个协议都是用于双向数据传输的协议，且都属于滑动窗口协议，但它们的效率、复杂度及对内存的需求都不同。