Improving routing in unstructured Peer-to-Peer systems

Abstract

Recent years have seen the emergence of the deployment of many distributed systems of global scale. In addition, one of the age-long requirements and goals of distributed systems is the attainment of large degree of scalability, the ability of a system to cope with ever increasing number of participants. As one of the solutions to this problem, the Peer-to-Peer (P2P) paradigm was introduced and immediately received increasing attention. This leads to the quick evolution of the P2P systems, which branched out into two main categories, namely the structured and the unstructured systems. Structured systems are based on a more sophisticated way of interconnection between the participants of the system, which enables more efficient communication primitives. At the same time, this rigidness limits the scalability of those systems. Unstructured systems, on the other hand, are based on a more loose interconnection structure. Although this structure makes it easier for those systems to scale to global deployment, the communication primitives are less efficient, thus limiting their scaling ability. In this thesis we present an effort to tackle this problem of unstructured systems in many levels. We develop novel algorithms which enable the communication primitives of unstructured systems to better scale to a higher number of participants by reducing the functional costs not only for the P2P system itself but also for the network medium used. Contributions of this thesis include (i) a novel broadcast-like technique which generates a much smaller amount of network traffic, (ii) a new participants interconnection structure which enables more sophisticated search methods without transforming an unstructured system to a structured one and (iii) another, complementary or stand-alone method to create the P2P overlay so as to allow the system to work in the same manner a before, but at the same time reducing the traffic load imposed on the network medium used by the system.

Τα τελευταία χρόνια αναπτύχθηκαν πολλά κατανεμημένα συστήματα παγκόσμιας κλίμακας. Επιπλέον, χρόνια απαίτηση και στόχος των κατανεμημένων συστημάτων είναι η επίτευξη όσο το δυνατόν μεγαλύτερου βαθμού επεκτασιμότητας, της ικανότητας δηλαδή ενός συστήματος να ανταπεξέρχεται σε συνεχώς αυξανόμενο αριθμό μελών. Σαν λύση στο θέμα αυτό, προτάθηκε η φιλοσοφία των Ομότιμων Συστημάτων (ΟΣ) και αμέσως απέκτησε δημοτικότητα και την προσοχή της ερευνητικής κοινότητας. Αυτό οδήγησε στην γρήγορη εξέλιξη των ΟΣ, τα οποία διακλαδίστηκαν σε δύο βασικές κατηγορίες, τα δομημένα και τα μη-δομημένα συστήματα. Τα δομημένα συστήματα βασίζονται σε μια πιο πολύπλοκη μέθοδο διασύνδεσης μεταξύ των μελών του συστήματος, κάτι που επιτρέπει ποιο αποτελεσματικές βασικές λειτουργίες επικοινωνίας. Παράλληλα όμως, αυτή η “ακαμψία” μειώνει την επεκτασιμότητα αυτών των συστημάτων. Τα μη-δομημενα συστήματα, από την άλλη μεριά, βασίζονται σε μια πιο χαλαρή δομή διασύνδεσης των μελών. Παρόλο που το γεγονός αυτό διευκολύνει τα συστήματα αυτά να επιτύχουν παγκόσμια ανάπτυξη, οι λειτουργίες επικοινωνίας είναι λιγότερο αποτελεσματικές, με αποτέλεσμα να μειώνεται η επεκτασιμότητα. Σε αυτή την διατριβή θα παρουσιάσουμε μια προσπάθεια αντιμετώπισης αυτού του προβλήματος σε πολλά επίπεδα. Αναπτύξαμε και θα παρουσιάσουμε πρωτότυπους αλγορίθμους που επιτρέπουν στις βασικές λειτουργίες επικοινωνίας να επιτύχουν μεγαλύτερο βαθμό επεκτασιμότητας μειώνοντας τα λειτουργικά κόστη όχι μόνο για το ίδιο το ΟΣ αλλά και για το μέσο επικοινωνίας που χρησιμοποιεί. Οι συνεισφορές της παρούσας διατριβής συμπεριλαμβάνουν (i) μια πρωτότυπη τεχνική μαζικής επικοινωνίας που παράγει πολύ λιγότερο ποσό κίνησης στο δίκτυο, (ii) μια νέα δομή διασύνδεσης των μελών του συστήματος που επιτρέπει την ανάπτυξη ποιο αποτελεσματικών μεθόδων αναζήτησης και επικοινωνίας, χωρίς να μετατρέπεται το όσο σύστημα από μη-δομημένο σε δομημένο και (iii) μια, είτε συμπληρωματική είναι ανεξάρτητη, μέθοδο δημιουργίας του ΟΣ που επιτρέπει στο σύστημα το λειτουργεί με τον ίδιο τρόπο όπως πριν αλλά παράγοντας λιγότερη κίνηση στο δίκτυο.