计网-数据链路层(3)

3.1 数据链路层的功能

数据链路层 使用 物理层 的 “比特传输” 服务，为 网络层 提供服务

物理链路：传输介质（0层）+物理层（1层）实现了相邻结点之间的 “物理链路” 。

逻辑链路：数据链路层需要基于 “物理链路”，实现相邻结点之间逻辑上无差错的 “数据链路（逻辑链路）

image-20261012164640438

3.2 组帧

主要问题：

  • 帧定界：确定帧的边界
  • 透明传输：接收方要能够取出 ”帧定界“ 的附加信息，把帧恢复原貌。

方法有：

  • 字符计数法
  • 字节填充法
  • 零比特填充法
  • 违规编码法

image-20261013182904941

image-20261013183434019

image-20261013184223938

违规编码法

利用物理层插入“违规信号”，标记帧的开头、结尾

image-20261013184414214

3.3 差错控制

image-20261013184745562

检错编码

奇偶校验

信息位：帧的“数据部分”

校验位（冗余位）：为了给帧的“数据部分”检错/纠错而附加的一些冗余比特

  • 奇校验：其整个校验码（有效信息位和校验位）中“1”的个数为奇数
  • 偶校验：其整个校验码中“1”的个数为偶数

校验位通过判断其余部分“1”的个数进行补充，使得符合奇校验码或者偶校验码。

缺点：无法检测出偶数位错误、无纠错能力

image-20261013185250456

循环冗余校验码（CRC码）

​ 数据发送、接收方约定一个“除数”,其实际上是一个生成多项式 (最高位和最低位必须为 $1$ )

生成多项式

  生成多项式就是用来把要进行防错处理的二进制码流进行转换生成校验码，然后接收方会收到原始的二进制码流和校验码，按照与发送方相同的多项式再次进行转换生成校验码，与发来的校验码进行比较。如果一致则说明接收到的二进制码流是正确的；反之则说明接收到的二进制码流包含错误。

​ $K$ 个信息位 + $R$ 个校验位 作为 “被除数”，添加校验位后需保证除法的余数为0。

​ 收到数据后，进行除法检查余数是否为0。若余数非0，说明出错，则进行重传或纠错

通过生成多项式和信息码求CRC码的步骤

  • 确定 $K$、$R$ 以及生成多项式对应的二进制码，其中校验位 $R$ = 生成多项式中的最高次幂。

  • 移位

    • 将信息码左移 $R$ 位，低位补 $0$

  • 相除

    • 对移位后的信息码，用生成多项式进行模2除法，产生余数

  • 检错, 判断余数是否为 0

image-20261013190426041

​ 进行模2除运算中（高位为1商1，否则商0），减法采用模2减运算（等同于模2加，即异或）

​ 设有 $K$ 个信息位，$R$ 个校验位，若生成多项式选择得当，且 $2^R\geq{K+R+1}$，则CRC码可纠正1位错。但一般只用来检错。

纠错编码

海明码

设计思路：将信息位分组进行偶检验$\rightarrow$多个校验位

​ 设有 $n$ 个信息位， $k$ 个校验位，则需要满足 $2^k\geq n+k+1$

n 1 2-4 5-11 12-26 27-57 58-120
k 2 3 4 5 6 7

海明码求解步骤

以信息位：1010 为例

  • 确定海明码位数

    • 设信息位$D_4D_3D_2D_1$，校验位$P_3P_2P_1$,对应的海明码为 $H_7H_6H_5H_4H_3H_2H_1$

  • 确定校验位分布

    • 检验位$P_i$放在海明位号位$2^{i-1}$的位置上

    • 信息位按顺序放到其余位置

    • $H_7$ $H_6$ $H_5$ $H_4$ $H_3$ $H_2$ $H_1$
      $D_4$ $D_3$ $D_2$ $P_3$ $D_1$ $P_2$ $P_1$
      1 0 1 0

  • 求校验位的值

    • 所有其二进制的第 $i$ 位为$1$的被检验数据位为第 $i$ 分组，$P_i$的值为第 $i$ 分组的异或和

  • 检错与纠错

    • $S_i = P_i\oplus{第i分组的异或和}$ $S_i$若为 $0$ 则正确
    • 我们将所有 $S_i$ 按顺序组成一个码，如果有一位不是 $0$ ，则这个码所表达的数字就是出错位置。如 $010$ 表示 $H_2$ 发生了跳变

注意：海明码也可按序号从小到大排序，反过来即可。

image-20261013193423708

​ 海明码具有 1 位的纠错能力 和 2 位的 检错能力 ，但无法区分是一位错还是两位错。需添加 全校验位 $P_i$ ，对整体进行偶校验:

  • 若 $S_3S_2S_1 = 000$ 且全体偶校验通过 $\rightarrow$ 成功
  • 若 $S_3S_2S_1 \neq 000$ 且全体偶校验失败 $\rightarrow$ 有 1 位错，可纠正
  • 若 $S_3S_2S_1 \neq 000$ 且全体偶校验成功 $\rightarrow$ 有 2 位错，需重传

下为求校验位的值的例子

image-20261013193637232

3.4 流量控制与可靠传输机制

流量控制与滑动窗口机制

发送窗口$W_T$：发送方当前允许发送的帧。发送窗口之外的帧，暂不允许发送。

接收窗口$W_R$：接收方当前允许接收的帧。若收到接收窗口之外的帧，直接丢弃。

​ 由接收方通过 “确认机制” 控制发送方的窗口向前滑动。从而实现流量控制。

可靠传输机制

停止-等待协议（S-W）

image-20261014152848440

​

帧的首、尾是一些控制信息，如：帧定界信息、校验码、帧类型、帧序号等。

​ 不存在帧失序问题

  • 若数据帧丢失，发送方计时器超时，发送方超时重传
  • 若确认帧丢失，接收方窗口移动到下一位，接收到发送方超时重传的重复帧后，丢弃重复帧，并返回重复帧的ACK
    • 用 0 1 编号就是为了让接收方辨别“重复帧”
  • 若数据帧有“差错”，接收方检测出差错，丢弃该帧，不发ACK，等待发送方超时重传

后退N帧协议（GBN）

image-20261014155000823

image-20261014155334830

若数据帧E丢失

image-20261014155904356

image-20261014155651843

​ 当确认帧丢失时，发送方计时器超时重传，接收方检测到不在接收窗口之内便丢弃，并返回最后一个正确帧的ACK。如果不满足 $W_T+W_R\leq 2^n$ ，则会发生序号错乱。

缺点：如果接收方收帧的速率很慢，或在信道误码率很高的情况下，可能会导致发送方的发送 进度经常需要“后退”，导致传输效率低下。

选择重传协议（SR）

image-20261016193934718

  • 发送窗口$W_T>1$，接收窗口 $1<W_R\leq W_T$ （发挥好性能，实际应用中常常$W_R = W_T$）
  • 确认机制
    • 确认帧：ACK_i
      • 若接收方收到 i 号帧，且无差错，需要返回确认帧 ACK_i
  • 重传机制
    • 超时重传
      • 若发送方超时未收到ACK_i，则仅重传 i 号帧，并重置计时器
  • 帧编号
    • 为了支持以上机制，至少需要 n bit 给帧“编号”
    • $W_T+W_R\leq2^n$
  • SR的特殊规则
    • 不支持 “累计确认”
    • 否认帧：NAK_i
      • 若接收方收到 i 号帧，但检测出有差错，需要丢弃该帧，并给发送方返回否认帧 NAK_i，并重置计时器
    • 请求重传：若发送方收到 NAK_i，则重传 i 号帧

image-20261016194430805

数据帧丢失的情况

image-20261016194519668

image-20261016194546387

image-20261016194741408

数据帧出错的情况

image-20261016195154120

image-20261016195312577

确认帧丢失的情况

image-20261016195544349

image-20261016195642444

image-20261016200358429

三种协议的信道利用率

S-W协议

U为信道利用率，2倍单向传播时延（往返时延）为RTT，$T_A、T_D$ 分别为确认帧和数据帧的传输时延

理想情况下：$U = \frac{T_D}{T_D+RTT+T_A}$

GBN协议/SR协议

理想情况下：$U = \frac{N\ T_D}{T_D+RTT+T_A}$

其中，$N$ 为发送窗口的大小

注意传输时延需要小于该分母，最大信道利用率1（公式不可生搬硬套）

术语补充

术语使用上，S-W协议不属于“滑动窗口协议”范畴

ARQ协议（自动重传请求协议）：包含S-W、GBN、SR，其中连续ARQ协议不包含S-W协议。

3.5 介质访问控制

介质访问控制（MAC）：多个节点共享同一个“总线型” 广播信道时，可能发生 “信号冲突”。

信道划分介质访问控制

TDM

时分复用（Time Division Multiplexing，TDM）

将时间分为等长的“TDM帧”，每个”帧”又分为等长的m个“时隙”（大小固定的时间片），将m个时隙分配给m对用户（节点）使用。

缺点

  • 每个节点最多只能分配到信道总带宽的 $\frac{1}{m}$
  • 如果某节点暂不发送数据，会导致被分配的“时隙”闲置，信道利用率低。

image-20261017193350201

STDM

统计时分复用（STDM），又称异步时分复用，在TDM的基础上动态按序分配时隙。

优点

  • 如需要时，一个节点可以在一段时间内使用全部带宽
  • 信道利用率更高

image-20261017193219106

FDM

频分复用（Frequency Division Multiplexing，FDM），是将信道的总频带划分为多个子频带（每个子频带之间存在隔离频带），每个子频带作为一个子信道，每对用户使用一个子信道进行通信。

  • 优点：各节点可用时发送信号；充分利用了信道带宽（Hz）
  • 缺点：FDM技术只能用于模拟信号的传输

image-20261017193758149

WDM

波分复用（Wavelength Division Multiplexing，WDM）——即光的频分复用

​ 复用器将各个节点发出的不同波长的光信号“复合”后传输到光纤上，分用器将不同波长得到光信号“分离”出来。

​ 光信号的频带范围（带宽）非常大，可划分多个子信道，因此适合采用WDM。

image-20261017193910374

CDM

在2G、3G时代常常采用CDM

image-20261017194424132

image-20261017194651911

规格化内积例子：

image-20261017194949804

由于互相正交，不怕叠加向量中其他向量的干扰

随机访问介质访问控制

ALOHA协议

Additive Links On-line Hawaii Area

事实上，aloha为夏威夷语，表示爱、感情、和平、同情和怜悯词，常用作问候语

纯ALOHA协议

  • 如果准备好数据帧，就立即发送，如果冲突，接收方就会检查出错误并丢弃，发送方随机等待一段时间后尝试重传。

时隙ALOHA

  • 时隙大小固定 = 传输一个最长帧所需时间
  • 只有在每个时隙开始时才能发送帧
  • 避免了用户发送数据的随意性，降低了冲突概率，相对提高了信道利用率

CSMA协议

CSMA协议，即载波监听多路访问协议

​ 在发送数据之前，先监听信道是否空闲，只有信道空闲时，才会尝试发送

1-坚持CSMA协议

  • 准备好数据帧后，信道若不空闲则一直监听，否则立刻发送到信道
  • 如果冲突，则随机推迟一段时间后尝试重传
  • 优点：信道利用率高
  • 缺点：多个数据准备好数据时，冲突概率大

非坚持CSMA协议

  • 准备好数据帧后，监听信道，若不空闲则放弃监听信道，随机推迟一段时间再重新尝试监听。若信道空闲则立刻发送数据帧
  • 如果冲突，则随机推迟一段时间后尝试重传
  • 优点：错开发送，降低了冲突概率
  • 缺点：相对的信道利用率降低

p-坚持CSMA协议

  • 坚持监听，但空闲时只有p的概率会发送，1-p的概率随机推迟一段时间尝试
  • 如果冲突，则随机推迟一段时间后尝试重传
  • 优点：降低冲突概率的同时，提升信道利用率

🌟CSMA/CD协议

用于早期有线以太网（总线型）

CD指冲突检测

基于1-坚持CSMA协议

image-20261017201201480

争用期 = $2 \times$ 最大单向传播时延

  • 若争用期内未发生冲突，就不可能再冲突
  • CSMA/CD没有ACK机制，若未检测到冲突，就认为帧发送成功

争用期示意图如下：

image-20250622164828037

image-20261017211224718

最短帧长 = $2\times$ 最大单向传播时延 $\times$ 信道带宽

  • 若收到的帧小于最短帧长，视为无效帧

最长帧长：规定最长帧长可防止某些节点一直占用信道

以太网 规定：最短帧长=64B；最长帧长=1518B

CSMA/CA协议

难点但非重点

用于 IEEE 802.11 无限局域网（WiFi）

CA为冲突避免

发送过程中不用检测冲突，发送前想办法尽量避免冲突

AP（Acess Point）——接入点，也就是平常连接的无线WiFi热点。

切换WiFi热点——漫游

家用路由器 = 路由器 + 交换机 + AP

校园网 = 路由器 + n个交换机 + n*m个AP

为什么在无线网络中不采用CSMA/CD协议？

  • 硬件上很难实现“边听边发”——接收信号的强度往往远小于发送信号的强度，且在无线介质上信号强度的动态变化范围很大。
  • 存在“隐蔽站”问题——在无线通信中，并非所有站点都能听见对方。发送节点处没有冲突并不意味着在接收结点处没有冲突。
    • e.g. A无法监听到B、C的信号，B、C对于A就是“隐蔽站”

image-20261017212345975

image-20261017211658843

image-20261017212837707

解决“隐蔽站”问题需要引入信道预约机制（可选）

  • 发送方广播RTS控制帧（先听后发，忙则退避）

  • AP广播CTS控制帧

    需要在RTS、CTS中指明预约时长

  • 其他无关节点收到CTS自觉**“禁言”**一段时间(即：虚拟载波监听机制)；发送方收到CTS后，就可以发送数据帧

  • AP收到数据帧后，进行CRC校验，若无差错就返回ACK帧

image-20261017214126897

轮询访问

令牌环网技术：IBM公司于1984开发的一种局域网技术

（已淘汰）

image-20261017220015324

3.6局域网

局域网的基本概念与体系结构

局域网

  • 为一个单位所有，且覆盖较小的地理范围
  • 较低的时延和误码率
  • 局域网内之间各节点以“帧”为单位进行传输
  • 能进行单播、广播、多播

分为有线局域网和无线局域网（WLAN）

​ 局域网的特性主要由三个要素决定：拓扑结构、传输介质、介质访问方式，其中最重要的是介质访问控制方式，它决定着局域网的技术特性。

image-20261019161301513

image-20261019161147278

​ 常见的局域网拓扑结构主要有以下 4 大类：1. 星形结构 2. 环形结构 3. 总线形结构 4. 星形和总线形结合的复合型结构

​ 局域网可以使用铜缆、双绞线和光纤等多种传输介质，其中双绞线为主流传输介质。

​ 局域网的介质访问控制方法主要有CSMA/CD协议、令牌总线协议和令牌环协议，其中前两种协议主要用于总线形局域网，最后一种用于环形局域网。

​ 三种特殊的局域网拓扑实现如下：

  • 以太网（目前使用最广）：逻辑拓扑是总线形结构，物理拓扑是星形结构
  • 令牌环：逻辑拓扑是环形结构，物理拓扑是星形结构
  • FDDI（光纤分布数字接口）：逻辑拓扑是环形结构，物理拓扑是星形结构

IEEE802标准定义的局域网参考模型只对应OSI的物理层和数据链路层，并将数据链路层拆分为两个子层：**逻辑链路控制（LLC）子层 **与 介质访问控制（MAC）子层

​ 每个节点具有唯一的MAC地址，可依此实现多播。

局域网的分类：

  • 有线局域网

    • 令牌环网：1.环形 2.同轴电缆或双绞线 3.令牌传递协议

    • 以太网/802.3

      • 同轴电缆以太网(早期,1982)：1.总线形 2.同轴电缆 3.CSMA/CD协议

      • 双绞线以太网(1990)

        • 用集线器连接：1.物理上星形，逻辑上总线形 2. 双绞线 3. CSMA/CD 协议

        • 用交换机连接：1.星形结构 2.双绞线 3. CSMA/CD或NULL（半双工模式采用协议，全双工则不需要）

          注：不是所有网线都会使用4对双绞线（支持全双工通信），早期网线只包含1对双绞线（只能支持半双工）

      • 光纤以太网(1993)：1. 点对点 2.光纤 3. NULL（用两条光纤实现全双工通信）

  • 无线局域网（WLAN）

    • WiFi/802.11：1.星形（1个AP+N台移动设备）2.无线 3.CSMA/CA协议

局域网的硬件架构

  • 网线连接局域网

    • 以太网适配器（网线插口背后的芯片）
      • 其中ROM芯片指明全球唯一的MAC地址（物理地址，48bit,其中高24bit产商号由IEEE分配）
      • RAM芯片用来帧缓冲（即将发送或接收的局域网帧数据会暂存在RAM中）

  • WiFi连接局域网

    • WiFi网络适配器（民间称为无线网卡）
      • RAM（帧缓存）
      • ROM存放MAC地址
      • 内置WiFi天线接收电磁波模拟信号

网络适配器（网络接口卡，网卡）

  • 负责把帧发送到局域网
  • 负责从局域网接收帧（有些系统由主机实现）
  • 根据接入局域网类型，按标准实现数据链路层+物理层功能
  • 需要完成数据的串/并行转换
  • 需要支持帧缓冲

以太网与IEEE 802.3

image-20261019182525866

物理层

image-20250622232712622

光纤只能支持全双工

同轴电缆只能支持半双工通信

双绞线

  • 速率<2.5Gbps可支持半双工或全双工
  • 速率>=2.5Gbps仅支持全双工
  • 一般配合交换机/集线器

如果一个网段工作在半双工模式下，才需要使用CSMA/CD协议实现介质访问控制

image-20261019162055077

介质访问控制子层MAC层

  • DEC、Intel、Xerox 推出的 DIX Ethernet V2 标准
  • IEEE 802.3推出的 IEEE 802.3标准

V2标准

记忆口诀662N4 收发协数验

N：46~1500

image-20261019162614684

802.3标准中，协议类型变为数据长度

一个链路层数据帧能承载的最大数据量称为最大传送单元（MTU）

重点：单播帧、广播帧如何传播？

单播帧

集线器传给所有连接的节点，节点自己判断是否接收，交换机会传给对应MAC地址的节点。

广播帧

目的地址全1

image-20261019181924668

image-20261019182223385

VLAN(虚拟局域网)

由IEEE 802.1Q负责

一个大型局域网面临的问题

  • 一个节点发出的广播帧，都会被广播至所有节点。可能出现“广播风暴”
  • 不安全，局域网内可能会有一些敏感节点

VLAN

  • 可将一个大型局域网分给成若干个较小的VLAN，每个VLAN是一个广播域

    • 需要支持VLAN功能的以太网交换机来实现

  • 每个VLAN对应一个VID

image-20261019183257060

划分方式

  • 基于接口（交换机内的数据结构，记录VID和接口号的映射关系）
  • 基于MAC地址（交换机内的数据结构，记录VID和MAC地址的映射关系）
  • 基于IP地址（交换机内的数据结构，记录VID和IP地址的映射关系）
    • 这种方式可以让VLAN范围跨越路由器，让多个局域网的主机组成一个VLAN（需要网络层功能支持）

image-20261019183604722

image-20261019183807639

image-20261019184009136

帧的作用

  • 如果帧的传输跨越交换机，需要指明VID
  • 主机与交换机之间，传输标准以太网帧
  • 交换机与交换机之间，传输802.1Q帧

802.1Q帧的结构

在标准以太网帧的源地址之后，插入VLAN标签（4字节），得到802.1Q帧

VLAN帧指明发送方所属VID

image-20261019184422823

无线局域网/IEEE 802.11

分类

  • 由固定基础设施无线局域网 —— 802.11无线局域网（WiFi）
  • 无固定基础设施移动自组织网络 —— （看书了解即可，非重点）

802.11 无线局域网

家用路由器 = 路由器 + 以太网交换机 + AP

通过门户（Portal）设备将两类局域网连接，变成一个更大的局域网

image-20261019185346809

  • 扩展服务集ESS：将多个AP连接到同一个分配系统，组成一个更大的服务集
  • 漫游：一个移动站从一个基本服务集切换到另一个基本服务集，仍然可以保持通信

802.11帧的分类

  • 数据帧
  • 控制帧：如ACK、RTS、CTS帧
  • 管理帧：如 探测请求/探测响应帧（用于发现WiFi）

数据帧

image-20250624001256074

去往AP时，地址1为AP地址，地址2、3为源地址、目的地址

来自AP时，地址1为目的地址，地址2、3为AP地址、源地址

AP和AP、以太网、路由器之间一般通过有线链路连接

控制帧格式

image-20250624001954862

3.7广域网

跳过（王道视频还没做）

3.8 以太网交换机

以太网交换机

  • 特点

    • 交换机=多端口网桥(408大纲已删除网桥)

    • 交换机工作在数据链路层，可以根据目的MAC地址转发帧

  • 自学习功能（支持即插即用）

    • 交换表
      • 初始为空，记录【MAC地址，端口号】的对应关系
    • 每收到一个帧，就将发送方的【MAC地址，端口号】更新到交换表
      1. 如果不知道接收方位置，就把帧广播到除入口外的其他端口
      2. 如果知道，就把帧精准转发至某个端口
    • 交换表中每个表项都有“有效时间”，过期表项自动作废（防止某些节点拔线跑路）

  • 两种交换方式

    • 直通交换
      • 只检查帧的目的MAC地址，以确定帧的转发端口
      • 优点：转发时延低
      • 缺点：不适用于需要速率匹配、协议转换或差错检测的线路
    • 存储转发交换
      • 先把帧完整地接收到交换机内部的高速缓存中，进行差错检测等必要处理，再根据交换表决定从哪个端口转发出去
      • 优点：适用于需要速率匹配、协议转换或差错检测线路
      • 缺点：转发时时延高