Rerouting Flows when Links Fail
summary
Defines a formal model for single-link failures that maximizes flow subject to any one link going down and introduces the objective max-flow value at risk. Proves the decision problem is computationally hard in general, derives a simple necessary cut condition that characterizes when full rerouting is possible, gives polynomial-time algorithms for restricted topologies and a practical approximation scheme, and evaluates when low-cost local reroutes restore most of the original throughput.
AI-written summary · about
chapters (10)
- 0:00Rerouting flows introduction
- 3:25Single link failures disrupt flows
- 7:33Max flow despite link failures
- 12:45Flow recovery conditions
- 16:31Special cases simplified
- 20:40Real-world constraints
- 26:01Walkabouts variation
- 30:21Combinatorial flow issues
- 34:46Zero-day link failures
- 37:45Conclusion open questions
related talks
13mContracting Wide-area Network Topologies to Solve Flow Problems Quickly
17mVerifying maximum link loads in a changing world
20mContra: A Programmable System for Performance aware Routing
07mVertex Connectivity in Poly-logarithmic Max-flows
41mEverything I know about Routing Reliability and Liquidity on the Lightning Network
29mSynthesis of dependable and self-driving communication networks
16mEnhancing Network Failure Mitigation with Performance-Aware Ranking
21mSemi-Oblivious Traffic Engineering: The Road Not Taken