In this paper, we investigate the roles of replication vs. repair to achieve durability in large-scale distributed storage systems. Specifically, we address the fundamental questions: How does the lifetime of an object depend on the degree of replication and rate of repair, and how is lifetime maximized when there is a constraint on resources? In addition, in real systems, when a node becomes unavailable, there is uncertainty whether this is temporary or permanent; we analyze the use of timeouts as a mechanism to make this determination. Finally, we explore the importance of memory in repair mechanisms, and show that under certain cost conditions, memoryless systems, which are inherently less complex, perform just as well.

Wireless networks based on 802.11a/b/g protocols have gained wide-spread acceptance in both enterprise as well as home networks. However, these devices lack native support for many advanced features such as service differentiation, etc., that are required in specific application domains. In this paper, we propose Covenant, a software based cooperative scheduling framework to provide a rich set of features for applications that require nodes to cooperate with each other to satisfy system-wide objectives. We propose a novel 2 1/2-stage pipeline architecture as an efficient mechanism to implement cooperative scheduling among multiple nodes. We demonstrate how Covenant can be easily implemented in software, thus requiring absolutely no hardware or firmware changes to the already widely installed base of 802.11a/b/g based wireless devices. We also evaluate, using a real Linux based test-bed with Covenant drivers, the efficacy of the approach on two different scheduling disciplines: proportional priority and strict priority. We demonstrate that these scheduling disciplines are effective in providing service guarantees to multimedia applications even in the presence of other competing traffic.

We study the problem of guaranteeing data durability [2] in distributed storage systems based on replication. Our work is motivated by several several recent efforts [3, 5, 1] to build such systems in a peer-to-peer environment. The key features of this environment which make achieving durability difficult are (1) data lifetimes may be several orders of magnitude larger than the lifetimes of individual storage units, and (2) the system may have little or no control over the participation of these storage units in the system. We use a model-based approach to develop engineering principles for designing automated replication and repair mechanisms to implement durability in such systems.

Indirect routing involves sending messages between Internet end nodes through a specified intermediate node to effect a different end-to-end route than the default "direct" route. Indirect routing offers the potential for significant improvements in throughput performance by exploiting the Internet's richness in throughput diversity. We present a performance analysis of indirect routing, showing that it can result in a 33-49% increase in average throughput performance while incurring low overhead.

This paper focuses on peer-to-peer storage systems that achieve availability through replication. We study the problem of resource allocation when the system must replicate multiple files using a fixed amount of resource. We characterize the optimal allocation that maximizes the average availability of the files in the system, and also study two simple, decentralized allocation schemes, viz., uniform allocation, where each file is allocated equal shares of the resource, and proportional allocation, where each file is allocated a share of the resource proportional to its size. We show that while uniform allocation is fair in terms of allocating resources, it may be arbitrarily sub-optimal. On the other hand, proportional allocation, though unfair in resource allocation, is competitive with the optimal allocation.

Today's cloud-based services integrate globally distributed resources into seamless computing platforms. Provisioning and accounting for the resource usage of these Internet-scale applications presents a challenging technical problem. This paper presents the design and implementation of distributed rate limiters, which work together to enforce a global rate limit across traffic aggregates at multiple sites, enabling the coordinated policing of a cloud-based service's network traffic. Our abstraction not only enforces a global limit, but also ensures that congestion-responsive transport-layer flows behave as if they traversed a single, shared limiter. We present two designs - one general purpose, and one optimized for TCP - that allow service operators to explicitly trade off between communication costs and system accuracy, efficiency, and scalability. Both designs are capable of rate limiting thousands of flows with negligible overhead (less than 3% in the tested configuration). We demonstrate that our TCP-centric design is scalable to hundreds of nodes while robust to both loss and communication delay, making it practical for deployment in nationwide service providers.

We present a study of end-to-end web access failures in the Internet. Part of our characterization of failures is based on directly observable end-to-end information. We also present novel analyses that reveal aspects of end-to-end failures that would be hard to discern otherwise. First, we combine end-to-end failure observations across a large number of clients to classify failures as server-related or client-related. Second, we correlate failures attributed to a client or server with BGP churn for the corresponding IP address prefix(es), to shed light on the end-to-end impact of BGP instability.

Abstract — We address the problem of using replication to reliably maintain state in a distributed system for time spans that far exceed the lifetimes of individual replicas. This scenario is relevant for any system comprised of a potentially large and selectable number of replicated components, each of which may be highly unreliable, where the goal is to have enough replicas to keep the system “alive ” (meaning at least one replica is working or available) for a certain expected period of time, i.e., the system’s lifetime. In particular, this applies to recent efforts to build highly available storage systems based on the peer-to-peer paradigm. We model notions of replica loss and replica repair in such systems by a simple Markov chain model, and derive an expression for the lifetime of the replicated state. We then apply this model to study the impact of practical considerations like storage and bandwidth limits on the system, and describe methods to optimally choose system parameters so as to maximize lifetime. Our analysis sheds light on the efficacy of various replication strategies. I.

Recent research has shown that one can use Distributed Hash Tables (DHTs) to build scalable, robust and efficient applications. One question that is often left unanswered is that of simplicity of implementation and deployment. In this paper, we explore a case study of building an application for which ease of deployment dominated the need for high performance. The application we focus on is Place Lab, an end-user positioning system. We evaluate whether it is feasible to use DHTs as an application-independent building block to implement a key component of Place Lab: its "mapping infrastructure." We present Prefix Hash Trees, a data structure used by Place Lab for geographic range queries that is built entire on top of a standard DHT. By strictly layering Place Lab's data structures on top of a generic DHT service, we were able to decouple the deployment and management of Place Lab from that of the underlying DHT. We identify the characteristics of Place Lab that made it amenable for deploying in this layered manner, and comment on its effect on performance.

This paper describes the Prefix Hash Tree, a distributed data structure that enables range queries over Distributed Hash Tables.

Fair queuing is a well-studied problem in modern computer networks. However, there remains a gap between scheduling algorithms that have provably good performance, and those that are feasible and practical to implement in high speed routers. In this paper, we propose a novel packet scheduler called Stratified Round Robin, which has low complexity, and is amenable to a simple hardware implementation. Stratified Robin Robin exhibits good fairness and delay properties that are demonstrated through both analytical results and simulations. In particular, it provides a single packet delay bound that is independent of the number of flows. This property is unique to Stratified Round Robin among all other schedulers of comparable complexity.

Internet routers and switches need to maintain millions of (e.g., per prefix) counters at up to OC-768 speeds that are essential for traffic engineering. Unfortunately, the speed requirements require the use of large amounts of expensive SRAM memory. Shah et al [1]introduced a cheaper statistics counter architecture that uses a much smaller amount of SRAM by using the SRAM as a cache together with a (cheap) backing DRAM that stores the complete counters. Counters in SRAM are periodically updated to the DRAM before they overflow under the control of a counter management algorithm. Shah et al [1] also devised a counter management algorithm called LCF that they prove uses an optimal amount of SRAM. Unfortunately, it is difficult to implement LCF at high speeds because it requires sorting to evict the largest counter in the SRAM. This paper removes this bottleneck in [1] by proposing a counter management algorithm called LR(T) (Largest Recent with thresh-old T) that avoids sorting by only keeping a bitmap that tracks counters that are larger than threshold T. This allows LR(T) to be practically realizable using only at most 2 bits extra per counter and a simple pipelined data structure. Despite this, we show through a formal analysis, that for a particular value of the threshold T, the LR(T) requires an optimal amount of SRAM, matching LCF. Further,we also describe an implementation, based on a novel data structure called aggregated bitmap, that allows the LR(T) algorithm to be realized at line rates.