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, I 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, I will present CacheFlow which helps enforce 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
iii
capacity. Since cross-rule dependencies make rule caching difficult, CacheFlow uses novel
algorithms to do dependency-aware, efficient rule caching that is transparent to control
applications.
Finally, I 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 effi-
ciently 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.