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

Abstract

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.

Στα πλαίσια της παρούσας διδακτορικής διατριβής ερευνώνται διάφορες υπάρχουσες τεχνικές για διάδοση πληροφορίας και προτείνονται ορισμένες νέες, για εφαρμογή στο περιβάλλον των μη δομημένων δικτύων. Μη Δομημένα ονομάζονται τα δίκτυα εκείνα, τα οποία λόγω του μεγάλου τους μέγεθος, της κατανεμημένης λειτουργίας τους και της μεγάλης δυναμική τους, καθιστούν αδύνατο για έναν κόμβο να έχει πλήρη γνώση ολόκληρης της τοπολογίας του δικτύου κάθε χρονική στιγμή. Η πρώτη τεχνική που μελετήθηκε ήταν αυτή της πιθανολογικής πλημμύρας. (probabilistic flooding) και η εφαρμογή της σε τυχαίους γράφους. Με τη βοήθεια δύο βοηθητικών τυχαίων γράφων μελετήθηκαν και βρέθηκαν τα ασυμπτωτικά όρια στα οποία πρέπει να βρίσκεται η τιμή της πιθανότητας προώθησης pf (ενός μηνύματος) έτσι ώστε το δίκτυο της πιθανολογικής πλημμύρας να επιτυγχάνει ολική κάλυψη του υφισταμένου συνδεδεμένου τυχαίου γράφου G(N,p) με το μικρότερο δυνατό αριθμό παραγόμενων μηνυμάτων. Επιπλέον αποδείχτηκε πως η εφαρμογή της εν λόγω τεχνικής, σε έναν τυχαίο γράφο, μπορεί να επιτύχει μείωση του παραγόμενου αριθμού μηνυμάτων σε σύγκριση με την τεχνική της πιθανολογικής πλημμύρας. Κατόπιν μελετήθηκε η τεχνική των πολλαπλών ταυτόχρονων δρομέων (Multiple Random Walkers) και παρουσιάστηκαν αναλυτικές εκφράσεις για την κάλυψη που επιτυγχάνεται στην περίπτωση ενός πλήρους γράφου. Κατά τη μελέτη της απόδοσης, ως προς την κάλυψη, σε λιγότερο πυκνές τοπολογίες παρατηρήθηκε μια μικρή χρονική περίοδος στα πρώτα βήματα όπου η κάλυψη που επιτυγχάνεται δεν είναι αποδοτική. Το φαινόμενο οφείλεται στη συσσώρευση στον εναρκτήριο κόμβο ενός μεγάλου αριθμού δρομέων (σύμφωνα με την τεχνική των MRW) οι οποίοι χρειάζονται λίγο χρόνο μέχρι να σταματήσουν να επισκέπτονται επικαλυπτόμενες περιοχές του δικτύου και να καλύπτουν καινούργιους κόμβους. Για την αντιμετώπιση του φαινομένου αυτού προτάθηκε μια τεχνική με την οποία οι τυχαίοι δρομείς αναπαράγονται κατά τη διάρκεια της κίνησης τους μέσα στο δίκτυο και αποφεύγεται η εξαρχής συγκέντρωσης τους σε έναν κόμβο. Τα αποτελέσματα των προσομοιώσεων επιβεβαίωσαν την αποδοτικότερη κάλυψη που επιτυγχάνεται με την τεχνική αυτή. Στη συνέχεια μελετήθηκε η απόδοση της τεχνικής των τυχαίων αναπαραγωγών ως προς τον αριθμό των κόμβων που επισκέπτεται και τη διάταση της πληροφορίας που επιτυγχάνει σε διάφορες τοπολογίες δικτύων. Αποδείχτηκε ότι σε τοπολογίες οι οποίες καταφέρνουν να επιδείξουν την έννοια της γεωγραφικής απόστασης των κόμβων η απόδοση της τεχνικής των τυχαίων αναπαραγωγών μπορεί να καλύψει το κενό ανάμεσα στην απόδοση της τεχνικής της ολικής πλημμύρας και αυτής του μοναδικού τυχαίου δρομέα.