计算机网络(5)——数据链路层

1.概述

数据链路层负责一套链路上从一个节点向另一个物理链路直接相连的相邻节点传输数据报。换言之，主要解决相邻节点间的可靠数据传输

节点(nodes)：路由器和主机
链路(links)：连接相邻节点的通信信道

2.数据链路层服务

2.1 组帧

组帧(framing)：将来自网络层的IP数据报构造成数据帧，添加首部(帧起始标志、地址信息)和尾部(校验序列)

典型帧格式： [起始符][地址字段][控制字段][数据][CRC校验/FCS][结束符]
注意：以太网标准规定，最小帧长度必须为64字节，所以最小数据长度=64-目的MAC(6)-源MAC(6)-类型(2)-FCS(4)=46

2.2 帧同步

帧同步：确保接收方能够正确识别数据帧的起始和结束位置的过程。常见的帧同步方法：

比特填充的标志比特法(Bit Stuffing)：使用一个特定的比特序列(如01111110)来标志帧的开始和结束
发送方：如果数据中出现连续的5个1比特，则直接插入1个0比特
接收方：当出现连续的5个1比特时

• 如果下一比特是0，则为有效数据，直接丢弃该0比特
• 如果下一比特是1，则连同后一位0比特构成定界符

2.3 介质访问控制

介质访问控制(MAC)：当多个节点共用同一条链路时，MAC决定了多个设备如何共享传输介质

2.4 寻址

寻址(Addressing)：在数据链路层使用物理地址(MAC地址)进行设备寻址，确保数据能够正确地传输到目标设备

MAC地址(Media Access Control Address)：用于在网络中唯一标识一个网络设备地地址

• 由48位二进制比特位组成，通常以12个十六进制数标识，每两个数字之间用冒号分隔。例如：00:1A:2B:3C:4D:5E
• 前24位(OUI，Organizationally Unique Identifier)：由IEEE(电气与电子工程师协会)分配个各个网络设备制造商，用于标识生产该网络设备的厂商
• 后24位(EUI，Extended Unique Identifier)：由制造商自行分配，用于区分同一厂商生产的不同设备

MAC寻址过程示例：主机A向主机D发送数据，途中经过路由器B和路由器C(这四个节点处于不同的网络段)

2.5 流量控制

流量控制(Flow Control)：协调发送方和接收端之间的数据传输速率，防止发送方发送速率过快导致接收方无法即使处理。常见方法：

• 停等协议(Stop-and-Wait)：发送方发送一帧等到接收方的确认，在发送下一帧
• 滑动窗口协议(Sliding Window)：允许发送方未收到确认的情况下发送多个帧，通过窗口大小控制发送速率(详细解释请移步计算机网络(3)——传输层)

2.6 差错控制

背景：信道的噪声导致的数据传输问题

• 1.差错(incorrect)：数据发生错误(发生比特翻转)
• 2.丢失(lost)：接收方未收到帧
• 3.乱序(out of order)：先发后至，后发先至
• 4.重复(repeatedly delivery)：接收方收到多个帧(由于传输层的超时重传机制)

解决办法：差错检测与纠正

• 1.在数据传输的过程中，检测帧中的比特错误，并在可能的情况下进行纠正

3.差错编码

概念：
数据链路层的差错编码(差错控制编码/信道编码)是确保数据在物理介质上可靠传输的核心技术。它通过在原始数据中添加冗余比特，使接收方能够检测甚至纠正传输过程中产生的比特翻转(如0变1或1变0)

• 检错码(Error Check Code)：主要用于检测数据传输或存储过程中是否发生了错误
• 纠错码(Error Correction Codes)：纠错码不仅能检测错误，还能纠正错误

核心功能：

• 1.差错检测：发现数据帧中是否存在错误
• 2.差错纠正：定位并修复错误比特(无需重传)
• 3.提高可靠性：降低因物理层不可靠导致的传输错误率

下面介绍几种主要的差错编码技术

3.1 奇偶校验

奇偶校验(Parity Check)：在数据中添加一个额外的校验位（奇偶位），使数据中“1”的个数满足奇数或偶数

• 奇校验：确保数据中“1”的总数(包括校验位)为奇数。如果原始数据中“1”的个数已是奇数，校验位为0；否则为1
• 偶校验：确保数据中“1”的总数(包括校验位)为偶数。如果原始数据中“1”的个数已是偶数，校验位为0；否则为1

奇校验示例：

缺点：

• 1.单比特错误检测：奇偶校验只能检测单个数据位或校验位的错误。如果数据中发生了奇数个位的错误，奇偶校验可以检测到；但如果发生了偶数个位的错误，奇偶校验将无法检测到
• 2.无法定位错误：奇偶校验只能告诉接收方数据中是否存在错误，但无法指出具体是哪个位发生了错误。这使得在检测到错误后，无法进行纠正，只能要求重传数据
• 3.误判：在某些情况下，奇偶校验可能会错误地认为数据有错误。例如，如果校验位本身发生了错误，而数据位没有错误，奇偶校验会认为整个数据有错误

3.2 循环校验

循环校验(Cyclic Redundancy Check，CRC)是一种在数字通信和数据存储中广泛使用的错误检测技术。它的核心目的是检测数据传输或存储过程中可能发生的意外改动(比特错误)，例如由噪声、干扰或硬件故障引起的错误

CRC校验码计算方法：
1.设原始数据D为x位二进制数字
2.使用预先定义好的生成多项式G作为除数

• 例如：CRC-16-CCITT的生成多项式是x¹⁶ + x¹² + x⁵ + 1，其二进制表示为1 0001 0000 0010 0001(通常简写为 0x11021)

3.生成多项式有y + 1位二进制数，最高次方为y，校验码的位数为y
4.将原始数据M乘以2^y(相当于在M后面添加y个0)
5.再用G对M做模2除(异或运算)，得到y位余数(不足y位前面用0补齐)，即为CRC校验码

CRC校验示例：

• 原始数据 (D): 11010011 (二进制)

• 生成多项式 (G): x⁸ + x² + x¹ + 1

  • 通常简写为 十六进制 0x107 (但计算时用 100000111 更直观)。

• CRC长度®: 8 位 (因为生成多项式最高次项是 x⁸)。

• 目标： 计算原始数据 11010011 的 CRC-8 校验码，并验证接收端如何检测错误。

---

步骤 1: 发送方计算 CRC 校验码

1. 在原始数据末尾附加 r 个 0：

   • 原始数据 D = 11010011
   • 附加 r=8 个 0： 11010011 + 00000000 = 1101001100000000

2. 进行模2除法 (XOR 除法)：

   • 被除数： 1101001100000000
   • 除数/生成多项式 (G)： 100000111 (9位)
   • 规则： 对齐除数最高位 1 到被除数当前最高位 1，做 XOR 操作。结果作为新的部分被除数，继续下移

   计算过程：

       1101001100000000  <-- 被除数 (原始数据 + 8个0)
   XOR  100000111         <-- 除数 (G) 第一次对齐最高位的1 (位置1)
   ----------------------1010000100000000  <-- 第一次 XOR 结果 (余数)100000111        <-- 除数右移对齐下一个最高位的1 (位置3)
   ----------------------100010100000000100000111       <-- 除数右移对齐 (位置4)
   ----------------------10110000000100000111   <-- 除数右移对齐 (位置7) (注意前面补了3个0)
   ----------------------110011100100000111 <-- 除数右移对齐 (位置8)
   ----------------------100110110100000111 <-- 除数右移对齐 (位置9)
   ----------------------1100100  <-- 最终余数 (8位)
   

   • 关键点：
     • 每次只对当前被除数中最高位的 1 进行对齐和 XOR。
     • XOR 操作是按位进行的，没有借位或进位。
     • 当除数位数大于剩余被除数位数时，除法停止。
     • 最后得到的余数位数必须等于 CRC 长度 r (8位)。如果不足，在前面补0。本例余数是 1100100，补足8位是 01100100 (前面加一个0)。

3. 得到 CRC 校验码：

   • 最终余数 01100100 (二进制) 就是计算出的 CRC-8 校验码。
   • 十六进制表示为 0x64。

4. 发送完整数据帧：

   • 发送方将 原始数据 + CRC校验码 一起发送出去：
     • 原始数据: 11010011
     • CRC 码: 01100100
     • 发送帧: 1101001101100100

---

步骤 2: 接收方验证数据 (无错误情况)

1. 接收数据帧： 1101001101100100

2. 使用相同的生成多项式进行模2除法：

   • 被除数： 接收到的整个帧 1101001101100100
   • 除数： 同一个 100000111
   • 目标： 计算余数是否为 0。

   计算过程：

       1101001101100100  <-- 接收到的完整帧 (数据 + CRC)
   XOR 100000111         <-- 除数对齐第一个1 (位置1)
   ----------------------1010000101100100100000111       <-- 对齐下一个1 (位置3)
   ----------------------1000101001100100100000111      <-- 对齐 (位置4)
   ----------------------10110010100100100000111  <-- 对齐 (位置7)
   ----------------------1100010000100100000111    <-- 对齐 (位置8)
   ----------------------100011110100100000111   <-- 对齐 (位置9)
   ----------------------110001100100000111 <-- 对齐 (位置12)
   ----------------------1000011  <-- 最终余数 100000111 <-- 位数不够除？停止！余数=1000011 (7位) -> 补0=01000011
   

   • 注意： 接收方计算时，除数会一直尝试对齐到数据末尾的 CRC 部分。
   • 最终余数： 经过完整的模2除法后，得到的余数是 01000011 (补足8位)。

3. 验证结果：

   • 计算得到的余数是 01000011 (二进制)，不等于 00000000。
   • 结论：数据在传输中发生了错误！

4.MAC

介质访问控制协议(Medium Access Control，MAC)负责解决多个设备共享同一通信信道时的冲突问题

MAC协议主要分为以下三类：

4.1 信道划分MAC

使用多路复用技术(FDM、TDM、WDM、CDM)
详细解析请见计算机网络(1)——概述中的3.1.2 多路复用

4.2 随机访问MAC

4.2.1 CSMA

载波监听多路访问协议(Carrier Sense Multiple Access，CSMA)：发送前先侦听，减少冲突概率。侦听/发送策略分类：

• 非坚持：侦听到忙->随机等待后重新侦听
• 1-坚持：侦听到忙->持续侦听
• p-坚持：侦听到忙->以概率p持续侦听；以概率(1-p)随机等待后重新侦听

冲突仍然可能发生：由于信号传播延迟
在t4/t5时刻之后，后续再发送数据已经没有意义了，但是CSMA协议一旦开始发送第一个比特，那么该数据就要发送完毕。这会导致不必要的资源浪费，所以基于CSMA提出了一改改进的CSMA/CD协议

4.2.2 CSMA/CD

CSMA/CD(Carrier Sense Multiple Access/Collision Detect冲突检测)：在CSMA协议的基础上增加了冲突检测机制

• 设备在发送数据的同时持续监听信道
• 能够即使发现数据传输过程中是否发生冲突
• 边发边听，不发不听
• t2时刻D检测到冲突后不再发送数据；t3时刻B检测到冲突后不再发送数据

冲突检测机制：

• 1.有线局域网易于实现：测量信号强度，比较发送与接收强度
• 2.无限局域网很难实现：信号衰减太快，接收信号强度直接淹没在本地发送信号强度下

场景假设：
某一空闲时间A发送数据，当数据即将到达B的临界时刻，B也开始发送数据；当B发送的数据到达A时，A才会检测到冲突。根据边发边听，不发不听的特性，如果B发送的数据到达A时，A已经完成数据发送的过程，那么A将不再检测冲突，所以要满足一个条件：L(min)/R >= 2d(max)/V

4.3 轮转访问MAC

/	信道划分MAC	随机访问MAC	轮询/令牌MAC
网络负载重时	共享信道效率高且公平	产生冲突开销	结合两者优点
网络负载轻时	共享信道效率低	共享信道效率高且单个节点可以利用信道的全部带宽	结合两者优点

4.3.1 轮询(Polling)

基本概念： 轮询是一种集中式的介质访问控制方法 由一个主节点(控制器)按顺序询问各个从节点是否有数据要发送

工作原理：

• 主节点定期向每个从节点发送轮询信号
• 从节点在被轮询时才能发送数据
• 主节点控制传输顺序和时机

特点：

• 确定性：传输顺序和时间是确定的
• 公平性：每个节点都有机会发送数据
• 简单性：实现相对简单
• 延迟可预测：传输延迟相对可预测

优点：

• 避免了冲突
• 适合实时性(数据从发送方到接收方传输的延迟)要求高的应用
• 易于管理带宽分配

缺点：

• 依赖主节点，主节点故障会导致整个网络瘫痪
• 效率可能不高，特别是在节点数量多或负载低时
• 延迟可能较大，特别是在节点数量多时

4.3.2 令牌环(Token Ring)

基本概念：令牌MAC是一种基于令牌的介质访问控制方法，使用一个称为"令牌"的特殊帧来控制网络访问

工作原理：
(1)令牌传递：

• 网络中只有一个令牌在循环传递
• 令牌是一个特殊的控制帧，授权节点发送数据

(2)节点访问流程：

• 节点想要发送数据时，必须等待令牌到达
• 节点接收到空闲令牌后，将其改为忙令牌
• 节点附加要发送的数据帧到忙令牌上
• 数据帧在环网中循环传递到目标节点

(3)数据接收：

• 目标节点复制数据帧
• 数据帧继续在环中传递，直到回到发送节点
• 发送节点移除数据帧，并将令牌恢复为空闲状态

主要特点:

• 确定性访问：每个节点都有确定的访问机会，避免了冲突
• 公平性：所有节点轮流获得访问权，避免了"饥饿"现象
• 效率：在重负载下表现良好，适合高密度网络
• 有序性：数据传输是有序的，避免了数据包的乱序问题

优点：

• 避免冲突：通过令牌机制完全避免了冲突，提高了网络可靠性
• 可预测性：传输延迟是可预测的，适合实时性要求高的应用
• 公平性：保证所有节点都有平等的访问机会，避免了某些节点独占信道的问题
• 稳定性：在高负载下性能稳定，不会出现CSMA类协议在高负载下效率急剧下降的问题

缺点：

• 复杂性：实现较为复杂，需要维护令牌环的完整性
• 单点故障：令牌丢失会导致网络瘫痪，需要额外的机制来处理令牌丢失问题
• 延迟：在轻负载下可能存在不必要的延迟，令牌传递本身会带来一定的开销
• 扩展性：随着网络规模扩大，令牌传递时间增加，可能影响整体性能

5.ARP协议

Question：在同一个LAN内，如何在已知目的IP地址的情况下确定其MAC地址？

地址解析协议(Address Resolution Protocol，ARP)：是一种用于解析网络层地址(如IP地址)和数据链路层地址(如MAC地址)的协议。它工作在网络层与数据链路层之间，通过广播请求和单播响应实现地址解析
ARP表：LAN中的每一个节点都会维护一张ARP表，用于存储该LAN中节点的IP地址和MAC地址的映射关系<IP地址；MAC地址；TTL>

• TTL(Time to Live)：表中每个条目/映射关系的有效时间(Windows系统默认值为120秒)

ARP工作原理：

• 请求阶段：当主机A需要与主机B通信时，若主机A的ARP缓存中没有主机B的MAC地址，主机A会发送一个ARP广播请求，询问“谁拥有IP地址X？”
• 响应阶段：主机B收到请求后，若IP地址匹配，会单播(利用单播帧)回复自己的MAC地址。主机A将这一映射存入ARP缓存