Πριν αρχίσετε να διαβάζετε αυτό το άρθρο, σας συμβουλεύουμε να εξοικειωθείτε με το υλικό για τον υπολογισμό της διαδρομής σύμφωνα με τον αλγόριθμο Bellman - Ford.
Ο αλγόριθμος ενημέρωσης διάχυσης (αλγόριθμος ενημέρωσης διάχυσης) είναι ένας από τους δύο αλγόριθμους που συζητούνται εδώ αρχικά προοριζόμενοι για υλοποίηση σε ένα κατανεμημένο δίκτυο. Είναι μοναδικό, καθώς καταργεί επίσης πληροφορίες σχετικά με την επίτευξη και την τοπολογία που περιέχεται στα τελικά αυτοματαράτα του αλγορίθμου. Άλλοι αλγόριθμοι που συζητήθηκαν εδώ αφήνουν την άρση των πληροφοριών κατά τη διακριτική ευχέρεια της εφαρμογής του πρωτοκόλλου και δεν θεωρούν αυτή την πτυχή του έργου του αλγορίθμου εντός του ίδιου του αλγορίθμου.
Μέχρι το 1993, η Bellman-Ford και η Dijkstra εφαρμόστηκαν ως κατανεμημένοι αλγόριθμοι σε διάφορα πρωτόκολλα δρομολόγησης. Η εμπειρία που αποκτήθηκε ως αποτέλεσμα αυτών των πρώιμων υλοποιήσεων και ανάπτυξης οδήγησε στο "δεύτερο κύμα" της έρευνας και του προβληματισμού σχετικά με το πρόβλημα της δρομολόγησης στα δίκτυα μεταγωγής δικτύων, τα οποία οδήγησαν στην εμφάνιση του διανύσματος διαδρομής και διπλής.
Δεδομένου ότι το Dual έχει σχεδιαστεί ως κατανεμημένος αλγόριθμος, είναι καλύτερο να περιγράψουμε το έργο του στο δίκτυο. Για το σκοπό αυτό, τα στοιχεία 8 και 9 χρησιμοποιούνται. Για να εξηγηθεί το διπλό, αυτό το παράδειγμα θα ανιχνευθεί σε ένα ρεύμα τριών προορισμών και, στη συνέχεια, οι αλλαγές επεξεργάζονται στην κατάσταση διαθεσιμότητας για τα ίδια στοιχεία προορισμού. Στο πρώτο παράδειγμα, η υπόθεση θα εξεταστεί όταν υπάρχει μια εναλλακτική διαδρομή, αλλά δεν υπάρχει προς τα κάτω γείτονα, το δεύτερο θα εξετάσει την υπόθεση όταν υπάρχει εναλλακτική πορεία και προς τα κάτω γείτονα.
Στο Σχήμα 8, μελέτη D από την άποψη Α:
- Ένας μαθαίνει δύο τρόπους d:
- Το Α δεν θα αναγνωρίσει τη διαδρομή μέσω Β, επειδή το Β χρησιμοποιεί ένα ως διάδοχό της:
- Ένα συγκρίνει τις διαθέσιμες διαδρομές και επιλέγει τη συντομότερη διαδρομή χωρίς βρόχους:
- Ένας ελέγχει τις υπόλοιπες διαδρομές για να προσδιοριστεί αν υπάρχουν από αυτές τις κάτω γείτονες:
Το Γνωρίζει αυτό επειδή το C ανακοινώνει τη διαδρομή προς D με την τοπική του μετρική ίση με 3.
Το A διατηρεί μια τοπική μετρική C στο τραπέζι τοπολογίας του.
Κατά συνέπεια, ένα γνωρίζει την τοπική τιμή στο C και την τοπική τιμή στο Α.
- 3 (Κόστος Γ) = 3 (Κόστος Α), οπότε η διαδρομή αυτή μπορεί να είναι βρόχος, συνεπώς, το C δεν πληροί την προϋπόθεση της σκοπιμότητας. Το C δεν φέρει ετικέτα ως κατάντη γείτονες.
Οι κατάντη γείτονες στο διπλό ονομάζονται πιθανούς διαδόχους. Ας υποθέσουμε ότι το κανάλι [a, h] δεν λειτουργεί. Το διπλό δεν βασίζεται σε περιοδικές ενημερώσεις, οπότε ένα δεν μπορεί να περιμένει μια άλλη ενημέρωση με αξιόπιστες πληροφορίες. Αντίθετα, πρέπει να ακολουθήσει ενεργά μια εναλλακτική διαδρομή. Έτσι, αυτή είναι μια διάχυτη διαδικασία ανίχνευσης μιας εναλλακτικής διαδρομής. Εάν το κανάλι [a, h] δεν λειτουργεί, λαμβάνοντας υπόψη μόνο το d:
- Ένας ελέγχει το τοπικό σας τραπέζι για πιθανούς διαδόχους (κατάντη γείτονες).
- Δεν υπάρχουν πιθανοί διάδοχοι, οπότε πρέπει να βρει μια εναλλακτική διαδρομή χωρίς βρόχους έως d (αν υπάρχει).
- Α στέλνει ένα αίτημα σε κάθε γείτονα για να διαπιστώσει εάν υπάρχει κάποια εναλλακτική διαδρομή χωρίς βρόχους στο D.
- Στο C:
- Στο Β:
- Ένα παίρνει αυτές τις απαντήσεις:
Στο σχήμα 9, το στοιχείο προορισμού (D) μετακινήθηκε με Η έως Ε. Αυτό θα χρησιμοποιηθεί στο δεύτερο παράδειγμα.
Σε αυτό το παράδειγμα, υπάρχει ένας πιθανός διάδοχος (προς τα κάτω γείτονας).
Μελέτη D από την άποψη Α:
- Ένας μαθαίνει δύο τρόπους d:
- Ένα δεν θα αναγνωρίσει κανένα τρόπο μέσω του Β:
- Ένα συγκρίνει τις διαθέσιμες διαδρομές και επιλέγει τη συντομότερη διαδρομή χωρίς βρόχους:
- Ένας ελέγχει τις υπόλοιπες διαδρομές για να προσδιοριστεί αν υπάρχουν από αυτές τις κάτω γείτονες:
Εάν το κανάλι [Α, C] δεν λειτουργεί, απλά εξετάζοντας ένα:
- Ένας ελέγχει τον πίνακα τοπικής τοπολογίας για έναν πιθανό διάδοχο.
- Πιθανός διάδοχος υπάρχει μέσω του Η.
- Ένα διακόπτει το τοπικό πίνακα του στο h ως τον καλύτερο τρόπο.
- Α στέλνει μια ενημέρωση στους γείτονές της, σημειώνοντας ότι το κόστος επίτευξης D έχει αλλάξει από 3 έως 4.
Όπως μπορείτε να δείτε, επεξεργασία όταν υπάρχει ένας πιθανός διάδοχος, πολύ πιο γρήγορος και ευκολότερος από το χωρίς αυτό. Στα δίκτυα όπου το πρωτόκολλο δρομολόγησης αναπτύχθηκε χρησιμοποιώντας διπλό (ειδικότερα, EIGRP), ένας από τους κύριους στόχους σχεδιασμού θα περιορίσει τον όγκο των αιτήσεων που παράγονται απουσία ενός πιθανού διαδόχου. Η περιοχή αιτήσεως είναι ο κύριος καθοριστικός παράγοντας τον τρόπο με τον οποίο ολοκληρώνεται γρήγορα ο διπλός αλγόριθμος και, ως εκ τούτου, πόσο γρήγορα το δίκτυο συγκλίνει.
Το σχήμα 10 δείχνει τη βασική τελική διπλή μηχανή.
Τα πράγματα που περιλαμβάνονται στη διαδρομή επιδεινώνονται (υποβάθμιση της διαδρομής) μπορεί να είναι:
- Αποτυχία του συνδεδεμένου καναλιού ή του γείτονα
- Λάβετε μια ενημέρωση για μια διαδρομή με υψηλότερη μέτρηση
- Να πάρει ένα ερώτημα από τον τρέχοντα διάδοχο
- Να πάρει μια νέα διαδρομή από έναν γείτονα
- Ένας νέος γείτονας βρέθηκε, καθώς και διαδρομές με τις οποίες μπορεί να πάρει
- Να πάρει όλα τα αιτήματα που αποστέλλονται στους γείτονες όταν η διαδρομή επιδεινώνεται
