PaperlayerView exact revision on arXiv

Source-linked AI summary

RouteNet: Leveraging Graph Neural Networks for network modeling and optimization in SDN

Krzysztof Rusek, José Suárez-Varela, Paul Almasan, Pere Barlet-Ros, Albert Cabellos-Aparicio

arXiv:1910.01508v2cs.NIcs.AIcs.LG

TL;DR

Network optimization lacks accurate, low-cost models for predicting delay, jitter, and loss from changing network conditions. The paper presents RouteNet, a GNN-based model that represents path–link relationships and evaluates its predictions on unseen networks and optimization tasks. RouteNet achieves accurate KPI estimates with a worst-case MRE of 15.4% and supports QoS-aware routing and link-placement planning.

  • Problem

    Existing network models lack accurate predictions of important KPIs such as delay, jitter, and packet loss at limited cost.

  • Method

    RouteNet uses a GNN with message passing over path and link representations to model topology, routing, and traffic and predict delay distributions and loss.

  • Results

    15.4% worst-case MRE was achieved on a never-seen 17-node network after training on 14-, 24-, and 50-node topologies, with accurate delay, jitter, and loss estimates on unseen conditions.

  • Takeaways & Limitations

    RouteNet predictions are used for QoS-aware routing optimization and network planning through optimal link-placement decisions.

Abstract

from arXiv · show

Network modeling is a key enabler to achieve efficient network operation in future self-driving Software-Defined Networks. However, we still lack functional network models able to produce accurate predictions of Key Performance Indicators (KPI) such as delay, jitter or loss at limited cost. In this paper we propose RouteNet, a novel network model based on Graph Neural Network (GNN) that is able to understand the complex relationship between topology, routing, and input traffic to produce accurate estimates of the per-source/destination per-packet delay distribution and loss. RouteNet leverages the ability of GNNs to learn and model graph-structured information and as a result, our model is able to generalize over arbitrary topologies, routing schemes and traffic intensity. In our evaluation, we show that RouteNet is able to predict accurately the delay distribution (mean delay and jitter) and loss even in topologies, routing and traffic unseen in the training (worst case MRE=15.4%). Also, we present several use cases where we leverage the KPI predictions of our GNN model to achieve efficient routing optimization and network planning.

I. INTRODUCTION

The paper introduces RouteNet, a GNN-based network model designed to predict network KPIs across unseen topologies, routing schemes, and traffic conditions, and applies those predictions to SDN optimization.

  • Motivation: Network optimization requires accurate, low-cost models that relate network state to KPIs such as delay, jitter, and packet loss.Existing analytic models and prior techniques do not provide sufficiently functional predictions for these KPIs at limited cost.
  • RouteNet: RouteNet uses a GNN to model relationships among topology, routing, and input traffic for per-source/destination delay-distribution and loss estimation.Its path representation treats routes as ordered sequences of links, enabling relational reasoning over network structure.
  • Model extensions: The extended model directly estimates per-packet delay distributions, allowing one model to derive mean delay and jitter while also predicting packet loss ratios.This replaces separate delay and jitter models and adds per-source/destination packet-loss prediction.
  • Evaluation: 15.4% worst-case MRE was obtained when testing on a never-seen 17-node network after training on 14-, 24-, and 50-node topologies.The evaluation also tested unseen routing and traffic conditions and reported accurate delay, jitter, and loss estimates.
  • Applications: RouteNet predictions support QoS-aware routing optimization that jointly considers delay, jitter, and loss, alongside network-planning use cases.The paper benchmarks routing optimization against traditional utilization-aware approaches and uses predictions for link-placement decisions.

II. SDN-BASED MODELING AND OPTIMIZATION SCENARIO

The SDN modeling architecture combines network-state inputs, a network model, and an optimizer to evaluate configurations and pursue policy-defined objectives. RouteNet implements the model with graph-aware message passing over paths and links.

  • SDN optimization architecture: SDN controllers use global network-state information and target policies to dynamically optimize configurations such as routing.The architecture combines a network model that predicts resulting performance with an optimizer that searches configurations.
  • RouteNet inputs and outputs: RouteNet takes topology, source-destination paths, and a traffic matrix as inputs and outputs per-path mean delay, jitter, and packet loss.Fixed-dimension path and link vectors propagate information according to the topology and routing scheme.
  • Graph representation: GNNs preserve graph-topology relationships, making them suitable for applying learned models across different network topologies without retraining.The approach represents graph elements with feature vectors and supports graph-structured relational reasoning.
  • Message passing: Message Passing Neural Networks alternate Message, Update, and Readout functions over fixed-dimension embeddings of graph elements.Messages are exchanged among neighbors for T iterations before the resulting embeddings are read out as model outputs.

C. Message Passing Architecture Of RouteNet

RouteNet uses graph-based message passing between links and paths to model circular dependencies while supporting variable-size topologies and arbitrary routing schemes. Repeated updates produce hidden states that feed path-, link-, or network-level metric readouts.

  • Message-passing formulation: RouteNet represents link and path states as hidden vectors whose dependencies are mutually defined through traversing relationships.Each path depends on all links it contains, while each link depends on all paths traversing it.
  • Model inputs and outputs: The model receives path features, link features, and routing description R, then outputs inferred per-path metrics.Its architecture is invariant to topology and routing scheme.
  • Message-passing formulation: Repeated message passing over link and path states addresses circular dependencies by approximating convergence toward a fixed point.The same operations are repeated T times from initial hidden states.
  • Message-passing operations: Paths aggregate messages from their constituent links, while links aggregate messages from all paths containing them.This direct mapping from end-to-end paths to message-passing operations supports arbitrary source-destination routing schemes.
  • Message-passing operations: Aggregation functions compress arbitrary numbers of received messages into fixed-dimension hidden states, enabling configurable representations and multiple readouts.Readout networks can infer path-level, link-level, and global features from the learned states.

D. Delay, Jitter, and Drops Models

RouteNet models delay, jitter, and packet loss with probabilistic outputs tailored to the corresponding performance distributions. The approach jointly models delay statistics and uses distribution-specific likelihoods for training.

  • Delay and jitter: Delay and jitter are modeled jointly as statistics of one per-path packet-delay distribution rather than with separate neural-network models.This avoids doubling training time and model parametrization relative to independent models.
  • Delay and jitter: RouteNet outputs parameters for a probability distribution representing each path’s delay, using sample mean and variance as estimates.The normal-distribution formulation trains by maximizing log-likelihood.
  • Delay and jitter: 43 The negative log-likelihood combines scaled squared delay error with terms representing jitter error under heteroscedastic regression.The formulation relies on mean and variance as sufficient statistics and assumes per-packet and per-path delays are iid.
  • Packet loss: Changing the modeled distribution allows RouteNet to represent different performance characteristics, including per-path packet loss with a discrete distribution such as Binomial.For alternative continuous distributions, the training data must provide their corresponding sufficient statistics.
  • Packet loss: Packet-loss training uses the observed number of losses as a sufficient statistic for the Binomial distribution.The associated log-likelihood is also common in binary classification.

IV. BASELINE

The baseline extends Jackson-style queuing analysis by modeling each link as a finite M/M/1/b system. A fixed-point procedure estimates loss-adjusted traffic and derives link and path performance statistics.

  • Baseline model: The baseline uses finite M/M/1/b queues to provide analytical packet-loss probabilities and handle overloaded links.It is used as a queuing-theory comparison for RouteNet’s network-performance predictions.
  • Baseline assumptions: The queuing model assumes Poisson arrivals, exponentially distributed packet lengths, and independent queues.Under these assumptions, it derives queue load, delay distribution, and blocking probability.
  • Fixed-point solution: A fixed-point method iteratively updates traffic intensities using path demands, link capacities, buffer size, and blocking probabilities.The first iteration assumes no packet loss before subsequent updates account for losses.
  • Performance computation: After convergence, standard queuing theory computes link delay, jitter, and drop probability, while path statistics are obtained assuming link independence.The baseline uses known queuing relations where RouteNet learns corresponding relations from data.

V. EVALUATION OF THE ACCURACY OF THE GNN MODEL

The evaluation measures RouteNet’s accuracy for per-source/destination mean delay, jitter, and packet drops across varied topologies, routing schemes, and traffic intensities.

  • Evaluation scope: The evaluation tests mean delay, jitter, and packet drops across a wide variety of network topologies, routing schemes, and traffic intensities.The stated targets are per-source/destination performance estimates.

A. Simulation Setup

The evaluation uses packet-level simulations across multiple topologies, traffic conditions, and routing schemes to train and assess RouteNet against queuing theory. Results examine accuracy, generalization, residual distributions, and inference cost.

  • Simulation Setup: Packet-level simulations compute per-source/destination mean delay, jitter, and packet drops over 16k time units.Traffic is generated from source-destination matrices, with exponential inter-packet arrivals, binomial packet sizes, 32-packet queues, and link capacities of 10, 40, or 100 kbps.
  • Dataset and Evaluation: 260,000 samples cover three training topologies, more than 200 routing schemes, and varied traffic matrices; 112,000 samples are used for testing.The independently simulated GBN topology is reserved for additional generalization testing.
  • Evaluation Metrics: RouteNet and queuing-theory models are evaluated using Mean Relative Error for delay, jitter, and loss across four network topologies.Table I summarizes the comparison between RouteNet and the finite-buffer queuing-theory baseline.
  • Inference Cost: 99.2 ms ± 561 µs is RouteNet’s single-inference time for a 200-node network with 39,800 paths on a GeForce GTX 1080.CPU inference on an i5-6400 takes 1.26 s ± 9.57 ms; training is performed once and is substantially more time-consuming.
  • Error Analysis: The relative-error CDF provides a comprehensive view of prediction residuals for delay, jitter, and packet loss.The figure distinguishes delay, jitter, and loss with solid, dashed, and dotted curves, respectively.
  • Generalization: Generalization to unseen routings and traffic matrices in known topologies is almost perfect, while accuracy remains comparable on the unseen GBN topology.The authors also describe reusing the message-passing component and fine-tuning only the readout for new networks.

C. Generalization Capabilities

RouteNet’s predictions support routing optimization under delay, jitter, and loss constraints, and the optimizer is evaluated against traditional routing strategies across traffic intensities. The results show constraint satisfaction and lower delay in many higher-load scenarios, while generalization depends on similarity to training distributions.

  • Generalization Capabilities: RouteNet is expected to be more accurate when deployment inputs resemble training topologies, routing patterns, and traffic-intensity ranges.Expanding generalization requires training data covering wider input distributions.
  • Delay, Jitter, and Loss-aware Routing Optimization: The QoS-aware optimizer prioritizes mean loss below 0.1%, jitter below 20% of mean delay, and then minimum mean delay.It evaluates candidate routing schemes using RouteNet’s predicted delay, jitter, and loss.
  • Delay, Jitter, and Loss-aware Routing Optimization: Figure 3 reports average mean delay, packet loss, and jitter-to-delay ratios across six traffic-intensity levels and 100 traffic matrices per level.Packet loss is displayed on a logarithmic y-axis.
  • Delay, Jitter, and Loss-aware Routing Optimization: RouteNet-based optimization maintains loss and jitter constraints in most medium-high-load scenarios at TI=14.At TI=15–16, some scenarios have no routing scheme meeting the loss requirement.
  • Delay, Jitter, and Loss-aware Routing Optimization: Traditional shortest-path and utilization-based optimizers exceed the loss threshold from TI=13, while RouteNet-based routing also achieves lower mean delay.The delay advantage becomes more pronounced as traffic intensity increases.
  • Delay, Jitter, and Loss-aware Routing Optimization: RouteNet-based optimization produces performance practically the same as optimization using packet-level simulator metrics.This comparison covers delay, jitter, and loss and contrasts learned predictions with computationally intensive simulation-based optimization.

B. Budget-constrained Network Upgrade

The budget-constrained upgrade use case selects a link placement and routing scheme for high-load scenarios where the loss constraint cannot otherwise be met. It evaluates a single added link against a utilization-based upgrade strategy.

  • Budget-constrained Network Upgrade: The upgrade problem targets optimal network expansion by adding new links to the topology.The scenarios are drawn from cases where high traffic prevents the RouteNet-based optimizer from meeting the 0.1% loss requirement.
  • Budget-constrained Network Upgrade: Eight TI=16 scenarios are evaluated for link placement and routing under a one-link upgrade budget.The added link has 10 kbps capacity, and all possible NSF placements are considered.
  • Budget-constrained Network Upgrade: For each possible placement, the optimizer evaluates 450 shortest-path routing variants and selects the combination with lower per-source/destination mean delay.Table II reports the resulting optimal link placements for the eight high-traffic matrices.
  • Budget-constrained Network Upgrade: The comparison strategy upgrades the currently most-loaded link to the next available capacity level.Links are upgraded from 10 to 40 kbps or from 40 to 100 kbps, depending on their original capacity.

VII. RELATED WORK

Prior network models struggle with graph complexity and generalization across scenarios. RouteNet addresses this with a GNN architecture that models path–link relationships and supports performance prediction and optimization use cases.

  • Motivation: Analytic models cannot handle network complexity, limiting optimization to global metrics or worst-case latency estimates.These limitations motivate data-driven network modeling for SDN optimization.
  • Motivation: Earlier deep-learning approaches used tailor-made architectures that failed to generalize across network scenarios.Prior methods modeled restricted settings such as fixed inputs, topologies, or performance measures.
  • RouteNet: RouteNet uses a custom GNN message-passing architecture to capture relationships between network paths and links induced by topology and routing.The architecture is designed specifically for computer network modeling.
  • RouteNet: RouteNet predicts per-source/destination delay and loss distributions and generalizes across unseen topologies, routing configurations, and traffic matrices.The extended model evaluates mean delay, jitter, and mean packet loss from predicted output distributions.
  • Applications: RouteNet supports transfer learning and optimization applications, including QoS-aware routing and link placement for network planning.The paper presents these as use cases based on RouteNet’s performance predictions.

APPENDIX LOSS FUNCTIONS

The appendix derives loss functions for probabilistic regression by expressing likelihoods in terms of predicted distribution parameters and observed statistics.

  • Normal regression: The normal-distribution probability density function is introduced as the basis for the likelihood formulation.The supplied passage identifies the density but does not include its full displayed equation.
  • Normal regression: The log-likelihood of a set of observations is formulated for the normal-regression case.This converts the density-based objective into a form suitable for optimization.
  • Normal regression: The derivation uses the biased sample variance estimator to simplify the normal log-likelihood.The estimator is introduced before the algebraic simplification.
  • Normal regression: L = −n log(σ) − 1 2σ2 (ns2 + nx2 −2nµx + nµ2) expresses the simplified normal log-likelihood.The equation uses n, σ, s^2, x̄, and µ as displayed in the supplied formulation.
  • Normal regression: Because the log-likelihood is maximized, the training loss is defined as −L.This produces the appendix’s equation (4).

B. Gamma

The gamma-regression formulation models delay with a gamma distribution and requires statistics of delay and log delay.

  • B. Gamma: Gamma regression introduces a probability density function for the delay.The supplied passage does not include the full displayed density equation.
  • B. Gamma: Gamma regression requires average delay x and average log delay log(x).These statistics are identified as the quantities needed by the formulation.
Loading 1910.01508v2…