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