National and Kapodistrian University of Athens
Σχεδιασμός και μελέτη αλγορίθμων για διάδοση πληροφορίας σε μη δομημένα δικτυακά περιβάλλοντα
Abstract
dc:descriptionThe 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- Δίκτυα υπολογιστών
- Μη δομημένα δίκτυα
- Διάδοση πληροφορίας
- Ανακάλυψη πληροφορίας
- Κάλυψη δικτύου
- Τεχνική αναπαραγωγής τυχαίων δρομέων
- Computer networks
- Unstructured networks
- Information dissemination
- Information discovery
- Network coverage
- Randomly replicated random walkers
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/20655