Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/562
Title: Πολλαπλή αποστολή δεδομένων σε DHT δίκτυα
Other Titles: Multicasting over DHTs
Authors: Καπρίτσος, Εμμανουήλ
Issue Date: 2007-10-23T07:01:53Z
Keywords: Κατανεμημένοι πίνακες κατακερματισμού
Δίκτυα ομοτίμων
Πολλαπλή αποστολή δεδομένων
Βελτιστοποίηση
Keywords (translated): DHT
P2p
Multicasting
Optimization
Abstract: Η ραγδαία ανάπτυξη του διαδικτύου και των τεχνολογιών που το υποστηρίζουν έχει οδηγήσει στην ραγδαία αύξηση των εφαρμογών διαμοίρασης δεδομένων. Ταυτόχρονα, οι ανάγκες για ταχεία μεταφορά δεδομένων γίνονται ολοένα και μεγαλύτερες. Μία από τις πιο απαιτητικές κατηγορίες εφαρμογών που διανέμουν πληροφορία είναι οι εφαρμογές πολλαπλής αποστολής δεδομένων. Σε αυτές τις εφαρμογές, ένας αποστολέας θέλει να στείλει δεδομένα σε μία ομάδα παραληπτών, οι οποίοι στη γενική περίπτωση είναι γεωγραφικά κατανεμημένοι. Είναι προφανές ότι ο αποστολέας δεν μπορεί να στείλει τα δεδομένα σε όλους τους παραλήπτες ταυτόχρονα, γιατί το έυρος ζώνης που διαθέτει είναι περιορισμένο, ενώ οι παραλήπτες μπορεί να είναι χιλιάδες. Έτσι, υιοθετείται συνήθως η τακτική δημιουργίας ενός δέντρου διανομής, όπου ο αρχικός κόμβος στέλνει σε μερικούς μόνο παραλήπτες, οι οπόιοι προωθούν το μήνυμα στα παιδιά τους κ.ο.κ. Το δέντρο διανομής συνήθως κατασκευάζεται πάνω από ένα δομημένο δίκτυο ομοτίμων (p2p networks) και πιο συγκεκριμένα πάνω από ένα δίκτυο βασισμένο σε Κατανεμημένους Πίνακες Κατακερματισμού (Distributed Hash Tables - DHT). Αυτή η τεχνική, αν και λύνει το πρόβλημα της πολλαπλής αποστολής, αντιμετωπίζει όμως κάποια προβλήματα. Πιο συγκεκριμένα, το δέντρο διανομής είναι στατικό, δηλαδή δεν μπορεί να μεταβληθούν οι συνδέσεις μεταξύ των κόμβων αν αλλάξουν οι συνθήκες του υφιστάμενου δικτύου. Ακόμα, δεν υπάρχει κάποιος έλεγχος για τις δυνατότητες των κόμβων που βρίσκονται στα υψηλότερα επίπεδα του δέντρου. Αυτό έχει σαν αποτέλεσμα το δέντρο να χάνει μεγάλο μέρος από την αποδοτικότητά του. Στα πλαίσια της εργασίας αυτής, μελετάμε τη δημιουργία ενός δυναμικού δέντρου διανομής, το οποίο μπορεί να αναπροσαρμόζεται στις εκάστοτε συνθήκες, αυξάνοντας έτσι σημαντικά τη συνολική αποδοτικότητα. Πιο συγκεκριμένα, η βασική μετρική είναι το εύρος ζώνης που παρατηρούν οι χρήστες κατα τη διάρκεια μιας αποστολής δεδομένων. Παρουσιάζουμε διάφορα στατιστικά στοιχεία που δείχνουν τη δραστική βελτίωση που επιτυγχάνουμε με τη χρήση του συγκεκριμένου αλγορίθμου. Ακόμα, μελετάμε τη δημιουργία ενός δέντρου διανομής που θα εκμεταλλεύεται τη δομή των DHT δίκτύων και θα μπορεί να διανέμει την πληροφορία αξιόπιστα (με χρήση erasure coding τεχνικών) ενώ θα εγγυάται ένα λογαριθμικό μέσο αριθμό βημάτων για την αποστολή των δεδομένων. Ταυτόχρονα, το σύστημα προσπαθεί να ισοκατανείμει το φόρτο προώθησης των μηνυμάτων σε όλους τους κόμβους του δικτύου. Και τα δύο συστήματα έχουν υλοποιηθέι και αξιολογηθεί χρησιμοποιώντας το DHT σύστημα Pastry και την υλοποίησή του σε Java (FreePastry).
Abstract (translated): The rapid evolution of the Internet and network technologies has led to an equally rapid increase in data dissemination applications. At the same time, the need for quick data transfer increase daily. One of the most demanding categories of information disseminating applications are file sharing applications. In these applications, one transmitter wants to send data to a group of receivers, that are geographically distributed. It is obvious that the transmitter can not send the data to all receivers simultaneously, because his bandwidth is limited , while the receivers may be hundreds or even thousands. Therefore, the most common method is that of the creation of a dissemination tree, where the initial node forwards the information to some recipients and they forward it to their children, etc. The dissemination tree is usually constructed over a peer-to-peer network, and specifically over a Distributed Hash Table (DHT) network. This method, although solves the problem of multicasting, faces some problems. First, the dissemination tree is static, which means that the connections between the nodes can not be rearranged, if the conditions of the underlying network change. Moreover, there is no control over the efficiency of the nodes in the highest levels of the tree. This leads to a significant drop in tree efficiency. In this thesis, we study the creation of a dynamic dissemination tree, which can adapt to the network conditions, thereby increasing the tree performance. Specifically, the basic evaluation metric is the bandwidth that end users perceive. We present evidence that shows the improvement that our algorithm imposes. We also study the creation of a dissemination tree that uses the existing DHT structure to efficiently and reliably (using erasure coding techniques) disseminate information and guarantees a logarithmic number of hops for message delivery. At the same time, the system tries to balance the load among all network nodes. Both systems were implemented and evaluated using the Pastry system and its implementation in Java (FreePastry).
Appears in Collections:Τμήμα Μηχανικών Η/Υ και Πληροφορικής (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
THESIS.PDF981.46 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.