Δρομολόγηση

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

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

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

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

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

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

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

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

Πίνακας περιεχομένων 1 Βασικές έννοιες της δυναμικής δρομολόγησης 1.1 Αλγόριθμοι διανυσμάτων απόστασης (Distance vector algorithms) 1.2 Αλγόριθμοι κατάστασης συνδέσεων (Link-state algorithms) 2 Δείτε επίσης 3 Αναφορές 4 Εξωτερικοί Σύνδεσμοι

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

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

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

Κυρίως άρθρο: Distance-vector routing protocol

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

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

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

Κυρίως άρθρο: Link-state routing protocol

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

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

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

[Επεξεργασία] Δείτε επίσης

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

Το αρχικό κείμεο του άρθρου είναι μετάφραση του αντίστοιχου άρθρου της Αγγλικής Wikipedia.

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

• Routing, ένα διάγραμμα για το πως δουλεύει η δρομολόγηση
• ITPRC's IP Routing Resource Center
• Router Troubleshooting Primer - Βήματα για την επίλυση λαθών στην δρομολόγηση.