Provably Efficient Algorithms for Joint Placement and Allocation of Virtual Network Functions

I. INTRODUCTION

• Earlier VNF placement work was largely heuristic, and the cited provable-guarantee exception did not consider network topology.Other cited work focused on delay, latency, or physical resource usage.Source: §I · pp. 1–2
• The paper jointly chooses VNF instance locations and resource allocations to minimize instance count while fully processing every flow.The model allows fractions of a flow to be processed at multiple nodes, as in some security and analytics services.Source: §I · pp. 1–2
• The authors prove NP-hardness and a (1 − o(1)) ln m inapproximability bound, then give greedy algorithms with a matching asymptotic guarantee.They also report a constant approximation ratio in practical cases with multiple instances per node, and an optimal greedy algorithm for tree topologies.Source: §I · p. 2
• The paper evaluates its algorithms on randomly generated dense graphs and a realistic InternetMCI backbone topology.The introduction reports strong performance across the scenarios considered.Source: §I · p. 2

II. SYSTEM MODEL AND PROBLEM FORMULATION

• The network is a connected, undirected graph with n nodes and m flows, each following a loop-free path.Each node is a possible VNF location, such as a cluster or private datacenter.Source: §II · p. 2
• Each VNF instance has R units of computing resource, nodes can host multiple instances, and resource can be shared among passing flows.The model considers one network function and requires every flow's packets to be processed before leaving the network.Source: §II · p. 2
• The MILP minimizes total VNF instances while fully processing all flows, jointly choosing instance counts and per-flow resource allocations.The capacity allocated at a node is constrained by its hosted instances, and each flow may receive processing at multiple nodes along its path.Source: §II · pp. 2–3
• In the example, solution (b) is optimal with three VNF instances, each having processing capacity 10.The table's gray cells show flow-node allocations for flows that pass through the node.Source: Table I · p. 3, §II · p. 3

III. HARDNESS OF JPA-VNF

• JPA-VNF is NP-hard through a reduction from the set cover problem.The construction maps sets to nodes and elements to flows, with a feasible solution using k instances exactly when k sets cover the universe.Source: §III · p. 3
• The reduction constructs each flow's path from the nodes corresponding to sets containing its element, making minimum node selection equivalent to minimum set cover.Every flow rate is R/m, so one VNF instance can fully process all flows.Source: §III · p. 3
• Unless P=NP, JPA-VNF cannot be approximated within a factor of (1 − o(1)) ln m.Here m is the number of flows.Source: §III · p. 3

IV. ASYMPTOTICALLY OPTIMAL GREEDY ALGORITHMS

• Both greedy algorithms achieve an approximation ratio of (1 − o(1)) ln m + 2, asymptotically optimal under the hardness bound.The section notes that neither algorithm dominates the other.Source: §IV · pp. 3–4
• FNG repeatedly selects the node with the largest number of unprocessed flows passing through it.It treats each flow as an element and ignores differences in flow rates.Source: §IV · p. 3
• FRG instead selects the node with the largest amount of unprocessed data in each iteration.It uses flow-rate information, but the paper states that neither FRG nor FNG dominates.Source: §IV · pp. 3–4
• At each selected node, the algorithms process all passing unprocessed flows rather than splitting their rates across nodes.This choice avoids an exponentially growing set of combinations as graphs and flow interactions become more complex, while the authors report only minimal performance loss.Source: §IV · p. 4

A. Flow Number based Greedy Algorithm

• FNG selects the node covering the largest number of unprocessed flows, then places just enough instances to process them fully.The proof partitions flows according to whether their selected node receives one instance or more than one.Source: A. Flow Number based Greedy Algorithm · pp. 4–5
• If average solution density A is at least 2, Lemma 1 gives FNG an approximation ratio below 2.Lemma 1 bounds the ratio by A/(A − 1) when A is not 1.Source: A. Flow Number based Greedy Algorithm · p. 4
• In the cited cellular-network example, density is at least 100 and FNG is guaranteed to be within 1% of optimal.The example assumes 100 datacenters, 10 million flows averaging 1 Mbps, and 1 Gbps processing capacity per instance.Source: A. Flow Number based Greedy Algorithm · p. 4
• For the one-instance subproblem, reducing flow rates maps the instance to set cover, where FNG matches the greedy set-cover algorithm.The set-cover greedy guarantee bounds this branch’s performance.Source: A. Flow Number based Greedy Algorithm · p. 6
• FNG’s approximation ratio is at most (1 − o(1)) ln m + 2, making it asymptotically optimal.The lower bound follows from Theorem 2.Source: A. Flow Number based Greedy Algorithm · pp. 5–6

B. Flow Rate based Greedy Algorithm

• FRG selects the node with the largest unprocessed flow rate and allocates computing resource according to the flows’ rates.The algorithm processes all unprocessed flows at its selected node.Source: B. Flow Rate based Greedy Algorithm · pp. 6–7
• Neither greedy algorithm dominates: FRG performs better in one two-node example, while FNG performs better in another.The examples use a graph with two nodes and R = 10.Source: B. Flow Rate based Greedy Algorithm · pp. 6–7, Table II · p. 7
• FRG’s approximation ratio is no greater than (1 − o(1)) ln m + 2; the analysis states FRG can achieve the same approximation ratio as FNG.When all flow rates are set to the same value, FRG is the same as FNG.Source: B. Flow Rate based Greedy Algorithm · pp. 6–7

C. Complexity Analysis

• Initializing the sets of flows passing each node takes O(mn) time by traversing the flow paths.The maximum path length is at most n under the loop-free-path assumption.Source: C. Complexity Analysis · p. 7
• Selecting a node and updating unprocessed-flow sets across iterations takes O(n^2 + mn) time for FNG.There are at most n iterations, and updating the sets costs the same as their initialization.Source: C. Complexity Analysis · p. 7
• FRG has the same overall running time as FNG: O(n^2 + mn).Source: C. Complexity Analysis · p. 7

V. AN OPTIMAL ALGORITHM FOR TREE TOPOLOGY

• The algorithm processes levels from largest to smallest, handling nodes at each level in sequence.Source: §V · p. 7
• At a node with flows leaving the network, it places enough instances for those flows, then allocates remaining capacity to the first flow and updates that flow’s rate or removes it when fully processed.Source: §V · p. 7
• The paper proposes an optimal JPA-VNF solution for tree topologies under simplifying assumptions.Tree topologies are noted as relevant to streaming services and content delivery networks.Source: §V · p. 7

A. An Optimal Algorithm for JPA-VNF with Tree Topology

• The model assumes all flows are upstream, but the results immediately generalize to flows that are upstream or downstream.The upstream-only assumption is for ease of presentation.Source: A. An Optimal Algorithm for JPA-VNF… · p. 7
• GFT traverses nodes bottom-up and delays processing a flow until it intersects other flows or is about to leave the network.This preserves the opportunity to combine flows at a higher-level node.Source: A. An Optimal Algorithm for JPA-VNF… · p. 7
• When a flow exits the network at a node, GFT places VNF instances there to process the unprocessed flows leaving through that node.Remaining computing resource is allocated to waiting flows, ordered by the level of their exit node.Source: A. An Optimal Algorithm for JPA-VNF… · pp. 7–8
• Fig. 2 marks flow paths with dashed lines, VNF-hosting nodes with hollow circles, and per-flow resource allocations with adjacent rectangles; each instance has capacity R = 10.Source: Figure 2 · p. 8

B. Main Result: Optimality

• GFT is optimal for JPA-VNF on tree topologies.Source: B. Main Result: Optimality · p. 8
• A breaking point hosts an underutilized VNF instance, while GFT's conservative solution has at most one underutilized instance at each such node.The proof uses this structure to analyze resource waste.Source: B. Main Result: Optimality · p. 8
• For a subtree whose root is its only breaking point and has no external flows, no feasible algorithm can use fewer VNF instances than a conservative solution.The proof bounds total flow demand in the subtree against the capacity of all but at most one instance.Source: B. Main Result: Optimality · p. 8
• The proof removes breaking-point external flows iteratively, then removes subtrees bottom-up; removing external flows does not reduce GFT's instance count within those subtrees.The process scans breaking points from root to leaves, including newly created ones.Source: B. Main Result: Optimality · pp. 8–9
• GFT's time complexity is O(n + m log n).The two algorithm steps cost O(m log n) and O(n + m log n), respectively.Source: B. Main Result: Optimality · p. 9

Simulation setup

• The simulations use random and InternetMCI topologies, compare against GLPK-computed optima, and vary path lengths, flow rates, and flow counts.The random topology has 40 nodes and 234 links; each VNF instance has processing capacity R = 10.Source: §VI · p. 10

Impact of path length

• Longer average paths reduce the number of VNF instances, especially for small-rate flows, because more flows can intersect and share processing.Short, medium, and long path lengths are sampled from [1, n/10], [1, n/4], and [1, n/2] hops, respectively.Source: §VI · p. 10

Impact of flow rate

• For large flow rates, the greedy solutions are very close to the optimal solution, with approximation ratios close to 1.The large-rate setting uses rates uniformly distributed in [0, 10R]; the passage attributes the near-1 ratio to solution density typically exceeding 10.Source: §VI · pp. 10–11

Impact of topology complexity

• On sparse InternetMCI, the greedy algorithms’ performance gap from the optimum is smaller because the smaller, sparser network leaves less room for optimization.The simulation results are shown in Fig. 5, and the topology is shown in Fig. 6.Source: §VI · p. 11, Figure 5 · p. 11, Figure 6 · p. 11

Number of nodes used to host VNF instances

• In most considered cases, the greedy algorithms use fewer hosting nodes than the optimal solution; with 400 large-rate flows, the optimum uses almost twice as many.The paper notes that the optimal solution’s performance improvement is less than 4% despite its greater complexity.Source: §VI · pp. 11–12, Figure 7 · p. 11

• The paper proves the joint placement and allocation problem NP-hard, proposes two asymptotically optimal greedy algorithms for general topologies, and gives an optimal greedy algorithm for tree topologies.The conclusion says simulations elucidate the theoretical analyses.Source: §VII · p. 12
• The study assumes fixed flow routes and a single network function; joint placement and routing, and service function chaining, remain for future work.Source: §VII · p. 12