How (Not) to Shoot in Your Foot with SDN Local Fast Failover - A Load-Connectivity Tradeoff
Michael Borokhovich, Stefan Schmid · 2013
Abstract. This paper studies the resilient routing and (in-band) fast failover mechanisms supported in Software-Defined Networks (SDN). We analyze the potential benefits and limitations of such failover mechanisms, and focus on two main metrics: (1) correctness (in terms of connectivity and loop-freeness) and (2) load-balancing. We make the following contri-butions. First, we show that in the worst-case (i.e., under adversarial link failures), the usefulness of local failover is rather limited: already a small number of failures will violate connectivity properties under any fast failover policy, even though the underlying substrate network remains highly connected. We then present randomized and deterministic algo-rithms to compute resilient forwarding sets; these algorithms achieve an almost optimal tradeoff. Our worst-case analysis is complemented with a simulation study. 1