Providing VNF Services with PipeHose Model Based Nonblocking SDN Networks

Combining Virtual Network Functions (VNF) and Software Defined Networking (SDN) enables fine-grained traffic steering to provide required network services to flows. However, online routing calculation and flow table enforcement incurs an non-negligible overhead. In this work, we propose to design a nonblocking network with fixed routing and VNF provisioning schemes to improve the network performance (e.g. the flow completion time). We first formulate this problem as a linear programming (LP) problem with infinite number of constraints, and leverage primal-dual technology to reformulate the problem as a polynomial size LP. The LP formulation is also extended to reconfigure the network when some components become unavailable, in order to keep the network nonblocking. Since solving the LP formulation is time consuming or even impossible in large scale networks, an efficient algorithm based on optimization decomposition and column generation is proposed to find a near optimal solution quickly. Simulation results show that nonblocking networks can speed up 60% of the flows by 2x, with a small increase in the required network capacity, compared with approaches that do not use the nonblocking networks.