Provable Approximation Algorithms for Online Traffic-Sensitive SFC Deployment

Yingling Mao

doi:10.1109/TON.2025.3566728

Provable Approximation Algorithms for Online Traffic-Sensitive SFC Deployment

0

PRE

AI

DOI：10.1109/TON.2025.3566728

原文链接

原文求助

摘要

En 中文

网络功能虚拟化（NFV）具有成本效益、管理便捷性和服务灵活性潜力，但同时也给服务功能链（SFC）部署问题带来了挑战，该问题属于NP难问题。该问题非常复杂，现有工作明显忽视了链路上的流量变化，仅提供了无性能保证的启发式算法。在本文中，我们通过构建一个对流量敏感的在线联合SFC部署与流量路由（TO-JPR）模型来填补这一空白，目标为联合优化资源成本和网络时延，并提出了一种新颖的两阶段方案来求解该模型。我们为第一阶段设计了动态分段打包（DSP）算法，该算法不仅能维持网络的最小流量负担，还能在资源成本上实现一个较小的常数近似比。此外，我们为第二阶段提出了贪婪映射（GM）算法，该算法能保证网络时延的全局近似比为O(d)。其中d是网络图的直径，通常小于O(log(M))，M为网络中的服务器数量。最后，我们进行了广泛的仿真实验，以证明我们的算法相较于最优解和基准方法具有出色的性能。

Keyword:

Network function virtualization

service function chain placement

flow routing

resource optimization

network latency optimization

Provable Approximation Algorithms for Online Traffic-Sensitive SFC Deployment

摘要

期刊

机构

引用论文