Joint Placement and Routing of Network Function Chains in Data Centers

In this work, we investigate the problem of joint optimization over placement and routing of network function chains in data centers. In the offline case, we demonstrate that a classical randomization algorithm works well and we derive a new bound on the performance sub-optimality gap. In the online case, we prove a fundamental lower bound in resource violation and propose a new algorithm that combines techniques from multiplicative weight update and primal-dual update paradigms. This online algorithm asymptotically achieves the best possible performance in terms of resource allocation among all online algorithms. We demonstrate the applicability of our solutions to address practical problems by conducting simulation-based evaluations over different data center architectures using data generated from real trace distribution