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 contributions. 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 algorithms to compute resilient forwarding sets; these algorithms achieve an almost optimal tradeoff. Our worst-case analysis is complemented with a simulation study.
Alternative solutions to make routing more resilient rely on special header bits (e.g., to determine when to switch from primary to backup paths, as in @cite_1 , or to encode failure information to make failure-aware forwarding decisions @cite_9 @cite_10 ), or on fly table modifications @cite_2 . Recently, @cite_5 made an interesting first step towards a better theoretical understanding of resilient SDN tables. The authors prove that routing tables can provide guaranteed resilience (i.e., loop-freeness) against a failure, when the network remains connected.
@cite_9 @cite_1 @cite_2 @cite_5 @cite_10
2131754091 2023696105 2035448486 1963915651
Link failures are part of the day-to-day operation of a network due to many causes such as maintenance, faulty interfaces, and accidental fiber cuts. Commonly deployed link state routing protocols such as OSPF react to link failures through global link state advertisements and routing table recomputations causing significant forwarding discontinuity after a failure. Careful tuning of various parameters to accelerate routing convergence may cause instability when the majority of failures are transient. To enhance failure resiliency without jeopardizing routing stability, we propose a local rerouting based approach called failure insensitive routing. The proposed approach prepares for failures using interface-specific forwarding, and upon a failure, suppresses the link state advertisement and instead triggers local rerouting using a backwarding table. With this approach, when no more than one link failure notification is suppressed, a packet is guaranteed to be forwarded along a loop-free path to its destination if such a path exists. This paper demonstrates the feasibility, reliability, and stability of our approach. Dealing with network failures effectively is a major operational challenge for Internet service providers. Commonly deployed link state routing protocols such as OSPF react to link failures through global (i.e., network-wide) link state advertisements and routing table recomputations, causing significant forwarding discontinuity after a failure. The drawback with these protocols is that they need to trade off routing stability and forwarding continuity. To improve failure resiliency without jeopardizing routing stability, we propose a proactive local rerouting based approach called failure insensitive routing (FIR). The proposed approach prepares for failures using interface-specific forwarding, and upon a failure, suppresses the link state advertisement and instead triggers local rerouting using a backwarding table. In this paper, we prove that when no more than one link failure notification is suppressed, FIR always finds a loop-free path to a destination if one such path exists. We also formally analyze routing stability and network availability under both proactive and reactive approaches, and show that FIR provides better stability and availability than OSPF. The increasing proportion of data traffic being carried in public networks is necessitating tractable and scalable algorithms in the design of ATM networks. In particular, the design of routing tables for ATM networks operated under the interim inter-switch signalling protocol (IISP) requires a significant amount of manual work in order to design and implement the underlying static routing tables that enable end-to-end connectivity as the network grows. This paper presents a scalable algorithm that generates IISP routing table entries such that no loops are created and so that connectivity is maintained between all origin destination nodes under single-link failures. The algorithm generates shortest (i.e., lowest-cost) primary and alternate paths for any single-link failure scenario, while also demonstrating that at least one such solution can be found for any network graph devoid of bridges. Note that re-routing for single-link failures is considered adequate when sufficient protection is provided at the lower network layers. The algorithm has been fully implemented in a practical software tool, with execution time being a polynomial function of the network complexity. Many modern network designs incorporate "failover" paths into routers' forwarding tables. We initiate the theoretical study of such resilient routing tables.