The Cost of Quality of Service: SLA Aware VNF Placement and Routing Using Column Generation

In the Network Function Virtualization (NFV) paradigm, Internet Service Providers (ISP) provide network services to customers by routing and processing traffic through an ordered sequence of Virtual Network Functions (VNF). The Quality of the Service (QoS) depends on the quantity and relative placement of the VNFs, and is quantified by a set of Key Performance Indicators (KPIs) in a Service Level Agreement (SLA): a contract reached between the ISP and customer. In order to provide the service in line with the SLA, ISPs must consider the SLA constraints directly when placing VNFs and provisioning the network services in the physical network infrastructure. In this paper, we present a VNF placement and routing algorithm based on the column generation method which iterates between generating improving paths, and optimising the placement of the VNFs given the generated paths. SLA constraints are modelled as soft constraints for which violation incurs a cost, the sum of which is minimised. Unlike prior approaches, we consider the throughput, latency and availability SLA constraints. We validate our approach against a heuristic greedy algorithm, on a multi-tiered Radio Access Network (RAN) and show that the column generation method provides solutions with significantly lower SLA violation cost versus the greedy approach, while still being able to solve problems of a practical size. We also highlight that satisfying QoS can significantly increase the number of host nodes required, thus a trade-off exists between QoS and operational cost which should be explored further.