On Congestion Minimization for Service Chain Routing Problems
Lingnan Gao, George N. Rouskas · 2019
Network function virtualization (NFV), with its perceived potential to accelerate service deployment and to introduce flexibility in service provisioning, has drawn a growing interest from industry and academia alike over the past few years. One of the key challenges in realizing NFV is the service chain routing problem, whereby traffic must be routed so as to traverse the various components of a network service that have been mapped onto the underlying network. In this work, we consider the online service chain routing problem with the goal of minimizing the maximum network congestion. To this end, we present a simple yet effective online algorithm in which the routing decision is irrevocably made without prior knowledge of future requests. We prove that our algorithm is O(log m)-competitive, where m is the number of edges of the underlying network topology, and we show that this ratio is asymptotically optimal.