计算机网络•自顶向下方法：链路层介绍

链路层

链路层：将数据报从一个节点传输到相邻的下一个节点

链路层服务

• 组帧(基本服务)
  • 发送：将数据报封装到帧中 (加上帧头和帧尾)
  • 接收：从原始比特流中提取出完整的帧
• 链路接入（广播需要）
  • 在广播信道上协调各个节点的发送行为
• 差错检测（基本服务）
  • 检测传输错误
• 差错纠正（有些提供）
  • 检测并纠正传输错误（不使用重传）
• 可靠交付（部分协议提供）
  • 过确认、重传等机制确保接收节点正确收到每一个帧（停-等、GBN、SR)
  • 低误码率链路（如光纤、某些双绞线）上很少使用，高误码率链路（如无线链路）应当使用
• 流量控制
  • 调节发送速度，避免接收节点缓存溢出
  • 提供可靠交付的链路层协议，不需要专门的流量控制
  • 不提供可靠交付的链路层协议，需要流量控制机制
• 半双工和全双工
  • 半双工通信时，提供收/发转换

链路层的实现

• 路由器：链路层在线卡（line card）中实现

• 主机：链路层主体部分在网络适配器（网卡）中实现

• 线卡/网络适配器连接物理媒体，还实现物理层的功能

链路层由硬件和软件实现：

• 网卡中的控制器芯片：组帧、链路接入、检错、可靠交付、流量控制等
• 主机上的链路层软件：与网络层接口，激活控制器硬件、响应控制器中断等
  

网络适配器之间的通信

检错和纠错

传输出错的类型：

• 单个错：由随机的信道热噪声引起，一次只影响1位
• 突发错：由瞬间的脉冲噪声引起，一次影响许多位，使用突发长度表示突发错影响的最大数据位数

差错控制编码的类型：

• 检错码：只能检测出传输错误的编码，不能确定出错位置，通常与反馈重传机制结合进行差错恢复
• 纠错码：能够确定错误位置并自行纠正的编码

一些术语

• 码字（codeword）：由$m$比特的数据加上$r$比特的冗余位（校验位）构成
• 有效编码集：由$2^m$个符合编码规则的码字组成
• 检错：若收到的码字为无效码字，判定出现传输错误
• 海明距离（Hamming Distance）：两个码字的对应位取值不同的位数（等长的）
  • 比如，100和101的海明距离为1
• 纠错：将收到的无效码字纠正到距其最近的有效码字

检错码与纠错码的能力都是有限的!

编码集的检错与纠错能力

• 编码集的海明距离：编码集中任意两个有效码字的海明距离的最小值
• 检错能力：为检测出所有d比特错误，编码集的海明距离至少应为d+1
• 纠错能力：为纠正所有d比特错误，编码集的海明距离至少应为2d+1

差错检测过程

• 发送端对要保护的数据D（包括帧头字段）生成校验位EDC，添加在帧头（尾）中

• 接收端对收到的数据D’计算校验位，与收到的校验位EDC’比较，不同则判定有错
  

奇偶检验

奇偶检验的原理：

1. 偶校验（Even Parity）：如果数据中1的个数是偶数，则奇偶位设为0；如果数据中1的个数是奇数，则奇偶位设为1。这样，通过传输的数据中的1的个数加上奇偶位的值总是偶数。
2. 奇校验（Odd Parity）：如果数据中1的个数是奇数，则奇偶位设为0；如果数据中1的个数是偶数，则奇偶位设为1。这样，数据中的1的个数加上奇偶位的值总是奇数。

循环冗余校验（CRC）

CRC（Cyclic Redundancy Check）是一种非常常见的错误检测技术，广泛应用于网络通信和存储设备等领域，用来检测数据在传输或存储过程中是否发生了错误。

原理：

CRC的基本思想是将数据视为一个大整数，使用一个固定的“生成多项式”来除这个大整数，从而得到一个校验码（即CRC值）。这个校验码会附加在数据后面一起传输，接收方在接收到数据后，再使用相同的生成多项式进行除法运算，如果结果是零，则说明数据传输过程中没有发生错误；否则，数据就被认为是有错误的。

生成多项式：

CRC使用的生成多项式是一个二进制数，也叫做“生成多项式”（generator polynomial）。它通常表示为一个带有系数的多项式。例如，CRC-32（最常见的CRC标准之一）使用的生成多项式如下：

$G(x)=x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^2+x+1$

在二进制表示中，生成多项式为：
100000100110000010001110110110111

生成多项式的选择影响CRC算法的性能和错误检测能力。

CRC的计算过程：

假设我们要传输的数据为 $D(x)$，CRC的计算过程分为以下几步：

1. 数据与生成多项式对齐： 将数据$D(x)$ 与生成多项式 $G(x)$对齐，通常是将数据的最低位（最右边的位）与生成多项式的最高位对齐。
2. 附加校验位： 在数据的末尾附加若干个零，零的个数与生成多项式的阶数相同（例如，CRC-32是32位，因此附加32个零）。
3. 除法运算： 使用二进制除法对数据进行除法运算（异或运算），除数是生成多项式。将数据除以生成多项式，得到的余数就是CRC校验值。
4. 校验值： 将计算得到的余数附加到原数据末尾，作为CRC校验值，形成最终的传输数据。
5. 接收方校验： 接收方接收到数据后，使用相同的生成多项式进行除法运算。如果余数为零，则说明数据没有错误；如果余数非零，则说明数据发生了错误。

为什么链路层使用CRC，而其上各层使用checksum？

• 硬件实现
• 软件实现