Efficient and robust resource allocation for network function virtualization

Abstract

With the advent of Network Function Virtualization (NFV), network services that traditionally run on proprietary dedicated hardware can now be realized using Virtual Network Functions (VNFs) that are hosted on general-purpose commodity hardware. This new network paradigm offers a great flexibility to Internet service providers (ISPs) for efficiently operating their networks (collecting network statistics, enforcing management policies, etc.). However, introducing NFV requires an investment to deploy VNFs at certain network nodes (called VNF-nodes), which has to account for practical constraints such as the deployment budget and the VNF-node limited resources. While gradually transitioning to NFV, ISPs face the problem of where to efficiently introduce NFV; here, we measure the efficiency by the amount of traffic that can be served in an NFV-enabled network. This problem is non-trivial as it is composed of two challenging subproblems: 1) placement of VNF-nodes; 2) allocation of the VNF-nodes' resources to network flows. These two subproblems must be jointly considered to satisfy the objective of serving the maximum amount of traffic.

We first consider this problem for the one-dimensional setting, where all network flows require one network function, which requires a unit of resource to process a unit of flow. In contrast to most prior work that often neglects either the budget constraint or the resource allocation constraint, we explicitly consider both of them and prove that accounting for them introduces several new challenges. Specifically, we prove that the studied problem is not only NP-hard but also non-submodular. To address these challenges, we introduce a novel relaxation method such that the objective function of the relaxed placement subproblem becomes submodular. Leveraging this useful submodular property, we propose two algorithms that achieve an approximation ratio of $\frac{1}{2}(1-1/e)$ and $\frac{1}{3}(1-1/e)$ for the original non-relaxed problem, respectively.

Next, we consider the multi-dimensional setting, where flows can require multiple network functions, which can also require a different amount of each resource to process a unit of flow. To address the new challenges arising from the multi-dimensional setting, we propose a novel two-level relaxation method that allows us to draw a connection to the sequence submodular theory and utilize the property of sequence submodularity along with the primal-dual technique to design two approximation algorithms. Finally, we perform extensive trace-driven simulations to show the effectiveness of the proposed algorithms.

While the NFV paradigm offers great flexibility to network operators for efficient management of their networks, VNF instances are typically more prone to error and more vulnerable to security threats compared with dedicated hardware devices. Therefore, the NFV paradigm also poses new challenges concerning failure resilience. That has motivated us to consider robustness with respect to the class of sequence submodular function maximization problem, which has a wide range of applications, including those in the NFV domain. Submodularity is an important property of set functions and has been extensively studied in the literature. It models set functions that exhibit a diminishing returns property, where the marginal value of adding an element to a set decreases as the set expands. This notion has been generalized to considering sequence functions, where the order of adding elements plays a crucial role and determines the function value; the generalized notion is called sequence (or string) submodularity. In this part of the dissertation, we study a new problem of robust sequence submodular maximization with cardinality constraints. The robustness is against the removal of a subset of elements in the selected sequence (e.g., due to malfunctions or adversarial attacks). Compared to robust submodular maximization for set function, new challenges arise when sequence functions are concerned. Specifically, there are multiple definitions of submodularity for sequence functions, which exhibit subtle yet critical differences. Another challenge comes from two directions of monotonicity: forward monotonicity and backward monotonicity, both of which are important to proving performance guarantees. To address these unique challenges, we design two robust greedy algorithms: while one algorithm achieves a constant approximation ratio but is robust only against the removal of a subset of contiguous elements, the other is robust against the removal of an arbitrary subset of the selected elements but requires a stronger assumption and achieves an approximation ratio that depends on the number of the removed elements. Finally, we consider important problems that arise in the production networks, where packets need to pass through an ordered set of network functions called Service Function Chains (SFC) before reaching the destination. We study the following problems: (1) How to find an SFC-constrained shortest path between any pair of nodes? (2) What is the achievable SFC-constrained maximum flow? We propose a transformation of the network graph to minimize the computational complexity of subsequent applications of any shortest path algorithm. Moreover, we formulate the SFC-constrained maximum flow problem as a fractional multicommodity flow problem and develop a combinatorial algorithm for a special case of practical interest.