Network05 Link
2023-02-15 20:26:46

Intro

链路层的意义是补全网络层剩下要做的事情,主要有两种类型:

  1. 共享介质,广播传输
  2. 点对点传输

一般在链路层把设备叫做节点,连接节点的东西叫做链路。链路层就是通过相邻的节点、沿着连续的链路向上提供服务的,包括:

  1. 把IP数据包封装成帧
  2. 提供 MAC(Medium Access Control)以利用共享的传输介质(如果是点对点就不需要)
  3. 可靠传输,例如 WiFi 就是在链路层保证可靠性的
  4. 错误检测和恢复,重点是恢复

链路层的大部分功能是用专用硬件实现的,链路层可以看到软硬件交互的接口。

校验码/纠错码

一般的模式是给定数据 D,计算校验码 EDC 一起组成数据 (D,EDC) 传输。接收方收到 (D',EDC') 后进行校验或纠错,如果判定为不可恢复就丢弃这个帧。

奇偶校验

EDC 为一个比特,使得 (D,EDC) 所有位的异或和是 0。可以查出奇数个比特翻转,别的就查不到了。

可以把奇偶校验拓展到二维,这样就可以用出错的行和列定位到出错的比特,从而实现一位的纠错。

校验和

只是提一嘴,就是酱油

CRC

CRC(Cyclic Redundancy Check)是一种比较高级的校验码。

不妨设数据 Dd 位。

  1. 收发双方首先要确定一个 r+1 位生成元 G,并保证 G 的最高位是 1
  2. 发送方要给出 r 位数据 R 使得 DR 拼接是 G 的整倍。这里 R=(D<<r)%G
  3. 接收方收到 D‘R' 后除一下 G 看看是否整除

需要注意的是,这里的运算均不考虑借位。即这里本质上都是 \(\mathbb{F}_2\) 上的多项式运算。

如果连续出错的比特数不超过 r 个,那么 CRC 是可以检测出来的。

共享介质协议

在共享介质 广播链路中,每个发送方发送的数据都会被所有该链路连接的节点收到,同时刻多方传输则会产生信号干扰,因此需要协议来协调各方的行为。这样的协议也叫 MAC(Multiple Access Control)

理想的协议应当:

  1. 实现简单
  2. \(M\) 个设备同时工作时,它们的长期平均带宽都应该是总带宽的 \(\frac{1}{M}\)
  3. 最好是去中心化的,足够鲁棒

这里对共享介质的假设包括:

  1. 多方同时传输会冲突,使得数据无效
  2. 节点可以检测到冲突的发生
  3. 任意节点的发送都可以被所有节点收到

Channel Partition

通过 FDM 或者 TDM 将共享介质进行划分,保证任意发送的主机对不会冲突,可以实现 \(\frac{1}{N}\) 的公平带宽。

问题在于 \(N\) 通常是固定的值,因此少数设备活动时可能没法得到全部的带宽。

也可以利用 CDMA(Code Division Multiple Access)。CDMA 给每个节点一个编号(code),每个节点发送时会利用 code 处理一下信息。如果选择恰当的 code 分配算法,就能保证即使多个节点同时传输也不会发生碰撞。

Random Access

  1. 每个节点都会全速(满带宽)发送帧
  2. 如果节点检测到了冲突,就停止传输
  3. 以某种策略重试(ALOHA用概率重传、CSMA/CD用随机back-off)

Slotted-ALOHA

有如下规定:

  1. 所有帧大小相等,含 \(L\) 比特
  2. 时间被划分成时间片,每个时间片大小为 \(L/R\)。即用满带宽传输一个帧花费的时间
  3. 每个节点只会在时间片的开始进行传输
  4. 所有节点拥有同步时钟
  5. 每个发送的节点能在当前时间片立即检测到冲突
  6. 定义参数 \(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

  1. 不要求所有节点的时钟同步

分析是类似的,区别在于某个时间片内单个节点成功的概率为 \(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)这一类协议要求:

  1. 在发送之前先检测是否有人在发送
  2. 检测到冲突后立刻停止发送
  3. 等待一个随机的时间,重试

目的是减少冲突

back-off 的策略也可以操作。例如在检测到第 \(n\) 次冲突后,节点将在 \(\set{0,1,2\ldots 2^n-1}\) 中随机挑一个数 \(K\),然后等待 \(K\) 个时间单位。而在 \(n\) 达到 \(N\) 次后将不再继续增长。

这样的好处:

  1. 首先这仍然是随机的
  2. 其次有一个探测的过程,back-off 的时间逐渐指数级变长
  3. 有一个上界

课本上给了一个效率,不会推。

Take turns

Master node

即选出一个 master 节点用于协调传输。每次 master 会发送令牌给一个节点,这个节点就开始广播。令牌用完之后就停止传输,由 master 继续发令牌。

这个协议最大的问题还是鲁棒性,如果 master 挂掉了就整个网络都挂掉了。

Token passing

也就是击鼓传花,手上拿着令牌的节点可以传输,时间一到就传给下一个节点。

问题还是鲁棒性,这个协议要求每个节点都必须正确地操作(让出令牌)。

MAC 地址/交换机

48位,一般每个设备的 MAC 是不变的(回忆 IP,主机的 IP 要设置为子网内有效 IP 地址,DHCP)

需要注意的是,交换机与主机和路由器直接相连的端口,是没有 MAC 地址的。这是因为这些链路上的主机和路由器不需要寻址,直接发就能被交换机收到(但主机和路由器的端口需要 MAC 地址,这是为了交换机发送数据)

链路层端口工作流程如下:

  1. 把 IP 数据包封装成帧,填入目标 MAC 地址,交给物理层打出去
  2. 收到帧后查看目标 MAC 地址
    1. 如果目标 MAC 地址就是当前端口的 MAC 地址,接收
    2. 丢掉这个帧
  3. 也可以广播,FF-FF-FF-FF-FF-FF 就是特殊的广播 MAC 地址

ARP

ARP(Address Resolution Protocol)是用来计算 IP 地址到 MAC 地址的映射的

计算 ARP 的模块通常包含若干表项,每个表项的内容为:

  1. IP 地址
  2. MAC 地址
  3. TTL

查询过程如下:

  1. 看看是否存在目标 IP 的映射
    1. 存在,直接返回 MAC 地址
    2. 不存在
      1. 构造 ARP 包,目标 MAC 是广播地址,包含要查询的 IP 地址和源 MAC 地址
      2. 收到 ARP 包的节点会比较查询 IP 地址和自己的 IP 地址,然后给源 MAC 发一个确认包
  2. 根据 TTL 去掉超时映射

需要注意的是,查询是广播而应答是点对点的。

以太网

以太网有这么几个优点:

  1. 发明得很早,大家都用
  2. 很简单,成本低
  3. 速度还不错

交换机

交换机对于主机和路由器而言是透明的,即主机只会标注目标路由器/主机的 MAC 地址。

  1. 交换机消除了冲突
  2. 引入交换机可以让不同链路跑在不同的速率
  3. 能够提高网络的鲁棒性,例如过滤某些可疑的帧

交换机的功能主要包括过滤和转发。不妨假设交换机的 x 端口收到了一个目标 MAC 地址为 M 的帧:

  1. 如果交换机没有 M 的转发表,那么就广播这个帧(x 端口除外)
  2. 交换机中记录 M 的出端口为 x,那么就丢掉这个帧
  3. 记录 M 的出端口为 y,那么就从 y 转发

而交换机中的转发表则是通过预定算法求出来的

  1. 每从端口 x 收到一个源 MAC 地址为 S 的帧,就记录一个表项 (S,x,TTL)
  2. 固定一段时间根据 TTL 清理表项

VLAN

即一个 LAN 仍然可以继续划分成若干个 VLAN。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 数据包

  1. A 先得到 B 的 IP 地址(或者利用 DNS 解析域名)
  2. 判断 A, B 是否处于同一子网
    1. 是,那么把 IP 数据包封装成帧,根据 IP 地址查询目标 MAC
      1. 存在 IP->MAC 映射,发
      2. 不存在,用 ARP 查询到 IP 对应的 MAC 地址,发
    2. 否,那么把 IP 数据包封装成帧,根据默认路由的 IP 地址查询 MAC
      1. 同上
      2. 同上