International audience

Online learning algorithms have been successfully used to design caching policies with sublinear regret in the total number of requests, with no statistical assumption about the request sequence. Most existing algorithms involve computationally expensive operations and require knowledge of all past requests. However, this may not be feasible in practical scenarios such asfemtocaching, where a base station (BS) jointly decides the content of many edge caches and visibility of all requests at the BS requires constant communication between these caches and the BS. To capture this constraint, we study a single cache problem under a more restrictive setting, that we refer to as the Bernoulli Partial Observability (BPO) model, in which the caching policy only observes a request with probability$p$, reflecting the fraction of requests forwarded from the edge caches to the BS in thefemtocachingexample. We propose a policy, based on the classic online learning algorithm Follow-the-Perturbed-Leader (FPL), that achieves an asymptotically optimal regret bound of$\mathcal {O}(\sqrt {CT/p})$under BPO in$\mathcal {O}(1)$amortized time complexity as$T$goes to infinity, where$C$is the cache size and$T$is the number of requests. Moreover, we show that our policy extends to bipartite caching albeit with a sublinear$\alpha $-regret for$\alpha =1-1/e$and a higher computational cost. The experimental evaluation compares the proposed solution with classic caching policies and validates the proposed approach using both synthetic and real-world request traces.

Software-Defined Networking (SDN) is a networking paradigm that decouples the forwarding plane from the control plane. The orchestration of the control plane is a critical challenge in SDN deployment, addressed by the Controller Placement Problem (CPP). At the same time, securing the control plane is another major concern, as controllers are primary targets for attacks. To address this, mechanisms such as consensus protocols are implemented. However, these mechanisms introduce additional costs, such as increased controller response time, which can render them unsuitable for delay-sensitive applications. This work introduces the concept of integrating security constraints into the CPP to analyze the impact of such mechanisms on network performance, particularly in terms of response time. As a case study, a consensus mechanism is examined, and an efficient algorithm is proposed to optimize the problem. The proposed algorithm is compared against a solver-generated solution on the real network topology GEANT. Results demonstrate that the proposed algorithm is time-efficient and with a gap of at most 10% compared to the optimal one. It permits to analyze the trade-off and show that it is possible to implement security mechanisms, such as consensus, at the control plane level and still meet performance constraints for delay-sensitive applications, provided that a certain level of security is accepted.

Monitoring the quality of streaming video applications is important for Internet service providers (ISPs) to detect network issues and facilitate capacity planning. Machine Learning (ML) inference models have emerged as an effective solution to determine service quality using network traffic. However, while much focus has been on enhancing model performance, little attention has been given to deploying these models across entire networks. This paper introduces a new placement approach of quality inference models and their associated tasks to enhance the monitoring of video streaming applications over an entire mobile traffic network. Starting from the observation that inference tasks require the deployment of multiple components to, first, calculate input features from raw traffic, and then execute the inference models, we define the placement problem as an integer programming problem and, given its NP-hardness, we provide a heuristic solution, experimentally close to the optimum, based on the relaxation and the rounding of fractional solutions. We highlight that decoupling these components for the inference of network traffic can be beneficial in terms of total accuracy of the ML inference tasks. Finally, we experimentally show that our solution outperforms state-of-the-art placement techniques by ~30% of accuracy of the deployed inference models.

Edge-based live video analytics are a promising approach to reduce bandwidth overheads caused by the transmission of raw video streams to the cloud. However, the limited resources available on edge devices make it challenging to successfully process video streams in real-time. This gets further exacerbated when attempting to process video streams from mobile cameras. While mobile cameras are a desirable source of information, thanks to them being in the right place at the right time, they are inherently dynamic and unpredictable. To address these challenges, we propose VideoJam, a decentralized load balancing solution for live video analytics. VideoJam uses a set of load balancers to balance incoming video traffic across replicas without the need of centralized coordination. Exploiting the inherent load dynamicity generated by different video sources, VideoJam predicts the incoming load for each processing component and offloads excessive traffic to less-loaded neighbors. Further, VideoJam operates independently of deployed configurations and cameras present in the system, dynamically adapting to handle load changes and balance video traffic across available resources. Our evaluation shows that VideoJam can adapt to different mixes of mobile and fixed cameras, as well as quickly adapting to configuration changes occurring at runtime. Compared to state-of-the-art solutions, VideoJam achieves 2.91× lower response time, while reducing video data loss by more than 4.64× and generating lower bandwidth overheads.

In Federated Learning (FL), devices– also referred to as clients– can exhibit heterogeneous availability patterns, often correlated over time and with other clients. This paper addresses the problem of heterogeneous and correlated client availability in FL. Our theoretical analysis is the first to demonstrate the negative impact of correlation on FL algorithms’ convergence rate and highlights a trade-off between optimization error (related to convergence speed) and bias error (indicative of model quality). To optimize this trade-off, we propose Correlation-Aware FL (CA-Fed), a novel algorithm that dynamically balances the competing objectives of fast convergence and minimal model bias.CA-Fedachieves this by dynamically adjusting the aggregation weight assigned to each client and selectively excluding clients with high temporal correlation and low availability. Experimental evaluations on diverse datasets demonstrate the effectiveness ofCA-Fedcompared to state-of-the-art methods. Specifically,CA-Fedachieves the best trade-off between training time and test accuracy. By dynamically handling clients with high temporal correlation and low availability,CA-Fedemerges as a promising solution to mitigate the detrimental impact of correlated client availability in FL.

In this paper we study online caching problems where predictions of future requests, e.g., provided by a machine learning model, are available. Typical online optimistic policies are based on the Follow-The-Regularized-Leader algorithm and have higher computational cost than classic ones like LFU, LRU, as each update of the cache state requires to solve a constrained optimization problem. In this work we analysed the behaviour of two different optimistic policies in a batched case, i.e., when the cache is updated less frequently in order to amortize the update cost over time or over multiple requests. Experimental results show that such an optimistic batched approach outperforms classical caching policies both on stationary and real traces.

The enormous amount of data produced by mobile and IoT devices has motivated the development of federated learning (FL), a framework allowing such devices (or clients) to collaboratively train machine learning models without sharing their local data. FL algorithms (like FedAvg) iteratively aggregate model updates computed by clients on their own datasets. Clients may exhibit different levels of participation, often correlated over time and with other clients. This paper presents the first convergence analysis for a FedAvg-like FL algorithm under heterogeneous and correlated client availability. Our analysis highlights how correlation adversely affects the algorithm’s convergence rate and how the aggregation strategy can alleviate this effect at the cost of steering training toward a biased model. Guided by the theoretical analysis, we propose CA-Fed, a new FL algorithm that tries to balance the conflicting goals of maximizing convergence speed and minimizing model bias. To this purpose, CA-Fed dynamically adapts the weight given to each client and may ignore clients with low availability and large correlation. Our experimental results show that CA-Fed achieves higher time-average accuracy and a lower standard deviation than state-of-the-art AdaFed and F3AST, both on synthetic and real datasets.

The use of virtualization techniques, such as containerization, is rapidly changing how the deployment of applications is performed at the network edge. Indeed, container images enable fast instantiation and small footprint. However, although having smaller size than VMs virtual disks, container images continue to have hundreds of megabytes and can take several seconds to be downloaded in an edge node. In fact, the heterogeneity and resource-constrained infrastructure, typical of an edge computing scenario, can also increase this latency, by the several bottlenecks that may occur on the network topology. We advocate that the use of well-positioned container registries on the topology can significantly improve the deployment process. To prove that, in this paper we focus our analysis on the network requirements of large amounts of container deployments, and the impact generated on two distinct edge topologies. We also present a new registries placement solution based on a fluid communities algorithm. We validated our proposal using simulation and results show that it validates the model and generality of the proposed solution, showing enhanced performance even with biased schedulers with large amounts of deployments in a concentrated set of nodes.

Fog computing promises to extend cloud computing to match emerging demands for low latency, location-awareness and dynamic computation. It thus brings data processing close to the edge of the network by leveraging on devices with different computational characteristics. However, the heterogeneity, the geographical distribution, and the data-intensive profiles of IoT deployments render the placement of fog applications a fundamental problem to guarantee target performance figures. This is a core challenge for fog computing providers to offer fog infrastructure as a service, while satisfying the requirements of this new class of microservices-based applications. In this article we root our analysis on the throughput requirements of the applications while exploiting offloading towards different regions. The resulting resource allocation problem is developed for a fog-native application architecture based on containerised microservice modules. An algorithmic solution is designed to optimise the placement of applications modules either in cloud or in fog. Finally, the overall solution consists of two cascaded algorithms. The first one performs a throughput-oriented partitioning of fog application modules. The second one rules the orchestration of applications over a region-based infrastructure. Extensive numerical experiments validate the performance of the overall scheme and confirm that it outperforms state-of-the-art solutions adapted to our context.