Network function virtualization (NFV) decouples network functions (NFs) from dedicated hardware, leading to significant cost reduction in network service provisioning. With NFV, a network service is represented by a series of inter-connected virtual network functions (VNFs), forming a service function chain (SFC). The problem of placing the VNFs on the NFV infrastructure (NFVI) and establishing the routing paths between them, according to the service chain template, is termed as SFC embedding.