Title: An efficient approach for incorporating underlay awareness in P2P networks for guaranteed availabilities

Authors: Madhu Kumar S.D., Umesh Bellur

Addresses: Department of Computer Science and Engineering, Indian Institute of Technology Bombay, Powai, Mumbai – 400 076, India. ' Department of Computer Science and Engineering, Indian Institute of Technology Bombay, Powai, Mumbai – 400 076, India

Abstract: Unstructured P2P overlays are employed by diverse applications like event dissemination. Many of these applications need the overlay to be highly available for guaranteeing QoS (such as delivery guarantees) to their clients. We demonstrate that underlay awareness i.e., knowledge of the structure of the underlying network, is necessary in such overlays for the availability of overlay paths. We model underlay aware overlays as a multilevel graph and with the help of graph theoretic concepts, existing and new, prove that the problem of formation of overlay networks with guaranteed availability is NP-complete. We show that, despite this complexity, underlay aware overlay networks for guaranteed availability can be formed and maintained efficiently. Such overlays use knowledge of the underlay and operate under a specified set of constraints which are relevant in large-scale networks. Using these constraints, we outline distributed algorithms for formation and maintenance of overlay networks of k degree of availability.

Keywords: overlay networks; event-based middleware; event notification services; distributed algorithms; underlay awareness; availability; latent availability; peer-to-peer networks; P2P networks; modelling; graph theory.

DOI: 10.1504/IJCNDS.2010.031184

International Journal of Communication Networks and Distributed Systems, 2010 Vol.4 No.2, pp.133 - 160

Published online: 25 Jan 2010 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article