Scalable system monitoring is a fundamental abstraction for large-scale networked systems. The goal of this dissertation is to design and build a scalable monitoring middleware that provides system introspection for large distributed systems and that will facilitate the design, development, and deployment of distributed monitoring applications. This middleware will enable monitoring applications to flexibly control the tradeoff between result precision and communication cost and to improve result accuracy in the face of node failures, network delays, and system reconfigurations. We present PRISM (PRecision-Integrated Scalable Monitoring), a scalable monitoring middleware that provides a global aggregate view of large-scale networked systems and that can serve as a building block for a broad range of distributed monitoring applications by coordinating views of multiple vantage points across the network. To coordinate a global view for system introspection, PRISM faces two key challenges: (1) scalability to large systems and high data volumes and (2) safeguarding accuracy in the face of node and network failures. To address these challenges, we design, implement, and evaluate PRISM, a system that defines precision as a new unified abstraction to enable scalable monitoring. PRISM quantifies (im)precision along a three-dimensional vector: arithmetic imprecision (AI) and temporal imprecision (TI) balance precision against monitoring overhead for scalability while network imprecision (NI) addresses the challenge of providing consistency guarantees despite failures. Our prototype implementation of PRISM addresses the challenge of providing these metrics while scaling to a large number of nodes and attributes by (1) leveraging Distributed Hash Tables (DHTs) to create scalable aggregation trees, (2) self-tuning AI budgets across nodes in a principled, near-optimal manner to shift precision to where it is useful, (3) pipelining TI delays across tree levels to maximize batching of updates, and (4) applying dual-tree prefix aggregation which exploits symmetry in our DHT topology to drastically reduce the cost of the active probing needed to maintain NI. Through extensive simulations and experiments on four large-scale testbeds, we observe that PRISM provides a key substrate for scalable monitoring by (1) reducing monitoring load by up to two orders of magnitude compared to existing approaches, (2) providing a flexible framework to control the tradeoff between accuracy, bandwidth cost, and response latency, (3) characterizing and improving confidence in the accuracy of results in the face of system disruptions, and (4) improving the observed accuracy by up to an order of magnitude despite churn. We have built several monitoring applications on top of PRISM including a distributed heavy hitter detection service, a distributed monitoring service for Internet-scale systems, and a detection service for monitoring distributed-denial-of-service (DDoS) attacks at the source-side in distributed networked systems. Finally, we demonstrate how the unified precision abstraction enables new monitoring applications by presenting experiences from these applications. / text

A common feature of emerging future Internet architectures is the ability for applications to select the path, or paths, their packets take between a source and destination. Unlike the current Internet architecture where routing protocols find a single (best) path between a source and destination, future Internet routing protocols will present applications with a set of paths and allow them to select the most appropriate path. Although this enables applications to be actively involved in the selection of the paths their packets travel, the huge number of potential paths and the need to know the current network conditions of each of the proposed paths will make it virtually impossible for applications to select the best set of paths, or just the best path. To tackle this problem, we introduce a new Network Path Advising Service (NPAS) that helps future applications choose network paths. Given a set of possible paths, the NPAS service helps applications select appropriate paths based on both recent path measurements and end-to-end feedback collected from other applications. We describe the NPAS service abstraction, API calls, and a distributed architecture that achieves scalability by determining the most important things to monitor based on actual usage. By analyzing existing traffic patterns, we will demonstrate it is feasible for NPAS to monitor only a few nodes and links and yet be able to offer advice about the most important paths used by a high percentage of traffic. Finally, we describe a prototype implementation of the NPAS components as well as a simulation model used to evaluate the NPAS architecture.