João Carlos Antunes Leitão
Topology Management for Unstructured Overlay Networks
Thesis submitted for the PhD in Computer Science and Engineering, Instituto Superior Técnico
(IST), Universidade Técnica de Lisboa
Abstract
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 to manage the topology of unstructured overlay networks, to
understand if and how is it 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 serve 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.
Selected Publications
- Topology Management for Unstructured Overlay
Networks
- João Carlos Antunes Leitão
- PhD Thesis. Departamento de Engenharia Informática,
Instituto Superior Técnico (IST), Universidade Técnica
de Lisboa
- September, 2012.
- Available pdf.
- X-BOT: A Protocol for Resilient Optimization of
Unstructured Overlay Networks.
- J. Leitão,
J. Marques, J. Pereira, L. Rodrigues.
- IEEE Transactions on
Parallel and Distributed Systems
-
in the IEEE DL
- Overnesia: a Resilient Overlay Network for Virtual
Super-Peers.
- J. Leitão and
L. Rodrigues.
- In proceedings of the 33rd IEEE International
Symposium on Reliable Distributed Systems (SRDS), Nara, Japan,
October 2014.
- Thicket: A Protocol for Building and Maintaining
Multiple Trees in a P2P Overlay.
- M. Ferreira,
J. Leitão, and L. Rodrigues.
- In proceedings of the 29th IEEE
Symposium on Reliable Distributed Systems (SRDS), New Delhi, India,
31 October-3 November 2010.
- Available BibTeX,
abstract (html) and report (pdf).
- Balancing Gossip Exchanges in Networks with
Firewalls.
- J. Leitão, R. van Renesse and
L. Rodrigues.
- In Proceedings of the 9th International Workshop
on Peer-to-Peer Systems (IPTPS '10), San Jose, CA, USA, 27 April,
2010.
- Available BibTeX,
abstract (html) and report (pdf).
Contact information
João Leitão
Luís Rodrigues