计算机网络 - 链路层

我想这是最后一篇了

任何运行链路层协议的设备均称为节点，把相连的节点之间的信道称为链路，在通过链路时，传输节点将数据报封装在链路层帧中。这里讨论两种不同的信道：广播信道——许多主机与一条广播信道连接；点对点通信链路

大多数情况下，链路层功能是由被称为网络适配器的芯片（网卡）实现的。即，链路层的许多功能是由硬件实现，链路层在协议栈中处于硬软交界地带

CRC 循环冗余检测

链路层可能提供差错检测服务，因为没有必要转发一个出错的数据报。不过链路层的差错检测更为复杂，并且还可能提供差错纠正

这里直接介绍 CRC 编码，也被称为多项式编码

发送方和接收方必须先协商一个 r+ 1 比特模式，称为生成多项式，用 G 表示（先理解为一个 r + 1 位的数吧）

假设发送方要发送长度为 d 比特的数据 D，这时，发送方会选择一个 r 位的附加比特 R，将其“拼”在 D 的后面，使得得到的这 d + r 比特的二进制数用模 2 算数恰好能被 G 整除

接收方用 G 去除收到的 d + r 比特，如果余数非零，则出现差错，否则正确

现在我们来理解这个策略：

在所有 CRC 的计算中，数据按照二进制计算，并且加法不进位，减法不借位。这意味着加法，减法，亦或，在 CRC 中是一个操作

回到发送方如何选择 R 上来，我们要求 R:

D x 2^r XOR R = nG

换言之：

D x 2^r = nG XOR R

所以，如果用 G 除 D x 2^r，余数刚好是 R（将 XOR 视为 + 看看），所以 R 应该是

(D x 2^r) % G

国际标准定义了 8、12、16、32 比特的生成多项式 G

每个 CRC 标准都能检测小于 r + 1 比特的突发差错，也可以检测到任何奇数比特的错误

多路访问链路和协议

广播链路能够将多个发送和接收节点连接到相同的、单一的、共享的广播信道上，如何协调它们，便是多路访问问题。因为所有的节点都能传送帧，如果节点同时收到多个帧，它们的信号纠缠在一起，发生了碰撞（不是比喻，而就是这么叫的）。这导致碰撞的帧消失了，随后引起的重传会消耗大量带宽

我们需要确认谁在什么时候“说话”，及所谓的多路访问协议，可以划分为 3 种：信道划分协议，随机接入协议，轮流协议

我们希望多路访问协议有这些特性：

• 只有一个节点发送时，此节点有 R bps 的吞吐量

• 有 M 个节点发送时，每个节点吞吐量在 R/M bps

• 去中心化

• 简单

信道划分协议

TDM 时分多路复用

TDM 将时间划分为时间帧，并进一步将时间帧划分为 N 个时隙（应当使一个时隙内可以传送一个分组），并将这些时隙分配给 N 个节点，每个节点在它们自己的时隙内发送

FDM 频分多路复用

FDM 则是将 R bps 的信道划分为不同的频段（每个频段拥有 R / N 的带宽），然后分配给 N 个节点

有着和 TDM 一样的优点和缺点：公平，但是限制了单个节点发送上限。当只有少数节点传送时，带宽被浪费了

CMDA 码分多址

因为它的抗干扰性曾用于军用，现在广泛用于民用。它精心选择一些编码，然后类似 TMD 的时隙分配给节点

随机接入协议

一个传输节点总是以满速率发送，碰撞发生后，该节点等待一个随机时延，然后重发，直到没有碰撞

时隙 ALOHA

没错，就是夏威夷的 ALOHA（最初的 ALOHA 好像就是在夏威夷大学搞出来的）

讨论之前，我们先做出如下假设：

• 所有帧为 L bit

• 时间被划分为长 L/R 的时隙

• 节点只在时隙开始前传输

• 所有节点知道时隙何时开始，并同步传输

• 如果出现了一个或多个碰撞，所有节点都能在此时隙结束前检测到碰撞

每个节点的操作如下：

• 节点有帧要发送时，应等到下个时隙开始

• 没有碰撞，准备传递新帧

• 有碰撞，节点以概率 p 在后续的时隙重传，否则再等一个，知道无碰撞地传出去

其实这种方法效率很低（）

CSMA 载波侦听多路访问

人们在谈话时大约是由这样一个不成文的约定的：

• 说话前先听，如果有人在说话，先等他讲完（载波侦听）

• 如果和其他人同时开口，先停止说话（碰撞检测）

这两条规则就包含在 CSMA 与 CMSA/CD（具有碰撞检测的 CSMA）协议族中

其实所谓载波监听，也得是在节点感知到广播信号的情况下才能侦听到信道并非空闲，监听不到已经发送但未到达的信号，所以碰撞是有可能发生的

关于碰撞检测，信号不是一瞬间发送的，有一段时间。如果节点在这段时间内监视到来自其他的信号能量，则说明碰撞发生了

所以对于一个将要发送的节点，简单来说：

1. 如果监听到行到空闲，发送。若非空闲，则等待到空闲时再发

2. 没有检测到碰撞，那么该帧就完成了。如果检测到了，中止传输

3. 中止传输后，等待一个随机时间，然后返回第一步

二进制指数后退解决了这个随机时长怎么取的问题：在帧经历了 n 次碰撞后，从 [0, 2ⁿ - 1] 中随机取一整数 K，然后等待 K * 512 比特时间（发送 512 bit 进入以太网所需时间的 K 倍）

轮流协议

轮询协议

要求有一个主节点，主节点一循环的方式轮询每个节点，通过观察信道，告诉每个节点能传送的最大帧数量

缺点是只有一节点活跃时，还需要轮询非活跃节点，另一个是主节点一旦故障，直接瘫痪

令牌传递协议

没有主节点，而是有一个称为**令牌（token）**的小特殊帧，在节点间以特定的顺序传送（节点1 -> 节点2 -> 节点3 ...）。当节点拿到令牌时，若没有要传输的，立即向下一个节点传令牌；若有，则发送最大帧数目的帧，然后将令牌传给下一个。挺像进程调度或者说锁的

但是，这里一旦有一个节点坏了，整个就会崩溃。而且，节点有可能忘记释放令牌

DOCSIS 用于电缆因特网接入的链路层协议

属于上面 3 个的每一种（应该说用到了每一种）

一个电缆接入网通产在电缆网头端将几千个住宅电缆调制解调器，与一个电缆调制解调器端接系统（CMTS）连起来。DOCSIS 用 FDM 将下行（CMTS -> 调制解调器）和上行（调制解调器 -> CMTS）网络段划分为多个频率信道

下行方向不存在多路访问问题，但上行很容易发生碰撞

每条上行信道被划分为多个时间间隔，每个时间间隔包含一个微时隙序列，电缆调制解调器在微时隙内向 CMTS 传输。CMTS 在下行信道通过发送 MAP 报文指定那个电缆调制解调器传输

有一组特殊的微时隙可以让电缆调制解调器以随机接入的方式向 CMTS 发送请求帧，告知 CMTS 有数据要发送。因为是随机接入，所以碰撞是可能的，但是调制解调器不能侦听信道，也不能检测碰撞。但是，若调制解调器没有在下一个控制报文收到对请求分配的响应（MAP 报文是广播的），则可以推断出碰撞，然后使用二进制指数回退重新发送

链路层寻址与 ARP

现在我们进入到局域网

路由器与主机并非是直接连接的，它们之间还要经过（可能）数台交换机与多条链路。

我们常说的光猫并非是交换机，它是将光信号转换成电信号，但是一般这两个设备的功能会集成在一个设备中

我一般把链路层交换机简称为交换机。其实路由器也是分组交换机

MAC 地址

链路层也是有地址的，也就是我们所称的物理地址，MAC 地址。并不是主机或路由器有 MAC 地址，而是它们的适配器（网络接口，比如网卡）有。链路层交换机透明地在主机和路由器之间承载数据报（即主机和路由器不会意识到交换机的存在）。

MAC 地址长 6 字节，用 6 个以 - 相连的 16 进制数表示。软件改变 MAC 是可能的，但是我们现在假定适配器的 MAC 地址不变

没有两块适配器有相同的 MAC 地址。IFEE 管理 MAC 地址空间，若一个公司要生产网络适配器，它象征性的购买 $2^{24}$ 个地址的空间（固定前 24 比特），然后自己分配

MAC 也有广播地址 FF-FF-FF-FF-FF-FF

ARP 地址解析协议

ARP 可以将一个 IP 地址解析成一个 MAC 地址，和 DNS 类似，将主机名解析为 IP，区别在于 ARP 只解析子网内部的主机

每台路由器或主机在内存中有一个 ARP 表，这张表的每个表项包含了 IP 地址，MAC 地址，TTL（寿命，指示删除该映射的时间）

主机 A（222.222.222.220）通过 IP 地址向主机 B（222.222.222.222）发送数据报，需要得知 B 的物理地址。如果 A 的 ARP 表有，那就好办；如果没有，发送方 A 则会构造一个** ARP 分组**（并不是链路层帧，是作为其载荷），里面包含了发送和接收 IP 及 MAC。ARP 的查询分组和响应分组有相同的格式

A 向其适配器传递 ARP 分组，指示它用 MAC 广播地址。适配器封装这个分组，以广播地址作为帧目的地址发送至子网。所有其他的适配器都受到了该帧，并按协议栈向上传递给 ARP 模块。ARP 检查 IP 地址，若匹配，则返回一个 ARP 响应分组。A 就可以根据此更新其 ARP 表，获得 B 的 MAC 地址

ARP 是即插即用的，并应当视为跨越网络层与链路层的协议

如果数据报发向子网之外，那么 ARP 查询的 IP 应当是网关的 IP（主机通过 DHCP 可以知道子网掩码和默认网关的 IP地址）。IP 数据报的目的 IP 当然是子网外的那个 IP，那是要给路由器看的，链路层帧的目的 MAC 地址是网关的 MAC 地址

以太网

以太网几乎占领着现有的有线局域网市场，对于本地区域联网的重要性就像因特网对于全球联网一样

以太网较 30 年前变化巨大，但是以太网帧结构基本稳定

以太网帧

数据：数据字段承载 IP 数据报，以太网的最大传输单元（MTU）是 1500 字节

类型字段：允许以太网复用多种网络协议（IP，ARP ...）

前同步码：总共 8 字节，前 7 字节都是 10101010，最后一个是 10101011，这可以用来调整时钟频率（使其与输入信号的频率和相位匹配），“唤醒”接收适配器（确保接收器在数据开始传输之前已经准备好），非常方便地识别帧开始的地方，还可以用于错误检测

如果 CRC 校验没有通过，接收方只是丢弃这个帧，发送方也没法执行重传操作，所以传输势必会产生间隙

主机应用会不会知道间隙的存在，就看用的是 TCP 还是 UDP 了（笑）

链路层交换机

交换机的输出接口也有缓存，和路由器一样

转发和过滤

这两个功能是借助交换机表完成的，交换机表的一个表项包含：MAC 地址，通向该 MAC 地址的交换机接口，表项放置在表中的时间

假定目的地址为 DD-DD-DD-DD-DD-DD 的帧从交换机的接口 x 到达。交换机采用的策略是：

• 如果表中没有这个 MAC 地址的表项，则向所有接口转发此帧的副本

• 如果表中有，但是是与接口 x 相连的，过滤此帧

• 若果表中有与接口 y != x 的表项相连，则转发到接口 y

可以自行推演模拟一下

自学习

转发表是自动、动态、自治地建立的，所以说交换机是自学习的。这种能力通过以下方式实现：

• 初始交换机表为空

• 对于在每个接口接到的入帧，交换机在其表中存储

• 在一段时间后（老化期），交换机没有收到一次地址作为源地址的帧，删除之

交换机是即插即用的，同时也是双工的，任何交换机接口可以同时发送和接收

一些性质

• 消除碰撞：交换机构建的局域网不会发生碰撞

• 异质链路：交换机将链路隔离，局域网可以由不同类型的链路组成

• 管理：交换机可以帮助更快地发现断开等错误

为了防止广播帧（没有寿命）的循环，交换网络的活跃拓扑限制为一棵树，换言之，其传递的路径并非是最短的，并不像路由器那样有丰富的拓扑结构

大型的交换网络意味着大量的 ARP 流量和处理量

交换机对广播风暴没有保护措施

虚拟局域网

现代机构的局域网往往是等级结构的，一个部门会有自己的局域网，但是在现实中会有些麻烦：

• 缺乏流量隔离：不希望行政流量到达雇员主机，但是广播会发给所有主机

• 交换机无效使用：96 端口的交换机只给几台主机用

• 管理用户：雇员到不同的组还要修改物理布线

所以我们有了虚拟局域网 VLAN，就像 VMM 可以运行多台虚拟机一样（只是方便理解，这个比喻并不准确），支持 VLAN 的交换机可以经一个物理局域网设施定义多个虚拟局域网。在基于端口的 VLAN 中，交换机端口被网络管理员划分为多个组，每个组构成一个 VLAN。一个 VLAN 内的主机彼此通信，仿佛在并没有其他主机的情况下与交换机连接

那么，如何让 VLAN 之间通信呢？一种方式是让这些 VLAN 各拿出一个端口，然后连在同一个路由器中

一种更具拓展性的方法是 VLAN 干线连接，即在 VLAN 交换机上定义特殊的 Trunk 端口，用 Trunk 链路将两台交换机连接起来。但是这样直接相连，交换机就需要知道一个帧来自于哪个 VLAN（毕竟视为两个局域网，不是同一个了），这就要在帧里添加 VLAN 标签