  Most modern communication networks include fast rerouting mechanisms,
implemented entirely in the data plane, to quickly recover connectivity after
link failures. By relying on local failure information only, these data plane
mechanisms provide very fast reaction times, but at the same time introduce an
algorithmic challenge in case of multiple link failures: failover routes need
to be robust to additional but locally unknown failures downstream. This paper
presents local fast rerouting algorithms which not only provide a high degree
of resilience against multiple link failures, but also ensure a low congestion
on the resulting failover paths. We consider a randomized approach and focus on
networks which are highly connected before the failures occur. Our main
contribution are three simple algorithms which come with provable guarantees
and provide interesting resilience-load tradeoffs, significantly outperforming
any deterministic fast rerouting algorithm with high probability.
