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).
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.
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.
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.