%{search_type} search results

Networking algorithms often perform sequential decision making under uncertainty: They observe a network path and decide, e.g., how many packets to send or what to put in them. The Internet presents a particularly challenging setting: performance varies across several orders of magnitude and changes with time, control is decentralized, each node observes only a noisy sliver of the overall system, and accurate simulators do not exist. Despite the recent progress in applying machine learning (ML) to networking research, sequential decision problems on the Internet continue to rely on hand-designed algorithms. Slow adoption of ML in these scenarios can be attributed to the requirement that control algorithms be not just performant, but also practical: robust, generalizable, real-time, and resource-efficient. Lack of research platforms for studying ML approaches in the real world exacerbates the problem. This dissertation presents the platforms and algorithms we developed to achieve practical ML in the context of video streaming and congestion control. We describe Puffer, a free, publicly accessible website that live-streams television channels and operates as a randomized experiment of adaptive bitrate (ABR) algorithms. As of June 2020, Puffer has attracted 120,000 real users and streamed 60 years of video across the Internet. Using Puffer, we developed an ML-based ABR algorithm, Fugu, that robustly outperformed existing schemes by learning in situ, on real data from its actual deployment environment. Next, we describe Pantheon, a community "training ground" for Internet congestion-control research. It allows network researchers to benefit from and contribute to a common set of benchmark algorithms, a shared evaluation platform, and a public archive of results. Pantheon has assisted four algorithms from other research groups in publishing at NSDI 2018, ICML 2019, and SIGCOMM 2020. It also enabled our own ML-based congestion-control algorithm, Indigo, which was trained to imitate expert congestion-control algorithms we created in emulation and achieved good performance over the real Internet

This thesis explores how RF backscatter can serve as an indispensable tool for designing low-power sensor networks. Low-power techniques allow sensors to be deployed where there is insufficient power or communication infrastructure for traditional sensor nodes. RF backscatter communication consumes an order of magnitude less power than even Bluetooth Low Energy. This dissertation presents three projects that advanced the state-of-the-art in sensing systems that harness RF backscatter. The first two projects, FreeRider and BackCam, describe systems that can backscatter commodity WiFi signals. Instead of having to invest in special-purpose transceivers, we can harness WiFi radios that are already ubiquitous. FreeRider is a backscatter communication platform designed to operate on top of existing ISM-band networks, like 802.11 WiFi. BackCam~\cite{backcam} extends this work by adding a camera sensor to the tag and implementing an edge-based control system. Using RF backscatter makes communication cheap, which allows us to push image processing to the edge. The next project, RayTag, demonstrates how pairing backscatter tags with radars makes the target signal 100-10,000x stronger in amplitude compared to the strongest clutter signal. This allows for simultaneous detection and identification of multiple targets, which is useful for a variety of sensing applications. To demonstrate the potential of RayTag, I show that deploying backscatter tags underground can be used to accurately measure soil moisture. Though I focus on the evaluation of sensing soil moisture, RayTag is not a single-purpose sensing system. Rather, RayTag can be used to enhance a number of existing sensing tasks (e.g. localization) or enable entirely new applications. To that end, this thesis also presents detailed evaluations beyond underground contexts, as well as multiple examples of constructing link budgets. This dissertation further explores a renewable power source for underground backscatter tags. Many backscatter communication systems can harvest their operating power via RF, but this is not practical for underground systems because wet soil attenuates RF too much for harvesting circuits to operate. One potential source of energy are microbes in the soil. Microbial fuel cells (MFCs), sometimes also known as mud or soil batteries, accept electrons that are a byproduct of redox reactions catalyzed by electrogenic microbes naturally occurring in soil. This creates a potential difference across the cathode and anode, which provides a low-cost renewable source of power. In the future, this could allow underground backscatter tags to have an indefinite lifetime

For decades, developers have been productive writing software by composing optimized libraries and functions written by other developers. Though hardware trends have evolved significantly over this time---with the ending of Moore's law, the increasing ubiquity of parallelism, and the emergence of new accelerators---many of the common interfaces for composing software have nevertheless remained unchanged since their original design. This lack of evolution is causing serious performance consequences in modern applications. For example, the growing gap between memory and processing speeds means that applications that compose even hand-tuned libraries can spend more time transferring data through main memory between individual function calls than they do performing computations. This problem is even worse for applications that interface with new hardware accelerators such as GPUs. Though application writers can circumvent these bottlenecks manually, these optimizations come at the expense of programmability. In short, the interfaces for composing even optimized software modules are no longer sufficient to best use the resources of modern hardware. This dissertation proposes designing new interfaces for efficient software composition on modern hardware by leveraging algebraic properties intrinsic to software APIs to unlock new optimizations. We demonstrate this idea with three new composition interfaces. The first interface, Weld, uses a functional intermediate representation (IR) to capture the parallel structure of data analytics workloads underneath existing APIs, and enables powerful data movement optimizations over this IR to optimize applications end-to-end. The second, called split annotations (SAs), also focuses on data movement optimization and parallelization, but uses annotations on top of existing functions to define an algebra for specifying how data passed between functions can be partitioned and recombined to enable cross-function pipelining. The third, called raw filtering, optimizes data loading in data-intensive systems by redefining the interface between data parsers and query engines to improve CPU efficiency. Our implementations of these interfaces have shown substantial performance benefits in rethinking the interface between software modules. More importantly, they have also shown the limitations of existing established interfaces. Weld and SAs show that a new interface can accelerate data science pipelines by over 100x in some cases in multicore environments, by enabling data movement optimizations such as pipelining on top of existing libraries such as NumPy and Pandas. We also show that Weld can be used to target new parallel accelerators, such as vector processors and GPUs, and that SAs can enable these speedups even on black-box libraries without any library code modification. Finally, the I/O optimizations in raw filtering show over 9x improvements in end-to-end query execution time in distributed systems such as Spark SQL when processing semi-structured data such as JSON

For decades, legal and policy analysis of data privacy issues have tended to be informed by factual assumptions rather than rigorous empirics. The motivation for this dissertation is to recast these assumptions into a set of empirical computer science research questions. Decision makers are, in essence, relying on a set of heuristics to analyze data privacy issues. Are the assumptions behind those heuristics accurate, and what are the consequences of applying those heuristics? The first chapter of this dissertation examines third-party web tracking and advertising, an area that has vexed policymakers in both the United States and Europe. The chapter contributes new methodologies for measuring web tracking, including instrumenting an ordinary web browser and simulating user activity (FourthParty) and collecting tracking-related data directly from ordinary users (BrowserSurvey). The results include new perspectives on the web tracking marketplace, identification of numerous non-cookie tracking technologies, and evidence of inconsistent performance and usability from consumer control mechanisms. The chapter also presents a new design for privacy-preserving third-party advertising (Tracking Not Required) that would provide a specific privacy guarantee, would not require modifying browsers, and would be externally auditable. The second chapter analyzes the distinction between metadata and content, a concept that is foundational to surveillance law and policy in the United States and worldwide. The chapter contributes a new crowdsourcing methodology for studying telephone metadata privacy. It then uses a crowdsourced dataset to demonstrate that telephone metadata is densely interconnected, susceptible to re-identification, and enables highly sensitive inferences. The third chapter assesses data territoriality, another surveillance distinction that is shared by the United States and across the globe. Results from simulated browsing activity indicate that data territoriality is a poor fit for modern web architecture; Americans unknowingly send a large volume of domestic online activity outside the United States, and foreign citizens send a large volume of (from their perspective) domestic online activity into the United States. The conclusion considers the relationship between the computer science community and policymaking about data privacy. It suggests how computer scientists can and must play a greater role in government decision making, to ensure that policy and law reflect the best available privacy science.

Many large-scale key-value storage systems sacrifice features like secondary indexing and/or strong consistency in favor of scalability or performance. This limits the ease and efficiency of application development on such systems. Implementing secondary indexing in a large-scale memory based system is challenging because the goals for low latency, high scalability, strong consistency and high availability often conflict with each other. This dissertation shows how a large-scale key-value storage system can be extended to provide secondary indexes while meeting those goals. The resulting architecture is called Scalable Low-Latency Indexes for a Key-Value Store, or SLIK. It extends a standard key-value store to enable multiple secondary keys for each object and allows lookups and range queries on these keys via secondary indexes. SLIK allows indexes to be partitioned and distributed independently of the data in tables in order to ensure scalability. Locating objects and corresponding index entries on different servers can lead to potential consistency issues. However, SLIK provides strong consistency guarantees using a lightweight ordered write approach. While SLIK stores indexes in DRAM to enable low latency, it ensures that the index information is durable and quickly recovered using backups in case of crashes. This design was implemented in RAMCloud, a distributed in-memory key-value storage system. This implementation performs indexed reads in 11--13 μs and writes in 30--37 μs, which is approximately twice the latency of basic non-indexed reads and writes in RAMCloud. It supports indexes spanning thousands of nodes, and yields linear scalability for throughput.

The Internet of Things describes the phenomenon of connecting low-resource edge devices to the Internet. This phenomenon, while exciting, uncovers safety, performance, and flexibility challanges for the low-resource computers. In particular, the microcontrollers that power these devices lack some of the hardware features and memory resources that enable multiprogrammable systems. Accordingly, microcontroller-based operating systems have not provided important features like fault isolation, dynamic memory allocation, and flexible concurrency. However, the Internet of Things changes these devices into software platforms, rather than single purpose devices, requiring multiprogramming features. This dissertation describes Tock, a new operating system for low-power platforms, that takes advantage of the limited hardware-protection mechanisms of contemporary microcontrollers as well as the type-safe features of the Rust programming language to provide a multiprogramming environment for microcontrollers. Tock isolates software faults, provides memory protection, and efficiently manages memory for dynamic application workloads written in any language. It achieves this while retaining the dependability requirements of long-running applications. The trade-off between extensibility, safety, and performance is long standing in operating systems. More specifically, prior systems in the research have attempted to use language type safety to replace, or augment, hardware-based isolation mechanisms in the kernel. However, these systems used garbage collected languages, generally viewed as too resource-heavy for kernel programming in production systems. Tock's use of Rust shows that, given a type-safe language with sufficient control of memory and processor resources, language-based approaches can be _more_ efficient than hardware. Moreover, Tock's use in academia and industry show that this approach is practical in real-world deployments.