Workshop on
Foundations of Routing


A common objective in many computer networks is to balance traffic across multiple paths in order to improve throughput, reduce congestion, and achieve higher utilization. But while there is an extensive theoretical literature on how best to route traffic through a capacitated network, many networks today rely on schemes that are easy to implement but do not perform well in practice.

This workshop will bring together leading researchers and industrial practitioners from the theory and networking communities to discuss recent successes and future challenges related to routing.


June 19th, 2019
8:15am-9:00am Breakfast
9:00am-9:15am Welcome
9:15am-10:15am Synthesizing Load-Sensitive Routing Protocols for Programmable Switches
Jennifer Rexford (Princeton)
We show how a distributed set of network switches can adapt routing to traffic changes at hardware speeds. While existing work has developed point solutions for a fixed topology (e.g., a Fattree) with a fixed routing policy (e.g., use least-utilized paths), our solution can be configured to operate seamlessly over any network topology and a wide variety of sophisticated routing policies. Users write network-wide policies that rank network paths given their current performance. A compiler then analyzes such policies in conjunction with the network topology and decomposes them into switch-local P4 programs, which collectively implement a new, specialized distance-vector protocol. This protocol generates compact probes that traverse the network, gathering path metrics to optimize for the user policy dynamically. Switches respond to changing network conditions at hardware speeds by routing flowlets along the best policy-compliant paths. Our system scales to large networks, and in terms of flow completion times, is competitive with hand-crafted systems that have been customized for specific topologies and policies.
10:15am-10:30am Scalable Verification of Probabilistic Networks
Steffen Smolka (Cornell)
I will present McNetKAT, a scalable tool for verifying probabilistic network programs. McNetKAT is based on a new semantics for the guarded and history-free fragment of Probabilistic NetKAT in terms of finite-state, absorbing Markov chains. This view allows the semantics of all programs to be computed exactly, enabling construction of an automatic verification tool. Domain-specific optimizations and a parallelizing backend enable McNetKAT to analyze networks with thousands of nodes, automatically reasoning about general properties such as probabilistic program equivalence and refinement, as well as networking properties such as resilience to failures.
10:30am-11:00am Coffee Break
11:00am-12:00pm Compact Oblivious Routing
Harald Räcke (TU Munich)
Oblivious routing is an attractive paradigm for large distributed systems in which centralized control and frequent reconfigurations are infeasible or undesired (e.g., costly). Over the last almost 20 years, much progress has been made in devising oblivious routing schemes that guarantee close to optimal load and also algorithms for constructing such schemes efficiently have been designed. However, a common drawback of existing oblivious routing schemes is that they are not compact: they require large routing tables (of polynomial size), which does not scale.
This talk presents an oblivious routing scheme which guarantees close to optimal load and is compact at the same time -- requiring routing tables of polylogarithmic size. Our algorithm maintains the polynomial runtime and polylogarithmic competitive ratio of existing algorithms, and is hence particularly well-suited for emerging large-scale networks.
This is joint work with Stefan Schmid.
12:00pm-12:15pm Semi-Oblivious Traffic Engineering
Praveen Kumar (Cornell)
Networks are expected to provide reliable performance under a wide range of operating conditions, but existing traffic engineering (TE) solutions optimize for performance or robustness, but not both. A key factor that impacts the quality of a TE system is the set of paths used to carry traffic. Some systems rely on shortest paths, which leads to excessive congestion in topologies with bottleneck links, while others use paths that minimize congestion, which are brittle and prone to failure. In this talk, I will present SMORE--a TE system that uses a static set of paths based on oblivious routing, and dynamically adapts sending rates using a centralized controller. Although oblivious routing and centralized TE have been studied previously in isolation, their combination is novel and powerful. We built a software framework to model TE solutions and conducted extensive experiments across a large number of topologies and scenarios, including the production backbone of a large content provider and an ISP. Our results show that semi-oblivious routing provides near-optimal performance and is far more robust than state-of-the-art systems.
12:00pm-1:30pm Lunch
1:30pm-2:30pm TeaVaR: Striking the Right Utilization-Availability Balance in WAN Traffic Engineering
Manya Ghobadi (MIT)
To keep up with the continuous growth in demand, cloud providers spend millions of dollars augmenting the capacity of their wide-area backbones and devote significant effort to efficiently utilizing WAN capacity. A key challenge is striking a good balance between network utilization and availability, as these are inherently at odds; a highly utilized network might not be able to withstand unexpected traffic shifts resulting from link/node failures. We advocate a novel approach to this challenge that draws inspiration from financial risk theory: leverage empirical data to generate a probabilistic model of network failures and maximize bandwidth allocation to network users subject to an operator-specified availability target (e.g., 99.9% availability). Our approach enables network operators to strike the utilization-availability balance that best suits their goals and operational reality. In this talk, I will present TeaVaR (Traffic Engineering Applying Value at Risk), a system that realizes this risk management approach to traffic engineering (TE). I will explain the optimization formulation and show that with TeaVaR operators can support up to twice as much throughput as state-of-the-art TE schemes, at the same level of availability.
2:30pm-3:30pm Routing via Network Design: Overlay Routing with Dissemination Graphs
Michael Dinitz (JHU)
Emerging applications such as remote manipulation and remote robotic surgery require communication that is both timely and reliable, but the Internet natively supports only communication that is either completely reliable with no timeliness guarantees (e.g., TCP) or timely with best-effort reliability (e.g., UDP). Is there a practical way, with theoretical justification, that will allow us to achieve both? In this talk I will discuss a system and supporting theory that uses overlay networks and structures which we call "dissemination graphs" to achieve this. The core idea is to route along subgraphs, rather than along paths. This allows us to turn routing problems into network design problems, which we can then design efficient algorithms for. In particular, we study the fixed-parameter tractability of the key algorithmic problem, deriving FPT algorithms for some important cases (which we can use in our system) and proving intractability in others (forcing our system to use heuristics).
3:30pm-4:00pm Coffee Break
4:00pm-5:00pm Traffic Engineering with Forward Fault Correction
Hongqiang Liu (Alibaba Group)
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 long—even 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.
6:30pm-8:30pm Dinner
June 20th, 2019
8:30am-9:00am Breakfast
9:00am-10:00am Parallel Reachability in Almost Linear Work and Square Root Depth
Aaron Sidford (Stanford)
Solving single source reachability, i.e. computing all vertices reachable from a given vertex, is perhaps one of the simplest and most well-studied graph optimization and routing problems. While obtain work-efficient parallel algorithms for this problem in undirected graphs is trivial, obtaining comparable results for directed graphs is notoriously difficult and a key barrier towards obtaining a broader range of parallel graph algorithms. In this talk I will present recent work which shows that this problem can be solved with nearly linear work and parallel depth proportional to the square root of the number of vertices in the graph, improving upon the previous best depth bound achieved by Fineman in 2018. Further, I will discuss how these result lead to the near optimal distributed algorithms for directed reachability in the CONGEST model in certain parameter regimes.
This talk reflects joint work with Arun Jambulapati and Yang P. Liu and is based on
10:00am-10:30am Intent-Driven Optimization of Network Objectives: Preliminary work and open challenges
Vyas Sekar (CMU)
As software-defined networking deployments mature, operators need to manage and compose multiple resource-management applications, such as traffic engineering and service chaining. Today such applications’ resource management algorithms run separately and composition approaches are output-driven, e.g., running each application on a statically provisioned slice of the network and then combining the flow rules output for each slice. Such approaches result in inefficient use of developer time, resource utilization, and unfairness. Instead, we argue for intent-driven optimization and composition, where a unified resource optimization formulation is composed from applications’ high-level intents and the solution to this problem formulation is realized in the network. In this talk, we will provide a brief overview of our recent work in this space (SOL [NSDI'16] and Chopin [Conext'18]) and present some potential open problems in this space.
10:30am-11:00am Coffee Break
11:00am-12:00pm Scalable Routing Strategies for Network Robustness
Marco Chiesa (KTH)
Network operators have long relies on a variety of route computation approaches to make efficient utilization of network resources. Unfortunately, failures of network devices and highly variable traffic conditions make this routing operation a gruelling task. Sudden changes in the network conditions may, in fact, lead to severe routing performance degradation (e.g., packet losses, increased delays). To address this problem, extensive efforts have been devoted to proactive routing approaches, in which operators precompute routing solutions that are robust to a variety of changes in the network conditions. In this talk, we will embark upon a systematic algorithmic study of the resiliency of forwarding tables in a variety of packet processing models (i.e., deterministic/probabilistic routing, with packet-header-rewriting, with packet-duplication, dynamic tables). Surprisingly, our results show that significant network resiliency can be achieved even in the simplest and highly scalable per-destination routing models.
12:00pm-12:15pm Wrapup
12:15pm-1:30pm Lunch


Johnson Museum

The workshop will be held on the 6th floor of the Johnson Museum at Cornell University.


Ithaca is served by Ithaca Tompkins (ITH) and Syracuse Hancock (SYR) airports. The Ithaca airport is about 10 minutes from campus while Syracuse is about an hour and 10 minutes away. Currently, American Airlines has flights to Ithaca via Philadelphia, United has flights via Dulles, and Delta has flights via Detroit. It is generally most convenient to fly to the Ithaca airport, but Syracuse has more options.

For visitors coming from within a three to four hour radius of Ithaca, it may be simplest to drive. From the south or east (e.g., Boston, NYC), take I-81 to NY-79 West to Ithaca. From the north (e.g., Rochester, Toronto), take I-90 to 81-South, to NY-212 South, to US-13 South to Ithaca.

For visitors coming from New York City, another good option is to take Cornell's Campus-to-Campus Shuttle. The shuttle takes about four hours and the bus is equipped with comfortable seats, a work table, wireless Internet, and a snack bar.


Parking on campus is limited. We recommend parking at the Forest Home Parking Garage. For detailed information regarding parking options, please visit Cornell Transportation.


We recommend booking a room at one of the following hotels:


The workshop is open to researchers in both industry and academia at no cost; however space is limited and will be allocated on a first-come, first-serve basis.

Please register here at your earliest convenience. For questions, contact Jenna Edwards.


Nate FosterCornell University
Dexter KozenCornell University
Robert KleinbergCornell University
Praveen KumarCornell University

Funding for this workshop is generously provided by the NSF under the Algorithms in the Field program, and the Cornell-Princeton Network Programming Initiative.