A decomposition approach for large virtual network embedding
summary
The gist
Virtual Network Embedding (VNE) is the core combinatorial problem of Network Slicing, a 5G technology which enables telecommunication operators to propose diverse service-dedicated virtual networks…
In short
The paper addresses Virtual Network Embedding (VNE), a complex problem in 5G network slicing, which involves mapping virtual networks onto a substrate network. They introduce an integer linear formulation based on an automatic partition of the virtual network to improve lower bounds using column generation. This leads to a decomposition scheme and a refined Price-and-Branch heuristic that finds high-quality solutions for large instances.
Key concepts
- Virtual Network Embedding (VNE)
- VNE is the core problem of 5G network slicing, which is finding the minimum cost way to place virtual network nodes and route virtual edges onto a shared physical substrate network. It determines how a desired service can be realized using existing infrastructure.
- Integer Linear Formulation (ILF)
- This is a mathematical model used to define the VNE problem precisely, ensuring that all decisions—like where to place nodes and how to route edges—are represented by integer variables. This formulation is crucial for creating strong lower bounds and guiding the optimization process.
- Column Generation
- This is an algorithmic technique used to solve large optimization problems by iteratively generating only the most promising solutions (columns) rather than checking every possibility. In this context, it helps find good lower bounds by solving pricing problems that are themselves VNE subproblems.
Terminology used across episodes
This episode discusses
- A decomposition approach for large virtual network embedding · Paper Radio
- Complexity of the Virtual Network Embedding with uniform demands
The paper
A decomposition approach for large virtual network embedding · Read on arXiv
Amal Benhamiche, Pierre Fouilhoux, Lucas Létocart, Nancy Perrot, Alexis Schneider
Orange Research · Laboratoire d’Informatique de Paris Nord, LIPN, CNRS
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "A decomposition approach for large virtual network embedding".
Jane: Here's the gist of the paper. Virtual Network Embedding (VNE) is the core combinatorial problem of Network Slicing, a 5G technology which enables telecommunication operators to propose diverse service-dedicated virtual networks, embedded onto a common substrate network On a benchmark of large virtual networks with realistic topologies we compiled, the state-of-the art heuristics often provide expensive solutions, or even fail to find a solution when resources are sparse We introduce a new integer linear formulation together with a decomposition scheme based on an automatic partition of the virtual network This results in a column generation approach whose pricing problems are also VNE problems Finally, we devise an efficient Price-and-Branch heuristic for large instances.
Tom: Problem Definition and Formulation The Virtual Network Embedding Problem (VNE) is defined as finding a minimum cost embedding of a virtual network Gr on a substrate network Gs A mapping m = (mV, mE) of Gr on Gs is a pair of functions where mV: Vr → Vs is called the node placement and mE: Er → Ps, is called the edge routing The VNE can be formulated as finding the minimum cost embedding of Gr on Gs given demands d, capacities c, and costs w.
Jane: Decomposition Strategy The authors propose a decomposition approach based on an automatic partition of the virtual network to tackle large instances The main contributions include introducing the Virtual Partition Formulation, an integer linear formulation based on a tuned partition of the virtual network.
Tom: This approach allows to compute better lower bounds than state-of-the-art methods.
Title and authors: Jane: So we've talked about the title and authors, but let's really unpack what this paper, "A decomposition approach for large virtual network embedding," is trying to achieve in its core summary. What’s the actual problem they are solving?
Tom: They are focusing on Virtual Network Embedding, VNE, which is that minimum cost mapping of a virtual network onto a substrate network that involves both node placement and edge routing decisions <ref:2512.17414#pg1>. It's the central combinatorial problem for resource allocation in network slicing <ref:2512.17414#pg3>.
Lu: The paper sets up the VNE as finding a minimum cost embedding of a virtual network Gr on a substrate network Gs, given demands, capacities, and costs <ref:2512.17414#pg3>. It defines the mapping as two functions: one for node placement and one for edge routing <ref:2512.17414#pg3>.
Jane: And they immediately point out that this VNE problem is known to be NP-complete, even with simpler constraints like uniform demands and topological restrictions <ref:2512.17414#pg3>. This sets the stage for why we need a smarter approach than just brute force.
Tom: Their main contribution is introducing the Virtual Partition Formulation, which they build on a tuned partition of the virtual network, and this leads to an integer linear formulation <ref:2512.17414#pg3>.
Meng: So it's taking that NP-complete problem and turning it into something solvable using integer linear programming by breaking it down based on that partition structure <ref:2512.17414#pg3>. That sounds like a big shift in methodology.
Jane: Right, and this decomposition allows them to compute much better lower bounds because they can use a column generation approach, where the pricing problems are also VNE problems on smaller virtual subgraphs <ref:2512.17414#pg3>.
Lu: And this is key because it means that instead of just solving one huge problem, you can solve many smaller VNE problems iteratively to get a better estimate <ref:2512.17414#pg3>.
Tom: They also detail how they use these pricing problems to compute Lagrangian bounds, which are strong lower bounds using the virtual network's structure <ref:2512.17414#pg3>.
Jane: And finally, they put all this together with a heuristic called Price-and-Branch that uses column generation to find the actual embedding solution for large instances <ref:2512.17414#pg3>.
Meng: So in simple terms, it’s about using structured decomposition to turn a very hard mapping problem into a series of solvable subproblems, helping you get both a good estimate and an actual answer.
Tom: That’s the essence of the paper: structure the problem to make solving it tractable by breaking down the complexity <ref:2512.17414#pg3>.
Jane: And they show that this structured approach, combined with their heuristic refinement, yields results that are significantly better than what we see from state-of-the-art algorithms <ref:2512.17414#pg3>.
The paper's summary: Lu: Let's focus on the specific ways they improved the existing methods, because I want to know what the paper actually suggests that is new and better than what we already have in the literature <ref:2512.17414#pg3>.
Tom: The first major improvement is introducing the Virtual Partition Formulation itself, which is based on a tuned partition of the virtual network, and this formulation allows them to compute better lower bounds compared to previous methods <ref:2512.17414#pg3>.
Jane: So it’s not just a new way to state the problem; it's a fundamentally different way to model the constraints on node placement and routing <ref:2512.17414#pg3>.
Lu: Then they introduce the decomposition scheme, which allows them to compute better lower bounds by using column generation where their pricing problems are VNE problems on smaller virtual subgraphs <ref:2512.17414#pg3>.
Meng: What about the heuristic refinement? Is there something specific in that Price-and-Branch heuristic that is new, or are we just seeing an application of existing techniques applied differently?
Tom: The improvement there is that they identified issues in the columns produced by their procedure and proposed algorithmic fixes, specifically partitioning the substrate network into balanced subgraphs one <ref:2512.17414#pg2>.
Jane: And they also propose modifying the objective functions of those sub-pricers to incorporate an estimation of routing costs for edges that cross between these virtual cuts one <ref:2512.17414#pg2>.
Lu: This modification is clever because it helps ensure that the columns generated on a subgraph don't intersect with all the columns from other subgraphs, which makes the generation process much more efficient one <ref:2512.17414#pg2>.
Tom: So they are essentially making sure that their decomposition works well practically, not just theoretically, by tuning those structural parameters based on where they see bottlenecks in column production one <ref:2512.17414#pg2>.
Jane: It sounds like they moved beyond just a mathematical formulation and into the practical engineering of how to make the search process actually work efficiently for large instances.
The paper's improvements: Tom: So wrapping up this paper, the main takeaway is that by using a decomposition approach based on partitioning both networks, they can achieve better lower bounds and then use an efficient Price-and-Branch heuristic to find high-quality solutions for large virtual network embedding instances <ref:2512.17414#pg3>.
Jane: This structured method lets them get a good estimate early on, and then the refinement helps them actually land on a solution that is much better than what we have in the literature <ref:2512.17414#pg3>.
Lu: It’s about getting that trade-off between how much you partition versus how efficient those pricing problems end up being, which is a core insight here <ref:2512.17414#pg3>.
Meng: From an operational standpoint, the fact that this heuristic outperforms algorithms on large instances of the Internet Topology Zoo and SNDlib is good, especially with tight capacities where greedy approaches fail <ref:2512.17414#pg3>.
Tom: Yeah, so they developed a new integer linear programming formulation for VNE based on network partitioning and then an automatic decomposition scheme that lets you get better bounds before using their Price-and-Branch heuristic for large instances <ref:2512.17414#pg3>.
Jane: It really gives us a solid tool to think about how to handle those massive resource allocation problems in future network designs <ref:2512.17414#pg3>.
Lu: The next step is seeing if this decomposition strategy holds up when we move beyond these benchmark instances and into much more complex, real-world topologies <ref:2512.17414#pg3>.
Meng: I'm still focused on the deployment cost aspect, but for now, this paper shows a path forward for handling these large VNE problems systematically <ref:2512.17414#pg3>.
Conclusion: Tom: So we've seen how they took Virtual Network Embedding, VNE, which is that hard mapping problem for 5G networks, and they introduced this new integer linear formulation based on partitioning the virtual network <ref:2512.17414#pg3>.
Jane: Exactly. The naive question a listener might have is how do you even start modeling all that placement and routing simultaneously? And they tackle that by introducing this partition structure <ref:2512.17414#pg3>.
Lu: It’s a decomposition approach. They take the big virtual network, break it down into smaller parts, and solve the embedding problem on those pieces <ref:2512.17414#pg3>.
Meng: So what does that actually mean for me running things at scale? Does breaking it down make the computation faster or just more complex to set up?
Tom: It's supposed to let them compute much better lower bounds, which is a big deal because those bounds are usually weak with standard approaches <ref:2512.17414#pg3>.
Jane: They use column generation for this decomposition, and the pricing problems are actually smaller VNE problems themselves <ref:2512.17414#pg3>. That means they can get stronger estimates iteratively <ref:2512.17414#pg3>.
Lu: And then they refine their heuristic, the Price-and-Branch method, by partitioning the substrate network into balanced subgraphs <ref:2512.17414#pg3>. They also adjust the objective functions of those sub-pricers to estimate routing costs for edges crossing between those cuts <ref:2512.17414#pg3>.
Meng: If you’re shipping models, that sounds like it adds a lot of overhead in terms of setup time, but if it helps you get a feasible solution faster on large instances, I can see that <ref:2512.17414#pg3>.
Tom: And the results show this heuristic beats the state-of-the-art algorithms on all solved instances <ref:2512.17414#pg3>. They found solutions for instances up to one hundred nodes in their tests <ref:2512.17414#pg3>.
Jane: It’s really a big step because before this, greedy approaches just couldn't solve the tight capacity instances correctly <ref:2512.17414#pg3>. This paper shows how structure helps you find those better embeddings <ref:2512.17414#pg3>.
Lu: The main point is that they created a new integer linear programming formulation for Virtual Network Embedding, based on network partitioning, and an automatic decomposition scheme that balances the partition size with pricing problem efficiency <ref:2512.17414#pg3>.
Meng: So it’s not just a theoretical improvement; it’s practical because they devised a way to get actual solutions for massive virtual networks, which is what I need to deploy things reliably <ref:2512.17414#pg3>.
Tom: It really is about structuring the problem so that you get better bounds first and then you have an efficient heuristic to find the actual embedding, which means we can actually build these virtual networks <ref:2512.17414#pg3>.
Jane: This work shows a clear path for how we can handle these huge resource allocation problems in future network designs <ref:2512.17414#pg3>.
Tom: That’s it for today on "A decomposition approach for large virtual network embedding". Next week, we’re looking at how LLM coding agents are using test generation to improve their performance <ref:2512.17414#pg56>
More episodes
- 2505.16254-Human-AI Writing as Distributed Cognition: Reassessing Collaborative Writing Theories in the Age of LLMs
- 2506.10913-Choreographic Quick Changes: First-Class Location (Set) Polymorphism
- 2507.14812-A Black-Box Approach for Exogenous Replenishment in Online Resource Allocation
- 2507.15448-Frames over finite fields with respect to the Galois inner product and their connections to self-orthogonal and LCD codes
- 2508.21572-NewsReX: An Open-Source Multi-Framework for Neural News Recommendation
- 2509.17028-Impact of Packetization on Network Calculus Analysis
- 2510.17342-AoA Services in 5G Networks: A Framework for Real-World Implementation and Systematic Testing
- 2511.04088-Efficient and rate-optimal list-decoding in the presence of minimal feedback
- 2511.17264-Notes on Stack Machines and Quantum Stack Machines
- 2601.15318-On the closest balanced game