Open Shortest Path First
OSPF
Trumpiausio atviro kelio pirmumo protokolas
Apibrėžimas
OSPF - protokolas, kuris optimalaus maršruto paieškai naudoja Dijkstros algoritmą.
Paaiškinimai
OSPF (angl. Open Shortest Path First) – tai protokolas, skirtas vidinei tinklo maršrutizacijai palaikyti ir buvo kuriamas kaip alternatyva RIP protokolui. Šis protokolas naudoja Dijkstros algoritmą ir yra pakankamai sudėtingas, jo aprašymas (RFC1583) užima 216 puslapių, o RIPv2 aprašymas (RFC1723) tik 33 puslapius. Kaip metrika dabar naudojamas ne šuolių skaičius, o aptarnavimo kokybes koeficientas. Didelis dėmėsis buvo skirtas maršrutizavimo lentelių vienodumą tinkle užtikrinantiems mechanizmams, kadangi esant skirtingoms lentelėms, maršrutizatoriai gali priimti vienas kitam prieštaraujančius maršrutizavimo sprendimus. Kiekvienas maršrutizatorius turi pilną informaciją apie visų tinklo maršrutizatorių tinklo sąsajų būsenas. OSPF palaiko skirtingos adresacijos tinklus. Jis tinka taškas-taškas, transliaciniams (Ethernet ir TokenRing) ir netransliaciniams (X.25) tinklams. OSPF standartas aprašo būvių automato, skirto maršrutizatoriaus elgesiui nustatyti, naudojimą. Kiekvienas maršrutizatorius tinkle gali būti viename iš keleto būvių. Būvių aibė yra pakankama tam, kad aprašyti visas įmanomas maršrutizatoriaus būsenas. Todėl maršrutizatorius bet kuriuo laiko momentu gali būti tik viename iš šių būvių. Būvio keitimą gali iššaukti tik įvykis. Standarte aprašytas baigtinis įvykių sąrašas, kuris gali aprašyti bet kokį tinklo būsenos pasikeitimą. Maršrutizatoriaus atliekamas veiksmas priklauso nuo būvio, kuriame jis yra ir nuo įvykio. Kiekvienas tinklo maršrutizatorius pats apskaičiuoja geriausią maršrutą. Jeigu yra du vienodą metriką turintys maršrutai, tai srautas lygiai dalinamas tarp tų maršrutų. Taip gaunamas efektyvesnis tinklo resursų išnaudojimas. Ieškant geriausia maršrutą, maršrutizatorius analizuoja orientuotą grafą, kurio mazgus sudaro tinklo mazgai, o ryšius tarp jų – ryšio linijos. Kiekvienai linijai priskiriama metrika. Paieškos algoritmas randa maršrutus, kurių metrikos yra mažiausios. Maršruto radimo pavyzdys pateiktas 1 pav. Paveikslo viršuje pateiktas pilnas tinklo grafas, o apačioje tas pats tinklas su paliktais geriausiais maršrutais iki visu mazgų.
1 pav. OSPF protokolo maršruto paieškos pavyzdys.
Aptarnavimo kokybes koeficientas charakterizuojamas tokiais parametrais: kanalo pralaidumas informacijos perdavimo delsa paketų stovinčių eilėje skaičius kanalo apkrovimas saugumo reikalavimai srauto tipas šuolių iki paskirties mazgo skaičius galimybė pasiekti paskirties mazgą kitais maršrutais
Pagrindinės charakteristikos, kurios žymiai įtakoja maršrutizacijos sprendimą – tai delsa, pralaidumas ir patikimumas. Transporto tikslams OSPF tiesiogiai naudoja IP, t.y. nenaudoja TCP ar UDP protokolų. OSPF turi savo kodą IP antraštes protokolo kodo lauke – 89. TOS kodas šiuose paketuose lygus 0. TOS reikšmė čia nurodoma ne antraštėje, o pačiame protokolo pakete. Šio protokolo paketų maršrutizacija priklauso tik nuo IP adreso ir TOS reikšmių. Kadangi protokolas nereikalauja inkapsuliacijos, tai leidžia lengvai naudoti protokolą sudėtinguose tinkluose. Skirtingai nuo RIP protokolo, naudojant OSPF protokolą, galima padalinti tinklą į zonas, kurių vidinė struktūra nėra matoma iš išorės. Tai leidžia žymiai sumažinti perduodamos maršrutizacijos informacijos kiekį ir supaprastinti maršrutizavimo lenteles. OSPF standarte aprašytas taip vadinamas tinklo skeletas (angl. backbone), skirtas komunikacijoms tarp atskirų tinklo zonų. Protokolas veikia tik savo zonos ribose, o kitose zonose gali būti taikomas ir kitas maršrutizavimo protokolas. Maršrutizatorių sąveikai naudojami du multicast IP adresai: 224.0.0.5 – skirtas ryšiui su visais maršrutizatoriais palaikančiais OSPF protokolą; 224.0.0.6 – skirtas ryšiui su specialiai išskirtu maršrutizatoriumi. Kiekvienas protokolo pranešimas prasideda nuo antraštės. Jos formatas pateiktas 2 pav.
2 pav. OSPF protokolo antraštes formatas.
Antraštė prasideda version lauku. Šiame lauke rašoma OSPF protokolo versija. Type lauke rašomas OSPF pranešimo tipas. Pranešimai būna 5 tipų:
1.Hello – skirtas maršrutizatoriaus pasiekiamumui patikrinti; 2.Database description – duomenų bazės (tinklo topologijos) aprašymas; 3.Link state request – kanalo būsenos užklausa; 4.Link state update – kalano būsenos pakeitimas; 5.Link state acknowledgment – kanalo būsenos priėmimo patvirtinimas. Packet length – paketo su antrašte ilgis matuojamas oktetais; Router ID – maršrutizatoriaus identifikacinis numeris; Checksum – kontrolinė suma, skirta paketo vientisumui patikrinti; Authentication type – nurodo ar įjungtas autentifikacijos mechanizmas; Authentication – autentifikacijai reikalinga informacija; Message body – pranešimo informacija.
Maršrutizacijos lentelių kūrimas vyksta 2 etapais:
Pirmo etapo metu kiekvienas maršrutizatorius savo atmintyje sudaro grafą, kurio mazgai yra prie to maršrutizatoriaus prijungti tinklo mazgai, tinklai ir kiti maršrutizatoriai, o ryšiai – maršrutizatorių tinklo sąsajos. Visi maršrutizatoriai siunčia vienas kitam informaciją apie jiems žinomos tinklo dalies topologiją. Šio etapo pabaigoje kiekvienas maršrutizatorius turi pilną informaciją apie tinklo struktūrą.
Antras etapas – optimalių maršrutų parinkimas turimame grafe. Optimalių maršrutų paieška – tai pakankamai sudėtingas procesas. OSPF protokole tam naudojamas iteratyvus Dijkstros algoritmas. Kiekvienas maršrutizatorius laiko savę tinklo centru ir apskaičiuoja trumpiausius kelius iki visų jam žinomų tinklų ir mazgų. Kiekviename tokiame maršrute įsimenamas tik 1 žingsnis – iki sekančio maršrutizatoriaus. Duomenys apie šį žingsnį įrašomi į maršrutizacijos lentelę. Jeigu keletas maršrutų turi vienodas metrikas, tai į maršrutizacijos lentelę įrašomi visi tokie įrašai.
Visi tinklo maršrutizatoriai kas 10 sekundžių siunčia savo kaimynams HELLO pranešimą, taip parodami, kad jie veikia ir ryšis tarp jų egzistuoja. Jeigu kuris nors maršrutizatorius negauna iš savo kaimyno tokios žinutes, tai jis koreguoja savo duomenų bazę (tinklo topologiją) ir siunčia savo kaimynams Link state update pranešimą. Kaimynai gauna šį pranešimą, koreguoja savo duomenų bazę ir siunčia tokį pat pranešimą visiems savo kaimynams, išskyrus tą, kuris atsiuntė pranešimą jiems. Po duomenų bazes atnaujinimo kiekvienas maršrutizatorius iš naujo apskaičiuoja optimalius maršrutus ir atnaujina savo maršrutizacijos lentelę. Toks pat procesas vyksta ir atsiradus naujam tinklo maršrutizatoriui, kuris pradeda siusti HELLO pranešimus.
Naudota literatūra
1. http://en.wikipedia.org/wiki/Open_Shortest_Path_First
2. В.Г. Олифер, Н.А. Олифер. Компютерные сети. 3-е издание.