  We consider the task of computing (combined) function mapping and routing for
requests in Software-Defined Networks (SDNs). Function mapping refers to the
assignment of nodes in the substrate network to various processing stages that
requests must undergo. Routing refers to the assignment of a path in the
substrate network that begins in a source node of the request, traverses the
nodes that are assigned functions for this request, and ends in a destination
of the request. The algorithm either rejects a request or completely serves a
request, and its goal is to maximize the sum of the benefits of the served
requests. The solution must abide edge and vertex capacities. We follow the
framework suggested by Even for the specification of the processing
requirements and routing of requests via processing-and-routing graphs
(PR-graphs). In this framework, each request has a demand, a benefit, and
PR-graph. Our main result is a randomized approximation algorithm for path
computation and function placement with the following guarantee. Let $m$ denote
the number of links in the substrate network, $\eps$ denote a parameter such
that $0< \eps <1$, and $\opt_f$ denote the maximum benefit that can be attained
by a fractional solution (one in which requests may be partly served and flow
may be split along multiple paths). Let $\cmin$ denote the minimum edge
capacity, and let $\dmax$ denote the maximum demand. Let $\Deltamax$ denote an
upper bound on the number of processing stages a request undergoes. If
$\cmin/(\Deltamax\cdot\dmax)=\Omega((\log m)/\eps^2)$, then with probability at
least $1-\frac{1}{m}-\textit{exp}(-\Omega(\eps^2\cdot \opt_f /(\bmax \cdot
\dmax)))$, the algorithm computes a $(1-\eps)$-approximate solution.
