Merging ring-structured overlay indices : toward network-data transparency
Date of Issue2012
School of Computer Engineering
Peer-to-peer index structures distributed and managed over the planet, commonly known as structured overlays (e.g., distributed hash tables) have been touted to play the role of a fundamental building block for internet-scale distributed systems. Traditional designs consider incremental or possibly even parallelized construction of a single overlay, which implicitly assumes global control and coordination to enforce the construction of an unique overlay. However, if merger of originally isolated overlays is made possible, then one can realize decentralized bootstrapping of overlays. So to say, smaller overlays can be constructed using any of the traditional mechanisms, which can then organically coalesce to form a larger overlay. Such self-organizational attributes of decentralized bootstrapping and organic growth are of paramount importance for large scale systems. In our previous works, we explained the challenges of merging important families of (tree and ring) structured overlays (Datta and Aberer in international workshop on self-organizing systems, 2006), and identified that tree structured overlays are relatively easier to merge in a transparent manner (Datta in IEEE international conference on self-adaptive and self-organizing systems, 2007). In this paper we investigate how ring structured overlays can be merged, both in terms of the necessary algorithms, as well as how it performs during the merger process, taking into account not only the ‘network’ merger process, but also looking into how and whether this process is ‘transparent’ for applications/end-users accessing and using the overlay as an index. We introduce interesting new metrics to evaluate the merger process and carry out asymptotic analysis for estimating the same, besides conducting simulation experiments to validate the theory as well as measure other aspects of the overlays’ performance under merger.
DRNTU::Engineering::Computer science and engineering