Open Shortest Path First

Το open shortest path first (OSPF) είναι ιεραρχικό πρωτόκολλο δρομολόγησης εσωτερικών πυλών (interior gateway protocol (IGP)) με βάση την κατάσταση της σύνδεσης (link-state), για δρομολόγηση σε δίκτυα υπολογιστών. Ο αλγόριθμος του Dijkstra, που εφαρμόζεται για να υπολογιστεί το δέντρο ελάχιστης διαδρομής (shortest path tree), χρησιμοποιεί το κόστος σαν μέτρο για την δρομολόγηση. Κατασκευάζεται μια βάση δεδομένων κατάστασης συνδέσεων της τοπολογίας του δικτύου η οποία είναι η ίδια σε όλους τους δρομολογητές.

Το OSPF είναι πιθανώς το πιο διαδεδομένο πρωτόκολλο εσωτερικών πυλών (IGP) σε μεγάλα δίκτυα. Μπορεί να λειτουργήσει με ασφάλεια, χρησιμοποιώντας MD5 για να πιστοποιήσει τους ομότιμούς του πριν να σχηματίσει γειτνιάσεις και πριν αποδεχτεί διαφημίσεις κατάστασης σύνδεσης (link-state advertisement). Είναι η συνέχεια του RIP, το οποίο είναι ένα πρωτόκολλο που υποστήριζε εξ αρχής διευθυνσιοδότηση χωρίς κλάσεις. Μια νεότερη έκδοση του OSPF, (η OSPFv3), υποστηρίζει επίσης και το IPv6. Επεκτάσεις πολυεκπομπής για το OSPF, όπως τα πρωτόκολλα multiport open shortest path first (MOSPF) έχουν μεν οριστεί, αλλά δεν χρησιμοποιούνται ευρέως προς το παρόν. Το OSPF μπορεί να βάλει «ετικέτες» στις διαδρομές και να τις μεταδώσει και αυτές μαζι με τις διαδρομές.

Τύποι περιοχών 
Ένα δίκτυο, σύμφωνα με το OSPF, διαχωρίζεται σε περιοχές. Αυτές είναι λογικές ομάδες από δρομολογητές, των οποίων οι πληροφορίες συνοψίζονται και προωθούνται στο υπόλοιπο δίκτυο. Αρκετές «ειδικές» περιοχές έχουν οριστεί:

Περιοχή Κορμού (backbone area) 
Η περιοχή κορμού (επίσης γνωστή και ως περιοχή μηδέν) σχηματίζει τον πυρήνα ενός δικτύου που στηρίζεται στον OSPF. Όλες οι υπόλοιπες περιοχές συνδέονται σε αυτή και η δια-περιοχιακή δρομολόγηση (inter-area routing) γίνεται μέσω ενός δρομολογητή που βρίσκεται στην περιοχή κορμού.

Σημείωση: Όλες οι περιοχές του OSPF θα πρέπει να συνδέονται με την περιοχή κορμού.

Περιοχή στελεχών (Stub Area) 
Μια περιοχή στελεχών είναι μια περιοχή η οποία δεν λαμβάνει εξωτερικές διαδρομές (external routes). Οι εξωτερικές διαδρομές ορίζονται ως οι διαδρομές που διανέμονται στο OSPF από ένα άλλο πρωτόκολλο δρομολόγησης. Επομένως οι περιοχές στελεχών τυπικά να στηριχτούν σε μια προεπιλεγμένη διαδρομή για να στέλνουν την κίνηση σε διαδρομές έξω από την παρούσα περιοχή.

Πλήρως «στελεχωμένη» περιοχή (Totally stubby area - TSA) 
Μια πλήρως στελεχωμένη περιοχή είναι παρόμοια με μια περιοχή στελεχών, εντούτοις αυτή η περιοχή δεν επιτρέπει διαδρομές συνοψισμού (summary routes) επιπρόσθετα στις εξωτερικές διαδρομές, αυτό σημαίνει, ότι δια-περιοχιακές διαδρομές δεν συνοψίζονται σε αυτές τις περιοχές. Ο μόνος τρόπος για να δρομολογηθεί η κίνηση έξω από την περιοχή είναι μια προεπιλεγμένη διαδρομή, η οποία είναι και η μόνη Τύπου-3 LSA (Type-3 LSA) που διαφημίζεται στην περιοχή. Όταν υπάρχει μόνο μια διαδρομή προς τα έξω από τη περιοχή, λιγότερες αποφάσεις δρομολόγησης πρέπει να ληφθούν από τον επεξεργαστή διαδρομών, γεγονός που μειώνει την χρησιμοποίηση των πόρων του συστήματος.

Όχι-τοσο-στελεχωμένη Περιοχή (Not-so-stubby area - NSSA) 
Μια όχι-τόσο-στελεχωμένη περιοχή είναι ένας τύπος περιοχής στελεχών η οποία μπορεί να εισαγάγει διαδρομές από αυτόνομα συστήματα (Autonomous System - AS) και να τις στείλει στην περιοχή κορμού, αλλά δεν μπορεί να λάβει εξωτερικές διαδρομές από την περιοχή κορμού ή άλλες περιοχές. Η Cisco επίσης εφαρμόζει μια ιδιόκτητη έκδοση του NSSA η οποία ονομάζεται NSSA πλήρως στελεχωμένη περιοχή. Κληρονομεί τις ιδιότητες μιας πλήρως στελεχωμένης περιοχής, εννοώντας ότι οι συνοπτικές διαδρομές τύπου 3 και 4 δεν κατακλύζουν μια περιοχή αυτού του τύπου.

Τύποι Δρομολογητών του OSPF 
Το OSPF ορίζει διάφορους τύπους δρομολογητών. Αυτοί είναι λογικοί ορισμοί, ένας δρομολογητής που χρησιμοποιεί το OSPF μπορεί να είναι ταξινομημένος σε περισσότερους από τους τύπους που ακολουθούν. Για παράδειγμα, ένας δρομολογητής, ο οποίος είναι συνδεδεμένος σε πάνω από μια περιοχές και λαμβάνει διαδρομές από μια διεργασία BGP που είναι συνδεδεμένη σε ένα άλλο ΑΣ (Αυτόνομο Σύστημα), είναι και ABR (Area Border Router) και ASBR (Autonomous System Boundary Router).

Δρομολογητής Ορίων Περιοχής (Area Border Router - ABR) 
Ένας δρομολογητής ορίων περιοχής (ABR) είναι δρομολογητής ο οποίος συνδέει μια η περισσότερες περιοχές OSPF στο κυρίως δίκτυο κορμού. Λειτουργεί σαν μέλος σε όλες τις περιοχές που είναι συνδεδεμένος. Ένας ABR κρατάει πολλαπλά αντίγραφα της βάσης δεδομένων κατάστασης συνδέσμων (link-state database) στην μνήμη, ένα για κάθε περιοχή.

Δρομολογητής Ορίων Αυτόνομου Συστήματος (Autonomous System Boundary Router - ASBR) 
Ένας δρομολογητής ορίων αυτόνομου συστήματος (ASBR) είναι δρομολογητής ο οποίος είναι συνδεδεμένος περισσότερα από ένα ΑΣ (Αυτόνομο Σύστημα) και ανταλλάσσει πληροφορίες δρομολόγησης με δρομολογητές σε άλλα ΑΣ. Οι ASBR τυπικά τρέχουν και ένα μη-IGP (Interior Gateway Protocol), όπως το BGP (Border Gateway Protocol). Ένας ASBR χρησιμοποιείται για να διανέμει τις διαδρομές που δέχεται από το ένα ΑΣ σ' όλο το ΑΣ που ανήκει.

Εσωτερικός Δρομολογητής (Internal Router - IR) 
Ένας δρομολογητής ονομάζεται εσωτερικός δρομολογητής (IR), αν έχει γείτονες μόνο δρομολογητές που ανήκουν στην ίδια περιοχή με αυτόν.

Δρομολογητής Κορμού (Backbone Router - BR) 
Ένας δρομολογητής κορμού (BR) είναι δρομολογητής μια διεπαφή (interface) του οποίου είναι συνδεδεμένη με την περιοχή κορμού. Ένας ABR είναι ένας BR, το αντίθετο μπορεί και να μην ισχύει.

Ορισμένος Δρομολογητής (Designated Router - DR) 
Ένας ορισμένος δρομολογητής (DR) είναι δρομολογητής ο οποίος εκλέγεται από το δίκτυο με επιλογές σύμφωνα με τα παρακάτω (προεπιλεγμένα) κριτήρια:

 Αν η προτεραιότητα σε έναν δρομολογητή OSPF είναι 0, αυτό σημαίνει πως αυτός ΠΟΤΕ δεν θα εκλεγεί σαν DR ή BDR
 Όταν ένας DR παρουσιάσει μια βλάβη και αναλάβει ο BDR, διενεργούνται και άλλες εκλογές για να βρεθεί ο αντικαταστάτης BDR.
 Ο δρομολογητής που στέλνει τα «πακέτα χαιρετισμού» ("Hello packets") με την μεγαλύτερη προτεραιότητα.
 Αν δύο ή περισσότεροι δρομολογητές στέλνουν με την ίδια, μεγαλύτερη προτεραιότητα, τότε ο δρομολογητής που έχει το μεγαλύτερο RID (Router ID - ID Δρομολογητή) κερδίζει.
 (Σημείωση) Το RID είναι η μεγαλύτερη λογική (loopback) διεύθυνση που έχει ρυθμιστεί σε έναν δρομολογητή, αν δεν έχει οριστεί καμία loopback/λογική διεύθυνση τότε ο δρομολογητής χρησιμοποιεί την μεγαλύτερη διεύθυνση IP που έχει οριστεί στις διεπαφές του. (π.χ. 192.168.0.1 θα ήταν μεγαλύτερη από την 10.1.1.2).
 Συνήθως ο δρομολογητής με την δεύτερη μεγαλύτερη προτεραιότητα γίνεται BDR (Εφεδρικός Ορισμένος Δρομολογητής - Backup Designated Router).
 Η προτεραιότητα παίρνει τιμές από 1 έως 255, όσο πιο μεγάλη η τιμή τόσο μεγαλύτερη η πιθανότητα να γίνει ένας δρομολογητής είτε DR είτε BDR.
 Αν ένας δρομολογητής με ΜΕΓΑΛΥΤΕΡΗ προτεραιότητα συνδεθεί ΜΕΤΑ από την εκλογή, δεν θα γίνει BR ή BDR μέχρι (τουλάχιστον) ο DR και BDR να πάθουν κάποια βλάβη.

Οι ορισμένοι δρομολογητές υπάρχουν με σκοπό να μειώνουν την κίνηση του δικτύου προσφέροντας την πηγή για τις ενημερώσεις της δρομολόγησης, ο DR διατηρεί ένα πλήρες πίνακα με την τοπολογία του δικτύου και στέλνει ενημερώσεις στους υπόλοιπους δρομολογητές μέσω πολυεκπομπής (multicast). Με αυτό τον τρόπο δεν χρειάζεται να ενημερώνουν όλοι οι δρομολογητές ο ένας τον άλλο συνεχώς, και μπορούν να παίρνουν τις ενημερώσεις του από μια πηγή. Η χρήση της πολυεκπομπής (multicasting) περαιτέρω μειώνει το φόρτο του δικτύου. Οι DR και BDR παντα ρυθμίζονται/εκλέγονται σε δίκτυα εκπομπής (broadcast networks) όπως το Ethernet. Οι DR μπορούν επίσης να εκλεγούν σε ΝΒΜΑ (Non-broadcast Multi-Access) δίκτυα όπως Frame Relay. Οι DR και BDR δεν ρυθμίζουν τις point-to-point συνδέσεις (όπως μια point-to-point WAN σύνδεση) γιατί το εύρος ζώνης μεταξύ δύο host δεν μπορεί να βελτιστοποιηθεί περαιτέρω.

Εφεδρικός Ορισμένος Δρομολογητής (Backup Designated Router - BDR) 

Ένας εφεδρικός ορισμένος δρομολογητής (BDR) είναι δρομολογητής ο οποίος γίνεται ορισμένος δρομολογητής αν ο υπάρχων ορισμένος δρομολογητής παρουσιάσει κάποια βλάβη. Ο BDR είναι ο OSPF δρομολογητής με την δεύτερη μεγαλύτερη προτεραιότητα.

Ιστορία των RFCs 

Η ιστορία καταγράφεται με τα RFCs (Requests For Comments που τελικά έγιναν αποδεκτά γνωρίζοντας ευρεία χρήση.)

 1989, Οκτώβριος - Αρχικά υποβάλλεται σαν προτεινόμενο πρότυπο, ως RFC 1131.

 1994, Μια παραλλαγή του OSPF από την NSSA, RFC 1587.

 1994, Μάρτιος - Επεκτάσεις πολυεκπομπής για το OSPF προτείνονται ως RFC 1584.

 1997, Ιούλιος - OSPF έκδοση 2η, όπως προτείνεται στο RFC 2178.

 1998, Απρίλιος - OSPF έκδοση 2, ενημερώθηκε στο RFC 2328, σαν standard 54.

 1999, Δεκέμβριος - OSPFv3, IPv6, RFC 2740.

 2003, Ιανουάριος - Ενημερώθηκε η παραλλαγή του OSPF της NSSA, RFC 3101.

Εξωτερικοί Σύνδεσμοι

Πηγές Πληροφοριών 
 IETF OSPF Working Group
 Ρύθμιση πρωτοκόλλου OSPF σε Point-to-Point network 
 Design and Implementation of OpenOSPFD (Paper)
 Design and Implementation of OpenOSPFD (Presentation)
 Cisco OSPF
 Cisco OSPF Areas and Virtual Links
 OSPF Tutorial

Υλοποιήσεις 
 OpenOSPFD «δαίμονας»
 Zebra λογισμικό δρομολόγησης για Unix-οειδή συστήματα που υποστηρίζουν το OSPF
 Quagga , βασισμένο (fork) στο Zebra 
 XORP  Μια σουίτα δρομολόγησης που περιλαμβάνει μια περιορισμένη έκδοση του OSPF

Πρωτόκολλα δρομολόγησης