Back to search

National and Kapodistrian University of Athens

Σχεδιασμός και μελέτη αλγορίθμων για διάδοση πληροφορίας σε μη δομημένα δικτυακά περιβάλλοντα

Abstract

dc:description

The focus of this thesis lies on the study of several existed techniques for information dissemination and on the introduction of new ones for application in the demanding environment of an unstructured network. Unstructured networks are the networks which because of their large scale, their scalability properties and their highly dynamic nature make it almost impossible for a node to possess accurate information, on any given time, regarding the overall network topology. One of the techniques studied here is the probabilistic flooding approach, especially its application on a random graph topology. Especially, by using two different, carefully selected random graphs it is possible to find the asymmetric bounds for the forwarding probability (pf) for an information message. This bounds will allow the probabilistic flooding network to successfully cover an underlying connected random graph G(N,p) by generating the minimum number of information dissemination messages. On top of it, it was proved both analytically and with simulations, that the use of probabilistic flooding in a connected random graph can succeed in reducing the generated number of disseminated messages, especially when this number is compared to the relative number produced by applying full flooding. Furthermore, the technique of Multiple Random Walkers was covered and analytical expressions regarding the coverage achieved for a fully connected topology were presented. For the study of less dense topologies, an ineffective coverage performance, at the early time slots, was expected and verified. This observation takes place because of the collection of a significant number of walkers near the initiator node, that need some time before managing to reach wider networking areas and, thus, to cover newly discovered nodes. As a solution to this phenomenon, the introduction of a new technique that is based on the replication of the walkers (each walker generates a replica of itself at each successful replication) during their move in the network and not from the beginning at the same (initiator) node. Simulation results proved that this technique shows a better performance for coverage. Finally, the performance of another replication technique, called the Randomly Replicated Random Walkers (RRRW), is studied in several networking topologies regarding the number of nodes that are covered along with the stretching of the information that is achieved. It was proved, via simulations, that the RRRW technique, in topologies that have a sense of a topological coverage of the network, can fill the performance gap between the full flooding and the single random walker approach.

Degree

thesis:*
Grantor dc:publisher
National and Kapodistrian University of Athens
Year dc:date
2010

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Kogias, Dimitrios
  • Κόγιας, Δημήτριος

Subjects

dc:subject × 16

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/20655

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Kogias, Dimitrios; Κόγιας, Δημήτριος. Σχεδιασμός και μελέτη αλγορίθμων για διάδοση πληροφορίας σε μη δομημένα δικτυακά περιβάλλοντα. National and Kapodistrian University of Athens, 2010. http://hdl.handle.net/10442/hedi/20655