Ενημέρωση 1 .

Η παρακάτω παρουσίαση αποτελεί την πρώτη ενημέρωση σχετικά με την πρόοδο της εργασίας.

Έως τώρα έχει κριθεί αναγκαία η δημιουργία 5 class και η χρήση μιας ακόμα opensource class η οποία έχει να κάνει με τον χειρισμό των numeric String.


Παρακάτω ακολουθεί μια πιο λεπτομερής παρουσίαση των class που προαναφέρθηκαν καθώς επίσης γίνεται αναφορά στην βασική λειτουργικότητά τους.

• ConsoleIO class
  

H class ConsoleIO αναλαμβάνει να εμφανίσει στον χρήστη ένα μενού στο οποίο ζητάται να καθοριστούν οι τιμές των Configuration paremeters. Στην συνέχεια η ίδια class αποθηκεύει αυτές τις τιμές. Διαθέτει επίσης μεθόδους public με τις μπορούν να προσπελαστούν οι τιμές των παραμέτρων b, L, M .

• FindIP class

H FindIP class είναι υπεύθυνη να εντοπίσει την IP address του localhost. Πιο συγκεκριμένα η μέθοδος getIP() επιστρέφει ένα String το οποίο είναι στην ουσία η IP address του peer.

• SHA1 class

Η SHA1 class είναι υπεύθυνη για την υλοποίηση της SHA1 συνάρτησης. Πιο συγκεκριμένα η μέθοδος convert() παίρνει ως όρισμα ένα String -που θα μπορούσε να είναι η IP του peer, και επιστρέφει ένα byte[] -το οποίο θα μπορούσε να παριστάνει το id του peer .

• IDhandler class

Η IDhandler class αναλαμβάνει να χειριστεί το id που επιστρέφει η συνάρτηση convert() -που υλοποιείται στην SHA1 class. Διαθέτει την μέθοδο IDasByteArray() η οποία δέχεται σαν είσοδο το byte[] που επιστρέφει η convert(). Σκοπός της είναι να επιστρέψει το byte[] της convert() ως ένα numeric String το οποίο θα είναι εκφρασμένο σε εκείνη την βάση (2^b, όπου b μια απο τις configuration parameters ) που επιλέγει ο χρήστης κατά την εμφάνιση του μενού καθορισμού των configuration parameters .

• Node class

Η Node class αναπαριστά τον κάθε peer του συστήματος και περιλαμβάνει όλες εκείνες τις λειτουργίες για την δημιουργία, διαχείρηση και ενημέρωση των leaf set, routing table και neighborhood list.

• Strings class

Αποτελεί μια υλοποίηση που διαχειρίζεται με μεγάλη αποδοτικότητα και αξιοπιστία τις συγκρίσεις numeric String .Επιλέξαμε να μην χρησιμοποιήσουμε την String class της Java και τις μεθόδους που αυτή παρέχει καθώς η σύγκριση των String γίνεται με λεξικογραφικά κριτήρια, ενώ εμείς επιθυμούμε την εφαρμογή αριθμητικών κριτηρίων. Να τονίσουμε πως η υλοποίηση της τάξης αυτής διατίθεται ελεύθερα στο διαδύκτιο .

Εργασία στο μάθημα των Κατανεμημένων Συστημάτων

ΟΙΚΟΝΟΜΙΚΟ ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΘΗΝΩΝ ΤΜΗΜΑ ΠΛΗΡΟΦΟΡΙΚΗΣ
ΚΑΤΑΝΕΜΗΜΕΝΑ ΣΥΣΤΗΜΑΤΑ

Υποχρεωτικό Μάθημα 5ου εξαμήνου Κύκλου ΙΙ
Φθινοπωρινό Εξάμηνο 2007-2008
Υποχρεωτικές Εργασίες


(a) Peer-to-Peer System

Το παράδειγμα (paradigm) του συστήματος ομοτίμων (peer-to-peer) έχει πρόσφατα γίνει πολύ δημοφιλές μέσω της δυνατότητας κοινής χρήσης και ανταλλαγής αρχείων,αντικειμένων, ψηφιακών δεδομένων και εφαρμογών πολυμέσων. Τα peer-to-peer συστήματα έχουν πολλά ενδιαφέροντα τεχνικά ζητήματα όπως η αποκέντρωση ελέγχου, αυτο-οργάνωση, προσαρμογή και επεκτασιμότητα. Χαρακτηριστικό αυτών των συστημάτων είναι ότι τόσο οι πόροι όσο και οι χρήστες είναι πολλοί σε πλήθος, με συχνές αφίξεις και αναχωρήσεις χρηστών. Ένα βασικό πρόβλημα που αντιμετωπίζουμε σε αυτές τις εφαρμογές είναι η αποδοτική εύρεση του κόμβου που αποθηκεύει το επιθυμητό στοιχείο δεδομένων.


Ο στόχος της εργασίας είναι η ανάπτυξη μιας εφαρμογής δικτύου καταμερισμού αντικειμένων (αρχείων, εφαρμογών πολυμέσων ή άλλων εφαρμογών) και μιας βιβλιοθήκης βασισμένης στο Pastry σύστημα ομοτίμων [1]. Κάθε κόμβος (peer) στο σύστημα έχει ένα μοναδικό, ομοιόμορφο τυχαία αναγνωριστικό (nodeId) σε ένα κυκλικό 128-bit αναγνωριστικό χώρο και είναι οργανωμένος στο δακτύλιο. Όταν παρουσιαστεί ένα μήνυμα και ένα αριθμητικό 128-bit κλειδί, ο κόμβος είναι υπεύθυνος να δρομολογήσει αποδοτικά το μήνυμα στον κόμβο με nodeId αριθμητικά πλησιέστερο στο κλειδί, μεταξύ όλων των κόμβων του συστήματος. Ο αναμενόμενος αριθμός βημάτων στο overlay δίκτυο είναι O (log N), ενώ το μέγεθος του πίνακα δρομολόγησης που τηρούνται σε κάθε κόμβο είναι μόνο O (log N) σε μέγεθος (όπου N είναι ο
αριθμός των κόμβων στο σύστημα).


Στόχος της εργασίας είναι η υλοποίηση του συστήματος αυτού με τις παρακάτω δυνατότητες:

• Δημιουργία δακτυλίου: οι κόμβοι στο σύστημα θα πρέπει να οργανωθούν σε ένα δακτύλιο.

Κάθε κόμβος στο σύστημα έχει ένα μοναδικό, ομοιόμορφο τυχαία αναγνωριστικό (nodeId) σε
ένα κυκλικό 128-bit αναγνωριστικό χώρο. Τα αναγνωριστικά των κόμβων μπορείτε να τα
επιλέξετε τυχαία και ομοιόμορφα, ώστε κόμβοι που είναι παρακείμενοι να ποικίλλουν
γεωγραφικά. Θα πρέπει να χρησιμοποιείται η SHA-1 συνάρτηση για να μετατρέπει τις
διευθύνσεις IP/θύρες TCP των κόμβων σε κλειδιά.

Κάθε κόμβος κρατά μια λίστα από δικτυακούς κόμβους (leaf nodes), μια γειτονιά λίστα
(neighborhood list), και έναν πίνακα δρομολόγησης (routing table). Η λίστα των δικτυακών
κόμβων αποτελείται από τους L / 2 πλησιέστερους κόμβους με βάση το αναγνωριστικό, προς
κάθε κατεύθυνση γύρω από τον κύκλο. Η γειτονιά λίστα αποτελείται από τους πλησιέστερους Mκόμβους με βάση τη μετρική δρομολόγησης. Ο πίνακας δρομολόγησης περιέχει τις διευθύνσεις των πλησιέστερων γνωστών κόμβων και χρησιμοποιείται για τη δρομολόγηση. Για τη μετρική δρομολόγησης το σύστημα θα πρέπει να λάβει υπ’ όψην του την εγγύτητα (proximity) στο Internet. Ο δακτύλιος θα πρέπει να προσαρμόζεται δυναμικά στην άφιξη, αναχώρηση και αποτυχία κόμβων.

• Αντιστοίχιση αντικειμένων σε κόμβους:

Κάθε αντικείμενο εφαρμογής είναι καταχωρημένομοναδικά. Το αντικείμενο περιγράφεται από ένα αναγνωριστικό (objId) και αντιστοιχίζεται σε έναν ή περισσότερους κόμβους (κ >=1) (με αναγνωριστικά nodeIds), έτσι ώστε οι κόμβοι να έχουν nodeIds αριθμητικά πλησιέστερα στο αναγνωριστικό του αντικειμένου objId. Ο αριθμός k αντανακλά την εφαρμογή της επιθυμητό βαθμό αναπαραγωγής για το αντικείμενο.

• Εισαγωγή αντικειμένων:
  

Tα αντικείμενα μπορούν να εισαχθούν από τη δρομολόγηση ενόςμηνύματος,χρησιμοποιώντας το objId ως το κλειδί. Όταν το μήνυμα φθάσει σε κόμβο με ένα από τους πλησιέστερους k nodeIds στο objId, ο κόμβος αναπαράγει το αντικείμενο μεταξύ των άλλων κ-1 κόμβων με το πλησιέστερο nodeIds (τα οποία είναι, εξ ορισμού, στο ίδιο σύνολο φύλλων (leaf set) που έχουν τεθεί για k <= L / 2). Θα πρέπει να χρησιμοποιείται η SHA-1 συνάρτηση για να μετατρέπει τα ονόματα των αρχείων καθώς και τις διευθύνσεις IP/θύρες TCP των κόμβων σε κλειδιά. Θα πρέπει να υπάρχει δυνατότητα και για διαγραφή αντικειμένων από
το σύστημα.

• Αναζήτηση αντικειμένων:

Kάθε αντικείμενο μπορεί να ανευρεθεί ή να ανακτηθεί από τη δρομολόγηση ενός μηνύματος, χρησιμοποιώντας το objId ως το κλειδί. Το μήνυμα θα πρέπει να καταλήξει σε κόμβο που διατηρεί ένα αντίγραφο του αντικειμένου που ζητήθηκε, εκτός και αν όλοι οι k κόμβοι με nodeIds πλησιέστερο στον objId έχουν αποτύχει.
Ένα μήνυμα αναζήτησης μπορεί να κατευθύνεται προς οποιαδήποτε διεύθυνση στο δακτύλιο αν υπάρχει peer με το εν λόγω nodeId. Το μήνυμα δρομολογείται προς τη σωστή θέση στο
δακτύλιο και ο κόμβος με nodeId πλησιέστερο στον επιθυμητό προορισμό θα λάβει το πακέτο.
Κάθε φορά που ένας peer λαμβάνει ένα μήνυμα για δρομολόγηση ή θέλει να στείλει ένα μήνυμα, πρώτα εξετάζει τα φύλλα και δρομολογεί το μήνυμα απευθείας προς τη σωστή κόμβο εάν εντοπιστεί. Σε περίπτωση αποτυχίας, ο peer διαβουλεύεται τον πίνακα δρομολόγησης με στόχο την εύρεση της διεύθυνσης ενός κόμβου η οποία έχει το μεγαλύτερο κοινό πρόθεμα με τη
διεύθυνση προορισμού, σε σχέση με τον ίδιο τον peer. Αν ο peer δεν έχει επαφές με το
μεγαλύτερο πρόθεμα ή η επαφή έχει πεθάνει, θα επιλέξετε ένα peer από την λίστα επαφών με
πρόθεμα του ίδιου μήκους του οποίου το nodeId είναι αριθμητικά πιο κοντά στον τόπο
προορισμού και να στείλει το μήνυμα σε αυτόν τον peer.


Ομάδες: Όλοι οι φοιτητές θα πρέπει να σχηματίσουν ομάδες των δύο (2) ατόμων ή τριών (3) προκειμένου να εκπονήσουν την προγραμματιστική τους εργασία. Γλώσσα προγραμματισμού θα είναι η Java, στην οποίακαι θα παρέχεται υποστήριξη από το βοηθό του μαθήματος.


Παραδοτέα

1. Το πρώτο παραδοτέο θα αφορά στην αρχιτεκτονική του συστήματος. Θα πρέπει να σχεδιαστεί η αρχιτεκτονική του τελικού συστήματος λαμβάνοντας υπόψη φυσικά και τα χαρακτηριστικά που περιγράψαμε παραπάνω. Στο παραδοτέο θα σχεδιάσετε την αρχιτεκτονική του τελικού συστήματος όπου θα περιγράφονται με λεπτομέρεια οι δομοενότητες λογισμικού που θα αποτελούν το τελικό σύστημα, και θα παρουσιάζεται ένα σενάριο χρήσης του στο οποίο θα περιγράφονται όλες οι αποστολές δεδομένων μέσω του υποκείμενου δικτύου καθώς η ανταλλαγή δεδομένων μεταξύ των δομοενοτήτων
λογισμικού.
Ημερομηνία παράδοσης: 24/11/2008

2. Το δεύτερο παραδοτέο θα είναι η κατασκευή ενός blog στο οποίο θα παρουσιάζεται η αρχιτεκτονική του συστήματος και στο οποίο θα αναφέρονται τα βήματα προόδου της εργασίας. Κάθε σημαντικό βήμα ή και πρόβλημα που θα συναντάται κατά τη διάρκεια της εργασίας θα αναρτάται στο blog αυτό.
Ημερομηνία παράδοσης: 15/12/2008

3. Τελικό παραδοτέο. Ο πηγαίος κώδικας μαζί με το πλήρως ενημερωμένο blog. Στο blog θα παρέχετε αναλυτική τεκμηρίωση του συστήματος που αναπτύξατε στο οποίο θα πρέπει να περιγράφονται αναλυτικά:

a. Ποια αρχεία αποτελούν την τελική εφαρμογή και πώς σχετίζονται μεταξύ τους

b. Αποκλίσεις από τις προδιαγραφές του πρώτου παραδοτέου

c. Πώς εκτελείται ακριβώς η εφαρμογή μαζί με παραδείγματα και screen shots

Ο πηγαίος κώδικας θα πρέπει να είναι αναρτημένος επίσης στο blog.
Ημερομηνία παράδοσης: 18/1/2009



Βαθμολόγηση

Κάθε ομάδα θα πρέπει να κάνει μία επίδειξη λειτουργίας της εργασίας της κατά τη διάρκεια της εξεταστικής περιόδου, στα πλαίσια της οποίας θα εξεταστούν τα μέλη της ομάδας. Όσες ομάδες δεν παρουσιάσουν τις εργασίες τους θα μηδενιστούν. Ο βαθμός της εργασίας θα αποτελέσει το 60% του τελικού βαθμού κάθε μέλους της ομάδας.


Αναφορές/Χρήσιμοι σύνδεσμοι
[1] “Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems”, A.Rowstron and P. Druschel, IFIP/ACM Middleware 2001, Heidelberg, Germany.