Title: Fast Control Plane Analysis Using an Abstract Representation

Modern networks employ complex, and hence error-prone, routing control plane configurations. In many cases, the impact of errors manifests only under failures, leading to devastating effects. Thus, it is important to proactively verify control plane behavior under arbitrary link failures.

State-of-the-art control plane verifiers are either too slow or impractical to use for such verification tasks. We propose a new high level abstraction for control planes, ARC, that supports fast control plane analyses under arbitrary failures. ARC's directed graph abstraction transforms the problem of checking key invariants into that of solving graph problems with known polynomial-time algorithms. ARC does not need to generate the data planewhich is the main reason for current tools' ineffectiveness.

In this talk, I will describe the algorithms we have developed to derive a network's ARC from its configuration files, and show how it can be used in proactive control plane verification. I will also talk about our current efforts on using ARC to automatically synthesize a control plane that offers provably safe behavior under arbitrary failures. I will present results from our study covering 314 data center networks whose control planes we verified using ARC.

Title: UnivMon: Software-defined Monitoring with Universal Sketch

In this work, we present UnivMon, a framework for flow monitoring which leverages recent theoretical advances in streaming algorithms---Universal Sketches and demonstrates that it is possible to achieve both generality and high accuracy on estimating metrics. UnivMon uses an application-agnostic data plane monitoring primitive; different (and possibly unforeseen) estimation algorithms run in the control plane, and use the statistics from the data plane to compute application-level metrics. We evaluate the effectiveness of UnivMon using a range of trace-driven evaluations and show that it offers comparable (and better) accuracy relative to custom sketching solutions.

In this talk, we will focus on the algorithmic details of universal sketches and the system design of UnivMon on SDN. Joint Work with (Greg Vorsanger (JHU), Antonis Manousis (CMU), and Vyas Sekar (CMU)

Title: Don't disturb my Flows: Consistent Migration in SDNs

The rise of Software Defined Networks has sparked an increasing interest in applying network flow algorithms to utilize the available bandwidth almost completely. Should new data flows appear or old flows change their traffic demands, one can use the established toolkit of multi-commodity flow theory to calculate a new network behavior optimized for efficiency. But, while the new network behavior might be optimal, what happens during the migration to the new behavior? Although the SDN controller is (logically) centralized, the network itself is still a distributed system. Thus, the inherent asynchrony will lead to over-utilization of links during the migration, inducing congestion and packet loss. In this talk, we focus on how to mitigate these negative migration effects by updating the network in a consistent manner, trading migration speed for reduced congestion. (Joint work with Sebastian Brandt, Laurent Vanbever, and Roger Wattenhofer)

Title: Kulfi: Robust Traffic Engineering Using Semi-Oblivious Routing

Wide-area network traffic engineering enables network operators to reduce congestion and improve utilization by balancing load across multiple paths. Current approaches to traffic engineering can be modeled in terms of a routing component that computes forwarding paths, and a load balancing component that maps incoming flows onto those paths dynamically, adjusting sending rates to fit current conditions.

Unfortunately, existing systems rely on simple strategies for one or both of these components, which leads to poor performance or requires making frequent updates to forwarding paths, significantly increasing management complexity. This talk explores a different approach based on semi-oblivious routing, a natural extension of oblivious routing in which the system computes a diverse set of paths independent of demands, but also dynamically adapts sending rates as conditions change.

Semi-oblivious routing has a number of important advantages over competing approaches including low overhead, nearly optimal performance, and built-in protection against unexpected bursts of traffic and failures. Through in-depth simulations and a deployment on SDN hardware, we show that these benefits are robust, and hold across a wide range of topologies, demands, resource budgets, and failure scenarios.

Joint work with Praveen Kumar (Cornell), Yang Yuan (Cornell), Chris Yu (CMU), Bobby Kleinberg (Cornell / MSR), and Robert Soule (Lugano)

Title: Simplifying Network Optimization for SDN Deployment

Realizing the benefits of SDN for many network management applications (e.g., traffic engineering, service chaining) involves addressing complex optimizations that are central to these problems. Unfortunately, deployment of these applications is made very difficult because of multiple challenges: 1) optimization problems require significant manual effort and expertise to express, 2) optimizations require non-trivial computation, and 3) composition of multiple applications is prone to errors and misconfigurations. Our work simplifies the deployment of SDN applications using general high-level abstractions for capturing optimization requirements, from which we can efficiently generate near-optimal solutions.

Title: High Speed Networks Need Proactive Congestion Control

As datacenter speeds scale to 100Gbps and beyond, typical flows will complete in a few RTTs. In such scenarios, traditional congestion control algorithms like TCP and RCP which have large convergence times will lead to poorer and less predictable user performance. Poor convergence times is caused by these algorithms being reactive : they perform gradient descent to compute rates in reaction to a congestion signal. We explore proactive congestion control algorithms that explicitly compute rates and and can be implemented at line rates in programmable hardware. Such algorithms can improve convergence times by an order of magnitude compared to RCP.

Title: Traffic Engineering with Forward Fault Correction

Network faults such as link failures and high switch configuration delays can cause heavy congestion and packet loss. Because it takes time for the traffic engineering systems to detect and react to such faults, these conditions can last longeven tens of seconds. We propose the concept of “Forward Fault Correction (FFC)” which proactively prevents a network from congestion caused by faults. FFC requires a traffic engineering (TE) to guarantee no congestion without reconfiguring the network as long as the number of faults is under k. The challenges to realize FFC lie in the overhead in network throughput and the computational complexity to prepare for a huge number of fault cases. We develop an efficient and uniform method to obtain a TE with FFC under diverse kinds of faults.

Title: A Universal Approach to Data Center Network Design

This talk proposes an approach to the design of large-scale general-purpose data center networks based on the notions of volume and area universality introduced by Leiserson in the 1980's in the context of VLSI design. In particular, we suggest that the principle goal of the network designer should be to build a single network that is provably competitive, for any application, with any network that can be built for the same amount of money. We illustrate our approach by walking through the design of a hierarchical data center network using the various networking components available today commercially.

The talk is based on a joint work with Aditya Akella, Theo Benson, Bala Chandrasekaran, Cheng Huang, and David Maltz.

Title: Bridging the Gap between Centralized Programming and Distributed Operation

Can network operators get the best of both worlds---the simplified policy specification of the centralized control planes (i.e., SDN-based networks) and the scalability and failure-robustness of distributed control planes (e.g., BGP-based networks)? I will describe techniques that enable this vision. They allow operators to centrally specify routing policies and compile these specifications to configurations of devices that run distributed routing protocols. I will also describe our experience of applying these techniques to policies and networks of a large cloud provider.

Title: Layering, Dynamics, Control and Optimization in Software Defined Networks

SDN allows great flexibility in allocating network functionality (including (de)centralization and layering) but the full benefits of this flexibility cannot be fully exploited without theory and tools to guide engineering design choices. This talk describes recent progress on a theory of network architecture that explicitly treats layering, dynamics, distributed/localized optimal control, and control infrastructure co-design in a unified and principled manner. We illustrate the benefits of this approach on a SDN enabled traffic control problem for wide area networks through simulation, emulation and experimental results.

Title: Competitive Path Computation and Function Placement in SDNs

We consider a task of serving requests that arrive in an online fashion in Software-Defined Networks (SDNs) with network function virtualization (NFV). Each request specifies an abstract routing and processing "plan" for a flow. Each processing function can be performed by a specified subset of servers in the system. The algorithm needs to either reject the request or admit it and return detailed routing (a.k.a. "path computation") and processing assignment ("function placement"). Each request also specifies the communication bandwidth and the processing load it requires. Components in the system (links and processors) have bounded capacity; a feasible solution may not violate the capacity constraints. Requests have benefits and the goal is to maximize the total benefit of accepted requests. In this paper we first formalize the problem, and propose a new service model that allows us to cope with requests with unknown duration. The new service model augments the traditional accept/reject schemes with a new possible response of "stand by." Our main result is an online algorithm for path computation and function placement that guarantees, in each time step, throughput of at least Ω(OPT*logn), where n is the system size and OPT* is an upper bound on the maximal possible throughput. The guarantee holds assuming that requests ask for at most an O(1/logn)-fraction of the capacity of any component in the system. Furthermore, the guarantee holds even though our algorithm serves requests in an all-or-nothing fashion using a single path and never preempts accepted flows, while OPT* may serve fractional requests, may split the allocation over multiple paths, and may arbitrarily preempt and resume service of requests.

Joint work with Guy Even and Boaz Patt-Shamir.

Title: Network Optimization for Search via Consistent Hashing and Balanced Partitioning

In this talk, I will survey two recent results in network optimization in search. First, I will present a new consistent hashing scheme that can handle hard capacity constraints in dynamic environments where both clients(balls) and servers(bins) can be added or removed. Finally, I'll demonstrate how an improved distributed graph partitioning algorithm helped us improve the flash bandwidth for backend of search, and elaborate on balanced partitioning algorithm.

Title: Universal Packet Scheduling

In this work we address a seemingly simple question: Is there a universal packet scheduling algorithm? More precisely, we analyze (both theoretically and empirically) whether there is a single packet scheduling algorithm that, at a network-wide level, can perfectly match the results of any given scheduling algorithm. We find that in general the answer is "no". However, we show theoretically that the classical Least Slack Time First (LSTF) scheduling algorithm comes closest to being universal and demonstrate empirically that LSTF can closely replay a wide range of scheduling algorithms in realistic network settings. We then evaluate whether LSTF can be used in practice to meet various network-wide objectives by looking at popular performance metrics (such as mean FCT, tail packet delays, and fairness); we find that LSTF performs comparable to the state-of-the-art for each of them. We also discuss how LSTF can be used in conjunction with active queue management schemes without changing the core of the network.

Title: Practical, Real-time Centralized Control for CDN-based Live Video Delivery

Live video delivery is expected to reach a peak of 50 Tbps this year. This surging popularity is fundamentally changing the Internet video delivery landscape. CDNs must meet users' demands for fast join times, high bitrates, and low buffering ratios, while minimizing their own cost of delivery and responding to issues in real-time. Wide-area latency, loss, and failures, as well as varied workloads ("mega-events" to long-tail), make meeting these demands challenging.

An prior analysis of video sessions concluded that a centralized controller could improve user experience, but CDN systems have shied away from such designs due to the difficulty of quickly handling failures, a requirement of both operators and users. We introduce VDN, a practical approach to a video delivery network that uses a centralized algorithm for live video optimization. VDN provides CDN operators with real-time, fine-grained control. It does this in spite of challenges resulting from the wide-area (e.g., state inconsistency, partitions, failures) by using a hybrid centralized+distributed control plane, increasing average bitrate by 1.7x and decreasing cost by 2x in different scenarios.

Title: Multi-Commodity Flow with In-Network Processing

We introduce and study a new class of multi-commodity flow problems where, in addition to demands on flows and capacity constraints on edges in the network, there is an additional requirement that flows be processed by nodes in the network. These problems are motivated by the placement and configuration of middleboxes at nodes in the network so as to perform services on the network traffic: how many middleboxes to run, where to place them, and how to direct traffic through them? We study the problems that arise from jointly optimizing the: (1) placement of middleboxes over a pool of server resources, (2) steering of traffic through a suitable sequence of middleboxes, and (3) routing of the traffic between the servers over efficient network paths. We introduce and study several problems in this class from the exact and approximation point of view.

Title: Consistency in Software Defined Networks

A large body of SDN research has focused on achieving consistency, for both the rules installed in the data plane and between distributed SDN controllers. As a result, today we can find controllers guaranteeing exactly once semantics while processing events, a large number of algorithms for ensuring packets are processed by a single policy version, and recent OpenFlow versions support a form of compare-and-swap on switches. However, networks were traditionally eventually consistent, and even today most large network deployments remain eventually consistent. In this talk we take a step back and ask is consistency required, and does it impose any costs. We look at both requirement and costs in terms of (a) the set of network level objectives that can be met with and without consistency; and (b) the percentage of time (given a failure model) the objectives are met. Finally we ask if there are algorithmic mechanisms that would allow networks to eschew the use of consistency mechanisms, while still achieving semantics similar to what is achievable with consistency mechanisms.

Title: Routing in Cost-shared Networks: Equilibria and Dynamics

In this talk, I will discuss how a network administrator/designer can efficiently route traffic in environments where a fixed cost for a network element is shared equally between the users using it. I will talk about both static and dynamic settings, based on whether the set of users is fixed or users can join and leave the network over time, and describe how the degree of control available to the administrator dictates the quality of solutions obtained. This is based on joint works with Rupert Freeman and Sam Haney, and with Shuchi Chawla, Seffi Naor, Mohit Singh, and Seeun Umboh.

Title: Flowlet Control for Datacenter Network

Traditionally, congestion control decisions are distributed across the network endpoints, which vary their offered load in response to changes in application demand and network feedback on a packet-by-packet basis. We propose a different approach for datacenter networks, flowlet control, in which congestion control decisions are made at the granularity of a flowlet, not a packet. With flowlet control, allocations have to change only when flowlets arrive or leave.

We have implemented this idea in a system called Flowtune using a centralized allocator that receives flowlet start and end notifications from endpoints. The allocator computes optimal rates using a new, fast method for network utility maximization, and updates endpoint congestion-control parameters. Experiments show that Flowtune outperforms DCTCP, pFabric, sfqCoDel, and XCP on tail packet delays in various settings, converging to optimal rates within a few packets rather than over several RTTs.

Title: A Concise Forwarding Information Base for Scalable and Fast Name Switching

Forwarding information base (FIB) scalability is a fundamental problem of numerous new network architectures that propose to use location-independent network names. We propose Concise, a FIB design that uses very little memory to support fast query of a large number of location-independent names. Concise makes use of an innovative data structure Othello. Othello relies on the SDN framework and supports fast name classification. We optimize the memory efficiency and query speed of Othello in the data plane and move the relatively complex construction and update components to the resource-rich control plane.

We have successfully implemented Concise on three platforms. Experimental results show that Concise uses significantly smaller memory to achieve faster name query speed compared to existing FIBs for name switching.

Title: Approximation Algorithms for Coflow Scheduling

Many modern datacenter applications involve large-scale computations composed of multiple data flows that need to be completed over a shared set of distributed resources. Such a computation completes when all of its flows complete. A useful abstraction for modeling such scenarios is a coflow, which is a collection of flows (e.g., tasks, packets, data transmissions) that all share the same performance goal.

We present asymptotically optimal approximation algorithms for scheduling coflows over general network topologies with the objective of minimizing total weighted completion time. We consider three different models for coflows based on the nature of individual flows: tasks, packets, and circuits. We design constant-factor polynomial-time approximation algorithms for scheduling task-based coflows, packet-based coflows with given flow paths, packet-based coflows where flow paths are not given, and circuit-based coflows with given flow paths. Finally, we give a sub-logarithmic-approximation polynomial time algorithm for scheduling circuit-based coflows where flow paths are not given.

(Joint work with Hamid Jahanjou and Erez Kantor.)

Title: Robust Network Design with Flexible Routing

A key challenge confronting network designers is verifying that their networks can properly cope with a wide range of traffic conditions and failure scenarios, and designing networks to meet this objective. Since many design choices (e.g., topology design, middlebox placement) are made over longer time-scales and cannot be easily adapted, it is important to make these choices in a manner robust to traffic demands and failure scenarios. In this paper, we develop an optimization-theoretic framework to provide guaranteed bounds on link utilization across traffic patterns and failure scenarios of interest, a well as help design networks with guaranteed bounds. The key novelty of our framework is that while some design choices (e.g., middlebox placement) are made in a manner robust to traffic demand, other decisions, especially the actual routing strategy may be optimized for a specific traffic demand. Considering flexible routing strategies is important since oblivious strategies can be unduly conservative, but poses theoretical challenges that we address. We apply our framework to multiple case studies including design of MPLS tunnels, and routing in the presence of middleboxes. Evaluations over real network topologies and traffic data show the promise of the approach.

Title: States on a (Data) Plane

States on a (Data) Plane: The focus will be on leveraging the capabilities of emerging switching chipsets that can read-modify-write state in the data plane, and carry state on packets from one hop to the next, to measure and control networks without the direct involvement of the controller.

Title:The Art of Consistent SDN Updates

Title: Path Switching: Reduced-State Micro-Flow Handling in SDN

Packet networks need to maintain state in the form of forwarding tables at each switch. The cost of this state increases as networks support ever more sophisticated per-flow routing, traffic engineering, and service chaining. Per-flow or per-path state at the switches can be eliminated by encoding each packet's desired path in its header. A key component of such a Path Switching method is an efficient encoding of paths. We introduce a mathematical formulation of this optimal path-encoding problem and prove that the problem is APX-hard, by showing that approximating it to within a factor less than 8/7 is NP-hard. A polynomial time algorithm for approximating the problem to within a factor of 2 is shown. Empirical results illustrating the effectiveness of Path Switching are given. Finally, we consider the problem of efficiently routing multicast demands in a Path Switching network. (Joint work with H. Adiseshu (Bell Labs), T.V. Lakshman (Bell Labs) and U. Niesen (Qualcomm).)

Title: Magellan: Toward Automatic Multi-Table SDN Programming

Multi-table pipelining has emerged as a key technique for the next-generation SDN data path. Programming such a data path model, however, can be challenging. In this talk, I will discuss several algorithmic challenges in programming multi-table pipelines.