Overview

Links/Downloads


Structured overlays, e.g., distributed hash tables (DHTs) are mechanisms to distribute an index, facilitating guaranteed and efficient lookup and search of resources. Structured overlays are used as a generic substrate for diverse distributed systems and applications - including indexing, routing, storage, publish-subscribe and multicast and peer data management systems, to name a few. We have worked on four generations of structured overlays: P-Grid (2002-6), Oscar (2005-7), FuzzyNet (2007-8) and SocialCircle (2008-9).

In the early days we were interested in performance and maintenance related issues like load-balancing, caching and resilience against churn and system heterogeneity, as well as data management issues like support for range queries, updates and directory service. We validated these ideas by developing P-Grid and Oscar. Recently we have been looking into issues which are essential for large-scale deployment of structured overlays. These include (i) transparent merger of multiple structured overlays (studied for both tree structured overlay like P-Grid, as well as ring based ones like Chord/Oscar), so that smaller networks can organically coalesce to form a larger network; (ii) ringless routing (FuzzyNet) mechanism to make the system robust against continuous violation of ring invariance inevitable in a large network due to churn and non-transitivity in IP routing due to various factors like NAT and firewalls; and (iii) structured overlay routing using only social connections (SocialCircle) in order to make the overlay resilient against several kinds of denial-of-service attacks - particularly Sybil attack, additionally, using social links ensure better cooperation among peers and reduces exposure to selfish behaviors like freeloading. Some representative publications on these are provided below.



P-Grid is a trie-structured overlay network designed specifically for data-oriented applications supporting efficiently queries like range-queries while achieving good load-balancing.

P-Grid

Oscar is an overlay based on algebraic small-world properties relying on scalable sampling scheme (based on medians instead of means) and is designed to deal with various heterogeneities - resource (bandwidth/storage) at peers, as well as rather arbitrary skews in access/storage loads. Like P-Grid, Oscar also supports data-oriented queries efficiently.

Oscar

In a network comprising of many peers, churn is continuous and the ring invariance is almost always in violation. By using a somewhat randomized (fuzzier) gossip based placement of data in the overlay, among other tweaks, we realized Fuzzynet overlay which does not rely on ring invariance for key lookup, and is thus significantly more resilient to churn for a relatively marginal self-stabilization maintenance overhead. The ideas are readily applicable for any ring based overlay such as Chord or Oscar.

FuzzyNet
Exploiting recent advances on ringless routing in structured overlays - including our previous work on Fuzzynet, as well as others (Microsoft research's Virtual Ring Routing "VRR"), we design an overlay which uses exclusively social links in order to realize a structured overlay. Such a friend-to-friend DHT is naturally resilient to many families of denial of service attacks.
SocialCircle


Representative publications


Systems/Overlay Networks

P-Grid: A Self-organizing Structured P2P System
Karl Aberer, Philippe Cudré-Mauroux, Anwitaman Datta, Zoran Despotovic, Manfred Hauswirth, Magdalena Punceva, Roman Schmidt
ACM SIGMOD Record, 32(3) Sept'2003. 
Structured Overlay For Heterogeneous Environments: Design and Evaluation of Oscar
Sarunas Girdzijauskas, Anwitaman Datta, Karl Aberer
Transactions on Autonomous and Adaptive Systems [ACM]
Fuzzynet: Ringless routing in a ring-like structured overlay
Sarunas Girdzijauskas, Wojciech Galuba, Vasilios Darlagiannis, Anwitaman Datta, Karl Aberer
Springer's Peer-to-Peer Networking and Applications Journal Volume 4, Number 3 (2011)
Mapping Social Networks into P2P Directory Service (SocialCircle)
Lukasz Zaczek, Anwitaman Datta
SocInfo 2009, International Conference on Social Informatics

Merger & Bootstrapping

Merging ring structured overlay indices - Toward network-data transparency
Anwitaman Datta
Springer Computing, Special issue on Extreme Distributed Systems: From large scale to complexity, 2012
The gamut of bootstrapping mechanisms for structured overlay
Anwitaman Datta
Handbook of Peer-to-Peer Networking, Springer Verlag. January 2010.
The challenges of merging two similar structured overlays: A tale of two networks
Anwitaman Datta, Karl Aberer
IWSOS 2006, International Workshop on Self-Organizing Systems.
[best paper award]
Merging Intra-Planetary Index Structures: Decentralized Bootstrapping of Overlays
Anwitaman Datta
SASO 2007, IEEE International Conference on Self-Adaptive and Self-Organizing Systems.
Indexing data-oriented overlay networks

Karl Aberer, Anwitaman Datta, Manfred Hauswirth, Roman Schmidt
VLDB 2005, 31st International Conference on Very Large Data Bases, Norway

Load-balancing

Multifaceted Simultaneous Load Balancing in DHT-based P2P systems: A new game with old balls and bins
Karl Aberer, Anwitaman Datta, Manfred Hauswirth
Self-* Properties in Complex Information Systems, "Hot Topics" series, Lecture Notes in Computer Science, Springer Verlag, 2005.
Query-load balancing in structured overlays
Anwitaman Datta, Roman Schmidt, Karl Aberer
CCGrid 2007, Seventh IEEE International Symposium on Cluster Computing and the Grid.

Churn & maintenance

Route maintenance overheads in DHT overlays
Karl Aberer, Anwitaman Datta, Manfred Hauswirth
WDAS 2004 The 6th Workshop on Distributed Data and Structures, EPF Lausanne, Switzerland.
Efficient, self-contained handling of identity in Peer-to-Peer systems
Karl Aberer, Anwitaman Datta, Manfred Hauswirth
TKDE [IEEE Transactions on Knowledge and Data Engineering] 16(7), 2004.

Applications, etc.

A decentralized public key infrastructure for customer-to-customer e-commerce
Karl Aberer, Anwitaman Datta, Manfred Hauswirth.
IJBPIM [International Journal of Business Process Integration and Management] (Inderscience Publishers) 1(1), 2005.

Miscellaneous

Range queries in trie-structured overlays
Anwitaman Datta, Manfred Hauswirth, Renault John, Roman Schmidt, Karl Aberer
P2P 2005, The Fifth IEEE International Conference on Peer-to-Peer Computing, Germany.

A Query-Adaptive Partial Distributed Hash Table for Peer-to-Peer Systems
Fabius Klemm, Anwitaman Datta, Karl Aberer
P2P&DB 2004 International Workshop on Peer-to-Peer Computing & DataBases, in conjunction with EDBT 2004 Conference, Greece.
Drupal 6 Appliance - Powered by TurnKey Linux