|
Progress - Overlay Networks
Computer networks in general, and the Internet in particular, are experiencing
explosive growth in many dimensions, including size, performance,
user base and geographical span. The potential for communication and access to
computational resources have improved dramatically both quantitatively and
qualitatively in a relatively short time.
New design paradigms such as peer-to-peer (P2P) and grid
computing have emerged in response to these trends.
The Internet, and all similar networks, pose special challenges
to the designer of large-scale, reliable distributed applications.
The ``best-effort'' design philosophy that characterizes such networks renders
the communication channels inherently unreliable and the continuous flow of nodes
joining and leaving the network make them highly dynamic. Control and monitoring
in such systems are particularly challenging: performing global computations
requires orchestrating a huge number of nodes.
We believe that, in order to respond to these challenges, a
modular paradigm is required.
The idea is to identify a collection of simple and predictable services as
building blocks and combine them in arbitrarily complex functions
and protocols.
Such a modular approach presents several attractive features.
Developers will be allowed to plug different components implementing a
desired function into existing or new applications, being certain that
the function will be performed in a predictable and dependable manner.
Research may be focused on the development of simple and well-understood
building blocks, with a particular emphasis on important properties like
robustness, scalability, self-organization and self-management.
The ``building blocks'' produced so far
can be informally subdivided into two broad categories: overlay
protocols and functional protocols. An overlay protocol is
aimed at maintaining application-layer, connected communication
topologies over a set of distributed nodes. These topologies may
constitute the basis for functional protocols, whose task is to
compute a specific function over the data maintained at nodes.
Our components are typically no more complicated than a cellular
automaton or a swarm model which makes them ideal objects for research.
Practical applications based on them can also benefit from
a potentially more stable foundation and predictability, a key concern
in fully distributed systems.
Additional details about the proposed paradigm can be found in a paper
published in the Proceedings of the EU-NSF Strategic Research Workshop
on Unconventional Programming Paradigms (UPP'04) [BJM04].
A previous paper on the subject, published in the Proceedings
of AAMAS Workshop on Engineering Self-Organizing Applications
(ESOA'03), illustrates how a load-balancing protocol can be
obtained combining other, simpler building blocks [JMB04].
Our current bag of protocols includes:
We have developed protocols for maintaining both unstructured and
structured topologies. Newscast [VJvS03,JGKvS04]
is a membership protocol aimed at maintaining robust, connected random
topologies; T-Man [JB05,MJB05] can be used to build
structured topologies like grids and tori; SG-1 [Mon04]
constructs superpeer-based topologies.
Aggregation is a common name for a set of functions that provide global,
statistical information about a distributed system.
Examples of aggregation functions include network size, total free storage,
maximum load, average uptime, location and description of hotspots, etc.
OverStat [JM04,MJB04a,MJB04b]
is a collection of decentralized
aggregation protocols that compute a broad range of statistical functions,
including means, sum, products, counting, variance, etc.
Decentralized aggregation can be used as a building block to obtain a
near-optimal load-balancing protocol [JMB04].
Search is a central function for any overlay network.Our research derives inspiration
from natural immune systems to improve various aspects of P2P search.
In order to improve the performance, we have a two-fold strategy (a) devising a
fast propagation scheme of the query message packets, and (b) arranging the peers to
form clusters of peers which host similar data so that the search operation can be
consequently speeded up.
Our aim is to build up a semi-structured P2P network, with the same level of robustness
provided by decentralized P2P network, offering however better quality of search service.
Path management refers to the finding, establishment, monitoring and
maintenance of virtual connection in communication networks. In
BISON we have been looking into the use of ant based systems to do
path management and monitoring in a distributed fashion. As an
example of use, in [HWH05], path management in a
Norwegian IP network is studied.
- BJM04
-
Ozalp Babaoglu, Márk Jelasity, and Alberto Montresor.
Grassroots approach to self-management in large-scale distributed
systems.
In Proceedings of the EU-NSF Strategic Research Workshop on
Unconventional Programming Paradigms, Mont Saint-Michel, France, September
2004.
[PDF],
[Bibtex].
- JMB04
-
Márk Jelasity, Alberto Montresor, and Ozalp Babaoglu.
A modular paradigm for building self-organizing peer-to-peer
applications.
In Giovanna Di Marzo Serugendo, Anthony Karageorgos, Omer F. Rana,
and Franco Zambonelli, editors, Engineering Self-Organising Systems:
Nature-Inspired Approaches to Software Engineering, number 2977 in Lecture
Notes in Artificial Intelligence, pages 265-282. Springer-Verlag, April
2004.
[PDF],
[Bibtex].
- VJvS03
-
Spyros Voulgaris, Márk Jelasity, and Maarten van Steen.
A robust and scalable peer-to-peer gossiping protocol.
In Proceedings of the 2nd International Workshop on Agents and
Peer-to-Peer Computing (AP2PC03), Melbourne, Australia, July 2003.
[PDF],
[Bibtex].
- JGKvS04
-
Márk Jelasity, Rachid Guerraoui, Anne-Marie Kermarrec, and Maarten van
Steen.
The peer sampling service: Experimental evaluation of unstructured
gossip-based implementations.
In Proceedings of the 5th International Middleware Conference,
Toronto, Canada, October 2004.
[PDF],
[Bibtex].
- JB05
-
Márk Jelasity and Ozalp Babaoglu.
T-Man: Gossip-based overlay topology management.
In Proceedings of Engineering Self-Organising Applications
(ESOA'05), July 2005.
[PDF],
[Bibtex].
- MJB05
-
Alberto Montresor, Márk Jelasity, and Ozalp Babaoglu.
Chord on demand.
In Proceedings of the 5th International Conference on
Peer-to-Peer Computing (P2P 2005), pages 87-94, Konstanz, Germany, August
2005. IEEE.
[PDF],
[Bibtex].
- Mon04
-
Alberto Montresor.
A robust protocol for building superpeer overlay topologies.
In Proceedings of the 4th International Conference on
Peer-to-Peer Computing (P2P 2004), pages 202-209, Zurich, Switzerland,
August 2004. IEEE.
[PDF],
[Bibtex].
- JM04
-
Márk Jelasity and Alberto Montresor.
Epidemic-style proactive aggregation in large overlay networks.
In Proceedings of the 24th International Conference on
Distributed Computing Systems (ICDCS'04), pages 102-109, Tokyo, Japan,
March 2004. IEEE Computer Society.
[PDF],
[Bibtex].
- MJB04a
-
Alberto Montresor, Márk Jelasity, and Ozalp Babaoglu.
Robust aggregation protocols for large-scale overlay networks.
In Proceedings of the 2004 International Conference on
Dependable Systems and Networks (DSN'04), pages 19-28, Florence, Italy,
June 2004. IEEE Computer Society.
[PDF],
[Bibtex].
- MJB04b
-
Alberto Montresor, Márk Jelasity, and Ozalp Babaoglu.
Decentralized ranking in large-scale overlay networks.
Technical Report UBLCS-2004-18, University of Bologna, Department of
Computer Science, Bologna, Italy, December 2004.
[PDF],
[Bibtex].
- HWH05
-
Poul E. Heegaard, Otto Wittner, and Bjarne Helvik.
Self-managed virtual path management in dynamic networks.
In Ozalp Babaoglu, Márk Jelasity, Alberto Montresor, Christof
Fetzer, Stefano Leonardi, Aad van Moorsel, and Maarten van Steen, editors,
Self-Star Properties in Complex Information Systems, volume 3460 of
Lecture Notes in Computer Science. Springer-Verlag, 2005.
[PDF],
[Bibtex].
|