Competitive Path Computation and Function Placement in SDNs

We consider a task of serving requests that arrive in an online fashion in Software-Defined Networks (SDNs) with network function virtualization (NFV). Each request specifies an abstract routing and processing "plan" for a flow. Each processing function can be performed by a specified subset of servers in the system. The algorithm needs to either reject the request or admit it and return detailed routing (a.k.a. "path computation") and processing assignment ("function placement"). Each request also specifies the communication bandwidth and the processing load it requires. Components in the system (links and processors) have bounded capacity; a feasible solution may not violate the capacity constraints. Requests have benefits and the goal is to maximize the total benefit of accepted requests. In this paper we first formalize the problem, and propose a new service model that allows us to cope with requests with unknown duration. The new service model augments the traditional accept/reject schemes with a new possible response of "stand by." Our main result is an online algorithm for path computation and function placement that guarantees, in each time step, throughput of at least $Ω\left(\frac{\text{OPT}^*}{\log n}\right)$, where $n$ is the system size and $\text{OPT}^*$ is an upper bound on the maximal possible throughput. The guarantee holds assuming that requests ask for at most an $O\left(1/{\log n}\right)$-fraction of the capacity of any component in the system. Furthermore, the guarantee holds even though our algorithm serves requests in an all-or-nothing fashion using a single path and never preempts accepted flows, while $\text{OPT}^*$ may serve fractional requests, may split the allocation over multiple paths, and may arbitrarily preempt and resume service of requests.