计算机网络原理 笔记 6

链路层与局域网

链路层

运行链路层协议的任何设备称为节点，相邻节点的通信信道称为链路，在链路上传递的数据报被封装为链路层帧

可能提供的服务

• 成帧：将网络层数据添加一些首部字段封装为链路层帧
• 链路接入：由MAC规定了帧在链路上的传输规则
• 可靠交付：保证无差错地传递网络层数据报，但是对于部分低比特差错链路，可靠性是不必要的
• 差错检测和纠正：由于硬件设备原因可能会导致部分比特被错误传输，因此可以在帧中包含相应差错检测/纠正比特来检测

实现

通常通过网络适配器（又称为网络接口卡）来实现

网络适配器

差错检测与纠正

接收方需要判断接收到的数据是否是原始数据，通常通过EDC来实现，但是需要注意的是EDC本身也有可能被损坏，并且即使使用了EDC也可能出现漏检的情况

差错检测与纠正

常见的EDC方法包括奇偶校验、检验和与循环冗余检测

奇偶校验

增加一位校验位，用于指示原始数据中’1’的个数的奇偶性，但是这只能判断出数据中出现了奇数个比特差错

为了提升其鲁棒性，采用二维奇偶校验的方式，即将原始数据划分为一个矩阵，分别检测每一行与每一列的奇偶校验和，这样可以检测并纠正单个比特差错，并且可以检测双比特差错

二维奇偶校验

检验和

与运输层协议中内容相似，将数据按字节求和取反码

循环冗余检测

现代广泛使用CRC编码，主要思想为将数据流看做系数为0, 1的多项式

CRC编码

如上图，编码操作为：

• 发送方与接收方协商$r+1$位比特模式作为生成多项式，记为$G$，要求$G$的最高位必须是1
• 对于数据段$D$，发送方将其附加$r$个比特$R$，得到$d+r$位比特模式，使其可以被$G$整除
• 接收方检测是否可以整除即可

因此关键问题在于如何选取$R$使得：

$$(D << r) \oplus R = nG$$

该式可化简为：

$$D << r = nG \oplus R$$

在CRC中，所有的加法和减法都等价于异或操作，因此乘法和除法需要对应的变化（竖式中的加减法也变成了异或）
因此，可以计算$R$为：

$$R = (D << r) \pmod{G}$$

国际标准的生产多项式为：

$$G_{\text{CRC-32}} = 10000001001100000010001110110110111$$

CRC可以检测出所有的奇数位、双比特、不大于$|G|$长度的错误

多路访问链路和协议

由于所有的节点都可以传输帧，因此同时被接收的信号会在接收方处发生碰撞，导致所有信号丢失，因此需要多路访问协议用于协调多个发送和接收节点共享一个信道的访问。

其应当具有的特性为：

• 仅有一个节点发送数据时，需要使用完整信道
• 有多个节点发送数据时，每个节点吞吐量可以趋近于平均
• 协议是分散的：不会因一个节点崩溃而崩溃
• 造价便宜！

可以划分为信道划分协议、随机接入协议与轮流协议

信道划分协议

采用时分复用或频分复用的方式，平均划分时间或频率

时分复用与频分复用

TDM/FDM的特点：

• 消除了碰撞，并且非常公平
• 在及诶单书很少的时候效果很差

另一种信道划分协议为码分多址，为每个节点分配一种不同的编码，如果编码选择合适，即可同时传输同时接收并且互不干扰

随机接入协议

每个节点都以信道最大速率发送分组，当发生碰撞时，等待一个随机时延并重发该分组，直到发送成功。

随机试验种类繁多，具体介绍ALOHA协议与载波侦听多路访问(CSMA)协议

时隙ALOHA

假设：

• 所有帧大小相同，记为$L$
• 时间被划分为等长的时隙，每个时隙可以发送一帧
• 只在时隙起点传输帧
• 节点之间同步时隙信息
• 如果在一个时隙中发生了碰撞，则时隙结束时所有节点可以检测到碰撞

则时隙ALOHA的操作如下：

• 当有数据需要发送时，等待下一个时隙起点传输
• 如果没有碰撞则万事大吉
• 反之，则在后续的每个时隙起点独立地以 $p$ 的概率重传，直到成功发送

定义成功时隙为恰好只有一个节点传输的时隙，成功时隙占所有时隙的比例为效率，则$N(N\gg 1)$个节点的效率为：

$$f(p) = C_{N}^{1}p(1-p)^{N-1} = Np(1-p)^{N-1}$$

极值点为：

$$p = \frac{1}{N}$$

因此：

$$\begin{align*} f(p) &\leq (1 - \frac{1}{N})^{N - 1} \\ \lim\limits_{N\to\infty}&f(p) \leq \frac{1}{e} \end{align*}$$

所以当节点数充分大时，效率最高约为37%

ALOHA

纯ALOHA将不考虑时隙问题，在分组到达时则立刻进行传输，碰撞时立即以概率 $p$ 重传分组，以概率 $1-p$ 等待一个分组传输时间，重复循环直到成功发送
若一个节点想要成功发送，则必须要保证其发送时间的前后各一个分组传输时间之内不能有其他节点发送，因此可以计算得其最大效率为：

$$\lim\limits_{N\to\infty}f(p) \leq \frac{1}{2e}$$

CSMA

模仿人类聚会时的发言，CSMA新增了如下协议：

• 说话之前先听：在传输之前先“听”信道，如果有其他节点正在发送则等待，直到一段时间内没有传输

而CSMA/CD则进一步增加了如下协议

• 和别人同时开始说话时停止说话：节点在传输过程中保持“听”信道，当有其他节点也开始传输的时候立刻停止传输，等待一段随机时间后，进入上一种状态

采用时空图说明：

时空图，其中B与D碰撞

可以看出，决定其碰撞发生的概率即决定性能的关键因素为信道传播时延，即在节点之间通信的效率

CSMA/CD的一些讨论

讨论两个问题：

1. 每次检测到碰撞后应该等待多久
2. CSMA/CD效率如何

对于等待时间的问题，采用二进制指数后退算法，具体为：

对于效率问题，定义CSMA/CD的效率为：

定义$d_{\text{prop}}$为两个适配器之间传递信号的最大时间，$d_{\text{trans}}$为传输一个最大以太网帧的时间，则CSMA/CD的效率为：

$$f = \frac{1}{1 + 5d_{\text{prop}}/ d_{\text{trans}}}$$

轮流协议

是一大类能够满足大量节点平均享有吞吐量的协议，主要讨论轮询协议与令牌传递协议

轮询协议

指定主节点，主节点可以轮询每个节点，告知其可以传输的最大帧数
这种方法引入了轮询时延，并且是集中式的（主节点坏了就似了）

令牌传递协议

讲一个称之为令牌的特殊帧在节点之间以一个固定的次序进行交换，每个节点持有令牌当且仅当自己需要发送帧，反之立刻传递给下一节点
同样的，该协议单个节点的故障可能导致整体的崩溃

DOCSIS

一个实际应用的综合性协议

上行与下行信道

DOCSIS定义了电缆数据网络体系结构及其协议，对于上行信道与下行信道都采用FDM，每个信道均为广播信道，并且下行信道不会存在多路访问问题，主要考虑上行信道
上行信道被划分时间间隔，每个时间间隔包含微时隙序列（类似TDM）

• CMTS发送MAP报文指定特定的调制解调器在特定时间间隔发送分组
• 调制解调器们在一组特殊的微时隙间隔内向CMTS发送请求帧，向其请求分配微时隙用于发送数据

请求帧以随机接入的方式发送，当其发生碰撞时（调制解调器只能通过下行信道的数据推测是否碰撞），采用二进制指数回退算法决定等待时间并重新发送

交换局域网

链路层寻址

MAC地址

链路层地址的所有者并非主机或路由器，而是其中的适配器（网络接口），链路层地址有多种称呼，包括LAN地址，物理地址，MAC地址，常用的为MAC地址，长度为6字节即48bits

MAC地址示意图

与IP不同，MAC具有扁平化特征，即不再具有类似IP的层次化特征，其地址值是随着设备而固定下来的

MAC寻址方法为，向帧中插入目的MAC地址后发送到局域网上，当接收时，检测目的MAC地址是否与己方一致，一致则解析数据，反之则丢给局域网，如果需要广播则使用广播地址（全1）

ARP

地址解析协议用于实现网络层地址与链路层地址之间的转换，是一个介于链路层和网络层之间的协议

工作方式为询表，ARP表中存有IP地址到MAC地址的映射，以及该表项的过期时间，当表项缺失时，会广播ARP查询分组，向子网上所有的主机询问此IP地址对应的MAC地址，相应的适配器接收到报文后会发送ARP响应报文

向子网外发送

通过路由器的转发表实现不同子网之间的转换，每个子网中的主机只需要把数据传到路由器就可以了，不然就会到达数据报天国！

以太网

简易、便宜、首发、告诉，在物理结构上采用交换机（之前是总线与集线器），有效避免了碰撞

帧结构

以太网帧架构

字段意义如下：

• 数据字段（46-1500字节）：过长的数据需要被分片
• 目的地址（6字节）：目的地MAC
• 源地址（6字节）：发送方MAC
• 类型字段（2字节）：用于指示需要使用的网络层协议
• CRC（4字节）：检测差错
• 前同步码（8字节）：AA-AA-AA-AA-AA-AA-AA-AB，用于同步时钟，最后两个1用于指示数据到来

以太网是无连接的，没有类似TCP的握手需求，也没有重传机制

以太网技术

100MHz以太网标准

一种标准是IEEE 803.2z：

• 使用上述帧格式
• 允许点对点以及广播
• 使用CSMA/CD来共享广播信道
• 点对点信道允许40Gbps全双工

链路层交换机

主要任务是接收入链路层帧并将其转发到出链路，对于主机来说是透明的，可能会存在过量数据，因此设有缓存

转发与过滤

过滤是决定一帧应该被转发到某个接口还是被丢弃，转发决定帧应该被导向哪个接口，这两项操作由交换机表完成，每个表项包含：

• MAC地址
• 通往该地址的交换机接口
• 表项存在时间

当接口$x$到达一帧链路层帧后，交换机表的索引过程如下：

• 如果不存在目的地MAC地址对应的表项，则广播
• 如果存在，但是表中的接口是$x$，也即想发给自己所在子网，直接丢弃（过滤）
• 如果存在，并且接口为$y\neq x$，则转发到$y$的输出缓存

自学习

交换机表的建立是自动、自治、动态建立的，即自学习，方法如下：

• 初始表为空
• 对于每个接口存储到的每个入帧，存储：源MAC地址、到达的接口、当前时间
• 一段时间后，如果没有接收到该MAC为源的帧，则删除之

交换机是即插即用的、双工的

链路层交换机的性质

• 清除碰撞：有缓存，网段上至多同时传输一帧
• 异质的：链路之间彼此隔离，不同链路能够以不同速率在不同媒体上运行
• 管理：更加安全，易于管理，例如可以自行解决异常适配器

交换机与路由器

交换机是链路层的分组交换机，路由器是网络层的分组交换机

路由器与交换机

虚拟局域网

交换局域网的缺点：

• 缺乏流量隔离：广播可以被整个机构的网络接收到，无法局部广播
• 交换机的无效使用：如果组小而交换机大，每个交换机将会有大量端口被浪费
• 用户管理：用户换组或多组将会导致复杂的物理布线变化

因此引入虚拟局域网，由网管将一个交换机的不同端口划分为不同组，每个VLAN中的端口形成一个广播域

VLAN实例

但是这样会导致VLAN之间完全隔离，常用的解决办法是引入一个路由器进行VLAN间的通信，与交换机中某个空闲的端口连接，该端口可以视作同时属于多个VLAN

如果需要多个交换机，并且交换机之间的VLAN需要互联（也许就是同种VLAN），采用的方法为VLAN干线互联而并非将各个VLAN分别互联，每个干线端口同时属于所有VLAN

为了确保帧可以正确跨越干线，对以太网帧进行扩展

扩展以太网帧

增加字段有：

• 标签协议控制符（2字节）：固定81-00
• 标签控制信息（2字节）：包含12比特的VLAN标识符字段和3比特的优先权字段

新增字段被干线端口添加与删除

EVPN

链路层交换机在逻辑上联结在一起，并且使用更顶层的协议进行通信，如将链路层帧包裹在IP数据报中

链路虚拟化

引入多协议标签交换，用于改善IP路由器交换速度，目标是通过选择性的标识数据报，并允许路由器通过固定长度标签转发数据报

MPLS首部

MPLS会扩展链路层帧，增加的首部字段位于链路层和网络层首部之间，新增字段包括：

• 标签
• 实验字段（3比特）：预留
• S字段：用于指示MPLS首部栈的结束
• TTL：寿命字段

MPLS使能的路由器称为标签交换路由器，其在转发表中查找MPLS标签并将数据报传递给相应的输出接口进行转发，但是这要求通信的两个路由器都是MPLS使能的

利用MPLS进行通信，其中R1234都是MPLS使能的

从上图可以看出，MPLS可以提供多条路径（同样的也可以人为限制路径），例如图中R4-A具有两条MPLS路径，这被称为流量工程

相比于传统网络，MPLS的优势有：

• 交换速度增加
• 流量工程
• 转发路径的快速恢复
• VPN

数据中心网络

数据中心：包含大量主机，称为刀片，刀片堆叠在机架上，每个机架顶部有一台交换机，交换机之间互联，数据中心网络需要支持两种类型的流量——外部通信与内部交换，由边界路由器负责与公共因特网相连

数据中心网络示意

负载均衡

外部请求首先被重定向到负载均衡器，向主机发送请求并在主机之间尽量保持负载均衡，基于目的端口号和IP地址做决定

同时其提供了客户与数据中心网络之间的屏障，形成了类似NAT的效果（公网内网转换）

等级体系结构

大型数据中心需要使用路由器和交换机等级结构，以保证交换机工作的稳定性（如上图），其中每台接入路由器下的主机构成了子网，并且可以被进一步划分为多个VLAN子网

但是这种等级体系结构可能导致主机之间容量首先，即交换机速率不足以支撑并发时主机之间能够以最大速率通信

发展趋势

全连接拓扑示意

克服等级结构缺陷可以采用FCT，即第一层和第二层之间全连接，提升了主机之间不相交的路径数，并且未直接连接到同一个交换机的机架之间的通信逻辑上是等价的

另一种修改方式称为模块化数据中心，略过

目前数据中心常用的协议有：

• 链路层：RoCE
• 运输层：DCTCP/DCQCN
• 路由选择：SDN