Δρομολόγηση: Διαφορά μεταξύ των αναθεωρήσεων

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

 

 

Το υλικό που χρησιμοποιείται στη δρομολόγηση περιλαμβάνει [[Συγκεντρωτής|συγκεντρωτές]], [[Μεταγωγέας|μεταγωγείς]], και [[Δρομολογητής|δρομολογητές]].

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

 

 

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

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

 

 

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

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

 

 

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

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

 

 

== Δείτε επίσης ==