UC San Diego

Peer-to-peer overlay networks provide a distributed, fault -tolerant, scalable architecture on which wide-area distributed systems and applications can be built. Two fundamental services provided by peer-to-peer overlay networks are a routing protocol to map keys in a large, virtual ID space to values associated with individual hosts in the overlay network, and a storage service to maintain data objects on behalf of higher-level services, applications, and users. In existing peer-to-peer routing protocols and object maintenance strategies, the system typically gives each host equal responsibilities in terms of routing messages and storing object data and metadata. In reality, however, hosts in the system have unequal capabilities. In this thesis, we propose enhancements to peer-to-peer routing protocols and object maintenance strategies that tailor them to take advantage of resource heterogeneity. Using an approach called ̀S̀hortCuts'', we use three caching techniques to improve routing performance while adjusting the overhead of maintaining consistent state to the available bandwidth of individual hosts. Combined, these caches achieve routing performance that approaches the aggressive performance of one-hop schemes, but with an order of magnitude less communication overhead on average. Compared to previous approaches that place data randomly among hosts, we explored refining object maintenance strategies according to host uptimes and lifetimes. As a first step, we performed an extensive measurement study of permanent host failures in the KAD peer-to-peer file sharing system. Our analysis have shown that, while a significant fraction of the entire population has a very short lifetime (e.g., one connection for a few hours), the network contains a very stable subpopulation of peers with lifetimes of months. As a second step, we propose new object maintenance strategies that bias the placement of redundant data on hosts with longer lifetimes and higher availabilities. Using trace- driven simulation of a peer-to-peer storage system and our trace of hosts in the KAD network, we show that peer-to- peer storage systems can reduce object maintenance overheads by biasing placement on long-lived and highly- available hosts