Overlay network construction in highly decentralized networks.

摘要

In recent years, highly decentralized networks such as wireless ad hoc and peer-to-peer (P2P) have emerged as the most interesting, challenging and innovation rich areas in computer networking. The nature of these networks require efficient, local, scalable and self-stabilizing algorithmic solutions.;In this thesis, the problem of overlay network construction in highly decentralized networks is studied. Firstly, our work on overlay network construction for wireless ad-hoc networks is presented. A more general communication model for wireless ad-hoc networks, and a locally self-stabilizing algorithm to construct an overlay network is presented. More precisely, a backbone structure is established by efficiently electing cluster leaders and gateway nodes. For electing cluster leaders, Luby's maximal independent set algorithm is extended to our more complex model and then every pair of cluster leaders which are close to each other is interconnected with the help of gateway nodes. Secondly, our work on construction of line-based P2P overlay networks is presented. Locally self stabilizing algorithms for constructing peer-to-peer overlay networks is presented. Linearization is proposed as the basic technique to sort any connected graph. The linearization technique is self-stabilizing and transforms any connected graph into a sorted list. Lastly our work on construction of publish-subscribe P2P overlay networks is presented. An overlay network is designed for publish/subscribe communication in a system where nodes may subscribe to many different topics of interest. The following problem is considered: Given a collection of nodes and their topic subscriptions connect the nodes into a graph which has least possible maximum degree and in such a way that for each topic t, the graph induced by the nodes interested in t is connected. The first polynomial time logarithmic approximation algorithm is presented for this problem and an almost tight lower bound on the approximation ratio is presented. Our algorithm is based on greedy matching algorithm for graphs. Experimental results show that our algorithm drastically improves the maximum degree of publish/subscribe overlay systems.;An important problem in highly decentralized networks is constructing an overlay network on top of which one can efficiently provide services such as routing, broadcasting and information gathering in wireless ad hoc networks and routing, data search and redundant storage in P2P networks.