Leírás
The talk is based on the paper "Perfect Network Resilience in
Polynomial Time" by Matthias Bentert and Stefan Schmid.
Modern communication networks use local fast rerouting rules to handle
link failures, where each node decides how to forward packets based
only on local information. The goal is perfect resilience: ensuring
packets still reach their destination as long as the source and target
remain connected. However, achieving this is not always possible, and
understanding when it can be done has been an open problem.
This paper provides a complete characterization of when perfect
resilience is achievable. It gives an algorithm to decide whether a
network can achieve perfect resilience and to construct suitable
rerouting rules when it can. These rules follow a simple and practical
“skipping” strategy, where nodes prioritize outgoing links and skip
failed ones—an approach that is efficient and hardware-friendly. The
results also show that this simple strategy is as powerful as more
complex rerouting schemes, resolving a longstanding open question.
The characterization relies on the minor-closed property of the
problem. Using the result of Robertson and Seymour and identifying 4
forbidden minors we can efficiently decide, whether perfect resilience
is achievable.