Topology Management for Unstructured Overlay Networks
Technical University of Lisbon, 2012
The peer-to-peer (P2P) paradigm has emerged as a viable alternative to overcome limitations of the client-server model namely, in terms of scalability, fault-tolerance, and even operational costs. This paradigm has gained significant popularity with its successful application in the context of file sharing applications. The success of these applications is illustrated by systems such as Napster, Emule, Gnutella, and recently, BitTorrent. In order to ensure the scalability of these solutions many P2P services operate on top of unstructured overlay networks, which are logical networks deployed at the application level. Unstructured overlay networks establish random neighboring associations among participants of the system. Although the random nature of these overlays is desirable by many P2P services, the resulting topology may present sub-optimal characteristics, for instance from the point of view of link latency. This may have a significative impact of the performance of P2P services executed over these overlays.
This thesis focuses on the design and evaluation of techniques that manage the topology of unstructured overlay networks, to understand if and how it is possible to manage the topology of unstructured overlays in such a way that the random nature and low overhead that characterizes these overlays is not lost, while being able to impose some relaxed constraints over the topology to benefit the operation of specific P2P services.
To answer this question, four different approaches to manage the topology of unstructured overlays are proposed and evaluated in the thesis. Each approach is evaluated in the context of a distinct P2P service that serves as a case study for measuring its benefits. In more detail, this thesis presents: i) CellFarm, a new overlay that combines properties of unstructured and structured overlays, to achieve a highly resilient topology composed of cliques of nodes, highly connected among themselves, that supports efficient replication for P2P systems; ii) X-BOT, a protocol to bias the topology of unstructured overlay networks given any criteria X; iii) Thicket, a protocol that efficiently embeds multiple interior-node-disjoint trees over a single unstructured overlay; and finally, iv) OpenFire, a protocol for balancing rumor mongering exchanges in networks populated by Firewalls and NAT-boxes.