Traffic routing in stochastic network function virtualization networks

Network Function Virtualization (NFV) is emerging as an attractive solution, which can transform complex network functions from the dedicated hardware implementations into software instances running in a virtualized environment. In NFV, the requested service is implemented by a sequence of Virtual Network Functions (VNF) that can run on generic servers by leveraging the virtualization technology. These VNFs are placed in a predefined order, which is also known as the Service Function Chaining (SFC). While most of the existing work on traffic routing in NFV networks assume deterministic link delay and bandwidth, the real-life network usually behaves in a stochastic manner, due to e.g., inaccurate data, expired exchanged information, insufficient estimation to the network. Motivated by this, we consider the stochastic NFV networks, where the link bandwidth and delay are assumed to be random variables and their cumulative distribution functions are known. We first study how to calculate the delay and bandwidth value in an SFC such that their realizing probabilities are satisfied. Subsequently, we formally define the traffic routing problem in stochastic NFV networks and prove it is NP-hard. We present an exact solution and a tunable heuristic to solve this problem. The proposed heuristic is a sampling-based algorithm, and it leverages the Tunable Accuracy Multiple Constraints Routing Algorithm (TAMCRA) to find a multi-constraint path for each adjacent VNF pair. It dynamically adjusts the link weights as well as delay and bandwidth realizing probability constraint after finding the path for each VNF pair so that the cumulated probabilities will not violate the specified values. Finally, we evaluate the performance of the proposed algorithms via extensive simulations.