Reservation of Virtualized Resources with Optimistic Online Learning

Jean-Baptiste Monteil, George Iosifidis, Ivana Dusparic

TL;DR

This paper introduces OOLR (Optimistic Online Learning for Reservation), a novel algorithm that helps service providers intelligently lease network "slices" in a volatile market. By incorporating a gradient prediction module (ARMA-OGD) into an online convex optimization framework, the authors achieve significantly lower costs and higher utility than standard methods, even when future demand and prices are highly unpredictable.

What Problem Does This Paper Address?

In the world of 5G and beyond, Network Slicing allows Service Providers (SPs)—like a streaming company or an autonomous vehicle fleet—to lease specific virtualized resources (bandwidth, CPU, storage) from a Network Operator (NO).

The challenge is that this market is "blind" and dynamic. An SP must decide how much capacity to reserve before knowing exactly how many users will show up or what the "spot price" of resources will be at that moment. Most existing solutions assume the environment is "stationary" (i.e., the math doesn't change over time), but real-world network traffic is notoriously non-stationary and messy. The SP needs a way to make real-time decisions that maximize service quality while minimizing leasing costs, without the luxury of perfect foresight.

Methods

The authors frame the reservation problem as Online Convex Optimization (OCO). Their core contribution is the OOLR algorithm, which builds upon the standard "Follow-the-Regularized-Leader" (FTRL) approach but adds an "optimistic" twist.

  • Optimistic FTRL: Unlike standard algorithms that only look at past performance, OOLR incorporates a prediction of the next time step’s gradient. If the prediction is accurate, the algorithm reacts much faster to emerging trends.
  • ARMA-OGD Prediction: To generate these "optimistic" guesses, they use an Auto-Regressive Moving Average model updated via Online Gradient Descent. This is a computationally "light" model that learns on the fly, requiring no expensive offline training phase.
  • Proximal Regularizers: The algorithm uses a sequence of quadratic regularizers that adapt based on the error of the predictions, ensuring the system remains stable even when predictions are off-base.

Datasets

The researchers evaluated their model using a mix of real-world and synthetic data to simulate a complex market:

  • Real-World Traffic: Aggregated traffic volumes from multiple base stations in Shanghai (provided by a major MNO), recorded over a one-month period in 10-minute intervals.
  • Synthetic Price/Utility Data: To simulate non-stationary market conditions, they modeled resource prices using an AR(1) process (specifically an Ornstein-Uhlenbeck process, common in financial math) and modeled resource "contributions" using seasonal sine waves with added stochastic noise.

Key Insights and Ideas

  • The "Best of Both Worlds" Guarantee: The most elegant part of OOLR is its mathematical safety net. If the predictions are perfect, the "regret" (the gap between the algorithm's performance and the best possible strategy in hindsight) is constant ($O(1)$). If the predictions are completely wrong, the algorithm gracefully degrades to the standard $O(\sqrt{T})$ performance. You gain a lot if you're right, but you don't lose extra if you're wrong.
  • Low Computational Overhead: Because the decision step and the prediction module both have low time complexity ($O(m^2)$ and $O(mq)$ respectively), the system can run in real-time at the network edge.
  • Handling "Partial Fulfillment": The paper accounts for the reality that a Network Operator might not always be able to provide 100% of a requested resource due to congestion. They show that OOLR remains robust even when the operator only meets a fraction (e.g., 80% or 50%) of the Service Level Agreement (SLA).

Key Results

  • Outperforming the Baseline: In numerical simulations, the OOLRgrad solution (the version using the ARMA-OGD predictor) consistently outperformed the standard FTRL baseline.
  • Tracking Non-Stationarity: The ARMA-OGD module successfully tracked intricate, non-stationary signals in the Shanghai traffic data, allowing the SP to "anticipate" demand spikes.
  • Negative Regret: Against a static benchmark, the optimistic model actually achieved "negative regret" in some scenarios, meaning it performed better than the best fixed strategy one could have chosen even with full knowledge of the past.

Limitations and Future Work

  • Strategic Competition: The current model focuses on a single SP interacting with a Network Operator. In a real market, multiple SPs would be competing for the same resources, potentially leading to game-theoretic behaviors that aren't fully explored here.
  • Prediction Limits: While ARMA-OGD is robust, it is still a linear-style predictor. Extremely chaotic or "black swan" events in network traffic might still challenge the "optimism" of the model.
  • Future Direction: The authors suggest that while they used ARMA-OGD for its low complexity and theoretical guarantees, more advanced (though computationally heavier) Neural Networks could be plugged into the OOLR framework to potentially further increase prediction accuracy.

Summary updated

Abstract

The virtualization of wireless networks enables new services to access network resources made available by the Network Operator (NO) through a Network Slicing market. The different service providers (SPs) have the opportunity to lease the network resources from the NO to constitute slices that address the demand of their specific network service. The goal of any SP is to maximize its service utility and minimize costs from leasing resources while facing uncertainties of the prices of the resources and the users' demand. In this paper, we propose a solution that allows the SP to decide its online reservation policy, which aims to maximize its service utility and minimize its cost of reservation simultaneously. We design the Optimistic Online Learning for Reservation (OOLR) solution, a decision algorithm built upon the Follow-the-Regularized Leader (FTRL), that incorporates key predictions to assist the decision-making process. Our solution achieves a $\mathcal{O}(\sqrt{T})$ regret bound where $T$ represents the horizon. We integrate a prediction model into the OOLR solution and we demonstrate through numerical results the efficacy of the combined models' solution against the FTRL baseline.
BibTeX
@inproceedings{monteil2023reservation,
  author = {Jean-Baptiste Monteil and George Iosifidis and Ivana Dusparic},
  title = {{Reservation of Virtualized Resources with Optimistic Online Learning}},
  booktitle = {ICC},
  year = {2023},
  url = {https://openreview.net/forum?id=8ncDhGOPSF},
}

Loading related content...

Figure