Δρομολόγηση


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

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

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

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

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

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

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


Βασικές έννοιες της δυναμικής δρομολόγησης

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

Αλγόριθμοι διανυσμάτων απόστασης (Distance vector algorithms)

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

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

Αλγόριθμοι κατάστασης συνδέσεων (Link-state algorithms)

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

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

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

Δείτε επίσης

* Αλγόριθμοι Δρομολόγησης:
o Ιεραρχική Δρομολόγηση - Hierarchical routing
o Edge Disjoint Shortest Pair Algorithm
o "Hot-potato routing"
o "Cold-potato routing"
* Deflection routing
* Policy based routing
* Wormhole routing
* Adaptive routing
* Ειδικοί Σχεδιασμοί
o Classless inter-domain routing (CIDR)
o MPLS routing
o ATM routing
o Routing in the PSTN
* Θέματα που αφορούν την προώθηση πακέτων (όχι επιλογής διαδρομής)
o Network address translation (NAT)
o IP spoofing (Security)
* Μαθηματική πολυπλοκότητα στην δρομολόγηση με πολλές παραμέτρους.
o Quality of Service in routing
* Overlay network routing schemes
o Key based routing (KBR)
o Decentralized object location and routing (DOLR)
o Group anycast and multicast (CAST)
o Distributed hash tables (DHT)
* RPSL


Αναφορές

* Kurose, James E. and Ross, Keith W. (2004). Computer Networking. Benjamin/Cummings. ISBN 321227352
* Doyle, Jeff (2005). Routing TCP/IP, Volume I, Second Ed.. Cisco Press. ISBN 1-58705-202-4, Cisco Press ISBN 1-58705-202-4

* Διαδίκτυο

Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License

<@=@=@>


www.hellenica.de