BUILDING EFFICIENT AND RELIABLE SOFTWARE-DEFINED NETWORKS

Abstract

Software-defined networking (SDN) promises flexible control of computer networks by orchestrating switches in the network dataplane through a centralized controller. However, despite this promise, operators used to fast and fault-tolerant routing using traditional protocols face three important problems while deploying SDN. One, the control plane timescales are too slow to enforce effective load balancing in order to efficiently use the available network capacity. Second, the commodity SDN switches have limited memory to enforce fine-grained policy rules which undermines the promise of flexible control. Third, the centralized controller itself is a single point of failure which is unacceptable for operators used to running distributed fault-tolerant network protocols. This thesis aims to mitigate these problems using novel algorithms that exploit advanced data plane capabilities and enhancements to the control plane software. At the same time, we also provide simple abstractions on top of these systems so that network operators writing control programs need not worry about low-level details of the underlying implementation mechanisms. First, we will present HULA, which gives the abstraction of one big efficient non-blocking switch. Instead of asking the control plane to choose the best path for each new flow, HULA efficiently routes traffic on least congested paths in the network. HULA uses advanced hardware data plane capabilities to infer global congestion information and uses that information to do fine-grained load balancing at RTT timescales. HULA is congestion-aware, scales to large topologies and is robust to topology failures. Second, we will present CacheFlow which helps enforcing fine-grained policies by proposing the abstraction of a switch with logically infinite rule space. CacheFlow uses a combination of software and hardware data paths to bring the best of both worlds to policy enforcement. By dynamically caching a small number of heavy hitting rules in the hardware switch and the rest of the rules in the software data path, it achieves both high throughput and high rule capacity. Since cross-rule dependencies make rule caching difficult, CacheFlow uses novel algorithms to do dependency-aware, efficient rule caching in a way transparent to control applications . Finally, we will present Ravana which gives the abstraction of one logically centralized controller. Given this abstraction, the network operator only writes programs for one controller and the Ravana runtime takes care of replicating the control logic for fault-tolerance. Since network switches carry additional state external to the controller state, Ravana uses an enhanced version of traditional replicated state machine protocols to ensure ordered and exactly-once execution of network events. Together these systems propose a new SDN paradigm where basic routing is done efficiently at dataplane timescales, policy enforcement is done scalably with the help of software data planes and the control plane is fault-tolerant. This new architecture has the properties of fast routing and fault-tolerance of traditional networks while delivering the promise of efficient enforcement of fine-grained control policies.