next up previous
Next: Μοντέλα προσομοίωσης Up: Οικονομία Διαχείρισης Δεδομένων Previous: Περιγραφή Προβλήματος

Οικονομικός αλγόριθμος αντιγραφής δεδομένων και δρομολόγησης δοσοληψιών DRR

Οπως μια ανθρώπινη οικονομία, το υπολογιστικό σύστημα διαθέτει ένα σύνολο διακριτών αγαθών, τα οποία πρέπει να διατεθούν σε ένα σύνολο καταναλωτών. Τα αγαθά του υπολογιστικού συστήματος είναι τα δεδομένα (data), ο υπολογιστικός χρόνος (CPU time) και το εύρος επικοινωνίας (communication bandwidth). Οι κόμβοι του συστήματος είναι οι πωλητές της οικονομίας ενώ οι κλάσεις δοσοληψιών θεωρούνται αγοραστές. Στόχος των κλάσεων δοσοληψιών είναι η εξυπηρέτησή τους με το μικρότερο δυνατό κόστος ενώ στόχος των κόμβων είναι η μεγιστοποίηση των κερδών τους. Οι κόμβοι κερδίζουν πουλώντας δεδομένα και υπολογιστικό χρόνο σε δοσοληψίες που εκτελούνται τοπικά. Χρησιμοποιούν τα κέρδη που αποκομίζουν, για την ενοικίαση ``μη τοπικών'' δεδομένων όταν θεωρούν οτι ανάλογη επένδυση, μακροπρόθεσμα, θα αυξήσει το εισόδημα τους. Η ενοικίαση ενός αντιγράφου γίνεται μετά από συμφωνία με τον ιδιοκτήτη (owner) του δεδομένου ή τον κάτοχο ενός άλλου αντιγράφου. Η τιμή ενοικίασης πρέπει να βρίσκει σύμφωνα και τα δύο μέλη του ``συμβολαίου'' και ανανεώνεται με την πάροδο του χρόνου ώστε να ανταποκρίνεται στην αξία του αγαθού. Οι κόμβοι προσφέρουν για ενοικίαση κάποιο από τα τοπικά τους δεδομένα ή αντίγραφο δεδομένου που έχουν ενοικιάσει, όταν η τιμή ενοικίασης εγγυάται αύξηση των κερδών τους. Σε κάθε δοσοληψία της κλάσης Cj που εισέρχεται στο σύστημα διατίθεται κεφάλαιο Bj. Η δοσοληψία εκμεταλλεύεται το χρηματικό αυτό ποσό για την αγορά δεδομένων, υπολογιστικού χρόνου και εύρους επικοινωνίας.Στόχος της δοσοληψίας είναι η ελαχιστοποίηση του κόστους αγοράς αγαθών, οπότε επιλέγει να εξυπηρετηθεί από τον κόμβο που καλύπτει τις απαιτήσεις της και προσφέρει την μικρότερη δυνατή τιμή. Η τιμή κάθε κόμβου αποτελεί συνάρτηση του φόρτου του κόμβου, της ζήτησης των δεδομένων που προσφέρει και του κόστους μεταβίβασης της δρομολογούμενης δοσοληψίας. Οι κλάσεις δοσοληψιών έχουν τις ίδιες προτιμήσεις σε αγαθά (utility function) αλλά μπορεί να διαθέτουν διαφορετικά κεφάλαια. Το κεφάλαιο κάθε κλάσης καθορίζεται από τον διαχειριστή του συστήματος και αντικατοπτρίζει τις υπολογιστικές απαιτήσεις κάθε κλάσης. Η δοσοληψία αποτυγχάνει να εξυπηρετηθεί όταν δεν διαθέτει ισχυρό κεφάλαιο (όλοι οι κόμβοι ζητούν περισσότερα από όσα μπορεί να πληρώσει). Το κεφάλαιο που διαθέτει κάθε κλάση αποτελεί δείκτη της προτεραιότητας των δοσοληψιών. Οσο μεγαλύτερο είναι το κεφάλαιο μιας κλάσης τόσα περισσότερα αγαθά ή ποσοστό ενός αγαθού δύναται να αγοράσει η κλάση αυτή και τόσο μικρότερη είναι η πιθανότητα απόρριψης δοσοληψιών της κλάσης. Η οικονομική πολιτική που ακολουθείται για την διαμόρφωση των τιμών είναι κοινή για όλους τους κόμβους του συστήματος. Κανένας κόμβος δεν υιοθετεί δόλια συμπεριφορά, δεν χρεώνει δηλαδή τα αγαθά του σε τιμές δυσανάλογες της αξίας τους.

Περιγραφή οικονομικού αλγορίθμου DRR

Θεωρώ σύστημα Ν επεξεργαστών P1, P2,.., PN όπου ri η υπολογιστική δύναμη του επεξεργαστή Pi, όπου i ε [1,N]. Η βάση δεδομένων αποτελείται από Μ σχέσεις O1, O2,.., OM. S(Oi) είναι το πλήθος σελίδων της σχέσης Oi ενώ Pij(Oi) είναι ο χρόνος προσπέλασης της σχέσης Oi στο χρονικό διάστημα tj στον κόμβο Pi. eij είναι ο σύνδεσμος επικοινωνίας μεταξύ των επεξεργαστών Pi, Pj. dij είναι η καθυστέρηση του συνδέσμου επικοινωνίας eij η οποία δεν μεταβάλλεται στο χρόνο.

Εχουν οριστεί Λ κλάσεις δοσοληψιών CA, CB,..,CΛ. μi είναι ο αναμενόμενος χρόνος εξυπηρέτησης δοσοληψίας της κλάσης Ci σε ιδανικό επεξεργαστή. Η συχνότητα άφιξης δοσοληψιών της κλάσης Ci το χρονικό διάστημα tj είναι λij και είναι ίδια για όλους τους κόμβους (πηγές φόρτου) του συστήματος. Οταν μια δοσοληψία της κλάσης Cj, όπου j ε [1..Λ] εισέρχεται στο σύστημα κατά το χρονικό διάστημα tα, διαθέτει κεφάλαιο Bj το οποίο εκμεταλλεύεται για να αγοράσει, με το μικρότερο εφικτό κόστος, δεδομένα, υπολογιστικό χρόνο και εύρος επικοινωνίας. Η δοσοληψία θα επιλέξει να δρομολογηθεί στον κόμβο που μπορεί να καλύψει τις απαιτήσεις της και προσφέρει την μικρότερη τιμή για τις υπηρεσίες του. Η συνάρτηση χρησιμότητας (utility function) αντανακλά τις προτιμήσεις της κλάσης Cj και καθορίζει τις αποφάσεις δρομολόγησης:

Utility function = min{J * (WTαi + STi + dki + ΣPαi(Op))} =
= min{J * (WTαi + μj / ri + dki + ΣPαi(Op))} , for all i ε [1,N]

όπου WTαi είναι ο χρόνος αναμονής (waiting time) της δρομολογούμενης δοσοληψίας στον κόμβο Pi το χρονικό διάστημα tα. Ο χρόνος αναμονής ορίζεται ως το άθροισμα των χρόνων εξυπηρέτησης των δοσοληψιών που έχουν ήδη δρομολογηθεί στον επεξεργαστή και περιμένουν να εκτελεστούν. Η παράμετρος STi = μj / ri δηλώνει τον αναμενόμενο χρόνο εξυπηρέτησης (service time) της δοσοληψίας της κλάσης Cj στον κόμβο Pi. Η παράμετρος dki είναι ο χρόνος μεταβίβασης της δοσοληψίας από την πηγή φόρτου Pk στον κόμβο Pi. Το κόστος αυτό είναι μηδενικό αν η δοσοληψία εκτελεστεί τοπικά. Το άθροισμα ΣPαi(Op) δηλώνει το συνολικό κόστος των σχέσεων που επιθυμεί να προσπελάσει η δρομολογούμενη δοσοληψία. Pαi(Op) είναι ο χρόνος που απαιτείται για προσπέλαση της σχέσης Op στο χρονικό διάστημα tα στον κόμβο Pi. Ο πολλαπλασιαστής J έχει τιμή 1 δραχμή ανά δεπτερόλεπτο.

Αν η δοσοληψία δεν διαθέτει αρκετά μεγάλο κεφάλαιο ώστε να μπορεί να πληρώσει κάποιον από τους κόμβους, απορρίπτεται από το σύστημα.

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

Τα δεδομένα αυτά θα ζητηθούν για ενοικίαση από τους ιδιοκτήτες κόμβους (κόμβοι στους οποίους έχει ανατεθεί το δεδομένο από τον διαχειριστή του συστήματος) ή από κόμβους που κατέχουν αντίγραφο, το οποίο ενοικίασαν σε προηγούμενο χρονικό διάστημα. Ο κόμβος που επιθυμεί να ενοικιάσει αντίγραφο μιας σχέσης Op, θα συνάψει ``συμβόλαιο'' με τον κάτοχο της σχέσεις που ζητεί μικρότερο ενοίκιο. Η επιλογή αυτή γίνεται για να μειωθεί το κόστος ενοικίασης.

Εστω Pj ο κόμβος που επιθυμεί να ενοικιάσει αντίγραφο της σχέσης Op το χρονικό διάστημα tα και Pi ο πιο ``φθηνός'' κάτοχος της σχέσης το χρονικό αυτό διάστημα. Το ``ενοίκιο'' (LeasePrice) που ζητάει ο κόμβος Pi δίνεται από τον ακόλουθο τύπο:

LeasePriceαi = Pαi(Op) * Service(α-1)i(Op) + S(Op) * dij

όπου Pαi(Op) η τιμή της σχέσης Op στον κόμβο Pi το χρονικό διάστημα tα, Service(α-1)i(Op) ο αριθμός δοσοληψιών που εκτελέστηκαν στον κόμβο Pi το προηγούμενο χρονικό διάστημα tα-1 και ζητούσαν την σχέση Op και S(Op) * dij το κόστος μεταβίβασης των σελίδων της σχέσης Op από τον κόμβο Pi στον υποψήφιο ενοικιαστή Pj. Το ενοίκιο ισούται στην χειρότερη περίπτωση με το ποσό που θα χάσει ο κόμβος Pi αν αριθμός δοσοληψιών ίσος με τον αριθμό των δοσοληψιών που εκτελέστηκαν τοπικά το χρονικό διάστημα tα-1 και ζητούσαν την σχέση Op δρομολογηθούν στο χρονικό διάστημα tα στον κόμβο Pj (συν το κόστος μεταβίβασης της σχέσης).

Το προηγούμενο χρονικό διάστημα ο κόμβος Pj δέχτηκε πλήθος δοσοληψιών ίσο με Demand(α-1)j(Op) οι οποίες επιθυμούσαν να προσπελάσουν τη σχέση Op. Οι δοσοληψίες αυτές δεν μπόρεσαν να εκτελεστούν τοπικά (λόγω απουσίας της σχέσης Op από τον κόμβο Pj) και έτσι δρομολογήθηκαν σε άλλους κόμβους. Ο κόμβος ζημειώθηκε κατά:

Pαi(Op) * Demand(α-1)j(Op) + dij* Demand(α-1)j(Op) δρχ.

όπου Pαi(Op) * Demand(α-1)j(Op) δρχ. το ποσό που δαπάνησαν Demand(α-1)j(Op) δοσοληψίες για την αγορά του αγαθού Op σε κάποιον άλλο κόμβο (κάτοχο της σχέσης Op) και dij* Demand(α-1)j(Op) δρχ. το ποσό που δαπάνησαν οι δοσοληψίες για την μεταβίβασή τους από τον κόμβο Pj σε κάποιον άλλο κόμβο. Θεωρούμε οτι οι δοσοληψίες δρομολογήθηκαν στον κόμβο Pi. Αν οι δοσοληψίες εκτελούνταν τοπικά, ανάλογο ποσό χρημάτων θα μπορούσε να είναι η αμοιβή του κόμβου Pj. Αρα ο κόμβος Pj δύναται να πληρώσει ενοίκιο (OfferPrice) ίσο με:

OfferPriceαi = Pαi(Op) * Demand(α-1)j(Op) + dij* Demand(α-1)j(Op) δρχ.

Αν LeasePriceαi < OfferPriceαi συνάπτεται συμβόλαιο μεταξύ των κόμβων Pi, Pj και ο κόμβος Pj αποκτά αντίγραφο της σχέσης Op για το χρονικό διάστημα tα. Ο κόμβος διαθέτει τη σχέση Op σε τιμή ίση με :

Pαj(Op) = Pαi(Op) * (ri /rj)

Παρατηρούμε οτι αν ο κόμβος Pj έχει υπολογιστική δύναμη μεγαλύτερη από τον κόμβο Pi (rj > ri) θα προσφέρει τη σχέση Op σε χαμηλότερη τιμή. Αν ο κόμβος Pj έχει μεγαλύτερη υπολογιστική δύναμη και εγγυάται μικρότερη τιμή για την σχέση Op από τον κόμβο Pj, αναμένεται να προσελκύσει μεγαλύτερο αριθμό δοσοληψιών που ζητούν να προσπελάσουν την σχέση Op. Ετσι θα επιτύχει να αποκομίσει ποσό χρημάτων μεγαλύτερου του ενοικίου που κατέβαλε στον κόμβο Pi. Αν αντίθετα έχει μικρότερη υπολογιστική δύναμη και ακριβότερη τιμή για την σχέση Op από τον κόμβο Pi θα προσελκύσει δοσοληψίες και θα αποσβέσει το ενοίκιο μόνο αν ο φόρτος του κόμβου Pi γίνει αρκετά μεγάλος ώστε να καλύψει τα προηγούμενα πλεονεκτήματά του (χαμηλή τιμή, μεγάλη υπολογιστική δύναμη).

Αν ο κόμβος Pj επιθυμεί να διατηρήσει αντίγραφο της σχέσης Op μετά το τέλος του χρονικού διαστήματος tα πρέπει να διαπραγματευτεί ξανά με τον κόμβο Pi (κόμβο από τον οποίο έχει ενοικιάσει το αντίγραφο) και να πληρώσει μέρος του ενοικίου για το χρονικό διάστημα tα+1.

Ο κόμβος Pi για το χρονικό διάστημα tα+1 απαιτεί ποσό ίσο με:

RenewalPrice(α+1)i = P(α+1)i(Op) * Serviceαi(Op)

Το ποσό αυτό ισούται με το ποσό χρημάτων που θα χάσει στην χειρότερη περίπτωση ο κόμβος Pi αν σύνολο δοσοληψιών ίσο με τον αριθμό των δοσοληψιών που ζήτησαν την σχέση Op το προηγούμενο χρονικό διάστημα και εξυπηρετήθηκαν στον κόμβο Pi δρομολογηθούν στο διάστημα tα+1 στον κόμβο Pj. Ο κόμβος Pj δύναται να πληρώσει, για την ανανέωση του ``ενοικιοστασίου'', ποσό ίσο με:

ReofferPrice(α+1)j = P(α+1)j(Op) * Serviceαj(Op)

Το ποσό αυτό ισούται με το ποσό των χρημάτων που θα αποκομίσει ο κόμβος Pj το χρονικό διάστημα tα+1 αν εξυπηρετήσει σύνολο δοσοληψιών ίσο με τον αριθμό των δοσοληψιών που ζήτησαν την σχέση Op και εκτελέστηκαν τοπικά το προηγούμενο χρονικό διάστημα. Αν

RenewalPrice(α+1)i <= ReofferPrice(α+1)j

τότε το συμβόλαιο των κόμβων Pi, Pj ανανεώνεται για το χρονικό διάστημα tα+1 και ο κόμβος Pj διατηρεί το αντίγραφο της σχέσης Op. Ανάλογη διαδικασία ανανέωσης του συμβολαίου πρέπει να ακολουθηθεί και στα επόμενα χρονικά διαστήματα tα+2, tα+3 κ.ο.κ.

Αν

RenewalPrice(α+1)i > ReofferPrice(α+1)j

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

Στον αλγόριθμο DRR ο χρόνος αναμονής της δοσοληψίας j στον επεξεργαστή Pi αποτελεί παράμετρο στη λήψη της απόφασης δρομολόγησης. Η παράμετρος αυτή αντικατοπτρίζει την ζήτηση που παρατηρείται στον κόμβο Pi και αποτελεί μέτρο του υπολογιστικού φόρτου που έχει ήδη δρομολογηθεί στον κόμβο αυτό. Οι τιμές στις οποίες οι κόμβοι προσφέρουν τα αγαθά τους διαμορφώνονται με τρόπο ώστε να αντικατοπτρίζουν τις δυνατότητες προσφοράς των κόμβων. Για παράδειγμα η τιμή των αντιγράφων σχέσεων ενός κόμβου αποτελεί συνάρτηση της υπολογιστικής δύναμης του κόμβου αυτού. Επίσης στην κοστολόγηση των δοσοληψιών του, ένας κόμβος λαμβάνει υπόψη του τόσο το χρόνο αναμονής όσο και το χρόνο εξυπηρέτησης της δρομολογούμενης δοσοληψίας. Oι χρόνοι αυτοί αποτελούν συνάρτηση του πλήθους των δοσοληψιών που έχουν δρομολογηθεί στον κόμβο, της υπολογιστικής δύναμης του κόμβου, καθώς και των δεδομένων που διαθέτει (εκτελεί δοσοληψίες που προσπελαύνουν δεδομένα των οποίων έχει αντίγραφα). Η απόφαση για την ενοικίαση ενός αντιγράφου βασίζεται κι αυτή στη ζήτηση και στην προσφορά που παρατηρείται στους κόμβους. Ο κάτοχος πρέπει να έχει συσσωρευμένο σχετικά μεγάλο αριθμό δοσοληψιών που ζητούν τη σχέση ώστε να μη ζημιωθεί από τον ανταγωνισμό που θα προκαλέσει ένα καινούριο αντίγραφο. Ανάλογα ο πιθανός ενοικιαστής πρέπει να έχει μεταβιβάσει σε άλλους κόμβους αρκετές δοσοληψίες που επιθυμούν μια συγκεκριμένη σχέση, πριν αποφασίσει οτι είναι προσοδοφόρο να ενοικιάσει αντίγραφο της σχέσης αυτής.

Οι κόμβοι είναι αξιόπιστοι και εγγυώνται οτι δεν πρόκειται να απαιτήσουν από κάποια δοσοληψία ποσό μεγαλύτερο της τιμής που ζήτησαν για την εκτέλεσή της πριν ληφθεί η απόφαση δρομολόγησης (price guarantees). Το σύστημα οδηγείται σε κατάσταση ισορροπίας όπου η ζήτηση σε ένα επεξεργαστή ισούται με την προσφορά.



Anastasiadi Anastasia
Tue Nov 12 16:13:18 EET 1996