Maršrutizacija – informacijos judėjimas

Maršrutizacija yra informacijos judėjimas tinklu iš šaltinio į nustatytą vietą pagal tam tikrą maršrutą. Maršrutizacija priklauso trečiam OSI (tinkliniam) lygiui. Maršrutizacijos sąvoka sieja optimalių maršrutų sudarymą ir informacinių paketų perdavimą tinkle. Maršruto sudarymas priklauso nuo tokių tikrų kriterijų kaip: trumpiausias atstumas, mažiausias mazgų skaičius, mažiausia kaina ir kt. Maršrutizavime dažniausiai naudojamos matricos, kuriose yra sukaupta maršrutų informacija. Matricų struktūra priklauso nuo pasirinkto maršrutizavimo metodo.

Maršrutizacija tinkluose pasireiškia tame, kad kur naudojami keli tinklų segmentai su skirtingais protokolais ir architektūromis, kartotuvas ar tiltas negalės sujungti tokių segmentų. Didesniems ir sudėtingesniems kompiuteriniams tinklams neužtenka žinoti galinio paskirties adreso, dar reikia nustatyti ir optimaliausią kelią duomenų siuntimui. Duomenys siunčiami iš vieno tinklo segmento į kitą gali pereiti daug segmentų, kurie gali būti labai apkrauti ir todėl reikia rasti geriausią kelią kaip perduoti duomenis greičiau. Įrenginys atliekantis šias funkcijas vadinamas maršrutizatoriumi. [8]

Maršrutizatoriai gali perjunginėti ir maršrutizuoti paketus skirtinguose kompiuteriniuose tinkluose. Maršrutizatorius kaip ir tiltas gali filtruoti ir izoliuoti duomenų judėjimą, sujungti skirtingus kompiuterinių tinklų segmentus. Maršrutizatoriai naudojami sudėtingose sistemose todėl, kad jie užtikrina geresnį duomenų perdavimą ir nepraleidžia trukdžių. Maršrutizatoriai gali tarpusavyje dalintis informacija ir taip išvengti labiau apkrautų segmentų. [8]

Šiame darbe panaudota literatūra pagrinde yra paimta iš interneto svetainės www.citforum.ru, publikacijos CISCO Internetworking Technology Overview (informacinė – analitinė informacija), kurioje apžvelgiami pagrindiniai maršrutizavimo metodų tipai, pagrindiniai rodikliai, maršrutizavimo vystymo tikslai ir kita. Maršrutizavimo metodų pagrindai aprašyti remiantis rusiška literatūra (žr. Literatūros sąrašas 20psl.,[9]).

Įvadas
Maršrutizavimo lentelės užpildomos priklausomai pagal naudojamą maršrutizacijos metodą. Ryšiai “Galinis mazgas/Siųsti į” praneša maršrutizatoriui, kad reikalingas galinis mazgas gali būti pasiektas optimaliu maršrutu, siunčiant paketą į nustatytą maršrutizatorių, kuris apibūdinamas kaip “sekantis persiuntimas” kelyje į reikiamą galinį mazgą. Priimdamas atėjusį paketą maršrutizatorius patikrina galinio mazgo adresą ir stengiasi susieti tą adresą su sekančiu persiuntimu.

Maršrutizatoriai “bendrauja” vienas su kitu (ir turi savo maršrutizavimo lenteles) perduodant įvairius pranešimus. Vienas tokių pranešimų tipų yra “maršrutizavimo atnaujinimas”. Toks maršrutizavimo atnaujinimas dažniausiai pateikia visą maršrutinę lentelę ar jos dalį. Analizuodami atnaujintą maršrutizavimo informaciją, ateinančią iš visų maršrutizatorių, kiekvienas jų gali sudaryti detalų tinklo apkrovimo vaizdą. Šie pranešimai informuoja kitus maršrutizatorius apie siuntėjo kanalus. Kanalinė informacija taip pat gali būti naudojama pilnam vaizdui apie tinklo apkrovimą sudaryti. Tada, kai situacija tinkle yra aiški, maršrutizatoriai gali nustatyti optimalius maršrutus galinių taškų pasiekimui. [1]
Maršrutizavimo vystymasis
Maršrutizavimo vystymąsi įtakoja šie veiksniai: [1]
Optimalumas
Optimalumas charakterizuoja maršrutizavimo metodo sugebėjimą išrinkti geriausią maršrutą.
Paprastumas
Maršrutizavimas turi užtikrinti efektyvų darbą, minimaliom sąnaudom ir didesniu naudingumu.
Gyvybingumas ir stabilumas
Maršrutizavimo metodai turi funkcionuoti ir nenumatytais atvejais (esant aparatūros sutrikimams, padidėjus tinklo apkrovimui ar kitiems faktoriams). Geriausiais metodai yra tie, kurie yra išbandyti ir yra patikimi esant skirtingomis tinklo darbo sąlygomis.
Suderinamumas
Suderinamumas yra susitarimų procesas tarp visų maršrutizatorių dėl optimalių maršrutų. Maršrutizavimo metodai, kurie lėtai susiderina vienas su kitu gali sudaryti maršrutizavimo kilpas ir gali sutrukdyti tinklo veiklą.
Pvz.: šiuo atveju, momentu t1 į pirmą maršrutizatorių ateina paketas. Maršrutizatoriuje 1 buvo atnaujinta informacija- jis žino, kad optimalus maršrutas į galinį tašką turi eiti per maršrutizatorių 2.

2 paveikslas. Maršrutizavimo kilpa

Todėl maršrutizatorius 1 pasiunčia paketą į maršrutizatorių 2. Maršrutizatorius 2 dar nebuvo informuotas, todėl jis mano, kad kitas optimalus siuntimas turi būti per maršrutizatorių 1. Todėl jis grąžina paketą maršrutizatoriui 1. Paketas bus siuntinėjamas pirmyn atgal tol, kol maršrutizatorius 2 negaus informacijos apie maršruto korekciją arba tol, kol paketo komutavimo skaičius neviršys maksimaliai leistino.

Lankstumas ir adaptacija
Lankstumas reiškia metodų sugebėjimą adaptuotis prie įvairių tinklo aplinkybių. Jeigu vieno kurio nors tinklo segmento darbas sutrinka, tai daugelis maršutizavimo metodų, sužinoję apie šį įvykį, išrenka kitą optimaliausią maršrutą. Kai kurie maršrutizavimo metodai gali adaptuotis prie tinklo pakeitimų, eilių susidarymo ir kt.
Maršrutizavimo metodų tipai
Maršrutizavimo metodai gali būti tokių tipų:
1. Statiniai, dinaminiai
2. Vieno maršruto, keleto maršrutų
3. Vieno lygio, hierarchiniai [1]
Statiniai, dinaminiai metodai
Statiniai maršrutizavimo metodai pagrįsti statinių maršrutizavimo lentelių sudarymu, kurias sudaro tinklo administratorius iš anksto. Šis maršrutizavimas nesikeičia, jei tinklo administratorius jo nepakeičia. Metodai, naudojantys statinius maršrutus labai yra paprasti. Kadangi statinės maršrutizavimo sistemos negali reaguoti į tinklo pakitimus, todėl jos yra netinkamos dideliems, intensyviems tinklams.

Dabar naudojami dažniausiai yra dinaminiai metodai. Dinaminiai maršrutizavimo metodai prisitaiko prie kintančios tinklo būklės. Tai atliekama analizuojant ateinančius pranešimus apie maršrutizavimo atnaujinimą. Jei pranešime yra įrašas apie tinklo pakitimus, tai maršrutizavimo programos perskaičiuoja maršrutus ir pasiunčia naujus pranešimus apie maršrutizavimo korekciją. Tokie pranešimai keliauja po visą tinklą ir priverčia maršrutizatorius pakeisti maršrutizavimo lenteles.
Vieno maršruto, keleto maršrutų metodai
Kai kurie maršrutizavimo metodai užtikrina daugelį maršrutų iki to pačio taško. Tokie keleto maršrutų metodai užtikrina multipleksinį trafiko perdavimą daugeliu linijų, vieno maršruto metodai to neatlieka. Taigi keleto maršrutų metodų privalumai: jie gali užtikrinti daug didesnį pralaidumą ir patikimumą.
Vieno lygio, hierarchiniai
Vieni maršrutizavimo metodai dirba viename lygyje, kiti – yra hierarchiniai. Vieno lygio sistemoje visi maršrutizatoriai yra lygūs. Hierarchinėje sistemoje kai kurie maršrutizatoriai formuoja tai, kas kitiems maršrutizatoriams yra maršrutizavimo pagrindas (backbone-bazė). Paketai iš nebazinių maršrutizatorių pereina į bazinius maršrutizatorius ir per juos yra perleidžiami tol, kol pasiekia bendros srities paskyrimo punktą. Nuo šio momento jie pereina iš paskutinio bazinio maršrutizatoriaus į vieną ar kelis nebazinius ir pasiekia savo numatytą maršruto pabaigą.

Maršrutizavimo sistemos dažnai nustato logines mazgų grupes, vadinamas domenais arba autonominėmis sistemomis (AS). Hierarchinėse sistemose vieni kokio nors domeno maršrutizatoriai gali susisiekti su kitų domenų maršrutizatoriais, tuo metu kai kiti to paties domeno maršrutizatoriai palaiko ryšį tik su savo domeno maršrutizatoriais. Labai dideliuose tinkluose gali būti papildomi hierarchiniai lygiai. Aukščiausio hierarchinio lygio maršrutizatoriai sudaro maršrutizavimo bazę.

Maršrutizavimo metodų rodikliai
Maršrutizavimo lentelėse yra saugoma informacija, kurią naudoja komutatoriai, turėdami išrinkti geriausią maršrutą. Maršrutizavimo metoduose naudojama daug skirtingų kriterijų. Sudėtingi maršrutizavimo metodai, rinkdami maršrutą, gali remtis daugeliu kriterijų.

Kriterijai naudojami maršrutizavimo metoduose:
Maršruto ilgis
Maršruto ilgis yra bene pagrindinis maršrutizavimo kriterijus. Dažniausiai maršruto ilgis yra suma išlaidų, susijusių su kiekvienu kanalu. Kai kurie maršrutizavimo protokolai numato persiuntimų kiekį, charakterizuojantį perėjimus, kuriuos paketas turi atlikti eidamas nuo šaltinio iki imtuvo per tinklo įrenginius.
Patikimumas
Patikimumas, tai kiekvieno kanalo patikimumas (jis dažniausiai apibūdinamas santykiu bitų skaičius/klaidų skaičius).
Užtrukimas
Užtrukimu dažniausiai vadinamas laiko tarpas, būtinas paketo judėjimui tinkle nuo šaltinio iki imtuvo. Užtrukimas priklauso nuo eilės faktorių, taip pat įskaitant kanalų pralaidumo juostos plotį, eiles prie kiekvieno maršrutizatoriaus, tinklo perkrovimą ar kt.
Pralaidumo juosta
Pralaidumo juosta yra bet kokio kanalo sugebėjimas praleisti tam tikrą trafiko kiekį.
Maršrutizavimo metodai
Dinaminio valdymo metodams priskiriami tokie metodai, kai maršrutas yra keičiamas priklausomai nuo realiu laiku esančios situacijos tinkle. Atnaujinant maršrutizavimo lenteles, reikia perduoti ir daug tarnybinės informacijos. Tai gali sukelti perkrovimus tinkle.

Pagrindiniai dinaminio valdymo metodai yra šie:
Banginis metodas
Banginis metodas priklauso dinaminio valdymo metodams. Banginis metodas naudojamas tada, kai reikia labai greitai atlikti sujungimą. Šis metodas palyginus su kitais maršrutizavimo metodais užima labai daug tinklo resursų, bet jo sujungimo greitis maksimalus. Atėjus paraiškai dėl sujungimo iš mazgo Ki į mazgą Kj, mazge Ki formuojama ieškančioji signalų banga į Kj ir ji išsiunčiama į visus kaimyninius Ki mazgus. Kiekviename mazge yra suvykdomas vienetinis ieškančiosios bangos užlaikymas, po jo banga siunčiama toliau. Pavyzdžiui, 1 schemoje (a) rodomas bangos išsisklaidymas nuo KA iki KE. Apibrėžkime PE(t0) – pradinį momentą (paleidimo) ieškančiosios signalų bangos PE, o i-tąjį momentą – signalų bangos PE praėjimą per PE(ti). KE atminties įrenginyje fiksuojamas tik tas signalas PE, kuris atėjo greičiau už kitus. Tuo atveju, kai tuo pat metu ateina keli PE signalai iš kelių krypčių, yra užfiksuojama tik vienas. Paskirties taške Kj gavus ieškančiosios bangos signalą, tame mazge formuojama atsakomoji signalų banga, kuri taip pat vienu taktu yra užlaikoma kiekviename mazge ir yra transliuojama visiems mazgams. Ši banga yra naudojama kelio ženklinimui tarp įeinančio ir išeinančio mazgų ir jai praėjus yra nutraukiamas ieškančiosios bangos siuntimas. Pradinis momentas (paleidimas) atsakomosios signalų bangos AE sutampa su pirmo ieškančiosios bangos signalo atėjimo momentu į KE (šiuo atveju tas momentas yra t2). [9]

Atsakomosios bangos praėjimo procesas mūsų pavyzdžiui yra pavaizduotas 1 schemoje ( b). Kai išsiuntęs K gauna atsakomosios bangos signalą, yra formuojama galutinė signalų banga. Jos siuntimo procesas yra analogiškas ieškančiosios ir atsakomosios bangų siuntimo procesams (tai pateikta 1 schemoje (c)).

Galutinė signalų banga atlieka dvi funkcijas:
1. Užtikrina sujungimo sudarymą tarp Ki ir Kj trumpiausiu keliu.
2. Sklinda link tinklo mazgų K, nedalyvaujančių šiame sujungime ir ištrina tokių mazgų atminties įrenginių informaciją, skirtą šio šaukimo įeinančio mazgo paieškai.

Reikia paminėti, kad kai kuriais atvejais šias funkcijas gali atlikti ir atsakančioji banga.

Esant šiam metodui, be būtinumo perduoti didelį kiekį tarnybinės informacijos (tai yra papildoma mazgų valdymo įrenginių apkrova) – kas yra visų vienkartinių metodų trūkumas, mazgų atminties įrenginiuose turi būti saugomas didelis kiekis informacijos: galinio mazgo numeris, bangos tipas (ieškančioji, atsakomoji, galutinė), išeinančiojo mazgo numeris ir kitos charakteristikos.

1 schema. Banginio metodo pavyzdys

Matricinis metodas
Dinaminio valdymo matricinis metodas paremtas informacijos maršrutizavimu pagal tam tikrą kriterijų. Kriterijais gali būti atstumas iki mazgo lij, talpa Vij (kanalų skaičius), pralaidumas Cij, kaina Kij. Matricinis metodas remiasi tuo, kad čia reikia sudaryti matricas. Tarkime turime tinklą ir, įvertinę jo mazgus siejančius ryšius pagal tam tikrą kriterijų, gausime mus dominančius duomenis (trumpiausią atstumą, mažiausią kainą ir t.t.). Tinklo mazgų įvertinimas parodo, kiek yra ryšių, taip pat galime sudaryti visus galimus maršrutus. Sudarykime reikalingas matricas tinklui pateiktam 2 schemoje. [9]

2 schema. Matricinio metodo pavyzdys

Mazgai sujungiami tiesėmis. Jei tiesė yra su rodykle, tai vadinasi ryšys yra vienpusis (tokios tiesės yra orientuotos). Dvipusis ryšys būna tada, kai kraštinė būna be rodyklės (neorientuotos tiesės). Jei tinkle nėra orientuotų tiesių, tai gausime simetrinę matricą.

Pirmiausiai turime turėti sąryšio matricą Aij – tarp kurių mazgų yra sujungimai, tarp kurių nėra (kur yra ryšys rašome 1, o kur ryšio nėra – 0).

Dauginant matricą B iš jos pačios gausime matricą B pakeltą tam tikru laipsniu. Matrica B2 parodo visus maršrutus tarp bet kurių dviejų taškų. Jei pakelsime kubu, parodys visus galimus 1, 2, 3 rangų maršrutus. Taip toliau sudarinėdami matricas galime surasti visus maršrutus tarp bet kokio skaičiaus mazgų. Bet iš to išplaukia matricinio metodo trūkumas – turint didelį tinklą reikia sudaryti labai daug matricų, o tai yra sudėtinga operacija. Be to, didelis matricų kiekis sudaro galimybę atsirasti klaidos tikimybei ir ilgai užtrunka matricų sudarymas (laiko resursai yra dideli).

Norint surasti visus galimus maršrutus iš vieno mazgo į visus kitus mazgus, yra sudaromas maršrutų grafas.

3 schema. Maršrutų grafas

Mazgų numeriai šakoje negali kartotis. Taigi, kaip matome, iš 1 mazgo į 4 mazgą galima patekti net šešiais maršrutais. Jeigu mus domino mažiausias tarpinių mazgų skaičius, tai iš 1 į 4 mazgą mažiausiai tarpinių mazgų turintys maršrutai yra ad ir bh.

Matricą L keliame kvadratu. Matrica L2D pavaizduoja ryšį tarp dviejų mazgų. Matricas keliam tol, kol elementai keičiasi. Jei užsiduotas skaičiumi kriterijus bus atstumas tai gausime minimalų atstumą, jei kaina – minimali kaina.

Reljefų metodas
Reljefų metodas priskiriamas prie dinaminio valdymo maršrutizavimo metodų. Šis metodas pagal iš anksto nustatytą kriterijų išrenka kryptį. Kriterijais gali būti: minimalus atstumas, minimalus tinklo atkarpų (mazgų) skaičius, minimali kaina. Bet šiuo atveju maršruto išrinkimo kriterijumi yra minimalus kelio atstumas kaip ir matriciniame metode. Ryšio tinkle, kur dinaminis valdymas yra atliekamas reljefų metodu, turi būti atliekamos sekančios operacijos: reljefo formavimas ir jo korekcija. Pirmoji operacija yra atliekama pradiniu momentu (tinklo paleidimo momentu), o taip pat tinklo vystymosi metu, t.y. įvedant į tinklą naujus mazgus K. Kita operacija atliekama periodiškai tinklo funkcionavimo procese arba atsiradus tinklo pažeidimams ar tinklo perkrovai. [9]
Tinklo paleidimo momentu jo reljefo formavimas prasideda nuo bet kokio mazgo Ka (a=1, 2, …, N, kur N – mazgų tinkle skaičius), kuris yra iniciatorius. Taigi šiuo atveju sakoma, kad prasideda a-reljefo sudarymas. Kiekvieno mazgo K atminties įrenginiuose išskiriamas tam tikras atminties dydis N*Mi (kur Mi – išeinančių iš mazgo Ki krypčių skaičius), kuriame bus patalpinta reljefų matrica Ri.

Formuojant reljefą iš mazgo K (iniciatoriaus) į visas iš jo išeinančias kryptis paduodamas 1 (vienetukas). Šis vienetukas kaimyniniuose su iniciatorium K mazguose yra įrašomas į matricą Ri su koordinatėmis (n,m1), kur n – iniciatoriaus K numeris, o m1 – numeris šakos, kuria atėjo tas vienetukas.

Paimkime pavyzdžiu tinklą pavaizduotą 5 schemoje (a). Tarkime, kad kiekviename mazge K yra išskirta atminties dalis matricos R suformavimui (5 schema (b)) ir tegul mazgu iniciatoriumi yra KA mazgas. Šiuo atveju vienetukas bus įrašytas į matricas RB ir RC.
Toliau reljefo kūrimas vyksta sekančiu būdu. Visi mazgai K, į kuriuos atėjo vienetukas, visomis išėjimo kryptimis (išskyrus tą kryptį, kuria atėjo vienetukas) perduoda skaičių 2. Šis skaičius visuose mazguose į kuriuos jis atėjo įrašomas į matricą Ri su koordinatėmis (n, m2), kur m2 – šakos numeris, kuria atėjo dvejetukas. Nagrinėjamu atveju skaičius 2 bus įrašytas į matricas RB, RC, RD, RE ir RF.

Dabar mazgai K, į kuriuos atėjo skaičius 2, perduoda į išėjimus skaičių 3 ir t.t. Bet reikia laikytis šių taisyklių:

1. Jei į K atėjo vienodas skaičius iš dviejų ar daugiau krypčių, tai tas mazgas inicijuoja vienetu didesnio skaičiaus nei atėjo perdavimą į visas kryptis. Pavyzdžiui į KE atėjo skaičius 2 iš KB ir KC. Šiuo atveju skaičius 3 iš KE yra perduodamas į visas kryptis.
2. Jei į K ateina skaičius viena kryptimi, tai tame mazge yra inicializuojamas vienetu didesnio skaičiaus perdavimas į visas kryptis išskyrus tą, kuria atėjo skaičius. Skaičiaus perdavimas ta kryptimi galimas tik tada, kai į mazgą K ateina sekantis skaičius. Skaičius perduodamas ta kryptimi turi būti vienetu didesnis už skaičių kuris atėjo antras. Pavyzdžiui., skaičius 2 atėjo į mazgą KD iš KB. Tada skaičius 3 iš KD turi būti perduodama į visas kryptis išskyrus KB. Šia kryptimi bus perduotas skaičius 4, kadangi sekantis atėjęs į KD skaičius yra 3.
3. Skaičių perdavimo visomis kryptimis į visus mazgus K inicializavimas įvyksta vieną kartą po pirmo skaičiaus atėjimo. Pavyzdžiui, perdavus skaičių 3 iš KC į KE, jis įrašomas į matricą RC pagal atitinkamas koordinates, o kito skaičiaus perdavimo inicializacija nevyksta, kadangi anksčiau jau buvo perduotas skaičius 2.

Tokiu būdu šiam pavyzdžiui bus suformuotas A-reljefas. Analogišku principu yra sukuriami reljefai ir visiems likusiems tinklo mazgams. Tinklo reljefas laikomas baigtu, jei yra suformuoti visi a-reljefai (a=1, 2, …, N). Optimalaus kelio nustatymas sujungime nuo Ki iki Kj yra mazge Ki.
Reljefų metodas turi trūkumų, kadangi čia gali būti naudojami maršrutai su apeinamaisiais keliais, tai gali atsirasti taip vadinamų “kilpų”, t.y. kai sujungimas du kartus praeina per tą patį mazgą. Tuo šis metodas skiriasi nuo anksčiau minėto banginio metodo. Reikia stengtis išvengti kilpų. Vienas tokių būdų yra tas, kad tinklo maršrutizavimo metu pranešimas įsimena mazgų K numerius, per kuriuos jis praėjo, kad nereikėtų jų pereiti antrą kartą. Tuo būdu sujungimai tinkle turi būti nustatomi remiantis suformuotomis matricomis be kilpų. Būtina pažymėti, kad, kadangi situacija tinkle vis kinta ( vienos kryptys yra perkraunamos, o apkrova kitose labai sumažėja, be to ryšio kanalai gali sugesti, taip pat gali sugesti mazgai arba atitinkamos ryšių kryptys), atsiranda būtinybė koreguoti tinklo reljefą.
MARŠRUTIZATORIAI (ROUTER)
Maršrutizatoriai sudaro maršruto lentelę ir ją naudoja perduodant duomenis. Jei yra sujungti keli maršrutizatoriai tai yra nustatomas trumpiausias ir greičiausias duomenų perdavimo kelias. Šitą kelia aptikti naudoja OSPF (open shortest path first), RIP (routing information protocol), NLSP (NetWare link services protocol) algoritmų pagalba. [8]

Statinis maršrutizatorius reikalauja administratoriaus rankinio nustatymo ir maršrutų lentelės. Dinaminis pats automatiškai nustato maršrutų lenteles.

BROUTER’IAI
Brouteris tai tas pats maršrutizatorius tik kartu atliekantis tilto ir maršrutizatoriaus funkcijas, tai yra jis gali dirbti su protokolais, su kuriais negali dirbti paprastas maršrutizatorius.
Maršrutizacijos protokolai
Tinkliniai protokolai naudoja savo darbe maršrutizacijos lentelę, bet jie jos nesudarinėja, neužsiima palaikymu jų turinio. Tas funkcijas atlieka maršrutizacijos protokolai. Tų protokolų pagrindų maršrutizatoriai apsikeitinėja tinklo topologijos informacija, o po to analizuoja gautas žinias, nustato geriausią pagal viena arba kitą kriterijų maršrutą. Analizės rezultatai ir sudaro maršrutizacijos lentelės turinį.
RIP
Maršrutizacijos Informacijos Protokolas (RIP) yra maršrutizacijos protokolas, kuris buvo pirmą kartą sukurtas universaliam protokolui PARC Xerox (kur jis vadinosi GWINFO) ir buvo naudojamas ХNS protokolų komplekte. RIP 1982 metais pradėjo jungtis kaip su UNIX, taip ir su TCP/IP, kada UNIX versija, vadinamąja Berkeley Standard Distribution (BSD), pradėjo leisti viena iš RIP realizacijų, kurią vadino „maršrutizuojama” (routed). RIP Protokolas, kuris vis dar yra labai populiarus maršrutizacijos protokolas Internete, formaliai apibrėžtas publikacijoje XNS ” Interneto perdavimo protokolai ” (XNS Internet Transport Protocols) (1981 m.) ir užklausose komentarams (Request for Comments – RFC) 1058 (1988 m.). [2]

RIP buvo plačiai priimtas personalinių kompiuterių gamintojų (РС) panaudojant jų gaminiuose duomenų perdavimui per tinklą. Pavyzdžiui, maršrutizacijos protokolas AppleTalk (protokolas maršrutizacijos lentelės- RTMP palaikymui) yra RIP modernizuota versija. RIP tapo protokolų Novell, 3Com, Ungermann-Bass ir Banyan baze. Kompanijų Novell ir 3Com RIP pagrinde sudaro kompanijos Xerox standartinį RIP. Kompanijos Ungermann-Bass ir Banyan įvedė nežymius RIP pakeitimus siekdamos patenkinti savo poreikius.

Kiekviename atskirame RIP pakete gali būti išvardinta iki 25 pristatymo punktų. Informacijos perdavimui iš didesnių maršrutinių lentelių naudojama daugybė RIP paketų.

RIP nustato eilę charakteristikų, skirtų didesniam darbo stabilumui, kai greitai kinta tinklo topologija. Tai nulemia persiuntimų skaičiaus ribojimas, laikinas pakeitimų sulaikymas (hold-downs), išskaidyti lygmenys (split-horizons) ir pakeitimų koregavimas (poison reverse updates).

RIP leidžia maksimalų persiuntimų skaičių, lygų 15. Bet kokiam pristatymo punktui, kuris randasi toliau, negu per 15 persiuntimų atstumą, prisegama etiketė „nepasiekiamojo”. Maksimalus RIP persiuntimų skaičius žymiai apriboja jo pritaikymą dideliuose jungtiniuose tinkluose, vienok tai padeda išvengti problemos, vadinamos skaičiavimu iki begalybės (count to infinity), privedančios prie maršrutų užsiciklinimo tinkle.
IGRP
Vidinių routerių maršrutizacijos protokolas (Interior Gateway Routing Protokol-IGRP) yra maršrutizacijos protokolas, sukurtas kompanijos Cisco Systems, Inc 1980 metų viduryje. Pagrindinis tikslas, kurio siekė Cisco kurdama IGRP, buvo užtikrinti maršrutizacijos protokolo gyvybingumą autonominės sistemos (AS)srityje, turint bet kokią sudėtingą topologiją ir įskaitant įvairius informacijos charakteristikų nešėjų juostos pločius ir užvėlinimus. AS yra tinklų grupė, turinti bendrą valdymą ir naudoja bendrą maršrutizacijos strategiją. Paprastai AS priskiriamas unikalus 16-bitų numeris. [3]

1980 metų viduryje pats populiariausias maršrutizacijos protokolas AS viduje buvo Maršrutizacijos Informacijos Protokolas (RIP). Nors RIP buvo visai naudingas maršrutizacijai palyginti nedidelio arba vidutinio dydžio bendrosiose tinkluose, jo apribojimas sulaikė tinklų plėtimąsi. Jų tarpe, leidžiamas nedidelis persiuntimų skaičius (15) RIP apribojo bendrojo tinklo dydį, o jo vienintelis rodiklis (persiuntimų skaičius) neužtikrino pakankamo lankstumo sudėtingose sistemose (žiūrėti „RIP”). Cisco routerių populiarumas ir IGRP gyvybingumas paskatino daugelį organizacijų, kurios turėjo didelius bendruosius tinklus, pakeisti RIP į IGRP.

Pirmoji kompanijos Cisco IGRP realizacija veikė IP tinkluose. Kadangi IGPR buvo skirtas bet kokiam tinklui, tai greitai Cisco jo naudojimą perkėlė į tinklus, naudojančius protokolus be sujungimo (Connectionless Network Protocol – CLNP) OSI.

IGRP yra vidinių routerių (IGP) protokolas su nuotolio vektoriumi. Maršrutizacijos protokolai su nuotolio vektoriumi reikalauja iš kiekvieno routerio per tam tikrus laiko intervalus siųsti visiems routeriams visą arba dalį savo maršrutinės lentelės ir pranešimus apie maršrutų koregavimą. Pagal tai, kaip maršrutinė informacija platinama tinkle, routeriai gali apskaičiuoti atstumą iki visų bendrojo tinklo mazgų.

IGRP savo rodikliams numato platų reikšmių diapazoną. Pavyzdžiui, patikimumas ir apkrova gali įgauti bet kokia reikšmę intervale nuo 1 iki 255, juostos plotis gali įgauti reikšmę, pralaidumo greitį nuo 1200 iki 10 Gbitų per sekundę, tuo tarpu sulaikymas gali įgyti bet kokią reikšmę nuo 1-2 iki 24-tosios eilės. Platus rodiklių reikšmių diapazonas leidžia realizuoti patenkinamą rodiklio reguliavimą jungtiniame tinkle su dideliu našumo reguliavimo diapazonu. Svarbiausia yra tai, kad rodiklių komponentai sprendžiami algoritmu, kurį nustato vartotojas. Todėl tinklo administratoriai gali daryti įtaką maršruto parinkimui, remdamiesi savo intuicija.

Papildomam lankstumui IGRP leidžia daugiatraktę maršrutizaciją. Dubliavimas vienodo juostos pločio linijų gali praleisti atskirą srautą apkrovos cikliniu būdu su automatiniu perjungimu į antrą liniją, jeigu pirma linija sugenda. Keletą traktų taip pat gali būti naudojami net tuo atveju, jeigu tų traktų rodikliai skirtingi. Pavyzdžiui, jeigu vienas traktas trys kartus geresnis už kitą dėka to, kad jo rodikliai trys kartus žemesni, tai geresnis traktas bus trys kart dažniau naudojamas. Tik maršrutai su rodikliais, kurie yra nustatyto diapazono geriausių maršrutų rodiklių ribose, naudojami daugiatraktei maršrutizacijai.

IGRP turi eile charakteristikų, skirtų savo stabilumo pagerinimui. Į jų skaičių įeina pakeitimų laikinas sulaikymas , išskaidyti lygiai ir pakeitimų koregavimas.

Laikinas pakeitimų sulaikymas naudojamas tam, kad sutrukdyti pranešimų koregavimą, neteisingai atstatyti maršruto teises, kuris pasirodė sugadintas. Kada koks nors routeris išeina iš rikiuotės, kaimyniniai routeriai tai aptinka kaip trūkumą užplanuotų reguliarių pranešimų. Toliau routeriai perskaičiuoja naujus maršrutus ir siunčia pranešimus apie maršrutizacijos atnaujinimą, kad informuoti savo kaimynus apie pakeitimus maršrute. Rezultatas šios veiklos yra paleidimas visos korekcijos bangos, kuri filtruojama per tinklą.

OSPF
Atviras protokolas, pagrįstas trumpiausio kelio paieškos algoritmu (Open Shortest Path Fisrt – OSPF) yra maršrutizacijos protokolas, sukurtas IP tinklui Internet Engineering Task Force (IETF) darbo grupės, užsiimančios protokolų kūrimu vidiniams routeriams (interior gateway protocol – IGP). Darbo grupė buvo sudaryta 1988 metais IGP protokolo kūrimui, kurio algoritmas pagrįstas ” trumpiausio kelio paieška ” (shortest path first – SPF), o jo tikslas panaudojimas Internete, dideliame tarptautiniame tinkle, jungiančiame mokslinio tyrimo institutus, valdžios įstaigas, universitetus ir nuosavas įmones. Kaip ir protokolas IGRP, OSPF buvo sukurtas todėl, kad 1980 metų viduryje išryškėjo RIP netinkamumas aptarnaujant dideles jungtines sistemas. [4]

ОSPF yra keleto sričių mokslinių tyrimų rezultatas, įskaitant:

• Kompanijos Bolt algoritmas SPF, Beranek ir Newman (BBN), sukurto Arpanet (paketų komutacijos programos, sukurtos 1970 pradžioje metų BBN, kuri buvo posūkio punktu tinklų kūrimo istorijoje) 1978 metais.
• Kompanijos Radia Perlman tyrimai maršrutinės informacijos, plataus siuntimo, patikimumo (1988).

Kaip matome iš jo pavadinimo, OSPF turi dvi pagrindines charakteristikas. Pirma iš jų, tai kad protokolas yra atviras, tai jo specifikacija yra visuomeninis turtas. OSPF specifikacija paskelbta užklausos komentarų (RFC) 1247 formoje. Antra pagrindinė charakteristika yra ta, kad jis pagrįstas SPF algoritmu. Algoritmas SPF kai kada vadinamas algoritmu Dijkstra pagal autoriaus vardą

OSPF yra maršrutizacijos protokolas praneša kanalo būseną (link-state). Tai reiškia, kad jis reikalauja siųsti pranešimus apie kanalų būseną (link-state advertisement – LSA) į visus routerius, kurie yra vienos ir tos pačios hierarchinės srities ribose. OSPF protokolo pranešime įtraukiama informacija apie prijungtus interfeisus, apie naudojamus rodiklius ir kitus kintamuosius. Priklausomai nuo OSPF informacijos sukauptos routeriuose apie kanalo būseną, jie naudoja SPF algoritmą kiekvieno mazgo trumpiausio kelio apskaičiavimui.

OSPF kaip algoritmas pranešimų apie kanalo būseną, skiriasi nuo RIP ir IGRP, kurie yra maršrutizacijos protokolai su atstumo vektoriumi. Routeriai, naudojantys atstumo vektoriaus algoritmą, siunčia visa arba dalį savo maršrutizacijos lentelės ir pranešimą apie maršrutizacijos koregavimą tik savo kaimynams.

OSRF papildomų charakteristikų tarpe – lygios išlaidos, daugiatraktė maršrutizacija (multipath routing) ir aukštesnio lygio maršrutizacija, remiasi į paslaugų tipo užklausas (type of service – TOS). TOS maršrutizacija palaiko tuos aukštesnio lygio protokolus, kurie gali skirti konkretu paslaugų tipą. Pavyzdžiui, kokia nors papildoma programa gali įvesti reikalavimus apie tai, kad nustatyta informacija yra skubi. Jeigu OSPF savo paskirstyme turi aukščiausių prioritetų kanalus, tai jie gali būti panaudoti skubių duomenų transportavimui.
EGP
Išorinių routerių protokolas (Exterior Gateway Protocol-EGP) yra tarpdomeninio pasiekiamumo protokolas, kuris pritaikomas Internete – tarptautiniame tinkle, jungiančiame universitetus, valstybines įstaigas, mokslinio tyrimo organizacijos ir privačius vartotojus. EGP dokumentaliai aprašytas komentarų užklausose (RFC) 904, pristatytas balandžio mėnesį 1984 metais. [5]

Yra pirmasis išorinių routerių protokolas, kuris buvo plačiai taikomas Internete. Tačiau, EGP trukumai išryškėjo dar labiau po to, kai Internetas plėtėsi labai dideliu mąstu. Dėl tų trukumų EGP dabartiniu metu netenkina visų interneto reikalavimų ir pakeičiamas kitais išorinių routerių protokolais, tokiais, kaip Protokolas ribinių routerių (Border Gateway Protocol – BGP) ir Protokolas tarpdomeninės maršrutizacijos (Inter-Domain Routing Protocol – IDRP) (žiūrėti 27 „BGP” ir skyrių 28 „Maršrutizacija OSI”).

Nežiūrint į tai, kad EGP yra dinaminis maršrutizacijos protokolas, jis naudoja labai paprastą schemą. Jis nenaudoja rodiklių, ir vadinasi, negali priėminėti intelektualius maršrutizacijos sprendimus. Maršrutizacijos koregavime EGP laiko tinklų pasiekiamumo informaciją. T.y. jie nurodo, kad tam tikri nustatyti keliai eina per tam tikrus nustatytus routerius.

EGP turi tris pagrindines funkcijas.
Routeriai, dirbantys su EGP, nusistato sau norimą skaičių kaimynų. Kaimynai – tai paprastai kiti routeriai, su kuriais koks nors routeris nori kolektyviai naudotis tinklų pasiekiamumo informacija.
Routeriai EGP apklausia savo kaimynus tam, kad įsitikintų apie jų darbingumą.
Routeriai EGP siunčia pranešimus apie korekciją savo AS ribose.
BGP
Ribinių routerių protokolas (Border Gateway Protocol – BGP) yra bandymas spręsti pačią svarbiausi problemą EGP. BGP yra maršrutizacijos protokolas tarp AS, sukurtas pritaikymui Internete. Skirtingai nuo EGP, BGP skirtas aptikti maršrutines kilpas. BGP galima pavadinti sekančia EGP karta. Ir iš tikrųjų, BGP ir kiti maršrutizacijos protokolai tarp AS pamažu išstumia EGP iš Interneto. [6]

Nors BGP sukurtas kaip maršrutizacijos protokolas tarp AS, jis gali būti naudojamas maršrutizacijai, kaip ribose, taip ir tarp AS. Du kaimynai BGP, susisiekiantys iš skirtingų AS, turi būti vienam ir tam pačiam fiziniame tinkle. BGP routeriai, esantys ribose vienos ir tos pačios AS, susisiekia vienas su kitu, ir kad užtikrinti suderinamumą su duota AS yra nustatoma, koks iš BGP routerių duotos AS tarnaus.

Pranešimai apie BGP korekciją susideda iš poros „tinklinis numeris/traktas AS”. Traktas AS laiko nuoseklumą iš AS, per kuriuos gali būti pasiektas nustatytas tinklas. Šie pranešimai apie koregavimą siunčiami TCP transportavimo mechanizmo pagalba užtikrinant pristatymo patikimumą.

Tarp dviejų routerių apsikeitimas pradine informacija yra laikymas visos BGP maršrutinės lentelės. Pasikeičiant maršrutinei lentelei siunčiamos inkrementuotos korekcijos koregavimas. Skirtingai nuo kai kurių kitų maršrutizacijos protokolų BGP nereikalauja periodinio atnaujinimo visos maršrutinės lentelės. Vietoj to BGP routeriai saugo naujausia maršrutinės lentelės versiją kiekvieno lygiateisio nario. Nors BGP palaiko maršrutinę lentelę visų galimų traktų kokio nors konkretaus tinklo, savo pranešimuose apie koregavimą jis praneša tik apie pagrindinius (optimalius) maršrutus.

BGP rodiklis parodo bet kokį vienetų skaičių, charakterizuojantį pirmenybės laipsnį kokio nors konkretaus maršruto. Tie rodikliai paprastai nustatomi tinklo administratoriaus remiantis konfigūraciniais failais. Pirmenybės laipsnis gali remtis į bet kokį skaičių kriterijų, įskaitant AS kiekį (traktai su mažiau AS geresni), taip pat kanalo tipą (stabilumas, greitaeigiškumas ir kanalo patikimumas) ir kitus faktorius.
OSI maršrutizacija
Paremiant tarptautiniai standartų organizacijai (ISO) jau sukurti arba dabartiniu metu kuriami keletas maršrutizacijos protokolų. ISO remia Tarpinių Sistemų Vidaus domeninės Maršrutizacijos Apsikeitimo Protokolą (Intermediate System to Intermediate System Intra-Domain Routing Exchange Protocol (IS-IS)), taip pat ir ISO 10589. ISO standartizacijos varomoji dokumento IS-IS jėga buvo komitetas Х.3S3.3 Amerikos Nacionalinių Standartų Instituto (ANSI), užsiimantis tinkliniu ir transportiniu lygiu. [7]

ES-IS tai yra daugiau aptikimo protokolas, negu maršrutizacijos protokolas. Per ES-IS sistemos ES ir IS sužino vienos apie kitą. Šitas procesas žinomas, kaip konfigūracija (configuration). Tai kad konfigūracija turi pradžią prieš tai, kai gali prasidėti maršrutizacija tarp ES, protokolas ES-IS peržiurimas pirmoje eilėje.

Išvados
• Maršrutas – tai maršrutizatorių eiliškumas, kuriuos turi pereiti paketas nuo siuntėjo iki punkto paskirties. Maršruto pasirinkimo uždavinį iš kelių galimų, sprendžia maršrutizatorius ir galiniai mazgai dirbantys maršrutizacijos lentelių pagrindų.
• Maršrutizavimo metodai:
• Banginis – pats greičiausias sujungimas, tačiau reikia persiųsti labai daug tarnybinės informacijos, dėl to labai neracionaliai išnaudojami tinklo resursai. Turi būti saugoma didelis kiekis informacijos
• Matricinis – galima sudaryti visus galimus maršrutus. Maršrutizavimas vyksta pagal tam tikrą kriterijų, bet reikia turėti labai daug matricų. (Dideliuose tinkluose reikalinga galinga aparatūra). Negalima rasti maršruto per kuriuos mazgus eina duomenys.
• Reljefų – pagal iš anksto užduotą kriterijų nustatoma jungimo kryptis. Naudoja daug tinklo resursų, reikia sudaryti daug reljefinių matricų, kurias reikia talpinti atminties įrenginiuose. Galimi maršrutai su apeinamaisiais keliais, todėl gali atsirasti “maršrutizavimo kilpų”.
• Maršrutizacijos protokolai (pavyzdžiui, RIP arba OSPF) surenka ir perduoda tinklu grynai tarnybinę informaciją apie galimus maršrutus.
• Dideli tinklai skirstomi į autonomines sistemas, kuriose vedama bendroji maršrutizacijos politika IP – paketų.
• Maršrutizacijos protokolai skirstomi į išorinius ir vidinius. Išoriniai protokolai (EGP, BGP) perneša maršrutine informacija tarp autonominių sistemų, o vidiniai (RIP, OSPF) pritaikomi tik autonominės sistemos ribose.
• Protokolas RIP yra labiausiai išplitęs maršrutizacijos protokolas tinkluose TCP/IP. Nežiūrint į jo paprastumą, naudojant nustatytą distanciškai vektorinį algoritmą, RIP gerai dirba nedideliuose tinkluose, kuriuose yra nedaugiau kaip 15 tarpinių maršrutizatorių.
• Protokolas OSPF buvo sukurtas efektyviai IP paketų maršrutizacijai dideliuose tinkluose su sudėtinga topologija, įtraukiant kilpas. Jis dirba ryšio būsenos algoritmo pagrindu, kuris turi didelį patikimumą į tinklo topologijos pasikeitimus.
• Išrenkant maršrutą, OSPF maršrutizatoriai įvertina praleidžiamąja geba jungiamajame tinkle.
• Protokolas OSPF yra aukšto skaičiavimo sudėtingumo, dėl to dažnai jis dirba tik galinguose aparatūriniuose maršrutizatoriuose.

Literatūros sąrašas
1. http://www.citforum.ru/nets/ito/2.shtml
2. http://www.citforum.ru/nets/ito/23.shtml
3. http://www.citforum.ru/nets/ito/24.shtml
4. http://www.citforum.ru/nets/ito/25.shtml
5. http://www.citforum.ru/nets/ito/26.shtml
6. http://www.citforum.ru/nets/ito/27.shtml
7. http://www.citforum.ru/nets/ito/28.shtml
8. http://aura.el.vtu.lt/Diplomas/500/www505.htm
9. Лазарев ”Динамическое управление потоками информаций в сетях связи”, Москва, 1983

Atsisiųsti darbą moku.lt_marsrutizavimas