Δρομολόγηση

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
 Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. Βοηθήστε συνδέοντας το κείμενο με τις πηγές χρησιμοποιώντας παραπομπές, ώστε να είναι επαληθεύσιμο.
Το πρότυπο τοποθετήθηκε χωρίς ημερομηνία. Για τη σημερινή ημερομηνία χρησιμοποιήστε: {{χωρίς παραπομπές|23|04|2024}}

Στα δίκτυα υπολογιστών ο όρος δρομολόγηση (αγγλ. routing) αναφέρεται στη διαδικασία με την οποία επιλέγεται η διαδρομή μέσα σε ένα δίκτυο πάνω από την οποία θα σταλούν δεδομένα.

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

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

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

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

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

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

Στατική δρομολόγηση[Επεξεργασία | επεξεργασία κώδικα]

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

Δρομολόγηση συντομότερης διαδρομής[Επεξεργασία | επεξεργασία κώδικα]

Ο όρος 'συντομότερη' δεν αφορά απαραίτητα φυσική απόσταση, αλλά μπορεί να είναι οποιοδήποτε κριτήριο, το οποίο ποικίλει από υλοποίηση σε υλοποίηση. Σε κάποιο πρωτόκολλο δρομολόγησης μπορεί ένα κριτήριο απόστασης να είναι το πλήθος των αλμάτων από κόμβο σε κόμβο ή η μέση καθυστέρηση μετάδοσης ή το εύρος ζώνης κλπ. Σε κάθε περίπτωση, υπολογίζονται (βάσει ενός κριτήριου) οι αποστάσεις από κάθε δρομολογητή προς τους γειτονικούς του. Δεδομένων των αποστάσεων μεταξύ γειτονικών δρομολογητών, μπορούν να χρησιμοποιηθούν διάφοροι αλγόριθμοι για τον υπολογισμό της συντομότερης διαδρομής μεταξύ δύο (όχι απαραίτητα γειτονικών) δρομολογητών. Ο πιο γνωστός αλγόριθμος εύρεσης συντομότερης διαδρομής είναι αυτός του Dijkstra. Έτσι, κάθε δρομολογητής υπολογίζει τη συντομότερη διαδρομή προς κάθε προορισμό και βάσει αυτού αποφασίζει σε ποιον δρομολογητή να στείλει το πακέτο IP.

Δρομολόγηση πλημμύρας (flooding)[Επεξεργασία | επεξεργασία κώδικα]

Σε έναν τέτοιο αλγόριθμο δρομολόγησης, κάθε εισερχόμενο πακέτο στέλνεται σε κάθε εξερχόμενη γραμμή εκτός από αυτή από την οποία έφτασε. Με τον τρόπο αυτό, δημιουργούνται άπειρα αντίγραφα του πακέτου και θα πρέπει να ληφθούν μέτρα για την ανακοπή της πλημμύρας. Ένα μέτρο είναι να περιέχεται ένας μετρητής αλμάτων στην κεφαλίδα κάθε πακέτου IP. Πρέπει όμως ο μετρητής αλμάτων να μην έχει τιμή μικρότερη από το πλήθος των αλμάτων που χρειάζονται για να φτάσει το πακέτο από την πηγή στον προορισμό. Για κάθε άλμα, ο μετρητής μειώνεται κατά ένα. Όταν μηδενιστεί, το πακέτο δεν θα αναμεταδοθεί, αλλά θα απορριφθεί.

Βασικές έννοιες της δυναμικής δρομολόγησης[Επεξεργασία | επεξεργασία κώδικα]

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

Αλγόριθμοι διανυσμάτων απόστασης (Distance vector algorithms)[Επεξεργασία | επεξεργασία κώδικα]

Οι 'αλγόριθμοι διανυσμάτων απόστασης' χρησιμοποιούν τον αλγόριθμο Bellman-Ford. Αυτή η διαδικασία αναθέτει έναν αριθμό, το κόστος, σε κάθε ένα από τις συνδέσεις μεταξύ των κόμβων σε ένα δίκτυο. Οι κόμβοι θα στέλνουν πληροφορίες από το σημείο Α στο σημείο Β μέσω της διαδρομής που έχει το μικρότερο συνολικό κόστος (δηλ. το αποτέλεσμα που βγαίνει από την άθροιση του κόστους μεταξύ των κόμβων που χρησιμοποιήθηκαν).

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

Ένα πρωτόκολλο που χρησιμοποιεί αλγόριθμο διανυσμάτων απόστασης είναι το RIP, το αρχικό εσωτερικό πρωτόκολλο πύλης δικτύου του Internet. Αργότερα, αντικαταστάθηκε από το OSPF, το οποίο αποτελεί υλοποίηση ενός αλγορίθμου κατάστασης συνδέσεων.

Αλγόριθμοι κατάστασης συνδέσεων (Link-state algorithms)[Επεξεργασία | επεξεργασία κώδικα]

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

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

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

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Αναφορές[Επεξεργασία | επεξεργασία κώδικα]

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]

Ανακτήθηκε από "https://el.wikipedia.org/w/index.php?title=Δρομολόγηση&oldid=10318191"