An ISP's customers increasingly demand delivery of their traffic without congestion and with low latency. The ISP's topology, routing, and traffic engineering, often over multiple paths, together determine congestion and latency within its backbone. We first consider how to measure a topology's capacity to route traffic without congestion and with low latency. We introduce low-latency path diversity (LLPD), a metric that captures a topology's flexibility to accommodate traffic on alternative low-latency paths. We explore to what extent 116 real backbone topologies can, regardless of routing system, keep latency low when demand exceeds the shortest path's capacity. We find, perhaps surprisingly, that topologies with good LLPD are precisely those where routing schemes struggle to achieve low latency without congestion. We examine why these schemes perform poorly, and offer an existence proof that a practical routing scheme can achieve a topology's potential for congestion-free, low-delay routing. Finally we examine implications for the design of backbone topologies amenable to achieving high capacity and low delay.

Early in in the Internet's history, routing within a single provider's WAN centered on placing traffic on the shortest path. More recent traffic engineering efforts aim to reduce congestion and/or increase utilization within the status quo of greedy shortest-path first routing on a sparse topology. In this paper, we argue that this status quo of routing and topology is fundamentally at odds with placing traffic so as to minimize latency for users while avoiding congestion. We advocate instead provider backbone topologies that are more mesh-like, and hence better at providing multiple low-latency paths, and a routing system that directly considers latency minimization and congestion avoidance while dynamically placing traffic on multiple unequal-cost paths. We offer a research agenda for achieving this new low-latency approach to WAN topology design and routing.

We present FUBAR, a system that reduces congestion and maximizes the utility of the entire network by installing new routes and changing the traffic load on existing ones. FUBAR works offline to periodically adjust the distribution of traffic on paths. It requires neither changes to end hosts nor precise prior knowledge of the traffic matrix. We demonstrate that even in the presence of traffic from all network devices to all other devices, FUBAR can optimize a real-world core-level network in a matter of minutes.

We consider the intra-AS route dissemination problem from first principles, and illustrate that when known route dissemination techniques propagate even a single external routing change, they can cause transient anomalies. These anomalies are not fundamental; they are artifacts of the order in which existing proposals disseminate routes. We show that carefully ordering route updates avoids transient looping and black holes. Perhaps surprisingly, this ordering may be enforced in a completely distributed fashion, while retaining familiar correctness, scalability, and convergence properties.