Edge computing is where latency matters most and every millisecond counts. It brings tiny data centers closer to people and devices, so games feel instant, augmented reality stays responsive, and smart devices react without waiting for a distant cloud. But the closer you sit to the action, the more you must juggle competing demands from a swarm of apps that want a slice of the same physical backbone. This is the essence of virtual network embedding VNE: you model each application as a mini network of functions and you map that virtual graph onto the real, capacity-limited substrate of edge nodes and links. The goal is to fit as many worthyEmbeddings as possible without overloading the hardware. It sounds straightforward, but it is a deep combinatorial puzzle that grows in difficulty as the number of requests scales up.
The paper behind this article comes from Technion Israel and IBM Research Israel, led by Oleg Kolosov with colleagues Gala Yadgar, David Breitgand, and Dean H. Lorenz. They tackle online VNE, where requests arrive one by one and the system must decide on the fly whether to accept and how to place them without knowing what comes next. In edge environments the demand can spike in bursts, so a solution must be not just clever but practical at scale. The researchers propose a plan based approach that blends offline planning with dynamic online adjustments, a combination they show can handle far higher request rates than previous methods while staying near optimal in cost.
What makes online VNE so hard
Think of the substrate as a fabric of datacenters connected by links, each with a finite amount of capacity and a price tag tied to energy and wear. Applications arrive as blueprints for virtual networks composed of VNFs and the links that tie them together. Embedding means assigning each virtual node to a real datacenter and routing each virtual link along a path in the substrate, all while never exceeding capacity and while the deployment lasts for a bounded time. The stubborn wrinkle is time: the demands come and go, and the system must keep room for new, possibly different requests even as old ones depart.
Then there is the scale and the variability. In edge networks you may be dealing with tens or hundreds of substrate nodes, and requests arriving at rates that can swamp the best-known algorithms. The problem is not just NP-hard in theory; in practice, a slow or unevenly performing embedding engine can stall services, ruin quality of experience, or waste energy. The online flavor is what trips up many offline solutions. Even if you could compute an optimal embedding for all requests up front, reality rarely cooperates—arrivals are bursty, durations vary, and the future is a moving target.
The OLIVE study places its bets on a simple, powerful idea: start with a carefully crafted embedding plan based on expected demand, then adapt as real demand arrives. The plan anchors decisions, but OLIVE is free to deviate and reallocate as needed when actual requests differ from what was anticipated. In other words, it blends a weather forecast with flexible rain checks that keep everything running smoothly when the sky changes. The promise is not theoretical elegance but real-world responsiveness at edge-scale rates that matter for next generation networks.
OLIVE and PLAN-VNE: turn plan into action
The authors break the problem into three steps that build a bridge from offline planning to online execution. The first step uses a history of requests to build a time aggregated set of demands. Rather than modeling each past request separately, they group requests by application type and user location and compute a peak demand profile for each class. This aggregated view, which they call the time aggregated set, drives the offline planning process. The key move is to treat the aggregated demand as a relaxed, splittable quantity that can be embedded in fractional form to yield a global plan. The offline plan is not a rigid blueprint; it is a guide with guaranteed shares of capacity for each request class, even before the system sees any new arrival.
The second step is PLAN-VNE, a novel offline linear program that computes the embedding plan for the aggregated demand. The plan is splittable, meaning it can assign fractions of an aggregated demand across substrate elements. This fractional planning makes the math tractable and the results scalable, producing a plan y that pinpoints where capacity should be allocated for the expected demand. A clever twist is the use of quantiles to manage rejection costs. The plan does not just try to fit everything; it assigns a structured penalty to the portion of any aggregated class that is rejected. By distributing potential rejections across quantiles, the plan avoids starving any one class of requests, preserving fairness and enabling more predictable behavior when new arrivals come in.
The third step is the online embedding that actually handles arrivals in real time. OLIVE uses the offline plan as a guide, checking whether each incoming request r can be embedded according to the residual capacity left by the plan. If there is room, the system marks the request as planned and allocates it along the plan’s suggested path. If capacity is tight, OLIVE borrows unused capacity from other underutilized classes to accommodate the new demand. When borrowing would tip the scales against other planned embeddings, it can preempt those borrowed allocations to free resources for the new arrival. If a request cannot be accommodated within the plan and borrowed adjustments, OLIVE falls back to a greedy, fast embedding that tries to map the request with minimal local cost, sometimes collocating VNFs to simplify the problem and reduce congestion on links.
All of this is encoded in a few compact ideas that the paper lays out with care. Residual capacity on the substrate is tracked for each time slot, and a parallel residual plan keeps track of how much of the plan is still available as requests come and go. The system distinguishes between allocations that follow the plan exactly and those that are non planned. In the latter case, borrowing and, if necessary, preemption keep the ensemble of embeddings balanced and prevents any single class from being starved when bursts hit. The overall objective remains cost based: minimize the total resource usage plus the penalty cost for rejections. The math is nontrivial, but the logic feels almost intuitive: plan for the expected, adapt for the actual, and do so in a way that treats different classes fairly as demand shifts.
Why this could reshape edge computing
What makes OLIVE exciting is not just that it can handle more requests per second, but that it does so with a philosophy that feels pragmatic and scalable. In their experiments, the authors show that the online plan based approach can sustain orders of magnitude higher request rates than the best previous online solutions. In simulations on realistic edge topologies and workloads, OLIVE halved rejection rates relative to the quickest greedy baselines and kept cost close to an ideal but intractable offline optimum. The numbers matter because edge environments face bursty workloads in real time when millions of devices and apps come alive at once. A method that can absorb those bursts without sacrificing performance is a meaningful upgrade over how things work today.
The study does not just claim speed. It emphasizes stability and fairness. By distributing rejection penalties across quantiles, the plan ensures that no single application class is permanently deprioritized during a burst. In their tests, this planning based approach yielded a higher fairness index than naive baselines, offering a more balanced allocation across diverse workloads. The result is not just fast embeddings; it is more predictable service for a broader set of apps, from lightweight IoT tasks to heavy duty augmented reality chains.
From a broader perspective, the work signals a practical path forward for edge networks as they scale toward 5G and beyond. The plan based method is inherently modular: the offline planner can be updated with new demand patterns, and the online engine can adjust on the fly without starting from scratch. That modularity matters when you think about the near future, where edge deployments will proliferate and the mix of applications will become ever more diverse. If you can plan for the expected, you gain a reliable backbone; if reality diverges, you have structured mechanisms to adapt without chaos.
One of the compelling future directions is to enrich the model with time dependent demand and more nuanced energy considerations. The current framework already accommodates (in)efficiency coefficients that influence how much substrate capacity a given VNF or link consumes. Extending this to account for dynamic energy pricing, cooling constraints, or even hardware accelerators could sharpen the planner’s ability to make greener, smarter choices under stress. The modular, plan driven approach makes such extensions tractable, which is perhaps the most valuable takeaway for practitioners thinking about real world deployments.
In the end, OLIVE is more than a clever trick for a single problem. It suggests a design pattern for complex, dynamic systems: build a robust plan from history, use it to guide real time decisions, and keep a disciplined set of fallback mechanisms that gracefully absorb the inevitable deviations. That combination—offline rigor plus online adaptability—feels like a practical recipe for the next wave of edge networks to stay fast, fair, and energy aware as bursts of demand become the new normal.
The study from Technion and IBM Research Israel highlights Oleg Kolosov as the lead author, with contributions from Gala Yadgar, David Breitgand, and Dean H. Lorenz. The work demonstrates that when you couple a near optimal offline plan with intelligent online corrections, you don’t just improve metrics—you change what is possible in edge scale and responsiveness. It is a reminder that sometimes the most powerful advances come not from a totally new algorithm but from a smarter way of blending planning and action, especially when reality refuses to follow your forecast.
