计算机网络杂记-03

数据链路层

数据链路层的作用是：将网络层传下来的IP数据报组装成帧，然后在通信的两个结点之间传送帧。

• 帧：数据链路层的数据单位。

• 数据链路：两个相邻结点之间的传输介质。

数据链路层的三个基本问题

1. 封装成帧

2. 可靠传输

3. 差错检测

封装成帧

封装成帧是指在数据报前后添加首部和尾部，组成帧。

帧的结构

以太网V2的MAC帧格式如下：

• 帧头：7个字段，共14个字节

  • 目的MAC地址：6个字节
  • 源地址：6个字节
  • 类型：2个字节，表示上层协议类型

• 数据：46~1500个字节

• 帧尾：4个字节，表示帧的结束

每个结构的作用

• 帧头和帧尾中包含了帧的定界符，用于标识帧的开始和结束；以及重要的控制信息。

• 透明传输是指数据链路对上层交付的数据不加以解释和修改，即不对数据进行任何处理。

• 为了提高帧的传输效率，应当使帧的数据部分的长度尽可能大些；数据链路层采用了帧的填充技术。

• 帧的填充技术是指在数据中出现特定字符时，数据链路层自动在该字符前面插入一个转义字符，以免与帧的定界符混淆。

• 考虑到差错控制等多种因素，每一种数据链路层协议都规定了帧的最大长度，即最大传送单元MTU（Maximum Transmission Unit）。

差错检测

实际的通信链路都是不可靠的，比特在传输过程中可能会出错：1变为0，0变为1，这种错误称为比特差错。

在一段时间内，传输错误的比特的个数称为比特差错率。

使用差错检测码可以检测出数据在传输过程中是否出错。

奇偶校验码

奇偶校验码是一种最简单的差错检测码，它的原理是：在每一帧的数据后面添加一个附加位，使得每一帧的数据加上附加位中1的个数为奇数或者偶数。

在奇校验中，如果传输过程产生 1 位差错，那么接收方检测到的附加位中1的个数就是奇数，就知道数据出错了。但是如果传输过程产生 2 位差错，那么接收方检测到的附加位中1的个数就是偶数，就无法检测出数据出错了。

偶校验与奇校验相反。

循环冗余检测码 CRC（Cyclic Redundancy Check）

CRC码是一种最常用的差错检测码，它的原理是：将数据看成是二进制数，用一个除数去除这个二进制数，得到的余数作为附加位。

• 收发双方事先约定好除数，这个除数称为生成多项式 G(x)。

• 发送方将数据看成是二进制数，用生成多项式 G(x) 去除这个二进制数，得到的余数作为附加位。

• 接收方将接收到的数据看成是二进制数，用生成多项式 G(x) 去除这个二进制数，得到的余数如果为0，说明数据没有出错；如果不为0，说明数据出错了。

e.g. 生成多项式 G(x) = x^4 + x^2 + x + 1，求生成多项式各项系数构成的比特串。

G(x) = 1 x^4 + 0 x^3 + 1 x^2 + 1 x + 1 x^0 = 10111

e.g. 生成多项式 G(x) = x^3 + x^2 + 1，数据 101001，计算过程如下：

1、构造被除数；待发送信息后面添加生成式最高次数个0，即 101001000。
2、构造除数；生成式各项系数构成的比特串，1101。
3、进行除法运算；将被除数与除数进行异或运算，得到的结果再与除数进行异或运算，直到被除数的位数小于除数的位数为止。

sign      110101
      ————————————
1101 / 101001000
     ⊕ 1101
    ——————
       01110
      ⊕ 1101
      ——————
        001110
        ⊕ 1101
        ——————
          001100
          ⊕ 1101
          ——————
            0001

其中，sign 表示此时是否够除，如果够除，sign 为 1，否则为 0。sign的作用是：当被除数的位数小于除数的位数时，将被除数的最高位补 0，使得被除数的位数大于除数的位数，这样才能进行异或运算。

4、得到的余数即为 CRC 码。余数的位数与生成式的最高次数相同，即 3 位，如果不够 3 位，前面补 0。
5、将余数添加到待发送信息后面，得到的结果即为发送的信息。即 101001000 + 001 = 101001001。

说明

• 检错码只能检测出数据在传输过程中是否出错，不能纠正数据出错。

• CRC 码的检错能力与生成多项式的次数有关，生成多项式的次数越高，检错能力越强。

• 想要纠正数据出错，需要使用纠错码。但是纠错码的计算量很大，一般不用于数据链路层。

可靠传输

• 利用差错检测技术，可以检测出数据在传输过程中是否出错，但是无法纠正数据出错。

• 数据链路层向上层提供的服务类型

  • 不可靠服务：数据链路层不对数据进行检错和重发，只是简单地将数据从一端传送到另一端。仅仅丢弃出错的帧，不进行重发。
  • 可靠服务：数据链路层对数据进行检错和重发，确保数据从一端传送到另一端的正确性。

• 有线链路误码率一般在 10^-9 ~ 10^-12 之间，无线链路误码率一般在 10^-3 ~ 10^-6 之间。所以，有线链路一般不需要可靠传输，而无线链路一般需要可靠传输。

• 比特差错只是数据链路层可能出现的差错之一，还有很多其他的差错，如：丢帧、重复帧、帧失序等。

• 从整个网络体系结构来看，传输差错还包括：分组丢失、分组失序、分组重复等。

• 可靠传输服务并不局限于数据链路层，网络层也可以提供可靠传输服务。

下面，我们将记录一些可靠传输协议。这些协议并不局限于数据链路层，也可以应用于网络层。

停止等待协议 SW（Stop-and-Wait）

停止等待协议是一种最简单的可靠传输协议，它的原理是：发送方发送一帧后，停止发送，等待接收方的确认帧；接收方收到帧后，发送确认帧，然后等待发送方的下一帧。

确认与否定

      互联网
发送方--------接收方
  |   DATA     |
  |  ------->  |
  |            |
  |   ACK      |
  |  <-------  |
  |            |
  |  DATA(误码) |
  |  ------->  | 丢
  |            |
  |   NCK      |
重|  <-------  | 弃
  |            |
  |   DATA     |
传|  ------->  |
  |            |
  ↓            ↓

ACK：肯定确认帧，表示接收方正确收到了帧。
NCK：否定确认帧，表示接收方没有正确收到帧。

说明

• 发送方发送一帧后，停止发送，等待接收方的确认帧；接收方收到帧后，发送确认帧，然后等待发送方的下一帧。

• 如果发送方在规定的时间内没有收到接收方的确认帧，就认为帧出错，需要重发。

• 如果接收方在规定的时间内没有收到发送方的帧，就发送 NCK，要求发送方重发。

• 如果发送方在规定的时间内没有收到接收方的 NCK，就认为帧没有出错，不需要重发。

• 如果接收方在规定的时间内没有收到发送方的帧，就认为帧出错，需要重发。

超时重传：发送方在规定的时间内没有收到接收方的确认帧，就认为帧出错，需要重发。

为什么需要超时重传？

• 如果发送方在规定的时间内没有收到接收方的确认帧，就认为帧出错，需要重发。

• 如果接收方在规定的时间内没有收到发送方的帧，就发送 NCK，要求发送方重发。

超时重传

      互联网
发送方--------接收方
  |   DATA     |
——|  -----丢失  |
等|            |
待|   DATA     |
——|  ------->  |
重|            |
传|   ACK      |
  |  <-------  |
  |            |
  |   DATA     |
  |  ------->  |
  |            |
  |   ACK      |
  |  <-------  |
  |            |
  ↓            ↓

• 如果发送方在规定的时间内没有收到接收方的确认帧，就认为帧出错，需要重发。

• 如果接收方在规定的时间内没有收到发送方的帧，就发送 NCK，要求发送方重发。

确认丢失

      互联网
发送方--------接收方
——|   DATA     |
等|  ------->  |
  |            |
待|   ACK      |
——|  丢失-----  |
重|            |
传|   DATA     |
  |  ------->  |
  |            |
  |   ACK      |
  |  <-------  |
  |            |
  ↓            ↓

上面的情况，ACK 丢失，发送方会重发，接收方会丢弃重复的帧。为了避免这种情况，需要在 ACK 中添加序号，这样接收方就可以检测出重复的帧。用1个比特来编号，就可以表示 0 和 1 两种状态，这种编号方式称为停止等待协议的可靠传输。

      互联网
发送方--------接收方
——|   DATA0    |
等|  ------->  |
  |            |
待|   ACK      |
——|  丢失-----  |
重|            |
传|   DATA0    |
  |  ------->  |
  |            |
  |   ACK      |
  |  <-------  |
  |            |
  |   DATA1    |
  |  ------->  |
  |            |
  |   ACK      |
  |  <-------  |
  |            |
  ↓            ↓

如果因为某些原因，接收方收到了重复的帧，就丢弃重复的帧，不发送 ACK。

确认迟到

ACK 因为某些原因，没有及时发送，而是延迟发送，这种情况称为确认迟到。

这时，我们在 ACK 中添加序号，这样发送方就可以检测出重复的帧。

在数据链路层中，通常不用给ACK编号，因为数据链路层的传输速率很高，一般不会出现确认迟到的情况。

SW 协议的信道利用率

信道利用率是指信道中有用的时间与总时间的比值。

U = TD / (TD + RTT + TA)

U 是信道利用率，TD 是数据传输时间，RTT 是往返时间，TA 是确认时间。

• 数据传输时间 TD = L / R，L 是帧的长度，R 是信道的传输速率。

• 往返时间 RTT = 2 * d / v，d 是信道的长度，v 是信号的传播速率。

• 确认时间 TA = L / R，L 是帧的长度，R 是信道的传输速率。

U = L / (L + 2 * d / v + L / R)

说明

• 信道利用率是指信道中有用的时间与总时间的比值。

• 数据传输时间 TD = L / R，L 是帧的长度，R 是信道的传输速率。

• 往返时间 RTT = 2 * d / v，d 是信道的长度，v 是信号的传播速率。

• 确认时间 TA = L / R，L 是帧的长度，R 是信道的传输速率。

通过上面的公式可以看出，信道利用率与帧的长度有关，帧的长度越大，信道利用率越高。所以，这暴露了 SW 协议的一个缺点：帧的长度不能太小，否则信道利用率会很低。所以，因为 SW 协议的信道利用率低，所以 SW 协议一般不用于数据链路层，而是用于网络层。

回退 N 帧协议 ARQ（Automatic Repeat Request）

SW 协议的信道利用率低，而且只能发送一帧，所以，我们可以将 SW 协议扩展成回退 N 帧协议 ARQ。

该协议也叫 Go-Back-N 协议，它的原理是：发送方连续发送 N 帧，而不需要等待接收方的确认帧；接收方收到帧后，发送确认帧，然后等待发送方的下一帧。

该协议采用流水线技术，发送方可以连续发送多帧，而不需要等待接收方的确认帧。

参考：

• 計算機網路概論 GBN、SR、TCP 比較

• Go-Back-N ARQ – Wikipedia

发送方

• 发送窗口尺寸 WT 取值范围为 1 < WT <= 2^n - 1，其中 n 为比特数。

  • WT = 1 时，退化为 SW 协议。
  • WT = 2^n - 1 时，退化为 SR 协议。

• 发送方可在未收到确认帧的情况下，将序号为 SN ~ SN + WT - 1 的帧连续发送出去。

• 发送方收到确认帧后，将窗口向前滑动，即 SN = SN + 1，然后发送 SN + WT - 1 帧。

• 发送方在规定的时间内没有收到接收方的确认帧，就认为帧出错，需要重发。

• 发送方在规定的时间内没有收到接收方的 NCK，就认为帧没有出错，不需要重发。

接收方

• 接收窗口尺寸 WR 取值范围为 WR = 1。因此，接收方只能接收序号为 RN 的帧。

• 接收方收到序号为 RN 的帧后，发送确认帧，然后接收下一帧。

• 接收方在规定的时间内没有收到发送方的帧，就发送 NCK，要求发送方重发。

选择重传协议 SR（Selective Repeat）

SR 协议也是一种流水线协议，它的原理是：发送方连续发送 N 帧，而不需要等待接收方的确认帧；接收方收到帧后，发送确认帧，然后等待发送方的下一帧。

发送方

发送方的发送窗口尺寸 WT 取值范围为 1 < WT <= 2^(n-1)，其中 n 为比特数。

• WT = 1 时，退化为 SW 协议。

• WT > 2^(n-1) 时，发送方的发送窗口尺寸超过了接收方的接收窗口尺寸，这种情况下，接收方无法接收所有的帧，所以，这种情况下，发送方的发送窗口尺寸应该等于接收方的接收窗口尺寸。

接收方

接收方的接收窗口尺寸 WR 取值范围为 1 < WR <= WT = 2^(n-1)，其中 n 为比特数。

• WR = 1 时，退化为 SW 协议。

• WR > 2^(n-1) 时，无意义。