An efficient approach for incorporating underlay awareness in P2P networks for guaranteed availabilities. (26th January 2010)

• Record Type: Journal Article
• Authors: Kumar S.D., Madhu; Bellur, Umesh
• Is Part Of: International journal of communication networks and distributed systems. Volume 4:Number 2(2010)
• Page Start: 133
• Page End: 160
• Publication Date: 2010-01-26
• Subjects: overlay networks -- event-based middleware -- event notification services -- distributed algorithms -- underlay awareness -- availability -- latent availability -- peer-to-peer networks -- P2P networks -- modelling -- graph theory; Computer networks -- Periodicals; Telecommunication systems -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; 004.6
• Languages: English
• ISSNs: 1754-3916

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.