Ant Colony based Online Learning Algorithm for Service Function Chain Deployment
Ant Colony based Online Learning Algorithm for Service Function Chain Deployment
复制标题
DOI：
10.1109/infocom53939.2023.10229012
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Yingling Mao;Xiaojun Shang;Yuanyuan Yang
中科院分区：
文献类型：
--
作者：
Yingling Mao;Xiaojun Shang;Yuanyuan Yang
网络功能虚拟化（Network Function Virtualization，NFV）是一种具有成本效益、管理便利性和灵活性的新兴技术，其中服务功能链（Service Function Chain，SFC）部署方案是一项关键技术。在本文中，我们提出了一种蚁群优化（ACO）元启发式算法的在线SFC部署，称为ACO-OSD，共同最小化服务器的运营成本和网络延迟的目标。作为一种元启发式算法，ACO-OSD的性能优于最先进的启发式算法，特别是平均降低42.88%的总成本。为了减少ACO-OSD的时间成本，我们设计了两种加速机制：下一个适合（NF）策略和SFC部署方案和蚂蚁旅行之间的多对一模型。此外，对于需要实时决策的场景，我们提出了一种新的在线学习框架的基础上的ACO-OSD算法，称为基于先验的学习实时布局（PLRP）。它实现了近实时的SFC部署，时间复杂度为O（n），其中n是所有新到达的SFC的VNF的总数。与现有启发式算法相比，该算法的平均总代价降低了36.53%。最后，我们进行了大量的模拟，以证明ACO-OSD和PLRP与基准相比，出色的性能。
Network Function Virtualization (NFV) emerges as a promising paradigm with the potential for cost-efficiency, manage-convenience, and flexibility, where the service function chain (SFC) deployment scheme is a crucial technology. In this paper, we propose an Ant Colony Optimization (ACO) meta-heuristic algorithm for the Online SFC Deployment, called ACO-OSD, with the objectives of jointly minimizing the server operation cost and network latency. As a meta-heuristic algorithm, ACO-OSD performs better than the state-of-art heuristic algorithms, specifically 42.88% lower total cost on average. To reduce the time cost of ACO-OSD, we design two acceleration mechanisms: the Next-Fit (NF) strategy and the many-to-one model between SFC deployment schemes and ant-tours. Besides, for the scenarios requiring real-time decisions, we propose a novel online learning framework based on the ACO-OSD algorithm, called prior-based learning real-time placement (PLRP). It realizes near real-time SFC deployment with the time complexity of O(n), where n is the total number of VNFs of all newly arrived SFCs. It meanwhile maintains a performance advantage with 36.53% lower average total cost than the state-of-art heuristic algorithms. Finally, we perform extensive simulations to demonstrate the outstanding performance of ACO-OSD and PLRP compared with the benchmarks.