Andrea Araldo

Amal Sakr, Andrea Araldo, Tijani Chahed et al.

Mobile Edge Computing (MEC) requires Network Operators (NOs) to undertake substantial infrastructure investments, while most revenues are captured by Service Providers (SPs) offering end-user applications. This cost-revenue imbalance discourages NOs from investing in MEC deployment, despite increasing demand for low-latency and bandwidth-intensive services. This paper proposes a co-investment scheme in which players, i.e., one NO and multiple SPs, jointly deploy, maintain, and share MEC infrastructure over multiple decision epochs. We devise a new coalitional game model that captures the planning of resources, their allocation among players, and cost and revenue sharing. To address fluctuating user demand and evolving participation incentives, we design a mechanism that updates resources and allows the dynamic entrance and exit of players over time. We sustain cooperation through a compensation scheme. Numerical results show that combining resource updates with dynamic participation increases the total payoff and strengthens the NO's incentive to invest.

Wei Huang, Richard Combes, Andrea Araldo et al.

We study the placement of virtual functions aimed at minimizing the cost. We propose a novel algorithm, using ideas based on multi-armed bandits. We prove that these algorithms learn the optimal placement policy rapidly, and their regret grows at a rate at most $O( N M \sqrt{T\ln T} )$ while respecting the feasibility constraints with high probability, where $T$ is total time slots, $M$ is the number of classes of function and $N$ is the number of computation nodes. We show through numerical experiments that the proposed algorithm both has good practical performance and modest computational complexity. We propose an acceleration technique that allows the algorithm to achieve good performance also in large networks where computational power is limited. Our experiments are fully reproducible, and the code is publicly available.

Duo Wang, Andrea Araldo, Mounim El Yacoubi

Designing a network (e.g., a telecommunication or transport network) is mainly done offline, in a planning phase, prior to the operation of the network. On the other hand, a massive effort has been devoted to characterizing dynamic networks, i.e., those that evolve over time. The novelty of this paper is that we introduce a method for the online design of dynamic networks. The need to do so emerges when a network needs to operate in a dynamic and stochastic environment. In this case, one may wish to build a network over time, on the fly, in order to react to the changes of the environment and to keep certain performance targets. We tackle this online design problem with a rolling horizon optimization based on Monte Carlo Tree Search. The potential of online network design is showcased for the design of a futuristic dynamic public transport network, where bus lines are constructed on the fly to better adapt to a stochastic user demand. In such a scenario, we compare our results with state-of-the-art dynamic vehicle routing problem (VRP) resolution methods, simulating requests from a New York City taxi dataset. Differently from classic VRP methods, that extend vehicle trajectories in isolation, our method enables us to build a structured network of line buses, where complex user journeys are possible, thus increasing system performance.

Duo Wang, Maximilien Chau, Andrea Araldo

Designing Public Transport (PT) networks able to satisfy mobility needs of people is essential to reduce the number of individual vehicles on the road, and thus pollution and congestion. Urban sustainability is thus tightly coupled to an efficient PT. Current approaches on Transport Network Design (TND) generally aim to optimize generalized cost, i.e., a unique number including operator and users' costs. Since we intend quality of PT as the capability of satisfying mobility needs, we focus instead on PT accessibility, i.e., the ease of reaching surrounding points of interest via PT. PT accessibility is generally unequally distributed in urban regions: suburbs generally suffer from poor PT accessibility, which condemns residents therein to be dependent on their private cars. We thus tackle the problem of designing bus lines so as to minimize the inequality in the geographical distribution of accessibility. We combine state-of-the-art Message Passing Neural Networks (MPNN) and Reinforcement Learning. We show the efficacy of our method against metaheuristics (classically used in TND) in a use case representing in simplified terms the city of Montreal.

Maxime Elkael, Massinissa Ait Aba, Andrea Araldo et al.

In this article, we consider the Virtual Network Embedding (VNE) problem for 5G networks slicing. This problem requires to allocate multiple Virtual Networks (VN) on a substrate virtualized physical network while maximizing among others, resource utilization, maximum number of placed VNs and network operator's benefit. We solve the online version of the problem where slices arrive over time. Inspired by the Nested Rollout Policy Adaptation (NRPA) algorithm, a variant of the well known Monte Carlo Tree Search (MCTS) that learns how to perform good simulations over time, we propose a new algorithm that we call Neighborhood Enhanced Policy Adaptation (NEPA). The key feature of our algorithm is to observe NRPA cannot exploit knowledge acquired in one branch of the state tree for another one which starts differently. NEPA learns by combining NRPA with Neighbordhood Search in a frugal manner which improves only promising solutions while keeping the running time low. We call this technique a monkey business because it comes down to jumping from one interesting branch to the other, similar to how monkeys jump from tree to tree instead of going down everytime. NEPA achieves better results in terms of acceptance ratio and revenue-to-cost ratio compared to other state-of-the-art algorithms, both on real and synthetic topologies.