Temporal Hyperbolic Graph Representation Learning for Scale-Free Internet Routing and Delay Prediction

Riepilogo Tecnico: HERMIT – Apprendimento di Rappresentazioni di Grafi Iperbolici Temporali per il Routing Internet Senza Scala e la Previsione della Latenza

Enunciato del Problema
Prevedere con precisione il Tempo di Andata e Ritorno (RTT) di Internet è essenziale per l'ottimizzazione del routing, la Qualità del Servizio (QoS) e l'ingegneria del traffico. Tuttavia, la previsione dell'RTT affronta tre sfide principali:

1. Distribuzioni a Coda Pesante: I dati RTT mostrano una variabilità estrema, che va da frazioni di millisecondo a diversi secondi, causando modelli di regressione tradizionali basati sull'Errore Quadratico Medio (MSE) di essere dominati dai valori anomali e di degradare le prestazioni sui range di latenza comuni.
2. Topologia Dinamica: L'RTT è influenzato da percorsi di instradamento in evoluzione, stati di congestione e cambiamenti nella topologia di rete, che sono difficili da catturare con embedding di distanza statici o modelli di regressione convenzionali.
3. Disallineamento Strutturale: La maggior parte delle Reti Neurali su Grafi Temporali (TGNN) esistenti opera in uno spazio euclideo. Questo è inadatto per i grafi di routing Internet, che possiedono strutture gerarchiche e senza scala. Gli embedding euclidei spesso richiedono dimensioni elevate o subiscono distorsioni geometriche per rappresentare queste topologie, mentre la geometria iperbolica si adatta naturalmente a tali strutture con bassa distorsione in dimensioni ridotte.

Metodologia: Il Framework HERMIT
Gli autori propongono HERMIT (Hyperbolic Edge-aware RTT modeling via Integrated Topology), un framework ibrido progettato per eseguire congiuntamente la previsione dei collegamenti e la previsione dell'RTT. L'architettura integra una GNN temporale che preserva la varietà iperbolica con un regressore Random Forest basato su alberi.

• Preprocessing dei Dati: Il modello utilizza un dataset di 10 anni (2015–2024) proveniente dal progetto CAIDA IPv4 Ark. I log grezzi di traceroute vengono puliti (mantenendo solo le tracce "completate"), potati ai primi 5% dei nodi per grado per focalizzarsi sull'infrastruttura di rete principale, e campionati tramite una strategia settimanale scorrevole (3 giorni/settimana) per gestire il carico computazionale. I dati risultanti sono strutturati come una sequenza di grafi ponderati giornalieri con caratteristiche degli archi che includono la media dell'RTT trasformata in logaritmo, la deviazione standard dell'RTT e il peso del collegamento.
• Encoder Temporale Iperbolico: Basandosi sulla struttura portante HMPTGN, HERMIT introduce due miglioramenti chiave:
  1. Caratteristiche degli Archi Consapevoli dell'RTT: Vengono incorporate caratteristiche esplicite degli archi (media log-RTT, deviazione standard e peso) per caratterizzare stati di collegamento a grana fine.
  2. Encoder degli Archi Apprendibile: Una trasformazione lineare seguita da un'attivazione sigmoide comprime le caratteristiche degli archi 3D in un peso scalare. Questo agisce come un meccanismo di attenzione, pesando adattivamente gli archi durante il passaggio dei messaggi per enfatizzare i collegamenti critici e stabili.
  3. Preservazione della Varietà: L'encoder esegue il passaggio dei messaggi direttamente sulla varietà della sfera di Poincaré (curvatura $c=1.0$) utilizzando l'addizione di Möbius e trasformazioni lineari di Poincaré, evitando la distorsione geometrica associata alle proiezioni nello spazio tangente utilizzate in modelli come HTGN.
• Compiti di Previsione Congiunta:
  • Previsione dei Collegamenti: Il modello calcola la distanza quadrata di Poincaré tra gli embedding dei nodi e la mappa sulle probabilità di esistenza del collegamento utilizzando una funzione di attivazione di Fermi-Dirac.
  • Previsione dell'RTT: Gli embedding dei nodi iperbolici ($z_u, z_v$) vengono concatenati con le statistiche storiche dell'RTT ($f_u, f_v$) per gli estremi dell'arco. Questo vettore di caratteristiche combinato viene immesso in un regressore Random Forest per prevedere l'RTT. Il modello è addestrato su valori RTT trasformati in logaritmo e normalizzati min-max per gestire le code pesanti, con le previsioni inverse-trasformate alla scala dei millisecondi per la valutazione.
• Obiettivo di Addestramento: Il modello è ottimizzato utilizzando una funzione di perdita combinata $L = L_{link} + \lambda L_{RTT}$, dove $L_{link}$ è la cross-entropia binaria e $L_{RTT}$ è l'MSE sui valori normalizzati. L'iperparametro di ponderazione $\lambda$ è impostato a 10.

Contributi Chiave

1. Pipeline Riproducibile: Una pipeline di preprocessing dei dati che trasforma i log grezzi CAIDA Ark in una sequenza di grafi ponderati giornalieri con statistiche RTT a livello di arco, affrontando le incoerenze dei dati comuni nelle misurazioni di traceroute.
2. Architettura Ibrida (HERMIT): Un framework innovativo che combina una GNN temporale iperbolica con un regressore Random Forest. È stato valutato su un dataset massivo e reale che copre un decennio.
3. Miglioramenti delle Prestazioni:
   • Previsione dell'RTT: HERMIT ottiene un miglioramento del 6% nell'RMSE rispetto a una forte baseline Random Forest che utilizza solo statistiche storiche. Nello specifico, migliora l'RMSE del 6,4% sui collegamenti esistenti e del 2,3% sui nuovi collegamenti apparsi.
   • Previsione dei Collegamenti: Incorporando caratteristiche esplicite degli archi e un encoder degli archi apprendibile, HERMIT supera le precedenti baseline TGNN iperboliche (HMPTGN e HTGN), ottenendo punteggi AUC e AP superiori a 0,99 sia sui collegamenti esistenti che su quelli nuovi.
4. Scalabilità: L'approccio dimostra che embedding iperbolici a 16 dimensioni possono codificare efficientemente strutture di routing gerarchiche, offrendo una soluzione scalabile per reti su larga scala.

Risultati e Significato
La carta afferma che HERMIT fornisce una soluzione robusta e scalabile per la previsione dell'RTT in condizioni di latenza di rete reali e a coda pesante. I risultati sperimentali sul dataset CAIDA dimostrano che:

• Gestione delle Code Pesanti: Il design ibrido mitiga efficacemente gli errori elevati sui campioni a coda pesante, superando i modelli che si affidano esclusivamente a statistiche storiche o embedding euclidei.
• Generalizzazione: Il modello mostra una forte generalizzazione verso connessioni precedentemente non viste (nuovi collegamenti), suggerendo che le rappresentazioni temporali iperboliche apprese catturano strutture gerarchiche latenti che aiutano nell'inferire connessioni di rete emergenti.
• Sinergia: La combinazione dell'organizzazione di rete a livello macro (catturata dall'encoder iperbolico) e delle interazioni di caratteristiche a livello micro (sfruttate dal Random Forest) produce previsioni più accurate e robuste rispetto a ciascun approccio da solo.

Gli autori concludono che incorporare la modellazione degli archi consapevole dell'RTT nei grafi temporali iperbolici migliora significativamente sia la previsione dei collegamenti che quella della latenza, offrendo un percorso pratico per l'ingegneria del traffico consapevole della latenza e il monitoraggio proattivo delle prestazioni.