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 et al.[1] 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, ε denote a parameter such that 0 < ε < 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 c min denote the minimum edge capacity, and let d max denote the maximum demand. Let ∆ max denote an upper bound on the number of processing stages a request undergoes. If c min /(∆ max · d max ) = Ω((log m)/ε 2 ), then with probability at least 1 . The key characteristics of these developments are: (i) separation between the data plane and the management (or control) plane, (ii) specification of the management of the network from a global view, (iii) introduction of network abstractions that provide a simple networking model, and (iv) programmability of network components. In this paper we focus on an algorithmic problem that the network manager needs to solve in an NFV/SDN setting. This problem is called path computation and function placing. Path computation is simply the task of allocating paths to requests. These paths are subject to the capacity constraints of the network links and the forwarding capacity of the network nodes. In modern networks, networking is not limited to forwarding packets from sources to destinations. Requests can come in the form of flows (i.e., streams of packets from a source node to a destination node with a specified packet rate) that must undergo processing stages on their way to their destination. Examples of processing steps include: compression, encryption, firewall validation, deep packet inspection, etc. The crystal ball of NFV is the introduction of abstractions that allow one to specify, per request, requirements such as processing stages, valid locations for each processing stage, and allowable sets of links along which packets can be sent between processing stages. An important example for such goal is supporting security requirements that stipulate that unencrypted packets do not traverse untrusted links or reach untrusted nodes. From an algorithmic point of view, the problem of path computation and function mapping combines two different optimization problems. Path computation alone (i.e., the case of pure packet forwarding without processing of packets) is an integral path packing problem. Function mapping alone (i.e., the case in which packets only need to be processed but not routed) is a load balancing problem. To give a feeling of the problem, consider a special case of requests for streams, each of which needs to undergo the same sequence of k processing stages w 1 , w 2 , . . . , w k . This means that service of a request from s i to t i is realized by a concatenation of k + 1 paths: ; t i , where processing stage w i takes place in node v i . Note that the nodes v 1 , . . . , v k need no be distinct and the concatenated path p 0 • p 1 • · · · • p k need not be simple. A collection of allocations that serve a set of requests not only incurs a forwarding load on the network elements, it also incurs a computational load on the nodes. The computational load is created by the need to perform the processing stages for the requests. Previous works. Most papers on the topic resort to heuristics or non-polynomial algorithms. For example, in [6] mixed-integer programming is employed. The online version is studied in [1] in which new standby/accept service model is introduced. Contribution and Techniques. Under reasonable assumptions (i.e., logarithmic capacityto-demand ratio and sufficiently large optimal benefit), we present the first offline approximation algorithm for the path computation and function placing problem. Our starting point is the model of SDN requests presented in [1]. In this model, each request is represented by a special graph, called a place-and-route graph (pr-graph, in short). The pr-graph represents both the routing requirement and the processing requirements that the packets of the stream must undergo. We also build on the technique of graph products for representing valid realizations of requests [1]. We propose a fractional relaxation of the problem. The fractional relaxation consists of a set of fractional flows, each over a different product graph. Each flow is fractional in the sense that it may serve only part of a request and may split the Even, Rost, and Schmid 3 flow among multiple paths. We emphasize that the fractional flows do not constitute a multi-commodity flow because they are over different graphs. Nevertheless, the fractional problem is a general packing LP [4]. We solve the fractional relaxation and apply randomized rounding [4] to find an approximate solution. Although randomized rounding is very well known and appears in many textbooks and papers, the version for the general packing problem appears only in half a page in the thesis of Raghavan [4, p. 41]. A special case with unit demands and unit benefits appears in [3]. Perhaps one of the contributions of this paper is a full description of the analysis of randomized rounding for the general packing problem. In Even et al. [1], a model for SDN requests, based on so called place-and-route graphs (pr-graphs) and product graphs is presented. The model is quite general, and allows each request to have multiple sources and destinations, varying bandwidth demand based on processing stages, task specific capacities, prohibited locations of processing, and prohibited links for routing between processing stages, etc. We overview a simplified version of this model so that we can define the problem of path computation and function placement. The substrate network is a fixed network of servers and communication links. The network is represented by a graph N = (V, E), where V is the set of nodes and E is the set of edges. Nodes and edges have capacities. The capacity of an edge e is denoted by c(e), and the capacity of a node v ∈ V is denoted by c (v). By scaling, we may assume that min x∈V ∪E c(x) = 1. We note that the network is static and undirected (namely each edge represents a bidirectional communication link), but may contain parallel edges. Each request is specified by a tuple , where the components are as follows: is a directed (acyclic) graph called the place-and-route graph (pr-graph). There is a single source (respectively, sink) that corresponds to the source (resp. destination) of the request. We denote the source and sink nodes in G j by s j and t j , respectively. The other vertices correspond to services or processing stages of a request. The edges of the pr-graph are directed and indicate precedence relations between pr-vertices. 2. The demand of r j is d j and benefit is b j . By scaling, we may assume that min j b j = 1. is a set of "allowed" nodes in N that can perform service x, and U j (y) is a set of "allowed" edges of N that can implement the routing requirement that corresponds to y. For each request r j , the product network pn(N, r j ) is defined as follows. The node set of pn(N, r j ), denoted V j , is defined as V j ∪ y∈Yj (U j (y) × {y}). We refer to the subset U j (y) × {y} as the y-layer in the product graph. The edge set of pn(N, r j ), denoted E j , consists of two types of edges E j = E j,1 ∪ E j,2 defined as follows.  Processing edges connect two copies of the same network vertex in different layers. E j,2 = (v, y), (v, y ) | y = y are 2 edges with a common endpoint x, and v ∈ U j (x) . Consider a pathp in the product graph pn(N, r j ) that starts in the s j -layer and ends in the t j -layer, where s j and t j are the source and sink vertices of the pr-graph G j . Such a path p represents the routing of request r j from its origin to its destination and the processing stages that it undergoes. The processing edges alongp represent nodes in which processing stages of r j take place. The routing edges within each layer represent paths along which the request is delivered between processing stages. Definition 1. A pathp in the product network pn(N, r j ) that starts in the (source) s j -layer and ends in the (sink) t j -layer is a valid realization of request r j . We note that in [1] the projection ofp to the substrate network is referred to as a valid realization. The projection of vertices of pn(N, r j ) to vertices in N maps a vertex (u, y) to u. By the definition of the product graph, this projection maps paths in pn(N, r j ) to paths in N . Consider the path p in N resulting from the projection of a pathp in the product graph. Note that p may not be simply even ifp is simple. Notation. Consider a pathp in the product graph pn(N, r j ). The multiplicity of an edge e = (u, v) in the substrate network N inp is the number of routing edges inp that project to e, formally: Similarly, the multiplicity of a vertex v ∈ V inp is the number of processing edges inp that project to v, formally: Capacity Constraints. LetP = {p i } i∈I denote a set of valid realizations for a subset {r i } i∈I ⊆ R of requests. The setP satisfies the capacity constraints if Definition of the PCFP-problem. The input in the PCFP-problem consists of a substrate network N = (V, E) and a set of requests {r i } i∈I . The goal is to compute valid realizations P = {p i } i∈I for a subset I ⊆ I such that: (1)P satisfies the capacity constraints, and (2) the benefit i∈I b i is maximum. We refer to the requests r i such that i ∈ I as the accepted requests; requests r i such that i ∈ I \ I are referred to as rejected requests. Even, Rost, and Schmid The Approximation Algorithm for PCFP The approximation algorithm for the PCFP-problem is described in this section.  We now define the fractional relaxation of the PCFP-problem. Instead of assigning a valid realizationp i per accepted request r i , we assign a fractional flowf i in the product graph pn(N, r i ). The source of flowf i is the source layer (i.e., a super source that is connected connected to the all the nodes in the source layer). Similarly, the destination off i is the destination layer. The demand off i is d i (hence |f i | ≤ d i ). As in the integral case, the capacity constrains are accumulated across all the requests. Namely, let f i denote the projection off i to the substrate network. The edge capacity constraint for e is i f i (e) ≤ c(e). A similar constraint is defined for vertex capacities. The benefit of a fractional solution We emphasize that this fractional relaxation is not a multi-commodity flow. The reason is that eachf i is over a different product graph. However, the fractional relaxation is a general packing LP. The algorithm uses a parameter 1 > > 0. The algorithm proceeds as follows. Divide all the capacities by (1 + ε). Namely,c(e) = c(e)/(1 + ε) andc(v) = c(v)/(1 + ε). Compute an maximum benefit fractional PCFP solution {f i } i . 3. Apply the randomized rounding procedure independently to each flowf i over the product network pn(N, r j ). (See Appendix B for a description of the procedure). Let p i denote the path in pn(N, r i ) (if any) that is assigned to request r i by the randomized rounding procedure. Let {f i } i denote the projection of p i to the substrate network. Note that each f i is an unsplittable all-or-nothing flow. The projection of p i might not be a simple path in the substrate, hence the flow f i (e) can be a multiple of the demand d i . Definition 2. The diameter of a pr-graph G j is the length of a longest path in G j from the source s j to the destination t j . We denote the diameter of G j by ∆(G j ). The diameter of G j is well defined because G j is acyclic for every request r j . In all applications we are sware of, the diameter ∆(G j ) is constant (i.e., less than 5). Notation. Let ∆ max max j∈I ∆(G j ) denote the maximum diameter of a request. Let c min denote the minimum edge capacity, and let d max denote the maximum demand. Let opt f denote a maximum benefit fractional PCFP solution (with respect to the original capacities c(e) and c(v)). Let alg denote the solution computed by the algorithm. Let B(S) denote the benefit of a solutions S. Define β(ε) (1 + ε) ln(1 + ε) − ε. Our goal is to prove the following theorem.  We remark in asymptotic terms, the theorem states that if cmin ∆max·dmax = Ω( log |E| ε 2 ), then alg satisfies the capacity constrains with probability 1 − O(1/|E|) and attains a benefit of (1 − O(ε)) · B(opt f ) with probability 1 Proof. The proof is based on the fact that randomized rounding is applied to each flowf i independently. Thus the congestion of an edge in alg is the sum of independent random variables. The same holds for the B(alg). The proof proceeds by applying Chernoff bounds. Proof of Eq. 1. For the sake of simplicity we assume that there are no vertex capacities (i.e., c(v) = ∞). The proof is based on the Chernoff bound in Theorem 5. To apply the bound, fix a substrate edge e ∈ E. Recall that f i (e) is a flow path that is obtained by a projection of a path in the product network pn(N, r i ). Let The conditions of Theorem 5 are satisfied for the following reasons. Note that 0 . Let alg(e) denote the load incurred on the edge e by alg. Namely alg(e) i∈I f i (e). Note that alg(e) ≥ (1 + ε) ·c(e) iff i∈I From Theorem 5 we conclude that: Eq. 1 follows by applying a union bound over all the edges. Proof of Eq. 2. The proof is based on the Chernoff bound stated in Theorem 6. To apply the bound, let capacities. The conditions of Theorem 6 are satisfied for the following reasons. Since  We note that in the case of identical benefits (i.e., all the benefits equal one and hence b max = 1) one can strengthen the statement. If B(opt f ) > c min , then the large capacities assumption implies that B(opt f )/(d max · b max ) ≥ c min /d max ≥ ε −2 · ln |E|. This implies that that B(alg) ≥ (1 − O(ε)) · B(opt f ) with probability at least 1 − 1/poly(|E|). By adding the probabilities of the two possible failures (i.e., violation of capacities and small benefit) and taking into account the prescaling of capacities, we obtain that with probability at least 1 − O(1/poly(|E|)), randomized rounding returns an all-or-nothing unsplittable multi-commodity flow whose benefit is at least 1 − O(ε) times the optimal benefit. Theorem 3 provides an upper bounds of the probability that alg is not feasible and that B(alg) is far from B(opt f ). These bounds imply that our algorithm can be viewed as version of an asymptotic PTAS in the following sense. Suppose that the parameters b max and d max are not a function of |E|. As the benefit of the optimal solution opt f increases, the probability that B(alg) ≥ (1 − O(ε)) · B(opt f ) increases. On the other hand, we need the capacity-to-demand ratio to be logarithmic, namely, c min ≥ Ω((∆ max · d max · ln |E|)/ε 2 ). We believe that the capacity-to-demand ratio is indeed large in realistic networks. Research supported by the EU project UNIFY FP7-IP-619609.
In contrast, we have considered in this paper a more general setting, in which the decomposition approach based on random walks REF is not feasible, as we allow for arbitrary service cactus graphs.