Verifying maximum link loads in a changing world
summary
Velo finds maximum link loads when links fail and BGP routes change by proving worst-case per-destination happens with a single-egress worst case and by clustering similar destinations to shrink a million-column traffic matrix. It computes all worst-case loads for large ISP topologies (1,790 links) in minutes–hours by exploring ~3M failure+route scenarios, runs ~300 scenarios/sec with 300 clusters, and speeds up computation ~70× versus no clustering while yielding 300 clusters <0.5% error and error bounds typically <5%.
AI-written summary · about
chapters (9)
- 0:00Network link congestion challenges
- 1:01Prior worst-case load analysis limits
- 3:32Modeling failures and routing changes
- 5:40Vevel system overview
- 8:30Reducing search space with routing
- 9:54Clustering traffic matrices
- 13:05Vevel scalability and accuracy
- 15:40Open questions and future work
- 17:04Summary and Q&A
related talks
17mReasoning about Network Traffic Load Property at Production Scale
31mExpectAll: A BDD Based Approach for Link Failure Resilience in Elastic Optical Networks
18mBayWatch: Practical Internet-Scale Topology Monitoring with Dynamic Bayesian Estimation
41mRerouting Flows when Links Fail
29mUsing the Internet as Your Load-Balancer
23mNetBouncer: Active Device and Link Failure Localization in Data Center Networks
34mHyperRouter: Lessons Learnt from Building an L4 Load...
32mCDN Scaling Challenges