Adaptive Game-Theoretic Routing for Software-Defined Networks under Single-Link Failures: Performance Analysis and Trade-Offs

1.1 Motivation

Modern critical infrastructure increasingly relies on high performance, low-latency networks, with software-defined networking (SDN) emerging as the de-facto paradigm for 5G and emerging 6G systems [1, 2]. SDN’s centralised control plane enables programmable traffic engineering, but also introduces new vulnerability modes: a single link failure can propagate congestion across multiple paths, degrading quality of service (QoS) in conventional static routing deployments [3]. Applications such as industrial IoT, autonomous vehicle coordination, and emergency communications impose strict latency budgets that cannot tolerate such degradation [4].

Existing routing protocols address failure recovery at various layers. Traditional interior gateway protocols (e.g., OSPF with Fast Reroute) react to failures within seconds, which is inadequate for ultra-reliable low-latency communication (URLLC). Equal-Cost Multi-Path (ECMP) routing distributes load across shortest paths but is oblivious to congestion and flow priority. Machine learning approaches have demonstrated offline path-selection improvements but struggle with real-time congestion adaptation. Game-theoretic (GT) methods offer coordination guarantees but have not been evaluated in unified failure benchmarks alongside their alternatives.

Scope statement. All results in this paper are obtained by discrete-event simulation on 11-node topologies under isolated single-link failures. They characterise algorithmic behaviour, not deployment performance; larger-scale emulation or physical-testbed validation would be required before any operational claim.

1.2 Problem statement and research gaps

Despite extensive individual study of static, machine learning (ML)-based, and GT routing, no unified comparative framework evaluates all three paradigms under identical failure conditions with priority-aware traffic and a shared candidate-path set. Three gaps are identified:

•Cross-paradigm benchmarking: most works evaluate a single routing family in isolation, precluding direct comparison.

•Priority-aware failure recovery: mechanisms that simultaneously honour flow priorities and recover from topology failures remain underexplored.

•Controlled path availability: comparisons rarely state how candidate paths are generated or whether competing routers receive the same set, confounding path availability with path selection.

1.3 Contributions

Congestion-aware GT routing algorithm. We formulate routing as a non-cooperative game, prove it is an exact potential game admitting a pure-strategy Nash equilibrium reachable by finite improvement (Lemma 1, Theorem 1), and bound its inefficiency (Theorem 2).

Unified comparative evaluation. We benchmark static, offline decision-tree (DT), and GT routing under identical single-link failure scenarios across three topology families using an explicitly specified shared candidate-path set complemented by a component ablation and by robustness studies under heterogeneous capacities and multi-link failures.

Analytical characterisation. We prove the routing game is an exact potential game with a pure Nash equilibrium reached by finite best-response dynamics, and identify a representational (not quantified) limitation of offline supervised path classifiers over static features. This limitation concerns congestion-blind classifiers and does not bound GNN or deep-RL routers that observe live network state.

Algorithm-selection framework. We derive a decision rule (Eq. (13)) partitioning the (latency-sensitivity, failure- frequency) plane into regions favouring each paradigm. Its parameters must be measured per deployment; we make no performance claim for the hybrid architecture, which is proposed but not evaluated.

Open-source platform. All code, topologies, and analysis scripts are publicly released for reproducibility.

1.4 Paper organisation

Section 2 surveys related work. Section 3 formalises the system model and algorithm designs. Section 4 describes the framework and simulation setup. Section 5 presents results, including two robustness studies. Section 6 analyses trade-offs and limitations. Section 7 gives analytical justification with proofs, and Section 8 concludes.

3.1 Network model

The network is a graph $\mathcal{G}=(\mathcal{V}, \mathcal{E})$ with $\mathcal{V}=\left\{v_1, \ldots, v_N\right\}$. the set of $N$ nodes and $E$ the link set. The system evolves in discrete time slots $t \in \mathcal{T}=\{1, \ldots, T\}$.

(1) Latency model

Each link $(u, v) \in \mathcal{E}$ has base latency $b_{(u, v)} \sim \mathcal{U}(1,10) \mathrm{~ms}$. modelling propagation delay. The instantaneous link latency is:

$\ell_{(u, v)}(t)=b_{(u, v)}+\eta f_{(u, v)}(t)+\varepsilon_{(u, v)}(t)$            (1)

where, $f_{(u, v)}(t)$ is the number of active flows on the link, $\eta=$ $0.5 \mathrm{~ms} /$flow is the congestion coefficient, and $\mathcal{E}_{(u, v)}(t) \sim$ $\mathcal{N}\left(0, \sigma^2\right)$ with $\sigma=0.5 \mathrm{~ms}$.

Eq. (1) is valid in the low-to-moderate utilisation regime with homogeneous link capacities. Because linearity and homogeneity materially affect the conclusions, they are tested directly rather than merely discussed: Section 5 repeats the full comparison under heterogeneous capacities with background traffic and a nonlinear near-saturation term. Absolute latency values reported under Eq. (1) are model-specific and should not be read as deployment predictions.

(2) Flow model

Each flow $i \in \mathcal{F}(t)$ is characterised by $\phi_i=$ ( $s_i, d_i, P_i, \tau_i^{a r r}, \tau_i^{d u r}$ ) , where $s_i, d_i \in \mathcal{V}$ are source and destination, $P_i \in\{1$ (high), 2 (low) $\}$ is priority, and $\tau_i^{\text {arr }}, \tau_i^{\text {dur }}$ are arrival time and duration. Arrivals are Poisson:

$\left|\mathcal{F}_{\text {new }}(t)\right| \sim \operatorname{Poisson}(\lambda), \operatorname{Pr}\left(P_i=1\right)=0.6$             (2)

with $\lambda=5$ flows$/ \mathrm{sec}$ fixed throughout to isolate failure-recovery behaviour from arrival-rate effects, and $\tau_i^{d u r} \sim$ $\mathcal{U}(5,15)$ s.

3.2 Multi-objective utility function

Path selection for flow i is posed as:

$\underset{\mathcal{P}_i}{\operatorname{maximise}} \mathcal{~U}_i(t)=\omega_1 \mathcal{R}_i+\omega_2 Q_i-\omega_3 \mathcal{D}_i$            (3)

where, $\mathcal{R}_i$ is a priority-based reward, $Q_i$ quantifies fairness, and $\mathcal{D}_i$ is path delay. Under linear flow-latency, additive path metrics, and linear priority rewards this reduces to:

$\mathcal{U}_i(t)=-\alpha L_i(t)-\beta C_i(t)+\gamma P_i$               (4)

with $L_i(t)=\sum_{(u, v) \in \mathcal{P}_i} \ell_{(u, v)}(t)$ the cumulative path latency and $C_i(t)=\sum_{(u, v) \in \mathcal{P}_i} f_{(u, v)}(t)$ the path congestion intensity. The term $\gamma P_i$ is path-independent for a given flow: it does not enter that flow's ranking of its own candidate paths and only sets the order in which flows exercise best response (high priority first). We therefore make no claim that priority produces a latency separation between classes; in our experiments it does not, and the update order is retained solely as a deterministic tie-break. A mechanism that genuinely differentiates priority classes (e.g. priority-weighted congestion cost or capacity reservation) is left to future work.

Weight sensitivity: The GT algorithm was evaluated over α ∈ [0.5,2.0], β ∈ [0.4,1.6], γ ∈ [0.6,2.4]. Mean latency remained within ±8% of the nominal result, supporting the chosen values (α = 1.0, β = 0.8, γ = 1.2).

3.3 Routing algorithms

All three routers select from the same candidate set; they differ only in the selection rule.

(1) Static shortest-path routing

Static routing selects the minimum-base-latency member of the candidate set,

$\mathcal{P}_i^{\text {static }}=\arg \min _{\mathcal{P} \in \mathbb{P}_i} \sum_{(u, v) \in \mathcal{P}} b_{(u, v)}$                (5)

and does not adapt to congestion.

(2) Offline DT baseline

The DT baseline is a depth-8 classifier trained on 45 independent episodes drawn evenly from all three topology families (Abilene, Erdos–Rényi, and Barabási–Albert), in which the GT algorithm’s chosen candidate index is the label, so it is not specialised to a single topology in the pooled evaluation. Its feature vector $x_i$ comprises the three candidates’ base latencies, their hop counts, and the flow priority—all static quantities. It selects:

$\hat{y}=\underset{k \in\{1, \ldots, K\}}{argmax } {Pr}\left(k \mid \boldsymbol{x}_i\right)$              (6)

falling back to the next-ranked valid candidate if $\hat{y}$ is invalidated by a failure. As stated, GNN and RL baselines are out of scope.

(3) GT routing

Routing is modelled as a non-cooperative game $\Gamma=$ $\left\langle\mathcal{F},\left\{\mathbb{P}_i\right\},\left\{\mathcal{U}_i\right\}\right\rangle$ in which each flow selects $\mathcal{P}_i \in \mathbb{P}_i$ to maximise Eq. (4). The algorithm implements iterative best response:

•Initialise $\mathcal{P}_i^{(0)}$ for all $i \in F$.

•For k = 1,...,K_max: update link latencies via Eq. (1); then, for each flow i in order of decreasing priority,

$\mathcal{P}_i^{(k)} \leftarrow \underset{\mathcal{P} \in \mathbb{P}_i}{\arg \max } \mathcal{U}_i\left(\mathcal{P}, \mathcal{P}_{-i}^{(k-1)}\right)$               (7)

•Terminate when no flow changes path, or at k = K_max.

Proposition 1 (Nash equilibrium existence). The game Γ admits a pure-strategy Nash equilibrium.

Proof. Each flow's action set $\mathbb{P}_i$ is finite and its cost is a sum of per-edge congestion costs, so $\Gamma$ is a finite congestion game. By Lemma 1 it admits an exact potential $\Phi$; a profile minimising $\Phi$ over the finite action space exists and is, by the finite improvement property, a pure-strategy Nash equilibrium (Theorem 1).

Remark. Existence follows from the potential-game structure rather than from fixed-point arguments over convex strategy spaces, which do not apply to a finite path set. The game may admit multiple equilibria; the empirical spread across runs is 4.04 ± 0.05 best-response sweeps, indicating practical stability.

5.3.3 Component ablation

To support the claim that GT’s benefit is attributable to specific mechanisms, we ablate the algorithm on Abilene (single-link failure, 30 runs), disabling one component at a time: the congestion term (β = 0, routing on base latency plus a load-blind sweep); iterative refinement (K = 1, a single best-response pass); and adaptivity (paths fixed at admission by minimum base latency, re-routed only on failure, i.e. effectively static se- lection). Table 5 and Figure 9 report the result.

Table 5. Component ablation of GT (Abilene, single-link failure, 30 runs, mean ± 95% CI). Latency increase is relative to full GT.

Figure 9. Component ablation on Abilene. Removing per-slot re-optimisation (adaptivity) accounts for essentially all of GT’s advantage (+10.3% latency), while the congestion term and extra best-response sweeps contribute little in the homogeneous linear regime (+0.6% and +0.3%)

The decomposition is informative and is reported as measured. Adaptivity — re-optimising installed paths as load evolves — is the dominant mechanism: fixing paths at admission forfeits 10.3%, recovering essentially the static-routing latency. The congestion term and additional sweeps add little in the homogeneous linear regime (+0.6% and +0.3%), consistent with the near-flat convergence trajectory. This does not diminish the congestion term: its value is realised under capacity heterogeneity, where Section 5 shows the same term driving a 42.6% margin. In short, dynamic re-optimisation drives the homogeneous-regime gain, while congestion pricing drives the heterogeneous-regime gain.

Table 5 presents the component-ablation results for the proposed GT router. The marked degradation produced by fixed paths shows that online adaptivity is the principal source of improvement in the homogeneous-capacity setting.

This section links the empirical observations to formal results. When ranking a single flow's paths we drop the zeromean noise ( $\mathbb{E}\left[\varepsilon_e\right]=0$ ) and the path-independent term $\gamma P_i$, and write the per-edge cost experienced by a flow on edge $e$ carrying $f_e$ flows as:

$c_e\left(f_e\right)=\alpha b_e+(\alpha \eta+\beta) f_e$            (11)

which is affine and strictly increasing in f_e since α,η,β > 0.

7.1 Potential-game structure

Lemma 1 (Exact potential). The routing game $\Gamma$ with perflow $\operatorname{cost} J_i\left(\mathcal{P}_i, \mathcal{P}_{-i}\right)=\sum_{e \in \mathcal{P}_i} c_e\left(f_e\right)$ is an exact potential game with Rosenthal potential:

$\Phi(\mathcal{P})=\sum_{e \in \mathcal{E}} \sum_{k=1}^{f_e} c_e(k)=\sum_{e \in \mathcal{E}}\left[\alpha b_e f_e+(\alpha \eta+\beta) \frac{f_e\left(f_e+1\right)}{2}\right]$              (12)

Proof. If flow i switches from $\mathcal{P}_i$ to $\mathcal{P}_i{ }^{\prime}$, its cost changes by $\sum_{e \in \mathcal{P}_{i^{\prime}} \backslash \mathcal{P}_i} c_e\left(f_e+1\right)-\sum_{e \in \mathcal{P}_i \backslash \mathcal{P}_{i^{\prime}}} c_e\left(f_e\right)$. Inserting (removing) flow $i$ on an edge changes the inner sum of (12) by exactly $\mathrm{c}_{\mathrm{e}}\left(\mathrm{f}_{\mathrm{e}}+1\right)\left(\right.$ by $\left.\mathrm{c}_{\mathrm{e}}\left(\mathrm{f}_{\mathrm{e}}\right)\right)$, so $\Delta \Phi=\Delta J_i[27]$.

Theorem 1 (Finite-time convergence). Sequential best response (in the fixed high-priority-first order) reaches a pure strategy Nash equilibrium after at most (Φ_max − Φ_min)/∆_min productive updates, where ∆_min > 0 is the smallest strictly positive single-move improvement.

Proof. Each productive move strictly lowers some J_i and, by Lemma 1, lowers Φ by at least ∆_min. As Φ takes finitely many values in [Φ_min,Φ_max], the monotone sequence terminates; at termination no flow can improve, i.e. the profile is a pure Nash equilibrium (finite-improvement property [28]). This establishes Proposition 1 and bounds the re-optimisation loop, whose recovery time obeys T_rec ≤ T_det +K_max δ with per-round cost δ.

7.2 Convergence trajectory (empirical)

Theorem 1 guarantees termination after finitely many productive moves but does not bound the number of sweeps. We therefore characterise convergence empirically rather than claim a geometric rate. If the per-sweep residual-gap contraction factor is ρ, then reaching a fraction 1 − θ of the eventual improvement takes k ≥ ln θ / ln ρ sweeps; fitting this to the measured trajectory (Figure 6) gives ρ ≈ 0.02 for the first sweep, i.e. one sweep already realises about 99% of the total gain, with full termination at 4.04±0.05 sweeps. We do not assert geometric contraction as a general property; it is an observed regularity for the instances tested.

7.3 Mean-latency reduction

The social cost is $\mathrm{S} C(\mathcal{P})=\sum_i J_i=\sum_e f_e c_e\left(f_e\right)$.

Theorem 2 (Bounded inefficiency, affine model only). For the affine atomic congestion game $\Gamma$ defined by the linear cost of Eq. (11), every pure Nash equilibrium satisfies $\mathrm{SC}\left(\mathcal{P}^{\mathrm{NE}}\right) \leq$ $\frac{5}{2} \mathrm{SC}\left(\mathcal{P}^{\mathrm{OPT}}\right) ~[29]$. This bound applies only to the affine model; it does not extend to the nonlinear near-saturation cost of Eq. (10), for which we make no price-of-anarchy claim.

Static routing minimises only $\sum_{e \in \mathcal{P}_i} \alpha b_e$ and ignores the load slope $(\alpha \eta+\beta) f_e$; on the classical Pigou instance with $m$ flows over two parallel links, congestion-blind concentration on the minimum-base-latency link gives social cost $\Theta\left(m^2\right)$ against the balanced $\Theta\left(m^2 / 2\right)$-a ratio of two, illustrating (though not attaining) the $5 / 2$ worst case. GT attains a Nash equilibrium within the constant factor 5/2 of optimum in the affine model, contributing to the lower mean latency in Table 2. The widening margin under the nonlinear model is consistent with this picture-steeper costs penalise concentration more-but is an empirical observation there, not a consequence of Theorem 2.

7.3.1 Load balancing and latency variance

Lemma 2 (Load balancing term). The potential decomposes as $\Phi=\underbrace{\sum_e \alpha b_e f_e}_{\text {base-latency term }}+\frac{\alpha \eta+\beta}{2}\left(\sum_e f_e^2+F\right)$, so its is loaddependent part is strictly increasing function of $\sum_e f_e^2$. When the candidate paths available to the flows have comparable base latency, the first term varies little across feasible routings and minimising $\Phi$ is dominated by minimising $\sum_e f_e^2$; in general the two terms trade off, and $\Phi$ balances base-latency routing against load spreading.

Proof. Expanding $\sum_{k=1}^{f_e} c_e(k)$ in (12) with the affine $c_e$ of Eq. (11) gives the stated decomposition. The base-latency term is not constant in general (different routings assign different edges), so the equivalence to $\min \sum_e f_e^2$ holds only in the comparable-base-latency limit; otherwise it is a weighted trade-off.

Corollary 1 (Peak and variance reduction). Over the $|\varepsilon| u$ sed edges, $\max _e f_e \geq \frac{F}{|\varepsilon|}$ with equality iff the load is uniform, and $\operatorname{Var}(f)=\frac{1}{|\varepsilon|} \sum_e f_e^2-\left(\frac{F}{|\varepsilon|}\right)^2$ is increasing in $\sum_e f_e^2$.

A pure Nash equilibrium is a local minimiser of $\Phi$ under single-flow deviations (Theorem 1), not necessarily the global minimiser. Nonetheless, because the load-dependent part of $\Phi$ (Lemma 2) penalises concentration through $\sum_e f_e^2$, best response drives the profile toward lower $\max _e f_e$ and lower $\operatorname{Var}(f)$ than congestion-blind static routing-an effect confirmed empirically in Figure 5 rather than claimed as an exact optimum (Corollary 1). Since the congestion-induced spread obeys $\operatorname{sd}(L) \propto \eta \operatorname{sd}\left(\sum_{e \in \mathcal{P}} f_e\right)$, this accounts for both the lower 95th-percentile latency and the higher diversity index in Table 2.

7.3.2 On priority ordering

The update order places high-priority flows first, but this does not imply a component-wise load advantage when flows have distinct source–destination pairs and candidate sets: a high-priority flow and a low-priority flow generally traverse different edges, so decision order alone does not order their experienced loads. We accordingly make no formal or empirical claim of a priority-latency separation, and no such proposition is asserted. A path-dependent priority mechanism that would support such a claim is identified as future work.

7.3.3 Selection rule

An operator should adopt GT when its expected latency benefit outweighs its re-convergence cost:

$\alpha s\left(\bar{L}_{\text {static }}-\bar{L}_{\mathrm{GT}}\right)>\kappa \varphi t_{\text {conv }}$             (13)

where, $s$ is latency sensitivity, $\varphi$ the failure frequency, and $\kappa$ a scaling constant. Inequality (13) partitions the $(s, \varphi)$ plane into GT-, DT-, and static-favouring regions. Its parameters are deployment-specific and must be measured; the inequality is offered as a decision structure rather than as a calibrated recommendation.

The authors thank the Department of Computer Science, GITAM Deemed to be University, for providing computational resources used in this study, and the anonymous reviewers, whose comments on the throughput metric and on candidate path construction identified errors that materially improved the correctness of this work.