  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 $\Omega\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.
