MILP-based optimization and heuristics for virtual function placement in in-network federated learning systems

In recent years, Machine Learning has gained significant importance in addressing the problem of real-time network monitoring. However, latency and privacy requirements have led to the introduction of a novel paradigm: Federated Learning. In this approach, a set of clients performs training on local data subsets and sends the model parameters to a central server, which aggregates them and returns the updated parameters to the clients. This mechanism ensures data privacy, as no raw data is shared, and reduces latency by distributing the training process over smaller data portions in parallel. Artificial Intelligent Functions can effectively act as clients in a Federated Learning framework. Since telecommunication networks require continuous monitoring, real-time data reflecting the system’s status must be processed efficiently, making Federated Learning a promising solution. To meet real-time requirements, it is essential to optimize function location and the path followed from Data Source to Artificial Intelligent Functions. This thesis addresses the problem of building a chain of virtual functions to pre-process monitoring data generated at Data Sources before Artificial Intelligent Function training. The three virtual functions are responsible for queuing and pre-processing the data and their position among the nodes of the network must be decided. The goal is to guarantee a suitable latency by minimizing the chain time from Data Sources to Artificial Intelligent Functions. Further, an even workload among Artificial Intelligent Functions must be guaranteed by balancing data arrivals. We propose Mixed Integer Linear Programming models to place the virtual functions, while satisfying network and real-time constraints. A strengthened version of the models is also presented, which includes an inequality based on the lower bound. In addition, we design and test several heuristic schemes to improve the solution: a Randomized Rounding used as warm start and three variants of the k-opt neighbourhood search. We consider three realistic scenarios based on the distribution of computing resources, the network coverage area, and the type of technology involved. Experimental results show that the enriched models can reach optimality for a number of Data Sources aligned with real-world demands, within a reasonable time limit. By combining the two objective functions the models are able to balance the workload among the Artificial Intelligent Functions while slightly increasing the chain time value.

Negli ultimi anni, il Machine Learning ha acquisito un'importanza significativa nella risoluzione del problema del monitoraggio in tempo reale delle reti di telecomunicazioni. Tuttavia, i requisiti legati alla latenza e alla privacy hanno portato all’introduzione di un nuovo paradigma: il Federated Learning. In questo approccio, un insieme di clients esegue l’addestramento su sottoinsiemi locali di dati e invia i parametri del modello a un server centrale, che li aggrega e restituisce i parametri aggiornati ai client. Questo meccanismo garantisce la privacy dei dati, poiché nessun dato grezzo viene condiviso, e riduce la latenza distribuendo in parallelo l’addestramento su porzioni di dati più piccole. Le Artificial Intelligent Functions possono agire efficacemente come client all’interno di un contesto di Federated Learning. Poiché le reti di telecomunicazione richiedono un monitoraggio continuo, è necessario elaborare in modo efficiente dati che riflettano lo stato del sistema in tempo reale, il Federated Learning rappresenta una soluzione promettente. Per soddisfare i vincoli di real-time, è fondamentale ottimizzare sia la posizione delle funzioni virtuali sia il percorso seguito dai dati dalla sorgente fino alle Artificial Intelligent Functions. Questa tesi affronta il problema della costruzione di una catena di funzioni virtuali per il pre-processing dei dati di monitoraggio generati dalle Data Sources, prima dell’addestramento nelle Artificial Intelligent Function. Le tre funzioni virtuali sono responsabili dell’accodamento e del pre-processing, e la loro posizione all’interno della rete deve essere opportunamente scelta. L’obiettivo è garantire una latenza adeguata minimizzando il chain time, ovvero il tempo di attraversamento della catena dalle Data Sources alle Artificial Intelligent Functions. Inoltre, è necessario garantire un carico di lavoro bilanciato tra le Artificial Intelligent Function, distribuendo equamente l’arrivo dei dati. La tesi propone modelli di Programmazione Lineare Intera Mista per posizionare le funzioni virtuali, rispettando i vincoli di rete e di tempo. Viene anche presentata una versione rafforzata dei modelli, che includono una disuguaglianza basata su una miglior valutazione del lower bound. Inoltre, alcuni schemi euristici, tra cui un Randomized Rounding usato come warm start e tre varianti della ricerca locale k-opt, sono stati sviluppati e testati per migliorare la qualità delle soluzioni. Nelle prove computazionali sono stati considerati tre scenari realistici che dipendono dalla distribuzione delle risorse computazionali, l’area coperta dalla rete e il tipo di tecnologia impiegata. I risultati ottenuti mostrano che il modello rafforzato è in grado di raggiungere l’ottimalità per un numero di Data Sources coerente con le esigenze reali entro un limite di tempo ragionevole. Quando si combinano le due funzioni obiettivo, si osserva che i modelli riescono a bilanciare il carico di lavoro tra le Artificial Intelligent Functions con un leggero aumento del valore del chain time.