Our end goal is that network problems can be identified in realtime, rather than today's matter of hours. While automated diagnosis and identification of root cause is fundamentally hard, our project benefits from dramatic recent progress in Internet measurement technologies, specifically reverse path measurement, that provides a much more complete picture of the Internet topology than ever before.

We obtained the following results:

(a) Probabilistic analysis of root cause and AS relationship inference: We developed a new algorithm for inferring business relationships between Autonomous Systems (ASes) from publicly available BGP paths. Unlike previous approaches, our algorithm does not depend on pre-defined characteristics of BGP policies, such as valley-free routing. Instead, we build a probabilistic model by learning patterns in historical BGP data. We identify a key set of route features that are highly predictive. Our algorithm, which makes relationship predictions based on a weighted sum of these route features, consistently achieves 99% prediction accuracy (less than 1% error rate) over 3-4 years of routing data, reducing significantly the error rate of state-of-the-art algorithm. The predictiveness of these features leads us to believe that we have identified underlying structures of AS relationships---particular hybrid AS relationships---that were not previously understood.

(b) Automated diagnosis of performance problems due to problems in the optical network: To confirm and quantify physical layer over-engineering in today's datacenters, we conduct what to our knowledge is the first large-scale study of operational optical links. We analyzed over 300K links across more than 20 datacenters of a large cloud provider over a period of 10 months. We find a remarkably conservative state of affairs---99.9% of the links have incoming optical signal quality that is higher than the minimum threshold for BER, while the median is 6 times higher! We then designed a practical system that builds multiple virtual topologies on the same physical topology, where the class of the topology offers a bound on the maximum packet error rate (i.e., grayness) on any path in it. The first-class topology does not have any gray paths; hence, it offers the same path packet error rate guarantee as current DCN designs offer. Other classes increasingly use more gray links. Each application uses the virtual topology that meets its needs. Thus, loss tolerant applications use virtual topologies that may have more gray paths. To support applications, such as large transfers that are otherwise loss-tolerant but suffer when the transport protocol (e.g., TCP) is sensitive to losses, Rail uses a transparent coding-based error correction scheme. We develop an efficient algorithm to compute virtual topologies that leverages the topological structure of DCNs. Rail is easily deployable as it requires no changes to the switch or transceiver hardware. We evaluated Rail using simulations-based analysis and a testbed. Even at the maximum stretched reach level we consider, we find 95% of all paths are as reliable as today. Furthermore, Rail successfully protects loss-sensitive applications from gray paths.

(c) Analysis of packet losses of microbursts inside datacenters: Our primary result is to provide a high-resolution characterization of a production data center network. To do so, we developed a custom high-resolution counter collection framework on top of the data center operator's in-house switch platform. This framework is able to poll switch statistics at a 10s to 100s of microseconds granularity with minimal impact on regular switch operations. With the framework, we proceed to perform a data-driven analysis of various counters (including packet counters and buffer utilization statistics) from Top-of-Rack (ToR) switches in multiple clusters running multiple applications. While our measurements are limited to ToR switches, our measurements and prior work indicate that the majority of congestion occurs at that layer. Our main findings include: (1) micro-bursts, periods of high utilization lasting less than 1ms, exist in production data centers, and in fact, they encompass most congestion events. (2) Link utilization is multimodal; when bursts occur, they are generally intense. (3) At small timescales, many multi-statistic features become possible to measure: load can be very unbalanced, packets tend to be larger inside bursts than outside, and buffers are related to simultaneous bursts in a nonlinear fashion.

Last Modified: 11/30/2017
Modified by: Arvind Krishnamurthy