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.
This work is motivated by the trend towards Software-Defined Networking and in particularly the fast failover mechanism which supports the in-band masking of failures (see Section 5.8 of the OpenFlow 1.1 specification). However, as the convergence time of routing algorithms is often relatively high compared to packet forwarding speeds, ranging from 10s of milliseconds to seconds depending on the network @cite_5 , many networks today incorporate some robustness already in the forwarding tables of a router or switch: Thus, robust routing concepts and link protection schemes have been studied intensively for many years, also outside SDN.
@cite_5
2035448486
When dealing with node or link failures in Software Defined Networking (SDN), the network capability to establish an alternative path depends on controller reachability and on the round trip times (RTTs) between controller and involved switches. Moreover, current SDN data plane abstractions for failure detection (e.g. OpenFlow "Fast-failover") do not allow programmers to tweak switches' detection mechanism, thus leaving SDN operators still relying on proprietary management interfaces (when available) to achieve guaranteed detection and recovery delays. We propose SPIDER, an OpenFlow-like pipeline design that provides i) a detection mechanism based on switches' periodic link probing and ii) fast reroute of traffic flows even in case of distant failures, regardless of controller availability. SPIDER can be implemented using stateful data plane abstractions such as OpenState or Open vSwitch, and it offers guaranteed short (i.e. ms) failure detection and recovery delays, with a configurable trade off between overhead and failover responsiveness. We present here the SPIDER pipeline design, behavioral model, and analysis on flow tables' memory impact. We also implemented and experimentally validated SPIDER using OpenState (an OpenFlow 1.3 extension for stateful packet processing), showing numerical results on its performance in terms of recovery latency and packet losses. A reliable and scalable mechanism to provide protection against a link or node failure has additional requirements in the context of SDN and OpenFlow. Not only it has to minimize the load on the controller, but it must be able to react even when the controller is unreachable. In this paper we present a protection scheme based on precomputed backup paths and inspired by MPLS “crankback” routing, that guarantees instantaneous recovery times and aims at zero packet-loss after failure detection, regardless of controller reachability, even when OpenFlow's “fast-failover” feature cannot be used. The proposed mechanism is based on OpenState, an OpenFlow extension that allows a programmer to specify how forwarding rules should autonomously adapt in a stateful fashion, reducing the need to rely on remote controllers. We present the scheme as well as two different formulations for the computation of backup paths. Software-defined networking provides flexibility in designing networks by allowing distributed network state to be managed by logically centralized control programs. However, this flexibility brings added complexity, which requires new debugging tools that can provide insights into network behavior. We propose a tool, SDN traceroute, that can query the current path taken by any packet through an SDN-enabled network. The path is traced by using the actual forwarding mechanisms at each SDN-enabled device without changing the forwarding rules being measured. This enables administrators to discover the forwarding behavior for arbitrary Ethernet packets, as well as debug problems in both switch and controller logic. Our prototype implementation requires only a few high-priority rules per device, runs on commodity hardware using only the required features of the OpenFlow 1.0 specification, and can generate traces in about one millisecond per hop. Managing today’s computer networks is a complex and error-prone task. These networks consist of a wide variety of devices, from routers and switches, to firewalls, network-address translators, load balancers, and intrusion-detection systems. Network administrators must express policies through tedious box-by-box configuration, while grappling with a multitude of protocols and baroque, vendor-specific interfaces. In contrast, Software-Defined Networking (SDN) is redefining the way we manage networks. In SDN, a controller application uses a standard, open messaging interface like OpenFlow [1], to specify how network elements or switches should handle incoming packets. Programmers develop their own new controller applications on top of a controller platform which provides a programming API built on top of OpenFlow. Separating the controller platform and applications from the network elements allows anyone—not just the equipment vendors—to program new network control software. In just a few years, SDN has enabled a wealth of innovation, including prominent commercial successes like Nicira’s network virtualization platform and Google’s wide-area traffic-engineering system. Most of the major switch vendors support the OpenFlow API, and many large information-technology companies are involved in SDN consortia like the Open Networking Foundation and the Open Daylight initiative. SDN is creating exciting new opportunities for networksavvy software developers and software-savvy network practitioners alike. But how should programmers write these controller applications? The first generation of SDN controller platforms offer programmers a low-level API closely resembling the interface to the switches. This forces programmers to program in “assembly language,” by manipulating bit patterns in packets and carefully managing the shared rule-table space. In the Frenetic project [2], we are designing simple, reusable, high-level abstractions for programming SDNs, and efficient runtime systems that automatically generate the low-level rules on switches [3, 4, 5, 6, 7]. Our abstractions cover the main facets of managing Figure 1: Software Defined Network (SDN)