// the problem
Why This Needed to Exist
In large Autonomous Systems using iBGP, full-mesh sessions scale as O(n²) — infeasible beyond ~10 routers. Route Reflectors (RRs) solve this by acting as BGP mirrors, but introduce a critical flaw: an RR selects exit paths based on its own IGP position, not its clients'. This causes hot-potato routing suboptimality — traffic exits the AS from a suboptimal point relative to the actual client. The academic question: can we place k RRs to minimize aggregate routing suboptimality across all client-destination pairs? This is documented in RFC 9107 and remains an open operational challenge.
// what i built
The Solution
We formalized the problem as a p-median facility location problem: given a weighted graph of ISP routers and links (sourced from the Internet Topology Zoo), select k nodes as Route Reflectors such that the sum of IGP distances from each non-RR node to its assigned RR is minimized. We implemented three solvers in Julia: (1) Integer Linear Program using JuMP with HiGHS backend — provably optimal but exponential worst-case; (2) Greedy Forward Selection — iteratively adds the RR that most reduces total cost; (3) Local Search with random restarts — swaps RRs to escape local optima. We benchmarked all three against baseline heuristics: betweenness centrality, highest-degree node selection, and random placement.
// the architecture
System Design
DATASET: Internet Topology Zoo — 260+ real ISP topology graphs (GML format)
Regions: US domestic, European, global backbone
Node counts: 6 to 754 nodes per topology
SOLVERS (Julia implementation):
ILP: JuMP modeling language + HiGHS open-source MIP solver
- Decision variables: binary x_ij (node i assigned to RR j), y_j (j is RR)
- Objective: minimize sum of IGP-weighted distances
- Constraint: exactly k RRs selected, each node assigned to exactly one RR
Greedy: O(k·n²) forward selection — adds best RR one at a time
Local Search: random initial placement → swap moves → accept improvements
- Multiple restarts to escape local optima
EXPERIMENTS (5 structured):
1. Optimality gap: ILP vs Greedy vs Local Search vs baselines
2. Scaling behavior: runtime vs topology size
3. k sensitivity: routing quality vs number of RRs (diminishing returns)
4. Topology class effects: US vs EU vs global
5. Baseline comparison: optimized vs centrality/degree/random heuristics// key challenges
Problems I Solved
ILP Scalability Wall
JuMP/HiGHS solved small-to-medium topologies optimally but timed out on large graphs (700+ nodes). We used ILP results as ground truth for smaller topologies and relied on Greedy/Local Search for larger ones, allowing valid optimality gap measurements where exact solutions were available.
Modeling IGP Distance as Routing Proxy
Real hot-potato routing cost depends on IGP link weights, not just hop count. We parsed actual link weights from the Internet Topology Zoo GML files and ran shortest-path (Dijkstra) to compute true IGP distances between all node pairs — making the objective function reflect real routing behavior rather than a simplification.
Diminishing Returns Threshold Identification
We ran experiments across k = 1 to 10 RRs on representative topologies and plotted marginal cost reduction per additional RR. Most topologies showed a clear elbow in the curve — beyond k=3 or k=4, additional RRs produced minimal routing improvement. This finding has direct operational significance: more RRs isn't always better.
// outcomes
What I Learned
ILP achieves provably optimal placement and serves as a benchmark. Greedy Forward Selection achieves 95–99% of optimal quality in a fraction of the runtime, making it operationally viable. Local Search consistently improves on greedy for larger topologies. All three optimized approaches substantially outperform betweenness centrality and degree-based heuristics — which are commonly used in practice. The diminishing returns finding suggests network operators can achieve near-optimal routing quality with far fewer RRs than currently deployed. This work bridges academic facility location theory with real BGP operational challenges documented in RFC 9107.
// tech stack
Tools & How I Used Them
Julia
Primary implementation language for all solvers and experiments
JuMP
Julia modeling language for mathematical optimization — used for ILP formulation
HiGHS
Open-source MIP solver backend for exact ILP solutions
Internet Topology Zoo
Dataset of 260+ real ISP network topologies in GML format
BGP / iBGP
Border Gateway Protocol — the routing protocol this work directly targets
p-Median Problem
Facility location optimization formulation used to model RR placement
Dijkstra's Algorithm
Used to compute all-pairs IGP shortest paths as routing cost proxy
RFC 9107
IETF standard documenting BGP RR routing suboptimality — the academic motivation