TY - JOUR

T1 - Traffic routing in stochastic network function virtualization networks

AU - Yang, Song

AU - Li, Fan

AU - Trajanovski, Stojan

AU - Fu, Xiaoming

N1 - Publisher Copyright:
© 2020 Elsevier Ltd

PY - 2020/11/1

Y1 - 2020/11/1

N2 - 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.

AB - 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.

KW - Bandwidth

KW - Delay

KW - Network function virtualization

KW - Routing

KW - Stochastic

UR - http://www.scopus.com/inward/record.url?scp=85089751770&partnerID=8YFLogxK

U2 - 10.1016/j.jnca.2020.102765

DO - 10.1016/j.jnca.2020.102765

M3 - Article

AN - SCOPUS:85089751770

SN - 1084-8045

VL - 169

JO - Journal of Network and Computer Applications

JF - Journal of Network and Computer Applications

M1 - 102765

ER -