Network modeling using graph neural networks

Abstract

(English) Network modeling is central to the field of computer networks. Models are useful in researching new protocols and mechanisms, allowing administrators to estimate their performance before their actual deployment in production networks. Network models also help to find optimal network configurations, without the need to test them in production networks.

Arguably, the most prevalent way to build these network models is through the use of discrete event simulation (DES) methodologies which provide excellent accuracy. State-of-the-art network simulators include a wide range of network, transport, and routing protocols, and are able to simulate realistic scenarios. However, this comes at a very high computational cost that depends linearly on the number of packets being simulated. As a result, they are impractical in scenarios with realistic traffic volumes or large topologies. In addition, and because they are computationally expensive, they do not work well in real-time scenarios.

Another network modeling alternative is Queuing Theory (QT) where networks are represented as inter-connected queues that are evaluated analytically. While QT solves the main limitation of DES, it imposes strong assumptions on the packet arrival process, which typically do not hold in real networks.

In this context, Machine Learning (ML) has recently emerged as a practical solution to achieve data-driven models that can learn complex traffic models while being extremely accurate and fast. More specifically, Graph Neural Networks (GNNs) have emerged as an excellent tool for modeling graph-structured data showing outstanding accuracy when applied to computer networks. However, some challenges still persist:

1. Queues and Scheduling Policies: Modeling queues, scheduling policies, and Quality-of-Service (QoS) mappings within GNN architectures poses another challenge, as these elements are fundamental to network behavior.

2. Traffic Models: Accurately modeling realistic traffic patterns, which exhibit strong autocorrelation and heavy tails, remains a challenge for GNN-based solutions.

3. Training and Generalization: ML models, including GNNs, require representative training data that covers diverse network operational scenarios. Creating such datasets from real production networks is unfeasible, necessitating controlled testbeds. The challenge lies in designing GNNs capable of accurate estimation in unseen networks, encompassing different topologies, traffic, and configurations.

4. Generalization to Larger Networks: Real-world networks are often significantly larger than testbeds. Scaling GNNs to handle networks with hundreds or thousands of nodes is a pressing challenge, one that requires leveraging domain-specific network knowledge and novel architectural approaches.

This dissertation represents a step forward in harnessing Graph Neural Networks (GNN models) for network modeling, by proposing a new GNN-based architecture with a focus on addressing these critical challenges while being fast and accurate.

(Català) El modelatge de xarxes és fonamental en el camp de les xarxes informàtiques. Els models són útils per investigar nous protocols i mecanismes, permetent als administradors estimar el seu rendiment abans del seu desplegament real a les xarxes de producció. Els models de xarxa també ajuden a trobar configuracions de xarxa òptimes, sense necessitat de provar-les a les xarxes de producció.

Sens dubte, la manera més freqüent de construir aquests models de xarxa és mitjançant l'ús de metodologies de simulació d'esdeveniments discrets (DES) que proporcionen una precisió excel·lent. Els simuladors de xarxa d'última generació inclouen una àmplia gamma de protocols de xarxa, transport i encaminament, i són capaços de simular escenaris realistes. Tanmateix, això comporta un cost computacional molt elevat que depèn linealment del nombre de paquets que s'estimulen. Com a resultat, són poc pràctics en escenaris amb volums de trànsit realistes o topologies grans. A més, i com que són computacionalment costosos, no funcionen bé en escenaris en temps real.

Una altra alternativa de modelització de xarxes és la teoria de la cua (QT) on les xarxes es representen com a cues interconnectades que s'avaluen analíticament. Tot i que QT soluciona la principal limitació del DES, imposa supòsits forts sobre el procés d'arribada de paquets, que normalment no es compleixen a les xarxes reals.

En aquest context, l'aprenentatge automàtic (ML) ha sorgit recentment com una solució pràctica per aconseguir models basats en dades que poden aprendre models de trànsit complexos alhora que són extremadament precisos i ràpids. Més concretament, les xarxes neuronals de gràfics (GNN) han sorgit com una excel·lent eina per modelar dades estructurades en gràfics que mostren una precisió excepcional quan s'apliquen a xarxes d'ordinadors.

Aquesta tesi pretén ser un pas endavant en l'aplicació de les xarxes neuronals de gràfics per al modelatge de xarxes. Tanmateix, encara persisteixen alguns reptes:

1. Cues i polítiques de programació: modelar cues, polítiques de programació i mapes de qualitat de servei (QoS) dins de les arquitectures GNN suposa un altre repte, ja que aquests elements són fonamentals per al comportament de la xarxa.

2. Models de trànsit: modelar amb precisió patrons de trànsit realistes, que presenten una forta autocorrelació i cues pesades, segueix sent un repte per a les solucions basades en GNN.

3. Entrenament i generalització: els models ML, incloses les GNN, requereixen dades d'entrenament representatives que cobreixen diversos escenaris operatius de la xarxa. La creació d'aquests conjunts de dades a partir de xarxes de producció reals és inviable, ja que requereix bancs de proves controlats. El repte rau a dissenyar GNN capaços d'estimar amb precisió en xarxes no vistes, que abastin diferents topologies, trànsit i configuracions.

4. Generalització a xarxes més grans: les xarxes del món real sovint són significativament més grans que els bancs de proves. Escalar les GNN per gestionar xarxes amb centenars o milers de nodes és un repte urgent, que requereix aprofitar el coneixement de la xarxa específic del domini i enfocaments arquitectònics nous.

Aquesta tesi representa un pas endavant en l'aprofitament de les xarxes neuronals de grafs per al modelatge de xarxes, amb un enfocament a abordar aquests reptes crítics.

(Español) El modelado de redes es fundamental para el campo de las redes informáticas. Los modelos son útiles para investigar nuevos protocolos y mecanismos, lo que permite a los administradores estimar su rendimiento antes de su implementación real en las redes de producción. Los modelos de red también ayudan a encontrar configuraciones de red óptimas, sin necesidad de probarlas en redes de producción.

Podría decirse que la forma más frecuente de construir estos modelos de red es mediante el uso de metodologías de simulación de eventos discretos (DES) que proporcionan una precisión excelente. Los simuladores de redes de última generación incluyen una amplia gama de protocolos de red, transporte y enrutamiento y son capaces de simular escenarios realistas. Sin embargo, esto tiene un costo computacional muy alto que depende linealmente de la cantidad de paquetes que se simulan. Como resultado, no resultan prácticos en escenarios con volúmenes de tráfico realistas o topologías grandes. Además, y debido a que son computacionalmente costosos, no funcionan bien en escenarios de tiempo real.

Otra alternativa de modelado de redes es la teoría de colas (QT), donde las redes se representan como colas interconectadas que se evalúan analíticamente. Si bien QT resuelve la principal limitación de DES, impone fuertes suposiciones sobre el proceso de llegada de paquetes, que normalmente no se cumplen en las redes reales.

En este contexto, el aprendizaje automático (ML) ha surgido recientemente como una solución práctica para lograr modelos basados en datos que pueden aprender modelos de tráfico complejos y al mismo tiempo ser extremadamente precisos y rápidos. Más específicamente, las redes neuronales gráficas (GNN) se han convertido en una excelente herramienta para modelar datos estructurados en gráficos que muestran una precisión excepcional cuando se aplican a redes informáticas.

Esta disertación pretende ser un paso adelante en la aplicación de Graph Neural Networks para el modelado de redes. Sin embargo, aún persisten algunos desafíos:

1. Colas y políticas de programación: modelar colas, políticas de programación y asignaciones de calidad de servicio (QoS) dentro de las arquitecturas GNN plantea otro desafío, ya que estos elementos son fundamentales para el comportamiento de la red.

2. Modelos de tráfico: modelar con precisión patrones de tráfico realistas, que exhiben una fuerte autocorrelación y colas pesadas, sigue siendo un desafío para las soluciones basadas en GNN.

3. Capacitación y generalización: los modelos de ML, incluidos los GNN, requieren datos de capacitación representativos que cubran diversos escenarios operativos de red. Crear tales conjuntos de datos a partir de redes de producción reales es inviable y requiere bancos de pruebas controlados. El desafío radica en diseñar GNN capaces de realizar estimaciones precisas en redes invisibles, que abarquen diferentes topologías, tráfico y configuraciones.

4. Generalización a redes más grandes: las redes del mundo real suelen ser significativamente más grandes que los bancos de pruebas. Escalar las GNN para manejar redes con cientos o miles de nodos es un desafío apremiante, que requiere aprovechar el conocimiento de la red específico del dominio y enfoques arquitectónicos novedosos.

Esta tesis representa un paso adelante en el aprovechamiento de Graph Neural Networks para el modelado de redes, con un enfoque en abordar estos desafíos críticos.