数据链路层可以细分成两个子层：

• 逻辑链路控制子层 LLC，Logic Link Control
• 介质访问控制子层 MAC，Medium Access Control

为什么要这样分呢？我们知道有三类通信方式：单播（unicast）、广播（broadcast）、组播（multicast）。在局域网中，传输介质是共享的，我们称这种信道是 广播信道 或 共享信道。为了避免终端同时占用信道造成冲突，就需要介质访问控制。

有两种分配信道的方式：

• 静态分配：每个用户预先分配，比如 FDM、TDM
  • 特点：会使得延迟增大 N 倍（N 是用户数），适用于用户数量少且固定的情况，或通信量大且流量稳定的情况，不适用于突发性业务。
• 动态分配：根据用户的使用来分配
  • 特点：利用多路访问协议动态分配信道，可提高信道利用率

多路访问协议又分为：

• 随机访问协议：站点争抢信道，比如 ALOHA、CSMA、CSMA/CD
• 受控访问协议：站点按一定顺序使用信道

ALOHA协议

ALOHA 协议是为了解决夏威夷和檀香山之间的无线信道上的通信而提出，这个名字来源于夏威夷人打招呼的用语。

ALOHA 协议分为：

• 纯 ALOHA 协议
• 分隙 ALOHA 协议

纯ALOHA协议

纯ALOHA协议的工作方式如下：

1. 生成一个帧后即可发送
2. 发帧的同时检测信道，判断是否发送成功
3. 若有冲突，则等一段时间后重发

我们将一个帧时¹内发送成功的平均帧数定义为 吞吐率 Throughout 或 利用率 $S$；一个帧时内所有通信站总共发送的帧的平均值定义为 运载负载 Carried Load $G$，指。$G$ 与 $S$ 的关系如下：

• $G=S$ 无冲突（待发=实发）
• $G>S$ 有冲突（待发>实发）
• $G>1$ 冲突频繁

此外，还有一个概念叫 $P_0$，指一帧发送成功（未发生冲突）的概率。显然，$S$，$G$，$P_0$ 三者满足：

我们可以用 $P_0$ 衡量多路访问控制协议的好坏。下面来说说怎么求纯 ALOHA 的 $P_0$。

假设帧时为 $t$（也就是发一帧需要的时间）。如果有一个帧在 $t_0$ 时刻发出，要不产生冲突，其他用户在 $[t_0-t,t_0+t]$ 内就不能发送帧，因此 冲突危险期 为 $2t$。

我们假设在一个帧时内，产生的帧的数量服从泊松分布：$\text{Pr}[k]=\dfrac{G^k }{k!}e^{-G}$，那么一个帧时内生成 0 帧的概率为 $\text{Pr}[0]=e^{-G}$。在冲突危险期内生成 0 帧的概率为：$\text{Pr}[0] \cdot \text{Pr}[0] = e^{-2G}$，所以 $P_0 = e^{-2G}$

我们将 $P_0$ 代入 $S=G\times P_0$，可以求出在 $G=0.5$ 时，信道的吞吐率最大，为 $18.4\%$

分隙 ALOHA 协议

分隙 ALOHA 协议（SLotted ALOHA）也叫分槽 ALOHA 协议。它在纯 ALOHA 协议的基础上增加了一个规定：将时间分成固定长的时隙，帧只能在时隙起点发送。

经过这种设定后，冲突危险期缩短至 $t$，（即$(t_0-t,t_0]$ 时间内不能生成帧）。从而，$P_0=e^{-G}$，最大吞吐率（利用率）为 $S_\max=36.8\%$

对比纯 ALOHA，分隙ALOHA的利用率大大提高😊

CSMA协议

CSMA，Carrier Sense Multiple Acess，载波侦听多路访问协议 的特点是：先听后发。可以分成两大类：

1. 非持续式：侦听到线路忙，就等待一个随机分布的时间再侦听。这样可以减少冲突，但会浪费时间。
2. 持续式：侦听到线路忙，就持续侦听，一旦空闲则再发送。没有浪费，但可能会有冲突。若发生冲突，则等待一段随机时间。
   1. 1-持续：就是下面的 CSMA/CD
   2. P-持续：若侦听到介质空闲，则以 P 的概率发送或以 1-P 的概率延迟，延迟后再重复这个步骤。

持续式会发生冲突的原因有两个：

1. 多个工作站侦听到空闲同时发送
2. 由于有传播延迟（帧传输的速度为 200m/us），侦听到空闲时，线路远处可能有帧发送

冲突窗口：检测到冲突的时间的最大值。假设信号的传输速度是 $v$，网卡延迟为 $t_p$，最远两个工作站相距 $S$，那么冲突窗口为：$2\frac{S}{v}+2t_p$（先发送，在最远处冲突，再返回），如果线路上还有中继器，那么还要加上中继器的延迟 $2(\frac{S}{v}+t_p+N\times t_\text{中继})$。

CSMA/CD 协议

CD 指 Collision Detection，全称是：带冲突检测的载波侦听多路访问协议，其工作方式是：

1. 先侦听，如果介质空闲，则发送；如果介质忙，则持续侦听，一旦空闲则立即发送；
2. 发送后，继续侦听，如果发生冲突，则立即停止发送，并发送一个强信号，称为 Jam信号，用来告知其他工作站。然后随机等待一段时间再重复 1。

冲突检测的原理是这样的：所有工作站在发送的同时也接收自己的信号，监测发送的情况，一旦收到的信号与发出的不一致，就说明发生了冲突。

要能检测到冲突，由两个要求：

1. 时隙宽度 = 冲突窗口（保证一个时隙内能检测到最远处的冲突）
2. 发送有效帧的时间 ≥ 冲突窗口（发生冲突时能有信号作为对比）

因此，CSMA/CD 对帧的长度有一定要求，取决于线路的传输速度。

CSMA 与 ALOHA 的效率总结如下：

无冲突的协议

位图协议

位图协议 也叫 预留协议，过程如下：

1. 如有N个站点共享信道，编号为0~N-1
2. 竞争周期将分为N个时隙，每个站点占有一个时隙，如某站准备发送，则可在属于它的时隙内填入1
3. 一个竞争周期后，则将按顺序发送，不会产生冲突

效率分析如下：若有 $N$ 个用户，则竞争周期有 $N$ bit，帧长为 $d$ bit，若仅有一个用户发送数据，则效率为 $d/(d+N)$；若所有用户都要发送，则效率为 $Nd/(Nd+N)=d/(d+1)$

最大延迟分析如下：若最后的第 $N-1$ 个用户要发数据，则要等待前面 $N+(N-1)\cdot d$ bit 发送完才能发。

缺点：位图协议无法考虑优先级

令牌传递

抓取到令牌的工作站可以发送一帧。除了环，令牌也可以运行在其它拓扑上。

二进制倒计数协议

把站号按相同长度的二进制数编号，需要发送 的站逐个按高位到低位在争用周期开始时发送， 凡低序号的站点发现有高序号站点也希望发送， 则退出竞争，即：高序号站点优先。

为什么叫倒数呢？是因为我们从编号的高位开始看，如果某个竞争站的高位是 1，那么高位为 0 的站就要退出竞争。然后我们再看下一位。

效率分析如下：如果有 $N$ 个站，那么编号有 $\log_2 N$ 位，即需要比较 $\log_2 N$ 次，最终只有一帧发送，帧长 $d$，所以效率为 $d/(d+\log_2 N)$

如果定义每个帧的帧头为发送地址，即竞争的同时也在发送。则效率为100%

有限竞争协议

有限竞争协议（Limited ContentionProtocol） 简单来说就是：

1. 在低负荷时使用竞争法，以减少延迟时间。
2. 在高负荷时，使用无冲突法，以获得高的信道效率。

为了实现上述过程，我们将站点进行分组（组之间允许重合），每组有一个时间槽，同一组的站点去争一个时间槽，如果竞争成功就发送，如果冲突就轮到下一组。

当每组的站比较少时，这个类似于位图协议；而当每组的站比较多时，这个类似于分槽 ALOHA 协议。

适应树搜索协议

适应树搜索协议（Adaptive Tree Walk Protocol），源自二战时，美军血液检查梅毒的方法，简单来说就是先将所有血液混在一起，如果检测出来，就减半。这个协议的过程如下：

1. 第一个竞争时隙（记为 $0$ 号槽），所有站点同时竞争
2. 如果只有一个站点申请，则获得信道。否则在下一竞争时隙，有一半站点参与竞争
3. 即将所有站点构成一棵完全二叉树。对二叉树作深度优先搜索

下图给出了一个例子：

以太网

以太网（Ethernet）最早是由 Xerox（施乐）公司创建的局域网组网规范，1980年DEC、Intel 和 Xeox 三家公司联合开发了初版 Ethernet 规范：DIX 1.0，1982年这三家公司又推出了修改版本 DIX 2.0，并将其提交给 IEEE 802 工作组，经 IEEE 成员修改并通过后，成为IEEE的正式标准，并编号为 IEEE 802.3。虽然 Ethernet 规范 和 IEEE 802.3 规范并不完全相同，但一般认为 Ethernet 和 IEEE 802.3 是兼容的。（考试的选择题遇到就选 DIX）

以太网分为：

• 经典以太网：3M~10Mbps，现在不常用
• 交换式以太网：10M、100M、1G，现在广泛使用

采用不同线缆的以太网的命名方式如下：

10Base2-TX
│  │  │  └─传输介质，TX指非屏蔽双绞线，F指光缆
│  │  └────传输距离，以 100m 为单位，四舍五入
│  └───────线路编码，这里指基带传输
└──────────传输速度，单位 Mbps

常用的以太网有：10Base5、10Base2、10Base-T，具体可以看 Ethernet（以太网）之二 物理介质（10Base、100Base-T、100Base-TX等），顺便说一句，现在用的就是 10Base-T.

10M以太网用的是曼彻斯特编码，也就是：从低到高跳变表示 0，从高到低跳变表示 1，所以10M以太网的波特率是带宽的两倍。快速以太网（100M）才用 4B/5B 编码。

以太网采用的是 CSMA/CD 协议，就是「先听后发，边听边发」。检测到冲突时，使用二进制指数后退算法确定等待时间，然后再发送。二进制指数后退算法如下：若发生第 $i$ 次冲突，则随机等待 $[0, 2^i-1]$ 个时隙，而以太网的时隙是 $51.2 {\mathrm \mu s}$，由 RTT（Round-Trip Time，来回传输时间）决定。

以太网把争用期设置为 51.2μs，这个时间的得来没有找到合适的答案，一个比较有说服力的说法是：端到端 5000m 时延需要 25μs，来回需要经过8个中继站，信号在中继站中转的途中也会消耗时间，总共约为 20μs，再加上发送强化冲突数据的时间一共 51.2μs。

如果发生了 16 次 冲突后依然没能成功发生，那么就不再发送，并向网络层报告。

以太网的帧格式

以太网的帧格式在 DIX 和 IEEE 802.3 中的定义略有差别。

802.3 帧的组成：

• 前导码：7个 10101010
• 帧起始符：10101011
• 目的地址（物理地址）
• 源地址（物理地址）
• 长度：不考虑前导码和帧起始符的长度。最短为 64 字节，最长为 1518 字节。
• 数据：LLC 数据，至少要 46 个字节，如果不够就要填充。
• 校验和：CRC 循环冗余校验，校验范围为除前导码和帧起始符外的字段

Ethernet 帧的组成：

• 前导码：8个 10101010
• 目的地址（物理地址）
• 源地址（物理地址）
• 类型：上层网络层使用的协议
• 数据：LLC 数据，至少要 46 个字节，如果不够就要填充。
• 校验和：32位 CRC 循环冗余校验，校验范围为除前导码和帧起始符以外的字段

一些解释：

物理地址（MAC 地址）一共有6个字节，用十六进制表示。前 3 个字节是 OUI，代表一个组织/公司，由 IEEE 分配，后 3 个字节则由网卡制造商设定。一般来说，全球的每个 MAC 地址是独一无二的。另外，除了单一结点地址外，还有组播地址和广播地址（全1）

如何区分是「长度」还是「类型」：根据数值大小，IEEE 规定类型要大于 1536（0x600），所以小于 1536 的就是长度。

最小帧长的由来：根据冲突检测的规定，$10\text{Mbps} \times 2 \times 51.2 \text{us} \div 8=64\text{Byte}$

关于以太网的信道利用率可以去看 Formula for calculating efficiency of ethernet，总的来说，帧长越大，效率越高。

快速以太网

快速以太网，又叫 100Mbps以太网 —— 802.3u：

• 改变编码方式：4B/5B编码
• 提高传输速率：使用五类双绞线 100Base-TX，波特率为 125MHz，（4bit/5）×125MHZ = 100Mbps

千兆以太网

时隙宽度 2t=最短帧长度 / 信道传输速率，若保持最短帧长64字节，则意味最大传输距离缩短，所以需要进一步扩充帧。有两种方法：

• 载荷扩充（carrier extension）
  • 方法：在发送方硬件加入/接收方硬件删除，将帧长扩展到512Byte(8倍)
  • 缺点：线路利用率低下
• 帧串（frame bursting）
  • 方法：连续发送多个帧，只有当帧串小于512Byte时填充
  • 目的：提高信道利用率

数据链路层交换

广播式网络的最大传输距离和可容纳最大站点数量决定了网络要分段。用同一传输介质连接起来的站点的集合称为一个 网段。

局域网间数据帧交换称为 L2 交换。L2交换设备是 网桥（交换机）。也就是说，网桥连接的是局域网，并基于 MAC 地址进行帧转发。（后面要学的路由器是基于 IP 地址）

如果两个局域网不同，网桥还要对不同的帧格式 进行重新封装。如果两个局域网数据传输速率不同，则网桥还要进行 Buffering

网桥与中继器的区别如下：

理想的网桥是透明网桥（transparent bridges ），它可以将多个LAN连接起来，LAN内的硬件和软件不需要做任何的变化。要实现透明网桥，需要解决以下问题：

1. 当一个帧到达网桥时，它必须作出丢弃（discard）还是转发（ forward ）的决策，如果是转发，它还要知道向哪个LAN转发?
2. 决策是通过在网桥内部的一张 地址表（hash table） 中查找目的 MAC 地址而作出的，怎么生成和维护这张地址表?

生成地址表的算法如下：

1. 逆向学习（backward learning）：网桥从到达帧的源地址认识到源地址对应的那台机是在帧来的那个LAN上，所以，把它写入MAC地址表
2. 扩散算法（泛洪算法，flooding algorithm）：当网桥不知道目的地址时（表中查不到），它会将这帧从除来的LAN外的所有LAN转发出去
3. 删除过时的地址记录：时间标记
   1. 每增加一条记录，为它打上时间标记；
   2. 每引用或找到某条记录，为它打上新的时间标记
   3. 当某条地址记录超过一定时间没被引用，则删除它

有了地址表后，每到一个帧，就执行以下算法：

1. 如果源LAN和目的LAN相同，则丢弃该帧 filtering；
2. 如果源LAN和目的LAN不同，则转发该帧 forwarding ；
3. 如果目的LAN未知，则广播该帧 flooding。

交换模式：

1. 直通交换：网桥收到 MAC 地址后，即可判断转发路径，而不必等待后面的数据（延时最低，无法检查出错误）
2. 存储转发：等整个帧到之后，先根据校验和判断有无错误，再转发（延时最高，可检查出所有错误）
3. 无分片交换（无碎片交换）：一旦数据帧已接收的部分超过64字节，就开始进行转发处理（延时较低，可检查出冲突造成的错误）

三种交换模式的转发时机见下图：

生成树协议

实际网络中采用冗余拓扑，这样的话，使用泛洪算法会导致一些问题，比如说广播风暴（一个帧在闭合环路中传输，并随着泛洪而增加数量，导致网络瘫痪）、多帧传送（泛洪导致多个相同的帧同时到达）、MAC地址库不稳定（多个相同的帧从不同口输入，导致路由表不断变化）

为了解决上述问题，引入 生成树协议（STP）：

1. 每个网络一个根网桥，可以选举 MAC 地址最小的网桥作为根，这个信息会通过扩散告知其他网桥
2. 每个网桥一个根端口，通过根端口，可以以最短路径到达根
3. 每网段一个指定端口，这样一个网段就只能通过一个路由器去转发
4. 非指定端口不被使用

使用上述算法就能生成一个逻辑无回路的生成树。

生成树的发明者：Radia Perlman 写的一首诗：

I think that I shall never see
A graph more lovely than a tree.
A tree whose crucial property
Is loop-free connectivity.
A tree which must be sure to span.
So packets can reach every LAN.
First the Root must be selected
By ID it is elected.
Least cost paths from Root are traced
In the tree these paths are placed.
A mesh is made by folks like me
Then bridges find a spanning tree.

VLAN

虚拟局域网（VLAN）可以将物理上不在同一 LAN 上的设备，在逻辑上归为同一组 LAN。一个VLAN对应一个广播域。有了VLAN，可使用二层交换机实现广播域的分割。实现方法有三种：

1. 基于端口：交换机内部有 VLAN 表，通过 VLAN 表来判断哪些端口属于同一 VLAN，转发时，将帧广播到同一 VLAN 中
2. 基于MAC地址
3. 基于三层协议

如果 VLAN 是跨交换机的，可以用 IEEE 802.1Q 协议，方法如下：在跨交换机之前，交换机会给帧打上一个 VLAN ID 标记，当到达另一个交换机后，交换机拆除 VLAN ID，并转发给对应端口。

网络设备

• NIC 网卡
  • Nework Interface Card
  • 为主机提供介质的访问。
  • MAC地址烧在网卡的 ROM中
• 网桥 Bridge：
  • 连接不同的LAN网段。
  • 通过过滤部分交通流量，减少冲突的机会，改善网络性 能。
  • 以网段分流交通，基于 MAC 地址过滤流量
• 交换机 Switch
  • LAN 交换机是多端口网桥
  • 连接 LAN 网段
  • 使用一张 MAC 表，来决定一帧转发的端口
  • 交换机常被用来替换集线器（hub），以改善现有网络性能。
  • 增加带宽