数据链路层

计算机网络

字数统计: 4.6k阅读时长: 17 min

 2021/05/08   Share

数据链路层

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

1.1 封装成帧

封装成帧（framing）就是在一段数据的前后分别添加首部和尾部，这样就构成了一个帧。接收端在收到物理层上交的比特流后，就能根据首部和尾部的标记，从比特流中识别帧的开始和结束。

首部和尾部的一个重要作用就是进行帧定界（即确定帧的界限）。此外，首部和尾部还包括许多必要的控制信息。

为了提高帧的传输效率，应当使帧的数据部分长度尽量大于首部和尾部的长度。

最大传输单元 MTU（Maximum Transfer Unit）：帧数据部分长度上限。

当数据是由可打印的 ASCII 码组成的文本文件时，帧定界可以使用特殊的帧定界符。

控制字符 SOH （Start Of Header）放在一帧的最前面，表示帧首部。
控制字符 EOT （End Of Transmission）放在一帧的最后面，表示帧尾部。

注意： SOH 和 EOT 都只是控制字符的名称，他们的十六进制编码分别是 01（二进制是00000001）和 04（二进制是00000100）。

SOH ， EOT 并不是 S O H E O T这几个字符，只是名字而已。

当传输中出现差错，帧定界符的作用更加明显。假设未发送完一个帧而发生故障，接收端就知道收到的数据是不完整的帧（只有首部），必须丢弃。

1.2 透明传输

如果数据中的某个字节的二进制代码恰好和 SOH 或 EOT 一样，数据链路层就会错误地找到帧的边界。

为了解决透明传输问题，字节填充法或字符填充：在控制字符SOH、EOT的前面插入一个转义字符 ESC（其十六进制编码是 1B，二进制是 0001 1011）。而接收端的数据链路层在把数据送往网络层之前删除这个插入的转义字符。

当然如果转义字符 ESC 也出现在数据当中，那么解决的方法仍然是在转义字符的前面插入一个转义字符，所以，当接受到连续的两个转义字符的时候，就去删除其中前面的一个。

在接收端进行处理之后可以还原出原始数据。这个过程透明传输的内容是转义字符，用户察觉不到转义字符的存在。

1.3 差错检测

在传输过程中可能会产生比特差错： 1 可能变成 0 , 0 可能变成 1 。

在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率（ BER，Bit Error Rate）。

误码率和信噪比有很大的关系。

为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检測措施。在数据链路层传送的帧中，广泛使用了循环冗余检验 CRC 的检错技术。

传输差错分为两类：

比特差错。
收到的帧出现了帧丢失、帧重复和帧失序。（停止等待协议，ARQ）。

差错控制（比特差错）

检错编码
- 奇偶校验码
- 循环冗余码 CRC
纠错编码
- 海明码

1.3.1 奇偶校验码

奇偶校验只能检测出奇数个错误，无法纠错。

通过在编码中增加一位校验位，要么是 0 ，要么是 1 。来使编码中 1 的个数为奇数或者偶数，校验位可以在原编码的前面或者后面加。通过计算加入校验位后， 1 的个数是奇数还是偶数，可分为两种：

奇校验：1 的个数为奇数
偶校验：1 的个数为偶数

1.3.2 循环冗余码 CRC

循环冗余码 CRC 由 n 位信息位和 k 位校验位构成。 k 位校验位拼接在 n 位数据位后面， n + k 为循环冗余校验码的字长，又称这个校验码（n + k, n ）码。
n 位信息位可以表示成为一个报文多项式 M(x)，最高幂次是 x^n-1 。约定的生成多项式 G(x) 是一个 k + 1 位的二进制数，最高幂次是 x^k 。将 M(x) 乘以 x^k ，即左移 k 位后，除以 G(x) ，得到的 k 位余数就是校验位。这里的除法运算是模 2 除法，即当部分余数首位是 1 时商取 1 ，反之商取 0 。然后每一位的减法运算是按位减，不产生借位。

循环冗余码 CRC 的特点：

可检测出所有奇数位错。
可检测出所有双比特的错。
可检测出所有小于、等于校验位长度的突发错。

计算 CRC ：

M(x) 代表发送信息的多项式，G(x) 代表校验位信息
$$
\begin{aligned}
M(x)&=x^3+1\hspace{50cm}\
&=1x^3+0x^2+0x^1+1X^0\
&=1001
\end{aligned}
$$

$$
\begin{aligned}
G(x) &= x^3+x+1\hspace{50cm}\
&=1x^3+0x^2+1x^1+1x^0\
&=1011
\end{aligned}
$$

M(X)加上校验位信息多项式的最高次幂个 0 。
$$
M(x)=1001000\hspace{100cm}
$$
M(x) 对 G(x) 做模 2 除法，取得余数。

余数为 110，即为校验位。故 CRC 码为：1001110

接收端校验：

CRC 码与 G(x) 进行模 2 除法。

结果为 0 ，则证明正确。

1.3.3 海明码

序列1100我们想要让其变成海明码只需如下操作：

算出校验位数 k

$2^k >= k + 数据位数+1$

示例：序列 1100 的校验位数为 3 。
确定校验位在海明码中的位置

每一位校验位在 $2^n$ 上。（ n 的取值为 0 ~ n - 1）

示例：序列 1100 的海明码为 XX1X100 。
分组
1. 我们需要确认 H1， H2， H4这三个校验位都来校验哪些位置。
  我们按这个规则进行分配。
  
  的二进制码写出来，并且最高位补到3位(前面算的K数)
  如下所示：
| 1 | 2 | 4 |
| —- | —- | —- |
| 001 | 010 | 100 |

然后我们将 0 替换为 * ，作为通配表：

| 1 | 2 | 4 |
| —- | —- | —- |
| 1 | *1* | 1 |

我们将1到7的二进制序列，列出来如下表：

| 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| —- | —- | —- | —- | —- | —- | —- |
| 111 | 110 | 101 | 100 | 011 | 010 | 001 |

我们将7->1依次与上面的通配表进行匹配：

| 1 | 2 | 4 |
| ——– | ——– | ——– |
| 1 | *1* | 1 |
| 001（1） | 010（2） | 100（4） |
| 011（3） | 011（3） | 101（5） |
| 101（5） | 110（6） | 110（6） |
| 111（7） | 111（7） | 111（7） |

因此我们可以确定
H1 负责 1 3 5 7 位数的校验
H2 负责 2 3 6 7 位数的校验
H4 负责 4 5 6 7 位数的校验
求出校验位是 0 还是 1
$$
\begin{aligned}
x_1 \bigoplus x_3\bigoplus x_5\bigoplus x_7=0\hspace{50cm}\
\end{aligned}
$$
依此类推：

H3 ，H5 ，H7中 1 的个数为奇数，因此 H1 = 1。
H3 ，H6 ，H7中 1 的个数为偶数，因此 H2 = 0。
H5 ，H6 ，H7中 1 的个数为偶数，因此 H4 = 0。

至此我们得出了完整的海明码：1100001
查错

查错比较简单，如果以下三组
既 H1，H3，H5，H7
或者 H2，H3，H6，H7
或者 H4，H5，H6，H7
偶校验出错，则出错。

比方说如果H1，H3，H5，H7由1100变成了1110（1的个数为偶数）就是出错了。
纠错

假设位置为 1011 的数据传输错误，由0变成了1。

则校验纠错的过程为：将所有位置形如xxx1, xx1x, x1xx, 1xxx的数据分别异或。
1
2
3
4
xxx1: 0^1^0^0^1^1 = 1
xx1x: 1^1^1^0^1^1 = 1
x1xx: 1^0^1^0 = 0
1xxx: 0^1^1^1 = 1
那么出错数据的位置为1011，这样便可得到出错的位置。

假设同时有两个位置出错，本例中假设位置为 1010 对应数据由 1 变成 0 ，位置为 1011 对应数据由 0 变成 1 ，则推出校验纠错过程：
1
2
3
4
xxx1: 0^1^0^0^1^1 = 1
xx1x: 1^1^1^0^0^1 = 0
x1xx: 1^0^1^0 = 0
1xxx: 0^1^0^1 = 0
那么校算出的错误位是 0001 ，即第一位。但实际上是倒数第二位和最后一位都有错误，说明海明码不能校验两位以上出错的数据，即海明码只能检测并纠正一位错误。

2 信道分类

2.1 广播信道

一对多通信，一个节点发送的数据能够被广播信道上所有的节点接收到。

所有的节点都在同一个广播信道上发送数据，因此需要有专门的控制方法进行协调，避免发生冲突（冲突也叫碰撞）。

主要有两种控制方法进行协调，一个是使用信道复用技术，一是使用 CSMA/CD 协议。

2.2 点对点信道

一对一通信。

因为不会发生碰撞，因此也比较简单，使用 PPP 协议进行控制。

3 信道复用技术

3.1 频分复用（FDM）

是按频率分割多路信号的方法，即将信道的可用频带分成若干互不交叠的频段，每路信号占据其中的一个频段。
在接收端用适当的滤波器将多路信号分开，分别进行解调和终端处理。

当采用频分复用技术时，所有用户在同样的时间占用不同的带宽资源。

3.2 时分复用（TDM）

TDM 帧：将传输时间划分为多个等长的时间段（ TDM 帧）
时隙：每个 TDM 帧划分成更小的时间段（时隙），每个用户在每个 TDM 帧中占用固定的时隙进行通信。类似分时 OS 的时间片概念。

当采用时分复用时，所有用户在不同的时间占用同样的频带宽度（分时不分频）。

使用频分复用和时分复用进行通信，在通信的过程中主机会一直占用一部分信道资源。但是由于计算机数据的突发性质，通信过程没必要一直占用信道资源而不让出给其它用户使用，因此这两种方式对信道的利用率都不高。

3.3 统计时分复用（STDM，Statistic TDM）

是对时分复用的一种改进，不固定每个用户在时分复用帧中的位置，只要有数据就集中起来组成统计时分复用帧然后发送。

STDM 的特点：

连接低速用户，集中数据传输。

STDM 帧：

不等长，时隙数小于所连接的用户数。
不是固定分配时隙，而是按需分配时隙，可提高线路的利用率。增加地址信息。

由于 STDM 帧中的时隙不是固定地分配给某个用户，因此在每个时隙中还必须有用户的地址信息，这将产生额外开销。
异步时分复用，指统计时分复用。
同步时分复用，指普通时分复用。

3.4 波分复用（WDM）

光的频分复用。由于光的频率很高，因此习惯上用波长而不是频率来表示所使用的光载波。

3.5 码分复用（CDM，CDMA，Code Division Multiple Access）

常用的名词是码分多址 CDMA (Code Division Multiple Access)。

码分复用 CDM（Code Division Multiplexing）是各用户使用经过特殊挑选的不同码型，在同样的时间使用同样的频带进行通信，但彼此不会造成干扰。

这种系统发送的信号有很强的抗干扰能力，其频谱类似于白噪声，不易被敌人发现。

CDMA的原理:

在CDMA中，每一个比特时间划分为 m 个短的间隔，称为码片（chip）。通常 m 的值是 64 或者 128 。

每个站被指派一个唯一的 m bit 码片序列（chip sequence）。

如发送比特 1，则发送自己的 m bit 码片序列。
如发送比特 0，则发送该码片序列的二进制反码。

每一个站分配的码片序列不仅必须各不相同，并且还必须相互正交。

4 CSMA/CD 协议

CSMA/CD 表示载波监听多点接入/碰撞检测。

多点接入 ：说明这是总线型网络，许多主机以多点的方式连接到总线上。
载波监听 ：每个主机都必须不停地监听信道。在发送前，如果监听到信道正在使用，就必须等待。
碰撞检测 ：在发送中，如果监听到信道已有其它主机正在发送数据，就表示发生了碰撞。虽然每个主机在发送数据之前都已经监听到信道为空闲，但是由于电磁波的传播时延的存在，还是有可能会发生碰撞。

记端到端的传播时延为 τ，最先发送的站点最多经过 2τ 就可以知道是否发生了碰撞，称 2τ 为 争用期 。只有经过争用期之后还没有检测到碰撞，才能肯定这次发送不会发生碰撞。

当发生碰撞时，站点要停止发送，等待一段时间再发送。这个时间采用截断二进制指数退避算法来确定。从离散的整数集合 {0, 1, .., (2k-1)} 中随机取出一个数，记作 r，然后取 r 倍的争用期作为重传等待时间。

5 PPP 协议（Point-to-Point Protocol）

PPP（Point-to-Point Protocol），数据链路层协议。PPP 是为在同等单元之间传输数据包这样的简单链路设计的链路层协议。这种链路提供全双工操作，并按照顺序传递数据包。

5.1 PPP 协议功能

IP 地址的动态分配和管理。
同步或异步的物理层通信。
链路的配置、质量检测和纠错。
多种配置参数选项的协商。

5.2 PPP 协议包括什么协议

LCP（ Link Control Protocol）
NCP（ Network Control Protocol）
PPP的扩展协议（如 Multilink Protocol）

5.3 PPP 帧的构成

这里写图片描述

Flag：标志位、用于标识帧的开始和结束
Addr：地址位，用于标识Station地址。PPP帧发源自HDLC帧，保留了此字段。对于PPP帧来说，由于是点对点协议，不需要地址位。PPP帧的地址位恒为0xFF。（PPP协议被运用在点对点链路上，不需要知道对端的链路地址，因为点对点链路，如PPPoE帧头中，已经确定了对端的地址）。
Control：在DHLC帧中，Control位用来标识帧的顺序和重传行为，但由于该功能在PPP协议中并没有普遍实现，因此PPP帧中，Control值固定为）0x03.
Protocol：协议字段，标识所携带报文的类型。如0x0021时，表示PPP帧的信息字段是IP数据报文。不同的Protocol标识Data字段的不同含义。
Data： 信息字段，即PPP帧的负载(如LCP帧、NCP帧）.信息域缺省时最大长度不能超过1500字节，其中包括填充域的内容
Pad：填充字段
FCS：循环冗余码。覆盖了两个Flag（不包括）之间的字段。

6 MAC 地址

MAC 地址是数据链路层地址，长度为 6 字节（48 位），用于唯一标识网络适配器（网卡）。

一台主机拥有多少个网络适配器就有多少个 MAC 地址。例如笔记本电脑普遍存在无线网络适配器和有线网络适配器，因此就有两个 MAC 地址。

7 局域网

局域网是一种典型的广播信道，主要特点是网络为一个单位所拥有，且地理范围和站点数目均有限。

主要有以太网、令牌环网、FDDI 和 ATM 等局域网技术，目前以太网占领着有线局域网市场。

可以按照网络拓扑结构对局域网进行分类：

8 以太网

以太网是一种星型拓扑结构局域网。

早期使用集线器进行连接，集线器是一种物理层设备，作用于比特而不是帧，当一个比特到达接口时，集线器重新生成这个比特，并将其能量强度放大，从而扩大网络的传输距离，之后再将这个比特发送到其它所有接口。如果集线器同时收到两个不同接口的帧，那么就发生了碰撞。

目前以太网使用交换机替代了集线器，交换机是一种链路层设备，它不会发生碰撞，能根据 MAC 地址进行存储转发。

以太网帧格式：

类型：标记上层使用的协议。
数据：长度在 46-1500 之间，如果太小则需要填充。
FCS ：帧检验序列，使用的是 CRC 检验方法。

9 交换机

交换机具有自学习能力，学习的是交换表的内容，交换表中存储着 MAC 地址到接口的映射。

正是由于这种自学习能力，因此交换机是一种即插即用设备，不需要网络管理员手动配置交换表内容。

下图中，交换机有 4 个接口，主机 A 向主机 B 发送数据帧时，交换机把主机 A 到接口 1 的映射写入交换表中。为了发送数据帧到 B，先查交换表，此时没有主机 B 的表项，那么主机 A 就发送广播帧，主机 C 和主机 D 会丢弃该帧，主机 B 回应该帧向主机 A 发送数据包时，交换机查找交换表得到主机 A 映射的接口为 1，就发送数据帧到接口 1，同时交换机添加主机 B 到接口 2 的映射。