Rutare dinamica

Rutare dinamica

Rutare dinamica are loc atunci cānd router-ele discuta cu router-ele adiacente informāndu-se reciproc asupra retelelor la care este conectat fiecare dintre ele. Router-ele trebuie sa comunice folosind un protocol de rutare. Īntr-un sistem cum este Internetul sunt folosite diverse protocoale de rutare. Internetul este organizat sub forma unei colectii de sisteme autonome (Automonous System-AS), fiecare fiind administrat de catre o singura organizatie. De multe ori, o corporatie sau un campus universitar definesc un sistem autonom. De exemplu, backbone-ul NSFNET formeaza un sistem autonom, deoarece toate rutele din acest backbone se afla sub un control administrativ unic. Īn cadrul fiecarui sistem autonom poate fi selectat propriul protocol de rutare ce asigura comunicatia īntre router-ele din cadrul respectivului AS. Acesta este numit "interior gateway protocol" (IGP) sau "intradomain routing protocol". Cel mai popular IGP a fost "Routing Information Protocol" (RIP). Un protocol de tip IGP mai nou este "Open Shortest Path First" (OSPF). Acesta a fost dezvoltat cu intentia de a īnlocui protocolul RIP. Īn prezent, īn Internet sunt utilizate ambele protocoale īn functie de conditiile specifice ale fiecarui AS.

O alta categorie de protocoale de rutare este "Exterior Gateway Protocols" (EGP) sau "Interdomain Routing Protocol". Aceste protocoale sunt utilizate pentru comunicatia īntre router-e apartinānd unor AS-uri diferite. Din punct de vedere istoric, protocolul de tip EGP predominant a fost protocolul cu acelasi nume: EGP (lucru ce poate da nastere uneori la confuzii). Un protocol de tip EGP mai nou este "Border Gateway Protocol" (BGP) ce a fost dezvoltat cu intentia de a īnlocui EGP (lucru care s-a produs īn mare masura).

Succesul unei rutari dinamice depinde de 2 functii de baza ale unui router:

actualizarea tabelei de rutare,

distribuirea periodica a cunostintelor catre alte router-e sub forma informatiilor de rutare actualizate.

Rutarea dinamica se bazeaza pe un protocol de rutare īn vederea partajarii informatiilor īntre router-e. Un protocol de rutare defineste un set de reguli folosit de un router pentru a comunica cu router-ele vecine. De exemplu, un protocol de rutare descrie:

cum sa se transmita actualizarile,

ce informatie este continuta īn aceste actualizari,

cānd sa se transmita aceasta informatie,

cum sa fie localizati destinatarii actualizarilor.

Atunci cānd un algoritm de rutare actualizeaza o tabela de rutare, obiectivul principal este de a determina cea mai buna informatie ce trebuie inclusa īn tabela de rutare. Fiecare algoritm de rutare interpreteaza acest lucru īn mod propriu. Algoritmul genereaza un numar, numit metrica, pentru fiecare cale prin retea. De obicei, cu cāt valoarea metricei este mai mica cu atāt calea corespunzatoare este mai buna. Algoritmii de rutare folosesc diverse metrici īn vederea determinarii rutei optime. Algoritmii de rutare complecsi pot utiliza mai multe metrici īn vederea selectarii rutei optime, combinānd aceste metrici īntr-o metrica hibrida. Exemplu de metrici folosite:

lungimea caii (numarul de hop-uri),

fiabilitatea,

īntārzierea,

capacitatea de trafic,

īncarcarea,

costul comunicatiei.

Lungimea caii este metrica cea mai des folosita. Unii algoritmi de rutare permit administratorilor de retea sa asigneze costuri arbitrare fiecarei conexiuni din retea. Īn acest caz, lungimea caii este suma costurilor asociate fiecarei conexiuni ce este traversata. Alte protocoale de rutare definesc metrica "hop count" (numarul de hop-uri) ce specifica numarul de treceri prin echipamente de intreconectare de retele (cum ar fi router-ele) pe care un pachet trebuie sa le realizeze īn drumul sau de la sursa pāna la destinatie.

Fiabilitatea, īn contextul algoritmilor de rutare se refera la rata de biti eronati a fiecarei conexiuni de retea. Unele conexiuni pot avea īntreruperi mai des decāt altele. Dupa o īntrerupere a unei conexiuni, timpul de repunere īn functiune a acesteia poate fi mai mic decāt īn cazul altei conexiuni. Īn vederea asignarii valorii corespunzatoare fiabilitatii fiecarei conexiuni, pot fi luati īn calcul orice factori ce influenteaza fiabilitatea. Aceste valori sunt de tip numeric si sunt asignate de catre administratorii de retea.

Īntārzierea se refera la perioada de timp necesara pentru transferul unui pachet de la sursa la destinatie. Īntārzierea depinde de multi factori, incluzānd capacitatea de trafic a conexiunilor intremediare, cozile de asteptare la fiecare router prin care trec pachetele, congestia unor conexiuni intermediare si distanta fizica ce trebuie parcursa. Deoarece īntārzierea cumuleaza cāteva variabile importante, este o metrica foarte utilizata si utila.

O caracteristica a oricarei conexiuni o reprezinta capacitatea de trafic disponibila. Daca ceilalti factori sunt echivalenti, atunci o conexiune Ethernet de 10Mbps este de preferat unei conexiuni pe linie telefonica īnchiriata de 64Kbps. Desi capacitatea de trafic depinde de debitul maxim al unei conexiuni, rutele prin conexiuni cu capacitate de trafic mai mare nu sunt neaparat mai bune decāt rutele prin conexiuni mai lente. De exemplu, īn cazul īn care o conexiune mai rapida este foarte īncarcata, timpul necesar pentru transmiterea unui pachet prin acesta conexiune poate fi mai mare decāt īn cazul utilizarii unei conexiuni cu o capacitate de trafic mai mica, dar lipsita de īncarcare.

Īncarcarea reprezinta gradul de ocupare a unei resurse de retea (cum ar fi router-ul). Īncarcarea poate fi calculata īn diverse moduri, cum ar fi gradul de utilizare al CPU sau numarul de pachete prelucrate pe secunda. Monitorizarea continua a acestor parametrii poate duce ea īnsasi la cresterea īncarcarii.

Costul comunicatiei este o alta metrica importanta, īn special din cauza faptului ca unele companii acorda mai putina importanta performantelor decāt costurilor de operare. Cu toate ca īntārzierile pot fi mai mari, acestia prefera sa utilizeze propriile linii de comunicatii īn locul liniilor publice pentru care se plateste īn functie de durata utilizarii acestora.

Majoritatea algoritmilor de rutare pot fi īncadrati īntr-una din urmatoarele categorii:

"distance vector" (vector distanta),

"link state" (starea conexi 343r175d unii).

Algoritmii de rutare de tip "distance vector" determina directia (vectorul) si distanta catre oricare conexiune din retea. Algoritmii de tip "link state" (numiti de asemenea "shortest path first" - īntāi calea cea mai scurta) recreeaza topologia exacta a īntregii retele (sau cel putin a portiunii din retea īn care se afla situat router-ul).

Algoritmii de rutare hibrizi combina aspecte ale celor 2 tipuri de algoritmi mentionati anterior.

Algoritmul de rutare este fundamental pentru rutarea dinamica. De cāte ori o topologie a unei retele se modifica din cauza extinderii, reconfigurarii sau defectiunilor, baza de informatii referitoare la retea trebuie de asemenea modificata. Informatiile trebuie sa reflecte o proiectie clara si consistenta a noii topologii. Aceasta proiectie este numita convergenta. Cānd toate router-ele dintr-o retea opereaza cu aceeasi baza de informatii se spune ca reteaua este convergenta. O caracteristica dorita pentru orice retea o reprezinta convergenta rapida a acesteia, deoarece acesta reduce perioada de timp īn care router-ele ar putea lua decizii incorecte.

4.1 Protocoale de rutare de tip "distance vector"

Algoritmul fundamental bazat pe vectorul distanta īncearca sa rezolve problema alegerii caii catre o anumita destinatie folosind cel mai mic numar posibil de hop-uri. Se considera un hop orice trecere printr-un nod. Astfel, īn reteaua din exemplul de mai jos, distanta de la router-ul A la reteaua D este 3.

Figura 4.1 Distanta de la un router la destinatie

Problema devine mai interesanta īn cazul īn care reteaua nu se īntinde de-a lungul unei linii. De exemplu, distanta dintre router-ul A si reteaua D īn exemplul urmator de retea (fig. 4.2) poate fi 3, 4, 5 sau 6.

Figura 4.2 Calea cea mai scurta

Īn acest exemplu, calea care este de dorit a fi urmata este de la A la B apoi la C si apoi la D. Gasirea acestei cai este asigurata de algoritmii Bellman-Ford sau Dijkstra. Apoi, fiecare nod din retea va fi īnstiintat de calea cea mai scurta de la el īnsusi la fiecare din celelalte noduri ale retelei.

Exista mai multe moduri de abordare a problemei de gasire a celei mai scurte cai. O metoda utila de clasificare a acestor abordari este pe baza tipului de informatii necesare a fi schimbate īntre gateway-uri pentru ca acestea sa fie capabile sa gaseasca aceste rute. Algoritmii bazati pe vectorul distanta se bazeaza pe schimbul unei cantitati mici de informatii. Fiecare entitate (gateway sau host) care participa la acest protocol de rutare se presupune ca pastreaza informatii despre toate destinatiile din interiorul sistemului. Īn general, informatia despre toate destinatiile posibile dintr-o retea se rezuma la o singura intrare, care descrie ruta catre toate destinatiile din acea retea. Acest lucru este posibil deoarece atāt timp cāt rutarea se face la nivel IP, rutarea īn interiorul unei retele este invizibila. Fiecare linie (intrare) din tabela de rutare include gateway-ul urmator catre care datagramele destinate unei alte retele vor trebui trimise. Īn plus, mai este trecuta si o masura "metrica" a distantei catre destinatie. Aceasta distanta este oarecum un concept generalizat, care poate caracteriza īntārzierea īn trimiterea mesajelor catre acea entitate, costul trimiterii mesajului, etc. Algoritmii bazati pe vectorul distanta sunt numiti astfel din cauza faptului ca e posibil sa gaseasca o cale optima atunci cānd singura informatie schimbata este lista cu aceste distante. Mai mult decāt atāt, informatia este schimbata īntre entitati adiacente, adica entitati care apartin aceleeasi retele.

4.1.1 RIP: Protocolul bazat pe informatii de rutare

RIP este un protocol dintr-o serie de protocoale de rutare bazate pe algoritmul Bellman-Ford (sau vectorul distanta). Acest algoritm a fost folosit pentru aflarea rutelor īn retelele de calculatoare īnca de la īnceputul ARPANET-ului.

Acest protocol este mai util ca "protocol de gateway interior". Īntr-o retea vasta, asa cum este Internetul, ar fi dezavantajos sa fie folosit un singur protocol de rutare. Mai curānd, reteaua ar trebui sa fie organizata ca o colectie de "sisteme autonome". Un sistem autonom este īn general administrat de o singura entitate (organizatie), sau cel putin de catre cineva cu competente rezonabile pentru controlul administrativ si tehnic. Fiecare sistem autonom va avea propria tehnologie de rutare. Acesta tehnologie poate fi diferita de la un sistem autonom la altul. Protocolul de rutare folosit īn cadrul unui sistem autonom este un protocol tip interior sau "IGP" (Interior Gateway Protocol). Un alt tip de protocol este folosit pentru interfata dintre sistemele autonome. Cel mai vechi astfel de protocol si care mai este īnca folosit īn Intrenet este "EGP" (Exterior Gateway Protocol - protocol de tip exterior). Acest tip de protocoale se mai numesc protocoale de rutare inter-AS. RIP a fost dezvoltat pentru retele de dimensiuni moderate si care folosesc tehnologii omogene. El este potrivit ca IGP pentru campusuri si retele regionale ce folosesc linii seriale a caror viteza nu variaza foarte mult. Nu este recomandat a fi utilzat īn medii mai complexe.

RIP face parte din clasa de algoritmi numita "algoritmi bazati pe vector distanta". Cea mai veche descriere a acestei clase de algoritmi de catre autori cunoscuti este aceea facuta de Ford si Fulkerson. Din aceasta cauza mai sunt numiti si algoritmi Ford-Fulkerson. Termenul Bellman-Ford este de asemenea utilizat, deoarece acesti algoritmi folosesc ecuatia Bellman, ecuatie care este baza "programarii dinamice".

RIP a fost dezvoltat pentru a fi folosit īn Internet. Intrenetul consta dintr-un numar de retele conectate prin gateway-uri. Retelele componente pot fi cu legaturi de tip point-to-point fie retele mai complexe cum sunt Ethernet sau ARPANET. Hosturile si gateway-urile ofera datagrame IP adresate unui anumit host. Rutarea este metoda prin care host-ul sau gateway-ul decide unde anume trimite datagramele. E posibil sa poata trimite datagrama direct catre destinatie, daca acesta destinatie este īn reteaua la care este direct conectat host-ul sau gateway-ul. Interesanta este situatia īn care destinatia nu poate fi atinsa īn mod direct. Īn acesta situatie, host-ul sau gateway-ul īncearca sa trimita datagrama la un gateway care se afla cāt mai aproape de destinatie. Scopul unui protocol de rutare este deci foarte simplu: furnizarea informatiei necesare īn vederea rutarii.

4.1.1.1 Limitarile protocolului

Acest protocol nu rezolva toate problemele posibile de rutare. Asa cum am mentionat mai sus, intentia primara a fost pentru folosirea acestuia ca IGP īn retele de dimensiuni mici si relativ omogene. Trebuie mentionate īn plus urmatoarele limitari ale acestuia:

Protocolul este limitat pentru retele a caror cea mai lunga ruta (cale) are 15 hopuri. Acest protocol, prin modul īn care a fost proiectat, nu este potrivit pentru retele mai mari. De remarcat ca acesta afirmatie referitoare la limita presupune ca pentru fiecare conexiune este folosit un cost de valoare 1. Aceasta este metoda prin care RIP-ul este configurat īn mod normal. Daca administratorul de sistem alege sa utilizeze costuri mai mari, limita superioara de 15 devine o problema.

Acest protocol se bazeaza pe "numararea la infinit" pentru rezolvarea anumitor situatii speciale. (Acest lucru va fi explicat īn capitolul urmator). Daca sistemul de retele cuprinde cāteva sute de retele si se formeaza o bucla de rutare, rezolvarea acestei bucle va necesita mult timp (daca frecventa actualizarilor de rute este limitata) sau largime de banda mare. O astfel de bucla va consuma mult din largimea de banda a retelei īnainte ca bucla sa fie corectata. Se presupune ca īn situatiile reale aceasta nu va fi o problema cu exceptia cazurilor īn care sunt folosite linii lente. Chiar si asa, problema va fi una speciala, atāta timp cāt sunt luate diferite precautii pentru prevenirea unor astfel de probleme īn majoritatea cazurilor.

Acest protocol foloseste "metrice" fixe pentru compararea rutelor alternative. Acest lucru nu este potrivit pentru cazurile īn care rutele trebuie sa fie alese tinānd cont de parametrii de timp real, cum ar fi īntārzierea, fiabilitatea sau īncarcarea.

4.1.1.2 Specificatiile protocolului

RIP permite host-urilor si gateway-urilor sa schimbe informatii pentru a putea gasi rute īntr-o retea bazata pe IP. RIP este protocol bazat pe vectorul distanta (de tip "distance vector"). Poate fi implementat si de host si de gateway. Ca īn majoritatea documentatiilor IP, termenul de "host" va fi folosit aici pentru a le defini pe oricare dintre ele. RIP este folosit pentru a comunica informatii cu privire la rute catre "destinatii", care pot fi host-uri individuale, retele, o destinatie speciala folosita pentru a comunica o ruta implicita (default).

Orice host care foloseste RIP este de asteptat sa aiba interfete catre una sau mai multe retele. Acestea sunt referite ca retele direct conectate la el. Protocolul se bazeaza pe accesul la anumite informatii despre fiecare din aceste retele. Cea mai importanta este metrica sau costul. Metrica unei retele este un numar īntreg īntre 1 si 15 inclusiv. El este setat īntr-o anumita maniera care nu este specificata īn acest protocol. Cele mai multe din implementarile existente folosesc o metrica de valoare 1. Implementarile mai noi permit administratorului de sistem sa seteze costul pentru fiecare retea. Īn plus fata de cost, fiecare retea va avea o adresa IP de retea si o masca de subretea asociata. Acestea sunt setate de catre administrator īntr-o maniera nespecificata de acest protocol.

Se presupune ca exista o singura masca de subretea ce se aplica pentru fiecare retea IP, si o singura masca de subretea pentru retelele direct conectate. Exista sisteme ce folosesc masti de subretea diferite pentru subretele diferite apartinānd unei anumite retele. De asemenea, exista situatii īn care este de preferat pentru un sistem sa cunoasca mastile subretelelor apartinānd unor retele aflate la distanta. Astfel de situatii necesita modificari ale regulilor ce guverneaza modul de raspāndire a informatiilor de subretea. Astfel de modificari cresc posibilitatile de interoperabilitate si trebuie avute īn vedere ca modificari ale protocolului.

Se considera ca fiecare host care are implementat RIP are o tabela de rutare. Aceasta tabela contine cāte o intrare (linie), descrisa prin RIP, pentru fiecare destinatie care poate fi atinsa. Fiecare intrare contine cel putin informatiile urmatoare:

Adresa IP a destinatiei

O metrica, ce reprezinta costul total al transmiterii datagramei de la host la acea destinatie. Acesta metrica este suma costurilor associate cu retelele care vor fi traversate īn drumul pāna la destinatie.

Adresa IP a gateway-ului urmator de-a lungul caii catre destinatie. Daca destinatia este īn una dintre retelele direct conectate, aceasta informatie nu este necesara.

Un flag care indica daca acea informatie privind ruta a fost modificata recent. Se mai numeste "route change flag."

Diferiti timpi asociati cu ruta respectiva.

Intrarile referitoare la retelele direct conectate sunt setate de catre host, folosind diverse informatii culese, nespecificate īn acest protocol. Metrica pentru o retea direct conectata este setata la costul acelei retele. Īn implementarile RIP existente, pentru acest cost este folosita totdeauna valoarea 1. Īn acest caz, metrica RIP se reduce la o simpla numarare de hop-uri. Metrici mai complexe pot fi folosite atunci cānd se doreste evidentierea preferintei pentru o anumita retea fata de altele, de exemplu din cauza diferentelor privind largimea de banda sau siguranta acelei retele. Exsita de asemenea posibilitatea de a permite administratorului de sistem sa adauge rute aditionale.

Rutele catre alte destinatii decāt cele initiale sunt adaugate si updatate de algoritmii descrisi īn capitolele urmatoare. Pentru ca un protocol sa asigure informatii de rutare complete, fiecare gateway din system trebuie sa participe la aceasta. Host-urile care nu sunt gateway-uri nu participa, dar multe implementari ale acestui algoritm permit host-urilor sa receptioneze informatiile transmise prin RIP pentru a-si actualiza tabelele de rutare.

4.1.1.3 Formatul mesajului

RIP este un protocol bazat pe UDP. Fiecare host care foloseste RIP are un process de rutare care trimte si primeste datagrame pe portul UDP cu numarul 520. Toate mesajele transmise prin RIP catre un alt host, sunt trimise catre portul 520. Toate mesajele de actualizare de rute sunt trimise pe portul 520. Mesajele de actualizare de rute nesolicitate au ambele porturi sursa si destinatie, 520. Ceea ce se trimite ca raspuns la o cerere se trimite catre portul de la care a venit cererea. Interogarile specifice si mesajele de tip debug trebuie sa fie trimise de la alte porturi decāt 520, dar ele vor fi directionate catre portul 520 al masinii tinta.

Figura 4.3. Formatul pachetului (RIP versiunea 1)

Formatul pachetului este evidentiat īn figura 4.3. Portiunea din datagrama de la address family identifier pāna la metric poate aparea de pāna la 25 de ori. Adresa IP (IP address) este adresa Internet obisnuita (versiunea 4) pe 32 de biti.

Īn protocol este prevazuta si facilitatea de a permite procese RIP īn starea de ascultare "silent RIP". Un process silent este unul care īn mod normal nu trimite nici un mesaj. Cu toate acestea, el asculta mesajele trimise de alte procese. Un silent RIP poate fi folosit de host-uri care nu functioneaza ca gateway-uri, dar care doresc sa asculte actualizarile privind rutele īn vederea monitorizarii gateway-urilor locale si a actualizarii tabelelor de rutare interne. Un gateway care a pierdut legatura cu toate celelalte mai putin cu una din retelele sale, poate alege sa devina de tip silent, moment din care el nu mai este efectiv gateway. Oricum, acest lucru nu se va īntāmpla daca exista posibilitatea ca gateway-urile vecine sa depinda de mesajele sale pentru a detecta daca reteaua "cazuta" va redeveni operationala.

Fiecare datagrama contine o comanda, un numar de versiune si posbil argumente. Mai jos este descrisa versiunea 1 a acestui protocol. Cāmpul command este folosit pentru a specifica scopul datagramei. Īn tabelul de mai jos sunt prezentate cāteva comenzi implementate īn versiunea 1:

Pentru cerere si raspuns, restul datagramei contine o lista de destinatii cu informatii despre fiecare. Fiecare intrare din aceasta lista contine o retea sau un host destinatie si metrica pentru ele. Formatul pachetului este facut pentru a permite RIP sa transporte informatii de rutare pentru cāteva protocoale diferite. Astfel, fiecare intrare are un cāmp address family identifier pentru a indica ce tip de adresa este specificata īn intrarea respectiva. Acest curs descrie numai rutarea īn cazul retelelor IP. Valoarea address family identifier pentru IP este 2. Totusi, pentru a permite dezvoltarea ulterioara, implementarile sunt obligate sa ignore intrarile care contin tipuri de adrese ce nu sunt suportate. (Dimensiunea acestor intrari trebuie sa fie aceeasi ca dimensiunea unei intrari ce specifica o adresa IP). Procesarea mesajului continua īn mod normal dupa ce au fost ignorate toate intrarile ce nu sunt suportate. Adresa IP este adresa Internet obisnuita, memorata pe 4 octeti. Cāmpul metrica trebuie sa contina o valoare cuprinsa īntre 1 si 15 inclusiv, prin care se specifica metrica curenta pentru destinatie, sau valoarea 16, ceea ce va indica faptul ca destinatia nu poate fi atinsa. Fiecare ruta trimisa de un gateway suprascrie orice ruta anterioara trimisa de la acelasi gateway catre aceeasi destinatie. Dimensiunea maxima a datagramei este 512 octeti. Acestia includ numai portiunea din datagrama descrisa mai sus. Nu este contorizata si dimensiunea header-ului IP sau UDP. Comenzile ce contin informatii de retea permit informatiilor sa fie īmpartite īn mai multe datagrame. Nu sunt necesare masuri speciale pentru continuare, atāta timp cāt se obtin rezultate corecte īn urma procesarii individuale a datagramelor.

Formatul pachetului RIP 2

Specificatia pentru RIP 2 (descrisa īn RFC 1723) permite includerea multor informatii īn pachetele RIP si asigura un mecanism de autentificare simplu care nu este suportat de catre RIP. Figura 4.4 reprezinta formatul pachetului IP RIP 2.

Figura 4.4 Formatul pachetului RIP 2

Cāmpurile ce alcatuiesc pachetul IP RIP 2 din figura de mai sus sunt urmatoarele:

Command - Indica daca pachetul este un pachet cerere sau un pachet raspuns. Un pachet de tip cerere īntreaba daca un router a trimis o parte sau toata tabela sa de rutare. Un pachet de tip raspuns poate fi un mesaj de actualizare de rute obisnuit nesolicitat sau poate fi un raspuns la o cerere. Raspunsurile contin linii ale tabelei de rutare. Pachetele RIP multiple sunt folosite pentr a aduna informatii din tabele mari de rutare.

• Version -Specifica versiunea de RIP folosita. Īntr-un pachet RIP ce contine oricare din cāmpurile RIP 2 sau foloseste autentificare, aceasta valoare este setata la 2.
• Unused - Setat 0.
• Address-family identifier (AFI) - Specifica ce familie de adrese este folosita. Cāmpul AFI din RIPv2 are acelasi rol ca si cāmpul AFI din RFC 1058 RIP, cu o singura exceptie: daca AFI pentru prima linie din mesaj este 0xFFFF, restul liniei contine informatii de autentificare. Īn mod obisnuit, singurul tip de autentificare este o simpla parola.
• Route tag - Asigura metoda de a face diferenta dintre rutele interne (īnvatate de RIP) si rutele externe (īnvatate de la alte protocoale)
• IP address - Specifica adresa IP corespunzatoare liniei.
• Subnet mask - Contine masca de subretea corespunzatoare acestei linii. Daca acest cāmp este 0, nici o masca de subretea nu este specificata pentru linia respectiva.
• Next hop -Indica adresa IP a urmatorului hop catre care trebuie trimise pachetele corespunzatoare acelei linii.
• Metric -Specifica cāte hopuri (router-e) sunt traversate īn drumul spre destinatie. Valoarea pentru acest cāmp este cuprinsa īntre 1 si 15 pentru rutele valide si este 16 pentru o ruta necunoscuta.

4.1.1.4 Consideratii privind adresarea

Asa cum am stabilit anterior, rutarea bazata pe vectorul distanta este folosita pentru a descrie rute spre host-uri individuale sau spre retele. Protocolul RIP permite oricare din cele 2 variante. Destinatiile ce apar īn mesaje de cerere sau de raspuns pot fi retele, host-uri sau un cod special folosit pentru a indica ruta implicita (default). Īn general, tipul de ruta folosit va depinde de strategia de rutare utilizata pentru o retea particulara. Multe retele sunt configurate astfel īncāt aceste informatii de rutare pentru host-uri individuale nu sunt necesare. Daca fiecare host dintr-o anumita retea sau subretea este accesibil prin intermediul aceluiasi gateway, atunci nu este nici un motiv pentru a mentiona host-urile individuale īn tabelele de rutare. Cu toate acestea, retelele care includ linii de comunicatie punct la punct, necesita cāteodata ca gateway-urile sa pastreze rute catre anumite host-uri. Daca acest lucru este cerut sau nu, depinde de modul de adresare si de rutare folosit īn sistemul respectiv. Astfel, unele implementari pot alege sa nu accepte rute catre host-uri. Daca nu sunt acceptate rute catre host-uri, acestea vor fi ignorate atunci cānd sunt primite īn mesajele de raspuns.

Formatele pachetului RIP nu fac deosebire īntre diferitele tipuri de adrese. Cāmpurile care au eticheta "address" pot contine:

Adresa hostului - host address

Adresa subretelei - subnet number

Adresa retelei - network number

0, indicānd ruta implicita (default)

Entitatile care folosesc RIP utilizeaza informatiile specifice ce sunt disponibile cānd ruteaza o datagrama. Aceasta īnseamna ca, atunci cānd are loc rutarea unei datagrame, adresa sa destinatie trebuie mai īntāi verificata īn lista de adrese de hosturi. Apoi se verifica daca se potriveste cu vreo adresa de retea sau subretea. Īn final, daca nu exista nici o potrivire, se va folosi ruta default.

Cānd un host evalueaza informatiile primite prin RIP, interpretarea unei adrese depinde daca se cunoaste masca de subretea ce trebuie aplicata. Daca se cunoaste masca de subretea atunci se poate determina semnificatia adresei respective. De exemplu, fie reteaua 128.6.0.0. Masca de subretea este 255.255.255.0. Astfel, 128.6.0.0 este o adresa de retea, 128.6.4.0 este o adresa de subretea si 128.6.4.1 este adresa unui host. Cu toate acestea, daca host-ul nu cunoaste masca de subretea, determinarea unei adrese poate fi ambigua. Deoarece daca īntr-o adresa exista o parte diferita de 0 pentru host, nu este o metoda clara pentru a determina daca adresa reprezinta un numar de subretea sau o adresa de host. Asa cum adresa de retea nu este de folos fara masca de subretea, se presupune ca īn aceasta situatie adresele reprezinta host-uri. Pentru a evita acest gen de ambiguitati, host-urile nu trebuie sa trimita rute de subretele host-urilor care se stie ca nu cunosc masti potrivite de subretele. Īn mod normal, host-urile cunosc numai masti de subretea pentru retelele direct conectate. De aceea, mai putin īn situatia īn care s-a prevazut acest lucru, nu trebuie trimise rute catre subretele īn afara retelei din care face parte subreteaua respectiva.

Aceasta filtrare este asigurata de gateway-urile aflate la "granita" retelei de subretele. Acestea sunt gateway-uri ce conecteaza reteaua cu alte retele. Īn aceasta retea de subretele, fiecare subretea este tratata ca o retea individuala. Rutele catre fiecare subretea sunt transportate de catre RIP. Cu toate acestea, gateway-urile de granita trimit numai o intrare (ruta) pentru retea ca si pentru toate host-urile din alte retele. Acest lucru īnseamna ca un gateway de granita va trimite informatii diferite catre vecini diferiti. Pentru vecinii conectati la reteaua de subretele, va fi generata o lista cu toate subretelele la care acesta este direct conectat, folosind adresa de subretea. Pentru vecinii conectati la alte retele, va fi trimisa o singura intrare (ruta) pentru retea ca un tot, aratānd si metrica asociata acestei retele. (Aceasta metrica ar trebui sa fie cea mai mica metrica pentru subretelele la care gateway-ul este conectat).

Īn mod asemanator, gateway-urile de granita nu trebuie sa mentioneze īn mesajele catre alte retele, rutele catre host-uri pentru host-urile ce apartin unei retele direct conectate. Acele rute trebuie sa fie subsumate īntr-o singura intrare (ruta) catre retea ca īntreg. Nu am specificat ce se īntāmpla cu rutele catre host-uri pentru host-urile aflate la distanta (adica host-uri ce nu fac parte din retelele direct conectate). Īn general, aceste rute indica anumite host-uri la care se ajunge folosind o ruta care nu suporta alte host-uri din reteaua din care face parte host-ul respectiv.

Adresa speciala 0.0.0.0 este folosita pentru ruta default. O ruta default este folosita atunci cānd nu este convenabil sa se faca o lista cu toate retelele posibile īntr-o actualizare RIP, si cānd unul sau mai multe gateway-uri strāns conectate (closely-connected) din sistem sunt pregatite sa se ocupe de traficul spre retelele ce nu sunt explicit specificate. Aceste gateway-uri trebuie sa creeze intrari RIP pentru adresa 0.0.0.0, ca si cum ar fi o retea la care sunt conectate. Decizia felului īn care sunt create aceste intrari pentru reteaua 0.0.0.0 este lasata celui care face implementarea. Cel mai adesea, administratorul de sistem va avea o metoda pentru a specifica ce gateway va crea intrari pentru 0.0.0.0. Sunt posibile, īnsa si alte mecanisme. De exemplu, cel care face implemantarea, poate lua decizia ca orice gateway care īntelege EGP trebuie sa fie declarat ca gateway default. Ar putea fi util sa se permita administratorului de retea sa aleaga metrica ce va fi folosita īn aceste intrari. Daca exista mai mult de un gateway default, aceasta metrica va face posbila alegerea unuia fata de altul. Intrarea pentru 0.0.0.0 revine īn sarcina RIP-ului īn exact aceeasi maniera ca si cānd ar fi vorba de o retea avānd aceasta adresa. Oricum, intrarea este folosita pentru a ruta orice datagrama a carei adresa destinatie nu se potriveste nici unei retele care apare īn tabela de rutare. Nu este obligatorie aplicarea acestei conventii īn implementare dar acest lucru este recomandat. Implementarile care nu suporta 0.0.0.0 trebuie sa ignore intrarile cu aceasta adresa. Īn astfel de situatii nu vor include aceste intrari īn propriile actualizari RIP. Administratorii de sistem trebuie sa se asigure ca rutele 0.0.0.0 nu vor fi transmise mai departe decāt īn mod intentionat. Īn general, fiecare sistem autonom, are propriul gateway default. Astfel, rutele cu 0.0.0.0 nu trebuie sa treaca de granita sistemului autonom. Mecanismul care se ocupa cu acest lucru nu este abordat īn curs.

4.1.1.5 Ceasuri (Timer-e)

Acest capitol descrie toate evenimentele ce sunt declansate de ceasuri.

La fiecare 30 de secunde, procesul de iesire este configurat sa genereze un raspuns complet catre fiecare gateway vecin. Cānd sunt multe gateway-uri īntr-o singura retea, apare tendinta ca acestea sa se sincronizeze unul cu altul astfel īncāt īsi trimit actualizarile īn acelasi timp. Acest lucru se īntāmpla atunci cānd timer-ul de 30 de secunde este afectat de īncarcarea sistemului. Nu este de dorit ca mesajele de actualizare sa se sincronizeze deoarece pot aparea coliziuni. Astfel, īn implementari trebuie sa se aiba īn vedere urmatoarele precautii:

actualizarile la 30 de secunde sunt declansate de un ceas ce nu trebuie sa fie afectat de īncarcarea sistemului sau de timpul ncesitat de actualizarea precedenta;

timer-ul de 30 de secunde este decalat prin adaugarea unui timp aleator de fiecare data cānd este setat.

Sunt 2 ceasuri asociate cu fiecare ruta, un "timeout" si un "garbage-collection time" (timp de colectare a gunoiului). Dupa expirarea timeout-ului, ruta nu mai este valida. Oricum, ea este mentinuta īn tabela pentru o scurta perioada de timp, astfel īncāt vecinii sa poata afla ca acea ruta a fost eliminata. Dupa expirarea "garbage-collection time" ruta este stearsa din tabela.

Timeout-ul este initializat cānd este stabilita o ruta si de fiecare data cānd un mesaj de actualizare este primit pentru ruta respectiva. Daca trec 180 de secunde de la ultima initializare a timeout-ului, ruta este considerata expirata si va īncepe procesul de stergere.

stergerea are loc din unul din urmatoarele 2 motive: (1) timeout-ul expira, sau (2) metrica este setata la 16 din cauza unei actualizari primite de la gateway-ul curent. Īn fiecare din cele 2 cazuri se īntāmpla urmatoarele:

Timpul "garbage-collection" este setat pentru 120 de secunde.

Metrica rutei este setata la valoarea 16 (infinit). Aceasta va face ca ruta sa fie stearsa.

Este setat un fanion pentru a arata ca acesta ruta a fost modificata si procesul de iesire este atentionat sa declanseze un raspuns.

Pāna cānd "garbage-collection timer" expira, ruta este inclusa īn toate actualizarile trimise de acest host, avānd o metrica de valoare 16 (infinit). Cānd "garbage-collection timer" expira, ruta este stearsa din tabela.

Va trebui ca īnainte de expirarea "garbage-collection timer" sa fie stabilita o noua ruta spre aceasta retea, ruta ce o va īnlocui pe cea care va fi stearsa. Īn acest moment, garbage-collection timer va fi resetat.

4.1.1.6 Tratarea modificarilor topologiei

Īn practica, se īntīlnesc situatii īn care liniile de comunicatie se īntrerup si apoi revin. Versiunea teoretica a algoritmului implica un numar minim de vecini apropiati. Daca topologia se modifica, se schimba si setul de vecini. Data viitoare cānd va fi facut calculul, aceste modificari vor fi oglindite. Implementarile actuale utilizeaza o versiune incrementala a minimizarii. Numai cea mai buna ruta pentru oricare destinatie data va fi reamintita. Daca gateway-ul implicat īn aceasta ruta īsi īntrerupe functionarea sau daca conexiunea de retea va cadea, calculul e posbil sa nu reflecte niciodata modificarile. Algoritmul se bazeaza pe faptul ca gateway-ul īsi īnstiinteaza vecinii daca metricile sale se modifica. Daca gateway-ul cade, nu exista nici o cale de a anunta vecinii despre modificare.

Īn ideea de a rezolva acest tip de probleme, protocoalele bazate pe vectorul distanta trebuie sa dispuna de facilitatea expirarii unei rute. Detaliile depind de protocolul ales. Ca un exemplu, īn RIP fiecare gateway ce participa la rutare trimite un mesaj de actualizare catre toti vecinii sai la fiecare 30 de secunde. Presupunem ca ruta curenta catre reteaua N foloseste gateway-ul G. Daca nu se primeste nimic de la G timp de 180 de secunde, se presupune ca acest gateway a cazut sau ca s-a īntrerupt conexiunea catre acea retea. Deci, ruta va fi marcata ca fiind invalida. Atunci cānd vom afla de la un alt vecin ca exista o ruta valida catre reteaua N, aceasta ruta valida o va īnlocui pe cea invalida. De remarcat ca se asteapta 180 de secunde īnaintea expirarii rutei chiar daca se asteapta mesaje de la fiecare vecin la fiecare 30 de secunde. Din pacate, cāteodata mesajele se pierd īn retea. De aceea, nu este o idee buna sa se invalideze o ruta numai pe baza unui singur mesaj lipsa.

Asa cum se va vedea mai departe, este util sa existe modalitati de īnstiintare a vecinilor ca o anumita ruta catre o anumita retea este invalida. RIP, īmpreuna cu alte cāteva protocoale din aceaasta clasa, fac acest lucru printr-un mesaj obisnuit de actualizare, marcānd acea retea ca "unreachable" (la care nu se poate ajunge). O valoare specifica a metricei va fi aleasa pentru a indica o destinatie de neatins; aceasta valoare fiind mai mare decāt cea mai mare metrica valida. In implementarea actuala a RIP-ului este folosita valoarea 16. Aceasta valoare este referita ca "infinit" deoarece este mai mare decāt cea mai mare valoare valida pentru o metrica. 16 poate parea totusi un numar surprinzator de mic. Motivul pentru care a fost aleasa aceasta valoare se va vedea īn continuare. Īn majoritatea implementarilor, aceeasi conventie este folosita intern pentru a marca o ruta invalida.

Numarare la infinit (Counting to infinity)

Algoritmul folosit pāna acum a presupus totdeauna existenta unui host sau gateway pentru stabilirea unei tabele corecte de rutare. Cu toate acestea, nu este suficient pentru a fi folositor si īn practica. Dovezile de mai sus arata ca o tabela de rutare va converge catre valorile corecte īntr-un interval de timp finit. Nu se garanteaza ca acest timp va fi suficient de mic pentru a fi util si nici nu se spune ce se va īntāmpla cu metricele retelelor ce devin inaccesibile. E relativ usor sa aplicam metode matematice pentru tratarea rutelor ce devin inaccesibile. Conventia de mai sus poate face acest lucru. S-a ales o metrica de valoare mare pentru a reprezenta "infinitul" Aceasta valoare trebuie sa fie suficient de mare astfel īncāt nici o metrica reala sa nu poata avea vreodata aceasta valoare. Pentru a exemplifica acest lucru s-a ales valoarea 16. Sa presupunem ca o retea devine inaccesibila. Toate gateway-urile din imediata vecinatate vor fi īn timeout si metrica pentru acea retea va fi setata la valoarea 16. Īn scopul de a face o analiza, se va presupune ca toate gateway-urile vecine au primit o piesa hard noua care le conecteaza direct la reteaua disparuta care are costul 16. Atāta timp cāt aceasta este singura conexiune catre reteaua disparuta toate celelalte gateway-uri din sistem vor tinde catre noi rute ce trec prin unul din aceste gateway-uri. E usor de obesrvat ca īn aceasta situatie, toate gateway-urile vor avea metrica de valoare minim 16 catre reteaua disparuta. Gateway-urile aflate la numai un hop distanta de vecinii initiali, vor avea o metrica de valoare cel putin 17; gateway-urile aflate la 2 hopuri, cel putin 18 etc. Atāta timp cāt aceste metrici sunt mai mari decāt cea mai mare valoare acceptata pentru o metrica, ele vor fi setate la 16. Este evident ca īn aceasta situatie sistemul va converge la nivelul tuturor gateway-urilor catre metrica 16 spre acea retea.

Din nefericire, durata intervalului de convergenta nu se poate stabili īntr-un mod foarte simplu. Īnainte de a merge mai departe sa analizam urmatorul exemplu (figura 4.5). de remarcat ca ceea ce va fi aratat īn continuare nu se va īntāmpla īn cazul unei implementari corecte a RIP-ului. Vom īncerca sa demostram de ce sunt necesare anumite caracteristici

Figura 4.5

Toate conexiunile au costul 1, mai putin legatura directa de la C la D care are costul 10. Fiecare router (gateway) va avea o tabela continānd o ruta catre fiecare retea.

Sa notam numai rutele de la fiecare gateway catre reteaua D.

D: conectata direct, metrica 1

B: ruta prin D, metrica 2

C: ruta prin B, metrica 3

A: ruta prin B, metrica 3

Sa presupunem acum ca legatura dintre B si D cade. Rutele vor trebui acum modificate pentru a folosi legatura de la C la D. Din pacate, va dura ceva vreme pentru ca acest lucru sa se īntāmple. Modificarile de rutare īncep atunci cānd B anunta ca ruta catre D nu mai este utilizabila. Pentru simplificare, īn tabelul urmator se presupune ca toate gateway-urile trimit mesaje de actualizare īn acealasi timp. Īn tabel apar metricile pentru reteaua tinta, asa cum apar īn tabela de rutare a fiecarui gateway.

timp ------>

Dir = conectat direct

Unr = de neatins (unreachable)

Apare urmatoarea problema: B este capabil sa scape de ruta cazuta folosind un mecanism de timeout. Dar urme ale acestei rute persista īn sistem pentru o lunga perioada de timp. Initial, A si C cred ca pot ajunge la D prin B. Deci, ele vor continua sa trimita mesaje de actulaizare continānd metrici de valoare 3. La urmatoarea iteratie, B va pretinde ca poate ajunge la D fie prin A, fie prin C. Desigur, acest lucru este posibil. Rutele pretinse de A si C sunt inutilizabile, dar ele nu stiu īnca acest lucru. si chiar si atunci cānd vor descoperi ca rutele lor prin B au disparut, fiecare va crede ca mai este o ruta disponibila prin celalalt. Eventual sistemul va converge dar va trece ceva timp pāna se va īntāmpla acest lucru. Cel mai rau caz este cānd o retea devine complet inaccesibila dintr-o anumita parte a sistemului. Īn acest caz, metrica poate creste īncet īntr-un mod ca cel de mai sus pāna cānd va deveni infinit. Din acest motiv, problema este denumita "numarare la infinit".

Acum se poate īntelege de ce "infinitul" a fost ales sa aiba o valoare cāt mai mica. Daca o retea devine complet inaccesibila, e de preferat ca numararea la infinit sa se opreasca cāt mai repede. Infinitul trebuie sa fie suficient de mare astfel īncāt nici o ruta reala sa nu fie atāt de mare. Dar nu poate fi oricāt de mare. Deci alegerea infinitului este o negociere īntre marimea retelei si viteza de convergenta īn cazul īn care are loc o numarare la infinit. Proiectantii RIP-ului cred ca protocolul nu e practic pentru retele cu o īntindere mai mare de 15.

Sunt cāteva lucruri ce pot fi facute pentru a preveni astfel de probleme. Una dintre ele si care este folosita de RIP se numeste "split horizon with poisoned reverse", and "triggered updates".

4.1.1.8 Mecanismul "Split horizon"

Se observa ca, partial, problema de mai sus e cauzata de faptul ca gateway-urile A si C sunt angajate īntr-un proces de dezinformare reciproca. Fiecare pretinde sa fie capabil sa ajunga īn D prin celalalt. Acest lucru poate fi prevenit daca se are mai multa grija cu privire la destinatarul informatiei transmise. Īn particular, nu este corect sa pretinzi ca detii o ruta pentru reteaua destinatie a vecinului de la care de fapt ai īnvatat acea ruta. "Split horizon" este o schema pentru evitarea problemelor cauzate de transmiterea actualizarilor catre gateway-ul de la care a fost īnvatata ruta. Schema "split horizon" īn varianta simplificata omite rutele īnvatate de la un vecin īn mesajele de actualizare trimise la acel vecin. "Split horizon with poisoned reverse"  include astfel de rute īn mesajele de actualizare dar seteaza metricele acestora la infinit.

Daca A crede ca poate ajunge la D prin C, mesajele sale catre C ar trebui sa indice ca D nu poate fi atins. Daca ruta prin C este reala, atunci C ori are o legatura directa cu D, ori o legatura prin alt gateway. Ruta lui C nu poate duce īnapoi la A, deoarece formeaza o bucla. Spunāndu-i lui C ca D nu poate fi atins, A previne situatia īn care C ar putea deveni confuz si ar crede ca exista ruta prin A. Acest lucru este evident pentru o legatura punct la punct. Dar sa consideram ca A si C sunt conectate printr-o retea broadcast, cum este Ethernet-ul si exista si alte gateway-uri īn aceasta retea. Daca A are ruta prin C, ar trebui sa indice ca D este de neatins cānd discuta cu orice alt gateway din acea retea. Celelalte gateway-uri din retea pot ajunge ele īnsele (īn mod direct) la C. Nu au nevoie de o ruta prin A pentru a ajunge la C. Daca cea mai buna ruta a lui A este prin C, nici un alt gateway din acea retea nu are nevoie sa stie ca A poate ajunge la D. Este o sansa, pentru ca īnseamna ca acelasi mesaj de actualizare care este folosit pentru C poate fi folosit pentru toate gateway-urile din retea. Astfel, mesajele de actualizare pot fi trimise ca broadcast.

Īn general, "Split horizon with poisoned reverse" este mai sigur decāt "Split horizon". Daca 2 gateway-uri au rute care indica unul catre celalalt, rutele "reverse" cu o metrica de 16 vor rupe bucla imediat. Daca rutele "reverse" nu sunt anuntate, rutele eronate vor trebui eleiminate prin asteptarea unui timeout. Totusi, "poisoned reverse" are un dezavantaj: creste marimea metricei rutei. Sa consideram cazul unui backbone de campus ce conecteaza un numar de cladiri diferite. Īn fiecare cladire exsista un gateway ce conecteaza backbone-ul la reteaua locala. Sa ne imaginam ce actualizari (de tip broadcast) de rute ar transmite acele gateway-uri pe backbone. Īntr-adevar restul retelei trebuie sa stie despre fiecare gateway la ce retele locale este conectat. Folosind "Split horizon" (varianta simpla), numai acele rute ar aparea īn mesajele de actualizare trimise de gateway prin backbone. Daca este folosit "Split horizon with poisoned reverse" gateway-ul va trebui sa mentioneze toate rutele pe care le īnvata de la backbone, cu metrica de 16. Daca sistemul este mare (numar mare de retele si gateway-uri), mesajul de actualizare va fi complex cu majoritatea intrarilor indicānd retele de neatins.

Īntr-un sens static, transmitānd rute de tip "reverse" cu metrica de valoare 16 nu sunt furnizate informatii aditionale. Daca exista multe gateway-uri īntr-o retea de tip broadcast, aceste intrari suplimentare pot folosi o latime de banda (capacitate de trafic) semnificativa. Motivul pentru care sunt acolo este pentru a īmbunatati comportamentul dinamic (a grabi convergenta). Totusi, īn unele situatii administratorul de retea prefera sa accepte o convergenta mai lenta pentru a evita supraīncarcarea retelei. Cei ce realizeaza implementarea ar putea alege ei īnsisi "Split horizon" īn detrimentul "Split horizon with poisoned reverse", sau pot furniza o optiune de configurare care permite administratorului retelei sa aleaga varianta pe care o considera optima. Este permis sa se implementeze scheme hibride care sa promoveze unele rute "reverse" cu o metrica de 16 si sa omita altele. Un exemplu de o astfel de schema ar fi folosirea unei metrice de 16 pentru rute "reverse" pentru o anumita perioada de timp (din momentul declansarii schimbarilor de rutare ce le implica) si apoi omitāndu-le din mesajele de actualizare.

4.1.1.9. Actualizari determinate de anumite evenimente

Mecanismul "Split horizon with poisoned reverse" va preveni orice bucle de rutare ce implica numai 2 gateway-uri. Totusi exista situatii īn care īn formarea buclei sunt implicate 3 gateway-uri. De exemplu, A poate crede ca are ruta prin B, B prin C si C prin A. "Split horizon" nu poate elimina o astfel de bucla. Aceasta bucla va fi rezolvata numai cānd metrica atinge infinit si reteua implicata este deci declarata de neatins.

Actualizarile determinate de anumite evenimente sunt o īncercare de a mari viteza convergentei. Pentru a obtine aceste actualizari, adaugam o regula prin care ori de cāte ori un gateway schimba metrica pentru o ruta, se cere sa se transmita imediat mesajul de actualizare corespunzator, chiar daca nu este īnca timpul pentru un mesaj obisnuit de actualizare. (Detaliile de timp vor fi definite pentru fiecare protocol. Unele protocoale bazate pe vector distanta, incluzānd RIP, specifica o mica īntārziere pentru a evita ca actualizarile sa genereze trafic excesiv īn retea). De observat cum acest lucru se combina cu regulile de calculare a noilor metrici. Sa presupunem ca o ruta a unui gateway X catre destinatia N trece prin gateway-ul G. Daca soseste un mesaj de actualizare de la G, gateway-ul X trebuie sa valideze informatia noua, necontānd daca noua metrica este mai mare sau mai mica decāt cea veche. Daca rezultatul este o schimbare de metrica, atunci gateway-ul X va trimite actualizarile catre toate host-urile si gateway-urile conectate la el. La rāndul lor acestea pot fiecare trimite actualizari catre vecinii lor. Rezultatul este o cascada de actualizari. E usor sa aratam care gateway-uri si host-uri sunt implicate īn cascada de actualizari. Sa presupunem ca gateway-ul G are ruta catre N expirata. G va trimite actualizarile catre toti vecinii sai. Totusi, singurii vecini care vor lua īn considerare aceste noi informatii sunt aceia ale caror rute catre N trec prin G. Celelalte gateway-uri si hosturi vor vedea aceste noi informatii ca fiind rute noi care sunt mai rele ca cele pe care deja le folosesc, si le vor ignora. Vecinii ale caror rute trec prin G vor actualiza metricele si vor trimite actualizarile catre toti vecinii lor. Din nou, numai acei vecini ale caror rute trec prin el vor tine cont de aceste actualizari. Astfel, actualizarile se vor propaga īnapoi de-a lungul tuturor cailor ce duc spre gateway-ul G, actualizānd metricele la infinit. Aceasta propagare se va opri cānd se va ajunge la o portiune a unei retele a carei ruta catre destinatia N o ia pe alte cai.

Daca sistemul ar putea fi facut astfel īncāt sa "īnghete" pāna cānd este transmisa toata cascada de actualizari, e posibil sa se demonstreze ca numaratoarea la infinit nu va avea loc. Rutele proaste vor fi sterse totdeauna imediat, si astfel nu se va putea forma nici o bucla de rutare.

Din pacate, lucrurile nu stau chiar asa īn realitate. Cānd sunt transmise actualizarile determinate de anumite evenimente, actualizarile uzuale pot avea loc īn acelasi timp. Gateway-urile care nu au primit īnca actualizari determinate de anumite evenimente vor trimite īn continuare informatii bazate pe rute care de fapt nu mai exista. Este posibil ca dupa trecerea actualizarilor determinate de anumite evenimente printr-un gateway, acesta sa primeasca o actualizare normala de la unul din aceste gateway-uri care nu a fost īnca informat asupra evenimentului respectiv. Acest lucru va restabili o ruta gresita.

4.1.2 IGRP Interior Gateway Routing Protocol

IGRP este un protocol (elaborat de Cisco) ce permite unui numar de gateway-uri sa īsi coordoneze procesele de rutare. Scopurile sunt:

• rutare stabila chiar si īn retele largi sau foarte complexe. Nici o bucla de rutare nu va aparea nici chiar īn mod tranzitoriu ;
• raspuns rapid privind schimbarile de topologie ale retelei;
• supraīncarcare redusa. Aceasta deoarece, IGRP foloseste latimea de banda minima necesara pentru task-urile sale;
• īmpartirea traficului de-a lungul cātorva rute paralele atunci cānd sunt aproximativ echivalente;
• luarea īn considerare a ratei de eroare si a nivelului traficului pentru cai diferite;
• abilitatea de a trata mai multe tipuri de servicii pe baza unui singur set de informatii.

Implementarea curenta a IGRP-ului are īn vedere rutarea pentru TCP/IP. Cu toate acestea, structura de baza a fost creata pentru a functiona cu o varietate de protocoale.

Cu timpul, rutarea a devenit o problema mai dificila decāt era de asteptat. Initial, protocoale ca RIP erau suficiente pentru a se descurca cu majoritatea retelelor. Cu toate acestea, cresterea Internet-ului, si descentralizarea controlului structurii sale, au avut ca rezultat crearea unui sistem de retele care este aproape dincolo de posibilitatile noastre de administrare. Situatii asemanatoare au loc de asemenea īn mari retele ale unor corporatii. IGRP este o unealta facuta cu intentia de a ajuta īn rezolvarea acestei probleme.

Nu exista vreo unelata care sa rezolve toate problemele de rutare. Īn mod conventional, problema rutarii este īmpartita īn cāteva parti. Protocoale ca IGRP sunt numite "Internal Gateway Protocols" - IGPs. Acestea sunt facute cu intentia de a fi utilizate īn cadrul unui singur set de retele, toate acestea aflāndu-se sub o singura administrare. Aceste seturi de retele sunt conectate īntre ele printr-un "external gateway protocol" (EGPs). Un IGP este creat pentru a tine evidenta privind detalile despre topologia retelei. Prioritar īn proiectarea unui IGP este gasirea de rute optime si raspunsurile rapide la schimbari. Īn cazul unui EGP se asteapta protejarea unui sistem de retele īmpotriva mesajelor eronate transmise intentionat sau nu de alte sisteme. Prioritar īn implementarea unui EGP este stabilitatea si administrarea. Adesea este suficient pentru un EGP gasirea de rute rezonabile, mai degraba decāt gasirea unei rute optime. De fapt, exista caracteristici ale implementarii Cisco ce permit IGRP-ului sa fie folosit ca EGP īn anumite circumstante. Cu toate acestea, IGRP a fost proiectat pentru a fi utilizat ca IGP.

IGRP are cāteva similaritati cu protocoale mai vechi cum ar fi Xerox's Routing Information protocol, Berkeley's RIP, si "Hello" al lui Dave Mills. Difera de aceste protocoale īn primul rānd prin aceea ca a fost creat pentru retele mai mari si mai complexe. RIP este cel mai utilizat din generatia de protocoale mai vechi.

Ca si aceste protocoale mai vechi, IGRP este de tip vector distanta. Īn cazul unui astfel de protocol, gateway-urile schimba informatii de rutare numai cu gateway-urile adiacente. Aceste informatii de rutare contin un rezumat al informatiilor despre restul retelei. Se poate demonstra matematic, ca toate gateway-urile implicate īn procesul de rutare iau parte īmpreuna la rezolvarea unei probleme de optimizare pe baza unui algoritm distribuit. Fiecare gateway are nevoie sa rezolve numai o parte a problemei si va primi pentru asta numai o parte din datele totale.

4.1.2.1 Problema rutarii

IGRP se foloseste de catre gateway-uri ce interconecteaza cāteva retele. Presupunem ca retelele folosesc o tehnologie bazata pe comutarea pachetelor. Drept urmare, gateway-urile actioneaza ca niste comutatoare de pachete. Cānd un sistem conectat la o retea doreste sa trimita un pachet unui sistem dintr-o alta retea, īl trimite unui gateway. Daca destinatia este īntr-una din retelele conectate la gateway, gateway-ul va trimite pachetul la destinatie. Daca destinatia este īntr-o alta retea, gateway-ul va trimite pachetul unui alt gateway care este mai aproape de destinatie. Gateway-urile folosesc tabele de rutare pentru a decide ce sa faca cu pachetele. Iata un exemplu de tabela de rutare. (Se considera ca protocolul de comunicatie folosit este IP; problema rutarii este similara si pentru alte protocoale)

(De fapt tabelele de rutare IGRP contin mai multe informatii pentru fiecare gateway dupa cum se va vedea)

Acest gateway este conectat la 2 Eternet-uri numite 0 si 1. Acestora le-au fost alocate adresele IP de retea (de fapt adrese de subretele) 128.6.4.0 si 128.6.5.0. Astfel, pachetele adresate acestor retele pot fi trimise direct catre destinatie, pur si simplu prin folosirea interfetei Ethernet corespunzatoare. Sunt 2 gateway-uri apropiate (īnvecinate) 128.6.4.1 si 128.6.5.4. Pachetele catre alte retele decāt 128.6.4.0 si 128.6.5.0 vor fi trimise catre unul sau altul din cele 2 gateway-uri. Tabela de rutare indica ce gateway trebuie folosit si pentru ce retea. De exemplu, pachetele adresate unui host din reteaua 10.0.0.0 trebuiesc trimise catre gateway-ul 128.6.5.4. Consideram ca acest gateway este mai aproape de reteaua 10, adica cea mai buna ruta catre reteaua 10.0.0.0 trece prin acest gateway. Scopul primar al IGRP este sa permita gateway-urilor sa construiasca si sa īntretina astfel de tabele.

4.1.2.2 IGRP - prezentare generala

Asa cum s-a mentionat mai sus, IGRP este un protocol care permite gateway-urilor sa construiasca tabela de rutare prin schimbarea de informatii cu alte gateway-uri. Un gateway īncepe completarea tabelei de rutare cu intrari pentru toate retelele care sunt direct conectate la el. Obtine informatii despre alte retele prin schimburile de actualizari de rute cu gateway-urile adiacente. O ruta contine: destinatia, urmatorul gateway catre care trebuie trimise pachetele, interfata de retea ce ar trebui folosita, si informatia privind metrica. Informatia referitoare la metrica este un set de numere care descrie cāt de buna este ruta. Aceasta permite gateway-ului sa compare rutele despre care a fost informat de alte gateway-uri si sa decida pe care sa o folosesca. Sunt cazuri cānd are sens sa īmpartim traficul īntre 2 sau mai multe rute. IGRP va face acest lucru oricānd 2 sau mai multe rute sunt la fel de bune. Utilizatorul īl poate de asemenea configura sa īmparta traficul atunci cānd rutele sunt aproape egal de bune. Īn acest caz mai mult trafic va fi trimis prin calea cu metrica cea mai buna. De exemplu daca se doreste ca traficul sa fie īmpartit īntre doua linii, una de 9600 bps si o alta de 19200 bps, liniei de 19200 bps i se va aloca o metrica de 2 ori mai buna decāt cea a liniei de 9600 bps.

Metrica folosita de IGRP poate reprezenta:

• īntārzierea introdusa de conexiunea respectiva;
• latimea de banda (capacitatea de trafic a conexiunii);
• gradul de īncarcare a conexiunii;
• fiabilitatea conexiunii.

Īntārzierea introdusa de o conexiune reprezinta timpul necesar pentru a ajunge la destinatie prin acea cale, īn conditiile unei retele neīncarcate. Desigur exista īntārziere aditionala cānd reteaua este īncarcata. Totusi, īncarcarea este contabilizata prin folosirea parametrului "gradul de īncarcare a conexiunii" si nu prin īncercarea de a masura īntārzierea propriu-zisa. Latimea de banda a conexiunii este capacitatea de trafic exprimata īn biti/sec. Gradul de īncarcare a conexiunii indica cāt de multa banda este folosita curent. Poate fi masurata si se modifica odata cu īncarcarea conexiunii. Fiabilitatea indica rata curenta de erori. Poate fi masurata.

Desi nu sunt folosite ca parte a metricei, 2 informatii aditionale sunt transmise cu ea: "hop count" si MTU. "Hop count" reprezinta numarul de gateway-uri pe care un pachet va trebui sa le traverseze ca sa ajunga la destinatie. MTU reprezinta marimea maxima a pachetului ce poate fi transmis prin īntreaga cale fara fragmentare (este MTU-ul cel mai mic dintre toate MTU-urile retelelor traversate).

Pe baza informatiei metricelor, pentru o cale se calculeaza o singura metrica compusa. Metrica compusa combina efectul componentelor diferitelor metrici īntr-un singur numar reprezentānd "calitatea" caii. Metrica compusa este folosita pentru a decide cea mai buna cale de urmat.

Periodic, fiecare gateway transmite prin broadcast īntreaga tabela de rutare catre toate gateway-urile adiacente (cu unele exceptii din cauza mecanismului "Split horizon"). Cānd un gateway primeste acest mesaj de tip broadcast de la un alt gateway, compara tabela primita cu cea proprie. Orice destinatii sau cai noi sunt adaugate tabelei proprii de rutare. Rutele din mesajul broadcast sunt comparate cu rutele existente. Daca o ruta noua este mai buna, o poate īnlocui pe cea existenta. Informatia din broadcast este folosita de asemenea pentru actualizarea ocuparii canalului de comunicatie si a altor informatii despre rutele existente. Aceasta procedura generala este similara cu cea folosita de toate protocoalele bazate pe vectorul distanta (īn literatura matematica sunt referiti ca algoritmi Belmann-Ford).

Īn IGRP, algoritmul general Belmann-Ford este modificat īn 3 aspecte esentiale. Īntāi, īn loc de o metrica simpla, este folosit un vector de metrici pentru a caracteriza caile. Apoi, īn locul alegeri unei singure cai cu metrica cea mai mica, traficul este īmpartit de-a lungul mai multor cai ale caror metrici se īncadreaza īntre anumite valori. Īn al treilea rānd, au fost introduse cāteva elemente pentru a asigura stabilitate īn situatiile īn care topologia este modificata.

Calea cea mai buna este selectata pe baza unei metrici compuse:

[(K1 / Be) + (K2 * Dc)] r

Unde:

K1, K2 = constante
Be = largime de banda efectiva
Dc = īntārziere
r = stabilitate.

Cale cu cea mai mica metrica compusa va fi calea cea mai buna. Īn cazul īn care exista mai multe cai catre aceeasi destinatie, gateway-ul poate ruta pachetele de-a lungul mai multor cai. Acest lucru este facut tinānd cont de metrica compusa pentru fiecare pachet de date. De exemplu, daca o cale are o metrica compusa 1 si o alta cale are metrica compusa 3, de 3 ori mai multe pachete vor fi transmise pe calea cu metrica 1. Oricum, vor fi utilizate numai cai ale caror metrici compuse se īncadreaza īntre anumite valori ale celei mai mici metrici compuse. K1 si K2 indica ponderile ce vor fi atribuite largimii de banda si īntārzierii. Acestea depind de tipurile serviciilor. De exemplu, traficul de tip interactiv va acorda īn mod normal o importanta mai mare īntārzierii iar traficul de tip transfer de fisiere, largimii de banda.

Sunt 2 avantaje ale folosirii vectorului de metrici. Primul este ca asigura posibilitatea suportarii mai multor tipuri de servicii pe baza aceluiasi set de date. Al doilea avantaj este ca īmbunatateste acuratetea stabilirii rutelor. Cānd este folosita o singura metrica, este tratata ca si cānd ar reprezenta īntārzierea caii. Fiecare conexiune a caii este adaugata la metrica totala. Daca exista o legatura cu o largime de banda mica, ea este caracterizata īn mod normal de o īntārziere mare. Cu toate acestea, limitarile de largime de banda nu se cumuleaza similar īntārzierilor. Considerānd largimea de banda ca o componenta separata, aceasta poate fi tratata corect. Īn mod asemanator, īncarcarea poate fi tratata ca un parametru separat care indica gradul de ocupare a canalului.

IGRP asigura un sistem pentru interconectarea retelelor de calculatoare care poate rezolva īn conditii de stabilitate o topologie generala (inclusiv bucle). Sistemul contine informatii privind metricele īntregilor cai, adica, stie parametrii cailor catre toate celelalte retele la care oricare gateway este conectat. Traficul poate fi distribuit pe cai paralele si parametrii caii multiple pot fi simultan calculati de-a lungul īntregii retele.

4.1.2.3 Descriere detaliata

Cīnd un gateway este pornit prima data, este initializata tabela sa de rutare. Acest lucru poate fi facut de un operator de la consola de comanda, sau prin citirea informatiilor din fisierele de configurare. Este astfel asigurata o descriere a fiecarei retele conectate la gateway, inclusiv informatii privind īntārzierea conexiunii (adica cīt de mult īi ia unui singur bit sa traverseze conexiunea) si largimea de banda a conexiunii.

Figura 4.6 Exemplu de retea

De exemplu, īn fig 4.6 gateway-ul S, īn urma configurarii adreselor IP si a mastilor de retea corespunzatoare pentru interfetele sale, stie ca este conectat direct la retelele 2 si 3 prin interfetele corespunzatoare. Deci, initial, gateway 2 stie numai ca el poate retransmite pachete catre calculatoarele din retelele 2 si 3. Toate gateway-urile sunt configurate sa transmita periodic gateway-urilor vecine informatiile cu care au fost initializate, precum si informatiile obtinute de la alte gateway-uri. Astfel, gateway-ul S va primi actualizari de la gateway-urile R si T si va īnvata ca poate "ajunge" la calculatoarele din reteaua 1 prin gateway-ul R si calculatoarele din reteaua 4 prin T. Gateway-ul S īsi trimite īntreaga tabela de rutare (actualizata) si prin urmare īn ciclul urmator gateway-ul T va īnvata ca el poate ajunge la reteaua 1 prin gateway-ul S. E usor de vazut ca aceste informatii despre orice retea din sistem vor ajunge eventual la fiecare gateway din sistem.

Fiecare gateway calculeaza o metrica compusa pentru a determina "calitatea" caii catre calculatoarele destinatie. De exemplu, īn figura 4.7, pentru o destinatie din reteaua 6, gateway-ul A va clacula valorile metricei pentru 2 cai, prin gateway-ul B si C. De remarcat ca aceste cai sunt definite īn mod simplu, prin hostul urmator. Exista 3 rute posible de la A la reteaua 6:

• prin B
• prin C si apoi prin B
• prin C si apoi prin D

Cu toate astea, gateway-ul A nu va trebui sa aleaga īntre cele 2 rute prin C. Tabela de rutare a lui A are o singura intrare reprezentānd calea prin C. Metrica sa reprezinta cea mai buna cale de a junge de la C la destinatia finala. Daca A trimite un pachet catre C, depinde de C sa decida daca va folosi pe B sau pe D.

Figura 4.7 Exemplu de cai alternative

Metrica compusa calculata pentru fiecare cale arata astfel:

[(K1 / Be) + (K2 * Dc)] r (1)

Unde:

r = fiabilitate
(cāt % din transmisie este primita cu succes de hopul urmator)

Dc = īntārziere compusa;

Be = largime efectiva de banda;

K1, K2 = constante.

Īn principiu, īntārzierea compusa, Dc, poate fi determinata astfel:

Dc = Ds + Dcir + Dt  (2)

Unde:

Ds = īntārziere de comutare;
Dcir = īntārzierea de circuit (īntārzierea data de propagarea unui bit);
Dt = īntārzierea de transmisie.

Cu toate acestea, īn practica este utilizata o valoare standard reprezentānd īntārzierea pentru fiecare tip de retea. De exemplu, exista o valoare standard reprezentānd īntārzierea pentru o retea Ethernet si diverse valori pentru liniile seriale de diverse viteze.

Un exemplu de cum arata tabela de rutare pentru gateway-ul A este prezentat īn figura 4.8 (Pentru simplificare, componentele individuale pentru vectorul de metrici nu sunt reprezentate)

Figura 4.8 Exemplu de tabela de rutare

Aceste proces de creare a unei tabele de rutare prin schimbul de informatii cu vecinii este descris de algoritmul Bellman-Ford. Algoritmul a fost folosit īn protocoalele mai vechi ca RIP (RFC 1058). Pentru a fi eficient īn retele mai complexe, IGRP adauga 3 caracteristici noi algoritmului de baza Bellman-Ford:

1. Īn locul unei metrici simple, pentru a caracteriza o cale, este folosit un vector de metrici. O singura metrica compusa poate fi calculata pornind de la acest vector si folosind ecuatia (1). Folosirea unui vector de metrici permite gateway-ului sa trateze diverse tipuri de servicii, utilizānd coeficienti diferiti īn ecuatia (1). De asemenea, permite o mai buna reprezentare a caracteristicilor retelei decāt o metrica simpla.
2. Īn locul alegerii unei singure cai avānd cea mai mica metrica, traficul este īmpartit de-a lungul mai multor cai avānd metrice cuprinse īntre anumite valori. Acest lucru permite folosirea cātorva rute īn paralel, asigurānd astfel mai multa eficienta īn privinta utilizarii largimii de banda decāt īn cazul folosirii unei singure rute. Administratorul de retea specifica o constanta de variatie V. Toate caile avānd metrica compusa minima M sunt pastrate. Īn plus, toate caile cu metrice mai mici decāt VxM sunt de asemenea retinute. Traficul este distrubuit de-a lungul mai multor cai invers proportional cu metricile compuse asociate acestora.
3. Exista cāteva probleme legate de conceptul de dezacord. Este dificil de stabilit o strategie care sa asigure folosirea unui constante de variatie cu valoare mai mare decāt 1, si de asemenea sa nu conduca la bucle de rutare. Īn Cisco IOS 8.2, mecanismul acesta nu este implementat. Efectul acestui lucru este setarea valorii constantei de variatie la 1 īn mod permanent.
4. Cāteva carcateristici au fost introduse pentru a asigura stabilitatea īn cazul schimbarilor de topologie. Aceste carcateristici au scopul de a preveni buclele de rutare si "numararea la infinit", fenomene ce au carcaterizat īncercarile anterioare de folosire a algoritmilor de tip Ford pentru acest tip de aplicatii. Mecanismele cele mai importante ce asigura stabilitatea sunt "holddowns", "triggered updates", "split horizon," si "poisoning".

Īmpartirea (split-area) traficului (punctul 2) ridica īnsa si o problema nedorita. Constanta de variatie V a fost introdusa pentru a permite gateway-urilor sa foloseasca cai diferite avānd viteze diferite. De exemplu, poate exista o linie de 9600 bps īn paralel cu o linie 19200 bps, pentru a asigura redundanta. In cazul īn care constanta de variatie V este 1, numai calea cea mai buna va fi folosita. Deci linia de 9600 bps nu va fi folosita daca linia de 19200 bps are o fiabilitate rezonabila. (Oricum, daca sunt cāteva cai similare, īncarcarea va fi īmpartita īntre ele). Prin cresterea valorii constantei V, putem permite ca traficul sa fie īmpartit īntre cea mai buna ruta si alte rute care sunt aproape la fel de bune. Pentru o valoare suficient de mare a constantei V, traficul va fi īmpartit īntre cele 2 linii. Pericolul este ca avānd o valoare mare pentru V, sa fie urmate cai care sunt mai lente dar si "īn directii gresite". Astfel trebuie sa existe o regula aditionala pentru a preveni traficul sa fie transmis īntr-o directie gresita. Nici un trafic nu va fi trimis de-a lungul unei cai a carei metrica compusa calculata la distanta (calculata la hop-ul urmator) este mai mare decāt metrica compusa calculata de gateway. Īn general administratorii de sistem sunt īndrunati sa nu seteze valoarea constantei la o valoare mai mare decāt 1, exceptie facānd situatiile cānd e necesara folosirea unor cai paralele. Īn acest caz, constanta este setata cu grija, astfel īncāt sa asigure rezultatul "corect".

IGRP are scopul de a lucra cu mai multe tipuri de servicii si mai multe protocoale. Tipul serviciului este o specificatie īn pachetul de date care modifica felul īn care sunt evaluate caile. De exemplu, protocolul TCP/IP permite pachetului sa specifice importanta relativa a largimii de banda, īntārziere mica, sau siguranta (fiabilitate) ridicata. Īn general, aplicatiile interactive vor specifica o īntārziere mica, īn timp ce aplicatiile de transfer cantitativ vor specifica largimea de banda ca fiind mai importanta. Aceste cerinte determina valorile relative pentru K1 si K2 ce sunt necesare īn ecuatia (1). Combinatiile de specificatii din cadrul unui pachet de care trebuie tinut cont sunt numite "tipuri de servicii". Pentru ficare tip de servicii, trebuie ales setul de parametri K1 si K2. Este pastrata o tabela de rutare pentru fiecare tip de servicii. Acest lucru este facut deoarece caile sunt selectate si ordonate īn functie de metrica compusa definita de ecuatia (1) si este diferita pentru fiecare tip de serviciu. Informatiile din toate aceste tabele de rutare sunt combinate pentru a genera mesajele de actualizare ce se schimba īntre gateway-uri.

4.2 Protocoale de rutare de tip "Link state"

4.2.1 Descriere generala

Router-ele ce folosesc protocoale de rutare de tip "link state" schimba īntre ele mesaje numite "link state advertisments" (anunturi privind starea conexiunii)- LSAs care constau īn ID-urile retelelor conectate la router si costurile interfetelor. LSAa sunt trimise dupa activarea gateway-ului si atunci cānd sunt detecate schimbari īn topologia retelei. LSA-urile sunt trimise folosind mai degraba mesaje de tip direct sau multicast decāt mesaje de broadcast. Router-ele "link state" construiesc o baza de date de anunturi LSA si folosesc aceasta baza de date pentru a calcula rutele optime care sunt adaugate īn tabela de rutare. Informatiile de rutare schimbate īntre router-ele "link state" sunt sincronizate si se bazeaza pe confirmari. Īn urmatorul tabel sunt cāteva protocoale de rutare de tip "link state".

Avantajele protocoalelor de rutare de tip "link state":

• Tabele de rutare mai mici. Numai o singura ruta optima pentru fiecare ID de retea este stocata īn tabela de rutare.
• Supraīncarcare scazuta a retelei. Router-ele bazate pe starea legaturii nu schimba nici o informatie de rutare cānd reteaua este convergenta.
• Capacitatea de scalare. Beneficiind de tablele de rutare mici si de supraīncarcare scazuta, protocoalele de rutare de tip "link state" se comporta bine si cu retele mari si foarte mari.
• Timp de convergenta scazut. Protocoalele de rutare de tip "link state" au un timp de convergenta scazut si retelele converg fara pericolul aparitiei buclelor de rutare.

Dezavatajele protocoalelor de rutare bazate de tip "link state":

• Complexitate. Aceste protocoale sunt mult mai complexe si mai dificil de īnteles si de depanat decāt protocoalele bazate pe vectorul distanta.
• Mai dificil de configurat. Implementarea unui protocol de tip "link state" necesita planificari si configurari suplimentare.

4.2.2 Open Shortest Path First (OSPF)

OSPF ruteaza pachetele IP numai pe baza adresei IP destinatie si a tipului de serviciu (Type of Service - TOS) specificat īn header-ul pachetului IP. Pachetele IP sunt rutate fara a fi īncapsulate īn vreun alt format al unui protocol suplimetar atāt timp cāt tranziteaza un sistem autonom (AS). OSPF este un protocol de rutare dinamica. Detecteaza cu usurinta schimbarile de topologie din sistemul autonom (cum ar fi "caderea" interfetei unui router) si calculeaza noile rute fara bucle dupa o perioada de convergenta. Aceasta perioada de convergenta este scurta si implica un trafic de rutare minim.

Īn protocolul de rutare de tip "link state", fiecare router pastreaza o baza de date cu descrierea topologiei sistemului autonom. Fiecare router participant are aceeasi baza de date. Fiecare element din aceasta baza de date este o descriere a unui router din cadrul sistemului autonom (de exemplu interfetele utilizabile ale router-ului si vecinii la care acesta poate ajunge). Router-ul distribuie starea sa locala īn tot sistemul autonom prin flood-are (inundare).

Toate router-ele executa īn paralel acelasi algoritm. De la baza de date topologica, fiecare router īsi construieste un arbore cu cele mai scurte cai avānd ca radacina pe sine īnsusi. Acest arbore cu cele mai scurte cai asigura rutele catre fiecare destinatie din sistemul autonom. Informatiile privind rutele externe derivate apar ca frunze īn arbore.

OSPF calculeaza rute separate pentru fiecare tip de serviciu (TOS). Cānd sunt cāteva rute cu cost egal catre o anume destinatie, traficul este distribuit īn mod egal de-a lungul acestora. Costul unei rute este descris de o singura metrica simpla.

OSPF permite gruparea mai multor tipuri de retele. Un astfel de grup se numeste arie. Topologia unei arii este ascunsa de restul sistemului autonom. Aceasta ascundere de informatii permite o reducere semnificanta a traficului de rutare. De asemenea, rutarea īn interiorul ariei este determinata numai de propria topologie a ariei, asigurānd totodata protectia īmpotriva unor informatii de rutare gresite. O arie este o generalizare a unei subretele IP.

OSPF permite configuratii flexibile de subretele IP. Fiecare ruta distribuita de OSPF are o destinatie si o masca. Doua subretele diferite ale aceleiasi retele pot avea dimensiuni diferite (adica masti diferite). Acest lucru este referit īn mod obisnuit ca subretea de lungime variabila (variable length subnet mask - VLSM). Un pachet este rutat catre subreteaua cea mai buna (adica cu largimea cea mai mare). Host-urile sunt considerate subretele a caror masca este 255.255.255.255 (0xffffffff).

Toate schimburile de mesaje ale protocolului OSPF sunt autentificate. Acest lucru īnseamna ca numai router-ele de īncredere pot participa la rutarea īn cadrul sistemului autonom. Poate fi folosita o varietate de scheme de autentificare dar numai o singura schema de autentificare se configureaza pentru fiecare arie. Acest lucru permite unor arii sa utilizeze metode de autentificare mai riguroase decāt altele.

Informatiile de rutare externe derivate (de exemplu rute īnvatate de la Exterior Gateway Protocol - EGP) sunt trecute īn mod transparent prin sistemul autonom. Aceste informatii externe derivate sunt mentinute separat de datele protocolului OSPF. Fiecare ruta externa poate fi de asemenea etichetata de router-ul ce transmite mesaje LSA, asigurānd transmiterea informatiilor aditionale īntre router-e de la marginea sistemului autonom.

4.2.2.1 Baza de date topologica

Baza de date topologica a sistemului autonom reprezinta un graf orientat. Nodurile grafului reprezinta router-e si retele. O conexiune a grafului leaga 2 router-e cānd acestea sunt interconectate printr-o legatura fizica punct-la-punct. O conexiune ce conecteaza un router de o retea indica faptul ca acel router are o interfata īn acea retea.

Nodurile dintr-un graf pot fi clasificate īn concordanta cu functia acestora. Numai unele dintre ele transporta trafic de tranzit, adica acel trafic care nu a luat nastere local si care nici nu are un destinatar local. Nodurile ce transporta traficul de tranzit sunt reprezentate īn graf avānd conexiuni atāt de intrare cāt si de iesire.

OSPF suporta urmatoarele tipuri de retele fizice:

Retele Point-to-point

Este o retea care interconecteaza o singura pereche de router-e. O linie seriala de 56 Kbs este un exemplu de retea punct-la-punct.

Retele de tip "broadcast"

Retele ce suporta multe (>2) router-e conectate, īmpreuna cu posibilitatea de a adresa un singur mesaj fizic tuturor router-elor conectate (broadcast). Router-ele vecine sunt descoperite dinamic īn aceste retele prin folosirea protocolului OSPF Hello. Protocolul Hello foloseste avantajele mesajelor de broadcast. De asemenea, protocolul foloseste facilitatile de multicast, daca acestea exista. O retea Ethernet este un exemplu de retea broadcast.

Non-broadcast networks

Retelele ce suporta multe (>2) router-e conectate dar fara sa aiba posibilitate de broadcast. In aceste retele router-ele vecine sunt de asemenea descoperite prin folosirea protocolului OSPF Hello. Cu toate acestea, din cauza lipsei posibilitatii de broadcast sunt necesare unele informatii de configurare pentru ca protocolul Hello sa functioneze corect. Īn aceste retele, pachetele protocolului OSPF care sunt de obicei multicast trebuie sa fie trimise fiecarui router vecin, pe rānd. Un exemplu de retea non-broadcast este reteaua de date publica X.25 (X.25 Public Data Network - PDN).

Vecinatatea fiecarui nod de retea din graf depinde de existenta facilitatii de multiacces (fie broadcast fie non-broadcast) si, daca aceasta exista, de numarul de router-e care au o interfata conectata la retea. Īn figura 4.9 sunt īnfatisate 3 cazuri. Router-ele sunt notate cu RT, iar retelele cu N. Interfetele router-elor sunt notate cu I. Liniile dintre router-e indica retele punct-la-punct. Īn parte a figurii este īnfatisata o retea cu router-ele conectate la ea urmata de graful corespunzator.

Doua router-e interconectate printr-o retea punct-la-punct sunt reprezentate īn graful orientat ca fiind conectate printr-o pereche de conexiuni, cāte una īn fiecare directie. Nu este obligatoriu ca interfetelor conectate īn reteaua punct-la-punct sa li se asigneze adrese IP. Astfel de retele punct-la-punct se numesc "fara adresa" (unnumbered). Reprezentarea grafica a retelelor punct-la-punct este conceputa astfel īncāt aceste retele "fara adresa" sa poata fi suportate īn mod natural. Cānd se asigneaza adrese IP interfetelor, acestea sunt modelate ca rute finale. De remarcat ca, īn aceasta situatie, fiecare router va avea o conexiune finala catre adresa interfetei celuilalt router. (figura 4.9)

Cānd mai multe router-e sunt atasate la o retea multiacces, garful orientat asociat va contine toate router-ele conectate bidirectional la retea (figura 4.9). Daca la o retea multiacces este atasat numai un singur router, īn graful corespunzator reteaua va aparea ca o conexiune finala.

Retea fizica punct-la-punct

Retea multiacces

Retea multiacces finala

Figura 4.9 Componentele hartii retelei

Fiecare retea (finala sau de tip tranzit) din graf are o adresa IP si o masca de retea asociata. Masca indica numarul de noduri din retea. Host-urile atasate direct la router-e apar īn graf ca retele finale. Masca de retea pentru un host este totdeauna 255.255.255.255 (0xffffffff), ceea ce indica prezenta unui singur nod.

4.2.2.2 Arborele celei mai scurte cai (shortest-path tree)

Cānd nici o zona OSPF nu e configurata, fiecare router īn sistemul autonom are o baza de date topologica identica, conducānd la o reprezentare grafica identica. Pe baza acestui grafic, un router īsi genereaza tabela de rutare, prin calcularea unui arbore al celor mai scurte cai avānd ca radacina router-ul īnsusi. Evident arborele depinde de router-ul care efectueaza calculele.

Dupa ce este creat arborele, este examinata informatia de rutare externa. Aceasta poate fi generata de un alt protocol de rutare ca EGP, sau poate fi configurata static. Rutele implicite (default) pot fi de asemenea incluse ca parte a informatiilor de rutare externa a sistemului autonom. Informatia externa este retransmisa (prin flood-are) nemodificat prin sistemul autonom.

OSPF suporta 2 tipuri de metrica externa. Tipul 1 este echivalent cu metrica "link state". Tipul 2 este reprezentat de metricele mai mari decāt costul oricarei cai interne a sistemului autonom. Utilizarea tipului 2 presupune ca rutarea īntre sisteme autonome reprezinta costul principal al rutarii unui pachet si elimina nevoia de conversie a costurilor externe īn metrici interne de tip "link state".

OSPF permite gruparea unei colectii de retele host-uri contigue. Un astfel de grup, īmpreuna cu router-ele avānd interfete conectate la oricare din retelele incluse, poarta numele de zona (arie). Fiecare zona ruleaza o copie separata a algoritmului de rutare de tip "link state". Acesta īnseamna ca fiecare zona are propria ei baza de date topologica si graful corespunzator. Topologia unei zone este invizibila din exteriorul zonei. Router-ele aflate īntr-o zona data nu stiu nimic despre topologia externa zonei respective. Aceasta izolare permite protocolului sa efectueze o reducere semnificativa a traficului de rutare fata de situatia īn care īntregul sistem autonom ar fi tratat ca un singur domeniu "link state".

Odata cu introducerea zonelor, nu mai este valabila ideea ca toate router-ele din sistemul autonom au baze de date topologice identice. Un router are o baza de date separata pentru fiecare zona la care este conectat. (Router-ele conectate la mai multe zone sunt denumite router-e de granita). Doua routere apartinānd unei zone au pentru acea zona baze de date topologice identice.

Rutarea īn sisteme autonome are loc la 2 nivele. Daca sursa si destinatia unui pachet se afla īn aceeasi zona este folosita rutarea intra-zonala; daca se afla īn zone diferite este folosita rutarea inter-zonala. Īn cadrul rutarii intra-zonale, pachetul este rutat numai pe baza informatiei obtinuta īn cadrul zonei. Nici o informatie de rutare obtinuta din afara zonei nu poate fi utilizata. Acest lucru protejeaza rutarea intra-zonala de injectarea informatiei de rutare eronate.

4.3. Sisteme autonome (Autonomous Systems)

Īn sisteme de retele interconectate de dimensiuni foarte mari, e necesar sa se īmparta reteaua īn entitati separate cunoscute ca sisteme autonome. Un sistem autonom este o parte a unei retele avānd aceeasi autoritate administrativa. Aceasta poate fi o institutie sau o corporatie, dar poate fi de asemenea reprezentata de utilizarea unui protocol de rutare comun (cum ar fi OSPF). Portiunile alaturate ale unei retele IP, ce foloseste OSPF pentru a distribui informatia de rutare, se afla sub autoritatea administrativa a OSPF-ului si formeaza, din aceasta cauza, un sistem autonom OSPF. Sistemul autonom poate fi mai departe īmpartit īn domenii, regiuni sau zone care definesc o ierarhie īn cadrul sistemului autonom.

Figura 4.10 Sisteme autonome, protocoale interior gateway, si protocoale exterior gateway.

Protocoalele folosite pentru distribuirea informatiei de rutare īn cadrul unui sistem autonom sunt cunoscute ca Interior Gateway Protocols (IGPs). Protocoalele folosite pentru distribuirea informatiilor de rutare īntre sisteme autonome sunt cunoscute ca Exterior Gateway Protocols (EGPs).

Interior Gateway Protocols (IGPs)

Protocoalele IGP sunt protocoale de rutare intra-SA. IGP distribuie rute īn interiorul SA.

Exemple de IGP:

• RIP pentru IP. IGP de tip vector distanta bazat pe RFC.
• OSPF. IGP de tip "link state" bazat pe RFC.
• Interior Gateway Routing Protocol (IGRP). IGP de tip vector distanta implementat de Cisco Systems, Inc.

Exterior Gateway Protocols (EGPs)

EGP-urile sunt protocoale de rutare inter-SA. Ele definesc modul īn care toate retelele din cadrul sistemelor autonome sunt "anuntate" īn afara sistemului autonom. Aceasta poate include o lista de rute īntr-o infrastructura de rutare pe un singur nivel sau o lista de rute simplificate īntr-o infrastructura de ruatre ierahica. EGP-urile sunt independente de IGP-urile folosite īn cadrul SA. Ele pot facilita schimbul de rute īntre sistemele autonome care folosesc IGP-uri diferite.

Exemple de EGP pentru retele IP:

Exterior Gateway Protocol (EGP). Un EGP bazat pe RFC ce a fost dezvoltat pentru utilizare īntre sisteme autonome din Internet. EGP nu mai e folosit īn Internet din cauza faptului ca nu dispune de suport pentru medii complexe multi-cale si Classless Inter-Domain Routing (CIDR).

Border Gateway Protocol (BGP). Un EGP bazat pe RFC care este īn mod curent folosit īntre sistemele autonome din Internet. BGP suplineste lipsurile EGP-ului. Versiunea curenta de BGP folosita pentru router-ele de backbone din Internet este BGP4.