Πανεπιστήμιο Κρήτης

Σχολή Θετικών Επιστημών

Τμήμα Επιστήμης Υπολογιστών

 

 

 

 

 

Ανακάλυψη της τοπολογίας του δικτύου Gnutella και μελέτη της απόδοσης του

Κωνσταντίνος Ξυνίδης

 

 

 

 

Διπλωματική Εργασία

 

 

 

 

 

 

 

 

 

 

 

 

Ιούλιος 2002

Ηράκλειο

 

Ανακάλυψη της τοπολογίας του δικτύου Gnutella και μελέτη της απόδοσης του

Κωνσταντίνος Ξυνίδης

Διπλωματική εργασία

Τμήμα Επιστήμης Υπολογιστών

Πανεπιστήμιο Κρήτης

 

 

ΠΕΡΙΛΗΨΗ

 

Τα μη δομημένα Peer-to-Peer συστήματα όπως το Gnutella είναι ελκυστικά για συγκεκριμένες εφαρμογές επειδή δεν απαιτούν έλεγχο όσο αφορά την τοπολογία του δικτύου ή την τοποθέτηση των δεδομένων. Παρόλα αυτά ο αλγόριθμος που χρησιμοποιείται τώρα στο Gnutella δεν μπορεί να χρησιμοποιηθεί για μεγάλα δίκτυα. Κάθε ερώτηση δημιουργεί μεγάλη κίνηση και μεγάλα συστήματα πολύ γρήγορα κατακλύζονται από την κίνηση αυτή. Στην εργασία αυτή μελετήθηκε, μέσω προσομοίωσης, το κατά πόσο είναι εφικτό να επιτύχουμε μικρότερη κίνηση κρατώντας τον κλασικό αλγόριθμο δρομολόγησης του Gnutella και μεταβάλλοντας την τοπολογία του δικτύου. Επίσης, ένα μέρος της εργασίας αυτής ασχολείται με την ανακάλυψη, μέσω προσομοίωσης, εναλλακτικών λύσεων του αλγορίθμου δρομολόγησης που χρησιμοποιεί το Gnutella. Προτείνεται, ένας αλγόριθμος δρομολόγησης ο οποίος δεν θα στέλνει μηνύματα σε όλους τους γείτονες ενός κόμβου αλλά σε ορισμένους ανάλογα με τον αριθμό των hops που έχει διανύσει το μήνυμα στο δίκτυο.

 

 

 

 

Επόπτης : Ευάγγελος Μαρκάτος, Αναπληρωτής Καθηγητής

Discovery of the topology of Gnutella network and study of its performance

 

Konstantinos Xinidis

 

Diploma Thesis

 

Department of Computer Science

University of Crete

 

ABSTRACT

 

Unstructured Peer-to-Peer networks such as Gnutella are attractive for certain applications because they require no precise control over network topology or data placement. However, the query algorithm used in Gnutella does not scale. Each query generates a large amount of traffic and large systems quickly become overwhelmed by the query-induced load. In this project we study, through simulation, if it is possible to achieve less traffic by keeping the classical routing algorithm of Gnutella and changing the network topology. Also, a portion of this project explores, through simulation, various alternatives to Gnutella’s query algorithm. We propose a routing algorithm, which does not send messages to all the neighbors of a node but to some of them according to the number of hops that the messages have traveled.

 

 

 

 

Supervisor: Evangelos Markatos, Assistant Professor

 

Ευχαριστίες

Ευχαριστίες

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

Ο επόπτης καθηγητής κ. Ευάγγελος Μαρκάτος μου έδωσε την δυνατότητα να ασχοληθώ με το θέμα των Peer-to-Peer δικτύων και με καθοδήγησε σε όλη την διάρκεια της εργασίας μου.

Ο συμφοιτητής και φίλος μου Κώστας Δημητρίου βοήθησε αποφασιστικά σε αρκετές φάσεις της εργασίας μου με τα πολύ εύστοχα σχόλια του.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Περιεχόμενα

 

Ευχαριστίες. 3

Ευχαριστίες. 3

Περιεχόμενα. 4

Εισαγωγή. 6

1.     Γενικά για Peer-to-Peer συστήματα. 6

2.     Περιγραφή του πρωτοκόλλου Gnutella. 6

Gnutella crawler. 9

1.     Περιγραφή λειτουργίας του crawler 9

1.1.      Γενική περιγραφή λειτουργίας του crawler 9

1.2.      Πως τρέχει ο crawler 12

1.3.      Περιορισμοί 12

2.     Περιγραφή υλοποίησης του crawler 13

2.1.      Γλώσσα υλοποίησης. 13

2.2.      Μη κατανεμημένη έκδοση του crawler 13

2.2.1.       Σχολιασμός σημαντικών σημείων της υλοποίησης. 15

2.3.      Κατανεμημένη έκδοση του crawler 17

2.3.1.       Παρατηρήσεις για τον client 18

2.3.2.       Παρατηρήσεις για τον server 18

Ανάλυση των αποτελεσμάτων. 19

1.     Κατασκευή του γράφου. 19

2.     Σκοπός της μελέτης. 20

3.     Κόμβοι που απορρίφθηκαν κατά την ανάλυση. 21

4.     Προγράμματα που κατασκευάσθηκαν. 21

5.     Γραφικές παραστάσεις που κατασκευάσθηκαν. 24

Προσομοιωτής του Gnutella. 30

1.     Στόχος του προσομοιωτή. 30

3.     Υλοποίηση. 30

2.     Παράμετροι που δέχεται ο προσομοιωτής. 31

4.     Μεθοδολογία προσομοίωσης. 37

5.     Αποτελέσματα που βγάζει ο προσομοιωτής. 37

6.     Αποτελέσματα. 38

Οπτικοποίηση του δικτύου που ανακαλύφθηκε. 43

1.     Ενδεικτικά αποτελέσματα. 43

Συμπεράσματα. 45

Παράρτημα. 46

1.     Βιβλιογραφία. 46

2.     Αναφορές στο διαδίκτυο. 47

 

Κατάλογος Σχημάτων και Γραφημάτων

 

Σχήμα 1 Τρόπος λειτουργίας του crawler.................................................................................... 10

Σχήμα 2  Διάγραμμα κλάσεων της μη κατανεμημένης έκδοσης του crawler. 14

Σχήμα 3  Διάγραμμα κλάσεων του client..................................................................................... 17

Σχήμα 4 Διάγραμμα κλάσεων του server..................................................................................... 18

Σχήμα 5 Πίνακας γειτονίας.................................................................................................................... 19

Σχήμα 6  Λίστα γειτονίας.......................................................................................................................... 20

Εικόνα 1 Otter.................................................................................................................................................. 43

Εικόνα 2 Plankton......................................................................................................................................... 44

 

 

 

 

 

 

 

 

Κεφάλαιο 1

 

Εισαγωγή

 

1.    Γενικά για Peer-to-Peer συστήματα.

 

Σε αντίθεση με τα κλασικά κατανεμημένα συστήματα, τα P2P δίκτυα σκοπεύουν να συναθροίσουν έναν μεγάλο αριθμό από υπολογιστές οι οποίοι συνδέονται και αποσυνδέονται από το δίκτυο τακτικά. Στα αυθεντικά P2P συστήματα, ανεξάρτητοι υπολογιστές επικοινωνούν μεταξύ τους και μοιράζονται πληροφορίες χωρίς να χρησιμοποιούν κάποιον εξυπηρετητή. Ένα χαρακτηριστικό αυτής της οικογένειας συστημάτων είναι ότι "χτίζουν" στο επίπεδο εφαρμογής ένα ιδεατό δίκτυο με τους δικούς του μηχανισμούς δρομολόγησης. Η τοπολογία αυτού του ιδεατού δικτύου και οι μηχανισμοί δρομολόγησης που χρησιμοποιούνται έχουν σημαντική επίδραση στην αποδοτικότητα της εφαρμογής. Στην εργασία αυτή μελετήθηκαν πιθανοί τρόποι βελτίωσης της απόδοσης ενός ευρέως διαδεδομένου P2P συστήματος, του Gnutella, αλλάζοντας την τοπολογία του δικτύου καθώς και το πρωτόκολλο δρομολόγησης.

 

2.    Περιγραφή του πρωτοκόλλου Gnutella.

 

Το πρωτόκολλο Gnutella είναι ένα ανοιχτό πρωτόκολλο που χρησιμοποιείται κυρίως για διαμοίραση αρχείων. Ο όρος Gnutella επίσης επιλέχθηκε για το ιδεατό δίκτυο από υπολογιστές που έχουν πρόσβαση στο διαδίκτυο και τρέχουν κάποια εφαρμογή που μιλάει το πρωτόκολλο Gnutella. Οι κόμβοι του Gnutella, ονομάζονται servents και εκτελούν λειτουργίες που σχετίζονται τόσο με εξυπηρετητές (servers) όσο και με πελάτες (clients). Παρέχουν διεπαφές μέσω των οποίων οι χρήστες μπορούν να κάνουν ερωτήσεις και να δουν τα αποτελέσματα, να δεχτούν ερωτήσεις από άλλους servents, να ελέγξουν αν μπορούν να απαντήσουν, και αν ναι, να στείλουν τα αποτελέσματα. Οι ίδιοι κόμβοι είναι υπεύθυνοι για την διαχείριση της κίνησης η οποία υπάρχει και χρησιμοποιείται για την ακεραιότητα του δικτύου.

Για να μπορέσει ένας νέος κόμβος να συνδεθεί στο Gnutella πρέπει πρώτα να συνδεθεί με έναν από ένα πλήθος γνωστών κόμβων οι οποίοι είναι πάντοτε διαθέσιμοι (π.χ router.limewire.com). Έχοντας συνδεθεί στο δίκτυο (έχοντας μία ή περισσότερες ανοιχτές συνδέσεις με κόμβους ήδη συνδεδεμένους στο Gnutella), οι κόμβοι στέλνουν μηνύματα για να αλληλεπιδρούν μεταξύ τους. Τα μηνύματα μπορεί να γίνονται broadcast (π.χ στέλνονται σε όλους τους κόμβους με τους οποίους ο αποστολέας έχει ανοιχτές συνδέσεις) ή απλά να διαδίδονται προς τα πίσω (back-propagated)(π.χ να στέλνονται σε μία συγκεκριμένη σύνδεση στην αντίθετη κατεύθυνση από την διαδρομή που ακολούθησε ένα αρχικό broadcasted μήνυμα). Αρκετά χαρακτηριστικά του πρωτοκόλλου επιτυγχάνουν αυτόν τον μηχανισμό broadcast/back-propagation. Πρώτον, κάθε μήνυμα έχει ένα μοναδικό αριθμό. Δεύτερον, κάθε κόμβος κρατάει στην μνήμη του τα πιο πρόσφατα μηνύματα που δρομολόγησε και χρησιμοποιείται για να αποτρέψει το re-broadcasting και να κάνει εφικτή την υλοποίηση του back-propagation. Τρίτον, τα μηνύματα έχουν ένα πεδίο Time-to-live (TTL) και ένα πεδίο "Hops taken".

Τα μηνύματα που επιτρέπονται στο δίκτυο είναι PING, PONG, QUERY, QUERYHIT και PUSH. Τα μηνύματα PING και PONG χρησιμοποιούνται για την συντήρηση του δικτύου ενώ τα QUERY, QUERYHIT και PUSH για την αναζήτηση αρχείων. Η παραλαβή των αρχείων γίνεται χρησιμοποιώντας το πρωτόκολλο HTTP με απευθείας σύνδεση των δύο κόμβων(αυτού που έχει το αρχείο και αυτού που θέλει να το αποκτήσει).

Ανακεφαλαιώνοντας, για να γίνει μέλος του δικτύου, ένας κόμβος πρέπει να ανοίξει μία ή περισσότερες συνδέσεις με κόμβους οι οποίοι είναι ήδη στο δίκτυο. Στο δυναμικό περιβάλλον όπου το δίκτυο Gnutella λειτουργεί, κόμβοι συχνά συνδέονται και αποσυνδέονται και οι συνδέσεις είναι αναξιόπιστες. Για να συμβιβαστεί με αυτό το περιβάλλον, αφού έχει συνδεθεί με το δίκτυο, ένας κόμβος περιοδικά στέλνει μηνύματα PING στους γείτονες του (γείτονες είναι οι κόμβοι με τους οποίους έχει ανοιχτές συνδέσεις) για να ανακαλύψει και άλλους κόμβους. Χρησιμοποιώντας αυτή την πληροφορία, ένας μη συνδεμένος κόμβος μπορεί σχεδόν πάντα να συνδεθεί με το δίκτυο. Οι κόμβοι αποφασίζουν που θα συνδεθούν στο δίκτυο βασιζόμενοι μόνο σε τοπική πληροφορία και έτσι συνθέτουν ένα δυναμικό δίκτυο από ανεξάρτητες οντότητες. Αυτό το ιδεατό δίκτυο έχει τους servents για κόμβους του και τις ανοιχτές TCP συνδέσεις για συνδέσμους(links).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Κεφάλαιο 2

 

Gnutella crawler

 

 

 

1.    Περιγραφή λειτουργίας του crawler

1.1. Γενική περιγραφή λειτουργίας του crawler

 

Ως μέρος αυτής της εργασίας αναπτύχθηκε ένας crawler ο οποίος συνδέεται στο δίκτυο Gnutella σαν servent και χρησιμοποιεί τον μηχανισμό PING-PONG για να μαζέψει πληροφορία για την τοπολογία του δικτύου. Ο crawler ξεκινάει δίνοντας του μία λίστα από κόμβους (μπορεί να περιέχει και μόνο έναν), ανοίγει TCP σύνδεση με κάθε κόμβο που βρίσκεται στην λίστα και στέλνει ένα PING με TTL 2. Οι κόμβοι που λαμβάνουν τα PING μηνύματα απαντούν με PONG μηνύματα. Τα PONG μηνύματα τα διαβάζει ο crawler και προσθέτει τους κόμβους που τα έστειλαν στην λίστα με τους κόμβους που έχει ανακαλύψει. Μετά, αναδρομικά, ο crawler συνδέεται με τους κόμβους που μόλις ανακάλυψε και επαναλαμβάνει αυτά που έκανε και πριν.

Ο ψευδοκώδικας που περιγράφει την παραπάνω διαδικασία είναι ο εξής

Procedure findGraph(H,L)   
Input: A initial host list H and an empty list with edges L
Output: A list H with all the hosts found and the edges between the hosts

for each element h of H

begin
     connect to h
     if (connection is successful)

     begin
          send ping message with TTL = 2

          for (all Pong messages received)
          begin

               if (h2 != h and edge h – h2 not in L)

               begin
                    add edge h – h2 to L
                    if ( h2 is not in H)
                         add h2 to the end of H

               end

          end

     end

end

 

Για να γίνει πιο ξεκάθαρο το πώς ακριβώς δουλεύει o crawler δίνεται το ακόλουθο παράδειγμα (Βλέπε σχήμα 1).

 

Σχήμα 1 Τρόπος λειτουργίας του crawler

Έστω ότι ο crawler τρέχει στον υπολογιστή Χ και έστω ότι η αρχική λίστα περιέχει τους κόμβους A, B, C. Τότε ο Χ θα στείλει 3 μηνύματα PING στους A, B, C με TTL 2. Ας εξετάσουμε τι συμβαίνει σε έναν από τους A, B, C μιας και η διαδικασία είναι η ίδια και για τους τρεις. Παίρνοντας τον Α έχουμε

1.      Επειδή το μήνυμα ήταν PING ο Α είναι υποχρεωμένος να απαντήσει με ένα PONG σε αυτόν από τον οποίο έλαβε το PING, δηλαδή στον Χ.

2.      Ο Χ λαμβάνει το PONG και βλέπει ότι το πεδίο Hops είναι ίσο με 1 οπότε το αγνοεί αφού αυτό σημαίνει ότι τον έχει ήδη ανακαλύψει.

3.      Ο Α μειώνει το πεδίο TTL του μηνύματος κατά 1 και ελέγχει αν είναι ίσο με 0.

4.      Δεν είναι οπότε προωθεί το μήνυμα σε όλους τους γείτονες του, δηλαδή στους D, E.

5.      Οι D, E μειώνουν και αυτοί το πεδίο TTL του μηνύματος κατά 1 και ελέγχει αν είναι ίσο με 0. Είναι οπότε δεν προωθούν το μήνυμα στους γείτονες τους, δηλαδή τον G.

6.      Επειδή το μήνυμα ήταν PING οι D, E είναι υποχρεωμένοι να απαντήσoυν με PONG σε αυτούς από τους οποίους έλαβαν τα PING.

7.      Ο Α λαμβάνει τα δύο μηνύματα PONG και βλέπει ότι είναι απαντήσεις στο PING που έλαβε από τον Χ.

8.      Ο Α προωθεί τα PONG στον Χ.

9.      Ο Χ βλέπει ότι το πεδίο Hops είναι 2 και προσθέτει τους D, E στην λίστα με τους κόμβους που έχει ανακαλύψει.

10.  Ο Χ ανοίγει TCP σύνδεση με τους D, E και επαναλαμβάνει την ίδια διαδικασία.

 

Βέβαια, όλα αυτά που περιγράφηκαν ισχύουν για την μη κατανεμημένη έκδοση του crawler. Ο πιο απλός τρόπος για να κάνουμε τον παραπάνω αλγόριθμο να τρέχει παράλληλα είναι να μοιράσουμε την αρχική λίστα από κόμβους. Κάθε υπολογιστής έτσι είναι υπεύθυνος για να ανακαλύψει μόνο ένα μέρος από τους κόμβους του Gnutella. Επιπρόσθετα, κάθε υπολογιστής θα ήταν σωστό να έχει έναν τρόπο να γνωρίζει εάν ο κόμβος που μόλις ανακάλυψε έχει ήδη βρεθεί από άλλον υπολογιστή. Υπάρχουν πολλοί τρόποι να γίνει αυτό αλλά όλοι τους απαιτούν επικοινωνία μεταξύ του συγκεκριμένου υπολογιστή και ενός άλλου αυξάνοντας έτσι τον φόρτο τόσο του δικτύου όσο και του υπολογιστή που θα κρατάει την βάση με τους κόμβους που ανακαλύφθηκαν και τις μεταξύ τους συνδέσεις. Για τον λόγο αυτό προτιμήθηκε μια λιγότερο κομψή λύση. Κάθε υπολογιστής εκτελεί τον αλγόριθμο που περιγράφηκε παραπάνω και ανακαλύπτει ένα μέρος του δικτύου χωρίς να ελέγχει εάν αυτός που βρήκε έχει βρεθεί ήδη από κάποιον άλλο. Η δουλειά αυτή ανατίθεται σε αυτόν τον υπολογιστή που δέχεται τα αποτελέσματα όλων των άλλων. Φυσικά, το γεγονός ότι η κατανεμημένη έκδοση του crawler μπορεί να επισκεφθεί έναν κόμβο περισσότερες από μία φορές δεν δημιουργεί καμία ασυνέπεια στον ανακαλυπτόμενο γράφο. Αντιθέτως, η τεχνική αυτή βοηθάει στην επίλυση ενός προβλήματος που περιγράφω παρακάτω και έχει να κάνει με την αδυναμία ενός κόμβου να απαντήσει σε μηνύματα PING λόγω φόρτου ή άλλων προσωρινών προβλημάτων.

 

 

1.2. Πως τρέχει ο crawler

 

Όπως αναφέρθηκε και προηγουμένως για να τρέξει ο crawler απαιτείται μια λίστα με κόμβους οι οποίοι βρίσκονται ήδη συνδεδεμένοι στο δίκτυο Gnutella. Οι κόμβοι που περιέχονται σε αυτή την λίστα δεν είναι απαραίτητο να βρίσκονται όλοι συνδεδεμένοι στο Gnutella. Αν κάποιοι δεν είναι τότε ο crawler απλώς τους αγνοεί αφού έχει αποτύχει η προσπάθεια σύνδεσης του με αυτούς. Αυτό είναι απαραίτητο να συμβαίνει μίας και λόγω της δυναμικής φύσης του Gnutella πολλοί κόμβοι συνδέονται και αποσυνδέονται κάθε λεπτό οπότε θα ήταν σχεδόν αδύνατο να έχουμε μια λίστα όλοι οι κόμβοι της οποίας θα βρίσκονται συνδεδεμένοι στο δίκτυο Gnutella.

Συνεχίζοντας, για να είναι δυνατή η ανακάλυψη όσο το δυνατόν περισσότερων κόμβων εφαρμόσθηκε η εξής τεχνική. Αρχικά, επειδή είναι πολύ πιθανόν να έχουμε μόνο έναν αρχικό κόμβο, π.χ τον Gnutella client που τρέχει στο μηχάνημα μας, τρέχουμε τον crawler για μερικά λεπτά με έναν μόνο αρχικό κόμβο και ανακαλύπτουμε για παράδειγμα 1000 κόμβους. Κατόπιν, βάζουμε αυτούς τους κόμβους ως αρχικούς και τρέχουμε ξανά τον crawler. Με τον τρόπο αυτό δίνουμε στον crawler την δυνατότητα να αναπτυχθεί πολύ γρήγορα στο δίκτυο και να ανακαλύψει στον ίδιο χρόνο περισσότερους κόμβους.

Επίσης, υπάρχει και μία άλλη τεχνική που όμως είναι λίγο πιο δύσκολο να εφαρμοστεί μιας και πρέπει να είναι προμελετημένη. Πιο συγκεκριμένα, κάθε φορά που τρέχουμε τον crawler και ανακαλύπτουμε κάποιους κόμβους τους αποθηκεύουμε σε ένα άλλο αρχείο (λίστα) το οποίο κρατάει όλους τους κόμβους που έχουν ανακαλυφθεί π.χ τον τελευταίο μήνα. Με την πάροδο του χρόνου αυτή η λίστα μπορεί να γίνει πολύ μεγάλη π.χ 500 χιλιάδες κόμβοι. Μετά τρέχουμε τον crawler με την λίστα αυτή ως αρχική λίστα οπότε το μόνο που θα κάνει ο crawler είναι να ελέγχει εάν οι κόμβοι συνεχίζουν να είναι συνδεδεμένοι στο Gnutella. Η τεχνική αυτή είναι πιο γρήγορη από την προηγούμενη και έχει υλοποιηθεί και ελεγχθεί με επιτυχία στον crawler.[1]

1.3. Περιορισμοί

 

Οι κύριοι περιορισμοί του crawler σχετίζονται με την έννοια των ιδιωτικών δικτύων (Private Networks). Μιας και ένα σημαντικό κομμάτι των χρηστών του Gnutella βρίσκονται πίσω από firewall το οποίο εμποδίζει οποιονδήποτε από έξω να ανοίξει σύνδεση με αυτόν, o crawler δεν είναι σε θέση να ανακαλύψει την τοπολογία μεταξύ τέτοιων κόμβων. Παρόλα αυτά τέτοιοι κόμβοι μπορεί ακόμη να φαίνονται στον τελικό γράφο, μίας και είναι συνδεδεμένοι με κόμβους εκτός του firewall. Για τον λόγο αυτό, ο γράφος που ανακαλύπτει ο crawler μπορεί να θεωρηθεί υπογράφος του πραγματικού δικτύου Gnutella.

Επίσης, αν και ο χρόνος τoν οποίο τρέχει ο crawler είναι μικρός (μερικά λεπτά) λόγω της δυναμικής φύσης του δικτύου Gnutella (εκατοντάδες χρήστες το λεπτό)  ο γράφος που ανακαλύπτεται δεν είναι ακριβές στιγμιότυπο του πραγματικού δικτύου.

            Παρόλα αυτά, τα αποτελέσματα που παίρνουμε είναι πολύ κοντά σε ένα στιγμιότυπο από στατιστικής πλευράς: όλες οι ιδιότητες του δικτύου, μέγεθος, διάμετρος και μέσος όρος συνδετικότητας των κόμβων διατηρείται.

 

2.    Περιγραφή υλοποίησης του crawler

2.1. Γλώσσα υλοποίησης

 

            Η γλώσσα υλοποίησης του crawler είναι η Java και συγκεκριμένα η έκδοση 1.4. Προτιμήθηκε κυρίως λόγω του γεγονότος ότι διευκολύνει πολύ το networking και τον χειρισμό των threads.

Επίσης, ως συνέπεια του γεγονότος ότι η Java τρέχει παντού, στην κατανεμημένη έκδοση του crawler μπορούν να συμμετέχουν ετερογενή δίκτυα.

2.2. Μη κατανεμημένη έκδοση του crawler

 

Η μη κατανεμημένη έκδοση του έχει το πρόβλημα ότι είναι αρκετά αργή και έτσι είναι πιθανόν το δίκτυο που θα ανακαλύψει να απέχει αρκετά από το πραγματικό δίκτυο Gnutella. Για τον λόγο αυτό αναπτύχθηκε και η κατανεμημένη έκδοση του crawler η οποία είναι κατά πολύ γρηγορότερη.

Στην συνέχεια παραθέτω το διάγραμμα κλάσεων της μη κατανεμημένης έκδοσης του crawler.

Σχήμα 2  Διάγραμμα κλάσεων της μη κατανεμημένης έκδοσης του crawler

            Παρατήρηση

 

Στο παραπάνω διάγραμμα και σε αυτά που θα ακολουθήσουν, τα κουτάκια είναι οι κλάσεις, τα βέλη με την διακεκομμένη γραμμή σημαίνουν extends ενώ τα βέλη με την συνεχή γραμμή υποδηλώνουν ότι για παράδειγμα η κλάση GnuNetExplorer δημιουργεί στιγμιότυπο της κλάσης ClientThread. Επιπλέον οι κλάσεις από πακέτα της Java διαφέρουν αφού έχουν πλάγιες διακεκομμένες γραμμές.

 

 

2.2.1.   Σχολιασμός σημαντικών σημείων της υλοποίησης

 

            Ένα πρόβλημα που καθυστέρησε αρκετά την υλοποίηση του crawler είναι το εξής. Ενώ ο crawler έστελνε σωστά ένα μήνυμα PING με TTL 2 ο μόνος κόμβος που απαντούσε με PONG ήταν πολλές φορές ο πρώτος που το λάμβανε και που ουσιαστικά είχε ήδη ανακαλυφθεί. Για παράδειγμα στο σχήμα 1 θα συνέβαινε το εξής. Ο Χ θα έστελνε ένα PING στον Α και ο μόνος που θα απαντούσε με PONG θα ήταν ο Α ενώ θα έπρεπε να απαντήσει επίσης ο D και ο E. Είναι πολύ πιθανόν αυτό να συνέβαινε λόγω του γεγονότος ότι ο Α ήταν πολύ φορτωμένος και δεν μπορούσε να προωθήσει το PING ή οι D και Ε ήταν πολύ φορτωμένοι και δεν μπορούσαν να απαντήσουν. Μια ακόμη εξήγηση έχει να κάνει με την έννοια των τοπικών δικτύων και συγκεκριμένα με το γεγονός ότι υπάρχει εάν σύνολο IP διευθύνσεων το οποίο χρησιμοποιείται μόνο για τοπικά  δίκτυα (βλέπε κεφάλαιο 3 παράγραφο3) για λόγους οικονομίας διευθύνσεων (υπολογιστές σε διαφορετικά τοπικά δίκτυα μπορούν να έχουν την ίδια IP με την προϋπόθεση ότι δεν συνδέονται απευθείας στο διαδίκτυο). Αναλυτικότερα, οι περισσότεροι από τους κόμβους αυτούς δεν έχουν απευθείας πρόσβαση στο διαδίκτυο οπότε και συνδέονται μέσω ενός Gnutella client που τρέχουν με έναν κόμβο που έχει σύνδεση στο διαδίκτυο, έστω Χ. Όταν αργότερα ο crawler θα ρωτήσει τον Χ «ποίοι είναι οι γείτονες σου;» αυτός θα απαντήσει και αυτούς που είναι στο τοπικό δίκτυο. Όταν στην συνέχεια ο crawler θα προσπαθήσει να συνδεθεί στους κόμβους αυτούς θα αποτύχει μιας και αυτοί δεν έχουν απευθείας πρόσβαση στο διαδίκτυο. Το πρόβλημα αυτό ήταν αρκετά σοβαρό γιατί δεν επέτρεπε τον crawler να «αναπτυχθεί» στο δίκτυο και τελικά «κολλούσε».

            Το πρόβλημα είχε δύο πιθανές λύσεις, οι οποίες και αναλύονται.

 

Ø      Μία λύση είναι στην αρχή να στέλνονται PING με TTL μεγαλύτερο του 2 π.χ 3 δίνοντας έτσι την δυνατότητα στον crawler να αναπτυχθεί. Όταν πλέον είμαστε σίγουροι ότι αναπτύχθηκε αρκετά τότε επαναφέρουμε το TTL στην τιμή 2. Τα μειονεκτήματα της μεθόδου αυτής είναι

o       πώς ορίζεται το «αρκετά». Αρκετές δεκάδες ανακαλυπτόμενων κόμβων ή αρκετά δευτερόλεπτα. Και αν είναι κόμβοι τότε πόσοι είναι αυτοί;

o       η μέθοδος αυτή λόγω του γεγονότος ότι στέλνει αρχικά PING με TTL 3 δεν ανακαλύπτει την πραγματική τοπολογία του δικτύου.

o       αν είμαστε άτυχοι και η μέθοδος αυτή μπορεί να «κολλήσει» αν και τις περισσότερες φορές δουλεύει καλά.

Για τους λόγους αυτούς δεν χρησιμοποιήθηκε αυτή η λύση αλλά η επόμενη.

 

Ø      Η δεύτερη λύση είναι η εξής. Πριν τερματίσει ένα ClientThread (το thread που είναι υπεύθυνο για την σύνδεση) ελέγχει τον αριθμό των threads που τρέχουν. Αν αυτά είναι λιγότερα από ένα κάτω όριο τότε επιλέγει έναν από τους κόμβους που έχει ήδη ανακαλύψει και ξαναστέλνει ένα PING σε αυτόν. Με τον τρόπο αυτό υπάρχουν πάντοτε threads που τρέχουν και ανακαλύπτουν κόμβους. Κάποιος μπορεί να σκεφτεί ότι αυτό είναι περιττό και ότι θα ανακαλύπτονται πολλές φορές οι ίδιοι κόμβοι. Εν μέρει αυτό είναι αλήθεια αλλά δεν πρέπει να ξεχνάει κανείς το γεγονός ότι πολλοί κόμβοι δεν απαντούν στα PING που δέχονται λόγω προσωρινού φόρτου. Με την μέθοδο αυτή δίνονται και άλλες ευκαιρίες σε αυτούς τους κόμβους. Επιπλέον, η μέθοδος αυτή κατασκευάζει τον σωστό γράφο μίας και οι κόμβοι που θα ανακαλυφθούν περισσότερες από μία φορές δεν ξαναπροστείθενται στο δίκτυο.

 

Συνεχίζοντας, αξίζει να αναφερθεί το γεγονός ότι κάθε σύνδεση που ανοίγεται από τον crawler έχει ένα timeout. Όταν περάσει αυτός ο χρόνος τότε το thread σκοτώνεται. Με τον τρόπο αυτό εξασφαλίζεται ότι δεν υπάρχει σπατάλη threads τα οποία για κάποιο λόγο δεν τερματίζουν. Συγκεκριμένα, υπάρχει ένα thread το οποίο σε τακτά χρονικά διαστήματα «ξυπνάει» και ελέγχει όλα τα threads που τρέχουν για να δει αν υπάρχουν κάποια για τα οποία έχει περάσει το timeout. Αν βρει τέτοια τότε τα σκοτώνει.

Επιπρόσθετα, λόγω του γεγονότος ότι ένα μηχάνημα έχει πεπερασμένους πόρους πριν η κλάση Connection δημιουργήσει ένα ClientThread ελέγχει αν υπάρχει αρκετή ελεύθερη μνήμη και αν ο αριθμός των threads που τρέχουν αυτή την στιγμή στο μηχάνημα δεν έχει υπερβεί τον μέγιστο δυνατό. Αν όλα τα παραπάνω είναι εντάξει τότε το thread δημιουργείτε διαφορετικά το τρέχον thread περιμένει μέχρι να συντρέξουν οι παραπάνω προϋποθέσεις.

 

2.3. Κατανεμημένη έκδοση του crawler

 

            Όπως αναφέρθηκε παραπάνω, για να γίνει δυνατή η περαιτέρω μείωση του χρόνου που τρέχει ο crawler, αναπτύχθηκε μια client/server στρατηγική. Πιο συγκεκριμένα, υπάρχει ένας client o οποίος είναι υπεύθυνος για την διανομή της αρχικής λίστας στους servers καθώς και για την συλλογή των αποτελεσμάτων. Οι servers, δοσμένης της αρχικής λίστας ανακαλύπτουν το δίκτυο Gnutella και δίνουν τα αποτελέσματα στον client o οποίος τα αποθηκεύει (η μεταφορά των δεδομένων από τους servers στον client γίνετε συνεχώς για να αποφευχθεί ο κίνδυνος απώλειας των δεδομένων λόγω κάποιας βλάβης κάποιου από τους servers). Με τον τρόπο αυτό επιτεύχθηκε μεγάλη αύξηση στον αριθμό των ανακαλυπτόμενων κόμβων ανά λεπτό από τους 300  στους 2000 περίπου (μαζί με τους τρόπους βελτιστοποίησης που περιγράφηκαν παραπάνω).

Στην συνέχεια παραθέτω το διάγραμμα κλάσεων της κατανεμημένης έκδοσης του crawler. (Ένα για τον client και ένα για τον server)

Σχήμα 3  Διάγραμμα κλάσεων του client

2.3.1.   Παρατηρήσεις για τον client

 

Ίσως φανεί παράξενο το γεγονός ότι ο client χρησιμοποιεί την κλάση  GnuNetExplorer (η μη κατανεμημένη έκδοση του crawler). Αυτό γίνεται για τον εξής λόγο. Σε περίπτωση που η αρχική μας λίστα με τους κόμβους που είναι ήδη συνδεδεμένοι στο δίκτυο είναι μικρή, ο client ψάχνει για λίγο μέχρι να βρει αρκετούς κόμβους στο δίκτυο και κατόπιν τους κατανέμει στους servers. Με τον τρόπο αυτό αυξάνεται η απόδοση των servers.

Σχήμα 4 Διάγραμμα κλάσεων του server

2.3.2.   Παρατηρήσεις για τον server

 

            Ίσως φανεί περίεργο το γεγονός ότι ο server δεν έχει κανένα Writer, οπότε πως δίνει τα αποτελέσματα πίσω στον client; Την εργασία αυτή την αναλαμβάνει ο GnuNetExplorer o οποίος γράφει τα αποτελέσματα που συλλέγει τόσο σε αρχεία όσο και σε sockets.

 

 

 

 

 

 

 

 

Κεφάλαιο 3

 

Ανάλυση των αποτελεσμάτων

 

1.    Κατασκευή του γράφου

 

Ο γράφος που κατασκευάζεται είναι ένας ισχυρά συνδεδεμένος αμφίδρομος γράφος. Υπάρχουν δύο τρόποι αποθήκευσης ενός τέτοιου γράφου που παρουσιάζονται παρακάτω.

 

1.1.            Πίνακας γειτονίας (adjacency matrix). Εδώ χρησιμοποιείται ένας δισδιάστατος πίνακας NxN θέσεων όπου Ν το πλήθος των κόμβων. Για Ν = 10Κ που είναι ένα μικρό υποδίκτυο του δικτύου Gnutella έχουμε ότι απαιτούνται 10⁸ θέσεις μνήμης (100Μ θέσεις μνήμης). Αν υποθέσουμε ότι κάθε θέση μνήμης καταλαμβάνει περίπου 50 bytes έχουμε ότι απαιτούνται 500Mbytes μνήμης. Το μέγεθος αυτό είναι πολύ μεγάλο και αν το Ν γίνει ακόμα πιο μεγάλο Ν=100Κ τότε πλέον είναι σχεδόν αδύνατο να αποθηκεύσουμε ένα τέτοιο γράφο. Παρακάτω δίνεται ένα παράδειγμα.

 

Σχήμα 5 Πίνακας γειτονίας

 

1.2.            Λίστες γειτονίας (adjacency lists). Εδώ χρησιμοποιείται ένας μονοδιάστατος πίνακας που περιέχει μία θέση για κάθε κόμβο του γράφου. Κάθε στοιχείο του πίνακα, εκτός των άλλων πεδίων περιέχει και έναν δείκτη σε μία συνδεδεμένη αλυσίδα η οποία περιέχει σε τυχαία σειρά τους γειτονικούς κόμβους. Η μέθοδος αυτή για αραιούς γράφους (γράφους με αριθμό συνδέσεων πολύ μικρότερο του αριθμού των κόμβων) δίνει πολύ καλά αποτελέσματα. Συγκεκριμένα απαιτεί χώρο αποθήκευσης Ν+2Μ όπου Μ ο αριθμός των συνδέσεων. Παρατηρώντας ότι στο Gnutella ο αριθμός των συνδέσεων είναι περίπου διπλάσιος του αριθμού των κόμβων (Μ = 2Ν) έχουμε για το παραπάνω παράδειγμα ότι απαιτούνται περίπου 250Κbytes. . Παρακάτω δίνεται ένα παράδειγμα.

Σχήμα 6  Λίστα γειτονίας

Φυσικά, στην συγκεκριμένη εργασία χρησιμοποιήθηκε ο δεύτερος τρόπος γιατί ο γράφος του δικτύου Gnutella είναι ένας αραιός γράφος.

2.    Σκοπός της μελέτης

 

Σκοπός μεγάλου μέρους των πειραμάτων που θα περιγραφούν παρακάτω είχαν σαν απώτερο σκοπό να λύσουν το παρακάτω πρόβλημα. Ποιος είναι ο «καλύτερος» τρόπος να οργανώσεις τους γράφους του Gnutella έτσι ώστε ο χρήστης να βρίσκει αυτό που ψάχνει με το μικρότερο δυνατό «κόστος». Να έχει πολλούς γείτονες και να στέλνει μηνύματα με μικρό TTL ή να έχει λίγους γείτονες και να στέλνει μηνύματα με μεγάλο TTL. Το κόστος ορίζεται ως ο αριθμός των μηνυμάτων που θα δημιουργηθούν στο δίκτυο.

 

3.    Κόμβοι που απορρίφθηκαν κατά την ανάλυση

 

Όπως αναφέρεται και στο RFC 1918 [VIII] υπάρχουν ορισμένες IP διευθύνσεις οι οποίες είναι δεσμευμένες από την IANA(Internet Assigned Numbers Authority) και οι οποίες χρησιμοποιούνται για ιδιωτικά δίκτυα. Οι διευθύνσεις αυτές είναι οι εξής

·        10.*.*.*[i]

·        172.16.*.*

·        192.168.*.*

Οι διευθύνσεις αυτές φιλτραρίστηκαν κατά την διάρκεια της δημιουργίας του γράφου και απορρίφθηκαν για ευνόητους λόγους. Το σημαντικό στην όλη υπόθεση είναι το γεγονός ότι η απόρριψη των κόμβων αυτών έχει σημαντική επίπτωση στην ανάλυση των πειραμάτων. Με άλλα λόγια τα αποτελέσματα με και χωρίς τους κόμβους αυτούς διαφέρουν πολύ.

Το κυριότερο είναι ότι αν δεν φιλτράρουμε τους κόμβους βγάζουμε σε πολλά σημεία τα ίδια αποτελέσματα με άλλους ερευνητές που έκαναν παρόμοια πειράματα [1],[2],[5]. Τι συνέβη λοιπόν; Οι ερευνητές αυτοί δεν είχαν υπόψη τους το RFC 1918 ; Τα αποτελέσματα που δημοσίευσαν είναι λανθασμένα ; Δεν γνωρίζουμε.

Τέλος, απορρίφθηκαν και οι εξής διευθύνσεις.

·        127.0.0.1

Χρησιμοποιείται για να υποδηλώσει την IP διεύθυνση του τοπικού μηχανήματος.

·        0.0.0.0

·        255.*.*.*, *.255.*.*, *.*.255.*, *.*.*.255

Χρησιμοποιούνται για broadcast.

 

4.    Προγράμματα που κατασκευάσθηκαν

 

4.1.            Κατασκευάσθηκε ένα πρόγραμμα το οποίο διαβάζει δύο αρχεία τα οποία περιέχουν τους κόμβους που ανακαλύφθηκαν και τις συνδέσεις μεταξύ τους και κατασκευάζει έναν ισχυρά συνδεδεμένο αμφίδρομο γράφο.

 

4.2.            Κατασκευάσθηκε ένα πρόγραμμα το οποίο παίρνει τον γράφο και μετράει τον αριθμό των κόμβων που είναι προσπελάσιμοι και των αριθμό των μηνυμάτων που δημιουργούνται αν σταλεί ένα μήνυμα με συγκεκριμένο TTL από έναν συγκεκριμένο κόμβο του δικτύου. Το πρόγραμμα αυτό χρησιμοποιεί εσωτερικά τον σειριακό προσομοιωτή που θα περιγραφεί στην συνέχεια.

 

4.3.            Επίσης, κατασκευάσθηκε ένα πρόγραμμα το οποίο παίρνει τον γράφο και έναν αριθμό που παριστάνει το μέγιστο TTL και κάνει τα εξής. Αρχίζει και αφαιρεί γείτονες από έναν συγκεκριμένο κόμβο της επιλογής μας και κάνει την μέτρηση 4.2 για κάθε αριθμό γειτόνων. Στο σημείο αυτό προκύπτει το εξής πρόβλημα. Ποιους γείτονες αφαιρούμε πρώτους. Υπάρχουν οι εξής επιλογές.

q       Αφαιρούμε γείτονες τυχαία.

q       Αφαιρούμε γείτονες που οι ίδιοι έχουν αρκετούς γείτονες.

q       Αρχίζουμε να αφαιρούμε γείτονες πετώντας πρώτα αυτούς που έχουν ένα γείτονα , μετά αυτούς που έχουν δύο γείτονες και συνεχίζουμε παρομοίως.

q       Μία παραλλαγή είναι να αφαιρούμε δύο-δύο τους κόμβους και να αφαιρούμε έναν γείτονα που δεν έχει ο ίδιος πολλούς γείτονες και έναν που έχει.

 

Όλες οι παραπάνω επιλογές έχουν εφαρμοσθεί αλλά τα αποτελέσματα των πειραμάτων που διεξήχθησαν ήταν παρόμοια. Για την δημιουργία των αποτελεσμάτων που θα παρουσιαστούν στην συνέχεια επιλέχθηκε η τρίτη επιλογή.

 

4.4.            Επίσης, κατασκευάσθηκε ένα πρόγραμμα το οποίο καλεί πολλές φορές το παραπάνω πρόγραμμα 4.3 αλλά με TTL που κυμαίνεται μεταξύ 1 και μίας μέγιστης τιμής. Επειδή το πρόγραμμα αυτό ήθελε περίπου μία ώρα για έναν γράφο δεκαέξι χιλιάδων θέσεων και TTL = 15 αποφασίστηκε να γίνει κατανεμημένο μιας και είναι το πιο συχνά χρησιμοποιούμενο πρόγραμμα. Πιο συγκεκριμένα, λόγω του γεγονότος ότι τα αποτελέσματα για διαφορετικά TTL είναι ανεξάρτητα μεταξύ τους αυτό που κάνει το κατανεμημένο πρόγραμμα είναι να κατανείμει τα TTL στα διάφορα μηχανήματα, να πάρει τα αποτελέσματα  και να τα αποθηκεύσει σε ένα αρχείο. Η επιτάχυνση που έχουμε είναι ίση με εάν το TTL διαιρείται ακριβώς από των αριθμό των μηχανημάτων, διαφορετικά  .

 

4.5.            Παράλληλα, κατασκευάσθηκε ένα πρόγραμμα που παίρνει τον αρχικό γράφο (δίκτυο) και τον αναδιατάσσει ως εξής. Διαλέγει ένα υποσύνολο των γειτόνων ενός συγκεκριμένου κόμβου (έστω Χ) και διαγράφει τις συνδέσεις μεταξύ του κόμβου Χ και των επιλεγμένων γειτόνων. Κατόπιν, επιλέγει έναν αριθμό από κόμβους που βρίσκονται «μακριά» και τους κάνει γείτονες του Χ.

 

4.6.            Επίσης, κατασκευάσθηκε ένα πρόγραμμα που «κλαδεύει» τον γράφο. Το πρόγραμμα αυτό παίρνει τον αρχικό γράφο και τον αριθμό των γειτόνων που θέλουμε να έχει ένας κόμβος (ο αριθμός αυτός πρέπει να είναι μικρότερος των γειτόνων που ήδη έχει) και πετάει γείτονες μέχρι οι γείτονες που μένουν να είναι ίσοι με τον αριθμό που ζητήθηκε. 

 

4.7.            Επιπλέον, κατασκευάσθηκε ένα πρόγραμμα το οποίο παίρνει τα αποτελέσματα του 4.4 (των αριθμό των κόμβων που βρίσκουμε και τον αριθμό των μηνυμάτων που χρειάστηκαν) και κατασκευάζει τις ισοϋψείς καμπύλες. Επίσης, βρίσκει τον καλύτερο συνδυασμό TTL και αριθμού γειτόνων για κάθε ισοϋψή καμπύλη έτσι ώστε να έχουμε τον μικρότερο δυνατό «φόρτο» στο δίκτυο. Υπάρχουν οι εξής επιλογές στην επιλογή των ισοϋψών καμπύλων.

 

q       Παίρνουμε τις ισοϋψείς σε προκαθορισμένα διαστήματα π.χ κάθε χίλιους κόμβους.

q       Παίρνουμε τον αρχικό γράφο και υπολογίζουμε πόσους κόμβους μπορούμε να προσπελάσουμε με TTL = 1,..,X και μετά παίρνουμε τις ισοϋψείς σε αυτές τις τιμές.

 

      Με τον τρόπο αυτό ουσιαστικά βλέπουμε για συγκεκριμένο αριθμό κόμβων ποιες εναλλακτικές επιλογές έχουμε. Έτσι μπορούμε να δούμε ποια επιλογή είναι «καλύτερη». Λέγοντας καλύτερη εννοούμε αυτή που δημιουργεί τον μικρότερο αριθμό μηνυμάτων στο δίκτυο. 

 

Επίσης, κατασκευάσθηκαν και άλλα προγράμματα τα οποία λόγω του γεγονότος ότι  είτε δεν είναι  πολύ σημαντικά είτε είναι δύσκολο να εξηγηθεί η λειτουργία τους δεν αναφέρθηκαν.

5.    Γραφικές παραστάσεις που κατασκευάσθηκαν

 

Για να γίνουν πιο κατανοητά τα αποτελέσματα των πειραμάτων κατασκευάσθηκε ένας μεγάλος αριθμός από γραφικές παραστάσεις ένα μέρος των οποίων θα παρουσιαστεί στην συνέχεια. Όλες οι γραφικές παραστάσεις κατασκευάσθηκαν με το πρόγραμμα gnuplot. Για όλες τις γραφικές παραστάσεις κατασκευάστηκαν scripts που τις παράγουν.

Παρακάτω, για να γίνουν πιο κατανοητές οι γραφικές παραστάσεις θα παρουσιαστούν μαζί με τις ερωτήσεις που προσπαθήσαμε να απαντήσουμε.

 

q       Πόσους κόμβους προσπελαύνει ένας κόμβος σαν συνάρτηση του TTL;

q       Πόσα μηνύματα στέλνει ένας κόμβος σαν συνάρτηση του TTL;

 

 

Όπως παρατηρούμε αυτή η γραφική παράσταση έχει ένα «γόνατο», ένα σημείο δηλαδή πέρα από το οποίο αύξηση του TTL δεν συνεπάγεται σημαντική αύξηση του αριθμού των προσπελάσιμων κόμβων όπως επίσης και των μηνυμάτων που στέλνονται.

Το «γόνατο» στα μηνύματα παρουσιάζεται γιατί οι κόμβοι του Gnutella πριν προωθήσουν ένα μήνυμα ελέγχουν πρώτα αν το έχουν ξαναδεί (μέσω του UID – Unique Identifier) και αν ναι δεν το προωθούν. Έτσι, όσο μεγάλο και αν είναι το TTL του μηνύματος θα φτάσει σε μια κατάσταση το δίκτυο που οι κόμβοι θα σταματήσουν να το προωθούν.

Το «γόνατο» στους ανακαλυπτόμενους κόμβους εμφανίζεται γιατί από ένα σημείο - TTL και μετά  έχουν ανακαλυφθεί σχεδόν όλοι οι κόμβοι.

 

q       Πόσους κόμβους προσπελαύνει ένας κόμβος σαν συνάρτηση του αριθμού των γειτόνων για συγκεκριμένο TTL (έστω 10);

q       Πόσα μηνύματα στέλνει ένας κόμβος σαν συνάρτηση του αριθμού των γειτόνων για συγκεκριμένο TTL (έστω 10);

 

Η παραπάνω γραφική παράσταση δημιουργήθηκε με τον εξής τρόπο. Παίρνουμε τον γράφο που ανακάλυψε ο crawler και βρίσκουμε έναν κόμβο με πολλούς γείτονες (65 στο παραπάνω παράδειγμα). Μετά αρχίζουμε να κόβουμε γείτονες από τον κόμβο αυτό  όπως περιγράφεται στο πρόγραμμα 4.3 παραπάνω.

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

 

q       Πόσα μηνύματα στέλνει ένας κόμβος για την προσπέλαση ενός συγκεκριμένου αριθμού κόμβων με δεδομένο TTL και δεδομένο αριθμό γειτόνων;

Όπως παρατηρούμε από αυτή την γραφική παράσταση ο αριθμός των κόμβων που βρίσκουμε αυξάνει γραμμικά με τον αριθμό των μηνυμάτων που στέλνουμε. Συμπεραίνουμε λοιπόν, ότι δεν μπορούμε να αυξήσουμε τον αριθμό των ανακαλυπτόμενων κόμβων χωρίς να αυξήσουμε τον αριθμό των μηνυμάτων που στέλνονται. Η συμπεριφορά αυτή είναι το κυριότερο μειονέκτημα του αλγορίθμου δρομολόγησης (flooding) που χρησιμοποιεί το Gnutella. 

 

q       Ποια είναι η σχέση μεταξύ αριθμού γειτόνων, TTL και κόμβων που προσπελαύνονται;

 

      Όπως παρατηρούμε όταν αυξάνεται είτε ο αριθμός των γειτόνων είτε το TTL αυξάνεται και ο αριθμός των κόμβων που προσπελαύνονται.

 

q       Ποια είναι η σχέση μεταξύ αριθμού γειτόνων, TTL και μηνυμάτων που στέλνονται;

Όπως παρατηρούμε όταν αυξάνεται είτε ο αριθμός των γειτόνων είτε το TTL αυξάνεται και ο αριθμός των μηνυμάτων που στέλνονται.

 

q       Πόσα μηνύματα στέλνει ένας κόμβος για την προσπέλαση ενός συγκεκριμένου αριθμού κόμβων;

 

 

Η γραφική αυτή παράσταση αρχίζει να μας εμφανίζει τα δυσάρεστα αποτελέσματα. Αν θέλαμε να ξεχωρίζει ένας από τους τρόπους που αναφέραμε παραπάνω θα έπρεπε η παραπάνω γραφική να μην ήταν ευθεία .

 

q       Ποια είναι η κατανομή των βαθμών των κόμβων του δικτύου Gnutella (βαθμός ενός κόμβου είναι ο αριθμός των συνδέσεων που έχει ένας κόμβος ή ισοδύναμα ο αριθμός των γειτόνων);

Από την γραφική αυτή παράσταση επιβεβαιώνεται και η άποψη πολλών ερευνητών ότι το δίκτυο Gnutella είναι ένα power-law δίκτυο. Σε ένα power-law δίκτυο ο αριθμός των κόμβων με L συνδέσεις είναι ανάλογος με L^-k, όπου K είναι μία σταθερά που εξαρτάται από το δίκτυο. Όπως παρατηρούμε, σε ένα power-law δίκτυο οι περισσότεροι κόμβοι έχουν λίγες συνδέσεις με ελάχιστους κόμβους να έχουν περισσότερες από 10 συνδέσεις.

 

q       Πως συμφέρει να οργανώσουμε τους γράφους του δικτύου Gnutella , κατά βάθος ή κατά πλάτος;

Όπως ίσως έχετε διαπιστώσει και μόνοι σας, οι δύο τρόποι οργάνωσης του δικτύου Gnutella είναι σχεδόν ισοδύναμοι. Ο τρόπος οργάνωσης του γράφου κατά πλάτος έχει μια μικρή υπεροχή η οποία δεν φαίνεται στις παραπάνω γραφικές παραστάσεις αλλά μπορεί κανείς να το διαπιστώσει αν δει τα νούμερα που βγαίνουν κατά την προσομοίωση.

 

 

Κεφάλαιο 4

 

Προσομοιωτής του Gnutella

 

Προφανώς, είναι αδύνατο να μοντελοποιήσουμε όλες τις παραμέτρους ενός P2P συστήματος. Η προσομοίωση που έγινε δεν είχε ως στόχο να αποκαλύψει μικρές ποσοτικές διαφορές μεταξύ διαφορετικών αλγορίθμων, αλλά προσπάθησε να φανερώσει ποιοτικές διαφορές. Για απλότητα, ο γράφος του δικτύου Gnutella δεν αλλάζει κατά την διάρκεια της προσομοίωσης. Επίσης, χρησιμοποιήθηκε ομοιόμορφη κατανομή των ερωτήσεων, δηλαδή όλα τα αρχεία είναι το ίδιο δημοφιλή. Τέλος, χρησιμοποιήθηκε ομοιόμορφη κατανομή επανάληψης των αρχείων (replication), δηλαδή όλα τα αρχεία υπάρχουν στον ίδιο αριθμό κόμβων. 

1.    Στόχος του προσομοιωτή

 

Ο προσομοιωτής αυτός κατασκευάστηκε κυρίως για την μελέτη διαφόρων αλγορίθμων που μπορούν να χρησιμοποιηθούν για το ψάξιμο αρχείων στο  Gnutella.

3.    Υλοποίηση

 

Στο σημείο αυτό αξίζει να αναφερθεί ότι υπάρχουν δύο υλοποιήσεις του προσομοιωτή. Την μία την ονομάζουμε «σειριακή» γιατί δεν χρησιμοποιούνται καθόλου threads και την άλλη «παράλληλη» γιατί χρησιμοποιούνται threads. O παράλληλος προσομοιωτής είναι πιο ρεαλιστικός αλλά έχει μεγάλες απαιτήσεις σε πόρους και είναι σαφώς πιο αργός από τον σειριακό. Αντίθετα, ο σειριακός έχει πολύ μικρές απαιτήσεις σε πόρους και είναι πολύ γρήγορος οπότε και χρησιμοποιείται και κατά την ανάλυση των αποτελεσμάτων που περιγράψαμε παραπάνω.

Η γλώσσα υλοποίησης του προσομοιωτή είναι η Java και συγκεκριμένα η έκδοση 1.4. Πρέπει επίσης να επισημανθεί το γεγονός ότι έγινε μεγάλη προσπάθεια ώστε να είναι όσο το δυνατόν πιο εύκολη προσθήκη και άλλων αλγορίθμων δρομολόγησης. Συγκεκριμένα, για να προστεθεί ένας ακόμη αλγόριθμος δρομολόγησης απαιτείται η προσθήκη μίας μόνο συνάρτησης και η προσθήκη ακόμη μίας περίπτωσης σε ένα switch.

Παράλληλα, όσο αφορά τις παραμέτρους που δέχεται ο προσομοιωτής, αυτές καθορίζονται σε ένα αρχείο. Εάν κάποιος επιθυμεί να αλλάξει κάποια παράμετρο δεν έχει παρά να αλλάξει την παράμετρο στο αρχείο.

 

2.    Παράμετροι που δέχεται ο προσομοιωτής

 

Ο προσομοιωτής που κατασκευάστηκε δέχεται τις εξής παραμέτρους. (Κάποιες από τις παραμέτρους που θα περιγραφούν παρακάτω έχουν νόημα μόνο για την σειριακή ή παράλληλη έκδοση του προσομοιωτή).

 

1.      Τυχαίο ή υπαρκτό δίκτυο.

a.       Τυχαίο δίκτυο.

Κατασκευάζεται ένας τυχαίος ισχυρά συνδεδεμένος αμφίδρομος γράφος. Στον γράφο αυτό ο χρήστης μπορεί να καθορίσει των αριθμό των κόμβων και τον μέσο αριθμό των γειτόνων.

b.      Υπαρκτό δίκτυο.

Ο προσομοιωτής διαβάζει ένα αρχείο που περιέχει έναν γράφο που ανακαλύφθηκε από τον crawler και κατασκευάζει τον γράφο της προσομοίωσης.

 

2.      Αριθμός των διαφορετικών αρχείων.

Ο αριθμός των διαφορετικών αρχείων που θα υπάρχουν στο δίκτυο.

 

3.      Επανάληψη των αρχείων.

Με τον τρόπο αυτό ορίζουμε πόσες φορές θα επαναλαμβάνεται ένα αρχείο στο δίκτυο ή ισοδύναμα πόσοι υπολογιστές θα έχουν το ίδιο αρχείο. Η επανάληψη των αρχείων γίνεται τυχαία, δηλαδή δεν έχουν όλοι οι κόμβοι τον ίδιο αριθμό αρχείων. Υπάρχουν κόμβοι με πολλά αρχεία και κόμβοι που δεν έχουν ούτε ένα αρχείο (φαινόμενο free riding).

 

4.      Αριθμός των ερωτήσεων.

Με την παράμετρο αυτή καθορίζουμε τον αριθμό των ερωτήσεων που θα γίνουν συνολικά στο δίκτυο. Οι ερωτήσεις γίνονται είτε από τυχαίους κόμβους του δικτύου είτε από έναν συγκεκριμένο κόμβο. Επίσης, στον παράλληλο προσομοιωτή υπάρχει η επιλογή οι ερωτήσεις να γίνονται παράλληλα ή σειριακά. Η πρώτη επιλογή επιτρέπει δύο ή περισσότερους κόμβους να κάνουν παράλληλα ερωτήσεις. Στην δεύτερη επιλογή γίνεται ερώτηση από έναν κόμβο του δικτύου κάθε φορά. Φυσικά, η πρώτη επιλογή είναι πιο κοντά στον τρόπο με τον οποίο δουλεύει το πραγματικό δίκτυο Gnutella αλλά ο τρόπος υλοποίησης της έχει πολλές απαιτήσεις σε πόρους, γεγονός που απαγορεύει την χρήση της για προσομοίωση μεγάλων δικτύων (δίκτυα με περισσότερους από 500 κόμβους).

 

5.      Μέγιστη καθυστέρηση στην επεξεργασία των ερωτήσεων

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

 

6.      Χρόνος αδρανοποίησης.

Εάν, όπως εξηγήθηκε προηγουμένως έχουμε παράλληλες ερωτήσεις τότε η παράμετρος αυτή είναι ο μέγιστος χρόνος που θα περιμένει ένας κόμβος πριν κάνει μία ερώτηση. Στην περίπτωση που έχουμε σειριακές ερωτήσεις είναι ο χρόνος μεταξύ δύο διαδοχικών ερωτήσεων.

 

7.      Time to live (TTL)

Η παράμετρος αυτή είναι το πεδίο TTL που μπαίνει στις ερωτήσεις και συμβολίζει τον μέγιστο αριθμό των κόμβων που θα προωθήσουν το μήνυμα.

 

8.      Αλγόριθμος δρομολόγησης.

Ο χρήστης μπορεί να διαλέξει μεταξύ τεσσάρων αλγορίθμων δρομολόγησης.

a.       Όταν ένας κόμβος δέχεται ένα μήνυμα το προωθεί σε όλους τους γείτονες του (flooding). Αυτός είναι ο αλγόριθμος που χρησιμοποιείται σήμερα στο δίκτυο Gnutella.

b.      Όταν ένας κόμβος δέχεται ένα μήνυμα το προωθεί σε έναν τυχαία επιλεγμένο γείτονα (random neighbour). Εδώ δεν γίνεται έλεγχος για το αν ο κόμβος έχει ξαναδεί το μήνυμα και είναι πιθανόν ένας κόμβος να στείλει το μήνυμα στον κόμβο από τον οποίο τον έλαβε αν δεν έχει άλλο γείτονα.

c.       Όταν ένας κόμβος δέχεται ένα μήνυμα το προωθεί στους γείτονες του με μία πιθανότητα που μειώνεται όσο αυξάνεται το TTL του μηνύματος (Ο αλγόριθμος flooding μπορεί να θεωρηθεί ως μια ειδική περίπτωση αυτού του αλγορίθμου με ). Οι συναρτήσεις πιθανότητας που δοκιμάστηκαν είναι

q       .

 

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

 

q       .

Με αυτή την συνάρτηση πιθανότητας έχουμε λίγο καλύτερα ποσοστά επιτυχίας από την προηγούμενη μιας και η συνάρτηση μειώνεται πιο ομαλά με αποτέλεσμα να στέλνονται περισσότερα μηνύματα.

 

q       .

Όπως φαίνεται από την παραπάνω γραφική παράσταση η συνάρτηση μειώνεται πολύ αργά. Έτσι στέλνονται αρκετά μηνύματα για την ανακάλυψη των ζητούμενων αρχείων με συνέπεια η μέθοδος αυτή να έχει μεγάλα ποσοστά επιτυχίας διατηρώντας σε «λογικά» πλαίσια τον αριθμό των μηνυμάτων.

 

q      

Με αυτή την συνάρτηση πιθανότητας έχουμε λίγο καλύτερα ποσοστά επιτυχίας από την προηγούμενη συνάρτηση πιθανότητας με ελάχιστα περισσότερα μηνύματα.

 

d.      Όταν ένας κόμβος δέχεται ένα μήνυμα το προωθεί στους γείτονες του με μία πιθανότητα που αυξάνεται όσο αυξάνεται το TTL του μηνύματος (Ο αλγόριθμος flooding μπορεί να θεωρηθεί ως μια ειδική περίπτωση και αυτού του αλγορίθμου με ). Οι συναρτήσεις πιθανότητας που δοκιμάστηκαν είναι

q       .

Με αυτή την συνάρτηση πιθανότητας έχουμε αρκετά υψηλά ποσοστά επιτυχίας με ελάχιστα μηνύματα.

 

e.       Random walks [4]. Είναι μια τεχνική, η οποία προωθεί ένα μήνυμα σε έναν τυχαία επιλεγμένο γείτονα. Αυτό το μήνυμα ονομάζεται “walker”. Για να μειωθεί η καθυστέρηση εύρεσης του ζητούμενου αρχείου μπορούν να αυξηθούν οι “walkers”. Δηλαδή, αντί να στέλνει ένα μήνυμα κάθε κόμβος, στέλνει k μηνύματα και κάθε μήνυμα ακολουθεί το δικό του τυχαίο μονοπάτι. Εδώ δεν γίνεται έλεγχος για το αν ο κόμβος έχει ξαναδεί το μήνυμα και είναι πιθανόν ένας κόμβος να στείλει το μήνυμα στον κόμβο από τον οποίο τον έλαβε αν δεν έχει άλλο γείτονα. Οι μηχανισμοί τερματισμού που χρησιμοποιούνται είναι οι εξής

q         TTL. Η χρήση του είναι παρόμοια με το flooding.

q         Checking. O “walker” περιοδικά επικοινωνεί με τον αρχικό κόμβο πριν προχωρήσει στον επόμενο κόμβο και αποφασίζει αν θα συνεχίσει ή όχι. Για να μην δημιουργείται υπερβολική κίνηση στο δίκτυο λόγω αυτής της επικοινωνίας συνήθως ένας “walker” επικοινωνεί με τον αρχικό κόμβο κάθε n hops (συνήθως n = 4). Έτσι λοιπόν εάν ένας “walker” βρει αυτό που ψάχνει τότε θα σταματήσουν και οι άλλοι “walkers” να ψάχνουν το πολύ μετά από n hops. Και αυτή η μέθοδος χρησιμοποιεί TTL αλλά το TTL είναι πολύ μεγάλο και χρησιμοποιείται για να εμποδίσει τους βρόγχους (loops).

 

9.      Αποστολέας

Ο χρήστης μπορεί να διαλέξει ποιος κόμβος θέλει να στέλνει τις ερωτήσεις. Αν δεν καθοριστεί με μια έγκυρη τιμή αυτό το πεδίο τότε ο προσομοιωτής επιλέγει τυχαία τους κόμβους που θα κάνουν τις ερωτήσεις. Η επιλογή αυτή γίνεται με κάποια κριτήρια, κυρίως με τον αριθμό των γειτόνων του κόμβου που θα επιλεγεί καθώς επίσης και με τον αριθμό των γειτόνων των γειτόνων του επιλεγμένου κόμβου. Έτσι λοιπόν στις περισσότερες προσομοιώσεις απαιτήθηκε ο επιλεγμένος κόμβος να έχει τουλάχιστον τέσσερις γείτονες και οι γείτονες του να έχουν τουλάχιστον τρεις γείτονες με τέσσερις γείτονες.

 

10.  Αριθμός Walker

Η παράμετρος αυτή έχει νόημα μόνο αν επιλεγεί ως αλγόριθμος δρομολόγησης ο Random Walks και καθορίζει τον αριθμό των walkers.

 

4.    Μεθοδολογία προσομοίωσης

 

Κατά την αξιολόγηση των αλγορίθμων εκτελέσαμε τις προσομοιώσεις εκτελώντας έναν μεγάλο αριθμό από ερωτήσεις για να μειωθεί όσο το δυνατόν περισσότερο το σφάλμα στις μετρήσεις. Οι ερωτήσεις γίνονταν από κόμβους τυχαία επιλεγμένους από το σύνολο των κόμβων. Μετά για κάθε ερώτηση προσομοιώσαμε την διαδικασία αναζήτησης χρησιμοποιώντας την επιλεγμένη μέθοδο αναζήτησης. Εάν βρισκόταν ένα αρχείο τότε πήγαινε και αντιγραφόταν στον κόμβο που το ζήτησε αυξάνοντας έτσι το replication του αντικειμένου(αρχείου).

 

5.    Αποτελέσματα που βγάζει ο προσομοιωτής

 

Ο προσομοιωτής επικεντρώνεται σε θέματα αποδοτικότητας του αλγορίθμου και μόνο και έτσι θα χρησιμοποιηθούν τα ακόλουθα κριτήρια. Αυτά τα κριτήρια, αν και είναι απλά, αντικατοπτρίζουν της θεμελιώδεις ιδιότητες των αλγορίθμων.

 

Ø      Διάσταση χρήστη

 

ü      Πιθανότητα εύρεσης του αναζητούμενου αρχείου πριν τερματίσει η  αναζήτηση. Διαφορετικοί αλγόριθμοι μπορεί να έχουν διαφορετικά κριτήρια τερματισμού και οδηγούν σε διαφορετικές πιθανότητες επιτυχίας. Οι αλγόριθμοι που υλοποιήθηκαν ήδη έχουν ως κριτήριο τερματισμού το TTL εκτός από τον Random Walks το κριτήριο τερματισμού του οποίου εξηγήθηκε παραπάνω.

ü      Καθυστέρηση στην εύρεση ενός αντικειμένου όπως μετράται σε αριθμό hops. Εδώ δεν μοντελοποιείται η πραγματική καθυστέρηση δικτύου, απλά μετράται ο μέσος όρος των hops που θα κάνει μία επιτυχημένη αναζήτηση.

 

Ø      Διάσταση φόρτου

 

ü      Μέσος όρος μηνυμάτων ανά κόμβο. Έχει να κάνει με τον μέσο αριθμό μηνυμάτων που πρέπει να επεξεργαστεί ένας κόμβος στο δίκτυο. Το κίνητρο γι αυτό το κριτήριο είναι το γεγονός ότι στα P2P συστήματα, η πιο μεγάλη επιβάρυνση είναι ο φόρτος επεξεργασίας που το δίκτυο επιβάλλει στους κόμβους του.

ü      Μέσος όρος κόμβων που δέχτηκαν έστω και ένα μήνυμα κατά την διάρκεια μιας ερώτησης (ισοδύναμα αριθμός των μοναδικών κόμβων που δέχθηκαν επίσκεψη).

ü      Μέσος όρος των μηνυμάτων που πήγαν δύο φορές στον ίδιο κόμβο (duplicated messages).

 

6.    Αποτελέσματα

 

Στο σημείο αυτό παρατίθενται ορισμένα αποτελέσματα πειραμάτων που διεξήχθησαν.

 

a)      Το πρώτο πείραμα έχει τις εξής παραμέτρους

 

Nodes	14632
Files	1000
Correlation	150
Queries	50

 

και τα εξής αποτελέσματα για τους αλγορίθμους flooding, random neighbour και random walks με 32 walkers.

 

 

Routing[ii]	TTL	Probability of Success	Messages
1	12	1.0	19321
2	12	0.12	12
2	100	0.28	100
5(checking) 32 walkers	100	1.0	217

 

b)      Το δεύτερο πείραμα έχει τις παραπάνω παραμέτρους με την διαφορά ότι θα ελέγχουν οι αλγόριθμοι 4 και 5 με διαφορετικές συναρτήσεις πιθανότητας και TTL = 12.

 

Routing[iii]	Probability Function	Probability of Success	Messages
3		0.5	117
3		1.0	387
3	, A = 10	1.0	1170
3	, A = 10	1.0	2146
4	, A = 20, B = 30	1.0	4171

Όπως παρατηρούμε λοιπόν οι αλγόριθμοι με αυξανόμενες και μειούμενες πιθανότητες έχουν πολύ καλά ποσοστά επιτυχίας με μικρό αριθμό μηνυμάτων. Όμως τα παραπάνω πειράματα έγιναν με μεγάλο replication. Πιο συγκεκριμένα, στα παραπάνω πειράματα βάλαμε τα αντίγραφα ενός αρχείου να βρίσκονται στο 1% των κόμβων του δικτύου. Το δίκτυο μας είχε δεκαπέντε χιλιάδες κόμβους ή αλλιώς ένα αρχείο βρισκόταν σε περίπου 150 κόμβους.

Για να δούμε τις επιδόσεις των παραπάνω αλγορίθμων και με μικρό replication επαναλάβαμε τα παραπάνω πειράματα με διαφορετικές τιμές για το replication και για διακόσιες ερωτήσεις. Τα ποσοστά επιτυχίας που είχαν οι παραπάνω αλγόριθμοι καθώς και ο αριθμός των μηνυμάτων που χρειάστηκαν φαίνεται στις παρακάτω γραφικές παραστάσεις. Στο σημείο αυτό πρέπει να αναφερθεί ότι για τον αλγόριθμο με τις μειούμενες πιθανότητες χρησιμοποιήθηκε η συνάρτηση πιθανότητας , A = 10 ενώ για τον αλγόριθμο με τις αυξανόμενες πιθανότητες χρησιμοποιήθηκε η συνάρτηση πιθανότητας , A = 20, B = 30.  Επίσης, όλες οι ερωτήσεις έγιναν από τον ίδιο κόμβο ο οποίος παρεπιμπτόντος είχε οκτώ γείτονες.

Όπως λοιπόν παρατηρεί κανείς, ο αλγόριθμος Random Walks είναι πολύ χειρότερος από τους πιθανοκρατικούς αλγορίθμους που προτείνονται σε αυτή την εργασία όταν το replication είναι πολύ μικρό, γεγονός που πιστεύουμε ότι ισχύει και στο πραγματικό δίκτυο Gnutella.

 

Όπως είναι φανερό οι πιθανοκρατικοί αλγόριθμοι που προτείνονται παράγουν τον ίδιο αριθμό μηνυμάτων ανεξαρτήτως replication μιας και ο μηχανισμός τερματισμού που χρησιμοποιείται βασίζεται αποκλειστικά στο TTL. Εδώ βλέπουμε την υπεροχή του αλγορίθμου Decreased Probability έναντι του Increased Probability. Παρατηρούμε επίσης την μικρή διαφορά που έχει ο Decreased Probability από τον  Random Walks.

Συνεχίζοντας, για δούμε πότε ακριβώς ο αλγόριθμος Random Walks αρχίζει να έχει ποσοστό επιτυχίας 100% επαναλαμβάνουμε το παραπάνω πείραμα με διαφορετικά replication και παίρνουμε την παρακάτω γραφική παράσταση.

Βλέπουμε λοιπόν ότι ο Random Walks αρχίζει να έχει ποσοστό επιτυχίας 100% όταν το replication γίνει μεγαλύτερο ή ίσο του εκατόν τριάντα ενώ ο Decreased Probability όταν το replication γίνει μεγαλύτερο του είκοσι.

Συνεχίζοντας, αν σε όλα τα παραπάνω προσθέσουμε και το γεγονός ότι ο αλγόριθμος Random Walks χρειάζεται πολύ περισσότερο χρόνο για να πετύχει τα παραπάνω ποσοστά επιτυχίας συμπεραίνουμε ότι ο αλγόριθμος Decreased Probability είναι ένας αρκετά ανταγωνιστικός αλγόριθμος.

Τέλος, πρέπει να επισημανθεί το γεγονός ότι τόσο ο παράλληλος όσο και ο σειριακός προσομοιωτής βγάζουν πολύ περισσότερα στατιστικά στοιχεία από αυτά που παρουσιάστηκαν εδώ αλλά δεν τα παραθέτουμε λόγω περιορισμένου χώρου.

Κεφάλαιο 5

 

Οπτικοποίηση του δικτύου που ανακαλύφθηκε

 

Για την οπτικοποίηση τους χρησιμοποιήθηκαν δύο εργαλεία της caida, το Otter και το Plankton. Τα εργαλεία αυτά όπως είναι φυσικό παίρνουν ως είσοδο ένα αρχείο που έχει συγκεκριμένο format. Για να δημιουργηθούν αυτά τα αρχεία κατασκευάσθηκαν δύο προγράμματα, τα ODF.java και PlanktonDF.java.

 

1.    Ενδεικτικά αποτελέσματα

Στο σημείο αυτό παρουσιάζονται μερικά ενδεικτικά αποτελέσματα των γράφων που ανακαλύφθηκαν από τον crawler. To δίκτυο που φαίνεται παρακάτω περιέχει 413 κόμβους.

Εικόνα 1 Otter

Εικόνα 2 Plankton

 

 

 

 

 

 

 

 

 

 

Κεφάλαιο 6

 

Συμπεράσματα

 

 

Η ανοιχτή αρχιτεκτονική και η ικανότητα κλιμάκωσης (scale) του δικτύου Gnutella το έχουν κάνει μία ενδιαφέρουσα αρχιτεκτονική για μελέτη. Οι κοινωνικές συνθήκες οι οποίες βοήθησαν στην ανάπτυξη και επιτυχία του δικτύου Gnutella μπορεί να αλλάξουν και το δίκτυο μπορεί να εξαφανιστεί. Παρόλα αυτά, οι μετρήσεις που έγιναν και οι τεχνικές ανάλυσης μπορούν να χρησιμοποιηθούν και για άλλα P2P συστήματα για να βοηθήσουν στην κατανόηση των tradeoffs της σχεδίασης ενός P2P συστήματος.

Από την ανάλυση των αποτελεσμάτων βγήκε το συμπέρασμα ότι οι δύο τρόποι οργάνωσης του γράφου του δικτύου Gnutella (κατά πλάτος ή κατά βάθος) είναι σχεδόν ισοδύναμοι. Μέτρο σύγκρισης ήταν ο αριθμός μηνυμάτων που χρειάζονται για να ανακαλυφθεί ένας αριθμός κόμβων.

            Από τις προσομοιώσεις που έγιναν, βγήκε το συμπέρασμα ότι  ένας καλός αλγόριθμος δρομολόγησης για μη δομημένα P2P συστήματα όπως το Gnutella πρέπει να έχει τουλάχιστον τις εξής τρείς ιδιότητες.

q       Δυναμικό (ή προσαρμοζόμενο) τερματισμό. Μηχανισμοί βασιζόμενοι στο TTL δεν δουλεύουν.

q       Πρέπει να περιορίζει όσο το δυνατόν περισσότερο τον διπλασιασμό των μηνυμάτων. Δηλαδή, ένα μήνυμα δεν πρέπει να περνάει περισσότερες από μία φορές από τον ίδιο κόμβο. Ιδανικά, κάθε μήνυμα πρέπει να επισκέπτεται έναν κόμβο μόνο μία φορά.

q       Κάθε επιπλέον βήμα στην αναζήτηση πρέπει να μην αυξάνει κατά πολύ τον αριθμό των κόμβων που έχουν ψαχθεί.

 

Φυσικά, ένας αλγόριθμος δρομολόγησης πρέπει να μειώσει την καθυστέρηση όσο το δυνατόν περισσότερο.

 

Κεφάλαιο 7

 

Παράρτημα

1.    Βιβλιογραφία.

 

[1]               Matei Ripeau, Ian Foster.Mapping the Gnutella Network: Macroscopic Properties of Large-Scale Peer-to-Peer Systems. 1st  International Workshop on Peer-to-Peer Systems (IPTPS’02), Cambridge, Massachusetts, March 2002.

[2]               Matei Ripeau. Peer-to-Peer Architecture Case Study: Gnutella Network. Internet2 workshop: Collaborative Computing in Higher Education: Peer-to-Peer and Beyond, January 30-31, 2002, Tempe, Arizona.

[3]               Qin Lv, Sylvia Ratnasamy, Scott Shenker. Can Heterogeneity Make Gnutella Scalable? In First International Workshop on Peer-to-Peer Systems (IPTPS) 2002.

[4]               Qin Lv, Pei Cao, Edith Cohen, Kai Li, Scott Shenker. Search and Replication in Unstructured Peer-to-Peer Networks. In 16th ACM International Conference on Supercomputing, New York, USA. June 2002.

[5]               Kelsey Anderson. Analysis of the Traffic on the Gnutella Network,University of Chicago, http://www.cs.ucsd.edu/classes/wi01/cse222/projects/reports/p2p-2.pdf.

 

2.    Αναφορές στο διαδίκτυο.

 

[I]                 http://www.openp2p.com/

General description of P2P systems.

[II]              http://www.gnutellanews.com/information/what_is_gnutella.shtml

A short descritpion of Gnutella Protocol.

[III]            http://rfc-gnutella.sourceforge.net/

The RFC-Gnutella project is working on defining a standard for the Gnutella protocol.

[IV]           http://www.gnutelliums.com/

Gnutelliums is a comprehensive directory of Gnutella clients for Windows, Linux/Unix, Java, and Macintosh.

[V]              http://www.ececs.uc.edu/~mjovanov/Research/gnutella.html

Gnutcrawl Home Page.

[VI]           http://www.caida.org/tools/visualization/otter/

Otter visualization tool Home Page.

[VII]         http://www.caida.org/tools/visualization/plankton/

Plankton visualization tool Home Page.

[VIII]      http://www.ietf.org/rfc/rfc1918.txt

Address Allocation for Private Internets.