Oscar is a data-oriented overlay network for heterogeneous environments. Practical scalable systems need to take into account heterogeneity explicitly in the systems design. For data-oriented overlays (internet-scale peer-to-peer index structures) heterogeneity is encountered both because of the peculiarities of the environment as well as the application characteristics. Measurement studies of deployed P2P systems show heterogeneity arising because of either diverse availability of resources like storage, bandwidth, computation and content at peers, or variation in individual willingness to contribute resources to the system, as well as software artifacts like default configurations. Data-oriented applications are characterized by non-uniform distribution of keys over the key-space as well as skewed query or access patterns. We introduce OSCAR, an overlay network design based on small world graphs, that can adapt to arbitrary distribution patterns. In order to deal with heterogeneous distributions reliable statistics need to be built by sampling. This leads to the problem of scalable sampling of key distributions during the construction of data-oriented structured overlay networks, a problem that has so far not been considered in the literature. We exploit the fact that knowledge of the continuous and complete distribution is not really necessary, and approximate knowledge of percentiles suffices to determine route choices adhering to the basic principles of Kleinberg style small-world networks. Because of the flexibility of small-world networks in choosing routes, peers in OSCAR can also autonomously and locally decide on the amount of resources - bandwidth and storage - they are willing to provide, depending on local perception of various loads, including storage, traffic and query answering. We provide analytical and simulation results and show that our approach substantially outperforms existing approaches to structured overlay networks in presence of diverse kinds of heterogeneity - workload as well as available resources - as characterized in either data-oriented applications or the peer-to-peer environments respectively.

Publications/Talks

• Why and how small-world routing can be used for skewed key-spaces? [NetDB 2005]
• What are the limitations of state of the art small-world based overlay network proposals? [DBISP2P 2006]
• Practical algorithms to realize small-world network in a heterogeneous environment and over skewed key-spaces. [ICDE 2007]
• Structured Overlay For Heterogeneous Environments: Design and Evaluation of Oscar [under review]
• FuzzyNet: Zero-maintenance Ringless Overlay [under review]
  
  
  

Last updated: 25th June 2006