Μια ομότιμη αρχιτεκτονική για ανταλλαγή περιεχομένου σε υπερκείμενα δίκτυα

Abstract

In this thesis a novel peer-to-peer architecture is presented, which provides users the capability to exchange content. Through an analytical theoretical and bibliographical study in peer-to-peer networks, and more specifically in architectures for systems based on Distributed Hash Tables (DHT) on top of Overlay Networks, it firstly describes the technological background of the study. The system follows the basic principals of DHT systems and more specifically those introduced by the Kademlia network, differentiating itself through the use of a K-ary tree structure for the production of a well defined and organized network with constrained number of neighboring nodes, which allows routing in logarithmic steps. The use of K-ary trees provides the system with the capability of both efficient routing and tolerance to network errors (due to node departure or communication failure). The architecture presented is based on the use of a neighborhood table which allows both the horizontal and vertical movement in the tree structure. Through this study the structure of the original architecture is analyzed and analytically presented for all of the basic functions that the system provides, namely those of insertion, publication, searching, departure and repair. It is then proven, through the results of a number of simulations that have been performed, the validity of the proposed design. More specifically, by extending the neurogrid simulator with the analytic model, it is initially proven that the system is able to route in logarithmic steps while retaining both a constant number of neighbors and a low total of network traffic (messages). A number of extensions is then present in addition to the basic algorithms that increases the system's tolerance to errors and its efficiency. The effect of these changes becomes even more evident through the results of another series of simulations, where the functionality of the system in environments with massive node failures (without the use of a repair mechanism) is presented. In order to further better the performance of the network, a repair algorithm is introduced, which is able to change the system's behavior during massive node failures and reduce the drop of successful inquires from logarithmic to linear, with respect to node failure percentage. This improvement becomes even more apparent with the inclusion of two additional extensions, those of replication schemas and virtual networks. The first one allows the publication and retrieval of content through the use of additional hash functions, while the second one introduces the concept of virtual networks, where each node belongs to more than one overlay network. The use of these two extension combined with the repair algorithm allows the network to successfully route even when the percentage of failing nodes surpasses that of 80% of the total node population. Once the effect of all these changes has been analyzed, a more general architecture is introduced, which provides the capability of varying the network's structure and behavior according to its performance and distribution of network load. In this architecture the capability of changing both the size of the K-ary tree and the routing behavior (from purely distributed to hybrid or pure hierarchical) is provided. This change offers the capability of using the network for different application domains, depending on the requirements with regards to work load distribution (across all levels of the K-ary tree) and optimal routing. Once the new system and all of its basic functionalities are presented in full detail, the results of a number of simulations are provided as means of assessing its performance and validating the variability it provides. Finally, once the new system has been thoroughly analyzed, a number of conclusions and open research issues are provided.

Στην διατριβή αυτή παρουσιάζεται μια πρωτότυπη ομότιμη αρχιτεκτονική, η οποία παρέχει στους χρήστες τη δυνατότητα ανταλλαγής περιεχομένου. Μέσα από μια αναλυτική θεωρητική και βιβλιογραφική αναφορά στα ομότιμα συστήματα και πιο συγκεκριμένα σε αρχιτεκτονικές συστημάτων που βασίζονται σε κατανεμημένους πίνακες κατατεμαχισμού (Distributed Hash Tables - DHT) πάνω σε υπερκείμενα δίκτυα (Overlay Networks), αναπτύσσεται αρχικά το τεχνολογικό υπόβαθρο της εργασίας αυτής. Το σύστημα ακολουθεί τις βασικές αρχές των συστημάτων DHT και πιο συγκεκριμένα ακολουθεί τις βασικές αρχές που εισήγαγε το δίκτυο Kademlia διαφοροποιώντας όμως ως προς τη χρήση Κ-δέντρων για την δημιουργία ενός καλά οργανωμένου δικτύου με σταθερό πίνακα γειτόνων, το οποίο έχει δυνατότητα δρομολόγησης σε λογαριθμικό αριθμό βημάτων. Η χρήση των Κ-δέντρων παρέχει στο σύστημα τη δυνατότητα γρήγορης δρομολόγησης αλλά και ανεκτικότητα ως προς την παρουσίαση σφαλμάτων στο δίκτυο (λόγω αποχώρησης κόμβων ή διακοπών στην επικοινωνία). Η αρχιτεκτονική που παρουσιάζεται βασίζεται στην χρήση ενός πίνακα γειτόνων που επιτρέπει τόσο την οριζόντια όσο και την κάθετη μετακίνηση στην δενδρική δομή. Μέσα από τη διατριβή αυτή αναλύεται η δομή της αρχικής αρχιτεκτονικής και παρουσιάζονται αναλυτικά οι βασικές διαδικασίες που παρέχει το σύστημα, αυτές της εισαγωγής, δημοσίευσης, αναζήτησης, εξόδου και επιδιόρθωσης. Στην συνέχεια, μέσα από την παρουσίαση των αποτελεσμάτων μιας σειράς εξομοιώσεων που έγιναν, αποδεικνύεται η ορθότητα της προτεινόμενης σχεδίασης. Πιο συγκεκριμένα, επεκτείνοντας τον εξομοιωτή neurogrid με βάση το αναλυτικό μοντέλο, αποδεικνύεται αρχικά ότι το σύστημα είναι σε θέση να δρομολογεί σε λογαριθμικό αριθμό βημάτων ενώ παράλληλα διατηρεί τον πίνακα γειτόνων σταθερό και τον αριθμό των συνολικών μηνυμάτων που ανταλλάσσονται στο δίκτυο πολύ χαμηλό. Εν συνεχεία παρουσιάζεται μια σειρά από επεκτάσεις στους βασικούς αλγορίθμους που αυξάνουν την ανεκτικότητα σε σφάλματα του δικτύου και βελτιώνουν την απόδοσή του. Η επίπτωση αυτών των αλλαγών γίνεται εμφανή μέσα από τα αποτελέσματα μιας ακόμα σειράς εξομοιώσεων, όπου παρουσιάζεται επίσης η λειτουργία του συστήματος σε περιβάλλον μαζικών αποχωρήσεων κόμβων (δίχως τη χρήση μηχανισμού επιδιόρθωσης). Για να βελτιωθεί ακόμα περισσότερο η συμπεριφορά του δικτύου, εισάγεται αρχικά ένας αλγόριθμο επιδιόρθωσης, ο οποίος επιτυγχάνει την αλλαγή της συμπεριφοράς του δικτύου κατά την μαζική αποχώρηση κόμβων, καθώς πλέον η μείωση των επιτυχών αναζητήσεων από λογαριθμική γίνεται γραμμική ως προς το ποσοστό σφαλμάτων. Η βελτίωση αυτή γίνεται ακόμα πιο αισθητή κατά την εισαγωγή δύο επεκτάσεων, αυτών των σχημάτων αντιγράφων και των εικονικών δικτύων. Η πρώτη επέκταση επιτρέπει τη δημοσίευση και αναζήτηση περιεχομένου με τη χρήστη επιπλέον συναρτήσεων κατατεμαχισμού, ενώ η δεύτερη εισάγει την έννοια των εικονικών δικτύων, όπου κάθε κόμβος ανήκει σε περισσότερα από ένα υπερκείμενα δίκτυα. Η χρήση αυτών των επεκτάσεων σε συνδυασμό με τον αλγόριθμο επιδιόρθωσης επιτρέπει στο δίκτυο να δρομολογεί επιτυχώς ακόμα και όταν το ποσοστό κόμβων που σφάλουν φτάνει το 80% του συνολικού πληθυσμού. Αφού αναλυθεί διεξοδικά η επίπτωση αυτών των αλλαγών, παρουσιάζεται μια πιο γενική αρχιτεκτονική, που δίνει τη δυνατότητα παραμετροποίησης με βάση την απόδοση και την κατανομή του φόρτου κίνησης. Στην αρχιτεκτονική αυτή δίδεται η δυνατότητα αλλαγής τόσο του μεγέθους του Κ-δέντρου όσο και του τρόπου δρομολόγησης (από καθαρά κατανεμημένο σε υβριδικό ή πλήρως ιεραρχικό). Η αλλαγή αυτή δίνει τη δυνατότητα χρήσης του δικτύου σε διαφορετικές εφαρμογές, ανάλογα με τις απαιτήσεις όσο αφορά την ομοιομορφία στην κατανομή του φόρτου κίνησης (σε όλα τα επίπεδα του Κ-δέντρου) και τη βέλτιστη δρομολόγηση. Αφού αρχικά παρουσιαστεί αναλυτικά το νέο σύστημα καθώς και όλες οι βασικές λειτουργίες, μέσα από μια σειρά εξομοιώσεων παρατίθεντο η απόδοσή του καθώς και η επιβεβαίωση των δυνατοτήτων παραμετροποίησης που παρέχει. Τέλος, αφού έχει αναλυθεί το νέο αυτό σύστημα, η διατριβή καταλήγει σε μια σειρά συμπερασμάτων και μελλοντικών ερευνητικών ζητημάτων.