Graph neural networks guide progressive metric updates for congestion free OSPF reconfiguration
TL;DR
Graph Neural Network Guided Progressive Metric Updates (GNN-PMU), a graph-aware scheduler that ranks metric changes using topology, utilization, queue, capacity, and pending-update information, is presented.
Abstract
Metric reconfiguration in OSPF can create transient routing states whose link utilization exceeds capacity even when the initial and target configurations are both feasible. This paper presents Graph Neural Network Guided Progressive Metric Updates (GNN-PMU), a graph-aware scheduler that ranks metric changes using topology, utilization, queue, capacity, and pending-update information. The learned ordering is checked with the exact Dijkstra and ECMP routing operator before deployment, and Serialized Min-Margin Greedy (SMG) provides a conservative fallback when the learned schedule fails exact validation. The framework distinguishes safety soundness from scheduling completeness and evaluates direct acceptance, fallback activation, final request rejection, and oracle-confirmed SMG false-infeasibility. Simulation-derived experiments also examine telemetry corruption, stale measurements, localized traffic spikes, soft-routing approximation error, embedding distribution shift for batches larger than those used in training, forwarding-table churn, and end-to-end OSPF reconfiguration time. Across the tested benchmark and simulation topologies, direct GNN acceptance ranges from 90.5% to 96.9%, final rejection remains between 0.4% and 2.4%, and accepted schedules satisfy the link-capacity constraint. GNN scheduling remains below 10 ms throughout the tested batch-size range, while exact validation preserves the safety property under out-of-distribution conditions.
