Intro
链路层的意义是补全网络层剩下要做的事情，主要有两种类型：
- 共享介质，广播传输
- 点对点传输
一般在链路层把设备叫做节点，连接节点的东西叫做链路。链路层就是通过相邻的节点、沿着连续的链路向上提供服务的，包括：
- 把IP数据包封装成帧
- 提供 MAC（Medium Access Control）以利用共享的传输介质（如果是点对点就不需要）
- 可靠传输，例如 WiFi 就是在链路层保证可靠性的
- 错误检测和恢复，重点是恢复
链路层的大部分功能是用专用硬件实现的，链路层可以看到软硬件交互的接口。
校验码/纠错码
一般的模式是给定数据 D，计算校验码 EDC
一起组成数据 (D,EDC) 传输。接收方收到
(D',EDC')
后进行校验或纠错，如果判定为不可恢复就丢弃这个帧。
奇偶校验
EDC 为一个比特，使得 (D,EDC)
所有位的异或和是
0。可以查出奇数个比特翻转，别的就查不到了。
可以把奇偶校验拓展到二维，这样就可以用出错的行和列定位到出错的比特，从而实现一位的纠错。
校验和
只是提一嘴，就是酱油
CRC
CRC（Cyclic Redundancy Check）是一种比较高级的校验码。
不妨设数据 D 有 d 位。
- 收发双方首先要确定一个
r+1位生成元G，并保证G的最高位是1 - 发送方要给出
r位数据R使得DR拼接是G的整倍。这里R=(D<<r)%G - 接收方收到
D‘R'后除一下G看看是否整除
需要注意的是，这里的运算均不考虑借位。即这里本质上都是 \(\mathbb{F}_2\) 上的多项式运算。
如果连续出错的比特数不超过 r 个，那么 CRC
是可以检测出来的。
共享介质协议
在共享介质 广播链路中，每个发送方发送的数据都会被所有该链路连接的节点收到，同时刻多方传输则会产生信号干扰，因此需要协议来协调各方的行为。这样的协议也叫 MAC（Multiple Access Control）
理想的协议应当：
- 实现简单
- 当 \(M\) 个设备同时工作时，它们的长期平均带宽都应该是总带宽的 \(\frac{1}{M}\)
- 最好是去中心化的，足够鲁棒
这里对共享介质的假设包括：
- 多方同时传输会冲突，使得数据无效
- 节点可以检测到冲突的发生
- 任意节点的发送都可以被所有节点收到
Channel Partition
通过 FDM 或者 TDM 将共享介质进行划分，保证任意发送的主机对不会冲突，可以实现 \(\frac{1}{N}\) 的公平带宽。
问题在于 \(N\) 通常是固定的值，因此少数设备活动时可能没法得到全部的带宽。
也可以利用 CDMA（Code Division Multiple Access）。CDMA 给每个节点一个编号（code），每个节点发送时会利用 code 处理一下信息。如果选择恰当的 code 分配算法，就能保证即使多个节点同时传输也不会发生碰撞。
Random Access
- 每个节点都会全速（满带宽）发送帧
- 如果节点检测到了冲突，就停止传输
- 以某种策略重试（ALOHA用概率重传、CSMA/CD用随机back-off）
Slotted-ALOHA
有如下规定：
- 所有帧大小相等，含 \(L\) 比特
- 时间被划分成时间片，每个时间片大小为 \(L/R\)。即用满带宽传输一个帧花费的时间
- 每个节点只会在时间片的开始进行传输
- 所有节点拥有同步时钟
- 每个发送的节点能在当前时间片立即检测到冲突
- 定义参数 \(p\)，冲突检测后以 \(p\) 的概率在下一个时间片立即重传
可以算一下 s-ALOHA 的效率极限。
注意到一个时间片内，某个节点成功的概率为 \(p(1-p)^{N-1}\)，故 \(N\) 个节点期望有 \(Np(1-p)^{N-1}\) 个节点传输成功
对于给定的 \(N\)，我们可以算出最优的 \(p^*\) 使得 \(Np(1-p)^{N-1}\) 最大，即 \(p^*=\frac{1}{N}\)，此时单个时间片内成功节点数期望为 \((1-\frac{1}{N})^{N-1}\)
这个函数是单调递减的，当 \(N\to\infty\)，可以知道 \((1-\frac{1}{N})^{N-1}\to e^{-1}\approx 37\%\)
ALOHA
- 不要求所有节点的时钟同步
分析是类似的，区别在于某个时间片内单个节点成功的概率为 \(p(1-p)^{2(N-1)}\)。不妨假设讨论的时间片为 \([s,s+len]\)，那么不冲突要求 \([s-len, s]\) 以及 \([s,s+len]\) 这两个时间片内都不能有节点传输。而每个节点在任意时间片内恰好传输一次，这里就是剩下的节点的两次都必须不传输。
算出来是 \(\frac{1}{2}e^{-1}\)
CSMA/CD
CSMA/CD（Carrier Sense Multiple Access with Collision Detection）这一类协议要求：
- 在发送之前先检测是否有人在发送
- 检测到冲突后立刻停止发送
- 等待一个随机的时间，重试
目的是减少冲突
back-off 的策略也可以操作。例如在检测到第 \(n\) 次冲突后，节点将在 \(\set{0,1,2\ldots 2^n-1}\) 中随机挑一个数 \(K\)，然后等待 \(K\) 个时间单位。而在 \(n\) 达到 \(N\) 次后将不再继续增长。
这样的好处：
- 首先这仍然是随机的
- 其次有一个探测的过程，back-off 的时间逐渐指数级变长
- 有一个上界
课本上给了一个效率，不会推。
Take turns
Master node
即选出一个 master 节点用于协调传输。每次 master 会发送令牌给一个节点，这个节点就开始广播。令牌用完之后就停止传输，由 master 继续发令牌。
这个协议最大的问题还是鲁棒性，如果 master 挂掉了就整个网络都挂掉了。
Token passing
也就是击鼓传花，手上拿着令牌的节点可以传输，时间一到就传给下一个节点。
问题还是鲁棒性，这个协议要求每个节点都必须正确地操作（让出令牌）。
MAC 地址/交换机
48位，一般每个设备的 MAC 是不变的（回忆 IP，主机的 IP 要设置为子网内有效 IP 地址，DHCP）
需要注意的是，交换机与主机和路由器直接相连的端口，是没有 MAC 地址的。这是因为这些链路上的主机和路由器不需要寻址，直接发就能被交换机收到（但主机和路由器的端口需要 MAC 地址，这是为了交换机发送数据）
链路层端口工作流程如下：
- 把 IP 数据包封装成帧，填入目标 MAC 地址，交给物理层打出去
- 收到帧后查看目标 MAC 地址
- 如果目标 MAC 地址就是当前端口的 MAC 地址，接收
- 丢掉这个帧
- 也可以广播，
FF-FF-FF-FF-FF-FF就是特殊的广播 MAC 地址
ARP
ARP（Address Resolution Protocol）是用来计算 IP 地址到 MAC 地址的映射的
计算 ARP 的模块通常包含若干表项，每个表项的内容为：
- IP 地址
- MAC 地址
- TTL
查询过程如下：
- 看看是否存在目标 IP 的映射
- 存在，直接返回 MAC 地址
- 不存在
- 构造 ARP 包，目标 MAC 是广播地址，包含要查询的 IP 地址和源 MAC 地址
- 收到 ARP 包的节点会比较查询 IP 地址和自己的 IP 地址，然后给源 MAC 发一个确认包
- 根据 TTL 去掉超时映射
需要注意的是，查询是广播而应答是点对点的。
以太网
以太网有这么几个优点：
- 发明得很早，大家都用
- 很简单，成本低
- 速度还不错
交换机
交换机对于主机和路由器而言是透明的，即主机只会标注目标路由器/主机的 MAC 地址。
- 交换机消除了冲突
- 引入交换机可以让不同链路跑在不同的速率
- 能够提高网络的鲁棒性，例如过滤某些可疑的帧
交换机的功能主要包括过滤和转发。不妨假设交换机的 x 端口收到了一个目标
MAC 地址为 M 的帧：
- 如果交换机没有
M的转发表，那么就广播这个帧（x 端口除外） - 交换机中记录
M的出端口为 x，那么就丢掉这个帧 - 记录
M的出端口为 y，那么就从 y 转发
而交换机中的转发表则是通过预定算法求出来的
- 每从端口 x 收到一个源 MAC 地址为
S的帧，就记录一个表项(S,x,TTL) - 固定一段时间根据 TTL 清理表项
VLAN
即一个 LAN 仍然可以继续划分成若干个 VLAN。VLAN 的功能需要交换机额外提供，可以提供更好的安全性和资源管理
如上图，所有的端口的划分构成了若干个不相交的广播域。即这个交换机被虚拟化成了好几个交换机，分管不同的广播域。
此时这些分属不同广播域的子网要怎么互联呢？解决方法是从交换机拉出一个端口到路由器，设置这个路由器的端口同时属于这两个子网。那么不同广播域的子网发消息，只需要经历 主机1->交换机广播域1->路由器->交换机广播域2->主机2
此时考虑这样一个问题：假如有两个交换机，每个交换机上分别有 N 个广播域。这 N 个广播域的端口，一半在交换机1上，另一半在交换机2上。我们希望让每个广播域分属两个交换机的端口互联，那么这需要至少 N 条链路。
另一种解决方案是利用 VLAN trunk。即两个交换机各挑出一个端口，设置成 trunk port，然后相连。这样交换机1的广播域1在广播的时候，帧会沿着 trunk 来到交换机2，再经过交换机2的分流进入交换机2的广播域1。
总览
假设主机 A 要向主机 B 发 IP 数据包
- A 先得到 B 的 IP 地址（或者利用 DNS 解析域名）
- 判断 A, B 是否处于同一子网
- 是，那么把 IP 数据包封装成帧，根据 IP 地址查询目标 MAC
- 存在 IP->MAC 映射，发
- 不存在，用 ARP 查询到 IP 对应的 MAC 地址，发
- 否，那么把 IP 数据包封装成帧，根据默认路由的 IP 地址查询 MAC
- 同上
- 同上
- 是，那么把 IP 数据包封装成帧，根据 IP 地址查询目标 MAC