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.
OSPF domėnai yra suskirstyti į zonas kurios sužymėtos 32 bitų identifikatoriais. Zonų identifikatoriai įprastai būna surašyti dešimtainių su tašku formatu, tokiu pat kaip IPv4 adresai. Tačiau, jie nėra IP adresai ir gali dubliuotis nekonfliktuodami su bet kokių IPv4 adresu. Zonų identifikatoriai IPv6 domėnams taip pat naudoja 32 bitu identifikatorius, parašytus tokiu pačiu formatu. OSPF zonos yra loginės kompiuterių ir tinklų grupės, įskaitant ir maršrutizatorius, prijungtus prie tinklų. Kiekviena zona turi atskira sujungimo buklės duomenų bazę, kurios informacija likusiam tinklui apybendrina prijungtas maršrutizatorius. Taigi erdvės topologija lieka nežinoma už zonos ribų. Tai sumažina duomenų srauta tarp atskirų tinklo dalių.
Yra numatytos kelios skirtingos zonų rušys.
==Pagrindinė sritis==
Pagrindinė sritis (0.0.0.0 zona) suformuoja tinklo branduolį. Visos kitos zonos yra prijungtos prie jos, ir tarp zoninio ryšis vyksta per maršrutizatorius prijungtus prie pagrindinės zonos ir prie savos susietosios srities. Tokia yra fizinė ir loginė OSPF domėno struktūra. Pagrindinė sritis yra atsakynga už maršrutizavimo iformacijos perdavima tarp ne pagrindinių zonų. Pagrindinė sritis turi buti susieta su kitomis tačiau ne butinai fiziskai, pagrindinės srities sujungimas gali buti realizuotas per per virtualius sujungimus. Visos OSPF zonos privalo buti sujungtos su pagrindinę zoną. Tačiau šį jungtis gali buti ir virtuali. Pavizdžiui, tarkime, kad zona 0.0.0.1turi fizini sujungima su zona 0.0.0.0, o zona 0.0.0.2 tokios jungties neturi, tačiau turi jungti su 0.0.0.1 zona. 0.0.0.2 zona gali panaudoti virtualu sujungima per tranzitinę 0.0.0.1 zoną, tam, kad pasiektu pagrindinę zoną. Tam, kad zona butu tranzitinė, zona turi turėti tranzito atributą, taigi ji jokių būdų nebus užkelmėjusi [angl. stub area].
==Užkelmėjusi zona==
Užkelmėjusi zona yra zona kuri negauna maršrutų aprašymų išorinių autonominei sistemai ir viduje zonos maršrutizuoja kaip numatyta pagal nutylėtąjį maršrutą.
==Ne visai užkelmėjusi zona==
Egzistuoja pagerinta užkelmėjusios zonos koncepcija vadinama ne visai užkelmėjusi zona. Taip pat yra keletas kitų patentuotu variacijų, kurias naudoja sistemų gamintojai. Ne visai užkelmėjusi zona yra tokia zona kuri gali importuoti autonominių sistemų išorinius maršrutus ir juos persiusti į kitas zonas.
Naudota literatūra
1. http://en.wikipedia.org/wiki/Open_Shortest_Path_First
2. В.Г. Олифер, Н.А. Олифер. Компютерные сети. 3-е издание.
3. http://www.cisco.com/en/US/tech/tk365/technologies_tech_note09186a0080094a74.shtml#typesofospfareas