Joint Virtual Network Function Placement and Flow Routing in Edge-Cloud Continuum

doi:10.1109/TC.2023.3347671

2024-03-01

PRE

Yingling Mao

Xiaojun Shang

Yu Liu

杨园园 (Yuanyuan Yang) *

DOI：10.1109/TC.2023.3347671

原文链接

原文求助

摘要

En 中文

Network Function Virtualization (NFV) is becoming one of the most popular paradigms for providing cost-efficient, flexible, and easily-managed network services by migrating network functions from dedicated hardware to commercial general-purpose servers. Despite the benefits of NFV, it remains a challenge to deploy Service Function Chains (SFCs), placing virtual network functions (VNFs) and routing the corresponding flow between VNFs, in the edge-cloud continuum with the objective of jointly optimizing resource and latency. In this paper, we formulate the SFC Deployment Problem (SFCD). To address this NP-hard problem, we first introduce a constant approximation algorithm for a simplified SFCD limited at the edge, followed by a promotional algorithm for SFCD in the edge-cloud continuum, which also maintains a provable constant approximation ratio. Furthermore, we provide an online algorithm for deploying sequentially-arriving SFCs in the edge-cloud continuum and prove the online algorithm achieves a constant competitive ratio. Extensive simulations demonstrate that on average, the total costs of our offline and online algorithms are around 1.79 and 1.80 times the optimal results, respectively, and significantly smaller than the theoretical bounds. In addition, our proposed algorithms consistently outperform the popular benchmarks, showing the superiority of our algorithms.

Keyword:

Servers

Approximation algorithms

Cloud computing

Heuristic algorithms

Routing

Costs

Edge computing

Network function virtualization

service function chain deployment

edge computing

cloud computing