数据链路层

数据链路层

数据链路层的功能

1. 物理链路：传输介质（0层） + 物理层（1层）实现了相邻结点之间的“物理链路”。
2. 逻辑链路：数据链路层需要基于“物理链路”，实现相邻结点之间逻辑上无差错的“数据链路（逻辑链路）”.
3. 组帧即是在定义数据格式。
4. 为防止在传输过程中帧丢失，在可靠的数据链路层协议中，发送方对发送的每个数据帧设计一个计时器，当计时器到期而该帧的确认帧仍未到达时，发送方将重发该帧。位保证接收方不会接收到重复帧，需要对每个发送的帧进行编号。

组帧

1. SOH：start of header
2. EOT:end of transmission
3. ESC:escape character

差错控制

码距

1. 码距指的是两个长度相同的编码（也称为码字）之间，对应二进制位不同的数量，也称为海明距离（或汉明距离）。
2. 对于某种校验码，其编码集中任意两个编码（码字）之间都存在码距，这些码距中最小码距就称为该编码集的码距
3. 求码距，可以直接两个编码相异或，得到的1的个数即为码距

编码集的码距决定了其是否能够作为校验码以及作为校验码时的检错（甚至纠错）能力

增大编码集的码距，可以把原本不具备检错能力的编码集变为具有检错能力的编码集

检错编码

奇偶校验码

循环冗余校验码

1. 循环冗余校验码（CRC，Cyclic Redundancy Check）
2. 带r个校验位的多项式编码可以检测到所有长度小于或等于r的突发性错误

• “突发长度（Burst Length）”：指从第一个出错位到最后一个出错位之间的总跨度（包含中间所有位）。中间即使有些位没出错，也算在“突发”的长度里。

接收端判断是否出错时，做法更简单：

把收到的整个比特串，也就是“原数据 + CRC 校验码”，再除以同一个生成多项式。

• 余数全0，未检测出错误
• 不是全0，检测到错误

纠错编码

流量控制与可靠传输机制

流量控制、可靠性传输与滑动窗口机制

停止等待协议

1. 在术语使用上，停止等待协议不属于“滑动窗口协议”范畴。

后退N帧协议（GBN）

1. GBN：Go-Back-N

选择重传协议（SR）

1. SR：Selective Repeat
2. W_R <= W_T是为了保证窗口的利用率。
3. NAK：Negative-Ackownledge

三种协议的信道利用率分析

1. ARQ：Automatic Repeat request
2. GBN、SR在理论上只要发送窗口足够大，是有可能达到100%信道利用率的。

信道利用率的核心本质就是一个简单的占比公式：

信道利用率 (\(U\)) = 有效发送数据的时间 / 一个完整的通信周期时间

第一步：计算一个“完整周期”的总时间（分母）

从发送方开始发送一个数据帧，直到它收到确认帧（ACK）并可以开始下一轮发送，这个完整过程经历了以下4个阶段：

1. 发送方发数据：将数据帧的所有比特推到信道上，耗时 \(T_D\)（数据帧传输时延）。
2. 数据在路上跑：数据在物理链路上传播到接收端，耗时单向传播时延，即 \(RTT/2\)。
3. 接收方发ACK：接收端将ACK帧推到信道上，耗时 \(T_A\)（确认帧传输时延）。
4. ACK在路上跑：ACK传播回发送端，耗时单向传播时延，即 \(RTT/2\)。

把它们加起来，总周期时间 = \(T_D + (RTT/2) + T_A + (RTT/2) = T_D + RTT + T_A\)。这就是所有公式的分母。

第二步：计算“有效发送时间”（分子）

区别不同协议的关键，就在于在这个总周期里，发送方到底有多长时间在真正干活（发数据）：

• 停等协议 (S-W)：

发送方发完1个帧就必须停下来“干等”ACK返回。所以在整个 \(T_D + RTT + T_A\) 的时间里，它真正在发数据的时间只有最初的那1个 \(T_D\)。

因此，公式为：\(U = \frac{T_D}{T_D + RTT + T_A}\)

• 回退N帧 (GBN) 与 选择重传 (SR)：

得益于滑动窗口机制，发送方不需要发一个等一个。如果发送窗口大小为 \(N\)，它可以在等第一个ACK回来之前，“一口气”连续发送 \(N\) 个帧。

那么在同样的一个总周期里，它实际发数据的时间就是 \(N\) 个帧的累计发送时延，也就是 \(N \times T_D\)。

因此，公式为：\(U = \frac{N T_D}{T_D + RTT + T_A}\)

注意： 正如图片提示的，如果算出来的 \(N T_D\) 大于了分母的总时间，说明发送方在整个周期里一刻没停地在发数据，此时信道利用率 \(U\) 达到最高，即 100%（利用率不能超过 1）。

介质访问控制

信道划分介质访问控制

1. 介质访问控制（Medium Access Control, MAC）:多个节点共享同一个“总线型”广播信道时，可能发生”信号冲突“。
2. TDM（Time Division Multiplexing）。为了实现TDM，必须满足：1. 介质的位速率（每秒传输的二进制位数）大于单个信号的位速率2. 介质的带宽大于结合信号的带宽。
3. 复用器：将各个节点发出的信号“复合”后传输到共享信道上
4. 分用器：将各个子频带信号“分离”出来。
5. 频分复用只能用于模拟信号
6. 注意是规格化，因此需要除以长度
7. CDM更常用的名字为CDMA。

随机访问介质访问控制

1. CSMA：Carrier Sense Multiple Access，即载波监听多路访问协议

CSMA CD协议

1. CD：Collision Detection(冲突检测)
2. 对最短帧长的理解：如果一帧数据太短，发送方可能会在冲突信号（Collision Signal）传回自己之前，就已经将数据全部发送完毕。一旦发送结束，网卡就会认为该帧已成功发送并将其从缓存中清除。但实际上，数据已在半路上与其他信号发生碰撞并损毁，这就造成了无法被检测到的丢包。就是从一头A传到另一头B，传输时间应该是一个最大单向传播时延，在这段时间里发送方要一直发，保证让别人能检测到冲突，若此时取极限，第一个bit马上到接收方B，但是还没到，此时接收方A也发出了数据产生了冲突，此时要将冲突信号传回出初始的发送方A，又是一个最大的单向传播时延，在此期间A还要不停的继续传，不能传完因为已经发生冲突了，当前传的数据是有问题的，不然会丢包，因此最小帧长公式由此而生：**RTT * 信道带宽 **

1. 先听后发，边听边发，冲突停传，随机重传
2. 对于为什么争用期是RTT：A向B传数据，在马上到B的时候B向A发出了数据，从A开始发数据到A收到B的数据需要一个来回，就是RTT。

\(2\tau\)（RTT） 是“能确认自己没撞上”所需的最小时间粒度。退避量若小于一个争用期，两个站就可能在彼此“还没发现对方”的窗口内再次冲出去，退避就形同虚设。

1. 5-4-3原则，五个网段、四个中继器、三台设备。
2. 通常退避时间为：从如下范围取一个随机数 * 固定时间片（通常取争用期，即RTT）

CSMA CA协议

1. CA：Collision Aviodance，冲突避免
2. AP：Access Point，接入点
3. RTS：Resquest to send //请求发送
4. CTS：Clear to Send //允许发送
5. 对于超过一定阈值的数据帧长度，就选择启用信道预约机制，因为重传一次开销太大。
6. 下图中推迟访问（自觉“禁言”）这段时间叫做NAV（Network Allocation Vector，网络分配向量），本质上就是一个“请勿打扰”倒计时器。同时，他也是虚拟载波监听技术实现的核心，因为无线网中存在着隐藏站的问题，无法保证监听一定正确，NAV这个“倒计时”就实现了类似监听的功能。
7. 持续期指的这个帧之后还需要持续多长时间，NAV是给站点设置的等待时间。
8. 需要注意的是AP作为网桥，不会把源MAC地址改为自己的地址。此处涉及802.11和802.3之间传输，建议看王道强化P5加场。

上图存在错误，右侧信道忙碌结束后应该经过一个DIFS后才可以让退避计数器减小

对于DIFS ，通常要求SIFS + 传播时延 < DIFS，防止在差错控制时发生信息冲突

令牌传递协议

1. MAU：Multistation Access Units，多站接入单元。
2. 没有数据要发送的节点收到令牌后将立刻传递下去而不能持有。
3. 一个站点收到自己发出去的数据帧时，它将不再转发该帧，并重新产生一个令牌

详细流程如下： 令牌环网的控制方式是“受控接入”。环网中有一个特殊的短帧叫令牌（Token），它就像一个“发言权”。

• 网络空闲时：没有站点要发数据，这个“发言权”不能丢，所以只有令牌帧在环路上空转（循环传递），等待有需要的站点来抓住它。
• 站点发送数据时：想要发数据的站点必须等令牌转到自己这里，然后把令牌帧“抓住”并修改成数据帧的头部，接着发送数据。
• 发送完毕后：数据绕环一圈回到发送站，发送站再产生一个新的令牌放回环路，恢复空闲状态。

局域网

局域网与IEEE 802

1. IEEE 802为局域网指定的标准相当于OSI参考模型中的数据链路层和物理层。其中的数据链路层又被进一步分为逻辑链路控制（LLC）和介质访问控制(MAC)两个子层。

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

以太网与IEEE 802.3

1. 做题时默认交换机连接的终端节点都可以全双工。
2. 集线器连接的节点，仅支持半双工。
3. 在曼彻斯特编码中，如果信号中间不跳变，就属于违规编码，当接收方检测到违规编码时，就知道帧已经结束。
4. 集线器属于物理层，所以没有MAC地址这一概念；而路由器，交换机是有的。
5. 只有同一个局域网下的各节点才属于同一个广播域。

吉比特以太网通常不采用曼彻斯特编码，而是8B/10B 编码。

注意此处

在现实中，我们通常规定最短帧长为64B，下图中除了数据需要18B，因此，数据部分最短需要46B，最长帧长为1518B - 18B = 1500B。如果是VLAN，因为VID，所以数据部分最短为46B - 4B = 42B；最长帧长为1518B + 4B = 1522B。

802.1Q VLAN 帧：

• 增加的开销： 在源 MAC 和类型字段之间插入了 4B 的 VLAN 标签（包含 TPID、PRI、CFI 和 VID）。此时，头部与尾部的总开销变为 18B + 4B = 22B。
• 最小数据部分的计算： 为了保证 CSMA/CD 协议的冲突检测机制（即最短发送时间必须大于等于争用期），最小帧长必须严格保持在 64B 不变。因此，数据部分长度的下限被压缩，计算结果为 64B - 22B = 42B。
• 最大帧长的计算： 为了不影响网络层，保证上层 IP 报文的 MTU 依然可以达到 1500B，数据部分的最大上限保持 1500B 不变。因此，最大帧长需要向外扩张，计算结果为 1500B + 22B = 1522B。

若目的地址不全为1，则称为单播帧，也就是指定目标的帧。

记忆：西游记魔改小曲

VLAN的基本概念与基本原理

1. VLAN建立在交换技术的基础上，以软件方式实现逻辑分组与管理。
2. VLAN是为局域网用户提供的一种服务，而不是一种新型的局域网。

IEEE 802.11无线局域网

1. 此处记忆地址1、2、3可以参考王道书。地址1和地址2分别表示接收地址和发送地址，这两个地址在传送时是会变的：
2. 如果是A -> AP（此处A、AP和B都表示各自的MAC地址,除了加粗部分）
   • AP就是接收地址，A就是发送地址
   • 而此时我们需要存储最终的地址B，所以AP把它放在了地址3，充当目标地址
3. 如果是AP -> B
   • B就是接收地址，AP就是发送地址
   • 而此时我们需要存储起始从哪来的地址A，所以AP把它放在了地址3，充当源地址
4. 小心别搞混了！！！802.3（有线以太网，只有目的 MAC 和 源 MAC）、802.11（无线局域网/Wi-Fi）、802.1Q（虚拟局域网 VLAN，4B的VTag）

广域网

广域网的基本概念

1. 广域网的通信子网主要使用分组交换技术。
2. 广域网的拓扑结构通常采用网状。

PPP协议

1. PPP：Point-to-Point Protocol(点对点协议)
2. 有连接不可靠。
3. PPP两端的网络层可以运行不同的网络层协议

PPP协议的工作过程

以太网交换机

1. 物理层和数据链路层
2. 对于由交换机连接的X Mbps以太网，N个用户，每个用户能占用的带宽为X Mbps。
3. 实际上是一个多端口的网桥。
4. 在标准以太网以及 408 考纲中，MAC 地址的标准长度固定为 48 位（6 字节）。

1. 共享式以太网和交换式以太网的区别就是前者使用集线器、后者使用交换机

对比维度	共享式以太网	交换式以太网
核心设备	集线器 (Hub)	以太网交换机 (Switch)
工作层次	物理层 (Layer 1)	数据链路层 (Layer 2)
冲突域 (Collision Domain)	整个网络是 1 个冲突域	每个端口是 独立的冲突域 (若有 \(N\) 个活跃端口，则有 \(N\) 个冲突域)
广播域 (Broadcast Domain)	1 个广播域	1 个广播域 (在未划分 VLAN 的情况下)
工作模式	仅支持半双工	支持全双工 (主流) 与半双工
带宽分配	所有端口共享总带宽 (若总带宽 \(B\)，\(N\) 台主机各分得 \(B/N\))	每个端口独占带宽 (若端口带宽 \(B\)，\(N\) 台主机总容量可达 \(N \times B\))
MAC层协议	必须严格依赖 CSMA/CD 进行碰撞检测	全双工模式下不使用 CSMA/CD（无碰撞发生）；半双工模式下仍需使用

习题笔记

1. 以太网设计的原则是简化通信，因此采用的是无确认、无连接的服务。
2. 无连接：以太网在发送数据之前，不需要“打招呼”建立连接。
3. 不可靠：接收方收到数据后，不会返回确认应答报文给发送方。无ACK。
4. 广播式网络使用共享的广播信道进行通信，通常是局域网的一种通信方式。局域网工作在数据链路层，因此可以不需要网络层，也就不存在路由选择问题。但是数据链路层使用物理层的服务必须通过服务接入点，数据链路层向高层提供服务也必须通过服务接入点。
5. 就交换技术而言，以太网采用的是分组交换技术。
6. 高速以太网的MAC帧结构与标准以太网的标准帧结构完全相同，以便升级和向后兼容。
7. 使用集线器连接的以太网

1. TCP/IP族主要包括TCP、IP、ICMP、ARP、RARP、UDP、DNS、FTP、HTTP，HDLC是ISO提出的一个面向比特型的数据链路层协议。