Open World Learning Graph Convolution for Latency Estimation in Routing Networks

Yifei Jin, Marios Daoutis, Sarunas Girdzijauskas, Aristides Gionis

Abstract

Accurate latency estimation is a cornerstone of optimization in Software-Defined Networking (SDN). However, existing deep learning models often fail to generalize to "Open World" scenarios where network scales and traffic distributions differ significantly from training data. This paper presents a novel Graph Neural Network (GNN) framework developed by researchers at KTH and Ericsson. By integrating directed spectral convolutions with neural arithmetic units, the proposed model achieves a 75% reduction in error and up to a 7x speedup over state-of-the-art solutions, maintaining high accuracy even when extrapolating to networks six times larger than those seen during training.

1. Introduction

In modern networking, the ability to predict performance metrics like latency is essential for effective routing and resource allocation. While deep learning has shown promise in this area, most models operate under a "closed-world" assumption, where the testing environment closely mirrors the training environment. In real-world SDN deployments, topologies are dynamic, and traffic volumes can fluctuate beyond historical bounds. This "Open World Learning" (OWL) challenge—the ability to extrapolate to unseen scales and numerical distributions—remains a significant barrier to the practical adoption of neural network-based network estimators.

2. The Challenge of Open World Learning

Traditional models, such as standard Multi-Layer Perceptrons (MLPs) and undirected GNNs, typically struggle with two types of drift:

  1. Structural Drift: A model trained on a 50-node network often fails when deployed on a 300-node network because the underlying graph properties and path lengths change.
  2. Numerical Drift: Models often fail to handle traffic volumes or capacities that fall outside the range of the training set, as standard activation functions are better at interpolation than extrapolation.

To address these issues, a model must move beyond simple pattern recognition and instead learn the fundamental "Network Calculus"—the mathematical relationships governing traffic flow and delay.

3. Proposed Methodology

The researchers developed a multi-layered GNN architecture designed specifically for directional, scalable network data. The framework rests on four technical pillars:

3.1 Line Graph Transformation

Rather than treating routers as the primary nodes, the model transforms the network topology into a "line graph." In this representation, the communication links become the nodes. This allows the GNN to predict link-level attributes directly, which is more aligned with how latency accumulates across a path.

3.2 Directed Spectral Graph Convolution (DGCN)

Network traffic is inherently directional. Standard undirected GNNs lose critical information regarding the flow of data. The use of DGCN allows the model to capture asymmetric dependencies, effectively separating "in-traffic" and "out-traffic" to better model how congestion at one point affects downstream nodes.

3.3 Neural Arithmetic Logic Units (NALU)

To solve the problem of numerical extrapolation, the authors replaced standard MLPs with Neural Arithmetic Logic Units. NALUs are specifically designed to learn arithmetic functions, such as the ratios between traffic volume and link capacity. This enables the model to maintain accuracy even when encountering traffic intensities far higher than those seen during training.

3.4 Role Recognition Attention

Certain nodes in a network, such as core switches or gateway routers, play specific structural roles regardless of their immediate neighbors. The model employs an attention mechanism to identify these roles, allowing it to capture long-range dependencies and structural similarities across the topology without requiring an excessively deep network architecture.

4. Experimental Setup

The model was evaluated using a high-fidelity simulation environment:

  • Data Generation: Packet-level simulations were conducted using OMNeT++ v5.5.1.
  • Topologies: Real-world connectivity patterns were sourced from The Internet Topology Zoo.
  • Scale Gap: The model was trained on 120,000 samples from networks with 25 to 50 nodes. It was then tested on 3,120 samples from much larger networks, ranging from 50 to 300 nodes, to specifically measure its OWL capabilities.

5. Results and Discussion

The proposed model demonstrated significant improvements across all key performance indicators:

  • Superior Accuracy: The model achieved a Mean Absolute Percentage Error (MAPE) of 2.317%. In contrast, existing benchmarks like RouteNet and RouteNet-GA exhibited errors of 274.5% and 557.8%, respectively, when faced with out-of-distribution network sizes.
  • Computational Efficiency: The model is highly optimized, requiring only 6–25% of the embedding size used by other top-performing benchmarks. This efficiency allows for inference speeds 3 to 7 times faster than competing models.
  • Hardware Accessibility: For a 300-node network, the model provides predictions in approximately 2.7 seconds on a standard CPU. This eliminates the need for expensive GPU clusters for real-time network monitoring.

6. Conclusion

By combining domain-specific graph transformations with arithmetic-aware neural components, this research provides a robust solution for latency estimation in large-scale, evolving networks. The model's ability to extrapolate to unseen topologies and traffic loads marks a significant step toward deployable AI in SDN environments. Future work will focus on adapting the model to handle bursty traffic patterns and real-time dynamic topology changes.

Summary updated

BibTeX
@inproceedings{jin2022open,
  author = {Yifei Jin and Marios Daoutis and Sarunas Girdzijauskas and Aristides Gionis},
  title = {{Open World Learning Graph Convolution for Latency Estimation in Routing Networks}},
  booktitle = {IJCNN},
  year = {2022},
  doi = {10.1109/ijcnn55064.2022.9892952},
}
Figure