We describe our experience with Fathom, a system for identifying the network performance bottlenecks of any service running in the Google fleet. Fathom passively samples RPCs, the principal unit of work for services. It segments the overall latency into host and network components with kernel and RPC stack instrumentation. It records these detailed latency metrics, along with detailed transport connection state, for every sampled RPC. This lets us determine if the completion is constrained by the client, network or server. To scale while enabling analysis, we also aggregate samples into distributions that retain multi-dimensional breakdowns. This provides us with a macroscopic view of individual services. Fathom runs globally in our datacenters for all production traffic, where it monitors billions of TCP connections 24x7. For five years Fathom has been our primary tool for troubleshooting service network issues and assessing network infrastructure changes. We present case studies to show how it has helped us improve our production services.

Teaching computer programming to K-12 learners is widely recognized as important for invoking interest in computing in college and beyond. Specifically, with respect to middle school students, several computing education efforts do an excellent job of making the curricula engaging through block-based and multimedia project-based content. However, the programming concepts covered are notably and understandably simpler than those covered in college-level AP CS or CS1. We instead believe that today's college-level CS1 curricula can and should be taught to middle school and early high school students. In this paper, we discuss our efforts in adapting the CS1 course offered at a large public university, for teaching programming to this age group. Over the course of 15 months, we designed and taught the adapted 16-lecture course to multiple sections of middle and early high school students (ranging from 6th to 10th grade and beyond). Our adaptations included persistent use of memory diagrams, extensive practice, and engaging reviews. Analysis of the final course assessment and surveys showed that these students were able to learn CS1 concepts in depth. Our results held regardless of grade level, mathematics knowledge, and acceleration level, but varied with students absences and gender. We urge the CS education community to adopt our approach widely.

Current computing education efforts do an excellent job of designing engaging curricula for middle school students through block-based platforms and multimedia project-based content. However, the programming concepts covered are notably and understandably simpler than those covered in college-level AP CS or CS1. In this paper, we present a new position that today's college-level CS1 curricula can and should be taught to middle school and early high school students. We discuss our efforts in teaching Python programming to this age group by adapting the pedagogical techniques of the CS1 course offered at a public university. Preliminary observations from an 8-week summer pilot study involving 7th - 10th grade students suggest that these students can learn CS1 concepts in depth when memory diagrams, extensive practice, and engaging reviews are relied upon.

Webpage fingerprinting methods infer the webpages visited in a traffic trace and are serious threats to the privacy of web users. Prior work evaluates webpage fingerprinting methods using traffic samples from a single client and does not consider the client diversity factor---webpages can be visited using different browsers, operating systems and devices. In this paper, we study the impact of client diversity on HTTPS webpage fingerprinting. First, we evaluate 5 prominent fingerprinting methods using traffic samples from 19 different clients. We show that the best performing methods overfit to the traffic patterns of a single client and do not generalize when they are evaluated using the samples from a different client (even if the clients use the same browser and operating system and only differ in device). Then, we investigate the traffic patterns of the clients and find differences in the HTTP messages generated, servers communicated and implementation of HTTP/2 across the clients. Finally, we show that the robustness of the methods can be increased by training them using the samples from a diverse set of clients. This study informs the community towards a realistic threat model for HTTPS webpage fingerprinting and presents an analysis of modern HTTPS traffic.

Abstract Website fingerprinting based on TCP/IP headers is of significant relevance to several Internet entities. Prior work has focused only on a limited set of features, and does not help understand the extents of fingerprint-ability. We address this by conducting an exhaustive feature analysis within eight different communication scenarios. Our analysis helps reveal several previously-unknown features in several scenarios, that can be used to fingerprint websites with much higher accuracy than previously demonstrated. This work helps the community better understand the extents of learnability (and vulnerability) from TCP/IP headers.

Delay and rate-based alternatives to TCP congestion-control have been around for nearly three decades and have seen a recent surge in interest. However, such designs have faced significant resistance in being deployed on a wide-scale across the Internet - this has been mostly due to serious concerns about noise in delay measurements, pacing inter-packet gaps, and/or required changes to the standard TCP stack/headers. With the advent of high-speed networking, some of these concerns become even more significant. In this paper, we consider Rapid, a recent proposal for ultra-high speed congestion control, which perhaps stretches each of these challenges to the greatest extent. Rapid adopts a framework of continuous fine-scale bandwidth probing, which requires a potentially different and finely-controlled gap for every packet, high-precision timestamping of received packets, and reliance on fine-scale changes in inter-packet gaps. While simulation-based evaluations of Rapid show that it has outstanding performance gains along several important dimensions, these will not translate to the real-world unless the above challenges are addressed. We design a Linux implementation of Rapid after carefully considering each of these challenges. Our evaluations on a 10Gbps testbed confirm that the implementation can indeed achieve the claimed performance gains, and that it would not have been possible unless each of the above challenges was addressed.

This paper presents the packet-scale paradigm for designing end-to-end congestion control protocols for ultra-high speed networks. The paradigm discards the legacy framework of RTT-scale protocols, and instead builds upon two revolutionary foundations-that of continually probing for available bandwidth at short timescales, and that of adapting the data sending rate so as to avoid overloading the network. Through experimental evaluations with a prototype, we report high performance gains along several dimensions in high-speed networks-the steady-state throughput, adaptability to dynamic cross-traffic, RTT-fairness, and co-existence with the conventional TCP traffic mixes. The paradigm also opens up several issues that are less of a concern for traditional protocols-we summarize our approaches for addressing these.

The ability to identify mobile apps in network traffic has significant implications in many domains, including traffic management, malware detection, and maintaining user privacy. App identification methods in the literature typically use deep packet inspection (DPI) and analyze HTTP headers to extract app fingerprints. However, these methods cannot be used if HTTP traffic is encrypted. We investigate whether Android apps can be identified from their launch-time network traffic using only TCP/IP headers. We first capture network traffic of 86,109 app launches by repeatedly running 1,595 apps on 4 distinct Android devices. We then use supervised learning methods used previously in the web page identification literature, to identify the apps that generated the traffic. We find that: (i) popular Android apps can be identified with 88% accuracy, by using the packet sizes of the first 64 packets they generate, when the learning methods are trained and tested on the data collected from same device; (ii) when the data from an unseen device (but similar operating system/vendor) is used for testing, the apps can be identified with 67% accuracy; (iii) the app identification accuracy does not drop significantly even if the training data are stale by several days, and (iv) the accuracy does drop quite significantly if the operating system/vendor is very different. We discuss the implications of our findings as well as open issues.

Web page classification is useful in many domains- including ad targeting, traffic modeling, and intrusion detection. In this paper, we investigate whether learning-based techniques can be used to classify web pages based only on anonymized TCP/IP headers of traffic generated when a web page is visited. We do this in three steps. First, we select informative TCP/IP features for a given downloaded web page, and study which of these remain stable over time and are also consistent across client browser platforms. Second, we use the selected features to evaluate four different labeling schemes and learning-based classification methods for web page classification. Lastly, we empirically study the effectiveness of the classification methods for real-world applications.

The structure of the web has been extensively studied using HTML-based data. However, the increase in dynamic and personalized content has made the analysis of HTML-based data more difficult. A viable alternative to studying the web using HTML data is to study the web using DNS traffic traces. In this paper, we conduct a preliminary study to investigate the question - What can DNS traffic traces tell us about the structure of the web? In particular, we analyze the connectivity properties of this web graph by using eigenvalue analysis and spectral clustering. We also discuss the implications of this analysis with respect to web development and user privacy.

Modern web pages are diverse and complex. There is also a wide range of devices, operating systems, and browsers that users use to access these web pages. In this work, we study how web pages, and the traffic generated by their download, differ across these different client types. We conduct a preliminary study that performs a client-side analysis of the network traffic. We identify both expected and unexpected differences among similar web pages across different browser platforms that can be used to drive future internet measurement research and identify potential design decisions and/or bugs in modern browsers.

While existing bandwidth estimation tools have been shown to perform well on 100Mbps networks, they fail to do so at gigabit and higher network speeds. This is because finer inter-packet gaps are needed to probe for higher rates -- fine gaps are more susceptible to be disturbed by small-scale buffering-related noise. In this paper, we evaluate existing noise reduction techniques for tackling the issue, and show that they are ineffective on 10Gbps links. We propose a novel smoothing strategy, Buffering-aware Spike Smoothing (BASS), which can be applied effectively to both single-rate and multi-rate probing frameworks and help significantly in scaling bandwidth estimation to ultra-high speed networks. Besides, we provide first evidence that accurate bandwidth estimation using our strategy can help improve the performance of congestion-control protocols on real 10Gbps networks.

The packet-scale paradigm is a novel framework for achieving ultra-high speed congestion control. Due to its reliance on finely-controlled inter-packet gaps, the paradigm is expected to be sensitive to transient burstiness in traffic encountered on bottleneck links. This paper uses a first-principles approach to study the impact of cross traffic burstiness on the efficiency of the packet-scale paradigm. It relies on a simple periodic on-off model for cross traffic and studies the interaction of the burstiness timescale, round-trip times, and the smoothing filters adopted by the paradigm. The analysis is validated against ns-2 simulations with a prototype. Our analysis helps gain fundamental insights on the impact of several factors.

TCP congestion-control is fairly inefficient in achieving high throughput in high-speed and dynamic-bandwidth environments. The main culprit is the slow bandwidth-search process used by TCP, which may take up to several thousands of round-trip times (RTTs) in searching for and acquiring the end-to-end spare bandwidth. Even the recently-proposed "highspeed" transport protocols may take hundreds of RTTs for this. In this paper, we design a new approach for congestion-control that allows TCP connections to boldly search for, and adapt to, the available bandwidth within a single RTT. Our approach relies on carefully orchestrated packet sending times and estimates the available bandwidth based on the delays experienced by these. We instantiate our new protocol, referred to as RAPID, using mechanisms that promote efficiency, queue-friendliness, and fairness. Our experimental evaluations on gigabit networks indicate that RAPID: (i) converges to an updated value of bandwidth within 1-4 RTTs; (ii) helps maintain fairly small queues; (iii) has negligible impact on regular TCP traffic; and (iv) exhibits excellent intra-protocol fairness among co-existing RAPID transfers. The rate-based design allows RAPID to be truly RTT-fair.

The TCP NewReno congestion control protocol relies only on packer losses for detecting congestion-this causes long NewReno transfers to build up large packet queues in router buffers. High buffer occupancy hinders performance of real-time applications as well as the development of high-speed routers. Several alternate congestion-control strategies have been proposed in the literature to help maintain low buffer occupancy. In this paper, we experimentally evaluate prominent proposals by emulating empirically-derived traffic mixes on a Linux-based lab testbed. We show that when existing proposals are used with such representative traffic mixes, they are unable to simultaneously ensure small router queues and high TCP throughput. Further analysis shows that the common practice of using TCP round-trip times for estimating queuing delays (as in TCP Vegas) fails in a highly-aggregated environment that contains short as well as long transfers' such environments would need to rely on explicit router feedback. We also find that proposals that rely on router feedback in the form of link utilization (as recently proposed in VCP) are not effective in maintaining high transfer throughput. Instead, we argue that a congestion control algorithm which used queuing delay feedback from routers can reduce the buffer occupancy of routers without sacrificing response time performance of connections. We use this idea to design two new protocals-EDN and PEDN-and show that these two protocols can help manage the trade-off between maintaining low buffer occupancy and providing high TCP throughput.

The efficiency of TCP congestion-control in achieving high throughput is quite poor in high-speed, lossy, and dynamic-bandwidth environments. The main culprit is the slow bandwidth-search process used by TCP, which may take up to several thousands of round-trip times (RTTs) in searching for and acquiring the end-to-end spare bandwidth. While several alternate protocols have been proposed to speed up the search process, these still take hundreds of RTTs for doing so. In this paper, we argue that the sluggishness of existing protocols stems from two limiting design decisions that help a transfer remain non-intrusive to competing transfers. We argue that these legacy design decisions can be done away with if we limit the impact of probing for spare bandwidth. We use this idea to design a new approach for congestion-control that allows TCP connections to boldly search for, and adapt to, the available bandwidth within a single RTT. Our approach relies on carefully orchestrated packet sending times and estimates the available bandwidth based on the delays experienced by these. We instantiate our new protocol, referred to as RAPID, using mechanisms that promote efficiency as well as queue-friendliness. Our experimental evaluations indicate that RAPID: (i) converges to an updated value of bandwidth within 1-2 RTTs; (ii) helps maintain fairly small queues even in high-speed networks; and (iii) has negligible impact on regular TCP traffic. The benefits of our approach are especially significant on lossy links and those with rapidly-changing bandwidth.

TCP is the dominant transport protocol used in the Internet and its performance fundamentally governs the performance of Internet applications. It is well-known that packet losses can adversely affect the connection duration of TCP connections - however, what is not fully understood is how well does the TCP design deal with losses. In this paper, we systematically evaluate the impact of design parameters associated with TCP's loss detection/recovery mechanisms on the performance of real-world TCP connections. For this, we rely on an analysis tool that partially emulates the sender-side TCP implementations of 5 prominent OSes for passively analyzing the traces of TCP connections. Our study conducts passive analysis of more than 2.8 million real Internet TCP connections. We find that the recommended as well as widely-implemented settings of TCP parameters are not optimal for a significant fraction of Internet connections.

Recent interest in using tomography for network monitoring has raised the fundamental issue of whether it is possible to use only a small number of probing nodes (beacons) for monitoring all edges of a network in the presence of dynamic routing. Past work has shown that minimizing the number of beacons is NP-hard, and has provided approximate solutions that may be fairly suboptimal. In this paper, we use a two-pronged approach to compute an efficient beacon set: (i) we formulate the need for, and design algorithms for, computing the set of edges that can be monitored by a beacon under all possible routing states; and (ii) we minimize the number of beacons used to monitor all network edges. We show that the latter problem is NP-complete and use an approximate placement algorithm that yields beacon sets of sizes within 1+ln(|E|) of the optimal solution, where E is the set of edges to be monitored. Beacon set computations for several Rocketfuel ISP topologies indicate that our algorithm may reduce the number of beacons yielded by past solutions by more than 50%.

This paper develops and evaluates new share-based scheduling algorithms for differentiated service quality in network services, such as network storage servers. This form of resource control makes it possible to share a server among multiple request flows with probabilistic assurance that each flow receives a specified minimum share of a server's capacity to serve requests. This assurance is important for safe outsourcing of services to shared utilities such as Storage Service Providers.Our approach interposes share-based request dispatching on the network path between the server and its clients. Two new scheduling algorithms are designed to run within an intermediary (e.g., a network switch), where they enforce fair sharing by throttling request flows and reordering requests; these algorithms are adaptations of Start-time Fair Queuing (SFQ) for servers with a configurable degree of internal concurrency. A third algorithm, Request Windows (RW), bounds the outstanding requests for each flow independently; it is amenable to a decentralized implementation, but may restrict concurrency under light load. The analysis and experimental results show that these new algorithms can enforce shares effectively when the shares are not saturated, and that they provide acceptable performance isolation under saturation. Although the evaluation uses a storage service as an example, interposed request scheduling is non-intrusive and views the server as a black box, so it is useful for complex services with no internal support for differentiated service quality.

We measured and analyzed the variability in round trip times (RTTs) within TCP connections using passive measurement techniques. We collected eight hours of bidirectional traces containing over 22 million TCP connections between end-points at a large university campus and almost $1$ million remote locations. Of these, we used over 1 million TCP connections that yield 10 or more valid RTT samples, to examine RTT variability within a TCP connection. Our results indicate that contrary to observations in several previous studies, RTT values within a connection vary widely. Our results have implications for designing better simulation models, and understanding how round trip times affect the dynamic behavior and throughput of TCP connections.

End-to-end throughput guarantee is an important service semantics that network providers would like to offer to their customers. A network provider can offer such service semantics by deploying a network where each router employs a fair packet scheduling algorithm. Unfortunately, these scheduling algorithms require every router to maintain per-flow state and perform per-packet flow classification; these requirements limit the scalability of the routers. In this paper, we propose the Core-stateless Guaranteed Throughput (CSGT) network architecture-the first work-conserving architecture that, without maintaining per-flow state or performing per-packet flow classification in core routers, provides to flows throughput guarantees that are within an additive constant of what is attained by a network of core-stateful fair routers.

In this paper, we present the first end-to-end fairness analysis of a network of fair servers. We argue that it is difficult to extend existing single-node fairness analysis to an end-to-end analysis of a network where each node may employ a different fair scheduling algorithm. We then present a two-step approach for end-to-end fairness analysis of heterogeneous networks. First, we define a class of scheduling algorithms, referred to as the fair throughput (FT) class, and prove that most known fair scheduling algorithms belong to this class. Second, we develop an analysis methodology for deriving the end-to-end fairness bounds for a network of FT servers. Our analysis is general and can be applied to heterogeneous networks where different nodes employ different scheduling algorithms from the FT class.

Many per-flow scheduling algorithms have been proposed to provide rate and delay guarantees to flows. It is often argued that the need for maintaining per-flow state and performing per-packet classification seriously limits the scalability of routers that employ such per-flow scheduling algorithms. Consequently, design of algorithms that can provide per-flow rate and delay guarantees without requiring per-flow functionality in the network core routers has become an active area of research. We propose a methodology to transform any guaranteed rate (GR) per-flow scheduling algorithm into a version that does not require per-flow state to be maintained in the core routers. We prove that a network of such core-stateless servers provides the same delay guarantee as a corresponding network of GR servers.