数据链路层 —— MAC 子层
MAC 子层
什么是 MAC 子层？
MAC（Medium Access Control）子层，是数据链路层的一部分，主要负责在物理介质上传输数据包。
在 OSI 模型中，数据链路层被分为逻辑链路控制（LLC）子层和媒体访问控制（MAC）子层，其中：
LLC 子层负责管理服务质量，例如流量控制和错误检测（不同于MAC层的错误检测）。这包括重发机制，以确保信息的正确传输等；而 MAC 子层处理物理地址（MAC 地址），用于在同一网络内识别设备，它负责封装数据，在数据包周围添加帧头和帧尾，包括源和目的地的物理地址。
总结来说，LLC 子层主要负责管理链路层与网络层之间的接口和服务质量，而 MAC 子层则集中于物理地址的处理、数据帧的封装和媒体访问控制。这种分层使得数据链路层可以灵活地支持多种不同类型的物理网络技术，同时为上层网络提供统一的接口和服务。
媒体访问技术
两类常见的媒体访问技术：
预约协议（Reservation Based Protocol）
- 需要知道网络的拓扑结构
- 无冲突（Collision Free）
Eg：令牌环、TDMA
争抢协议（Contension Based Protocol）
- 不需要知道网络的拓扑结构
- 各个节点会竞争资源，可能产生冲突
Eg：ALOHA、CSMA
令牌环
一种古老的技术，定义了一种短帧，称为令牌（Token）。令牌环网络的拓扑结构呈环状，所有计算机连接成一个闭合的环路。每台计算机都直接连接到环上，并通过物理介质（通常是双绞线或光纤）相互连接。在令牌环中令牌以固定速率在网络中沿着环路传递。只有拥有令牌的计算机才能发送数据，其他计算机必须等待令牌传递到它们之前才能发送。
- 优点：不会产生冲突
- 缺点：一个节点失效会影响到整个信道
TDMA
TDMA（Time Division Multiple Access）技术将传输过程分成不同的时槽（Time Slot），每个时槽只允许一个用户传输信息。TDMA 在大多数 2G 系统中使用。
优点：和令牌环一样，TDMA 也能避免冲突
缺点：某个节点如果长期没有请求，则可能造成信道浪费
ALOHA
不同于令牌环和 TDMA，ALOHA 属于冲突协议，即每个节点会竞争资源。
纯 ALOHA
纯 ALOHA 协议相当简单，它是一种无协商（Without coordination）的协议，每个节点可以在任意时刻传输信息，如果在规定时间没有收到 ACK，则重传该帧。
想象一根总线拓扑结构，所有节点可以在任何时刻传输信息，则无可避免会产生冲突：
当两个不同的节点在同一时刻传输信息就会发生冲突，脆弱时间（Vulnerable Time）等于 \(2 \times T_{fr}\)，这里的 \(T_{fr}\) 指帧传递时间（Frame transmission time）。
Slotted ALOHA
时槽 ALOHA（Slotted ALOHA）就是在纯 ALOHA 协议的基础上，把时间段分为许多等长的时槽，每一帧只允许在时槽的起始点开始传输，这么设计之后，所有的帧要么错开（Miss），要么重合（Overlap）。
脆弱时间：\(T_0\)，这里的 \(T_0\) 指时槽的长度。
CSMA
CSMA，全称 Carrier Sense Multiple Access，这里的 Carrir Sense 指的就是监听信道，其基于一个假设，就是节点可以监听信道是否空闲。
传统 CSMA
- 如果信道是空闲的（Idle），节点会传输信息
- 如果信道是繁忙的（Busy），节点则会一直等待直到信道空闲
这是否意味着 CSMA 就不会产生冲突呢？答案是否定的，如果两个节点恰巧在同一时刻传输帧，则会发生冲突：
和 ALOHA 一样，CSMA 通过 ACK 确定是否发送冲突，如果节点在发送帧后未在指定时间内收到 ACK，则确定为帧可能发生冲突或出错，则重传帧。
脆弱时间：\(\tau\)，\(\tau\) 在这里指传输时延。
CSMA 还可以分为两种类型：
非坚持 CSMA（Nonpersistant CSMA）
在非坚持 CSMA 中，如果节点检测到信道是繁忙的，则会随机等待一定的时间，然后重新监听信道。
坚持 CSMA（Persistant CSMA）
在坚持 CSMA 中，如果节点检测到信道是繁忙的，则会一直监听信道直到信道变得空闲然后传输帧。
在坚持 CSMA 中，还可以细分两类：
1-坚持 CSMA（1-persistent CSMA）
检测到信道空闲，则立马发送帧
在低负载的情况下可以实现高吞吐量（High throughput）和低时延（Low delay），而在高负载的情况下可能会造成低吞吐量，因为所有节点在信道空闲的时候都会争抢着发送帧，跟有可能造成冲突。
p-坚持 CSMA（p-persistant CSMA）
检测到信道空闲，以概率 p（0 < p < 1）发送帧
在高负载的情况下可以实现高吞吐量。但其在低时延的情况下可能会增大时延。
CSMA/CD
CSMA/CD（Carrier Sense Multiple Access with Collision Detection），在 CSMA 的基础上添加了冲突检测（Collision Detection）。
这是什么意思呢，就是说在 CSMA 的基础上给了节点能够在传输过程中检测到冲突的能力，一旦检测到冲突，改节点会立刻舍弃此次传输。具体来说步骤如下：
- 如果冲突被检测，则取消传输（Cease transmission）并且传输一个强化信号（Jam signal）而不是传递完整个帧。
- 在发送强化信号之后，节点随机等待一段时间然后重新开始，这一步我们称为退避（Back-off）。
- 使用这个机制，可以节约时间和带宽。
CSMA/CD 最差情况下每个节点要多长时间检测到冲突：答案是 \(2 \times \tau\)。
假设节点 A 和节点 B 是分布在总线上两端的两个节点，A 在检测到信道空闲后发送帧，在即将到 B 时 B 也发送了一帧，此刻发送冲突，A 需要两倍传输时延才能检测到冲突。
指数退避（Exponential Back-off）
在检测到冲突后，节点会退避并且重新等待一段随机时间。这里的随机时间是如何定义的呢？
我们定义 \(K = min\{10, \text{number of attempt}\}\)，每次退避时从区间 \([0, 2 ^ k)\) 中随机选取一个整数作为退避系数 \(r\)，退避时间 = \(r \hat t\)，这里的 \(\hat t\) 表示基本重传时间（Basic retransmission time），一般是 51.2 \(\mu s\)。
在 16 次冲突后，改请求就会取消，这一帧会被舍弃。
完整流程：
参考协议：IEEE 802
IEEE 802 是一种包括了物理层和数据链路层的网络协议。不同的 IEEE 802 子标准针对不同的局域网和城域网技术，如以太网、无线局域网（Wi-Fi）、WiMAX 等，都基于这一模型进行规范和实现。
以太网
以太网（Ethernet）是一种常见的局域网（LAN）技术，用于在计算机和网络设备之间进行数据通信。以太网起源于 20 世纪 70 年代，是由 Xerox、Intel 和 Digital Equipment Corporation（DEC）共同开发的，后来被广泛采用，并成为最常见的局域网技术之一。
以太网支持多种数据传输速度，包括10 Mbps（常称为10BASE-T）、100 Mbps（100BASE-TX）、1 Gbps（1000BASE-T）和更高速度。IEEE 802.3系列标准定义了以太网的规范，不同速度的以太网遵循不同的 IEEE 802.3 子标准。
NIC
网卡（Network Interface Card，NIC），是一种用于建立和管理计算机连接到设备，其包含了物理层和数据链路层（LLC 与 MAC）的功能，每张网卡都有一个唯一的物理地址，称为 MAC 地址。
MAC 地址
每个 MAC 地址由 6 个字节组成，前 3 个字节表示供应商的标识符，后 3 个字节表示供应商提供的序列号。
Eg：1c:57:dc:68:23:0d
传统以太网
拓扑结构：逻辑上都是总线型的。
传统以太网比如 10Base-T 通过一个集线器（Hub）连接所有主机：
从上述结构可知，每一台主机发送的帧所有其他主机都可以接收，看上去拓扑结构是星型的，实际上还是总线型的。
使用的媒体访问技术：CSMA/CD
传统以太网使用 CSMA/CD 作为媒体访问技术，更具体来说，使用的是 1-persistent CSMA/CD 技术，这个前文已经说过，再次就不赘述了。
以太网的数据帧
Preamble：前导码，用于时钟同步（Clock synchronization），SFD 用于标记帧的开始。
Address：包括目的地和出发地的 6 字节 MAC 地址，由于以太网是广播链路传播，因此地址是必须的。
如果 Destination address 的值为
FF:FF:FF:FF:FF:FF，那就说明该帧是发送给全部节点的，所有计算机都会接收。Type：指定帧的类型，IPv4 或 IPv6。
Data and padding：数据和填充，这部分的大小在 46 字节到 1500 字节。
这部分至少 46 字节就是为了保证整个帧大小不小于 64B，这么设计的目的就是让帧的传输时间不少于传输时延。否则 CSMA/CD 有时候将无法检测到冲突。
CRC：校错码。
交换以太网
交换以太网在传统以太网的基础上将集线器改成了交换机（Switch）。
与传统的以太网集线器（Hub）不同，交换机能够根据数据帧中的目标 MAC 地址，将数据帧有针对性地发送到正确的端口，而不是广播给所有连接设备。为了实现有针对性的数据帧交换，交换机维护一个 MAC 地址表，记录了各个设备的 MAC 地址与相应端口之间的映射关系。当数据帧到达交换机时，它会查找 MAC 地址表以确定如何转发数据帧。
集线器（Hub）属于半双工通信，这是因为它在数据传输方面有一些限制和局限性。半双工通信意味着在同一时间内，设备只能进行单向的数据传输，要么发送数据，要么接收数据，而不能同时进行发送和接收。
相比之下，交换机（Switch）是一种支持全双工通信的设备，因为它具有智能的数据帧处理功能，可以在不同的端口之间建立虚拟电路，允许同时进行双向通信。交换机更高效、可靠，并且不容易发生碰撞，因此在现代网络中广泛使用，取代了集线器。集线器通常仅用于旧的网络中或特定的测试和诊断场景中。由于在交换机中不存在资源的争抢，也就不需要像 CSMA/CD 这样的介质访问技术。
快速以太网
快速以太网（Fast Ethernet）是对传统以太网的升级，旨在提供更高的数据传输速度。
快速以太网支持 100 Mbps（兆位每秒）的数据传输速度，相对于传统以太网的 10 Mbps 来说，它提供了更快的网络连接速度。因此，它通常被称为 100BASE-T。
Gigabit 以太网
Gigabit 以太网是一种高速的以太网技术，提供了 1 Gbps 的传输速度，用于满足高带宽需求的各种应用，如企业网络、数据中心和多媒体传输。它是现代网络基础设施的关键组成部分，为快速和可靠的数据传输提供了支持。
无线局域网
为什么 CSMA/CD 不适用于无线通信？
CSMA/CD 不适用于无线通信是因为其可能产生两个问题：
隐藏基站问题（Hidden station problem）
如上图所示，假设 A 要传输帧给 B，于此同时 C 也要传输帧给 B，由于无线信号的范围覆盖问题，A 和 C 均不能接收到彼此的信号，因此 A 和 C 都无法检测到 B 处发生了冲突。
暴露基站问题（Exposed station problem）
如上图所示，B 要传输帧给 A，C 要传输帧给 D，C 在发送帧时检测到与 B 传输的帧发送冲突，于是便会立刻停止帧的传输。而事实上 C 传输帧给 D 不收到 B 的影响，因为 B 的帧无法传输到 D，实际上不存在冲突问题。
以上两种情况可以总结为在无线通信中检测不到冲突和错误判断了冲突。
MACA
为了解决隐藏站的问题，人们提出了 MACA（Multiple Access Collision Avoidance），不同于冲突检测，该技术强调冲突避免。
MACA 的具体是通过基站之间的握手机制实现的，步骤如下：
- 若 S 要传递帧给 R，那么首先 S 会传输一个称为 RTS 的帧
- 终点 R 收到 RTS 后，会传输一个 CTS
- S 接收到 CTS 后传输帧给 R
- R 成功接受帧后返回 ACK 给 S
具体流程
- A 与 B 建立通信，发送 RTS，C 和 E 收到 RTS 帧，接下来将保持沉默；
- B 收到 A 传输的 RTS，返回一个 CTS，D 和 E 收到 CTS 帧，接下来将保持沉默。
MACA 为什么可以解决隐藏站的问题？
节点只收到 CTS，未收到 RTS：节点在接收节点 R 的范围内，不在发送节点 S 的范围内，所以该节点是一个隐藏站，也就是说该节点在 S 到 R 的传输过程将无法传输信息。如上图，D 是一个隐藏站，在 A 与 B 通信的过程中会被沉默。
注意：MACA 无法解决暴露站的问题，如上图，C 是一个暴露站，其通信是不受到影响的，但其错误判断可能会产生冲突从而造成信道浪费。
LAN 架构
LAN 架构主要可以分为以下两个部分：
接入点（Access Point，AP）：
AP 是一种网络设备，通常是一个无线路由器或无线接入设备，用于创建一个无线局域网，比如基站。它允许无线设备（如笔记本电脑、智能手机、平板电脑）连接到有线局域网或互联网。AP 负责将有线网络信号转换成无线信号，并为连接到它的无线设备提供网络连接。它通常有一个或多个无线接口（通常是 Wi-Fi），以允许多个设备连接。
基本服务集（Basic Service Set，BSS）：
BSS 是一个概念，用于描述一个无线局域网中的基本单元。每个 BSS 由一个 AP（或无线路由器）和与之连接的无线设备组成。BSS 通常包括一个无线网络的一个小覆盖区域，所有连接到同一个 AP 的设备属于同一个 BSS。在同一个 BSS 内，设备可以相互通信。BSS 还有一个唯一的标识符，称为 BSSID，通常是 AP 的 MAC 地址，用于在网络中唯一标识一个 BSS。
Ad hoc
Ad hoc，也就是自组织网络，是一种无线 LAN 模式，其不依赖基站，这种网络只能通过节点的连接覆盖来将数据传输给其他节点，所有节点将自己组织成网络。
寻找可用节点的两种方法
被动扫描（Passive Scanning）
被动扫描是一种相对较简单的方法，其中无线设备只是监听周围的 Wi-Fi 信号，而不主动发送请求。它通常用于发现并显示附近可用的 Wi-Fi 网络列表，以供用户选择连接。无线设备在特定时间间隔内监听 Wi-Fi 信道上的信号帧，以检测是否有 AP 广播它们的信标帧（Beacon Frames）。这些信标帧包含有关 AP 的信息，如 SSID（网络名称）、BSSID（AP的MAC地址）、信号强度等。一旦设备收到信标帧，它就可以在扫描结果中列出相应的 Wi-Fi 网络，以便用户选择连接。
主动扫描（Positive Scanning）
主动扫描涉及到无线设备主动发送探测请求来查找附近的 Wi-Fi 网络。这个请求通常是一个 802.11 探测请求帧（Probe Request Frame），其中包含了设备想要连接的 SSID 信息。接入点在收到探测请求后，可以响应并发送一个探测响应帧（Probe Response Frame），其中包含有关网络的信息，如支持的加密方法、信号强度、频道等。主动扫描允许设备更主动地发现附近的Wi-Fi网络，而不仅仅是等待信标帧的广播。这对于设备在新环境中快速连接到 Wi-Fi 网络或在切换网络时非常有用。
CSMA/CA
CSMA/CA（Carrier Sense Multiple Access with Collision Avoidance）是一种用于无线通信的可以避免冲突的载波监听多路访问技术。
工作流程：
不同于 persistent CSMA，802.11 Sender 不会在信道空闲的第一时刻发送数据，而是等待一个时间段 DIFS（Distributed Inter-Frame Space）后发送数据。
如果检测到信道处于繁忙状态，则会随机等待一个退避时间。如果没有收到 ACK 应答，则认为产生了冲突或错误，此时会增大随机退避区间，这里的增加机制和 CSMA/CD 是一样的。
同时，802.11 Receicer 在收到数据帧后会等待一个时间段 SIFS（Short Inter-Frame Space）后再传输 ACK。
为了解决隐藏站和暴露站的问题，CSMA/CA 还可以使用 MACA 中的 RTS/CTS 握手机制：
802.11 帧结构
