未来网络技术网

【Sigcomm 2023】 Achelous：超大规模云网络中如何实现网络的可编程性、弹性和可靠性

Fri, 06 Oct 2023 19:52:39 +0800

0、摘要

云计算取得了巨大的增长，促使企业迁移到云端以获得可靠且按需购买的计算力。在单个 VPC 内，计算实例（如虚拟机、裸金属、容器）的数量已达到数百万级别，VPC 实例规模达到百万量级，将会对云网络的热迁移、高弹性、高性能和高可靠性都带来了前所未有的挑战。然而，学术届主要集中在高速数据平面和虚拟路由基础设施等具体问题上的研究上，而工业届现有的网络技术无法充分应对这些挑战。

在本文中，我们将阐述阿里云网络虚拟化平台 Achelous 的相关设计和经验。Achelous 包含三个实现超大规模 VPC 的关键设计：

◼ (𝑖) 一种基于数据平面和控制平面协同设计的新颖的分层编程架构；

◼ (𝑖𝑖) 分别用于无缝纵向扩展（scale-up）和横向扩展（scale-out）的弹性性能策略和分布式 ECMP 方案；

◼ (𝑖𝑖𝑖) 健康检查方案和透明的虚拟机实时迁移机制，可以确保故障转移期间的状态流（stateful flow）的连续性。

评估结果表明，Achelous 可以在减少 25 倍的编程时间（配置变更）的前提下，将单个 VPC 中将虚拟机的规模扩展到超过 1,500,000，并且 99% 的配置更新都可以在 1 秒内完成。

对于故障转移（failover），它将虚拟机热迁移期间的停机时间压缩了 22.5 倍，并确保了 99.99% 的应用程序不会出现停顿。更重要的是，三年的运营经验证明了 Achelous 的耐用性，以及独立于任何特定硬件平台的多功能性。

1、介绍

多年来，云计算持续增长，有前景的新兴云服务（如无服务（serverless）、AI 训练和数字办公）更加强化了这一趋势。大型企业将业务迁移至云端，以寻求灵活的扩展能力来应对不断变化的业务需求，这往往会带来网络峰谷现象。同时，租户期望云中的网络服务能像物理网络一样可靠。这些综合需求对云网络的设计提出了重大挑战。然而，学术研究主要集中在高速数据平面和虚拟路由基础设施等具体问题上，而现有的工业网络技术难以支持超大规模的云网络。例如，Google 在其虚拟云网络 Andromeda 中提出了 Hoverboard，以便在其云网络中能够提供高性能、隔离的超大规模 VPC。然而，这些技术不足以解决现代云中应用带来的网络可扩展性和突发性的性能问题等更重大挑战。

我们的经验告诉我们，整个云网络系统（控制器、网关和 vSwitches 等）构成一个集成系统一起协调工作。在控制器、网关和 vSwitches 等网络基础设施之间如何分配云网络系统的功能非常重要。下面，我们将重点介绍下现代云环境中遇到的三个主要挑战。

挑战一：百万级别实例的配置更新时间为亚秒级（sub-second）

第一个重大挑战源于电子商务业务（例如淘宝）在向云迁移的过程中，导致在单个 VPC 中部署了大量实例（例如VM、BM 和 Container）。

图 1 展示了阿里巴巴单个 VPC 内电子商务实例呈现指数级增长的典型例子，到 2022 年单个 VPC 内将达到 1,500,000 个实例。超大规模网络呈现出两个关键特征：实例部署密度和实例创建/销毁频繁。例如，在流量高峰期间，我们可能需要额外启动 20,000 个容器实例，每个容器实例的生命周期只有几分钟。

现有的网络编程方法无法同时处理如此大批量实例的创建和准备工作。例如，Andromeda 在论文中提出了一种可扩展到 100,000个（十万级别）实例的设计，根据最新报告，AWS 支持每个 VPC 最多 256,000 个（二十五万级别）实例。然而，在阿里云内部，单个 VPC 需要支持的实例数量比任何现有技术所能容纳实例数量都要高出一个数量级。这些超大规模 VPC 的激增导致路由条目大幅增加以及高频率的网络变化，对网络收敛速度提出了挑战。具体来说，云供应商必须能够在有限的时间内提供服务，例如能够在 1 秒内启动大量网络连接准备就绪的 serverless 容器。

挑战二：适合大流量网络中间设备（middle-box/云网关）部署的高弹性网络

第二个重大挑战来自于将传统的重负载网络应用（例如 middle-box），迁移到云中的虚拟机 (VM) 上。最初，这些中间件（例如负载均衡器、NAT 网关和防火墙）部署在物理网络内的专用硬件上。将它们迁移到 VM 中可以提供网络按需弹性和进行企业成本优化的优势。然而，这种转换破坏了最初通过专用网络设备提供的隔离性，可能导致与同一主机上的其他实例发生资源争抢（网络和 CPU 资源）。此外，middle-box VM 必须表现出弹性可扩展性（包括纵向扩展（scale-up）和横向扩展（scale-out）），以有效处理因为客户的容量需求变换而导致的流量变化。

不幸的是，现有的研究未能考虑到资源争抢的情况，因此不适合在多租户云主机上提供隔离但弹性的资源分配。在横向扩展（scale-out）场景方面，负载均衡和传统的 ECMP 路由机制引入了新的瓶颈。由于它们处理来自数百万个虚拟机的流量，集中式负载均衡器和 ECMP 转发节点成为网络可扩展的主要限制因素。

挑战三：云服务高可用性和高可靠性

对于云厂商来说，资源利用率和可靠性是云平台的重要指标。然而，检测故障并快速实现故障转移对云网络提出了重大挑战。虚拟网络和物理设备之间的动态映射使得建立精确的拓扑变得非常困难，这反过来又阻碍了故障遥测。现有的故障遥测技术要么关注于物理网络，要么缺乏实时性，无法保证虚拟网络的可靠性。更加复杂的是，大多数热迁移技术忽视了有状态流的流量连续性，从而导致租户服务中断。

考虑到上述挑战，我们在三年前就开始重新构建我们的网络架构。我们发现当前无法通过独立的网络组件设计（即控制器、网关或 vSwitch）来满足这些要求。于是我们提出了阿里云的网络虚拟化平台 Achelous，可以在超大规模云网络中实现网络的可编程性、弹性和可靠性。我们重点介绍下基于我们丰富的运营经验总结出的三个主要设计点：

首先，为了解决转发表较大和收敛速度较慢的挑战，我们提出了一种新颖的编程机制，该机制按需主动从网关而不是从控制器学习转发信息。控制器只需将转发信息下发到网关，而不用下发到每台主机上的 vSwitch 上（§4.1）。我们还设计了一个轻量级的转发缓存，可以对网络进行 IP 粒度的有效管理，以进一步缩小表项结构的大小（§4.3）。

其次，为了在保证性能隔离的同时实现主机内的可扩展性，我们提出了一种新颖的弹性策略，以在隔离和突发流量之间取得平衡，并实现带宽和CPU资源的高利用率（§5.1）。此外，我们演示了一种分布式 ECMP 机制，将流量重定向到多个 vSwitch，以实现主机之间服务的无缝横向扩展（§5.2）

最后，我们提出了一种链路健康检查方案用来验证 vSwitch 和 VM 之间的网络链路状态，以及一个用于检测 vSwitch 本身状态的监视器（§6.1）。

此外，我们还介绍了一系列透明的虚拟机实时迁移技术，包括流量重定向、会话重置和会话同步。这些技术缩短了 VM 迁移停机时间，在应用无感知的情况下支持无状态和有状态流的连续性（§6.2）。

我们的部署和评估结果验证了这些设计选择是有效的。多年来 Achelous 一直是阿里巴巴 VPC 网络的基石，它显著改善了用户的用云体验。值得注意的是，99% 的服务启动延迟小于 1 秒，99.99% 的应用没有出现卡顿。经过多年的运营，我们相信 Achelous 的设计选择不仅可行而且非常有效，该经验教训（§8）可以广泛应用于其他云供应商。

本文主要做出以下贡献：

◼ 我们提出了一种新颖的具有优化的表结构的按需主动学习编程机制，以加速超大规模 VPC 的网络覆盖。在包含超过 150 万 VM 实例的 VPC 中，配置可以在 1.33𝑠 内完成覆盖。与传统部署模式相比，我们的机制将配置收敛时间提高了 25 倍以上。

◼ 我们提出了弹性网络容量策略和分布式 ECMP 机制，支持主机间隔离的前提下的纵向扩展和无缝横向扩展。对于重载网络服务，我们支持 0.3𝑠 以内无缝扩缩容。

◼ 我们为 VM 设计了一整套故障检测和避免机制，其中包括丰富的健康检查方法和无缝热迁移方案。通过这些机制，VM 的故障转移延迟约为 100𝑚𝑠，从而不会影响 guest VM 内的应用程序

2、背景与动机

Achelous 是阿里云的网络虚拟化平台，在过去十年中不断发展以支持阿里云虚拟网络。在经历了 Achelous 1.0 和 Achelous 2.0 阶段，它的性能得到了显著改进。

随着云网络不断扩展，新的挑战不断出现，促使我们增强和迭代 Achelous 2.0。在本节中，我们将讨论 Achelous 的演变、Achelous 2.0 中的 VM 网络数据路径以及遇到的新的挑战。

2.1 Achelous 在阿里云中的作用

在阿里云中，Achelous 通过三个基本组件提供 VM 网络虚拟化（如图 2 所示）：控制平面的 SDN 控制器，数据平面的vSwitch 和 Gateway。

在控制平面上，控制器管理实例（例如虚拟机、裸金属）生命周期中的所有网络配置，并将网络规则发布到 vSwitch 和网关。例如，一旦创建了 VM 实例（例如 VM1），控制器会将所有现有 VM1 的网络转发信息发布到 vSwitch 和网关。然后，如果 VM1 的网络发生变化（例如迁移到另一台宿主机、增加新的网卡），控制器将更新并更正数据平面中的相应规则。

在数据平面上，vSwitch 作为每个 Host 上专用于 VM 流量转发的交换节点。网关作为促进不同域之间的互连的更高层级转发组件。在图 2 中，我们提供了一个示例：

当 VM1 的数据包被 vSwitch 处理时，它会确定适当的目的地。如果目的 VM 与 VM1位于同一宿主机上（例如 VM2），则vSwitch 直接转发数据包。否则，如果目标 VM 与 VM1 位于不同的宿主机上（例如裸金属），则数据包将通过网关进行中继。有关网关的更多详细信息，请参考阿里云关于 Sailfish 网关的相关论文，Sailfish 支持在各种硬件平台上进行部署。

2.2 Achelous 的进化

Achelous 的初始版本 Achelous 1.0 的开发始于十多年前，它为阿里云提供了基础的虚拟网络环境。由于其开发时间早于 VXLAN 标准的制定，Achelous 1.0 经历了从 classic 二层网络到标准 VPC overlay 网络的架构转变。这一演进通过 VXLAN 网络标识符 (VNI) 进行 Guest VM 的二层隔离，从而增强了网络的安全性。然而，由于 Achelous 1.0 数据平面通过基于 Linux 内核中的 netfilter 模块实现，这将始终成为网络瓶颈。

在 Achelous 2.0 中，通过 DPDK 加速和硬件卸载，数据平面性能得到了显着提高。这些加速方法有效地减少了数据路径上的数据包 copy 开销，这对于转发性能来说至关重要。此外，Achelous 2.0 中的优化涉及 offload 东西向流量（VM-VM 流量）以缓解潜在的性能瓶颈。由于东西向流量占总流量的 3/4 以上，在依靠网关进行中继时会带来更明显的转发瓶颈。在 Achelous 2.0 中，控制器向 vSwitch 下发所有的东西向转发规则，以便 vSwitch 之间可以直接转发东西向流量（见图 2）。然而，这会带来挑战一（§2.4），因为当网络发生变化时，每个 vSwitch 都要被下发正确的转发规则。

2.3 Achelous 2.0 中的 VM 数据路径

为了读者对该平台能有更深入了解，我们简要介绍下 Achelous 2.0 的 VM 网络数据转发路径上的关键流程和数据结构。

Achelous 2.0 的 VM 网络数据转发路径（图 3）由两部分组成：慢速路径和快速路径。

慢速路径：包含一个由各种表组成的数据包处理 pipeline，每个表都提供特定的功能逻辑。这些表包括 ACL、QoS、VXLAN 路由表（VRT）、VM-HOST 映射表（VHT）（即 vm_ip - host_ip 映射关系）等。所有表均由控制器下发配置，其中 VHT 尤其重要。随着 VPC 内虚拟机数量的增加，VHT 大幅扩容，导致条目激增。

快速路径：针对快速路径我们首先引入一种称为 会话（session） 的新数据结构，它由一条流的两个方向的 flow entry（即原始方向的 oflow 和反向的 rflow）以及数据包所需的所有状态组成。

flow entry 包含报文的五元组，采用精确匹配算法。报文处理流程如下：

◼ 1）第一个报文通过慢速路径的 pipeline 进行处理；

◼ 2）然后生成五元组 flow entry 表项及其会话，并将其添加到快速路径中；

◼ 3）后续报文可以直接在快速路径上进行匹配和处理。

Achelous 2.0 中快速路径和慢速路径之间的性能差距很大，快速路径比慢速路径表现出 7-8 倍的性能优势。这会导致专用于网络处理的 CPU 消耗和性能对于来自不同流的数据包有所不同。例如，具有大量短连接的 VM 可能会独占高达 90% 的 vSwitch CPU 资源，从而影响其他 VM 的转发。这加剧了挑战二（§2.4）。

此外，对超大规模 VPC 网络的需求放大了 Achelous 2.0 数据平面和控制平面中设计“缺陷”，特别是在适应电子商务和 middle-box 迁移上云等新业务场景方面。

2.4 Achelous 2.0 面临的挑战

与云厂商管理的有限 VPC 网络规模相比，超大规模 VPC 的新场景下部署下带来了三大严峻挑战：

◼ （1）路由表越大，收敛速度越慢。

最关键考虑因素之一是控制平面的可扩展性。一方面，大型网络的扩展性需要更大的路由表，例如 VHT 和 VRT，从而导致资源受限的 Host 或 DPU/CIPU 上的内存消耗增加。例如，在阿里云中，VPC 可以容纳超过150 万个 VM，从而导致表项数量庞大，并消耗数 GB 内存来实现高效的数据包转发。

另一方面，还存在管理大量表项并发条目变更请求的问题。我们的实证分析表明，控制平面每天收到超过 1 亿次网络变更请求。如此大量请求的涌入对网络收敛提出了挑战，而网络收敛是网络弹性扩展和故障转移的关键因素。

◼ （2）在保证公平性和隔离性的同时平衡闲置资源和突发流量。

随着 VM 部署密度的不断增加，对网络弹性可扩展能力的需求也日益迫切。通过在阿里云的实际运行情况进行分析，我们揭示了以下发现：

◼ 1）超过 98% 的虚拟机平均吞吐量低于 10Gbps，表明网络资源严重闲置（见图 4a）；

◼ 2）网络流量突发每天都会发生，导致数据平面带宽和 CPU 资源的竞争（见图 4b）；

例如，视频会议服务在上班时间会出现流量突发的情况，同时在下班时间只有较少的带宽。为了平衡闲置资源和突发流量，在保持公平性和隔离性的同时资源分配实现高弹性势在必行。此外，大流量租户在面临流量突发时需要具有跨多个 Host 的无缝弹性扩展能力。

◼ (3) 检测网络风险并在租户无感知的情况下逃逸。

随着 VPC 网络配置的日益复杂，保证网络的高可靠性至关重要。传统上，网络运维严重依赖人工干预，导致缺乏故障预测的能力。

租户报障通常需要花费大量时间和精力来进行定位和解决。尽管我们已经开发了各种网络故障定位技术，但在租户报障之前进行故障检测仍是一个挑战。

在超大规模 VPC 的背景下，为了能够不间断地向租户提供服务，网络风险感知方法对于早期故障的检测与避免变得越来越重要。此外，无感知的热迁移技术对于帮助租户将 VM 从故障 Host 或网络进行迁移时确保流量不被中断至关重要。

上述挑战促使我们重新思考 Achelous 中数据面和控制面的设计，并做出相应的创新。

3、设计概览

为了应对规模爆炸带来的挑战，我们在 Achelous 2.1 中进行了创新设计和改进。我们探索数据面和控制面之间的协同设计，避免单个组件过度优化。主要包含以下三个关键改进：

◼ 超大规模网络可编程性。

为了减少网络收敛时间并提高 Host 中的内存利用率，我们在 Achelous 2.1 中提出了转发信息主动学习机制（§4.1）。在该机制中，vSwitch 仅管理转发缓存，并通过路由同步协议（RSP）主动从网关学习路由信息。

因此控制器只需要对网关进行网络编程，而不需要对每个 vSwitch 节点进行网络编程。这种方法可以通过高性能数据平面实现网络的快速更新，并确保以最短的收敛时间同步到受影响的 vSwitch。因此，我们可以避免在每台 Host 上存储完整的转发信息，从而将每台服务器的内存利用率和可扩展性提高了一个数量级。

◼ 网络容量弹性。

Achelous 通过无缝的纵向扩展和横向扩展以实现基于隔离的网络性能的高弹性。在数据面中，网络容量是通过专用 CPU 核心提供的，因此需要考虑所有可用的资源。Achelous 2.1 采用弹性策略（§5.1）为 Host 内的所有虚拟机分配带宽和CPU 资源，不仅可以充分利用空闲资源应对突发流量，而且可以保证性能隔离。此外，为了在 Host 之间提供服务的无缝扩展，我们在每个 vSwitch（Achelous的边缘节点）中实现了分布式 ECMP 机制（§5.2），消除了与 undelay 网络集中部署相关的转发瓶颈。

◼ 网络风险感知和热迁移。

Achelous 执行网络链路健康检查，主动感知和预警发生的故障，例如网络发生拥塞或 VM halt（§6.1）。这涉及 vSwitch 根据预配置的检查列表向 VM 周期性的发送运行状况检查数据包。与此同时，vSwitch 自身向控制器报告性能统计数据，从而实现主动干预以减轻网络风险。一旦检测到风险，vSwitch 就会在控制器的指导下提供透明的虚机热迁移以进行故障转移。在迁移过程中，Achelous 实施流量重定向、会话重置和会话复制技术（§6.2），以满足不中断应用服务的网络属性（例如较短的停机时间、无状态流、有状态流和应用程序无感知）。

4、超大规模网络编程

在本节中，我们将介绍 Achelous 2.1 的设计，其目标是 §2.4 中的挑战一。我们详细介绍了为超大规模云网络开发的编程机制，命名为主动学习机制（ALM）。

4.1 ALM 设计

问题与目标。

高内存消耗仍然是大规模转发表的关键挑战。在软转架构中，vSwitch 与 VM 共享 Host 的内存，超大规模转发表项使用了大量内存，可能会导致 Host 内存资源紧张。在硬转架构中，专用硬件上可用高速片上存储器的资源十分有限，进一步加剧了存储器资源的紧张。

更糟糕的是，当大规模转发表遇到高并发的网络变更请求时，控制器无法及时通知到每个受影响的 vSwitch，控制器从而成为配置变更的瓶颈。因此，我们的目标是在 Achelous 中开发一种有效的编程机制用来服务于超大规模网络。

洞察力。

我们的主要观点是，数据中心网络为了处理故障、进行部署/升级服务、并适应网络流量的波动，需要不断的进行网络变更。

因此，虚机或容器的位置可能会因虚机迁移、虚拟故障和虚机创建/释放事件而频繁变化。具体一点，就是 VXLAN 路由表（VRT）和虚机-宿主机映射表（VHT）会经历高频变更。另一方面，vSwitch 上的配置表（例如 ACL 和 QoS）更改频率较低。例如，租户安全组配置保持相对稳定，而 VHT 在业务扩展或收缩的过程中进行更新。因此，我们就可以将经常变更的表项转移到强大的网关上，从而合理的减少 vSwitch 的资源消耗，提高整体效率。

设计概述。

我们会根据长期的生产经验，持续对我们的 Achelous 设计进行迭代。

ALM 是我们在单 VPC 支持百万级 VM，迈向超大规模 VPC 的最新举措。如图 5 所示，ALM 需要对 Achelous 中的所有三个核心组件进行修改。ALM 的核心思想是将控制器从下发网络变更的繁重负担中解放出来，让 vSwitch 按需主动通过网关同步转发规则。

据此，我们进行了如下设计：

◼ 1）轻量级转发表，命名为转发缓存（FC）表，以提高内存使用率；

◼ 2）按需转发规则同步机制，以实现更快的网络收敛。

4.2 具有数据包分层处理路径的轻量级转发表

轻量级转发表。

我们引入了轻量级转发缓存（FC）表以实现高效的软转发。vSwitch 不依赖 VRT/VHT 转发条目，而是利用从网关获知的紧凑的 “目的 IP -> 下一跳” 映射关系。

首先，以目的 IP 为维度的转发 entry 更加紧凑并且可以覆盖更多的 VM-VM 的转发流量，因为 VM-VM 的多个流仅重用一个 entry。

我们可以将以端口号为维度的流表条目减少到以 IP 为维度的流表条目，在极端情况下这可能会减少 65535 倍的存储空间。

其次，通过从将基于流的转发表转变为基于 IP 的转发表，我们解决了可能利用元组空间爆炸 (TSE) 进行的漏洞攻击，TSE 是一种针对软件包分类器的 DOS 攻击。

分层的数据包处理路径。

如图 5 所示，在解析 VXLAN 数据包的内部报头的目标 IP 后，后续的数据包处理遵循分层的数据路径：

◼ 1）快速路径：快速路径与 §2.3 所述相同，作为与业务逻辑无关的高性能加速路径。在快路径中不匹配的报文将被上送到慢路径；

◼ 2）慢速路径：慢速路径上原来的 VHT 和 VRT（见§2.3）被 FC 替换，但 ACL 和 QoS 表仍然保留。

慢速路径按需从网关获取转发信息更新 FC 表项，该表项很小，只需要占用很小的内存。

具体来说，慢速路径根据每个数据包的 “Dst IP” 查找 FC。如果 FC 未命中，数据包将被上送到网关 ① ，并最终转发到目的地 ②。而命中 FC 的数据包将生成一条快速路径 entry 添加到快速路径表中，并将数据包直接路由到目的地 ③。

Achelous 中的分层数据包处理设计简化了 vSwitch 内的转发表数据结构和数据包处理逻辑。通过利用网关存储和管理整套转发规则，vSwitch 可以按需同步转发条目，从而显著减少每个 vSwitch 节点的内存开销。

这种设计方法还将 vSwitch 与复杂的路由逻辑解耦，从而提高转发性能、增强多功能性并简化维护。

4.3 转发规则按需同步机制

流量驱动的主动学习机制。

除了在数据面中的作用之外，Achelous 架构中的网关还充当控制面转发规则调度程序。vSwitch 节点通过路由同步协议 (RSP)（私有协议）从网关按需学习转发规则。

如图 6 所示，RSP 有两种报文类型：请求报文和应答报文。请求报文包含流的五元组，应答报文包含相应请求的下一跳信息。

vSwitch 根据流量时长、吞吐量等因素决定是否学习转发规则还是直接将流量发送到网关。当 vSwitch 需要学习转发规则时，它会构造 RSP 请求报文并发送给网关。网关随后解析请求报文，并收集特定的转发规则写入到回复数据包中。vSwitch 收到回复报文后，将相应的转发条目插入到转发缓存 (FC) 中。

周期性同步。

为了保证从网关学习到的 vSwitch FC 中已有表项的及时性，ALM 采用了周期性同步更新的策略。我们在 vSwitch 中创建了一个管理线程，每隔 50𝑚𝑠 遍历一次 FC 条目，用于检查每个条目的生命周期（上次更新与当前之间的间隔）是否超过某个阈值（例如 100𝑚𝑠）。如果生命周期超过阈值，vSwitch 会主动发送 RSP 请求 ④ 与网关进行数据核对。然后，vSwitch 根据网关 ⑤ 的 RSP 回复，在本地 FC 上执行相应的操作。

例如，如果网关上的条目发生更改或被删除，vSwitch 将更新相应的本地 FC 条目。如果数据核对显示本地 FC 中的 entry 是最新的，则 vSwitch 将不会对 FC 进行操作。

减少开销。

为了减少网络中 RSP 数据包的数量，提高 ALM 的效率，我们在 ALM 中采用批处理设计。在 vSwitch 中，我们允许将多个查询请求封装到单个 RSP 数据包中。相应地，网关也可以实现批量处理，将多个响应封装在一个回复包中。

我们在部署中验证了我们的设计，得到的结果是平均每个 RSP 请求数据包长度约为 200 字节，RSP 报文最大占用 < 4% 的带宽（§7.1）。这与它为虚拟网络带来的更强大的功能相比，这种开销是可以接受的（必要时我们可以通过 RSP 协议协商租户连接的 MTU、加解密参数和其他功能）。

5、网络容量弹性

在本节中，为了解决 Achelous 2.0 中的挑战二（§2.4），我们首先引入单 Host 内的纵向扩展（scale-up）方案，该方案在性能隔离的前提下提供弹性。然后，我们将在 Host 集群中展示我们的横向扩展（scale-out）方案。

5.1 Host 内的纵向扩展

问题与目标。

弹性带宽被广泛研究，然而，仅对带宽指标进行监控并不能满足弹性要求。例如，当虚拟机出现突发的短连接时，虽然该虚拟机的带宽没有达到上限，但是反而会消耗更多的 vSwitch 的 CPU 资源。同一主机上的其他虚拟机无法获得足够的 CPU 资源，从而导致带宽下降，主机内租户 CPU 资源隔离被破坏。因此，我们需要在同一主机内的虚拟机 CPU 资源隔离的基础上提供弹性。

弹性和隔离。

为了解决这个问题，我们提出了监控两个维度指标的策略。

第一个指标是虚拟机的 BPS/PPS，用 RB 表示，它直接限制了虚拟机的流量速率。第二个指标是 vSwitch 为 VM 传输流量所使用的 CPU cycle，用 RC 表示。

这两个指标为每个虚拟机的弹性和隔离性的提供了系统保证。

弹性策略。

如 Algorithm 1 所示，我们提出了一种弹性 credit 算法，用以实现带宽和 CPU 资源的高利用率。其核心思想是平衡 Host 内虚拟机的空闲 CPU 资源和突发流量之间的关系，使虚拟机可以利用主机的空闲 CPU 资源来处理短时的突发流量。

主机上所有虚拟机的总带宽资源（CPU 资源）用 𝑅B𝑇 (𝑅C𝑇) 表示。VM 的实际带宽资源（CPU 资源）使用率用 𝑅Bvm (𝑅Cvm) 表示。我们为每个虚拟机设置的默认资源限制用 𝑅Bbase (𝑅Cbase) 表示。此外，每个虚拟机都有自己的信用值 𝐶𝑟𝑒𝑑𝑖𝑡B (𝐶𝑟𝑒𝑑𝑖𝑡C)。

VM 可以消耗或累积其信用值。例如，如果 𝑅Bvm < 𝑅Bbase ，在空闲状态下，vSwitch 将给 VM 累积 𝐶𝑟𝑒𝑑𝑖𝑡B = 𝐶𝑟𝑒𝑑𝑖𝑡B + ( 𝑅Bbase - 𝑅Bvm）的信用值。

如果 𝑅Bvm > 𝑅Bbase ，在流量突发的情况下，vSwitch 将消耗 𝐶𝑟𝑒𝑑𝑖𝑡B = 𝐶𝑟𝑒𝑑𝑖𝑡B - ( 𝑅Bvm - 𝑅Bbase ) × 𝐶，其中 0 < 𝐶 ≤ 1 是 VM 的 credit 消耗率。

与令牌桶法的比较。

我们的信用算法优于的令牌桶算法。首先，信用消耗有特定的上限，这是信用算法与令牌桶的重要区别之一。其次，信用算法的通信开销低于令牌桶，因为它不需要在信用桶之间交换信息。此外，我们的方法可以抵御由于长时间大量资源占用而导致的 VM 隔离被破坏，例如 DDoS 攻击。

5.2 Host 横向扩展

问题。

单主机内的纵向扩展无法满足租户不断增长的服务扩展需求。因此，利用 ECMP 来横向扩展主机间的服务能力势在必行。然而，ECMP 部署中的引入的集中式网关将成为阻碍网络扩展的新瓶颈。为此，我们在每个 vSwitch 节点上设计了分布式 ECMP 机制，以提供无缝的横向扩展。

分布式 ECMP。

在此机制中，虚拟机可以创建 bonding vNIC 以实现 VPC 间的安全通信。如图 7 所示，Host1 上的租户 VM 创建了三个 bonding vNIC ，并将它们挂载到 service VPC 的 VM 中（如 “Middlebox” VPC 的 Host2、3 和 4 中的 VM 所示）。

所有 bonding vNIC 共享一个主 IP （图中的 “192.168.1.2” ）和相同的安全组。然后控制器将相应的 ECMP 路由条目发布到 Host1 上的 vSwitch 中。这确保租户虚拟机的数据包可以发送到 “Middlebox” VPC 中相应的虚拟机进行处理。

为了横向平滑扩容，如果 “Middlebox” VPC 中的虚拟机资源耗尽，则会自动创建额外的虚拟机并挂载到 bonding vNIC。随后，将会更新源 vSwitch 相应的 ECMP 条目，从而将流量重定向到新添加的虚拟机。值得注意的是，每个虚拟机都能够挂载来自不同 VPC 的多个 bonding vNIC。这使得 “Middlebox” VPC 中的虚拟机能够为来自不同 VPC 的大量虚拟机提供服务。

分布式 ECMP 机制通过确保每个源虚拟机都与一个 vSwitch 关联来消除潜在的瓶颈，从而有效地重新分配流量。这种方法显著的增强了大流量需求服务的弹性能力。例如，阿里云云防火墙可以通过在其 VPC 上暴露 bonding vNIC 接口，为数百万租户提供安全检测服务。借助分布式 ECMP 机制提供的水平可扩展性，租户可以无缝地从增加的资源中受益，无需主动管理或调整 Middlebox 的可用性。

相比负载平衡的好处。

尽管 LB 架构可以提供与分布式 ECMP 机制类似的功能，但它们通常需要更多的租户配置。例如，随着流量的增加，中心化的 LB 节点可能会成为性能瓶颈，需要进行横向扩展，这伴随着租户侧 proxy 配置的变化。此外，LB 架构不支持每个租户单独安全组。假设多个租户使用同一个 LB 节点，但每个租户都需要特定的安全组规则，唯一的选择就是在 LB 节点后面的 vSwitch 上手动配置这些安全组规则。相比之下，分布式 ECMP 机制通过统一配置 bonding vNIC，可以实现网络配置的无缝同步，从而更容易实现企业服务的横向扩展。

分布式 ECMP 中的故障转移。

为了防止租户 VPC 的大量遥测流量导致服务 VPC 中的虚拟机崩溃，我们利用集中式的管理节点在分布式 ECMP 中进行健康检查。如图 7 所示，管理节点定期遥测 “Middlebox” 虚拟机所在的 vSwitch。然后管理节点维护 VM 的全局状态并与源侧 vSwitch 进行同步。一旦 vSwitch 出现故障（例如 Host4 上的 vSwitch），管理节点会通知源侧 vSwitch 更新相应的 ECMP 表（即删除 ECMP 表中的 Host4 表项），以避免出现丢包。

6、网络风险感知与热迁移

在本节中，我们将解决 Achelous 数据平面的最后一个挑战（§2.4）。我们首先介绍网络风险感知方案。具体来说，我们探测主机内部和主机之间的网络链路状态，并向控制平面上送即将到来的网络风险的警报。然后，我们提出用于故障恢复的无缝热迁移方案。

6.1 网络风险感知

问题与目标。

由于物理网络探测不涉及虚拟网络，因此许多虚拟网络错误无法通过以前的物理遥测方法发现。然而，超大规模 VPC 中异常网络事件非常频繁并且不可避免。如果不能及时、适当地解决这些问题，可能会导致小故障升级为严重的网络拥塞或应用故障。为此，我们在 Achelous 上设计了链路健康检查模块，用于监控超大规模网络的状态，以主动感知故障并进行早期预警。

本模块重点关注两种类型的网络风险：

◼ 1）网络链路运行状况，包括 VM-vSwitch、vSwitch-vSwitch 和 vSwitch-gateway 链路；

◼ 2）虚拟网络设备状态信息，用于指示网络设备本身的运行状态。

下面将两者的设计细节进行介绍：

链接健康检查。

VM-vSwitch 健康检查和 vSwitch-vSwtich 健康检查分别是图 8 中的红色路径和蓝色路径。

VM-vSwitch 表示从 vSwitch 到主机中 VM 的链路。vSwitch 向虚拟机发送 ARP 请求，并获取虚拟机的 ARP 响应，以检查虚拟机的网络状态。

vSwitch-vSwitch 是从一个 Host 上的 vSwitch 到其他主机上的 vSwitch 的链路。监控控制器系统配置检查表（即IP地址）后，链路健康检查模块向检查表中的虚拟机发送健康检查报文。然后，链路运行状况监视器分析响应的延迟并向控制面报告潜在的风险（例如，虚拟机故障和链路拥塞）。

为了最大限度地减少健康检查数据包对数据面的侵入，我们将健康检查频率设置为 30𝑠 以减少额外的开销。同时，Achelous 以特定格式封装健康检查报文，仅将健康检查报文转发给链路健康监控器。

设备状态健康检查。

Achelous 除了检查链路的健康状态外，还检查虚拟网络设备的健康状态。

首先，Achelous 监视设备的 CPU 负载和内存使用情况。同时，Achelous 监控网络性能，例如虚拟和物理网卡的丢包率。如果网络设备存在风险（例如 CPU 负载高、NIC 掉线率高、内存耗尽等），我们会将这些异常情况报告给控制器。然后，控制器将介入并启动故障恢复机制。健康检查机制让网络具有风险感知的能力，能够改变潜在风险，主动干预风险。

6.2 虚拟机透明热迁移

问题与目标。

我们通过热迁移来执行故障恢复。然而，传统的热迁移机制没有考虑到有状态流量的连续性和租户无感。为了解决这个挑战，我们首先引入四个属性来保证虚拟机热迁移过程中的流量连续性。然后，我们将展示 Achelous 中为了满足这些特性热迁移方案的演变过程。

VM 热迁移的属性。

如表 1 所示，通过热迁移来进行故障恢复应满足以下属性：- 1）低停机时间：意味着热迁移过程中应实现流量的持续高吞吐量和毫秒级的停机时间。秒级宕机无法满足超大规模场景的需求；- 2）无状态流：我们应该快速重定向无状态流（例如 UDP 和 ICMP）；- 3）有状态流：意味着热迁移方案支持有状态流（例如 TCP 和 NAT），即流状态、会话信息甚至 ACL 安全组状态的自适应处理；- 4）应用无感知：是指热迁移方案要适应各种应用，原生应用不需要感知迁移过程。

VM 热迁移方案。

我们首先设计了一种流量重定向（TR）方案来转发无状态流量并满足低停机时间的要求。为了扩展 TR 方案以确保无状态流的连续性，我们提出了会话重置（SR）方案。然而，SR 方案需要修改 VM 中的客户端应用程序以响应热迁移期间的 TCP 重连接请求，这降低了厂商的服务的兼容性。

最后，我们在 Achelous 中开发会话同步 (SS)方案，它可以按需同步必要的会话，并在迁移过程中保持会话连接状态。SS 方案确保了本机应用程序无感知的情况下保证状态流的连续性。

我们在图 9 中展示了这些所有方案。由于篇幅限制，我们将这些方案的热迁移详细步骤，放到了附录 B。

我们的热迁移方案只有几毫秒的停机时间。因此，Achelous 数据面可以快速恢复无状态和有状态流，而无需感知本机客户端的应用服务。基于健康监控和故障预警，我们可以将虚拟机平滑的迁移到其他主机，避免可能发生的故障或快速从故障中进行恢复，极大提高了云网络的可靠性。

7、评估

在本节中，我们首先介绍 ALM 在实际部署性能评估。然后，我们将评估弹性信用算法的有效性和鲁棒性。最后，我们测量热迁移方案的停机时间和数据流的连续性。在我们的评估中，我们收集了阿里云中部署 Achelous 的五个典型 region 的数据。这些 region 的实例规模从数百到数千万个不等。

7.1 ALM 的有效性

编程时间。

图 10 展示了 Achelous 在不同规模 region 的编程时间。我们可以看到：

◼ 1）ALM 在我们的生产场景中收敛时间较短。例如，在含有 106 个虚拟机的 VPC 中，平均编程时间为 1.334 秒，而预编程网关模型为 28.5 秒，比 ALM 大了 21.36 倍；

◼ 2）ALM具有更好的可扩展性。随着虚拟机数量从 10 个增加到 106 个，预编程网关模型的平均编程时间从 2.61s 变为 28.50s，增加了 10.9 倍。然而，ALM 的平均编程时间从 1.03 秒增加到 1.33 秒，仅增加了 0.3 秒。这表明 Achelous 有能力支持更高数量级的网络规模。

ALM 流量和 FC 条目。

图 11 展示了 ALM 流量在不同 region 网络总流量中的占比（总流量从数百 Gbps 到数十 Tbps 的）。我们可以看到：- 1）ALM 流量占比非常低，不超过 4%，相较于其所带来的编程时间的降低来说是可以接受的；- 2）含有较小实例的 Region 相关路由规则也较少，因此 Region 越小，ALM 流量比例越低。

图 12 显示了典型 region 中 FC 表 entry 的 CDF（cumulative distribution function）统计。

内存开销：使用 ALM 时，每个 vSwitch 平均消耗 1,900 个缓存条目。拥有 150 万虚拟机 VPC 的 FC 存储峰值为 3,700 个，远小于 𝑂（N2）。我们可以发现 ALM 节省了 95% 以上的内存，并且几乎不需要额外的开销就解决了超大规模云网络路由表的存储问题。

7.2 网络弹性能力

弹性信用算法的效果。

为了验证弹性信用算法的效果，我们在同一台 Host 上设置了 VM1 和 VM2 的弹性网络实验，如图 13 和图 14 所示。我们将这两个 VM 中任意一个的 base 带宽限制为 1000 Mbps。

共分为三个阶段：

◼ 1）在前 30 秒内，我们使用另一台主机上的两个 VM 分别向 VM1 和 VM2 发送稳定的 300 Mbps 流量。VM1 与 VM2 的 CPU 使用率均为 20%；

◼ 2）之后，向 VM1 发送持续 30s 到 60s 的突发流。我们观察到 VM1 的带宽可以短暂达到 1500Mbps 左右。然后，VM1 消耗掉所有信用值，带宽并被限制到到 1000Mbps。VM1 的 CPU 使用率短时间内达到 55%，随后回落至 40%；

◼ 3）60秒后，我们向 VM2 发送小包（这将消耗更多的 CPU 资源），因此 VM2 的 CPU 利用率将达到 60%。VM2 带宽可以达到 1200Mbps，而基于 CPU 的弹性信用算法则可以将其带宽限制在 1000Mbps。

因此，我们观察到 vSwitch 总是严格保证 VM1 分配的 CPU 资源至少为 40%（在资源抢夺的情况下），因此可以保证 VM1 的带宽基本不变。在实践中，我们基于 BPS-Based + CPU-Based 的方法也可以通过消除资源竞争来保证时延，99%的流量延迟在 300𝜇s 以内。

自从我们部署此机制以来，如图 15 所示，遭受资源（CPU/带宽）抢夺的主机平均数量减少了 86%。综上所述，我们采用基于 BPS-Based + CPU-Based 的弹性信用算法方法，无论在简单还是复杂的 VPC 场景下都可以保证隔离性并具有较高的弹性性能。

分布式ECMP机制的有效性。

关于分布式 ECMP 机制，我们将其部署在所有生产 region 中。通过无缝横向扩展，我们实现了在 0.3 秒内网络服务即可完成扩展和收缩。

基于这些技术，我们已经实现阿里云 80% 的网络 middlebox（如 LB、NAT、VPN 网关等）以 NFV 的形式迁移到云上VM 。VM 的这些 middlebox 为数百万租户提供了高级网络服务。

7.3 健康检查和热迁移的有效性

健康检查发现的异常情况。

如 §6.1 所述，Achelous 可以检测出链路故障和设备故障。通过健康检查预警，Achelous 可以提前让租户意识到可能发生的故障。

表 2 说明 Achelous 能够检测出多类硬件故障（表 2 的第一部分）。其中，CPU 异常是最常见的故障类型，因为很多虚拟网络设备都是基于 CPU 进行转发（例如 vSwitch、网关）。

此外，Achelous 可以检测出资源争夺情况（表 2 的第二部分），这可能会导致 VM 的网络发生抖动或性能下降。Achelous 的健康检查机制可以进行扩展，未来我们可以添加更多监控指标，以快速发现其他类型的故障。

热迁移期间的停机时间。

我们测量 ICMP 和 TCP 流量的停机时间、热迁移和重新连接之间的时间间隔。

具体来说，我们首先顺序发送 ICMP 探测。通过统计热迁移过程中数据包的丢包量，来计算停机时间。其次，我们在虚拟机之间建立 TCP 连接，我们通过检查 TCP 序列号来得出停机时间。

图16 展示了 TR 方案和传统无重定向方案的停机时间。我们观察到 TR 可以大大减少热迁移过程中的停机时间，TR 的停机时间为 400ms，在 ICMP 和 TCP 场景下分别比传统方法快 22.5 倍和 32.5 倍。

会话重置和会话同步的有效性。

在图 17 中，如果应用程序具有自动重连功能（见绿线），它将在 32s（Linux 系统配置的默认值）内重启应用程序连接。

否则（见红线），在虚拟机热迁移过程中连接将会被丢失。相比之下，我们 TR + SR 仅引入 1 秒的停机时间。因此，我们的 TR + SR 可以成功减少应用程序重连之前的等待时间。

在目标虚拟机配置了 ACL 规则的场景中，该规则仅允许源虚拟机进入并拒绝任何其他虚拟机的流量。如图 18 所示，我们观察到由于热迁移后新的 vSwitch 中缺少 ACL 规则，TR + SR 下的连接将被阻塞，导致报文无法进行转发。

相比之下，我们的 TR + SS 方案使 vSwitch 能够进行会话同步，连接不会被阻止。该方案仅引入了约 100𝑚𝑠 的故障恢复延迟。我们的结论是，Achelous 热迁移方案不仅实用而且低延迟，同时保证有状态流的连续性。

8、经验

Achelous 已在我们的超大规模 VPC 中部署多年，提高了阿里云可服务性。即使面临网络规模不断扩大，突发流量和恶意攻击不断等生产挑战，它仍然为租户提供了良好的体验。除了论文中的设计之外，我们将在本节分享我们积累的云网络研发经验。

8.1 部署问题

Achelous 设计是否可以用于硬件卸载架构？

随着硬件卸载已经成为趋势，各大云厂商都通过部署 SmartNIC 或基于 CIPU 的 vSwitch 来提升 VM 的网络性能。然而事实是，FPGA 等非 CPU 硬件由于迭代效率问题，并且缺乏足够的灵活性，无法独立实现云中 vSwitch 的所有功能。所以对于 Achelous 来说，硬件扮演着加速缓存的角色（就像 §2.3 中提到的快速路径）。CIPU 的硬件卸载不会影响本文的协同设计，阿里巴巴近年来在硬件卸载加速方面的经验也证明了这些协同设计可以很好地服务于基于 SoC 的 vSwitch。

Achelous 可以在不基于阿里云的架构提供服务吗

Achelous 2.0 的主要致力于解决超大规模 VPC 所遇到的难题。这些设计都不是基于阿里云专用硬件平台或软件框架来实现。因此可以在任何硬件和软件平台上轻松实现。随着云计算市场的增长，其他中小型云供应商很快就会面临像我们一样规模的问题，他们将从我们的经验中受益。

8.2 得到教训

协同设计是云网络的趋势。

由于摩尔定律失效，单个模块的过度设计很难获得良好的效益。硬件卸载也并不意味着在复杂场景下能始终提供稳定的高性能。因此，不同网络组件之间的协同设计对于更高质量的虚拟网络来说是极其必要的。以 ALM 机制（§4.1）为例，在如此庞大且多变的网络中，如果没有网关、控制器和 vSwitch 的配合，就无法实现快速收敛。我们相信，在未来，协同设计将发挥更加关键的作用，并且超越通过简单堆叠硬件资源所能实现的性能目标。

除了性能之外，快速迭代和灵活性对于网络转发组件来说至关重要。

转发组件的迭代速度将直接决定我们能够以多快的速度支持租户的新需求并修复现有的问题。这些功能对于云基础设施的发展至关重要。在实现过程中，我们需要兼顾架构设计的灵活性和高性能。在 Achelous 中，经过几年的迭代，我们采用了服务逻辑与加速路径解耦的设计。这使得我们能够在同一套业务逻辑下实现软件、硬件等不同形式架构的加速。

9、相关工作

网络虚拟化一直是过去十年的研究热点。在数据面，最流行的开源项目 Open vSwitch 首先提出了快慢路径分离的设计理念。之后，又提出了一系列性能优化方法，例如用户态加速和硬件卸载。对于控制面，Google 提出了 B4，Azure 提出了 VFP，进一步丰富了 SDN 理论。随着云计算发展逐渐进入新的阶段，单方面的优化已经无法支撑日益增长的租户需求。因此，Achelous 提出了数据面和控制面的协同设计来支持 hyperscsale VPC 网络。我们将简要讨论与 Achelous 最相关的工作。

超大规模网络编程。

预编程模型是第一个用于 SDN 编程的模型。然而，它的编程开销随着 VPC 的大小呈平方增加，这对于超大型集群来说是不能接受的。Andromeda 和 Zeta 结合了网关模型和按需模型的优点，使用中心化节点来执行卸载策略，它们选择的流粒度将使网关成为潜在的被重击者，而且也比 Achelous 更加繁重。

弹性。

关于网络带宽分配策略已经有许多深入研究的著作，然而，传统的带宽分配策略忽略了虚拟网络中多种资源的消耗。Picnic 的作者提到有必要为租户分配网络专属 CPU 资源，但其缺乏统一的系统管理。Achelous 对不同资源采用统一的资源分配算法，既保证了隔离性又适应了网络突发状况。另一方面，我们注意到目前还没有关于如何在虚拟网络中部署 ECMP 路由的论文。因此，我们提出分布式 ECMP 机制来克服集中式部署带来的性能瓶颈，并为租户提供轻松横向扩展的能力。

可靠性。

对于故障遥测，目前已经有很多论文致力于物理网络中的故障遥测，但由于它们大多数不能直接在虚拟网络中进行使用。因此，我们在 Achelous 中开发了一种虚拟网络遥测方法，以在租户感知之前感知故障并进行故障转移。对于热迁移，大多数现有工作都集中在主机资源迁移，例如裸金属云上的内存脏页或 SR-IOV 网络设备。khai 等人提出了一种通过多步迁移来减少停机时间并确保迁移过程中的流量连续性的方案，但其无法解决有状态流的连续性。在Achelous 中，采用基于 “TR + SS” 机制的热迁移来保证租户有状态服务的不中断。

10、结论

随着云计算需求的不断增长，云供应商需要在单个 VPC 中托管数百万个实例。因此网络配置的快速收敛、高弹性、高可靠性变得极具挑战性。为此，我们提出了 Achelous，它为阿里云中的超大规模 VPC 已经提供了多年的高可服务性。

在 Achelous 中，我们详细展示了它通过 ALM 机制、弹性网络容量策略、分布式 ECMP 机制和网络故障避免方案来实现超大规模 VPC。与数据面上现有的经过充分研究的设计相比，Achelous 开辟了一些关于如何确保云网络可服务性的研究方向，我们认为这是云供应商成功的关键指标。Achelous 不依赖任何定制硬件，因此其他中小型云供应商可以从我们的设计和本文介绍的部署经验中受益。

（正文完）

Reference：

◼ Achelous：Enabling Programmability, Elasticity, and Reliability in Hyperscale Cloud Networks

文章来源公众号：Flowlet

【ICNP 2021】基于弱监督学习的ISP自助BGP异常检测

Wed, 10 May 2023 11:36:38 +0800

背景

边界网关协议 (BGP) 缺乏路由认证和验证，这使得互联网更容易受到恶意用户和错误配置的影响，例如前缀劫持、路由泄漏、中断和路由劫持等异常。这些攻击或异常可能会造成重大的经济损失、潜在的用户隐私泄露以及大规模网络不可避免的中断，影响着成千上万的用户和组织。

例如，2020 年 8 月 31 日，CenturyLink 错误配置 BGP 导致全球互联网流量下降 3.5%，这是历史上最大的互联网中断之一。事实上，在互联网上发现了越来越多的 BGP 异常和漏洞。因此，提供一种有效的方案来识别这些异常事件是非常重要的。

然而当下大多数 ISP 依赖第三方异常检测系统来检查他们的网络是否受到攻击，因为还没有一个通用的方法可以处理所有异常情况。而依赖第三方会导致一些问题。首先，一旦本地网络配置发生变化，他们需要及时更新第三方异常检测系统。其次，异常检测系统是为一些特定的异常设计的，不能有效地处理其他异常，所以没有一个系统可以检测到所有的异常。因此，ISP 必须与多个第三方异常检测系统达成协议，以检测所有异常。这使得ISP 无法做出足够快的反应来检测异常并避免大规模的 BGP 振荡。

因此，我们旨在为 AS 设计一个自营的异常检测系统，以识别所有 BGP 异常，并且无需其他 AS 的合作。

BGP常见异常分类

BGP 在其设计中不考虑自治系统的身份验证。它假设每个自治系统发布的公告都是可信可靠的，并且可以被对等体转发。这种设计导致了一系列BGP异常，使得网络容易出现路由泄露、劫持等异常情况。此外，劫持可以分为前缀劫持和路由劫持。基于图 1 所示的合法路由，我们在以下小节中提供定义和示例。

图1. 合法路线。每个AS公布的路径都是可信可靠的

A. 前缀劫持

前缀劫持可以分为两大类：常规前缀劫持和子前缀劫持。

常规前缀劫持：如图2所示,劫持者在网络层可达信息（NLRI）中伪造目标AS1的前缀。在这种情况下，从AS3和AS4到AS1的数据将被AS5重新路由和窃取。

子前缀劫持： 如图3所示，劫持者不仅在NLRI公告中伪造前缀，而且使用目标AS的更长的子前缀，导致数据都被重新路由到劫持者AS5。

常规前缀劫持一般按照就近原则吸引劫持者附近的流量。此外，由于最长匹配原则，子前缀劫持通常会劫持更多流量。

图2. 常规前缀劫持。AS1 合法拥有 192.1.0.0/20 地址块。劫持者 AS5 非法通告地址为 192.1.0.0/20 的路由。则根据BGP最短路径原则，AS3&AS4到192.1.0.0/20的数据将被重定向到AS5

图3.子前缀劫持。AS5 声明了比 AS1 更长的前缀。根据最长匹配原则，所有数据流向劫持者AS5。

B. 路由泄露

路由泄漏是最常见的 BGP 异常事件之一。它可能会导致多种类型的问题，从经济损失到网络中断。路由泄漏的定义是AS将一个Provider或Peer的路由传播到另一个Provider或Peer。根据路由策略优先级，提供商可能会选择客户的路由而不是对等方或提供商的路由，因此网络的路由将发生巨大变化。

C. 路由劫持

在这种攻击场景中，劫持者只需要向目标AS通告一个虚假的 AS-PATH。假设假路径比从被感染AS到目标AS的路径短。根据AS-PATH最短路径优先原则，这将导致中间人 (MITM) 攻击。这种攻击更难检测，因为它避免了检测多源前缀冲突 (MOAS)。根据路径的真实性，路由劫持可以分为假路由（图4）和Defcon攻击（图5）。Defcon 攻击与假路由相比具有真实路径，但其伪造子前缀以实现 MITM 攻击。因此Defcon 检测起来更具挑战性，因为路径是可达的。

图4.虚假路由攻击。劫机者伪造了一条较短的路由 5,1，从而劫持了 AS4 的流量。

图5. Defcon 攻击。劫机者伪造更具体的前缀，以便它可以用于 MITM 攻击。

挑战

1)BGP异常事件由于复杂的商业考量，难以收集和验证，不准确的监督学习是必然的。因此，第一个挑战是构建一个规模可观的综合弱异常数据集。

2）给定的标签并不总是经过验证的基本事实，并且类别不平衡。因此，第二个挑战是从可能不准确和不平衡的数据中训练有效的异常检测模型。

模型框架

如图6所示，我们提出了一个基于弱监督学习的自适应通用框架。这分为以下模块：知识收集模块、特征提取模块和自适应异常检测模块。所有模块都可以在ISP中自行操作。

图6.流程图

第一个模块旨在提取知识。它从众所周知的异常检测系统如BGPStream和BGPObservatory中获取事件信息，然后从RIPE RIS数据库中获取原始BGP UPDATE消息。第二个模块是特征提取模块，从原始BGP UPDATE消息中提取特征。最后一个模块是自适应异常检测模块，它使用基于自注意力机制的LSTM模型。自注意力机制用于从全局探索异常事件时间序列的内部关系。此外，LSTM的隐藏层自适应地为特征分配权重，从而支持特征的选择。这些模块在以下小节中阐述。

A.知识采集模块

知识收集模块通过访问众所周知的异常检测系统来收集异常事件。在给定的标签并不总是基于基本事实的情况下，它可能是不准确的数据。然而，数据遵循中心极限定理，这在第六节中得到了证明。此外，我们定制的弱监督学习模型可以学习异常之间的不同分布。每个异常事件都包含如下表一中对应的信息。需要注意的是，并非所有事件都具有这两个属性：事件结束时间和劫持者AS。例如，当发生前缀劫持时，异常可能会持续很长时间，因此不会有结束时间属性。在大多数情况下，没有针对突围事件的特定劫机者 AS。

然后，根据异常事件列表，我们使用pybgpstream的python API从控制平台RIPE RIS获取原始BGP UPDATE数据包。本模块完成后，我们将原始BGP UPDATE 数据包作为流量输入到下一个模块。

B.特征提取模块

在本模块中，我们从原始 BGP 流量数据中提取特征。我们将 BGP 流量数据定义为以1分钟为时间间隔的时间序列特征。Sn=（x1,x2,x3,…,xn)。其中每个时间点x又由多个特征f组成，xt=(f1,f2,f3,…,fm)。同时我们采用滑动时间窗口来捕捉时间维度的变化，其大小定义为 w。

其中特征集如表二所示，我们将特征分为四类：前缀特征、Peer特征、AS-volume特征和AS-PATH特征。我们将在以下小节中讨论这些。

前缀特征：特征 f1-4 表征前缀劫持事件。f4 还可以识别 MITM 攻击。

Peer特征：特征 f5-7 与对等点的数量有关。f5 和 f7 描述了目标 AS 通知范围，f6 反映了 MITM 攻击。

AS Volume特征：特征 f8-13 是Volume类型特征。为了进一步区分路由工程和劫持，我们将公告分为MOAS公告和其他普通公告。

AS-PATH特征：我们可以通过测量给定时间段内的AS-PATH长度来估计目标AS更新的范围。AS-PATH 特性主要用于描述路由变化。我们使用编辑距离算法来估计路径差异。以及使用路径增加和减少来进一步区分路由工程和劫持。

C.自适应异常检测模块

图7.自适应异常检测模型。

我们设计了自适应 LSTM 的功能，将每个时间戳提取的信息传递到下一个时间戳，并在最后一个时间戳识别异常。在 LSTM 模型中，Cell状态贯穿整个滑动时间窗口。同时，通过逻辑门，新的输入 xt 被选择性地添加到单元状态，并选择性地去除过去的信息。基于这些方法，我们可以从整个时间窗口中捕获长期信息。此外，LSTM 的神经网络层可以自适应地计算每个特征的重要性。而自注意力机制生成一系列权重，然后使用这些权重与输入参数相乘。然后它使用损失的反向传播来实现输入参数的重新分配。self-attention 的优点是从全局的角度观察每个时间戳信息的重要性，然后对输入进行重新加权输出。

数据集

弱数据集收集：我们使用最著名的 BGP 异常检测系统（例如，BGPStream和BGPObservatory）作为异常事件的教师模型。此外，我们使用MANRS倡议的AS作为正常事件的教师模型，因为这些AS部署了RPKI并且可以相对信任。其中各异常检测系统的检测范围及收集的各事件数量如表三所示。对于弱数据集的训练和测试，每个异常事件获取异常数据集异常前后20分钟。同时，我们从MANRS获取20个具有代表性的AS作为正常数据的提供者，对其中每个AS收集1440分钟的数据作为正常数据。

Ground truth 数据集集合：为了解释不准确数据对模型的影响，我们使用公开异常数据集来测试我们训练的模型。该数据集包含四个众所周知的 BGP 事件，如表 IV 所示。其中包括来自土耳其电信 (TTnet)、Indosat（印度尼西亚）、马来西亚电信 (TM)以及对亚马逊网络服务 (AWS)的攻击的数据。其中每个案例包含1440个数据，并根据异常的持续时间标记数据。

数据预处理

丢弃重复事件和低覆盖率事件：由于教师异常检测系统可能会报告一段时间内的重复事件，这可能会隐藏真实的事件开始时间。因此，我们以 15 分钟的间隔删除重复事件，只保留第一个事件。此外，我们的 BGP 数据是从 RIPE RIS 收集器收集的，可能存在一些覆盖率较差的区域。因此，我们在整个收集期间丢弃 f7 总和小于 5 的事件。

数据集去噪：为了防止特征在初始化期间发生剧烈变化，我们使用前 100 分钟作为初始化阶段。然后我们从训练数据中丢弃它。

动态步幅采样方法：为了解决类不平衡问题，我们设计了一种采样方法，在训练阶段对正常数据和异常数据使用不同的步幅大小。基于下面的公式3和4，我们可以得到数据集的大小。

其中 Di 表示事件 i 提供的数据大小， Ei 表示事件 i 的时间（以分钟为单位）。Wc 代表每个类别的滑动窗口大小，sc 定义每个类别的步幅。Nc 代表每个类别的事件数，Tc 定义每个类别的总数据大小。

数据预处理分析：为了便于特征分布的分析，我们将异常前后15分钟的特征总和作为单个样本，即每个异常总共30分钟。对于正常事件，我们使用 30 分钟的滑动窗口来生成正常事件集。

数据分析

在本节中，我们展示弱数据集中不同特征对于各类异常的可区分性。结果表明，不同的异常类别确实是可分离的，并且数据集满足中心极限定理。

图 8. 基于前缀特征集将前缀劫持事件与正常事件进行比较。从左到右，f1-3 显着区分前缀劫持事件和正常事件，而 f4 用于表征路由劫持（例如，Defcon）。请注意，Y 轴使用的是对数刻度。

图 9. 基于AS Volume特征比较中断事件与正常事件。从左到右，基于 f9−13 的突破异常比普通事件高 1000 倍。f8 用于表征前缀劫持。请注意，Y 轴基于对数刻度。

图 10. 路径特征的重尾分布，其中每个重尾比例小于各自路径特征总和的 1%。此外，与正常事件相比，异常都表现出异常行为。

如图10，基于我们对AS-PATH特征集的重尾分布观察，我们将AS-PATH特征集划分为如表5所示，并在总特征量减少一半的同时，增强了特征集的信息量，由于重尾部分往往是异常，将其进行求和有助于异常的识别。

实验

A.超参数选择

根据我们的超参数选择，我们在后续的实验中采用128 hidden size大小，以及30分钟的滑动时间窗口。

图11.超参数选择

B.Self Attention的可解释性分析

通过可视化每个异常类别的自注意力权重，我们可以发现注意力模型基于不同类型的异常有不同的侧重点。如图 12 所示，对于前缀劫持，权重随着时间序列的增加而增加，这比对所有时间戳使用相同权重的传统模型更合理。相比之下，路由泄漏检测模型更关注历史信息，因为路由策略的变化更难被检测到。此外，大规模事件（例如，突破）会导致大量消息无法访问，这会对网络产生巨大影响。因此，注意力模型需要更多地关注最近时间戳的特征。但是，对于典型的路径劫持（例如，假路由和Defcon），与前缀劫持和突破不同，路径劫持由于影响范围较小而难以检测。因此，模型也需要更多地关注过去的信息。

图 12. 每个事件的注意力权重。

C. 不同模型和特征集的比较

相关框架仅使用我们的部分特征（例如，前缀特征、Peer Feature + AS Volume类型或仅使用 AS Volume）来识别异常，因此我们将它们组合起来并将它们设置为基线特征（BL）。

在这个实验中，我们成功地从异常检测系统中提取了知识，并通过我们的框架实现了更好的性能。此外，我们的模型具有比任何检测系统都更全面的异常检测能力，并且可以在目标 AS 中自我操作。

D.在公开数据集上的测试

为了更好地表明在弱数据集上训练的模型具有更好的泛化性能，我们使用一个众所周知的异常事件集来测试训练后的模型。

即时检测：如图13所示，我们用不同的异常模型可视化事件的识别。我们的实验表明，可以立即识别异常。我们还发现，异常发生后，网络中的重路由会持续一段时间。

不同异常类别的关系：对于TTNet（AS9121）和IndoSat（AS4761）事件，我们可以观察到可以准确识别出路由泄漏引起的中断。我们还可以发现，该路由在中断后会立即重新路由，并带有大量新的路由路径，我们的模型将其识别为路由劫持。此外，对于TM（AS 4788）和AWS（AS 200759），虽然发生了路由泄漏，但并没有导致网络中断，说明这两个网络对异常的鲁棒性更强。通过这样的分析，我们发现了当大量异常事件发生时异常类别之间的关系。同时，这突出了我们的方法在其他数据集上的推广。

图13.基于已知异常的异常检测

E.迁移学习

为了获得更好的性能，我们结合了现有的Ground truth数据集。我们使用从弱数据集学习的模型作为预训练的基础模型，并将我们的模型转移到众所周知的异常中。我们将预训练的模型转移到异常数据的小样本中进行微调，其中最后一层和骨干网络具有不同的学习率。此外，我们使用这些模型作为集成模型来检测异常。因此，该模型可以通过设置投票阈值来适应不同规模的 AS。

我们的基线模型是最先进的 BGP 检测模型 MLGF。MLGF 将图特征与 SVM 结合使用。图特征来源于AS拓扑，包括node centrality, clique theory, clusteringcoefficient and eccentricity。

如表7，我们采用交叉验证的方式将数据集划分为4部分。如表 VIII 所示，我们的方法在 RC 和 F1 指标方面都有显着改进。具体来说，我们的模型在 PR 仅降低 1.34% 的情况下提高了 20% 的召回率。同样值得注意的是，高召回率非常重要，因为当异常被忽略时，这可能会导致无法弥补的经济损失或安全问题企业/国家。此外，我们的集成模型具有良好的泛化性能，可以作为预警系统转移到各种AS。具体来说，当出现异常情况时，可以根据报警置信度的强弱采取不同的措施。例如，在强置信度告警的情况下，可以直接阻止异常BGP更新的传播。对于低置信度警报，我们可以实施 Route Flap Dampening 或限制更新速率或使用人工/专家审查。

结果表明，我们的弱数据集解决了BGP数据不足的问题，可以带来更多的先验知识。此外，预训练的模型也可以转移到其他地面实况数据集以实现更好的性能。

总结

越来越多的BGP异常不断涌现，同时数据标记高成本和网络动态性导致：无论是有监督学习还是无监督学习都无法实现稳定高效的BGP异常检测。因此，在本工作中，我们提出一种弱监督学习框架来处理BGP异常检测。首选，方案从第三方系统中提取BGP知识；然后，使用弱数据集来训练一个可以处理数据噪声的自注意力LSTM模型；同时，将预先训练的模型转移到目标AS数据集以进行进一步的微调。据我们所知，这是第一个使用弱监督进行BGP异常检测的工作，框架的部署不依赖于其他AS，可以避免在第三方异常检测系统上进行繁琐的更新操作。实验中证明，在众多BGP异常事件下，检测框架同时实现了高精度和低开销。

参考文献： Y. Dong, Q. Li, R.Sinnott, Y. Jiang, and S. Xia, “ISP Self-Operated BGP Anomaly Detection Based on Weakly Supervised Learning,” in 2021 IEEE 29th International Conference on Network Protocols (ICNP). IEEE, 2021, pp. 1–11.

【ICNP 2021】怒赞！上海交大团队先于谷歌提出光电混合数据中心慢切换方案

Wed, 10 May 2023 10:40:20 +0800

SIGCOMM 2022 谷歌的 Jupiter evolving 横空出世，让世界的目光再次投向光电混合数据中心。事实上，早在2021年，上海交大赵世振团队发表于ICNP的论文 (TROD: Evolving From Electrical Data Center to Optical Data Center) 首次提出“慢切换”控制方案（一作为该团队博士生曹培睿），大幅降低了光电混合数据中心的控制难度，并避免了对快速光交换硬件的依赖。同时，该论文提出的阈值分流路由方案在最大程度上增加了光电混合数据中心面对突发流量的抗性。谷歌的Jupiter evolving论文指出其光电混合数据中心也采用了慢切换方案，并引用了TROD。笔者将从Motivation，Design，Evaluation 和 Conclusion 四个方面简单介绍一下他们的工作TROD。

Motivation: 快速光切换是唯一出路吗？

光交换机（OCS）具有超低功耗，超大带宽的特性，但因其端口一对一连通，想支持多对多连接需要不断做重配置切换状态（耗时数十毫秒），在十多年前被提出后，一直未被广泛部署于实际数据中心。前人设计的光电混合网络对光交换硬件的切换时延和网络控制器的收敛速度要求极高，难以真正落地。以微软为代表的快切换流派，虽然能将光切换时延缩小到了纳秒级，但依然局限在小型testbed，没能真正量产。在硬件方面，能够商业量产的光交换器件切换时延高、灵活性差。而在软件方面，光电混合数据中心的控制方案还比较不成熟，包括拓扑、路由算法等。为了降低光电混合数据中心的落地难度，TROD提出不依赖快速光切换技术，使用商用OCS结合慢切换控制+阈值分流方案，也能对抗流量突发，保证性能。该整体方案能够大幅降低光电混合数据中心的控制、部署和运维难度，从而降低整个数据中心的成本和功耗。（谷歌2022年在大规模实际数据中心进一步验证了慢切换方案的可行性。）

Design: 慢切换如何应对突发？

物理架构方面，前人的Helios在Clos核心层使用一部分光交换机（OCS）来分担大流而让时延敏感流继续走电交换机（EPS），该方案需要维持双平面控制且难以应对流量突发，导致网络运维人员工作量增加。不同于Helios，如图2所示，TROD将传统Clos架构的核心层电交换机全部替换为了光交换机（OCS），有效降低成本和功耗，但需要去解决流量突发的问题，TROD在慢切换控制中提出阈值分流方案，有效解决了该问题。

TROD分析了一些真实数据中心的历史流量发现，PoD间流量在长期往复相似的范围内波动。TROD利用这种相似性，提出慢切换控制，优化拓扑使其能覆盖这些范围内大部分流量模式。当PoD间的突发流量超出这些范围，TROD就利用中转PoD绕路缓解一部分突发；同时为了不加重网络负担，TROD提出阈值分流路由方案来巧妙地解决流量突发且不增加网络负担，其核心思想是只让超过阈值的流量分到非最短路径。TROD阈值分流方案已经在ofsoftswitch13软件仿真以及现实P4交换机中实现（详见该团队发表于ToN的拓展版论文 Threshold-based Routing-Topology Co-design for Optical Data Center）。另外，笔者认为TROD的阈值分流方案还有一大好处是能够在汇聚层电交换机上分离式地实现，算法和部署难度显著降低；而谷歌路由方案需要依赖集中式控制，其算法难度有所增加。

Evaluation

流完成时间（FCT），特别是流尾部完成时间对用户体验至关重要，因此除了成本和功耗外，TROD做了丰富的实验来评估流尾部完成时间。测试的数据集包含了数据中心常见流量模式，以及突发流量模式。各自对比在TROD论文中有详细讨论，总结来说，TROD对比谷歌最新的Jupiter方案有1.15-2.16倍性能提升；对比其他现有光电混合数据中心，有至少2倍的性能提升；对比expander数据中心，有2.4-3.2倍的性能提升。另外，由于更换了核心层电交换机可以降低成本并且降低跳数，TROD还评估了在OCS层通过α超额配置是否可能使光电混合数据中心网络实现比non-blocking Clos更好的性能。惊喜的是，TROD的仿真结果表明，当α达到1.2时，TROD开始表现出超越non-blocking Clos的性能。相比之下，其他光电混合数据中心方案无论α值为何都无法击败non-blocking Clos，或者需要很大的α值。

Conclusion: 光电混合网络后续如何演进？

TROD提出的慢切换控制以及阈值分流路由方案较为科学地在PoD间解决了流量突发问题，并大幅降低光电混合数据中心的控制、部署和运维难度，从而降低整个数据中心的成本和功耗。

同时TROD还提出了光电混合数据中心可能的演进路径如图8所示。笔者关注到，该团队也确实在沿着他们提出的演进路径做更深入的研究。在2022年发表于SIGMETRICS的论文（Understanding the Performance Guarantee of Physical Topology Design for Optical Circuit Switched Data Centers）中，针对如何在光电混合数据中心搭建初期进行容量规划，以及如何设计ToR电交换机与光交换之间的物理拓扑等问题，他们首次提出“竞争比”概念，能够在不知道数据中心流量模式的前提下严格分析光电混合数据中心物理拓扑的性能。2023年，该团队发表于NSDI的论文（Flattened Clos: Designing High-performance Deadlock-free Expander Data Center Networks Using Graph Contraction）运用虚拟up-down路由解决了光电混合网络中使用RDMA产生的死锁问题。有兴趣的读者可进一步跟进。

参考文献：Peirui Cao, Shizhen Zhao, Min Yee Teh, Yunzhuo Liu, Xinbing Wang, “TROD: Evolving From Electrical Data Center to Optical Data Center”, in ICNP, Dallas, Texas, USA Virtual Event, November, 2021.

【中科院】为什么chiplet需要标准？

Fri, 24 Feb 2023 22:17:44 +0800

近日，清华大学姚期智院士代表中国Chiplet产业联盟，联合国内外IP厂商、国内领先封装厂商、国内领先系统与应用厂商共同发布了《芯粒互联接口标准》- Advanced Cost-driven Chiplet Interface（ACC），该标准由交叉信息核心技术研究院牵头，中国Chiplet产业联盟共同起草。目前该标准涉及相关的团体标准、行业标准在申请中。

那到底什么是芯粒互联以组成chiplet？为什么 chiplet 需要标准？中国科学院计算技术研究所互连技术实验室早在2021年就在一篇文章中进行了详细的阐述。

1 chip-let 概念介绍

从 5nm 工艺节点开始，集成电路先进制程的演进可能停滞，而继续提升制程，由于面临隧道效应，从工艺上面临较大的困难，有一种说法是先进制程演变到 1nm，可能需要 100 年，这种说法虽然有点夸张，但可以理解摩尔定律再也不会像以前那样实现每 18 个月提升一倍晶体管密度的步伐，这给需要通过先进制程的演变不断提升性能的芯片设计带来比较大的问题。

工业界已经围绕这个问题，开始寻找解决方案，一种可行的解决办法是采用 chip-let（小芯片）的架构设计芯片。Chip-let 是一种把传统的单芯片设计方案改成多芯片进行设计，并利用先进封装工艺进行集成的设计方法。由于在传统的芯片设计中，本来就存在多个功能单元，以及某些功能单元如计算部分存在模块化的设计以方便多次复用以降低设计成本，因此在基于 chip-let 架构设计的芯片中，主要是把多个功能单元分别用单独的芯片设计实现或者把模块化多次复制的单元用多个单独的芯片进行设计，最终通过先进的封装工艺实现集成。这种设计方案主要有以下好处：

提升芯片制造良率。由于良率和芯片的面积有关系，越大可能越低，因此当把一个大的芯片分拆成多个小芯片设计并分别投片，就可以提高良率，从而可能降低芯片的制造成本。

以不同的工艺实现一颗芯片，在利用先进制程的同时降低整体的实现代价。由于数字电路往往可以从先进制程的演进中得到好处，然而模拟电路往往性能随着先进制程的演进性能提升并不大，因此如果将芯片中负责计算的部分（通常是数字电路）和负责 I/O 的部分（通常以模拟电路为主）分开各自以不同的工艺实现，则在充分利用了先进制程的工艺的同时，又降低了整体的实现成本，因为采用老的工艺实现 I/O 模块更为经济。

实现产品的设计灵活性，一个产品架构可以应用于不同的应用场景。这一点，在 AMD 的产品设计中被展现的淋漓尽致，AMD 从 Zen(AMD CPU 的架构代码)第一代设计即采用了 chip-let 的方式，这种方式使 AMD 可以在 PC 和服务器之间共享同一个 CPU 芯片架构，PC 和服务器 CPU 产品的区别只是不同的核数，或者可能采用不同的 I/O die（封装前的裸芯片），这种架构极大的降低了其设计成本，成为 AMD 成功的重要因素之一。

本文将从 chip-let 的设计场景入手，对 chip-let 设计过程中需要的一些技术组件进行介绍，针对为什么 chip-let 架构的芯片设计过程中需要标准以及其可能发挥的作用进行分析，得出在我国制订 chip-let 标准的必要性。

2 基于 chip-let 架构芯片的应用场景介绍

从目前微电子芯片发展的情况看，越来越多的芯片设计场景需要使用 chip-let 架构进行设计，这主要体现在需要先进制程以进一步提升 PPA（power，performance，area）的芯片设计场景，如消费电子产品中的 CPU、服务器 CPU/AI 加速芯片、网络中交换机（switch）/ 路由器（router）芯片等，由于先进制程的演进受阻，这些芯片设计场景转而选择 chip-let 架构设计芯片，以维持摩尔定律的发展。

消费电子产品中基于 chip-let 架构的 CPU 芯片案例以 intel 公司于 19年发布的 lakefield 为典型。Intel 在 lakefield CPU 中使用了三维（3D logic）的方式，这是一种典型的 chip-let 方式的芯片，不过基于 intel 的私有技术 foveros 开发；lakefield 由 3 层 die 组成，顶层为片上内存 die，中间一层为计算 die，包括了 1 个大核 Sunny cove，4 个小核 Tremont，还包括了 GPU，IPU（信号处理）等计算的核心，最下面一层为 base die，主要是各种协议的 IO 功能，如 USB，PCIe 等。

数据中心服务器产品中基于 chip-let 架构的 CPU 芯片案例以 AMD 的 ZEN 系列为主，从 ZEN 第一代开始，AMD 即采用了基于 chip-let 的架构设计芯片，ZEN-1 架构的服务器产品 naples 为 4 个同样结构的 die（均含有计算的核和 DDR 内存以及 I/O 功能，I/O 功能主要包括 PCIe，以太网，CPU 片间互连等）通过 IFOP（Infinity Fabric on Package，一种片内互连物理层技术）互连技术相连，ZEN-2 架构的服务器产品 roma 为 8 个计算核心的 die 通过升级版的 IFOP 互连技术和一个 I/O die（将 DDR 和 I/O 功能独立出来）互连，ZEN-3 的架构基本和 ZEN-2 相同。与消费电子产品的 CPU 不同的是，服务器 CPU 中很少有 GPU 和 IPU 等功能。

值得注意的是，在高端芯片上被广泛应用的 HBM（High Bandwidth Memory）本身即是一种 chip-let 技术，HBM 本质上是 DRAM 芯片通过 TSV（Through Silicon Via）连接并堆叠在一起，目前一般为 2/4 层，然后通过一个 logic die，经由基板（interposer）和计算 die 如 GPU 或者 AI 芯片完成互连；在大多数应用 HBM 的场景如各种 AI 芯片中，HBM 被用来提供高带宽的内存解决方案，以 chip-let 的方式通过先进封装和 GPU 或其他类型的 AI 芯片集成在一起。

数据中心 switch/router 产品中的 chip-let 案例以 intel 收购的 barefoot 为典型。Barefoot 的 tofino-2 芯片，采用了 chip-let 的方式设计芯片，整个芯片有一个主 die 和 4 个 serdes tile（die）通过基于并行单端信号的接口相连，主 die 主要由多个网络报文处理流水线和 MAC （实现以太网协议中的链路层功能）组成，由于 switch ASIC 的吞吐量越来越大，而 serdes 在整个 switch 芯片中占的面积约来越大，因此将 serdes 部分用 chip-let 方式分离单独设计和投片，可以提升整体良率，简化整个芯片的设计，并且让芯片架构更加灵活化。值得注意的是 switch/router 中的计算核心功能是分组报文处理流水线及链路层 MAC 功能，这点和服务器 CPU 又有所不同。

3 在我国设计基于 Chip-let 架构的芯片需要标准的支持

由上可见，这么多应用场景都会用到 chip-let 的方式设计芯片，似乎看起来 chip-let 芯片的设计不太可能有一种标准支持。然而，事实上，在多种 chip-let 场景中，真正用于多个 die 之间互连的总线接口只有 3 种方式，一种基于大量单端信号，另外一种是基于差分信号，还有一种是介于两者之间，信号为单端，时钟信号则采用了差分方式传递。这个原因是因为 chip-let 架构中多个 chip-let 之间通常在物理层互连，主要用于在 die 和 die 之间架设物理数据通道，而在物理层实现互连则主要考虑电气性能如何达到、数据速率的匹配（并串转换等），一般不会涉及到协议层面的通信，而协议通常和应用场景有关系，一个可以用作对比的例子是，chip-let 之间的关系有点像在整个网络中的二层交换机和三层路由器的作用，交换机和路由器通常只负责在 OSI 协议的第二层和第三层进行连接和交互（转发），不会涉及到应用层的会话，而第二层和第三层的协议种类则相对要少的多，类似交换机和路由器在整个 OSI 协议中的功能，多 die 之间的互连通信协议种类不会太多，因此存在制订标准的可行性空间。

然而，基于 chip-let 架构进行芯片设计到目前为止，国际上尚无公认标准，由于该技术的门槛较高，如果自己全部完成设计，需要芯片厂商从芯片整体的架构设计、到其中并行或者串行物理层接口、甚至先进封装能力全部具备，目前唯一具备这些能力的厂商是 intel 公司，intel 公司提出了一种叫 AIB（Advanced Interface Bus）的 chip-let 物理层协议，并借用自有的先进封装技术 EMIB（Embedded Multi-Die Interconnect Bridge），可以实现 chip-let 方式的芯片设计，美国 Ayar lab 即采用了 AIB 协议实现其设计的 Optic I/O die 与 Intel FPGA 连接，实现芯片级光 I/O 功能；而 AMD 公司的 ZEN-3 采用台积电的 CoWos（Chip-onWafer-on-Substrate） 2.5D 先进封装技术，ZEN-4 则可能采用台积电的 SOIC 3D 先进封装技术。

在我国，目前具备这种整体能力的芯片厂商极少，大多数芯片厂商还是依赖芯片 IP 厂商提供并行物理层或者串行物理层 IP，台积电提供先进封装能力（如 CoWos 等封装技术），因此首先需要形成完整的、面向 chip-let 架构设计芯片的社会分工，但在这方面目前我国的情况还不太理想，如目前只有 2-3 家 IP 厂商可以为系统芯片厂商提供高速串行物理层 IP，而串行物理层 IP 在某些场景如 C2C（计算 die-计算 die 互连）存在延时较大的弊端，至于高带宽密度的并行物理层 IP 则能够提供的厂商更少，在基于并行物理层设计 chip-let 架构的芯片时，由于在极其狭小空间中高速信号的数目太多，因此信号完整性问题引起的挑战更大；另外一方面，基于 chip-let 架构的芯片强烈依赖于先进封装技术，但我国在先进封装技术方面如高密度的基板/interposer 设计、大尺寸的基板材料、小尺寸 bump 方面都还比较薄弱，因此短期看，设计 chip-let 架构的芯片可能还是需要依赖国外厂商的先进封装技术，但从长远发展看有必要提前展开相应的研究工作，面向 chip-let 应用场景，研究和开发高性能的串行/并行物理层技术以及相应的先进封装技术。

在形成围绕 chip-let 设计的广泛设计分工基础之上，形成 chip-let 标准则更加重要，由于我国绝大多数芯片厂商并不能自行完成基于 chip-let 架构的芯片设计和制造闭环，在形成广泛的设计分工之后，就必须有一个标准，以规定设计分工中的各种部件如各种不同的功能 die 的规格和各种接口通信约束条件，在每一个设计链条节点上推动形成多家技术供应商，形成良性竞争，把整个市场做大，使 SOC 系统厂商有充分的选择空间，避免形成商业垄断，最终阻碍 chip-let 技术和生态的发展壮大。

在有了 chip-let 的标准以后，还需要进行充分的技术验证，相比传统的单芯片设计，基于 chip-let 架构设计的芯片，由多个不同功能的 die、或者不同工艺的 die 组成，因此必须经过实际的验证，才能最终通过先进封装实现互连，因此 chip-let 标准的制订必须要延伸到实现各种各样的参考设计，并且要保证所有的参考设计都完成验证，才能为标准的制订画上句号，因此 chip-let 标准的制订十分挑战，需要大量的技术工作，时间周期也比较长。

综上所述，在我国，制订、形成一个 chip-let 的标准，推动芯片设计厂商和各种 IP 厂商围绕标准开发和设计 chip-let 架构的芯片，有一定的必要性和意义。

4、CCITA 的 chip-let 标准工作进展

综上所述，鉴于 chip-let 芯片设计概念的飞速发展，以及我国芯片设计行业所涌现出的需求，结合先进制程演进放缓的现实情况，制订一个我国需要的 chip-let 标准逐渐变得非常必要；中国计算机互连技术联盟（CCITA）目前已经围绕 chip-let 展开了标准制订工作，主要工作集中在物理电气层、PCS 物理编码层，并对 chip-let 所需要的先进封装概念，进行了探索，力图找到一种或者几种成本低廉、重点针对 chip-let 芯片架构、可以覆盖 80%以上应用场景的先进封装手段，并能够基于国内的封装技术基础实现，以推动 chip-let 全产业链条的自主化；在此基础上，CCITA 的 chip-let 标准也会支持 CoWos 等先进封装技术。

目前 CCITA 的 chip-let 标准已经经过提案阶段，正在进行标准草案制订工作，预计将于 2021 年底发布标准草案，并于 2022 年年中进行技术验证，2022 年底正式完成标准制定工作。

参考资料：

一文读懂Dragonfly拓扑

Fri, 24 Feb 2023 22:00:31 +0800

Dragonfly是由John Kim等人在2008年的论文Technology-Driven, Highly-Scalable Dragonfly Topology中提出，它的特点是网络直径小、成本较低，对于高性能计算有着非常大的优势。现在已经被运用在使用Cray XC系列网络的各种超算中。

拓扑结构

一个简单的dragonfly网络如下图所示。

Dragonfly的拓扑结构分为三层：Switch层，Group层，System层[也叫路由器(Router)、组(Group)、系统(system)层）]。

◼ Switch层：包括一个交换机，及其相连的 p 个计算节点

◼ Group层：包含 a 个Switch层，这 a 个Switch层的 a 个交换机是全连接(All-to-all)的，换言之，每个交换机都有 a-1 条链路连接分别连接到其他的 a-1 台交换机

◼ System层：包含 g 个Group层，这 g 个Group层也是全连接的

对于单个switch交换机，它有p个端口连接到了计算节点，a-1个端口连接到Group内其他交换机，h个端口连接到其他Group的交换机

因此，我们可以计算得到网络中的如下属性

◼ 每个交换机的端口数为 k=p+(a-1)+h

◼ Group的数量为 g=ah+1

◼ 网络中一共有 N=ap(ah+1) 个计算节点

◼ 如果我们把一个Group内的交换机都合成一个，将它们视为一个交换机，那么这个交换机的端口数为 k‘=a(p+h)

在一个较小规模的网络中， g=ah+1 个group可能会较多，可以将任意两个Group之间的连接数由一条增加为多条，这样任意两个Group之间就有 floor((ah+1)/g) 条链路连接。

不难发现，在确定了 p，a，h，g 四个参数之后我们就可以确定一个dragonfly的拓扑，因此一个Dragonfly的拓扑可以用 dfly(p,a,h,g) 来表示

一种推荐的较为平衡的配置是方法是：a=2p=2h

路由算法

Dragonfly的路由算法主要有两类，最小路由算法（Minimal Routing，最短路径的路由）与由Valiant提出的可以在系统层面上应用的非最短路径的路由算法（Non-Minimal Routing，非最短路径的路由）。此外作者在论文中还提出了UGAL(Universal Globally-Adaptive Load-balanced，全局自适应负载均衡路由)算法。具体来讲：

◼ Minimal Routing：最短路径的路由，简写为MIN。由于拓扑的性质，Minimal Routing中最多只会有1条Global Link和2条Local Link，也就是说最多3跳即可到达。在任由两个Group之间只有一条直连连接时（即g=ah+1时），最短路只有一条。

◼ Non-Minimal Routing：非最短路径的路由，可以简写为Non-Min，来自论文A scheme for fast parallel communication。有的地方叫Valiant algorithm，简写为VAL，还有的地方叫Valiant Load-balanced routing，简写为VLB。随机选择一个Group，先发到这个Group然后再发到目的地。由于拓扑的性质，VAL最多会经过2条Global Link和3条Local Link，最多5跳即可到达。

◼ Universal Globally-Adaptive Load-balanced(UGAL)：全局自适应负载均衡路由，来自论文Load-Balanced Routing in Interconnection Networks。当一个数据包到达交换机时，交换机根据最短路径路由MIN 和非最短路径的路由VAL 的路径上所有交换机队列的排队长度的和，来选择路由。

因为要获取到全局网络状态信息太难了，所以提出了一系列变种，在Dragonfly中有如下若干种实现方式：

◼ UGAL-G：只根据发送节点所在的Group的所有交换机的队列排队长度来进行判断。但是要实现这个依然很难，也是一个非常理想的情况。

◼ UGAL-L：只根据本地交换机的队列排队长度来进行判断，这种方式会产生一个问题：当在源Group中进行路由时，如果最短路径和非最短路径都要经过源Group中另一个交换机时，此时这两条路径的出口队列一致，因此总是会选择最短路径。

◼ UGAL-LVC：针对UGAL-L的问题进行了一点改进：将最短路径和非最短路径分为两个VC，分别排队来计算长度。但是这样又会导致数据包更偏向选择非最短路由，导致在均匀流量模式下性能不好。

◼ UGAL-LVC_H：针对UGAL-LVC的问题又进行了一点改进：只有在MIN和VAL的输出端口不一样的时候，才用VC的队列长度来进行判断，否则还是直接使用队列长度来判断。

◼ UGAL-LCR：由于只用本地信息来判断拥塞，在buffer越大时反而造成的延迟越大，因为buffer被填满了之后，上游的交换机才能通过没有credit了感知到。为了克服这个问题，可以通过当前拥塞情况主动增加credit的返回延迟，上游交换机认为返回credit越快的交换机拥塞程度越小。

死锁避免

在Dragonfly中，形成环路的概率要高很多。因此，如果使用最短路由，需要2个VC来避免死锁；如果使用非最短路由，需要3个VC来避免死锁。

参考资料：

1、http://ngdcn.com/post/208.html

2、https://www.cnblogs.com/Nreyab/p/15590684.html

3、http://blog.sysu.tech

Alibaba高性能通信库ACCL介绍

Tue, 21 Feb 2023 11:30:22 +0800

ACCL（Alibaba Collective Communication Library）是一款高性能通信库，提供了AllReduce、 AllToAllV、Broadcast等常用集合操作接口以及点到点Send/Recv接口，为多机多卡训练提供高效的通信支持。

背景信息

ACCL面向阿里云灵骏架构设计，通过算法与拓扑的深入协同来收获更好的通信性能，充分挖掘高性能RoCE网络的带宽效率、最大化分布式训练系统的可扩展性。

ACCL提供了简单易用的C++ API，语义与MPI等主流集合操作接口相近。ACCL提供了对PyTorch、Horovod 等深度学习框架以及数据并行、模型并行等主流并行训练模式的支持，便于深度学习用户快速使用。

ACCL的关键特性包括：

◼ 异构拓扑感知，例如节点内PCIE与NVLink/NVSwitch、节点间多轨RDMA网络，分层混合算法设计，充分利用不同互连的带宽。

◼ 端网协同选路，算法与拓扑协同设计实现无拥塞通信，支撑训练性能上规模可扩展。

◼ 端侧RoCE LAG感知、在网多流负载均衡，多任务并发、资源争抢时保障整体吞吐。

参考资料：如何安装ACCL库_智能计算灵骏-阿里云帮助中心

【微软】MSCCL Github仓库介绍

Mon, 20 Feb 2023 08:04:18 +0800

MSCCL

Microsoft Collective Communication Library (MSCCL) 是一个为 Microsoft Azure 支持的多个加速器执行自定义集合通信算法的平台。

介绍

MSCCL 是一个建立在NCCL之上的加速器间通信框架，并使用其构建块来执行自定义编写的集合通信算法。MSCCL 的愿景是提供一个统一、高效和可扩展的框架，用于跨多个加速器执行集合通信算法。为实现这一目标，MSCCL 具有多种功能：

◼ 可编程性：加速器之间的互连具有不同的延迟和带宽。因此，通用的集合通信算法不一定适用于所有拓扑和缓冲区大小。MSCCL 允许用户为给定的拓扑结构和缓冲区大小编写超优化的集合通信算法。这可以通过两个主要组件实现：MSCCL toolkit和MSCCL runtime（此 repo）。MSCCL toolkit包含一个高级 DSL (MSCCLang) 和一个为 MSCCL 运行时（此 repo）生成 IR 以在后端运行的编译器。MSCCL 将始终在没有自定义算法的情况下，MSCCL 将自动回退到 NCCL 的通用算法。例子提供了有关 MSCCL toolkit与运行时如何工作的一些实例。有关更多信息，请参阅MSCCL toolkit.

◼ Profiling/分析：MSCCL 有一个分析工具NPKit，它为每个原始发送和接收操作提供详细的时间线，以了解给定集合通信算法中的瓶颈。

MSCCL 是微软研究院许多优秀研究人员和实习生的成果。以下是我们的出版物列表：

◼ GC3：用于 GPU 集合通信的优化编译器– ASPLOS’23

◼ 综合最优集合算法——PPoPP’21（最佳论文奖）

◼ 打破分布式机器学习工作负载中的计算和通信抽象障碍——ASPLOS’22

◼ TACCL：使用通信草图指导集合算法综合– NSDI’23

如果您在研究中使用 MSCCL，请考虑引用我们的工作。此外，如果您有任何疑问或需要针对特定拓扑优化的集合通信算法，请联系我们。

例子

为了使用 MSCCL 自定义算法，您可以按照以下步骤在具有 8xA100 GPU 的 Azure NDv4 上为 AllReduce 使用两种不同的 MSCCL 算法：

安装 MSCCL 的步骤：

$ git clone https://github.com/microsoft/msccl.git
$ cd msccl/
$ make -j src.build
$ cd ../

然后，按照以下步骤安装nccl-tests进行性能评估：

$ git clone https://github.com/nvidia/nccl-tests.git
$ cd nccl-tests/
$ make MPI=1 NCCL_HOME=../msccl/build/ -j 
$ cd ../

接下来安装MSCCL toolkit来编译一些自定义算法：

$ git clone https://github.com/microsoft/msccl-tools.git
$ cd msccl-tools/
$ pip install .
$ cd ../
$ python msccl-tools/examples/mscclang/allreduce_a100_allpairs.py --protocol=LL 8 2 > test.xml
$ cd ../

编译器生成的代码是一个 XML 文件 ( test.xml)，它被提供给 MSCCL 运行时。要评估其性能，请在 Azure NDv4 节点或任何 8xA100 系统上执行以下命令行：

$ mpirun -np 8 -x LD_LIBRARY_PATH=msccl/build/lib/:$LD_LIBRARY_PATH -x NCCL_DEBUG=INFO -x NCCL_DEBUG_SUBSYS=INIT,ENV -x MSCCL_XML_FILES=test.xml -x NCCL_ALGO=MSCCL,RING,TREE  nccl-tests/build/all_reduce_perf -b 128 -e 32MB -f 2 -g 1 -c 1 -n 100 -w 100 -G 100 -z 0

如果一切安装正确，您应该在日志中看到以下输出：

[0] NCCL INFO Connected 1 MSCCL algorithms

test.xml``MSCCL_XML_FILES在命令行中传递给运行时。test.xml您可以通过比较in-place（新算法）与out-of-place（默认环算法）来评估性能，在 8xA100 NVLink 互连 GPU 上它应该快 2-3 倍。MSCCL toolkit具有一组丰富的算法，适用于不同的 Azure SKU 和集合操作，与普通 NCCL 相比具有显着的加速。

Build

要构建库：

$ cd msccl
$ make -j src.build

如果 CUDA 未安装在默认的 /usr/local/cuda 路径中，您可以使用以下命令定义 CUDA 路径：

$ make src.build CUDA_HOME=<path to cuda install>

build/除非BUILDDIR设置，否则MSCCL 将被编译和安装。

默认情况下，为所有支持的体系结构编译 MSCCL。为了加速编译并减少二进制文件的大小，可以考虑重新定义NVCC_GENCODE（defined in makefiles/common.mk）以仅包含目标平台的架构：

$ make -j src.build NVCC_GENCODE="-gencode=arch=compute_80,code=sm_80"

安装

要在系统上安装 MSCCL，请创建一个包，然后以 root 身份安装它。

Debian/Ubuntu：

$ # Install tools to create debian packages
$ sudo apt install build-essential devscripts debhelper fakeroot
$ # Build NCCL deb package
$ make pkg.debian.build
$ ls build/pkg/deb/

RedHat/CentOS：

$ # Install tools to create rpm packages
$ sudo yum install rpm-build rpmdevtools
$ # Build NCCL rpm package
$ make pkg.redhat.build
$ ls build/pkg/rpm/

与操作系统无关的压缩包：

$ make pkg.txz.build
$ ls build/pkg/txz/

PyTorch 集成

要与 PyTorch 集成，请遵循此存储库中的 dockerfile。它有一个如何用 MSCCL 替换默认 NCCL 的示例。

NPKit 集成

MSCCL 集成了NPKit，这是一个分析器框架，可以在 MSCCL 组件中收集细粒度的跟踪事件，从而识别传输瓶颈。

要启用 NPKit，只需添加NPKIT=1您的 make 命令。在执行期间，环境变量NPKIT_DUMP_DIR将用于生成所有输出（每个等级一个输出文件）。默认情况下，/tmp/将被使用。

要分析 NPKit 输出，请运行 python 脚本tools/npkit_trace_generator.py以获取最终.json文件，该文件可以通过 Microsoft Edgeedge://tracing或 Google Chrome等跟踪查看器查看chrome://tracing。

参考资料：https://github.com/microsoft/msccl

【英伟达】NCCL Github仓库介绍

Sat, 18 Feb 2023 20:58:38 +0800

NCCL

优化了 GPU 间通信的原语。

介绍

NCCL（发音为“Nickel”）是一个独立的 GPU 标准通信例程库，实现全归约、全聚集、归约、广播、归约分散以及任何基于发送/接收的通信模式。它经过优化，可在使用 PCIe、NVLink、NVswitch 的平台以及使用 InfiniBand Verbs 或 TCP/IP 套接字的网络上实现高带宽。NCCL 支持在单个节点或跨多个节点安装任意数量的 GPU，并且可用于单进程或多进程（例如 MPI）应用程序。

有关 NCCL 使用的更多信息，请参阅NCCL 文档。

Build

注意：NCCL 的官方和测试版本可以从以下网址下载： https: //developer.nvidia.com/nccl。如果您选择使用官方Build，则可以跳过以下Build步骤。

Build库：

$ cd nccl
$ make -j src.build

如果 CUDA 未安装在默认的 /usr/local/cuda 路径中，您可以使用以下命令定义 CUDA 路径：

$ make src.build CUDA_HOME=<path to cuda install>

build/除非BUILDDIR设置，否则将编译和安装 NCCL 。

默认情况下，NCCL 是为所有支持的体系结构编译的。为了加速编译并减少二进制文件的大小，可以考虑重新定义NVCC_GENCODE（defined in makefiles/common.mk）以仅包含目标平台的架构：

$ make -j src.build NVCC_GENCODE="-gencode=arch=compute_70,code=sm_70"

安装

要在系统上安装 NCCL，请创建一个包，然后以 root 身份安装它。

Debian/Ubuntu：

$ # Install tools to create debian packages
$ sudo apt install build-essential devscripts debhelper fakeroot
$ # Build NCCL deb package
$ make pkg.debian.build
$ ls build/pkg/deb/

RedHat/CentOS：

$ # Install tools to create rpm packages
$ sudo yum install rpm-build rpmdevtools
$ # Build NCCL rpm package
$ make pkg.redhat.build
$ ls build/pkg/rpm/

与操作系统无关的压缩包：

$ make pkg.txz.build
$ ls build/pkg/txz/

测试

NCCL 的测试在https://github.com/nvidia/nccl-tests上单独维护。

$ git clone https://github.com/NVIDIA/nccl-tests.git
$ cd nccl-tests
$ make
$ ./build/all_reduce_perf -b 8 -e 256M -f 2 -g <ngpus>

参考资料：https://github.com/nvidia/nccl

【MPI】MPI组和通讯器介绍

Fri, 30 Dec 2022 20:06:32 +0800

在以前的教程中，我们使用了通讯器 MPI_COMM_WORLD。对于简单的程序，这已经足够了，因为我们的进程数量相对较少，并且通常要么一次要与其中之一对话，要么一次要与所有对话。当程序规模开始变大时，这变得不那么实用了，我们可能只想一次与几个进程进行对话。在本次教程中，我们将展示如何创建新的通讯器，以便一次与原始线程组的子集进行沟通。

通讯器概述

正如我们在学习集体例程时所看到的那样，MPI 允许您立即与通讯器中的所有进程进行对话，以执行诸如使用 MPI_Scatter 将数据从一个进程分发到多个进程或使用 MPI_Reduce 执行数据归约的操作。但是，到目前为止，我们仅使用了默认的通讯器 MPI_COMM_WORLD。

对于简单的应用程序，使用 MPI_COMM_WORLD 进行所有操作并不罕见，但是对于更复杂的用例，拥有更多的通讯器可能会有所帮助。例如，如果您想对网格中进程的子集执行计算。例如，每一行中的所有进程都可能希望对一个值求和。这将是第一个也是最常见的用于创建新的通讯器的函数：

MPI_Comm_split(
    MPI_Comm comm,
    int color,
    int key,
    MPI_Comm* newcomm)

顾名思义，MPI_Comm_split 通过基于输入值 color 和 key 将通讯器“拆分”为一组子通讯器来创建新的通讯器。在这里需要注意的是，原始的通讯器并没有消失，但是在每个进程中都会创建一个新的通讯器。第一个参数 comm 是通讯器，它将用作新通讯器的基础。这可能是 MPI_COMM_WORLD，但也可能是其他任何通讯器。第二个参数 color 确定每个进程将属于哪个新的通讯器。为 color 传递相同值的所有进程都分配给同一通讯器。如果 color 为 MPI_UNDEFINED，则该进程将不包含在任何新的通讯器中。第三个参数 key 确定每个新通讯器中的顺序（秩）。传递 key 最小值的进程将为 0，下一个最小值将为 1，依此类推。如果存在平局，则在原始通讯器中秩较低的进程将是第一位。最后一个参数 newcomm 是 MPI 如何将新的通讯器返回给用户。

使用多个通讯器的示例

现在，让我们看一个简单的示例，在该示例中，我们尝试将单个全局通讯器拆分为一组较小的通讯器。在此示例中，我们将想象我们已经在逻辑上将原始通讯器布局为共 16 个进程的 4x4 网格，并且希望按行划分网格。为此，每一行将获得自己的颜色（参数 color）。在下图中，您可以看到左图具有相同颜色的每组进程如何最终变成右图的自己的通讯器。

让我们看一下代码。

// 获取原始通讯器的秩和大小
int world_rank, world_size;
MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
MPI_Comm_size(MPI_COMM_WORLD, &world_size);

int color = world_rank / 4; // 根据行确定颜色

// 根据颜色拆分通讯器，然后调用
// 利用原始秩
MPI_Comm row_comm;
MPI_Comm_split(MPI_COMM_WORLD, color, world_rank, &row_comm);

int row_rank, row_size;
MPI_Comm_rank(row_comm, &row_rank);
MPI_Comm_size(row_comm, &row_size);

printf("WORLD RANK/SIZE: %d/%d \t ROW RANK/SIZE: %d/%d\n",
    world_rank, world_size, row_rank, row_size);

MPI_Comm_free(&row_comm);

前几行获得原始通讯器 MPI_COMM_WORLD 的秩和大小。下一行执行确定局部进程 color 的重要操作。请记住，color 决定了拆分后该进程所属的通讯器。接下来，我们将看到所有重要的拆分操作。这里的新事物是，我们使用原始秩（world_rank）作为拆分操作的 key。由于我们希望新通讯器中的所有进程与原始通讯器中的所有进程处于相同的顺序，因此在这里使用原始等级值最有意义，因为它已经正确地排序了。之后，我们将打印出新的等级和大小以确保其有效。您的输出应如下所示：

WORLD RANK/SIZE: 0/16      ROW RANK/SIZE: 0/4
WORLD RANK/SIZE: 1/16      ROW RANK/SIZE: 1/4
WORLD RANK/SIZE: 2/16      ROW RANK/SIZE: 2/4
WORLD RANK/SIZE: 3/16      ROW RANK/SIZE: 3/4
WORLD RANK/SIZE: 4/16      ROW RANK/SIZE: 0/4
WORLD RANK/SIZE: 5/16      ROW RANK/SIZE: 1/4
WORLD RANK/SIZE: 6/16      ROW RANK/SIZE: 2/4
WORLD RANK/SIZE: 7/16      ROW RANK/SIZE: 3/4
WORLD RANK/SIZE: 8/16      ROW RANK/SIZE: 0/4
WORLD RANK/SIZE: 9/16      ROW RANK/SIZE: 1/4
WORLD RANK/SIZE: 10/16      ROW RANK/SIZE: 2/4
WORLD RANK/SIZE: 11/16      ROW RANK/SIZE: 3/4
WORLD RANK/SIZE: 12/16      ROW RANK/SIZE: 0/4
WORLD RANK/SIZE: 13/16      ROW RANK/SIZE: 1/4
WORLD RANK/SIZE: 14/16      ROW RANK/SIZE: 2/4
WORLD RANK/SIZE: 15/16      ROW RANK/SIZE: 3/4

如果您的顺序不正确，请不要惊慌。当您在 MPI 程序中显示内容时，每个进程都必须将其输出发回启动 MPI 作业的位置，然后才能将其打印到屏幕上。这往往意味着排序变得混乱，因为您永远无法假设仅以特定的秩顺序打印内容，即输出结果实际上将按照您期望的顺序结束，但是显示不是。只是在这里重新排列输出内容，以至看起来不错。

最后，我们使用 MPI_Comm_free 释放通讯器。这似乎不是一个重要的步骤，但与在其他任何程序中使用完内存后释放内存一样重要。当不再使用 MPI 对象时，应将其释放，以便以后重用。 MPI 一次可以创建的对象数量有限，如果 MPI 用完了可分配对象，则不释放对象可能会导致运行时错误。

其他通讯器创建函数

尽管 MPI_Comm_split 是最常见的通讯器创建函数，但还有许多其他函数。 MPI_Comm_dup 是最基本的，它创建了一个通讯器的副本。似乎存在一个仅创建副本的函数似乎很奇怪，但这对于使用库执行特殊函数的应用（例如数学库）非常有用。在这类应用中，重要的是用户代码和库代码不要互相干扰。为了避免这种情况，每个应用程序应该做的第一件事是创建 MPI_COMM_WORLD 的副本，这将避免其他使用 MPI_COMM_WORLD 的库的问题。库本身也应该复制 MPI_COMM_WORLD 以避免相同的问题。

另一个功能是 MPI_Comm_create。乍一看，此功能与 MPI_Comm_create_group 非常相似。其原型几乎相同：

MPI_Comm_create(
    MPI_Comm comm,
    MPI_Group group,
    MPI_Comm* newcomm)

然而，主要区别（除了缺少 tag 参数之外）是，MPI_Comm_create_group 仅是 group 中包含的一组进程的集合，而 MPI_Comm_create 是 comm 中每个进程的集合。当通讯器的规模很大时，这是一个重要的区别。如果尝试在运行 1,000,000 个进程时创建 MPI_COMM_WORLD 的子集，则重要的是使用尽可能少的进程来执行该操作，因为大型集的开销会变得非常昂贵。

通讯器还有其他一些更高级的功能，我们在这里不介绍，例如内部通讯器与内部通讯器之间的差异以及其他高级通讯器创建功能。这些仅用于非常特殊的应用，以后的教程中可能会介绍这些应用程序。

组的概述

尽管 MPI_Comm_split 是创建新通讯器的最简单的方法，但并非唯一的方法。创建通讯器有更灵活的方法，但是它们使用一种新的 MPI 对象 MPI_Group。在详细讨论组之前，让我们再回顾一下通讯器的实际含义。在内部，MPI 必须（除其他事项外）保持通讯器的两个主要部分，即区分一个通讯器与另一个通讯器的上下文（或 ID）以及该通讯器包含的一组进程。 The context is what prevents an operation on one communicator from matching with a similar operation on another communicator. 上下文阻止了与一个通讯器上的操作匹配的另一通讯器上的类似操作。 MPI 在内部为每个通讯器保留一个 ID，以防止混淆。组更易于理解，因为它只是通讯器中所有进程的集合。对于 MPI_COMM_WORLD，这是由 mpiexec 启动的所有进程。对于其他通讯器，组将有所不同。在上面的示例代码中，组是所有以相同的 color 传参给 MPI_Comm_split 的进程。

MPI 使用通常起作用集合理论的相同方式来使用这些组。您不必熟悉所有的集合理论即可理解 MPI，但是了解两个操作的含义会有所帮助。首先，并会从其他两个集合中创建一个新的（可能）更大的集合。新集合包括前两个集合的所有成员（无重复）。其次，交会从其他两个集合中创建一个新的（可能）更小的集合。新集合包括两个原始集合中都存在的所有成员。您可以在下面以图形方式查看这两个操作的示例。随后，我们将使用适用于 MPI 的术语“组”（groups），而非“集合“（sets）。

在第一个示例中，两个组 {0,1,2,3} 和 {2,3,4,5} 的并集是 {0,1,2,3,4,5}，因为这些项中的每一个都出现在组中。在第二个示例中，两个组 {0,1,2,3} 和 {2,3,4,5} 的交集为 {2,3}，因为每个组中同时仅出现那些项。

Using MPI groups

现在，我们了解了组工作原理的基础，让我们看看如何将其应用于 MPI 操作。在 MPI 中，很容易通过 API 调用 MPI_Comm_group 来获取通讯器中的进程组。

MPI_Comm_group(
    MPI_Comm comm,
    MPI_Group* group)

如上所述，通讯器包含一个上下文或 ID，以及一个组。调用 MPI_Comm_group 会得到对该组对象的引用。组对象的工作方式与通讯器对象相同，不同之处在于您不能使用它与其他秩进行通信（因为它没有附加上下文）。您仍然可以获取组的秩和大小（分别为 MPI_Group_rank 和 MPI_Group_size）。但是，组特有的功能而通讯器无法完成的工作是可以使用组在本地构建新的组。在此记住本地操作和远程操作之间的区别很重要。远程操作涉及与其他秩的通信，而本地操作则没有。创建新的通讯器是一项远程操作，因为所有进程都需要决定相同的上下文和组，而在本地创建组是因为它不用于通信，因此每个进程不需要具有相同的上下文。您可以随意操作一个组，而无需执行任何通信。

一旦有一个或两个组，对它们执行操作就很简单。并看起来像这样：

MPI_Group_union(
    MPI_Group group1,
    MPI_Group group2,
    MPI_Group* newgroup)

您可能会猜到交看起来像这样：

MPI_Group_intersection(
    MPI_Group group1,
    MPI_Group group2,
    MPI_Group* newgroup)

在这两种情况下，操作均在 group1 和 group2 上执行，结果存储在 newgroup 中。

MPI 中有许多关于组的用法。您可以比较组以查看它们是否相同，从另一个组中减去一个组，从组中排除特定秩，或使用一个组将一个组的秩转换为另一组。但是，MPI 中可能是最有用的一个函数是 MPI_Comm_create_group。这是一个用于创建新通讯器的函数，但无需像 MPI_Comm_split 之类那样需要进行计算以决定组成，该函数将使用一个 MPI_Group 对象并创建一个与组具有相同进程的新通讯器。

MPI_Comm_create_group(
    MPI_Comm comm,
    MPI_Group group,
    int tag,
    MPI_Comm* newcomm)

Example of using groups

让我们看一下使用组的简单示例。在这里，我们将使用另一个函数，该函数允许您选择组中的特定秩并构建为新组，即 MPI_Group_incl。

MPI_Group_incl(
    MPI_Group group,
    int n,
    const int ranks[],
    MPI_Group* newgroup)

该函数中，newgroup 将包含 group 中的秩存在于 ranks 数组中的 n 个进程。想看看它是如何工作的？让我们尝试创建一个包含来自 MPI_COMM_WORLD 的主要秩的通讯器。

// 获取原始通讯器的等级和大小
int world_rank, world_size;
MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
MPI_Comm_size(MPI_COMM_WORLD, &world_size);

// 获取 MPI_COMM_WORLD 中的进程组
MPI_Group world_group;
MPI_Comm_group(MPI_COMM_WORLD, &world_group);

int n = 7;
const int ranks[7] = {1, 2, 3, 5, 7, 11, 13};

// 构造一个包含 world_group 中所有主要秩的组
MPI_Group prime_group;
MPI_Group_incl(world_group, 7, ranks, &prime_group);

// 根据组创建一个新的通讯器
MPI_Comm prime_comm;
MPI_Comm_create_group(MPI_COMM_WORLD, prime_group, 0, &prime_comm);

int prime_rank = -1, prime_size = -1;
// 如果此秩不在新的通讯器中，则为
// MPI_COMM_NULL。使用 MPI_COMM_NULL 作为 MPI_Comm_rank 或
// MPI_Comm_size 的错误
if (MPI_COMM_NULL != prime_comm) {
    MPI_Comm_rank(prime_comm, &prime_rank);
    MPI_Comm_size(prime_comm, &prime_size);
}

printf("WORLD RANK/SIZE: %d/%d \t PRIME RANK/SIZE: %d/%d\n",
    world_rank, world_size, prime_rank, prime_size);

MPI_Group_free(&world_group);
MPI_Group_free(&prime_group);
MPI_Comm_free(&prime_comm);

在此示例中，我们通过仅选择 MPI_COMM_WORLD 中的主要秩来构建通讯器。这是通过 MPI_Group_incl 完成的，并将结果存储在 prime_group 中。接下来，我们将该组传递给 MPI_Comm_create_group 以创建 prime_comm。 At the end, we have to be careful to not use prime_comm on processes which don’t have it, therefore we check to ensure that the communicator is not MPI_COMM_NULL, which is returned from MPI_Comm_create_group on the ranks not included in ranks. 最后，我们必须小心不要在没有 prime_comm 的进程上使用 prime_comm，因此我们要检查以确保通讯器不是 MPI_COMM_NULL 状态 —— 不在 ranks 中而从 MPI_Comm_create_group 返回的结果。

欢迎扫码关注微信公众号“网络技术风云汇”，更快速接收更多网络技术咨询。

【MPI】MPI Reduce和Allreduce函数

Fri, 30 Dec 2022 20:06:14 +0800

在上一节中，我们介绍了一个使用MPI_Scatter和MPI_Gather的计算并行排名的示例。在本课中，我们将通过MPI_Reduce和MPI_Allreduce进一步扩展集体通信例程。

归约简介

归约是函数式编程中的经典概念。数据归约包括通过函数将一组数字归约为较小的一组数字。例如，假设我们有一个数字列表 [1,2,3,4,5]。用 sum 函数归约此数字列表将产生 sum([1、2、3、4、5]) = 15。类似地，乘法归约将产生 multiply([1、2、3、4、5]) = 120。

就像您想象的那样，在一组分布式数字上应用归约函数可能非常麻烦。随之而来的是，难以有效地实现非可交换的归约，即必须以设定顺序发生的缩减。幸运的是，MPI 有一个方便的函数，MPI_Reduce，它将处理程序员在并行程序中需要执行的几乎所有常见的归约操作。

MPI_Reduce

与 MPI_Gather 类似，MPI_Reduce 在每个进程上获取一个输入元素数组，并将输出元素数组返回给根进程。输出元素包含减少的结果。 MPI_Reduce 的原型如下所示：

MPI_Reduce(
    void* send_data,
    void* recv_data,
    int count,
    MPI_Datatype datatype,
    MPI_Op op,
    int root,
    MPI_Comm communicator)

send_data 参数是每个进程都希望归约的 datatype 类型元素的数组。 recv_data 仅与具有 root 秩的进程相关。 recv_data 数组包含归约的结果，大小为sizeof（datatype）* count。 op 参数是您希望应用于数据的操作。 MPI 包含一组可以使用的常见归约运算。尽管可以定义自定义归约操作，但这超出了本教程的范围。 MPI 定义的归约操作包括：

◼ MPI_MAX - 返回最大元素。

◼ MPI_MIN - 返回最小元素。

◼ MPI_SUM - 对元素求和。

◼ MPI_PROD - 将所有元素相乘。

◼ MPI_LAND - 对元素执行逻辑与运算。

◼ MPI_LOR - 对元素执行逻辑或运算。

◼ MPI_BAND - 对元素的各个位按位与执行。

◼ MPI_BOR - 对元素的位执行按位或运算。

◼ MPI_MAXLOC - 返回最大值和所在的进程的秩。

◼ MPI_MINLOC - 返回最小值和所在的进程的秩。

下面是 MPI_Reduce 通信模式的说明。

在上图中，每个进程包含一个整数。调用 MPI_Reduce 的根进程为 0，并使用 MPI_SUM 作为归约运算。这四个数字相加后将结果存储在根进程中。

查看当进程拥有多个元素时会发生什么也很有用。下图显示了每个进程归约多个数字的情况。

上图中的每个进程都有两个元素。结果求和基于每个元素进行。换句话说，不是将所有数组中的所有元素累加到一个元素中，而是将每个数组中的第 i 个元素累加到进程 0 结果数组中的第 i 个元素中。

现在您了解了 MPI_Reduce 的外观，我们可以尝试一些代码示例。

使用 MPI_Reduce 计算均值

在上一节中，我们展示了如何使用 MPI_Scatter 和 MPI_Gather 计算平均值。使用 MPI_Reduce 可以简化上一节的代码。以下是本节示例代码中 reduce_avg.c 的片段。

float *rand_nums = NULL;
rand_nums = create_rand_nums(num_elements_per_proc);

// Sum the numbers locally
float local_sum = 0;
int i;
for (i = 0; i < num_elements_per_proc; i++) {
  local_sum += rand_nums[i];
}

// Print the random numbers on each process
printf("Local sum for process %d - %f, avg = %f\n",
       world_rank, local_sum, local_sum / num_elements_per_proc);

// Reduce all of the local sums into the global sum
float global_sum;
MPI_Reduce(&local_sum, &global_sum, 1, MPI_FLOAT, MPI_SUM, 0,
           MPI_COMM_WORLD);

// Print the result
if (world_rank == 0) {
  printf("Total sum = %f, avg = %f\n", global_sum,
         global_sum / (world_size * num_elements_per_proc));
}

在上面的代码中，每个进程都会创建随机数并计算和保存在 local_sum 中。然后使用 MPI_SUM 将 local_sum 归约至根进程。然后，全局平均值为 global_sum / (world_size * num_elements_per_proc)。如果您从 repo 的 tutorials 目录中运行 reduce_avg 程序，则输出应与此类似。

>>> cd tutorials
>>> ./run.py reduce_avg
mpirun -n 4  ./reduce_avg 100
Local sum for process 0 - 51.385098, avg = 0.513851
Local sum for process 1 - 51.842468, avg = 0.518425
Local sum for process 2 - 49.684948, avg = 0.496849
Local sum for process 3 - 47.527420, avg = 0.475274
Total sum = 200.439941, avg = 0.501100

现在是时候接触 MPI_Reduce 的同级对象 - MPI_Allreduce 了。

MPI_Allreduce

许多并行程序中，需要在所有进程而不是仅仅在根进程中访问归约的结果。以与 MPI_Gather 相似的补充方式，MPI_Allreduce 将归约值并将结果分配给所有进程。函数原型如下：

MPI_Allreduce(
    void* send_data,
    void* recv_data,
    int count,
    MPI_Datatype datatype,
    MPI_Op op,
    MPI_Comm communicator)

MPI_Allreduce 等效于先执行 MPI_Reduce，然后执行 MPI_Bcast。很简单，对吧？

使用 MPI_Allreduce 计算标准差

许多计算问题需要进行多次归约来解决。一个这样的问题是找到一组分布式数字的标准差。或许您可能已经遗忘了什么是标准差，标准差是数字与均值之间的离散程度的度量。较低的标准差表示数字靠得更近，对于较高的标准差则相反。

要找到标准差，必须首先计算所有数字的平均值。总和均值的平方根是最终结果。给定问题描述，我们知道所有数字至少会有两个和，转化为两个归约。本文代码 reduce_stddev.c 中的一个片段展示了如何应用 MPI 解决此问题的概况。

rand_nums = create_rand_nums(num_elements_per_proc);

// Sum the numbers locally
float local_sum = 0;
int i;
for (i = 0; i < num_elements_per_proc; i++) {
  local_sum += rand_nums[i];
}

// Reduce all of the local sums into the global sum in order to
// calculate the mean
float global_sum;
MPI_Allreduce(&local_sum, &global_sum, 1, MPI_FLOAT, MPI_SUM,
              MPI_COMM_WORLD);
float mean = global_sum / (num_elements_per_proc * world_size);

// Compute the local sum of the squared differences from the mean
float local_sq_diff = 0;
for (i = 0; i < num_elements_per_proc; i++) {
  local_sq_diff += (rand_nums[i] - mean) * (rand_nums[i] - mean);
}

// Reduce the global sum of the squared differences to the root
// process and print off the answer
float global_sq_diff;
MPI_Reduce(&local_sq_diff, &global_sq_diff, 1, MPI_FLOAT, MPI_SUM, 0,
           MPI_COMM_WORLD);

// The standard deviation is the square root of the mean of the
// squared differences.
if (world_rank == 0) {
  float stddev = sqrt(global_sq_diff /
                      (num_elements_per_proc * world_size));
  printf("Mean - %f, Standard deviation = %f\n", mean, stddev);
}

在上面的代码中，每个进程都会计算元素的局部总和 local_sum，并使用 MPI_Allreduce对它们求和。在所有进程上都有全局总和后，将计算均值 mean，以便可以计算局部距平的平方 local_sq_diff。一旦计算出所有局部距平的平方，就可以通过使用 MPI_Reduce 得到全局距平的平方 global_sq_diff。然后，根进程可以通过取全局距平的平方的平均值的平方根来计算标准差。

使用运行脚本运行示例代码将产生如下输出：

>>> ./run.py reduce_stddev
mpirun -n 4  ./reduce_stddev 100
Mean - 0.501100, Standard deviation = 0.301126

Up next

现在您可以轻松使用所有常见的集合 - MPI_Bcast，MPI_Scatter，MPI_Gather 和 MPI_Reduce，我们可以利用它们来构建复杂的并行程序。在下一节中，我们将开始研究 MPI 组和通讯器.

欢迎扫码关注微信公众号“网络技术风云汇”，更快速接收更多网络技术咨询。