Route maintenance overheads in DHT overlays
Karl Aberer, Anwitaman Datta, Manfred Hauswirth · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2004
Efficient route maintenance in DHTs is still an area of very active research due to its complexity and multitude of aspects to be considered. In this paper we propose novel correctionon-failure (CoF) and correction-on-use (CoU) approaches that support route maintenance more efficiently than existing methods even under highly dynamical network conditions. In contrast to previous work which addresses static resilience, we apply the more realistic model of viewing changes in the network as a continuous Markovian process and demonstrate that the system can reach a dynamic equilibrium in the presence of continuous changes while remaining operational, efficient, and scalable. We devise a generally applicable method for analyzing the dynamic behavior of route maintenance and use it to proof the efficiency of our approach. The equilibrium equations derived from the analytical model allow us to predict a system’s behavior over a wide range of parameters and demonstrate its scalability. Simulation results additionally verify our analytical results. Our approach also introduces the principle of data independence into route maintenance which we demonstrate to be achievable at low cost. This separation of concern disentangles the overlay from the underlying network dynamics and is an important step towards semantic overlay networks as a basic constituent in distributed information management. It specifically facilitates the application of the P2P paradigm in mobile ad-hoc networks, identity management, tracking of past interactions (e.g., for reputation management), etc. which are of basic importance for overlay supported P2P commerce. Moreover, other domains, for example P2P based publish/subscribe systems, will also benefit from this property of our approach.