Αντικείμενο και Στόχος Εργασίας
Αντικείμενο της συγκεκριμένης εργασίας αποτελεί η μελέτη του δομημένου ομότιμου υπερκείμενου δικτύου (structured peer-to-peer overlay network) Pastry και η χρήση του στην ανάπτυξη μίας δικτυακής εφαρμογής διανομής αρχείων μουσικής.
Το Pastry συνιστά ένα σχήμα κατανεμημένου εντοπισμού και δρομολόγησης αντικειμένων (Distributed Object Location and Routing scheme – DOLR scheme), του οποίου τα σημαντικότερα χαρακτηριστικά είναι ο πλήρως αποκεντρωμένος έλεγχος, η αυτό-οργάνωση, η κλιμάκωση, η προσαρμοστικότητα, η αξιοπιστία και οι αποδοτικές τοπολογικές ιδιότητες. Η ιδέα στην οποία στηρίζονται τα δομημένα ομότιμα δίκτυα είναι η εξής: Οτιδήποτε αναζητείται στο δικτύο χαρακτηρίζεται από ένα αναγνωριστικό(identifier). Σε κάθε αντικείμενο αποδίδεται ένα αναγνωριστικό – κλειδί (key) και κάθε κόμβος (node) του δικτύου είναι υπεύθυνος να διατηρεί ένα σύνολο αντικειμένων που αντιστοιχίζονται σε ένα συγκεκριμένο εύρος τιμών του κλειδιού. Συνεπώς, σε ένα δίκτυο Pastry ο εντοπισμός και η δρομολόγηση αντικειμένων εκτελούνται σύμφωνα με την εξής θεμελιώδη αρχή: Δεδομένου ενός μηνύματος και ενός κλειδιού, ένας κόμβος του δικτύου Pastry δρομολογεί αποδοτικά το μήνυμα στον κόμβο του οποίου το αναγνωριστικό είναι αριθμητικά πλησιέστερο στο κλειδί, μεταξύ όλων των ενεργών κόμβων (route(msg, key)).
Αρχιτεκτονική Συστήματος
Δημιουργία δακτυλίου
Οι κόμβοι στο δίκτυο Pastry οργνώνονται σε ένα δακτύλιο (Pastry ring), όπου κάθε κόμβος χαρακτηρίζεται μοναδικά από ένα αριθμητικό αναγνωριστικό (nodeId). Το αναγνωριστικό κάθε κόμβου παράγεται εφαρμόζοντας τη συνάρτηση κατακερματισμού SHA-1 στο ζεύγος (διεύθυνση IP κόμβου, αριθμός θύρας εφαρμογής), με αποτέλεσμα το σύνολο των αναγνωριστικών των κόμβων να είναι ομοιόμορφα κατανεμημένο. Επίσης, κάθε κόμβος διατηρεί μία κατάσταση δρομολόγησης που αποτελείται από το σύνολο γειτόνων (neighborhood set), το σύνολο φύλλων (leaf set) και τον πίνακα δρομολόγησης (routing table). Το σύνολο γειτόνων και ο πίνακας δρομολόγησης συντίθενται βάσει μίας μετρικής εγγύτητας (proximity metric) στο Διαδίκτυο(Internet), η οποία αρχικά υπολογίζει τον αριθμό των βημάτων δρομολόγησης (routing hops number) και στη συνέχεια αξιολογεί το χρόνο διαδρομής μετ’ επιστροφής (round trip time - rtt) σε ένα καθορισμένο υποσύνολο του αρχικού αποτελέσματος, ώστε να αποφευχθούν καταστάσεις συμφόρησης.
Θεωρούμε μία ομάδα N χρηστών, οι οποίοι είναι διασυνδεδενένοι μέσω του Διαδικτύου και επιθυμούν να δημιουργήσουν το δίκτυο Pastry, ώστε να διανέμουν αρχεία μουσικής. Αρχικά, ένας από τους N κόμβους δημιουργεί το δακτύλιο παράγοντας το αναγνωριστικό του και αρχικοποιώντας την κατάσταση δρομολόγησής του ως κενή. Στη συνέχεια, κάθε νέος κόμβος, που επιθυμεί να εισαχθεί στο δακτύλιο με ένα νέο αναγνωριστικό, αρχικοποιεί την κατάσταση δρομολόγησής του επικοινωνώντας με τον πλησιέστερό του Pastry κόμβο (bootstrapped/rendezvous node), βάσει της μετρικής εγγύτητας, και αιτώντας τη δρομολόγηση ενός ειδικού μηνύματος συμμετοχής (join message), όπου η τιμή του κλειδιού τίθεται ίση με την τιμή του αναγνωριστικού του. Το μήνυμα δρομολογείται στον Pastry κόμβο με αναγνωριστικό αριθμητικά πλησιέστερο στο κλειδί. Ο νέος κόμβος ανακτά πληροφορίες από τον αρχικό Pastry κόμβο, τον Pastry κόμβο στον οποίο κατέληξε το μήνυμα και τους ενδιάμεσους Pastry κόμβους από τους οποίους διήλθε το μήνυμα. Χρησιμοποιώντας τις συγκεκριμένες πληροφορίες, ο νέος κόμβος αρχικοποιεί την κατάσταση δρομολόγησής του ορθά και γνωστοποιεί την άφιξή του στους Pastry κόμβους που απαιτείται.
Οι κόμβοι στο δίκτυο Pastry ανιχνεύουν επίσης μία απροειδοποίητη αναχώρηση ή αποτυχία ενός γειτονικού κόμβου μέσω της μη ανταπόκρισής του στην επικοινωνία. Στη συγκεκριμένη περίπτωση, διενεργείται ενημέρωση της κατάστασης δρομολόγησης τους μέσω επικοινωνίας με άλλους ενεργούς γειτονικούς κόμβους.
Εισαγωγή αντικειμένων και αντιστοίχιση αντικειμένων σε κόμβους
Τα αντικείμενα (αρχεία μουσικής) στο δίκτυο Pastry περιγράφονται μέσω κλειδιών που προκύπτουν από την εφαρμογή της συνάρτησης κατακερματισμού SHA-1 στην τριάδα (όνομα αρχείου, διεύθυνση IP κόμβου-ιδιοκτήτη, αριθμός θύρας εφαρμογής). Η εισαγωγή ενός αρχείου μουσικής επιτυγχάνεται μέσω της δρομολόγησης ενός μηνύματος εισαγωγής (insert message), όπου η τιμή του κλειδιού τίθεται ίση με την τιμή του κλειδιού του αρχείου προς εισαγωγή. Το μήνυμα δρομολογείται στον Pastry κόμβο με αναγνωριστικό αριθμητικά πλησιέστερο στο κλειδί. Στη συνέχεια, αντίγραφα του αρχείου αποθηκεύονται στους k-1 αριθμητικά πλησιέστερους στο κλειδί Pastry κόμβους (όπου k ≤ |leaf set|). Μέσω του συγκεκριμένου μηχανισμού, το δίκτυο Pastry επιτρέπει την ύπαρξη αντιγράφων, αυξάνοντας συνεπώς την αξιοπιστία και την επίδοση του συστήματος. Επίσης, το σύστημα επιτρέπει τη διαγραφή ενός αρχείου μουσικής μέσω της δρομολόγησης ενός μηνύματος διαγραφής (delete message), όπου η τιμή του κλειδιού τίθεται ίση με την τιμή του κλειδιού του αρχείου προς διαγραφή. Σημειώνεται ότι το αντικείμενο διαγράφεται τελικά και από τους k Pastry κόμβους στους οποίους είναι αντιστοιχισμένο.
Αναζήτηση αντικειμένων
Η αναζήτηση αρχείων μουσικής στο δίκτυο Pastry πραγματοποιείται μέσω της δρομολόγησης ενός μηνύματος αναζήτησης (lookup message), όπου η τιμή του κλειδιού τίθεται ίση με την τιμή του κλειδιού του αρχείου προς αναζήτηση. Ο ευρετικός μηχανισμός δρομολόγησης του συστήματος Pastry, ο οποίος αξιοποιεί και πληροφορίες σχετικά με τη φυσική τοπολογία, εξασφαλίζει ότι το μήνυμα θα καταλήξει στον πλησιέστερο Pastry κόμβο, βάσει της μετρικής εγγύτητας, μεταξύ των k Pastry κόμβων με αναγνωριστικά αριθμητικά πλησιέστερα στο κλειδί. Αναλυτικότερα, δεδομένου ενός μηνύματος αναζήτησης προς δρομολόγηση, ένας Pastry κόμβος αρχικά εξετάζει το σύνολο φύλλων του, ώστε να διαπιστώσει αν ο ίδιος ή κάποιος από τους άμεσους γείτονές του είναι «υπεύθυνος» για το ζητούμενο αρχείο μουσικής. Αν εντοπιστεί ένας «υπεύθυνος» κόμβος, το μήνυμα δρομολογείται άμεσα στον προορισμό του. Αν δεν εντοπιστεί ένα «υπεύθυνος» κόμβος στο σύνολο φύλλων, ο Pastry κόμβος χρησιμοποιεί τον πίνακα δρομολόγησης, προκειμένου να εντοπίσει έναν Pastry κόμβο, του οποίου το αναγνωριστικό έχει μεγαλύτερου μήκους κοινό πρόθεμα με το κλειδί συγκριτικά με το δικό του αναγνωριστικό. Ωστόσο, ενδέχεται ένας Pastry κόμβος με τη συγκεκριμένη ιδιότητα να μην αναφέρεται στον πίνακα δρομολόγησης ή να μην είναι ενεργός. Στη συγκεκριμένη περίπτωση, επιλέγεται ένας Pastry κόμβος από το σύνολο φύλλων, του οποίου το αναγνωριστικό έχει ίσου μήκους κοινό πρόθεμα με το κλειδί και είναι αριθμητικά πλησιέστερο στο κλειδί συγκριτικά με το αναγνωριστικό του τρέχοντος Pastry κόμβου.
