OSPF

Open Shortest Path First (OSPF) er en innvendig rutingprotokoll som brukes innenfor et avgrenset autonomt system. Den er basert på koblingsdata og fungerer på lag 3 i OSI-modellen. OSPF ble utviklet som et alternativ til Routing Information Protocol (RIP) for å håndtere sistnevntes begrensninger. Protokollen bygger et algoritmisk tre over nettverkstopologien, og ved hjelp av Dijkstras algoritme regner den ut korteste vei til destinasjoner og nettverk.

Opprinnelse

OSPF ble utviklet av Interior Gateway Protocol (IGP)-gruppen i Internet Engineering Task Force (IETF). Gruppen ble dannet i 1988 for å utforme en IGP basert på en algoritme for korteste vei først (shortest path first, SPF). Dijkstras algoritme er en slik algoritme.

Protokollen bygger på forskning fra blant annet Richard Bolt, Leo Beranek og Robert Newman sin SPF-algoritme utviklet i 1978 for ARPANET, deres senere arbeid med områderuting i 1986, Radia Perlman sin forskning på feiltolerant kringkasting av rutinginformasjon i 1988, samt en tidlig versjon av Intermediate System to Intermediate System (IS-IS)-rutingprotokollen.

OSPF er en åpen standard som hvem som helst kan implementere uten lisenskostnader. Dette har gjort at mange leverandører av nettverksutstyr støtter protokollen. Som en følge av dette har OSPF blitt populær som en erstatning for proprietære rutingprotokoller.

Prinsipp

I OSPF er rutingen basert på koblingsdata (link-state routing), i motsetning til den eldre Routing Information Protocol (RIP) som er basert på avstand og retning (distance-vector routing). Dette innebærer at ruterne kjenner til hverandre og kontinuerlig oppdaterer status og informasjon om forbindelsene seg imellom.

Disse koblingsdataene danner et bilde av nettverkstopologien. Ruteren legger dem i en lokal database som samkjøres med alle de andre ruterne. Ut fra dette beregner ruteren den optimale veien til hver destinasjon og genererer sin rutingtabell.

Konkret virkemåte

For å nå sine mål om oppdaterte rutingtabeller går hver ruter i et OSPF-oppsett gjennom en kontinuerlig prosess som er forenkelt beskrevet her. Merk at selv om essensen er riktig kan steg overlappe eller utføres parallelt.

Kartlegging

En ruter finner sine naborutere og oppretter relasjoner til dem. Dette gjør den ved å sende ut dedikerte kontrollpakker kalt «hallo-pakker» (hello packets). Deretter fortsetter ruteren å sende slike pakker med jevne mellomrom for å vedlikeholde oversikten over naborutere og relasjoner. I tillegg lytter den etter tilsvarende pakker fra kjente naborutere.

Ruteren kan konfigureres med et sendingsintervall (hello interval) som angir hvor lang tid det skal gå mellom hver gang en «hallo-pakke» sendes ut. Tilsvarende finnes det en innstilling for lytteintervall (router dead interval) som angir hvor lenge ruteren skal vente på en «hallo-pakke» fra en naboruter før naboruteren erklæres som død.

Kunngjøring av koblingsdata (LSA)

Ruteren kunngjør koblingsdataene sine (link-state advertisement, LSA) ved å dele denne informasjonen med sine kjente relasjoner.

For å unngå å sende fullstendige data hver gang, sender ruteren først ut metadata om databasen (database description). I praksis er dette en liste over tilgjengelige oppføringer av koblingsdata, men uten selve dataene. Hver mottakende ruter sjekker metadataene opp mot egen database. For hver oppføring som måtte mangle, sendes en forespørsel om selve koblingsdataene (link-state request) tilbake til den opprinnelige ruteren, som deretter sender dataene for oppføringen.

Oppbygging av database (LSDB)

Hver ruter har sin egen database over koblingsdata (link-state database), kalt LSDB. Det er viktig at alle ruternes LSDB-er er identiske for å unngå at rutingen går i sirkel (routing loops), og derfor må ruterne jevnlig synkronisere sine LSDB-er med hverandre. Utveksling av data (LSA) er prosessteget som gjennomfører denne nødvendige synkroniseringen.

Hver ruters LSDB bygges dermed opp på grunnlag av både egen kartlegging og synkronisering med de andre ruterne.

Generering av rutingtabell

Straks en ruter har en oppdatert LSDB, bruker den Dijkstras algoritme til å regne ut den optimale veien til hver destinasjon eller nettverk i tilhørende OSPF-område (OSPF area). Optimal vei beregnes ut fra den samlede kartleggingen til samtlige rutere, og stammer altså fra koblingsdataene. Derfor er det ikke sikkert at geografisk nærhet eller kortere nettverkskabling automatisk medfører optimal vei. Denne distinksjonen er noe av styrken i OSPF sammenlignet med RIP.

På bakgrunn av disse optimale veiene lager ruteren oppføringene i rutingtabellen sin.

OSPF areas

• Normal Areas
• Stubby Areas
• Not-so-stubby-areas

OSPF router types

• Internal Router – Har alle sine interfaces i samme area.
• Area Border Router – Har interface tilkoblet i mer enn ett area og har ansvaret for å generere oppsummeringsannonseringer for ett eller flere areas.
• Autonomous System Boundary Router – Fungerer som en gateway mellom OSPF og andre rutingprotokoller, og har ansvaret for å generere AS-eksterne annonseringer.

OSPF og ulike nettverkstyper

• Broadcast-nettverk (Ethernet)
• Point-to-Point nettverk
• Non-broadcast Multi access (NBMA) nettverk
• Point-to-Multipoint nettverk

Designated Router Types

Hvis alle ruterne i et broadcast-nettverk utveksler ruter med hverandre kan dette bidra til mye trafikk og begrense båndbredden spesielt på trege linker. For å redusere trafikk velger alle broadcast-nettverk en Designert Ruter (DR). En DR lytter til LSA-er på All Designated Routers multicast-adresse 224.0.0.6. Dette er for å forhindre at andre rutere tar imot og bruker ressurser på å prosessere meldinger som ikke er adressert til dem. Den sender ut nettverks-LSA til andre rutere på 224.0.0.5; dette forsikrer alle at alle rutere har samme LSDB. Backup Designated Router (BDR) lytter også på LSA på multicast-adressen 224.0.0.6. BDR sikrer kjapp failover hvis den designerte ruteren skulle bli utilgjengelig.

Andre OSPF-rutere sender LSA til DR og BDR med multicast-adressen 224.0.0.6 og lytter til nettverks-LSA-er på 224.0.0.5. Point-to-point og point-to-multipoint nettverk velger ikke DR og BDR.

Litteratur

• Douglas E. Comer: TCP/IP: Principles, protocols and architecture Fifth Edition. ISBN 0-13-1876716
• Adrian Farrel: The Internet and its protocols: A comparative approach. ISBN 1-55860-913-X