链路层

链路层的基本服务是将封装为帧的数据报通过单一通信链路(沿着通信路径连接相邻节点的通信信道)从一个节点(运行链路层协议协议的任何设备)移动到相邻节点

此外链路层还可能提供成帧、链路接入、可靠交付、流量控制、错误控制、差错纠正以及半双工全双工等服务
可靠交付通常在低差错链路(以太网)上很少使用，在高差错链路(无线网)上使用

链路层功能在网络适配器/网卡/NIC上实现

数据报/分组在不同的链路上以不同的链路协议传送，不同的链路协议提供不同的服务并具有不同的帧格式

差错检验和纠正

在发送节点，为了保护比特免受差错，使用差错检测和纠正(Error Detection and Correction，EDC)来增强数据D，要保护的数据通常包括帧中封装的数据报以及链路帧首部中的链路级的寻址信息、序号和其他字段
接收方的挑战是在只收到D'和EDC'的情况下，确定D'是否和初始的D相同
接收方检测和纠正差错的能力被称为前向纠错(Forward Error Correction, FEC)
例如二维奇偶校验中接收方可通过行校验和列校验定位单个比特错误并纠正

循环冗余检测

现今计算机网络中广泛应用的差错检测技术基于循环冗余检测(Cyclic Redundancy Check, CRC)编码，也称为多项式编码(polynomial code)

1. 发送方和接收方协商一个r+1比特模式，称为生成多项式G
2. 对于一个给定的数据段D，发送方选择r个附加比特R并将它们附加到D后，使得到的d+r比特模式用模2运算恰好能被G整除(模2运算等价于操作数的按位异或(XOR))
3. 接收方用接收到的d+r比特除以G，余数非零说明出现了差错

$D\cdot 2^{r}XORR=nG$ -> $D\cdot 2^r=nGXORR$ -> $R=rem[\frac{D\cdot 2^r}{G}]$

国际标准已经定义了r=8、12、16和32比特的生成多项式G
每个CRC标准都能检测小于r+1比特的突发差错。

多路访问协议

节点之间的连接方式包括点对点链路以及多点链路
点对点链路由链路一端的单个发送方和链路另一端的单个接收方组成。
多点链路让多个发送和接收节点都连接到相同的、单一的、共享的广播信道上。当任何一个节点传输一个帧时，信道广播该帧，每个其他节点都收到一个副本
广域网WAN通常采用点到点链路
局域网LAN一般采用多点链路

多路访问协议(multiple access protocol)协调多个发送和接收节点对一个共享广播信道的访问，决定节点如何使用共享信道

理想的多路访问协议：

• 给定Rbps的广播信道，当一个节点要发送时，可以R速率发送
• 当M个节点要发送，每个节点以R/M的平均速率发送
• 完全分布，无专门的控制节点，节点之间不用同步
• 相对简单

多路访问协议包括三种类型：信道划分协议、随机接入协议、轮流协议

信道划分协议

时分多路复用TDM、频分多路复用FDM和码分多址(Code Division Multiple Access, CDMA)是三种信道划分协议
TDM将时间划分为时间帧，并进一步划分每个时间帧为N个时隙，然后把每个时隙分配给N个节点中的一个。在有分组要发送的时候，节点在循环的TDM帧中指派给它的时隙内传输分组比特
FDM将信道划分为不同的频段，并把每个频率分配给N个节点中的一个
CDMA对每个节点分配一种不同的编码，然后每个节点用它唯一的编码来对它发送的数据进行编码，可以实现所有节点在整个频段上同时进行传输, 采用编码原理加以区分

随机接入协议

当节点有帧要发送时以信道带宽的全部速率Rbps发送，当发生碰撞时，涉及碰撞的每个节点等待一个随机时延后重发帧，直到该帧无碰撞地通过为止

时隙ALOHA

时隙ALOHA假设：

• 所有帧是等长的L比特
• 时间被划分成相等的时隙，每个时隙可发送一帧
• 节点只在时隙开始时发送帧
• 节点在时钟上是同步的
• 如果两个或多个节点在一个时隙传输，所有的节点都能检测到冲突

运行：

• 当节点获取新的帧，在下一个时隙开始时传输
  • 传输时没有检测到冲突，成功，节点能够在下一时隙发送新帧
  • 检测时如果检测到冲突，失败，节点在每一个随后的时隙开始时以概率p重传帧直到成功

载波侦听多路访问(CSMA)

CSMA令节点在传输前先侦听信道，如果侦听到信道空闲，传送整个帧，如果侦听到信道忙，推迟传送
由于传播延迟仍可能导致碰撞冲突

CSMA/CD为具有碰撞检测的CSMA，其令传输节点在传输时一直侦听信道，如果它检测到另一个节点正在传输干扰帧，它停止传输，等待一段随机时间后重复“侦听-当空闲时传输”循环。

二进制指数退避算法用于确定检测节点停止传输后的等待时间，对于当前传输帧，在该帧经历了n次碰撞后，节点随机地从{0, 1, 2,…，2^n-1}中选择一个K值，一个帧经历的碰撞越多，K选择的间隔越大。
对于以太网，一个节点等待的实际时间量是K・512比特时间(即发送512比特进入以太网所需时间量的K倍)，n的最大值限制为10

CSMA/CA用于无线局域网(无线链路特性：每帧需要ACK确认)
由于节点自身信号远远大于其他节点信号，无线局域网无法检测冲突，且无线局域网中是否冲突与传输是否成功之间无明确关联

发送方

1. 如果站点侦测到信道空闲持续DIFS(分布式协调帧间隔)长，则传输整个帧
2. 如果侦测到信道忙碌，那么设置一个随机回退值，并在侦测到信道空闲时递减该值(如果信道忙碌，回退值不会变化)
3. 回退到0时发送整个帧，如果没有收到ACK, 增加回退值，重复步骤2

接收方

• 如果帧正确，则在SIFS(短帧间隔)后发送ACK

CSMA/CA也无法完全避免冲突，可以采用小的预约分组完全避免数据帧的冲突

1. 发送方首先使用CSMA向接收方发送一个小的RTS分组(RTS可能会冲突，但是由于比较短，浪费信道较少)
2. 接收方广播CTS(clear-to-send)作为RTS的响应，CTS能够被所有涉及到的节点听到
3. 发送方发送数据帧，其它节点抑制发送

轮流协议

信道划分协议在高负载时共享信道有效且公平，低负载时效率低下
随机访问MAC协议低负载时效率高，高负载时冲突开销较大，效率极低

轮询协议

节点之一被指定为主节点，主节点以循环的方式轮询每个从节点，告知从节点能够传输的帧的最大值。
主节点能够通过观察在信道上是否缺乏信号，来决定一个节点何时完成了帧的发送。

缺点:

• 轮询开销：轮询本身消耗信道带宽
• 等待时间：每个节点需等到主节点轮询后开始传输，即使只有一个节点，也需要等到轮询一周后才能够发送
• 单点故障：主节点失效时造成整个系统无法工作

令牌传递协议

一个称为令牌(token)的小的特殊帧在节点之间以某种固定的次序进行交换
当一个节点收到令牌时
如果它确实有帧要传输，它发送最大目的帧数，然后把令牌转发给下一个节点
否则它立即向下一个节点转发该令牌

缺点:

• 令牌开销：本身消耗带宽
• 延迟：只有等到令牌才可传输
• 单点故障：令牌丢失系统级故障，整个系统无法传输，重新生成令牌机制复杂

DOCSIS：用于电缆因特网接入的链路层协议

DOCSIS是运用多种多路访问协议的一个例子

一个电缆接入网通常在电缆网头端将几千个住宅电缆调制解调器与一个电缆调制解调器端接系统(Cable Modem Termination System, CMTS)连接
数据经电缆服务接口(Data-Over-Cable Service Interface, DOCSIS)规范定义了电缆数据网络体系结构及其协议。

DOCSIS使用FDM将下行(CMTS到调制解调器)和上行(调制解调器到CMTS)网络段划分为多个频率信道，每个上行和下行信道均为广播信道。
每条上行信道被划分为时间间隔(类似于TDM)，每个时间间隔包含一个微时隙序列，电缆调制解调器可在该微时隙中向CMTS传输

电缆调制解调器在一组特殊的微时隙间隔内向CMTS发送微时隙请求帧请求数据发送
CMTS在下行信道上通过发送称为MAP报文的控制报文，显式指定哪个电缆调制解调器(带有要发送的数据)能够在微时隙中传输由控制报文指定的时间间隔
由于微时隙明确分配给电缆调制解调器，故CMTS能够确保在微时隙中没有碰撞传输

电缆调制解调器如果没有在下行控制报文中收到对请求分配的响应的话，就推断出它的微时隙请求帧经历了一次碰撞
当推断出一次碰撞，电缆调制解调器使用二进制指数退避将其微时隙请求帧延缓到以后的时隙重新发送
当在上行信道上有很少的流量，电缆调制解调器可能在名义上分配给微时隙请求帧的时隙内实际传输数据

交换局域网

链路层寻址

MAC地址

主机或路由器的网络适配器具有链路层地址，也被称为 LAN 地址、物理地址或 MAC 地址
MAC 地址用于在局域网中唯一标识和定位设备，使帧从一个网卡定点传递到与其物理连接的另一个网卡，具有扁平结构，与物理设备相绑定，不随设备位置和接入子网的改变而改变
MAC 地址长度为48bit，通常用十六进制表示法，地址的每个字节被表示为一对十六进制数，e.g. 1A-2F-BB-76-09-AD
MAC 地址由 IEEE 管理和分配，理论上全球任何设备的 MAC 地址都不相同，制造商购入 MAC 地址空间制造适配器保证唯一性

当适配器接收到一个帧时，将检查该帧中的目的 MAC 地址是否与其自身的 MAC 地址匹配
如果匹配，该适配器提取出封装的数据报，并将该数据报沿协议栈向上传递
如果不匹配，该适配器丢弃该帧

发送适配器可将帧的目的地址字段设为一个特殊的 MAC 广播地址来让局域网上所有其他适配器来接收并处理该帧
对于使用6字节地址的局域网来说，广播地址是48个连续的1组成的字符串(即以十六进制表示法表示的 FF-FF-FF-FF-FF-FF)

ARP 协议 - 地址解析

地址解析协议(Address Resolution Protocol, ARP)被用于网络层地址(e.g.IP)和链路层地址(MAC)的转换

每台主机或路由器在其内存中具有一个 ARP 表，包含 IP 地址到 MAC 地址的映射关系和该关系的寿命值(TTL)

当 A 要发送帧给同一局域网中已知 IP 地址但 MAC 地址未知的主机 B 时

1. A 通过地址 FF-FF-FF-FF-FF-FF 广播包含 B 的 IP 地址的 ARP 查询包
2. 局域网上的所有节点都会收到该查询包，B 接收到该包后使用 A 的 MAC 地址向 A 回复自己的 MAC 地址
3. A 在自己的 ARP 表中新增 B 的 IP-MAC 地址映射关系缓存，直到信息超时

当 A 要发送帧给不同局域网中已知 IP 地址但 MAC 地址未知的主机 B 时

1. A 创建一个链路层的帧，目标 MAC 地址是本局域网的网关路由器 R，该帧包含 A 到 B 的 IP 数据报
2. 帧被 R 接收到，从中提取出 IP 分组，交给上层 IP 协议实体
3. R 根据路由转发表转发数据报，数据报源 IP 地址为 A，目标 IP 地址为 B
4. R 创建一个链路层的帧，目标 MAC 地址为下一跳的路由器，帧中包含 A 到 B 的 IP 数据报

以太网

以太网提供无连接、不可靠的服务
以太网使用 CSMA/CD 多路访问协议

以太帧结构

• 数据字段(46 ~ 1500字节)- 以太网的最大传输单元 MTU 是1500 字节
• 目的地址(6字节)
• 源地址(6字节)
• 类型字段(2字节)- 高层协议类型
• CRC (4字节)- 循环冗余检测
• 前同步码(8字节)- 用于同步接收方和发送方的时钟频率(7字节 10101010 + 1字节 10101011)

交换机

目前以太网大多为星形结构，主机和路由器都与交换机相连，交换机由集线器进化而来
集线器在一个碰撞域同时只允许一个站点发送，而交换机允许多个同时发送
集线器将收到的数据包广播到所有连接的设备，而交换机会根据目标 MAC 地址将数据包只发送到目标设备，避免了网络冲突和无谓的带宽浪费

• 交换机对帧进行存储，转发和过滤，其输出接口设有缓存
• 交换机自身对子网中的主机和路由器等同于不存在
• 交换机对每个帧进入的链路使用以太网协议，无碰撞，全双工

交换机借助交换机表完成链路层帧的转发或过滤，交换机表包括

• 一个MAC地址
• 通向该MAC地址的交换机接口
• 表项放置在表中的时间

发送方式：
对于到来的链路层帧，交换机在交换机表中查询其目标MAC地址

• 表中没有相应表项 - 交换机向除输入接口外的所有接口前面的输出缓存转发该帧的副本，换言之广播该帧
• 表中存在相应表项，但对应输出接口与输入接口相同 - 交换机通过丢弃该帧执行过滤功能
• 表中存在相应表项，对应输出接口与输入接口不相同 - 交换机将该帧放到相应输出接口前面的输出缓存，完成转发功能

交换机即插即用，无需配置，通过自学习更新交换机表

1. 交换机表初始为空
2. 对于在每个接口接收到的每个入帧，该交换机在其表中存储：
   • 在该帧源地址字段中的MAC地址
   • 该帧到达的接口
   • 当前时间
3. 如果在一段时间(老化期)后，交换机没有接收到以该地址作为源地址的帧，就在表中删除这个地址

三层交换机

三层交换机是在网络层上工作的网络设备，与二层交换机只能通过 MAC 地址进行数据帧交换不同，三层交换机还能根据 IP 地址进行数据包的转发，实现更高级别的路由功能

路由器的转发采用最长匹配的方式，实现复杂，通常使用软件来实现。而三层交换机的路由查找是针对流的，它利用 CACHE 技术，很容易采用 ASIC 实现，因此可以大大节约成本，并实现快速转发

从技术上讲，路由器和三层交换机在数据包交换操作上存在着明显区别
路由器一般由基于微处理器的引接执行数据包交换，而三层交换机通过硬件执行数据包交换，因此与三层交换机相比，路由器功能更为强大，像 NAT、VPN 等功能仍无法被完全替代

从整体性能上比较的话，三层交换机的性能要远优于路由器，非常适用于数据交换频繁的局域网中
而路由器虽然路由功能非常强大，但它的数据包转发效率远低于三层交换机，更适合于数据交换不是很频繁的不同类型网络的互联，如局域网与互联网的互联

虚拟局域网VLAN

虚拟局域网(Virtula Local Network，VLAN) 通过交换机实现
支持 VLAN 的交换机允许经一个单一的物理局域网基础设施定义多个虚拟局域网
在一个 VLAN 内的主机彼此通信，仿佛只有它们与交换机连接

在一个基于端口的 VLAN 中，交换机的端口(接口)由网络管理员划分为组
每个组构成一个 VLAN，每个 VLAN 中的端口形成一个广播域(即来自一个端口的广播流量仅能到达该组中的其他端口)

同一交换机下不同 VLAN 的交流方法：

• 各自外接路由器，通过路由器传递消息，仿佛 VLAN 各自属于独立的交换机
• VLAN 干线连接 - 每台交换机上的一个特殊端口被配置为干线端口，以互联两台 VLAN 交换机。该干线端口属于所有 VLAN，发送到任何 VLAN 的帧经过干线链路转发到其他交换机。