In Mobile Edge Computing (MEC), users' traffic needs to traverse a set of service functions in a specific order, referred to as a service function chain (SFC), to complete service requests. Thus, SFC routing is an essential issue in MEC. In practice, user mobility and resource limitation are two critical challenges of SFC routing in MEC. However, the previous works either ignore the user mobility or resource limitation, especially the flow-table resources, leading to high transmission latency and resource overhead. In this paper, we study the mobility-aware service function chain routing in MEC. We design an SFC routing scheme called MASCOT to address the above challenges. MASCOT implements SFC routing through three steps: user location prediction, routing path decision, and packet forwarding. For user location prediction, we adopt the order-K Markov prediction method to predict users' next accessed base station. For routing path decision, we formulate the SFC routing selection (SRS) problem, which respects the resource constraints. We propose a primal-dual online SFC routing algorithm (POSR) for the SRS problem and prove that POSR can achieve good competitiveness. For packet forwarding, we propose a forwarding scheme based on segment routing to address the resource limitation challenge further. Extensive simulation results show that our scheme can improve the system throughput by about 40% compared with the state-of-the-art approaches.

More and more tenants (enterprises and personal users) migrate their tasks to clouds since it is a simple and low-cost way to obtain enough computing resources. However, due to potential node failures and malicious tenants, the modern cloud encounters one critical challenge, i.e., robustness. Conventionally, the cloud vendors deploy auxiliary systems to protect the cloud, which requires additional resource cost and increases the network complexity. To enhance the system robustness, this paper proposes a complementary scheme to improve the cloud robustness through efficient VM placement. Specifically, to alleviate the impact of malicious tenants and node failures on the cloud, when deploying VMs, we limit the number of pods (or service nodes) that each tenant can access, and the number of tenants hosted by each pod (or service node). Though there are a lot of works on VM placement, it is very challenging when the robustness issue is taken into consideration. To solve this problem, we formulate an integer linear programming and propose a rounding-based algorithm with a logarithmic approximation ratio. The simulation results show the high efficiency of the proposed algorithm. For example, our algorithm can improve the network throughput by 150% with other alternatives.

To meet the ever-increasing demands for high-quality network services, a software defined network (SDN) can support various virtual network functions (VNFs) using virtualization technology. Due to network dynamics, an SDN needs to be updated frequently to optimize various performance objectives, such as load balancing. Most previous solutions first determine a new network configuration (e.g., target VNF placement and flow routing) based on the current workload, and then update the VNF placement and routing paths of the existing flows. However, due to massive VNF’s state migration and slow update of the flow table, unacceptable update delay may occur, especially in large or frequently changed networks. In this paper, we address the real-time network update, which jointly considers the optimization of the service function chain (SFC) update and the routing update. We propose the delay-satisfied NFV-enabled network update (DSNU) problem, and prove its NP-Hardness. We design an algorithm with bounded approximation factor to solve this problem. To further reduce the delay, we also design an efficient algorithm for the update scheduling. The experimental results show that our method can reduce the network update delay by about 86% compared with the previous network update methods while preserving a similar network performance,i.e., the VNF instance load ratio increases by less than 5%.

Network Function Virtualization (NFV) is a new paradigm to enable service innovation through virtualizing traditional network functions. To construct a new NFV-enabled network, there are two critical requirements: minimizing server deployment cost and satisfying switch resource constraints. However, prior work mostly focuses on the server deployment cost, while ignoring the switch resource constraints (e.g., switch's flow-table size). It thus results in a large number of rules on switches and leads to massive control overhead. To address this challenge, we propose an incremental server deployment (INSD) problem for construction of scalable NFV-enabled networks. We prove that the INSD problem is NP-Hard, and there is no polynomial-time algorithm with approximation ratio of (1- ϵ)· ln m, where ϵ is an arbitrarily small value and m is the number of requests in the network. We then present an efficient algorithm with an approximation ratio of 2 · H(q · p), where q is the number of VNF's categories and p is the maximum number of requests through a switch. We evaluate the performance of our algorithm with experiments on physical platform (Pica8), Open vSwitches, and large-scale simulations. Both experimental results and simulation results show high scalability of the proposed algorithm. For example, our solution can reduce the control and rule overhead by about 88% with about 5% additional server deployment, compared with the existing solutions.

Network Function Virtualization (NFV) is a new paradigm to enable service innovation through virtualizing traditional network functions. To construct a new NFV-enabled network, there are two critical requirements: minimizing server deployment cost and satisfying switch resource constraints. However, prior work mostly focuses on the server deployment cost, while ignoring the switch resource constraints (e.g., switch's flow-table size). It thus results in a large number of rules on switches and leads to massive control overhead. To address this challenge, we propose an incremental server deployment (INSD) problem for construction of scalable NFV-enabled networks. We prove that the INSD problem is NP-Hard, and there is no polynomial-time algorithm with approximation ratio of (1- ε) ·ln m, where ε is an arbitrarily small value and m is the number of requests in the network. We then present an efficient algorithm with an approximation ratio of 2 · H(q · p)1, where q is the number of VNF's categories and p is the maximum number of requests through a switch. We evaluate the performance of our algorithm with experiments on physical platform (Pica8), Open vSwitches, and large-scale simulations. Both experiment and simulation results show high scalability of the proposed algorithm. For example, our solution can reduce the control and rule overhead by about 88% with about 5% additional server deployment, compared with the existing solutions.