Adaptive Placement and Routing for Service Function Chains With Service Deadlines

Network Function Virtualization (NFV) pushes the hardware-based network functions to generic servers as software and brings a highly flexible for deployment. The availability of Virtual Machines (VMs) enables the dynamic placement of Virtual Network Functions (VNFs) on demand, and it can reduce a large number of manual configuration processes that increase deployment efficiency. However, some services require more than one VNF to process. Therefore, the network flows need to traverse a set of sequential network functions called Service Function Chain (SFC). How to efficiently route traffic along service function chain and place VNFs in a network under operational constraints is a crucial issue. In this paper, we must overcome two challenges: (1) determining a flow path that traverses suitable network functions in the required order to meet the requirement of services, and (2) considering network loading and other dynamic characteristics when traffic is routed through existing VNFs. Thus, we present methods to solve the routing and placement problems for the service function chain. Our solutions transform the network representation to a virtual layered graph that considers NFV processing latency and allows conventional shortest path algorithms to solve the problem. We are not only pursuing high success rates to serve more flows but also taking into account the execution time of the algorithms.