计网数据链路层

数据链路层是基于物理层不可靠的传输向上层提供可靠的传输，它提供的是相邻两个节点之间可靠的数据传输。本章将学习网络模型中的第二层（即数据链路层）的设计原则。学习内容涉及两台相邻（指两台机器通过一条通信信道连接起来）机器实现可靠有效的完整信息块（称为帧）通信的一些算法，而不像物理层那样只关注单个比特传输。解决通信线路中出错的情况、关于有限的数据传输率、发送时间和接受时间存在的非零延迟等问题。

本章内容结构：

  1. 首先介绍数据链路层的关键设计问题，并学习如何考察错误的本质以及如何检测和纠正这些错误。
  2. 然后，我们将学习一系列复杂性逐步递增的协议，每个协议解决了本层中越来越多的问题。
  3. 最后会给出一些数据链路层协议的例子。

上图为本章考试重点，非原书结构，仅供参考。

数据链路层的设计问题

数据链路层使用物理层提供的服务在通信信道上发送和接受比特。完成一些功能：

  1. 向网络层提供一个定义良好的服务接口。
  2. 处理传输错误。
  3. 调节数据流，保证慢速的接收方不会被快速的发送方淹没。

为实现这些目标：，数据链路层从网络层获得数据包，并将之包装成包含：帧头+ 有效载荷（存放数据包）+ 帧尾的帧（frame）。

数据链路层的工作核心就是帧的管理。

帧的通用结构中前三项称为帧头。

提供给网络层的服务

最主要的服务是将数据从源机器的网络层传输到目标机器的网络层。

一般情况下，提供以下三种可能的服务：

  1. 无确认的无连接服务。

    源机器向目标机器发送独立的帧，目标机器不对这些帧进行确认。不需建立逻辑连接。适用于错误率低或者实时通信（语音传输）的情况。

  2. 有确认的无连接服务。

    源机器向目标机器发送独立的帧，目标机器会对这些帧进行确认。不需建立逻辑连接。适用于不可靠的信道（无线系统，WiFi）。

  3. 有确认的有连接服务。

    源机器和目标机器在传输任何一个数据之前要建立一个连接，保证目标机器按照正确的顺序接受每一个帧。适用于长距离且不可靠的链路（卫星信道，长途电话）。

成帧

为检测错误和纠正错误，数据链路层将比特流拆分成多个离散的帧，为每个帧计算一个称为校验和的短令牌，并将该校验和放在帧中一起传输。为拆分比特流需要解决两个问题：

  1. 帧的边界问题：如何识别帧的边界
  2. 帧的透明传输（填充）问题：如果帧的数据中出现和边界一样的flag 该如何防止被识别为边界

下面介绍四种成帧方法

  1. Character count（字节计数法）

    用头部的一个字段来标识该帧中的字符数。
    问题：因为一个传输错误，就会全弄混。很少被使用。

  2. Flag Bytes with byte stuffing（字节填充的标志字节法）

    发送方使用标志字节（FLAG）作为开始和结束；使用转义字节（ESC）表示其后的字节为数据字节而不是标志字节或转义字节。接收方将收到的数据中的转义字节删除后再传递给网络层。

  3. Starting and ending flags,with bit stuffing（比特填充的标志比特法）

    使用“01111110”表示帧的开始和结束（帧的边界问题解决），并且在数据中，若遇到5 个连续的比特1，就在其后填入一个比特0（帧的填充问题解决）。接收方除了将首尾的“01111110”删除外，还要将数据中所有5 个连续比特1 其后的比特0 删除。

  4. Physical layer coding violation（物理层编码违禁法）

    使用“不会出现在常规数据中”的冗余比特作为边界。好处是除了开始和结束的填充外，不再需要填充额外的数据。

差错控制

为确保所有帧按照正确顺序传递给目标机器的网络层：

  • 发送方发送反馈信息来确保传递可靠。
  • 引入计时器来防止硬件故障或通信信道出错等原因丢失某一帧使发送方持续等待确认。
  • 通过序号保证每一帧按照顺序且不会被接收方重复接收。

具体的确认方式在后面通过协议的形式来讲。

流量控制

发送方发送帧的速度超过了接收方能够接收这些帧的速度，而导致丢帧。
解决方法：

  • 基于反馈的流量控制（链路层）。
  • 基于速率的流量控制（网络层）。

差错检测和纠正

纠错码

推断出被发送的数据是什么。适用于错误发生很频繁的信道，因为再次传输仍可能出错。

海明码（参考原书p159 ）：

检错码

循环冗余校验码（CRC，Cyclic Redundancy Check，也称作多项式编码)，推断是否发生错误。适用于高度可靠的信道，错误偶尔发生时，只需重传整个数据块即可。注意有一定的误判率。
步骤：（以下面算式为例讲解，具体原理参见课本P165）

  1. 收发双方商定一个比帧短且头尾都是1 的01 串叫做生成多项式，如下的10011
  2. 帧的后面附上生成多项式长度减一个0 后，作为被除数对生成多项式模2 除，得到
    商和余数，如10011 长度为5，所以附上了4 个0
  3. 若帧与余数合并以后在接收方被生成多项式整除，那么认为传递的过程没有出错

模2除原则：列竖式的方式同除法，但是模2 除法中加法无进位，减法无借位，即加减皆等同于异或，而商0 还是1 由被除数首位决定，首位是1 商1，否则商0。

基本数据链路层协议

组成帧的四个字段：kind、seq、ack 和info。前三个包含控制信息，称为帧头，最后一个可能包含了要被传输的实际数据。

一个乌托邦式的单工协议（协议1）

  • 不需考虑任何错误情况：数据单向传输，双方总是就绪，数据处理时间不计，缓存空间无限大，通信信道永不丢帧。
  • 这是一个完全不现实（理想化）的协议，所以称为“乌托邦” 协议。
  • 发送过程是一个无限的while 循环，它尽可能快速地把数据放到线路上。无差错控制或者流量控制方面的限制。接受过程一直等待一个未损坏的帧到达。（发送速率和接收速率必须一样快）

无错信道上的单工停-等式协议（协议2）

单向数据传输，发送方网络层一直有无限的数据要发送， 信道不会出错，从不损坏或丢失帧，发送方需等待接收方确认帧返回后才发送下一帧。如果接收方不反馈应答信号，则发送方必须一直等待，然后就陷入等待接收方确认信息的过程中，因而传输效率低。

有错信道上的单工停-等式协议（协议3）

信道存在噪音。需要计时器与序号配合，需要超时重传机制。

滑动窗口协议

基本概念

滑动窗口（sliding window）：为了便于理解，可以认为数据是一条传送带，而滑动窗口中的数据是当前准备处理的数据。一旦窗口的第一条数据被确认处理结束，窗口就会继续向后滑动以处理后面的数据。下面是发送方的发送窗口形象化的表示：

  • 捎带确认（piggybacking）：暂时延缓确认以便将确认信息搭载在下一个出境数据帧上的技术。捎带确认通常与累计确认一同使用，更好的利用了信道的可用带宽。
  • 期望确认：收到数据帧以后向发送方发送期望对方发送的下一帧的序号。
  • 累计确认（cumulative acknowledgement）：当n 号帧的确认到达，n-1 号帧、n-2号帧等都会自动被确认。
  • 否定确认（NAK）：接收方检测到错误时发送的否定确认，实际是一个重传请求，在NAK中指定了要重传的帧。
  • 发送窗口（sending window）：发送方总维持着一组序号，分别对应于允许它发送的帧，我们称这些帧落在发送窗口。
  • 接收窗口(receiving window):接收方维持着的一个窗口对应于一组允许它接受的帧。

1 位滑动窗口协议（协议4）

（发送窗口大小=1，接收窗口大小=1）

当接收窗口大小为1 时，可保证帧的有序接收，但效率较低。

源站发送单个帧后必须等待确认，在目的站的确认到达源站之前，源站不能发送其他数据帧。这是因为发送窗口大小仅为1，必须用来保存当前未确认的帧以超时重传。

发送方必须在内存中保存所有的帧，因此如果最大窗口的尺寸为n，则发送方需要n 个缓冲区才存放未被确认的帧。

回退N 协议（协议5）

（发送窗口大小>1，接收窗口大小=1）

发送方按照顺序向对方发送帧，在收到对方的确认以后窗口向后滑动，若当前窗口中的第一个帧出现超时，那么回退到这个帧重新发送所有的帧。

而因为接收窗口大小为1，除了数据链路层必须要递交给网络层的下一帧外，接收方拒绝接受任何帧。如果在计时器超时以前，发送方的窗口已被填满，则管道将变为空闲，最终，发送方将超时，并且按照顺序重传所有未被确认的帧，从那个受损或者丢失的帧开始。

一般使用累计确认。

选择重传协议（协议6）

（发送窗口大小>1，接收窗口大小>1）

发送方按照窗口的顺序依次发送帧给接收方，而接收方检查该帧是否可以落在接收窗口内，即以前没有接收过且该序号在窗口可接收的范围内，如果可以那么不管这一帧是否为网络层所期望的下一个数据包都接收该帧并暂存于缓冲区内。该帧会一直保存在数据链路层中直到所有序号比它小的帧已经按顺序递交给网络层，它才能被传递给网络层。

辅助计时器：在发送方的计时器超时之前，没有出现需要发送的反向流量，则发送一个单独的确认帧，而发送的时间间隔由辅助计时器决定，因此辅助计时器的超时间隔应该明显短于数据帧关联的计时器的间隔。

除ACK，选择重传还有否定确认，当接收方发现坏帧丢弃时，立刻发送一个NAC 给发送方告知该帧未收到让它重传，以防超时。

选择重传和回退N 实际是带宽使用效率与数据链路层缓存空间之间的权衡。

数据链路协议实例

这里要考察的是那些出现在Internet 两种常见情形下的数据链路协议，这些协议主要用在点到点的线路上。第一种情形是通过广域网中的SONET 光纤链路发送数据包。例如，这些链路被广泛用于连接一个ISP 网络中位于不同位置的路由器。

第二种情形是运行在Internet 边缘的电话网络本地回路上的ADSL 链路。这些链接把成千上百万的个人和企业连接到Internet 上。

针对上述这些使用场景Internet 需要点到点链路，还会用到拨号调制解调器、租用线路和线缆调制解调器等。所谓点到点协议（Point-to-Point Protocol) 的标准协议就是使用这些链路来发送数据包。PPP 由RFC1661 定义，并在RFC1662 中得到进一步的阐述(Simpson, 1994a， 1994b)。 SONET 和ADSL 链路都釆用了PPP, 但在使用方式上有所不同。

详见原书。