[Paper] 路由引导的进化算法用于大规模多目标VNF放置问题

Source: arXiv - 2512.15339v1

概述

本文探讨了现代云基础设施中最大的隐藏成本之一：数据中心数千台服务器的能耗。通过对虚拟网络功能（Virtual Network Functions，VNFs）——网络服务的软定义构建块——进行最优放置，运营商可以在仍然满足性能保证的前提下显著降低功耗。作者提出了一种 Routing‑Led Evolutionary Algorithm (RLEA)，该算法能够扩展到拥有 64 000 台服务器 的数据中心规模，突破了现有放置工具的限制。

关键贡献

• RLEA meta‑heuristic：一种并行进化算法，利用路由信息引导搜索，以获得高质量的 VNF 部署方案。
• 快速、轻量的目标评估：针对 QoS 指标（延迟、带宽）的新颖启发式函数，几乎常数时间运行，使得能够对数百万候选解进行快速适应度评估。
• 内存高效的数据结构：自定义的紧凑网络拓扑和路由表表示，即使在超大规模图上也能保持算法占用的内存足迹低。
• 简单基线启发式：一种快速、确定性的部署规则，尽管实现简单，却在超大规模实例上能够产生具竞争力的结果。
• 可扩展性演示：在合成和真实数据中心拓扑上进行的实证验证，规模最高达 64 K 台服务器，显示相较于基线部署可实现高达 30 % 的能耗节省。

方法论

1. 问题表述 – 将 VNF 放置任务建模为多目标优化问题：
   • 最小化总能耗（主要目标）。
   • 满足 QoS 约束（延迟、带宽和处理能力）。
2. 路由引导编码 – 每个候选解在预先计算的路由路径上对 VNFs 与物理服务器的映射进行编码。通过将进化搜索与实际流量路径对齐，算法避免了探索不可行或高度次优的放置方案。
3. 进化算子 – 标准遗传算子（选择、交叉、变异）经过调整以遵守路由约束。并行线程评估不同的子种群，并定期共享精英个体。
4. 启发式目标函数 – 作者不对每个候选解运行完整的网络仿真，而是使用从路由表和服务器负载估计中推导的轻量公式计算 QoS 分数。
5. 内存高效结构 – 稀疏邻接表和位打包路由矩阵使得即使在 64 K 节点的情况下，内存表示也保持在几百兆字节以内。
6. 基线启发式 – 一个贪婪算法，将 VNFs 放置在最短路径路由上负载最小的服务器上，既作为对比点，也作为进化运行的初始化器。

结果与发现

• 质量：RLEA 始终优于朴素贪婪基线和最先进的混合整数规划（MIP）求解器（后者在最大实例上未能在 24 小时限制内完成）。
• 速度：得益于快速的 QoS 启发式算法，每代评估仅需毫秒级时间，使算法能够在数小时内探索数百万个放置方案。
• 可扩展性：在 64 K 节点情况下，内存使用保持在 1 GB 以下，使该方法在普通服务器上也可行。

实际意义

• 能源感知编排：云运营商可以将 RLEA 接入现有的 NFV 编排器（例如 OpenStack Tacker、ONAP），自动生成能源最优的 VNF 部署方案，同时不牺牲时延保证。
• 动态重新优化：由于算法运行快速且并行，可定期（例如每晚）或在工作负载突增时触发，以实时重新平衡 VNF。
• 成本节约：功耗降低 30 % 可直接转化为超大规模数据中心运营支出下降——每年可能节省数百万美元。
• 绿色合规：通过提供可量化的能效指标，满足新兴的可持续性标准（例如欧盟数据中心行为准则）。
• 可扩展性：路由引导的编码可适用于其他部署问题，如容器调度或边缘计算资源分配，其中流量模式是性能的主要驱动因素。

限制与未来工作

• 启发式 QoS 估计 – 虽然快速，但简化的延迟/带宽公式可能会遗漏在高度拥塞网络中的细微交互；引入轻量级仿真可能提升准确性。
• 静态路由假设 – 当前方法假设路由矩阵固定；未来版本可以共同优化路由和放置，以获得更大收益。
• 真实环境验证 – 实验在合成拓扑和有限的公共数据中心轨迹上进行；在生产环境部署 RLEA 将揭示运营挑战（例如 VM 迁移开销）。
• 多租户公平性 – 该算法侧重于全局能耗降低；将其扩展以遵守租户层面的 SLA 和隔离政策是一个未解的研究方向。

结论：路由驱动进化算法为数据中心运营商提供了一条务实且可扩展的路径，以在保持网络服务性能的同时大幅降低能耗——这一进展弥合了学术优化理论与日常云工程之间的鸿沟。

作者

• Peili Mao
• Joseph Billingsley
• Wang Miao
• Geyong Mi
• Ke Li

论文信息

• arXiv ID: 2512.15339v1
• 分类: cs.NE
• 出版日期: 2025年12月17日
• PDF: 下载 PDF