链路层和局域网

1. 广播信道：用于连接有线局域网、卫星网和混合光纤同轴电缆 (Hybird Fiber Coaxial cable, HFC) 接入网中的多轴，需要媒体访问协议来协调帧传输
2. 点对点通信链路

链路层概述

1. 本章为方便讨论，将运行链路层协议的任何设备都称为节点 (node)，把沿着通信路径连接相邻节点的通信信道称为链路 (link)
2. 通过特定链路时，传输节点将数据报封装在链路层帧中，并将该帧传输到链路中

链路层提供的服务

1. 成帧 (framing)：在每个网络层数据报经链路传送前，链路层协议将网络层数据报用链路层帧封装起来，帧的结构由链路层协议规定
2. 链路接入：媒体访问控制协议 (Medium Access Control, MAC) 规定了帧在链路上传输的规则，对于点对点链路，无论何时链路空闲都能发送帧，多个节点共享广播链路时，MAC 协议用于协调多个节点的帧传输
3. 可靠交付：保证无差错地经链路层移动每个网络层数据报，链路层的可靠交付服务通常是通过确认和重传取得的，目的是在本地纠正一个差错 (链路两端)，而不是用过运输层或应用层协议进行端到端数据重传
4. 差错检测和纠正：许多链路层协议提供一种让发送节点在帧中包括差错检测比特，让接收节点进行差错检查的机制，以此来完成差错检测

链路层在何处实现

1. 链路层的主体部分在网络适配器中实现 (network adapter)，网络适配器又称作网络接口卡 (Network Interface Card, NIC)，位于网络适配器核心的是链路层控制器
2. 发送端协议栈取得了协议栈较高层生成并存储在主机内存中的数据报，在链路层帧中封装数据报，然后遵循链路接入协议将该帧传进通信链路中

差错检测和纠正技术

1. 比特级差错检测和纠正 (bit-level error detection and correction)：通常是两种服务 (检测 / 纠正)，从一个节点发送到另一个物理上连接的邻近节点的链路层帧中的比特损伤进行检测和纠正

2. 发送节点使用差错检测和纠正比特 (Error-Detection and-Correction, EDC) 增强数据 D ，要保护的数据包括网络层数据报和链路帧首部

   

3. 即使采用差错检测比特，也可能存在未检出比特差错 (undetected bit error)

4. 检测差错的三种技术包括奇偶校验、检验和方法和循环冗余检测

奇偶校验

1. 偶 / 奇校验方案，发送方包含一个附加的比特，使 $d + 1$ 比特中 $1$ 的总数是偶数 / 奇数

2. 二维奇偶校验方案 (two-dimension parity)：可检测和纠正单个比特差错，可检测但不能纠正两个比特差错，行奇偶比特和列奇偶比特加上一个附加比特构成了链路层帧的差错检测比特

   

3. 向前纠错 (Forward Error Correction, FEC)：接收方检测和纠正差错的能力，允许在接收方立刻纠正差错，避免了不得不等待的往返时延

检验和方法

1. d 比特数据被作为 k 比特整数的序列处理
2. 因特网检验和 (Internet checksum) 将数据字节作为 16 比特的整数对待并求和，和的反码形成了携带在报文段首部的因特网检验和
3. TCP 和 UDP 中对所有字段都计算因特网检验和，XTP 对首部计算一个检验和对整个分组计算另一个检验和
4. TCP 和 UDP 的检验和只用了 16 比特，与链路层 CRC 相比提供相对弱的差错保护，因为运输层检验和通常由操作系统中的软件实现，链路层的差错检验通常在适配器中用专用的硬件实现，能够执行更复杂的 CRC 操作

循环冗余检测

1. 循环冗余检测 (Cyclic Redundancy Check, CRC) 编码：也称多项式编码 (polynomial code) ，将要发送的比特串看作系数是 0 和 1 的一个多项式，对比特串的操作被解释为多项式算术

2. 生成多项式 (generator) $G$ ：发送方和接收方协商的 $r + 1$ 比特模式

3. 对于一个给定的数据段 $D$ ，发送方要选择 $r$ 个附加比特 $R$ 将它附加到 $D$ 上，使得得到的 $d + r$ 比特模式用模 2 算数 [@ModularArithmetic2023] 恰好能被 $G$ 整除

   

4. $R$ 的计算

   1. 需要满足 $D\cdot 2^r\oplus R=nG$
   2. 对等式两边异或 $R$ 得到 $D\cdot 2^r=nG\oplus R$
   3. 该等式说明 $R = remainder\frac{D\cdot 2^r}{G}$

5. 国际标准定义的 CRC-32 标准被多种链路级 IEEE 协议采用，使用的一个生成多项式是

$$G_{CRC-32}=1000001001100000100001110110110111$$

多路访问链路和协议

1. 点对点链路 (point-to-point link)：由链路一端的单个发送方和链路的另一端的单个接收方组成，许多链路层协议都是为点对点链路设计的，如点对点协议 (point-to-point protocol, PPP) 和高级数据链路控制 (high-level data link control, HDLC)
2. 广播链路 (broadcast link)：能够让多个发送和接受节点都连接到相同的、单一的、共享的广播信道上，当任何节点传输一个帧时，信道广播该帧，每个其他节点都收到一个副本
3. 多路访问问题 (multiple access problem)：协调多个发送和接受节点对一个共享广播信道的访问
4. 碰撞 (collide)：多个节点可能会同时传输帧，此时所有节点同时接收帧，传输的帧在接收方处碰撞，涉及碰撞的所有帧都丢失了
5. 多路访问协议的类型
   1. 信道划分协议 (channel partitioning protocol)
   2. 随机接入协议 (random access protocol)
   3. 轮流协议 (taking-turns protocol)
6. 理想特性
   1. 当只有一个节点活跃时，该活跃节点有 $R$ bps 的吞吐量
   2. 当有 M 个节点活跃时，每个活跃节点的吞吐量接近 $R/M$ bps

信道划分协议

1. 时分多路复用 (TDM)
2. 频分多路复用 (FDM)
3. 码分多址 (Code Division Multiple Access, CDMA)

随机接入协议

时隙 ALOHA

假设

1. 所有帧由 $L$ 比特组成
2. 时间被分为长度为 $L/R$ 秒的时隙
3. 节点只在时隙起点开始传输帧
4. 节点是同步的，每个节点知道时隙何时开始
5. 如果在一个时隙中有两个或者多个帧碰撞，则所有节点在该时隙结之前检测到该碰撞事件

操作

1. 当节点有一个新帧要发送时，它等到下一个时隙开始并在该时隙传输整个帧
2. 如果没有碰撞，该节点成功地传输它的帧，从而不需要考虑重传该帧
3. 如果有碰撞，该节点在时隙结束之前检测到这次碰撞，该节点以概率 $p$ 在后续每个时隙中重传它的帧，直到该帧被无碰撞地传输出去

效率

1. 时隙多路访问协议的效率(efficiency)：当有大量的活跃节点且每个节点总有大量的帧要发送时，长期运行中成功时隙的概率
2. 假设每个节点试图在每个时隙以概率 p 传输一帧
3. 一个给定时隙是成功时隙的概率是节点之一传输而余下的 $N-1$ 个节点不传输的概率，因此给定节点成功传输的概率为 $p(1-p)^{N-1}$，因为有 $N$ 个节点，成功传输的概率为$Np(1-p)^{N-1}$
4. 最大效率为 $1/e=0.37$ (待补充)

ALOHA

1. 纯 ALOHA 中当一帧首次到达时，节点立刻将该帧完整传输进广播信道，如果传输的一个帧和多个传输经历了碰撞，这个节点将立刻以概率 $p$ 传输该帧，否则，该节点等待一个帧传输时间

效率

1. 待补充

CSMA

重要规则

1. 载波侦听 (carrier sensing)：一个节点在传输前先听信道，如果来自另一个节点的帧正向信道上发送，节点则等待直到检测到一小段时间没有传输，然后开始传输
2. 碰撞检测 (collision detection)：当一个传输节点在传输时一直在侦听此信道，如果它检测到另一个节点正在传输干扰帧，它就停止传输，在重复"侦听 - 当空闲时传输"循环之间等待一段随机时间
3. 这两个规则包含在载波侦听多路访问 (Carrier Sense Multiple Access, CSMA) 和具有碰撞检测的 CSMA (CSMA with Collision Detection, CSMA/CD) 协议族中

信道传播时延

1. 比特沿着广播媒体传播实际需要时间，在经过一个短暂的时间后，B 发送的比特到达 D ，开始干扰 D 的传输

CSMA/CD

1. 两个节点在检测到碰撞后短时间内都放弃了比特的传输
2. 图图图图图图图
3. 适配器在经历碰撞后需要等待一个随机时间量，二进制指数后退算法 (binary exponential backoff) 解决了确定时间量的问题

二进制指数后退算法

1. 一个帧经历了 $n$ 次碰撞，节点随机从 ${0, 1, 2, \dots, 2^{n}-1}$ 中选择一个 $k$ 值，以太网节点等待的实际时间量是 $K 512$ (发送 $512$ 比特进入以太网所需时间量的 $K$ 倍)，$n$ 能够取的最大值在 10 以内
2. 从中选择 $K$ 的集合长度随着碰撞次数呈指数增长，所以该算法被叫做指数后退

效率

1. CSMA/CD 效率 (efficiency of CSMA/CD)：当有大量的活跃节点，且每个节点有大量的帧要发送时，帧在信道中无碰撞地传输的那部分时间在长期运行时间中所占的份额

$$效率=\frac{1}{1+5d_{prop}/d_{trans}}$$

轮流协议 (taking-turns protocol)

轮询协议 (polling protocol)

1. 节点之一被指定为主节点，主节点以循环的方式轮询 (poll) 每个节点
2. 轮询协议引入了轮询时延，即通知一个节点可以传输的时间
3. 主节点有故障，整个信道都变得不可操作
4. 每次活跃节点发送了了最多数量的帧时，主节点必须依次轮询每一个非活跃节点

令牌传递协议 (token-passing protocol)

1. 不存在主节点，一个成为令牌 (token) 的特殊帧在节点之间以某种固定的次序进行交换
2. 一个节点收到令牌时，仅当它有一些帧要发送时，它才持有该令牌，否则立刻向下一个节点转发令牌
3. 当节点有帧要传输，节点发送最大数目的帧数，然后把令牌转发给下一个节点
4. 节点故障可能会使整个信道崩溃