Archipelago

数据链路层 + MAC 子层

讲义完成更新于 2026-08-27

摘要

MACAW: A media Access Protocol for Wireless LAN’s, SIGCOMM'94

承接视频流（Video Streaming / ABR）
后续数据中心网络架构

Lec 4 数据链路层 + MAC 子层

阅读资料

本讲导览

  • 数据链路层介绍
  • 错误检测与纠正
  • ARP 和 以太网
  • DOCSIS

数据链路层介绍

学习内容涉及两台相邻机器实现可靠有效的完整信息块（称为帧）通信的一些算法，而不像物理层那样只关注单个比特传输。这里的相邻指两台机器通过一条通信信道连接起来，通信信道在概念上就像一条线路（比如同轴电缆、电话线或者无线信道〉。信道像一条线路的本质特性使得信道上传递的比特顺序与发送顺序完全相同。

刚开始，你可能认为这个问题非常简单，似乎没有什么内容需要学习一一机器 把比 特放到线路上，然后机器 将这些比特取下来。不幸的是，通信线路偶尔会出错。而且， 它们只有有限的数据传输率，并且在比特的发送时间和接收时间之间存在一个非零延迟。 这些限制对数据传输的效率有非常重要的影响。通信所采用的协议必须考虑所有这些因素。 这些协议正是本章的主题。

提供的服务

链路层基本服务都是将数据报通过单一通信链路从一个节点移动到相邻节点。但是服务细节随着协议的不同而变化。能够提供的服务有：

  • 成帧（framing）：在通过链路传输前，都会将每个网络层数据报封装在链路层帧中。帧的结构由链路层协议规定。
    • 之所以要把比特组合成帧为单位，是为了在出错时自重发错误的帧，而不必重发全部数据
  • 链路接入。介质访问控制（MAC）协议规定了帧被传输到链路上的规则。对于简单的点对点链路，我们并不关心；有趣的情况是，多个节点共享一个广播链路，即所谓的多路访问问题。这种情况下，MAC 协议用于协调多个节点的帧传输。
  • 可靠传输。链路层的可靠传输服务通常用于高误码率的链路，如无线链路，目的是在发生错误的链路上本地纠正错误，而不是让传输层或应用层协议进行端到端的数据重传。然而，对于误码率较低的链路（如光纤、同轴电缆以及许多双绞线铜缆链路），链路层的可靠传输被认为是不必要的开销。
  • 错误检测与纠正。接收节点的链路层硬件可能会错误地将帧中的一个比特识别为 0，而实际上它是 1。这类比特错误是由信号衰减和电磁噪声引起的。相比互联网的传输层和网络层提供的有限的错误检测形式——即互联网校验和， 链路层的错误检测通常更为复杂，并在硬件中实现，接收方不仅能够检测到帧中发生了比特错误，还能够确定错误发生的具体位置（并随后纠正这些错误）

链路层哪里实现？

image-20240925211823571

主体部分在网络适配器中实现，有时也称为网络接口卡（NIC）。位于网络适配器核心的是链路层控制器，是（成帧、链路接入、差错检测等）的专用芯片。

1. 介质访问控制子层

网络链路分成两大类： 点对点连接和广播信道。这节探讨广播网络和相应的协议。关键问题在于当多方竞争信道时的使用权如何确定的问题。用来确定多路访问信道下一个使用者的协议属于数据链路层的一个子层，称为介质访问控制（Medium Access Control）子层。在局域网中，MAC 子层尤为重要，无线局域网更是如此。相反，WAN 则使用点到点链路（除了卫星网络）。技术上说，MAC 子层位于数据链路层的底部。

1.1 通道分配问题

1.2 多路访问协议

1.3 以太网

1.4 无线局域网

1.5 蓝牙（optional）

1.6 DOCSIS

1.7 数据链路层交换

许多组织有局域网，我们希望把他们连接在一起。如果我们能把多个局域网连接起来组成更大的局域网岂不是更加方便？ 我们可以通过网桥（bridge，现代名称是以太网交换机）做到这点。网桥在数据链路层，因此他们通过检查数据链路层地址（MAC 地址）来转发帧。我们首先探讨网桥的工作机制，即如何将多个物理 LAN 连接成一个逻辑 LAN。然后我们探讨如何倒过来，将一个物理 LAN 看成多个逻辑 LAN，这种技术叫 VLAN。这两种技术都提供了网络管理的灵活性。

1.7.1 网桥的使用

动机：

  • 社团 A，社团 B 因为目标不同，会选择不同 LAN，但是后面他们需要相互合作时候，这时候需要网桥打通
  • 建筑 A，建筑 B 各自弄一个独立 LAN，然后通过网桥和光纤连起来，比全部连到一个中央交换机更具性价比
  • 有时候有必要将逻辑上单个 LAN 分成多个独立的 LAN，比如上千员工，不适合将所有的连在一个交换机上，端口不够。

然而，两个独立的局域网有两倍于单个 LAN 的带宽容量。网桥让局域网结合在一起，同时保持了这种容量。这里的关键是不往不需要去的端口发送流量，使得每个局域网得以全速运行。这种行为也增加了传输的可靠性，因为单个局域网上的一个出错节点连续输出垃圾流量可以堵塞整个网络。

为了更容易获得这些好处，理想的网桥应该是完全透明的。走出去把网桥买回来，然后把 LAN 线缆插入网桥，顷刻间，一切都能很好地工作。

也可以创建一个透明的网桥。这里需要用到两种算法： 一个是后向学习算法（backward learning ），用来阻止不需要发送的流量：另一个是生成树算法（ spanning tree ），用来打破不管三七二十一把交换机线缆连接起来而可能形成的环路。

1.7.2 网桥原理

两个局域网桥接在一起的拓扑结构分两种情况。图 4.33 所示，两个多点（multidrop）局域网连接在一起。右边是局域网用点到点电缆连接在一起，包括了一个集线器。

image-20241107183623282

所有附在网桥同一端口的站都属于同一个冲突域，网桥能隔绝冲突域，但是不能隔绝广播域。在如何构建桥接局域网上，两种情况还是有区别的。为了桥接多点局域网，网桥的加入犹如在每个多点局域网上增加了一个新站（左边的情况）； 而桥接点到点 LAN，要么集线器连到网桥，或者最后换成网桥以提高性能。右边的情况，可以类比楼宇建设，楼宇之间用的是长距离光纤；其他用双绞线。

现在看内部发生什么。每个网桥工作在混杂模式（promiscuous mode）下，它接受隶属于每个端口的占发送的帧。网桥必须决定是否转发或丢弃收到的每一个帧，如果是转发还得确定在哪个端口传输帧，依据是帧的目标地址。举个例子，左边情况，

错误检测和纠正

三种数据传输中常用的错误检测技术——奇偶校验（用于解释错误检测和纠正的基本概念）、校验和方法（通常用于传输层）以及循环冗余校验（通常用于适配器中的链路层）。

循环冗余校验（CRC）相比，校验和对错误的保护相对较弱，CRC 通常在链路层中使用。此时的一个自然问题是：为什么在传输层使用校验和，而在链路层使用循环冗余校验？记住，传输层通常在主机的操作系统中用软件实现。由于传输层的错误检测是在软件中实现的，因此使用一个简单快速的错误检测方案（如校验和）是很重要的。另一方面，链路层中的错误检测是在适配器的专用硬件中实现的，这可以快速执行更复杂的 CRC 操作

多路访问协议

网络链路有两种类型：点对点链路和广播链路。点对点链路在链路的一端有一个发送者，另一端有一个接收者。许多链路层协议是为点对点链路设计的；点对点协议（PPP）和高级数据链路控制（HDLC）就是这样的协议。第二种类型的链路是广播链路，它可以有多个发送和接收节点，这些节点都连接到同一个、共享的广播信道。以太网和无线局域网是广播链路层技术的例子。广播信道常用于局域网（LAN）。

关于多路访问协议的研究产生了成千上万篇论文，我们可以将几乎所有多路访问协议归类为三类之一：信道划分协议、随机访问协议和轮流协议。

理想的广播信道多路访问协议，其速率为 R 比特每秒，应该具备以下理想特性：

  1. 当只有一个节点有数据要发送时，该节点的吞吐量为 R bps。
  2. 当有 M 个节点有数据要发送时，每个节点的吞吐量为 R/M bps。这并不意味着每个节点在任何时候都有一个恒定的 R/M 速率，而是指在某个适当的时间间隔内，每个节点应该有一个平均传输速率为 R/M 的传输速率。
  3. 协议是分散化的，即没有一个主节点作为网络的单一故障点。
  4. 协议简单，易于实现。

信道划分协议

信道划分协议（Channel partitioning protocol）

  • 频分复用（FDM）
    • 缺点是，假如只有一个人想说话，也被限制为 R/Nbps
  • 时分复用 （TDM）
    • 缺点是，假如只有一个人想说话，也被限制为 R/Nbps
  • 码分复用（CDMA）：与时分多址（TDM）和频分多址（FDM）分别为节点分配时间槽和频率不同，CDMA 为每个节点分配一个不同的码（code）。每个节点使用其唯一的码对发送的数据位进行编码。如果代码选择得当，CDMA 网络具有一个非常好的特性：不同的节点可以同时传输，而各自的接收器能够正确接收发送者编码的数据位（假设接收器知道发送者的代码），即使有其他节点的干扰传输

随机访问协议

随机访问协议（Random Access Protocol）

  • 时隙多路访问协议
  • ALOHA
  • CSMA（载波侦听多路访问）

轮流协议

交换局域网

image-20240925223727581

MAC 地址

ARP 协议

以太网

链路层交换机

交换机 vs 路由器

VLAN

现代的机构局域网（LAN）通常是分层配置的，每个工作组（部门）都有自己的交换局域网。但是这样一来有 3 个缺点

  • 缺乏流量隔离
  • 交换机的利用率低
  • 用户管理
    • 如果员工在组之间移动或者是属于两个组，问题会变得复杂

幸运的是， 支持虚拟局域网（VLAN）的交换机可以解决每一个问题。网络管理员将交换机的端口（接口）划分为多个组（未声明的端口属于默认 VLAN）。每个组构成一个 VLAN，每个 VLAN 中的端口组成一个广播域。

可以想象一下 VLAN 交换机如何实现的，交换机内部维护一个端口到 VLAN 的映射表；并且交换机硬件仅在属于同一 VLAN 的端口之间传递帧。

但是，完全隔离两个 VLAN 会引入一个新问题！如何将 EE 部门的流量发送到 CS 部门？

image-20240925224906467

一种处理方法是将 VLAN 交换机的一个端口（例如图 6.25 中的端口 1）连接到外部路由器，并将该端口配置为同时属于 EE 和 CS VLAN。在这种情况下，尽管 EE 和 CS 部门共享同一个物理交换机，但逻辑配置看起来就像 EE 和 CS 部门有各自的交换机，通过路由器相连。来自 EE 部门的 IP 数据报首先会穿越 EE VLAN 到达路由器，然后通过路由器转发到 CS VLAN，最终到达 CS 主机。幸运的是，交换机供应商通过制造同时包含 VLAN 交换机和路由器的单一设备，因此不需要单独的外部路由器。

假设不再有一个单独的计算机工程系，而是一些 EE 和 CS 的教员位于另一座建筑中，此时有两台 VLAN 交换机，又该怎么操作呢？

image-20240925224047900

Solution：

方法 1：每个交换机上定义一个属于 CS VLAN 的端口（EE VLAN 的情况类似），并将这些端口互相连接，如图 6.26(a)所示。然而，这种解决方案无法扩展，因为 N 个 VLAN 将要求每个交换机上有 N 个端口仅用于互连两个交换机

方法 2：VLAN 中继。每个交换机的一个特殊端口（左侧交换机的端口 16 和右侧交换机的端口 1）被配置为中继端口，以互连两个 VLAN 交换机。中继端口属于所有 VLAN，发送到任何 VLAN 的帧通过中继链路转发到另一台交换机。

交换机如何知道通过中继端口到达的帧属于哪个 VLAN？

IEEE 定义了一种扩展的以太网帧格式 802.1Q，用于穿越 VLAN 中继的帧。如图 6.27 所示，802.1Q 帧由标准以太网帧组成，并在帧头中添加了一个四字节的 VLAN 标记，该标记承载帧所属 VLAN 的身份。VLAN 标记由 VLAN 中继发送端的交换机添加，并由中继接收端的交换机解析并移除。VLAN 标记本身由一个 2 字节的标签协议标识符（TPID）字段（固定的十六进制值为 81-00）、一个包含12 位 VLAN 标识符字段和 3 位优先级字段的 2 字节标签控制信息字段组成

image-20240925225859210

VLAN 也被视为虚拟化云数据中心中二层网络的一个有前途的解决方案，使每个租户能够拥有自己的二层网络，从而将其流量与其他租户的流量隔离开。但问题在于：4096 个 VLAN 的上限不足以满足云主机中所有租户的需求，而且在云环境中，网络需要连接虚拟机而非这些虚拟机所在的物理主机。

Vxlan

为了解决这个问题，推出了一个称为虚拟扩展局域网 (Virtual Extensible LAN， VXLAN) 的标准。与原始方法不同，原始方法实质上是将虚拟化的以太网帧封装在另一个以太网帧内，而 VXLAN 则是将虚拟以太网帧封装在 UDP 数据包内。这意味着基于 VXLAN 的虚拟网络（通常称为覆盖网络 Overlay Network）运行在 IP 网络之上，而 IP 网络又运行在底层以太网上（或者可能只在底层以太网的一个 VLAN 中）。VXLAN 还允许云租户拥有多个 VLAN，从而可以将其内部流量进行隔离。这意味着最终可以实现一个 VLAN 封装在 VXLAN 覆盖层中，再封装在另一个 VLAN 中。

虚拟化的强大之处在于，当它做得好的时候，应该能够将一个虚拟化资源嵌套在另一个虚拟化资源中，毕竟，虚拟资源应该像物理资源一样运作，而我们已经知道如何虚拟化物理资源！换句话说，能够虚拟化一个虚拟资源，正是证明你成功虚拟化了原始物理资源的最好证据。借用“世界巨龟”的神话：这是一层又一层的虚拟网络。

VXLAN 头部实际上非常简单。它包含一个 24 位的虚拟网络 ID (VNI)，加上一些标志位。同时，这也意味着特定的 UDP 源和目标端口设置（见 5.1 节），其中端口 4789 被正式保留用于 VXLANs。要确定虚拟局域网 (VLAN 标签) 和虚拟网络 (VXLAN VIDs) 的唯一标识符是相对容易的部分，因为封装是虚拟化的基石；你只需要添加一个标识符，告诉你这个封装包属于哪个用户即可。

难的部分在于理解虚拟网络嵌套（封装）在虚拟网络内部的概念，这是网络中的递归问题。另一个挑战是理解如何自动创建、管理、迁移和删除虚拟网络，而在这方面还有很多改进空间。掌握这个挑战将是未来十年网络技术的核心，虽然其中一些工作无疑会发生在专有环境中，但也有开源网络虚拟化平台（如 Linux 基金会的 Tungsten Fabric 项目）正在引领潮流

论文阅读

Ethernet: Distributed Packet Switching for Local Computer Networks， 1975.

问题

以太网协议在有线局域网（LAN）中普遍采用，这篇文章是介绍第一版的。简单看第 6 节。它描述了一些公式，尽管不需要详细推导，但要理解这些公式对我们了解以太网的"分布式竞争模式"非常有用。

阅读时，请考虑以下问题：

  1. 作者试图解决什么问题？
  1. 他们做了什么选择，并如何解释或证明这些选择？
  1. 他们是否提到了替代方案？如果是，他们对这些替代方案有何不良评价？
  1. 这篇论文与课堂讲座之间有何联系？

知识点

几个概念

  • 计算机网络：两台或多台计算机交换消息的一种手段。
  • 本地计算机网络：物理上靠近。与“广域”网络相对。
  • 分组交换：分组交换网络发送数据包（数据 + 头部）。适合突发流量，大多数网络流量都是突发的。
  • 分布式交换：端点做出本地决策。

性能模型

以太网的性能模型可以用两个交替的时间段表示

  • 传输间隔：在期间，以太网已经成功被某个设备或站点获取数据包。
  • 竞争间隔：由重传时隙（retransmission slots）组成，期间各站点尝试获取以太网控制权。

由于模型中的以太网处于负载状态，并且各个站点在开始传输之前会推迟传输数据包，因此重传时隙会受到前一次获取间隔末尾的同步影响。换句话说，重传时隙的开始时间会根据上一个获取间隔的结束时间进行调整或同步。当一个时隙中只有一个站点尝试传输数据时，意味着这个站点已经成功获取了以太网，可以开始传输数据包。这时，竞争间隔结束，传输间隔开始，以太网被成功获取并用于整个数据包的传输。

假设：

  • P: 以太网数据包的比特数
  • C：单位时间传输的最大比特数，也称峰值容量
  • T：1 个时隙（slot）的时间，即发送数据包后检测到碰撞所需的时间长度
  • Q: 表示同时排队等待发送数据包的站点数量
  • A 是指在一个时隙（slot）中恰好有一个站点尝试发送数据包并成功获取以太网控制权的概率

在竞争时隙中，每个站点有两种选择：

  • 以概率 1/Q 发送数据包：站点根据这个概率决定在当前时隙发送数据包
  • 以概率 1-1/Q 延迟发送：站点根据这个概率决定在当前时隙不发送数据包，而是等待下一个时隙
效率计算
  • E = ( P / C ) / ( ( P / C ) + ( W * T ) )
  • W 时竞争间隔中平均等待的时隙

截屏 2024-07-04 21.56.04

问题解答

阅读时，请考虑以下问题：

  1. 作者试图解决什么问题？

作者试图解决的是在高负载情况下，以太网的性能和效率问题。特别是，他们关注的是如何在多个站点同时尝试传输数据时，确保以太网的有效利用和减少碰撞的影响。

  1. 他们做了什么选择，并如何解释或证明这些选择？

通过统计仲裁机制，每个站点根据当前网络负载估算来决定是否在当前时隙尝试传输。这种机制有助于减少碰撞并提高网络利用率.

通过将数据包的最大长度限制在接近 4000 比特，减少网络访问延迟，提高缓冲存储的效率。实验结果显示，对于大小超过 4000 比特的数据包，效率保持在 95%以上。这表明在数据包大小控制上的选择是有效的

使用几何分布模型计算站点在成功获取以太网控制权前的平均等待时间.模型计算结果与实验结果相吻合，证明这种几何分布模型在描述以太网性能方面是准确和有用的

  1. 他们是否提到了替代方案？如果是，他们对这些替代方案有何不良评价？

是的，作者提到了时隙 Aloha 网络作为替代方案。

  • 评价：时隙 Aloha 网络的效率为 1/e，作者认为这种效率在高负载情况下较低，而他们提出的分布式竞争机制在高负载情况下能保持更高的效率（如保持在 95%以上）
  1. 这篇论文与课堂讲座之间有何联系？
  • 以太网的工作原理：讲座中介绍了以太网的基本工作原理，包括数据包传输和碰撞检测机制，这与论文中详细描述的分布式竞争机制和等待时间模型直接相关。
  • 网络性能分析：讲座中讨论了网络性能和效率的分析方法，而论文第 6 节通过数学模型和实验数据具体展示了以太网在高负载情况下的性能和效率。
  • 分布式系统：讲座中可能提到了分布式系统和去中心化控制的概念，论文中以太网的设计原则和实现正是这些概念的具体应用