Σημειώσεις:Προβλήματα:Δρομολόγηση
Από DistrSys
Πολύ συχνά, οι διάφορες διεργασίες που υπάρχουν σε ένα δίκτυο θέλουν να επικοινωνήσουν με άλλες μέσω ανταλλαγής μηνυμάτων. Παρατηρούμε όμως, ότι στην γενική περίπτωση ένας κόμβος δεν συνδέεται άμεσα με όλους τους άλλους κόμβους, που σημαίνει ότι κάθε κόμβος μπορεί να επικοινωνήσει άμεσα μόνο με ένα υποσύνολο κόμβων (τους γείτονές του). Η δρομολόγηση σε ένα γενικό δίκτυο απαιτεί την επιλογή μιας ή περισσότερων γειτονικών διεργασιών για την προώθηση μηνυμάτων προς κάποια τελική διεργασία-προορισμό. Η δρομολόγηση γενικά μπορεί να είναι είτε κεντρικοποιημένη ή κατανεμημένη. Εμάς μας ενδιαφέρει η δεύτερη περίπτωση όπου η ευθύνη του υπολογισμού των μονοπατιών μοιράζεται ανάμεσα στους κόμβους, οι οποίοι ανταλλάσουν πληροφορίες μεταξύ τους όταν είναι απαραίτητο. Επίσης, η δρομολόγηση διακρίνεται σε στατική και δυναμική. Στην στατική δρομολόγηση (static routing), το μονοπάτι που χρησιμοποιείται για ένα ζεύγος κόμβων πηγής-προορισμού, παραμένει σταθερό. Στην δυναμική ή προσαρμοζόμενη (adaptive routing) το μονοπάτι μπορεί να αλλάζει ανάλογα με την συμφόρηση που υπάρχει στα κανάλια. Εδώ τίθενται διάφορα ζητήματα όπως ποιο είναι το καλύτερο δηλαδή το βέλτιστο μονοπάτι; Τι γίνεται όταν κάποιος κόμβος έχει υψηλό φόρτο εργασίας και καθυστερεί την προώθηση μηνυμάτων ή όταν κάποιο κανάλι αντιμετωπίζει (προσωρινά) σφάλματα; Η εύρεση του βέλτιστου μονοπατιού εμπλέκει την αξιολόγηση όλων των μονοπατιών που ενώνουν δύο κόμβους σύμφωνα με μια πολιτική η οποία μπορεί να είναι:
- Ελάχιστες Μεταβάσεις (Minimum Hop), σύμφωνα με την πολιτική αυτή εξετάζουμε το μήκος του μονοπατιού, δηλαδή ο αριθμός των βημάτων, μεταβάσεων από κόμβο σε κόμβο.
- Συντομότερο Μονοπάτι (Shortest Path), στην περίπτωση αυτή αντιστοιχούμε σε κάθε ακμή e του γραφήματος ένα βάρος(μη αρνητικό) και επιλέγουμε το μονοπάτι με το μικρότερο κόστος.
- Ελάχιστη Καθυστέρηση (Minimum Delay), εδώ αντιστοιχούμε δυναμικά σε κάθε ακμή e του γραφήματος ένα βάρος το οποίο εξαρτάται από την κυκλοφορία μηνυμάτων στην ακμή αυτή, και πάλι επιλέγουμε το μονοπάτι με το μικρότερο κόστος.
Ανεξάρτητα με το είδος της δρομολόγησης υπάρχουν διάφορα κριτήρια για την απόδοσή της. Τα κριτήρια αυτά είναι:
- Ορθότητα (Correctness), πρέπει να εξασφαλίζεται έγκυρη υπόδειξη των μονοπατιών για την μεταφορά των μηνυμάτων στους τελικούς παραλήπτες.
- Πολυπλοκότητα (Complexity), οι διεργασίες πρέπει να ενημερώνονται με τον ελάχιστο χρόνο, χώρο και αριθμό μηνυμάτων.
- Αποδοτικότητα (Efficienty), ο αλγόριθμος δρομολόγησης πρέπει να χρησιμοποιεί μονοπάτια που δημιουργούν τις μικρότερες καθυστερήσεις και συσ-σωρεύσεις μηνυμάτων σε μέρη δικτύου.
- Βιωσιμότητα (Robustness), ο αλγόριθμος δρομολόγησης θα πρέπει να είναι σε θέση να αντιμετωπίσει τις αλλαγές στην τοπολογία, οι διερασίες να ενημε-ρώνονται καταλλήλως χωρίς να απαιτείται ο τερματισμός αυτών ή επανεκκίνησή τους.
- Προσαρμοστικότητα (Adaptiveness), ο αλγόριθμος δρομολόγησης θα πρέπει επίσης να αναπροσαρμόσει τις διαδρομές όταν τα κανάλια αποκτάνε μεγάλο φόρτο αποστολών.
- Δικαιοσύνη (Fairness), ο αλγόριθμος θα πρέπει να εξυπηρετεί όλους τους κόμβους στον ίδιο βαθμό.
Χαρακτηριστικά αυτόματου Δρομολόγησης
Ο αλγόριθμος δρομολόγησης με πίνακες απόστασης αναπτύχθηκε πρώτη φορά από τους Bellman(1957) και Ford-Fulkerson(1962).
Καταστάσεις:
- Κάθε κόμβος διατηρεί έναν πίνακα δρομολόγησης που δίνει την καλύτερη γνωστή απόσταση προς κάθε προορισμό, καθώς και το μονοπάτι που πρέπει να χρησιμοποιηθεί για να φτάσουμε εκεί.
Μεταβάσεις:
- Δημιουργία πινάκων: τα περιεχόμενα των πινάκων υπολογίζονται κατά την φάση αρχικοποίησης του δικτύου.
- Ενημέρωση πινάκων: τα περιεχόμενα των πινάκων ανανεώνονται μετά από κάποια αλλαγή στην τοπολογία του δικτύου. Οι πίνακες αυτοί ενημερώνονται μέσω ανταλλαγής πληροφοριών με τους γείτονες.
- Προώθηση μηνυμάτων: σύμφωνα με τα στοιχεία των πινάκων τα μηνύματα προωθούνται στους κατάλληλους κόμβους.
Παραπάνω αναφέραμε ότι υπάρχουν 3 πολιτικές για την εύρεση του βέλτιστου μονοπατιού οι ελάχιστες μεταβάσεις, το συντομότερο μονοπάτι και η ελάχιστη καθυστέρηση. Ας δούμε μέσω ποιων γνωστών αλγορίθμων πετυχαίνουμε την κάθε μία από αυτές.
Για να έχουμε ελάχιστες μεταβάσεις μπορούμε να κατασκευάσουμε για κάθε κόμβο u ένα επικαλυπτικό δέντρο Tu(G) με ρίζα την u, ενώ στους πίνακες δρομολόγησης, για κάθε κόμβο v διατηρούμε μια μεταβλητή γονέας v που αντιστοιχεί στον γονέα της u στο δέντρο Tv(G). Αν για την κατασκευή του επικαλυπτικού δέντρου χρησιμοποιήσουμε τον αλγόριθμο AsynchSpanningTree τότε έχουμε πολυπλοκότητα επικοινωνίας O(n • m) και χρονική πολυπλοκότητα O(δ • (l + d)), ενώ αν χρησιμοποιήσουμε τον AsynchBFS θα έχουμε πολυπλοκότητα επικοινωνίας O(n • m) και χρονική πολυπλοκότητα O(n • δ(l + d)). Αξίζει εδώ να παρατηρήσουμε ότι για τον αλγόριθμο SynchBFS που είχαμε αντίστοιχα στα σύγχρονα δίκτυα, η πολυπλοκότητα επικοινωνίας είναι O(n • m) και η χρονική πολυπλοκότητα είναι O(δ).
Για να βρούμε τα συντομότερα μονοπάτια χρειάζεται κάθε κόμβος u να υπολογίζει την απόσταση που έχει από κάθε άλλο κόμβο v του δικτύου, ενώ στους πίνακες δρομολόγησης, για κάθε κόμβο v διατηρούμε μια μεταβλητή γονέαςv που αντιστοιχεί στον γονέα της u στο δέντρο των συντομότερων μονοπατιών. Για τον σκοπό αυτό χρησιμοποιούμε τον αλγόριθμο AsynchBellmanFord, ο οποίος έχει πολυπλοκότητα επικοινωνίας O(nn • m) και χρονική πολυπλοκότητα O(nn+1 • (l+d)). Και πάλι αξίζει να θυμηθούμε τις αντίστοιχες πολυπλοκότητες για τον αλγόριθμο BellmanFord στο σύγχρονο δίκτυο. Η πολυπλοκότητα επικοινωνίας σε αυτήν την περίπτωση είναι O(n2 • m) και η χρονική πολυπλοκότητα είναι σημαντικά λιγότερο, μόλις O(n).
Τέλος, για να πετύχουμε την ελάχιστη καθυστέρηση πρέπει καταρχάς να βρούμε τα συντομότερα μονοπάτια. Και πάλι όπως και πριν κάθε κόμβος u υπολογίζει την απόσταση που έχει με κάθε άλλο κόμβο v του δικτύου, ενώ στους πίνακες δρομολόγησης, για κάθε κόμβο v διατηρούμε μια μεταβλητή γονέαςv που αντιστοιχεί στον γονέα της u στο δέντρο των συντομότερων μονοπατιών. Πρέπει επίσης να γίνεται ενημέρωση των πινάκων, το οποίο γίνεται εφικτό όταν κάθε κόμβος u υπολογίζει ξανά την απόσταση που έχει με κάθε άλλο κόμβο v του δικτύου. Ο αλγόριθμος που χρησιμοποιείται είναι και πάλι ο AsynchBellmanFord με τις παραπάνω πολυπλοκότητες για κάθε ενημέρωση των πινάκων.
Γενικά, δεν υπάρχει μια γενική, καθολική λύση για το πρόβλημα της δρομολόγησης καθώς επίσης σε πραγματικά δίκτυα οι συνθήκες του δικτύου αλλάζουν καθώς εξελίσσεται χρονικά το σύστημα. Συνεπώς, οι αλγόριθμοι δρομολόγησης θα πρέπει να εντοπίζουν τις αλλαγές και να προσαρμόζονται αναλόγως. Επίσης, από την παραπάνω συζήτηση παρατηρούμε ότι ορισμένοι αλγόριθμοι που σχεδιάστηκαν για σύγχρονα συστήματα επιτυγχάνουν καλύτερη αποδοτικότητα ως προς την χρονική πολυπλοκότητα αλλά και την πολυπλοκότητα επικοινωνίας οπότε και εύλογα αναρωτιόμαστε αν μπορούμε να προσαρμόσουμε τους αλγορίθμους αυτούς στα ασύγχρονα συστήματα. Η απάντηση είναι ναι, και εδώ έρχονται στο προσκήνιο τα αυτόματα εισόδου/εξόδου που αναφέραμε στην αρχή της ενότητας αυτής, τα οποία θα συντελέσουν στο να παρεμβάλλουμε ένα ενδιάμεσο επίπεδο μεταξύ του υλικού (κόμβοι, κανάλια) και λογισμικού (διεργασίες). Το αποτέλεσμα θα είναι το ενδιάμεσο αυτό επίπεδο να παρουσιάζει το υποκείμενο σύστημα ως σύγχρονο σύστημα. Γενικά η διαδικασία σχεδιασμού που ακολουθούμε είναι αρχικά να θέτουμε το πρόβλημα όπως τι δρομολόγηση θέλουμε, αν θέλουμε κατασκευή επικαλυπτικού δέντρου, αναζήτηση κατά εύρος κτλ, και στην συνέχεια προσδιορίζουμε το σύστημα για παράδειγμα κάποια εκδοχή του ασύγχρονου μοντέλου, και έπειτα παρεμβάλουμε το ενδιάμεσο επίπεδο συγχρονισμού και τέλος σχεδιάζουμε ένα νέο αλγόριθμο ή προσαρμόζουμε κάποιον από τους υπάρχοντες για το σύγχρονο μοντέλο. Η παραπάνω διαδικασία μπορεί να χαρακτηριστεί ως ένας τρόπος μετατροπής αλγορίθμων για σύγχρονα συστήματα σε αλγορίθμους για ασύγχρονα συστήματα.
Το αρχικό μας σημείο εκκίνησης είναι ένα σύγχρονο μοντέλο δικτύου, με μια συλλογή από n σύγχρονες διεργασίες να τρέχουν στους κόμβους ενός μη κατευθυνόμενου γράφου G=(V,E), επικοινωνώντας μέσω μηνυμάτων που στέλνονται πάνω στις ακμές. Στο σύγχρονο δίκτυο κάθε διεργασία u παρουσιάζεται σαν ένα είδος μηχανής καταστάσεων με γεννήτρια μηνυμάτων και συναρτήσεις μεταβάσεων. Εδώ, παρεκτρεπόμαστε από την προηγούμενη υλοποίηση παρουσιάζοντας την κάθε διεργασία σαν ένα αυτόματου εισόδου/εξόδου έστω Pu. Επίσης θεωρούμε ένα αυτόματο εισόδου/εξόδου S το οποίο εκτελεί την λειτουργία του συγχρονιστή.
Η πάνω εικόνα αντιστοιχεί στην γραφική αναπαράσταση ενός σύγχρονου δικτύου, ενώ η κάτω στην μοντελοποίηση ως σύγχρονου, ενός ασύγχρονου δικτύου.
Θεωρούμε ότι το πρόβλημα του συγχρονισμού λύνεται από έναν αλγόριθμο Α αν προσφέρει ένα περιβάλλον εκτέλεσης τέτοιο ώστε μια διεργασία P να μην μπορεί να διαχωρίσει αν εκτελείται σε ένα ασύγχρονο σύστημα (δηλαδή ο κατανεμημένος αλγόριθμος μαζί με τον συγχρονιστή), ή απευθείας σε ένα σύγχρονο σύστημα. Συνεχίζοντας θεωρούμε Μ το αλφάβητο μηνυμάτων που χρησιμοποιεί ο αλγόριθμος κατά την εκτέλεσή του σε σύγχρονο σύστημα. Αντιστοιχούμε σε κάθε μήνυμα m μια ετικέτα της μορφής <m,v> προσδιορίζοντας έτσι τον παραλήπτη του μηνύματος, όπου m Є M και 1 ≤ i ≤ n. Η ενέργεια εξόδου του αυτόματου Pu είναι της μορφής send(T,r)u, όπου Τ είναι ένα σύνολο από ετικέτες μηνυμάτων και r Є N+ είναι ο γύρος του σύγχρονου συστήματος κατά τον οποίο πραγματοποιείται η ενέργεια. Αν το αυτόματο δεν έχει να στείλει μηνύματα στον γύρο r, τότε πραγματοποιεί ενέργειες της μορφής send(null,r)u. Η ενέργεια εισόδου του αυτομάτου είναι της μορφής receive(T,r)u, όπου Τ είναι ένα σύνολο από ετικέτες μηνυμάτων και r Є N+ είναι ο γύρος του σύγχρονου συστήματος κατά τον οποίο πραγματοποιείται η ενέργεια. Έτσι για κάθε γύρο r, το Pu στέλνει στον συγχρονιστή ένα send(T,r)u και αναμένει από τον συγχρονιστή receive(T,r)u. Για να γίνουν πιο σαφή τα παραπάνω, δίνεται ένα παράδειγμα ενεργειών εισόδου/εξόδου για το αυτόματο P.
Έστω n=3. Η ενέργεια send({(m1,1),(m2,2)},4)3 υποδεικνύει ότι στον γύρο 4, η διεργασία P3 στέλνει το μήνυμα m1 στην P1 και το μήνυμα m2 στην P2. Αντίστοιχα, η ενέργεια receive({(m1,1),(m2,2)},4)3 υποδεικνύει ότι στον γύρο 4, η διεργασία P3 παραλαμβάνει το μήνυμα m1 από την P1 και το μήνυμα m2 από την P2.
