链路层 | Dasi's Blog

1. 概述

术语

节点（node）：运行链路层协议的任何设备，包括主机、路由器、交换机
链路（link）：沿着通信路径连接相邻节点的通信信道
帧（frame）：是数据包在链路层中的叫法，传输节点将网络层的数据报封装在链路层的帧中，然后传送到链路中

考虑旅游公司为旅客安排从广东广州塔到北京天安门出行手段，旅客首先坐大巴从广州塔到白云机场，然后坐飞机到大兴机场，最后坐地铁到天安门
在这个类比中，旅游公司相当于路由选择协议，每种运输方式相当于每种链路层协议，游客相当于数据报

链路层提供的服务

成帧：链路层将网络层的数据报封装成帧，添加必要的首部信息，然后在物理层进行传输
链路接入：确保数据的有效发送和接收，处理竞争和碰撞
可靠交付：某些链路层提供可靠交付服务，保证无差错地经链路层移动数据报
差错检测和纠正：提供错误检测功能，部分协议还支持错误纠正功能

网络适配器/网络接口控制器/网络接口卡（NIC）：是实现链路层协议的地方，负责将数据帧从主机传输到物理媒介，是主机中的硬件

2. 差错检测和纠正技术

2.1 EDC和FEC

比特级（bit-level）：对从一个节点发送到另一个物理上连接的邻近节点的链路层帧中的比特损失进行检测和纠正

差错检测和纠正比特（Error-Detection and Correction,EDC）：使用额外的比特提供检测和纠正功能，从而增强数据D

前向纠错（Forward Error Correction,FEC）：是一种数据传输技术，使得接收方能自动检测和纠正错误，而无需发送方重传，适用于实时网络应用

EDC不能保证始终检测出比特差错
未检出差错的概率越小的技术，开销越大

2.2 parity bit

单位奇偶校验：附加一个奇偶校验位用于检测差错

奇校验：d+1个比特中1的总数是奇数
偶校验：d+1个比特中1的总数是偶数

局限性

只能检测是否存在比特差错，不能定位和纠正
只能检测是否出现奇数个比特差错，否则会导致未检出差错
奇偶检验位也有可能出错，可能导致误判

差错经常是以突发的方式聚集在一起，即一次性多个比特出错，这种时候很有可能是偶数个比特差错，测量表明单个奇偶校验位的检测准确度只有50%！

二维奇偶校验：d个比特被划分为i行j列，每一行每一列都有一个对应奇偶校验位，且行列的校验比特还拥有一个奇偶校验位

通过行和列的奇偶校验位可以定位到比特差错的具体位置，并实现纠正
行和列的奇偶校验自身是可以被检测的，但是无法被定位和纠正！

2.3 checksum

检验和流程

发送方对数据进行求和运算得到sum
发送方对sum进行取反生成checksum，封装在数据报中
接收方对数据进行求和运算（sum+checksum）
如果出现任何比特是0，代表检测出错误

2.4 CRC

概念

帧检测序列（Frame Check Sequence,FCS）：CRC的r位冗余码
生成多项式（generator）：采用国际标准或传输双方协商定义的比特模式G
模2减运算：本质上是按位进行异或运算（XOR）
模2除运算
- 当被除数的位数小于除数位数时，除法无效，商为0，被除数就是最终余数
- 当余数的位数小于除数位数时，除法停止，商补0，得到最终余数
- 当余数的位数等于除数位数时，商直接填1，使用模2减法得到余数

循环冗余检测（Cyclic Redundancy Check,CRC）

发送方将d位数据视为一个二进制多项式，除以一个预定义的生成多项式G，得到的r位余数作为CRC校验码，附加到数据后面
接收方将数据除以生成多项式G，如果余数非零，代表检测出错误

检验	EDC	相对优点
checksum	原本数据的和取反	计算更简单
CRC	原本数据除以生成多项式的余数	错误检测能力更强

运输层使用checksum：软件处理加法比处理除法的效率更高
链路层使用CRC：可以利用专用硬件提高CRC操作的效率

3. 多路访问协议

3.1 信道与碰撞

信道（channel）：用于传输数据的媒介或路径，可以是物理的（如电缆、光纤）或无线的（如无线电波）

广播信道（broadcast）：允许发送的信息同时传输到所有连接到该信道的设备，是共享信道的一种

碰撞（collide）：在共享信道中多个节点同时传输帧，从而导致接收方处产生信号干扰或数据丢失的情况

多路访问协议（multiple access protocol）：为了管理多个设备共享同一通信信道而设计的规则，帮助优化信道利用率，减少碰撞发生，从而提高数据传输的效率

协议	碰撞处理	吞吐量
信道划分协议	将一个信道划分为多个信道	限制在R/N
随机接入协议	重传帧前需要等待一个随机时延	只有一个节点活跃时是R，但是如果有多个节点活跃时吞吐量会很低（甚至低于R/N）
轮流协议	一次只让一个节点发送帧	R，但是引入了额外时延

3.2 信道划分协议

信道划分协议	作用	性质
时分多路复用（TDM）	将时间帧划分为多个时隙（timeslot），每个节点在特定的时隙内占用信道进行数据传输	节点吞吐量被限制在R/N，如果时隙内没有数据发送会浪费宽带
频分多路复用（FDM）	将可用带宽划分为多个频段，每个节点在不同的频段内进行数据传输	节点吞吐量被限制在R/N，频段划分复杂，管理和维护成本较高
码分多址（CDMA）	使用独特的编码方案为每个节点分配不同的码，发送方可以同时发送数据，接收方通过相应的码字提取出数据	提高了信道的利用率，具有较强的抗干扰能力和保密性，但是需要精确的编码和解码技术，且消耗一部分内存

3.3 随机接入协议

3.3.1 时隙ALOHA

操作	描述
节点同步	每个节点都知道时隙何时开始和结束，当节点有新帧发送时，它会等到下一个时隙的起点才发送帧，而不会在当前时隙发送
划分时隙	时间被划分成长度为L/R的时隙，一个时隙只能传输一帧
碰撞处理	所有对应节点都可以在时隙结束之前检测到碰撞，并且以概率p在后续每个时隙中重传该帧，直到成功发送为止
独立重传	所有涉及碰撞的节点都是独立地重传，不考虑其他节点的影响

性质

成功时隙定义：刚好有一个节点传输的时隙，即该时隙内没有发生碰撞
效率定义：当有大量活跃节点且每个节点总有帧要发送时，长期运行中成功时隙的份额
概率计算：假如有N个节点，则一个节点成功传送要求当前时隙内只有该节点发送帧，概率为 $p(1-p)^{N-1}$ ，则任意一个节点成功传送的概率为 $Np(1-p)^{N-1}$
最大效率： $1/e \approx 0.37$

只有37%的时隙在做有用功！实际的传输速率只有0.37R！

3.3.2 纯ALOHA

操作	描述
节点非同步	如果有一帧从网络层传递下来，节点会立刻将该帧发送
碰撞处理	节点检测到碰撞后会立即以概率p重传该帧，或者以概率1-p等待一个帧时间

性质

概率计算：假如有N个节点，则一个节点成功传送要求前一个帧时间和当前帧时间都不允许有任何节点发送，概率为 $p(1-p)^{2*(N-1)}$ ，则任意一个节点成功传送的概率为 $Np(1-p)^{2*(N-1)}$
最大效率： $1/2e \approx 0.18$ ，是时隙ALOHA的一半

3.3.3 CSMA/CA

具有碰撞避免的载波侦听多路访问（Carrier Sense Multiple Access with Collision Avoidance,CSMA/CA）：一个节点在传输前先听信道，如果信道忙碌将会一直等待，直到信道空闲才发送数据

信道传播时延：节点A正在传输的信息需要经过信道传播时延才能到达节点B，而在该时延内节点B并不知道信道忙碌，因此可能在这段时延中发送帧从而导致碰撞

3.3.4 CSMA/CD

具有碰撞检测的CSMA协议（Carrier Sense Multiple Access with Collision Detection,CSMA/CD）

适配器从网络层获得数据包，并封装为链路层帧
适配器侦听到信道空闲，开始传输帧，否则将等待
传输过程中，适配器一直监视来自其他使用同一信道的信号
如果适配器检测到来自其他适配器的信号，就中止传输，并等待一个随机时间量后重传，返回步骤2

等待时间量的选择

不能是固定时间量，否则两个适配器的信号将发生周期性碰撞，从而导致永远无法正确传输
时间量不能太小，否则当碰撞帧较多且传输时间较长时，会不断积累碰撞

时间间隔应该和碰撞节点数量成反比关系

二进制指数后退算法（binary exponential backoff）：经历了一连串的n次碰撞后，节点等概率地从 $\{0,1,2,...,2^{n-1}\}$ 中选择一个值K，然后等待K×512bit的时间量后重传

第一次碰撞，节点从{0,1}等概率选择到K=1，然后等待512比特时间
第二次碰撞，节点从{0,1,2,3}等概率选择到K=3，然后等待1536比特时间
第三次碰撞，节点从{0,1,2,3,4,5,6,7}等概率选择到K=5，然后等待3072比特时间
以此类推直到没有碰撞发生
可以发现，随着碰撞次数的变多，可供选择的K呈指数级增长，从而保证了碰撞次数和等待时间的平衡

效率定义：当有大量活跃节点且每个节点都有大量帧要发送时，帧在信道中无碰撞传输的那部分时间在长期运行时间中所占的比例

当传播时延接近0时，效率接近1，因为信号瞬时到达，不会发生碰撞
当传输时延接近无穷大时，效率接近1，因为较大的传输时间内足以完成传播，不会发生碰撞

3.4 轮流协议

协议	描述	缺点
轮询（polling）	其中一个节点被指定为主节点，以循环的方式轮询每个节点，以确定哪个节点可以发送帧以及发送多少帧	引入了轮询时延，主节点故障导致信道不可用
令牌传递（token-passing）	一个称为令牌的特殊帧在节点之间以某种顺序进行交换，只有持有令牌的节点可以发送帧，并且在发送完帧或无帧可发时立即将令牌传递给下一个节点	引入了令牌传递时延，令牌丢失或令牌传递失效导致信道不可用

4. 交换局域网

4.1 链路层寻址

4.1.1 MAC

介质访问控制（Media Access Control,MAC）：负责管理如何在共享的通信介质（如无线电信道或以太网）上有效地访问和传输数据帧

链路层地址有不同称呼：LAN地址、MAC地址、物理地址、硬件地址，而MAC地址是最为流行的术语
实际上，并不是每个主机或设备都有一个MAC地址，而是他们的适配器/网络接口卡具有一个MAC地址，就如同IP地址是对于每个接口而言的

MAC地址的唯一性和永久性：每个网络接口卡在制造时都会被分配一个唯一的MAC地址，并且他们会永久占据这个MAC地址，因此在同一网络中没有两个设备会拥有相同的MAC地址

MAC地址就好比一个人的身份证信息，是不会改变的，而IP地址就是一个人的邮政信息，是会随着空间和时间改变而改变的。尽管MAC地址被设置为永久的，但也可以用特殊软件来改变MAC地址，通常称为“MAC地址伪装”
MAC地址空间是由电气和电子工程师协会（IEEE）管理的，制作商需要向IEEE支付费用来获取MAC地址空间的使用许可

格式：通常为48位，表示为6个字节，每个字节用十六进制表示，中间用短破折号-或冒号:分隔

广播地址（全1）表示为：FF-FF-FF-FF-FF-FF

4.1.2 ARP

地址解析协议（Address Resolution Protocol,ARP）：将网络层的IP地址转换为数据链路层的MAC地址，以便数据帧可以在局域网中正确发送到目标设备

DNS和ARP非常相似，DNS将域名解析为IP地址，而ARP将IP地址解析为MAC地址
只不过DNS可以用于将任何地方的域名解析为IP地址，而ARP只能用于将同一局域网内的IP地址解析为MAC地址

ARP表：每台主机或路由器在内存中缓存了一个ARP表，用于映射IP地址到MAC地址，并包含了一个寿命值（TTL），指示了从表中删除该条映射的时间

过程	描述
ARP请求	首先检查自己的APR表是否已经有目标IP地址对应的MAC地址，如果没有则将广播地址作为目的地的MAC地址，然后广播ARP请求
ARP响应	目标设备接收到ARP请求，如果该请求的目的IP地址与自己的IP地址匹配，则会向源单播一个ARP响应
ARP缓存	源接收到ARP响应后，会将目标设备的MAC地址与其IP地址存储到ARP缓存中

ARP分组不止包含MAC地址和数据帧，还包含IP地址和IP数据报，因此可以将ARP协议视为网络层和链路层的夹层协议
除此之外，ARP还是即插即用协议，因为ARP表是自动建立的，不需要管理员来配置

网关（Gateway）：是一种特殊类型的路由器，由于ARP协议的作用域是子网，ARP的广播域被限定在同一子网内，所以ARP无法直接获得其他子网的MAC地址，因此需要网关路由器来实现跨子网通信

如果我们要访问子网外的某服务器，那么IP地址应该设置为该服务器的IP地址，MAC地址应该设置为当前子网的网关MAC地址

4.2 以太网

以太网（Ethernet）：是一种标准化的网络协议，定义了数据在局域网中如何格式化、传输以及如何在设备间进行通信，并使用CSAM/CD协议处理碰撞

以太网在局域网的重要性相当于因特网在广域网的重要性！！

以太网帧结构

字段	长度/字节	描述
前同步码	8	用于同步传输，确保数据帧的正确传输
目的地址	6	目标设备的MAC地址
源地址	6	源设备的MAC地址
类型	2	指示数据帧的类型，如ARP请求、IP数据报等
CRC	4	用于检测数据帧中的错误
数据	46-1500	数据帧的有效载荷，以太网的MTU是1500字节

以太网的服务性质

无连接：发送方和接收方不会进行握手和挥手
不可靠：接收方会进行CRC校验，但如果发现数据帧出错，只是丢弃该帧，并不会响应NAK也不会响应ACK

虽然以太网本身不提供可靠性服务，但是从整体上来看，数据传输可以依赖于上层协议（如TCP）提供的可靠性服务
以太网并不知道正在传输的是一个新帧，还是一个重传帧

4.3 交换机

4.3.1 交换机的功能

过滤（filtering）：决定一个帧应该被转发还是应该被丢弃

转发（forwarding）：决定一个帧应该被导向哪个出接口

交换机表：用于映射MAC地址到出接口，并记录了生存时间

不存在MAC地址：缓存MAC地址，向所有接口广播该帧
出接口等于入接口：丢弃该帧
出接口不等于入接口：转发该帧
老化期内没有接收到以该MAC地址作为目的的帧，则会丢弃该表项

交换机是自学习的，是一个即插即用设备
交换机是双工的，即任何接口既可以接收也可以转发，因此如果记录了从A到B的转发，那么之后B返回A时，就会选择先前入端口作为此时出端口

交换机毒化（poisoning）：是一种对抗交换机的攻击，攻击者向交换机发送大量具有不同伪造MAC地址的帧，从而使得交换机表充斥这些伪造的MAC地址表项，没有为合法主机留下表空间

4.3.2 集线器、交换机、路由器

设备	层次	对象	地址	作用域
集线器（Hub）	物理层	比特流（bit）	物理地址	物理互连的设备
交换机（Switch）	链路层	数据帧（frame）	MAC地址	局域网内设备互连
路由器（Router）	网络层	数据报（datagram）	IP地址	广域网内设备互连

交换机对主机和路由器是透明的（transparent）：主机或路由器始终是对另一个主机或路由器寻址，而不是对一个交换机寻址，即主机和路由器根本意识不到交换机的存在，因此路由选择、流量管理等功能只能在路由器上实现

交换机一定有MAC地址，但是否有ip地址要看交换机是网管型还是非网管型

交换机的必要性

原因	没有交换机	有交换机
消除碰撞	所有数据都需要通过广播信道传播，所有接口共享同一个冲突域，容易发生冲突和碰撞，导致数据包丢失和重传	交换机使得每个接口都有独立的冲突域
数据泄露	所有设备都能接收到所有的数据帧，增加了数据泄露的风险	交换机通过学习和转发MAC地址，确保只有目标设备接收到相应的数据帧
管理困难	集线器只负责传输，没有过滤、转发等任何功能	交换机可以自学习，支持VLAN
异质链路	集线器只支持相同类型的链路，难以适应不同的网络环境和需求	交换机可以转发到不同媒介的链路，从而实现链路隔离，提高整体带宽

4.3.3 虚拟局域网

下图架构的局限性

缺乏留流量隔离：所有主机都在同一个广播域中，无法实现留流量隔离
交换机资源浪费：如果有多个组别但每个组别的主机数量较少，那么使用多台交换机就会浪费资源
管理用户的困难：如果一个成员在不同组内切换，那么就需要更改物理布线

虚拟局域网（Virtual Local Area Network,VLAN）：将单一的物理局域网划分为多个逻辑局域网的技术，在一个VLAN内的主机彼此通信，仿佛只有它们与交换机连接

网络管理员使用交换机管理软件声明一个端口属于某个给定的VLAN
在交换机中维护一张端口到VLAN的映射表
通过将一个端口声明给两个VLAN，并将该端口与一台外部路由器相连，可实现同一交换机上不同VLAN之间的通信（相当于交换机让路由器把数据发给自己）
通过将一台交换机的端口与另一台交换机的端口互连形成干线连接（trunking），可实现不同交换机上不同VLAN之间的通信（当然也可以通过路由器）

5. MPLS

多协议标签交换（Multiple Protocol Label Switching,MPLS）：一种在链路层上网络层下实现网络数据传输的技术，通过在数据包中添加标签/MPLS首部来实现更快速、更灵活的转发和路由

字段	长度/bit	作用
标签	20	用于标识流量，是MPLS的核心
实验	3	提供流量的优先级或实验性信息
S	1	表示该标签是否为栈中的最后一个标签
TTL	8	用于防止数据包在网络中无限循环

MPLS增强：MPLS使能的路由器支持MPLS协议并能够处理和转发基于标签的数据报，不需要提取目的IP地址，而是利用MPLS首部的标签值来确认输出端口

速度更快：使用固定长度的标签，而不是长的IP地址查找，从而减少了查找时间
路由灵活：允许网络管理员基于标签来根据需求设置特定的流量路径，以实现负载均衡和更好的带宽管理，而基于IP则无法实现
QoS：MPLS使用实验字段来标识不同流量的优先级，使网络管理员能够根据业务需求设定QoS策略

6. 数据中心网络

6.1 数据中心的作用

为用户提供网页、搜索结果、电子邮件和流媒体视频等网络内容
用于特定数据处理任务的大规模并行计算基础设施
为企业和用户提供云计算服务

6.2 数据中心网络拓扑

组件	描述	作用
刀片（blade）	是数据中心中的主机/服务器	相当于蜂巢的工蜂，负责一切计算工作，运行应用程序和处理数据
机架（rack）	是一组刀片的集合，主机被堆叠在机架上	为刀片提供电源、冷却和物理支撑
机架顶部交换机（Top of Rack,TOR）	位于机架顶部的交换机，与当前机架上的主机互连，并与其他交换机互连	负责局部网络流量的管理和转发
边界路由器（border router）	将数据中心网络与公共因特网相连	处理进出数据中心的流量，确保数据在内部网络和外部网络之间的有效传递
负载均衡器（load balancer）	位于数据中心网络的入口点	通过计算，将用户请求分发到不同的服务器上，以实现负载均衡和高可用性

负载均衡器还可以实现类似NAT的功能，即实现外部IP地址和子网内部的IP地址的转换，从而向客户隐藏网络内部结构，实现内部网络的隐藏，提高数据中心的安全性和可靠性

问题	描述	解决
扩展性问题	大企业的主机规模可能需要扩展到几万甚至几十万台	等级体系：每台接入路由器与多台第一层交换机互连，每台第一层交换机又与多台第二层交换机以及一台负载均衡器互连，每台第二层交换机又与多台TOR互连，每台TOR又与多台刀片互连
带宽问题	不同TOR上的主机间通信可能需要经过多条路由器间链路，导致速率低、延时高，甚至出现瓶颈链路	部署速度更快的交换机和路由器，将相关服务和数据放在尽可能近的地方，让每台TOR交换机可以连接多台第二层交换机，从而增加聚合容量

7. Web页面请求全过程

Bob电脑在试图连网时，操作系统先生成一个DHCP请求报文，然后将这个报文封装在目的端口为67（DHCP服务器），源端口为68（DHCP客户）的UDP报文段中，接着又将这个报文段封装在具有广播目的IP地址255.255.255.255和本地源IP地址0.0.0.0的IP数据报中，最后封装在具有广播目的MAC地址FF-FF-FF-FF-FF-FF和电脑源MAC地址00-16-D3-23-68-8A的以太网帧中
交换机接收到帧后，向所有出端口广播
当DHCP服务器接收到帧后，分解数据包获取到DHCP请求报文，DHCP服务器管理的CIDR地址块为68.85.2.0/24，因此DHCP服务器分配空闲IP地址68.85.2.0.101给Bob电脑
DHCP服务器生成包含这个IP地址和网络掩码以及DNS服务器的IP地址68.87.71.226和网关路由器的IP地址68.85.2.1的DHCP ACK报文段，同上，依次被封装在UDP报文段、IP数据报和以太网帧中
由于交换机是自学习的，包含DHCP ACK的以太网帧的目的MAC地址是Bob电脑的源MAC地址，因此交换机知道从哪个端口转发该帧
Bob电脑接收到帧后抽取得到DHCP ACK报文，电脑上的DHCP客户程序记录下本机的IP地址以及DNS服务器的IP地址，并在其IP转发表中添加了网关路由器的IP地址
Dasi将谷歌的URLwww.google.com键入其Web浏览器的搜索栏，然后按下回车
操作系统生成一个DNS查询报文，将URL字符串放入DNS查询报文的问题字段中，然后封装在目的端口为53（DNS服务器）的UDP报文段中，接着又封装进目的IP地址为68.87.71.226的IP数据报中
操作系统在进行上一步的同时，还生成了一个ARP查询报文，先封装进目的IP地址为68.85.2.1的IP数据报中，再封装进具有广播目的MAC地址FF-FF-FF-FF-FF-FF的以太网帧中
网关路由器接收到包含ARP查询的帧，发现目的IP地址匹配到自身IP地址，因此生成了一个ARP回答报文，指示自己的MAC地址为00-22-6B-45-1F-1B
Bob电脑得到默认网关路由器的MAC地址后，再将第8步得到的IP数据报封装成以太网帧（注意这里的目的IP地址是DNS服务器的，但是目的MAC地址是网关路由器的）
网关路由器接收到该帧后，抽取IP目的地址，然后根据其转发表和BGP协议决定转发到Comcast网络中的网关路由器，该路由器收到后再一次检查IP目的地址，根据其转发表决定转发到DNS服务器
DNS服务器此时终于接收到DNS查询报文，然后在它的DNS数据库中查找名字www.google.com对应的IP地址64.233.169.105，并生成一个DNS回答报文
Bob电脑从DNS回答报文中抽取出谷歌服务器的IP地址，然后浏览器程序生成TCP套接字，与谷歌服务器中的TCP进行三次握手，先生成一个具有目的端口80（HTTP服务）的SYN报文段，封装进目的IP地址为64.233.169.105的IP数据报，再封装进MAC地址为00-22-6B-45-1F-1Bd的以太网帧
由BGP协议和AS协议实现域间和域内路由，谷歌服务器分解得到与端口80相连的欢迎套接字，随后也生成一个TCP套接字，并封装进一个SYN-ACK报文段返回
Bob电脑接收到SYN-ACK报文段并分解得到TCP套接字，从而进入连接状态
Bob电脑借助TCP套接字，生成并发送包含要获取URL的HTTP GET报文，封装进一个TCP报文段
谷歌中的HTTP服务器从TCP套接字中读取到了HTTP GET报文，并生成一个HTTP响应报文，将Web页的字节内容放入HTTP响应报文的有效载荷中，最后发送进TCP套接字中
Bob电脑上的浏览器程序获得了HTTP响应报文，抽取有效载荷中关于Web网页的html、css等数据，开始渲染，最后呈现一个Web网页在屏幕上

总结为以下步骤

获取IP地址（1-6）
获取DNS服务器的IP地址和网关路由器的MAC地址（7-10）
获取目标服务器的IP地址（11-12）
建立TCP连接（13-16）
获取HTTP内容（17-19）