Hello World.

Robustness-aware VNF Placement and Request Scheduling in Edge Cloud

INFOCOM22: (Rejected) Scores 3 3 2 1
IWQoS 2022: (Rejected) Scores 3 3 1
Accepted by ComNet (2023.6.16)


In edge clouds, service providers place virtual network functions (VNFs) in edge computing nodes (ECNs) to serve requests generated by users. Thus, it is essential to consider VNF placement and request scheduling in edge clouds. To efficiently utilize network resources and ensure users’ QoS, existing works often focus on minimizing request completion time or maximizing network throughput. However, they ignore two practical factors: malicious users and failed VNFs, leading to poor network robustness.
To solve this issue, this paper studies robust VNF placement and request scheduling. Specifically, we limit the number of VNFs each user can access and the number of users each VNF can serve to control the influence scope of malicious users and VNF failures.
Since placing VNFs is time-consuming and requests arrive dynamically, we solve this problem through two phases: robust VNF placement and assignment, and online request scheduling. For the first phase, we design an efficient knapsack-based rounding algorithm with bounded approximation factors. For online request scheduling, we propose a primal-dual based online algorithm with a competitive ratio of $[1-\epsilon, O(\log 1/\epsilon)]$ where $\epsilon \in (0,1)$. Experiment and simulation results show that our algorithms can achieve better performance and robustness compared with other alternatives.


In edge clouds, service providers supply services by placing VNFs (eg , firewall, load balancer) in the ECNs, while users obtain services through forwarding requests to corresponding VNFs. Thus, VNF placement and request scheduling are important in edge clouds.

However, the existing works ignore the following two factors which will degrade the robustness of the edge cloud.
The first factor is the malicious users. Owing to 5G, there are massive users in edge clouds, and the diversity of users brings more probability of malicious users.
The second factor is the failed VNFs. VNF failures are common and influence the users’ QoS significantly. When a VNF is unavailable, the served requests should be rescheduled to other available VNFs, which will cause a long rescheduling delay and significantly decrease users’ QoS.

We consider two robustness constraints when placing VNFs and scheduling requests:

  1. User constraint: Different from legitimate users, malicious users may try to access as many VNFs as possible to expand the influence scope of the attacks. Thus, to limit the influence of the malicious user, each user’s requests will be scheduled to a limited number of VNFs. In this way, we can control the number of affected VNFs when encountering the malicious user.
  2. VNF constraint: to control the impact of the VNF failure on users, each VNF will serve a limited number of users. In this way, we can limit the affected number of users when encountering the VNF failure.

— Aug 1, 2021