Submodularity of the placement value function in multi-dimensional VNF placement and resource allocation (multi-VPRA)

In the multi-VPRA problem of Sallam, Zheng, and Ji (ICNP 2019; IEEE TMC 2023), an Internet service provider with a deployment budget chooses at most $k$ network nodes to become NFV-enabled (VNF-nodes) and allocates their multiple resource types to network flows so as to maximize fully processed traffic. The paper solves the problem through a two-level relaxation precisely because the submodularity of the first-level-relaxed placement value function $R_3(\mathcal{U})$ — the optimal value of a multi-resource allocation linear program (LP) over the set $\mathcal{U}$ of available VNF-nodes — is unknown: the authors conjecture that $R_3$ is submodular but do not prove it, and their second-level (sequence-based) relaxation, which restores tractable analysis, loses a factor of $1/2$. This problem asks to prove or refute the conjecture: determine whether $R_3$ is submodular over subsets of nodes for all multi-VPRA instances. A proof would let submodular-greedy placement carry the $(1-1/e)$ guarantee and would show the factor-losing second-level relaxation unnecessary; a refutation would close the gap in the paper's simulation-only submodular-greedy heuristics and justify the two-level relaxation as essential. The conjecture has remained open since it was posed in 2019.

Background

Network function virtualization (NFV) is a design paradigm in which network functions that traditionally ran on dedicated hardware middleboxes (e.g., firewalls, intrusion detection systems, load balancers) are implemented as software modules, called virtual network functions (VNFs), running on general-purpose commodity servers; a network node hosting such modules is called a VNF-node. Sallam, Zheng, and Ji studied the planning-phase question an Internet service provider (ISP) faces when transitioning to NFV under a limited budget: given a network graph, a set of flows with predetermined routing paths and traffic rates, a required set of network functions for each flow, per-node capacities for several resource types (e.g., CPU, memory, and I/O), and a budget that translates into a cardinality constraint $|\mathcal{U}|\le k$ on the chosen VNF-node set $\mathcal{U}$, select $\mathcal{U}$ and allocate the nodes' resources to flows so that the total traffic rate of fully processed flows is maximized. They call this the multi-dimensional VNF placement and resource allocation problem (multi-VPRA). A flow counts toward the objective only if its entire rate is processed (the fully processed requirement); its traffic may be split across the VNF-nodes on its path, and processing one unit of flow by function $\phi$ consumes $\beta_\phi^r$ units of resource $r$ at the hosting node.

The problem is NP-hard, and its objective is non-submodular — a set function $g$ is submodular when $g(A)+g(B)\ge g(A\cup B)+g(A\cap B)$ for all sets $A,B$, the diminishing-returns property that makes greedy selection algorithms provably near-optimal. These difficulties were already present in the one-dimensional predecessor of Sallam and Ji (IEEE/ACM Transactions on Networking, 2021), where all flows require a single network function consuming one unit of a single resource. There, a relaxation that awards partial credit for partially processed flows turns the placement value function into a maximum-flow value, which is submodular, enabling greedy placement with a $(1-1/e)$ approximation ratio (an algorithm's approximation ratio bounds its objective value relative to the optimum).

In the multi-dimensional setting this route breaks. After the same first-level (partial-credit) relaxation, the resource-allocation subproblem for an available node set $\mathcal{U}$ becomes a multi-dimensional generalization of the generalized assignment problem (the classical problem of packing items into capacity-limited bins, where each item's profit and resource consumption depend on its assigned bin) with assignment restrictions (each flow may only use nodes on its own path), expressible as a linear program (LP); its optimal value defines the placement value function

$$R_3(\mathcal{U}) \triangleq \max \ \sum_{f\in\mathcal{F}} \sum_{v\in\mathcal{V}_f\cap\mathcal{U}} x_f^v$$

subject to the per-node multi-resource constraints $\sum_{\phi\in\Phi}\beta_\phi^r \sum_{f\in\mathcal{F}(\phi)} x_f^v \le c_v^r$ for every resource $r$ and node $v\in\mathcal{U}$, the per-flow rate caps $\sum_{v\in\mathcal{U}} x_f^v \le \lambda_f$, and $x_f^v = 0$ for $v\notin\mathcal{V}_f\cap\mathcal{U}$, where $\mathcal{V}_f$ is the set of nodes on flow $f$'s path, $\mathcal{F}(\phi)$ the set of flows requiring function $\phi$, and $x_f^v\ge 0$ the portion of flow $f$ assigned to node $v$. The authors state that, to their knowledge, $R_3$ can only be evaluated by LP, which provides no insight toward proving or disproving submodularity, and that its submodularity remains unknown; nevertheless, in their numerical section they conjecture that $R_3$ is submodular and build two simulation-only heuristics (submodular-greedy placement combined with their allocation algorithms) on this conjecture. Because submodularity was unavailable for analysis, they introduce a second-level relaxation: nodes are ordered and resources allocated one node at a time, yielding a sequence-based value $R_4$ that is sequence submodular (submodularity generalized to functions on ordered sequences, where the order of elements determines the value) but only a $1/2$-approximation of $R_3$ for any node ordering. Greedy over sequences combined with two primal-dual (a standard LP-duality-based algorithm design technique) allocation algorithms then yields provable approximation ratios for the original multi-VPRA problem, at the cost of the factor-$1/2$ loss from the second-level relaxation. Whether that loss is fundamentally necessary hinges exactly on the unresolved theoretical status of $R_3$.

Problem Statement

Determine whether the placement value function of the first-level-relaxed multi-VPRA problem is submodular, as conjectured by Sallam, Zheng, and Ji. Specifically, prove or refute the following statement: for every instance of the multi-VPRA model — a set of nodes $\mathcal{V}$ with resource capacities $c_v^r$ over resource types $r\in\mathcal{R}$, flows $f$ with rates $\lambda_f$, path node sets $\mathcal{V}_f$, required function sets $\Phi_f$, and per-unit resource demands $\beta_\phi^r$ (where $\Phi$ denotes the set of all network functions and $\mathcal{F}(\phi)\subseteq\mathcal{F}$ the set of flows requiring function $\phi$) — the set function

$$R_3(\mathcal{U}) \triangleq \max_{x\ge 0} \ \sum_{f\in\mathcal{F}} \sum_{v\in\mathcal{V}_f\cap\mathcal{U}} x_f^v$$

subject to $\sum_{\phi\in\Phi} \beta_\phi^r \sum_{f\in\mathcal{F}(\phi)} x_f^v \le c_v^r$ for all $r\in\mathcal{R}$ and $v\in\mathcal{U}$, $\sum_{v\in\mathcal{U}} x_f^v \le \lambda_f$ for all $f\in\mathcal{F}$, and $x_f^v = 0$ for $v\notin\mathcal{V}_f\cap\mathcal{U}$, satisfies the submodularity inequality

$$R_3(A) + R_3(B) \ge R_3(A\cup B) + R_3(A\cap B)$$

for all node subsets $A, B \subseteq \mathcal{V}$. A refutation consists of an explicit multi-VPRA instance and subsets $A, B$ for which the inequality is strictly violated; a proof must hold for all instances of the stated model, without artificial restrictions on the number of resource types, functions, flows, or network structure. Beyond the inequality itself, the answer determines whether the paper's factor-losing second-level relaxation is avoidable in principle, since monotone submodularity of $R_3$ would immediately give the $(1-1/e)$ submodular-greedy guarantee for the placement subproblem.

References

1. G. Sallam, Z. Zheng, and B. Ji, "Placement and Allocation of Virtual Network Functions: Multi-Dimensional Case," IEEE Transactions on Mobile Computing, vol. 22, no. 7, pp. 4195-4211, 2023. DOI: 10.1109/TMC.2022.3151908, https://doi.org/10.1109/TMC.2022.3151908 (arXiv:1910.06299, https://arxiv.org/abs/1910.06299)
2. G. Sallam, Z. Zheng, and B. Ji, "Placement and Allocation of Virtual Network Functions: Multi-dimensional Case," in Proc. IEEE 27th International Conference on Network Protocols (ICNP), 2019, pp. 1-11. DOI: 10.1109/ICNP.2019.8888148, https://doi.org/10.1109/ICNP.2019.8888148
3. G. Sallam and B. Ji, "Joint Placement and Allocation of VNF Nodes With Budget and Capacity Constraints," IEEE/ACM Transactions on Networking, vol. 29, no. 3, pp. 1238-1251, 2021. DOI: 10.1109/TNET.2021.3058378, https://doi.org/10.1109/TNET.2021.3058378 (arXiv:1901.03931, https://arxiv.org/abs/1901.03931)