Documente online.
Zona de administrare documente. Fisierele tale
Am uitat parola x Creaza cont nou
 HomeExploreaza
upload
Upload




Rutare dinamica

Informatica


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:

1 - request

O cerere ca sistemul repondent sa transmita o parte sau întreaga tabela de rutare.

2 - response

Un mesaj ce contine toata sau numai o parte din tabela de rutare a expeditorului. Acest mesaj poate fi trimis ca raspuns la o cerere (request), sau poate fi un mesaj de actualizare generat de expeditor.

3 - traceon

Învechit.  Mesajele continând aceasta comanda vor fi ignorate.

4 - traceoff

Învechit.  Mesajele continând aceasta comanda vor fi ignorate.

5 - reserved

Aceasta valoare este folosita de Sun Microsystems pentru scopuri personale. Daca noi comenzi sunt adaugate în oricare din versiunile urmatoare, acestea trebuie sa înceapa cu 6. Mesajele continând aceasta comanda pot fi ignorate de implementarile care aleg sa nu raspunda la ele.

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.

1-octet

command

field

1-octet

version

number field

2-octet

unused field

2-octet

AFI field

2-octet

route tag field

4-octet network address field

4-octet subnet mask field

4-octet next hop field

4-octet metric field

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 ------>

Next hop

Dist.

Next hop

Dist.

Next hop

Dist.

Next hop

Dist

Next hop

Dist.

Next hop

Dist.

D

Dir

Dir

Dir

Dir

Dir

Dir

B

Unr

C

C

C

C

C

C

B

A

A

A

A

D

A

B

C

C

C

C

C

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)

Destination

Gateway

Interface

none

Ethernet 0

none

Ethernet 1

Ethernet 0

Ethernet 1

Ethernet 1

(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)

Destinatie

Interfata

gw urmator

Metrica

Network 1

I1

conectata direct

Network 2

I2

conectata direct

Network 3

I3

conectata direct

Network 4

I2

C

I3

B

Network 5

I2

C

I3

B

Network 6

I2

C

I3

B

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".

Routable Protocol

Link State-based Routing Protocol

IP

OSPF (Open Shortest Path First)

IPX

NLSP (NetWare Link Services Protocol)

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.

Tip nod

Nume nod

Tranzit

Router

Da

Retea

Da

Retea finala

Nu

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.

de la

s

p

r

e

RT1

RT2

RT1

X

RT2

X

Ia

X

Ib

X

Retea fizica punct-la-punct

de la

s

p

r

e

RT3

RT4

RT5

RT2

N2

RT3

X

RT4

X

RT5

X

RT6

X

N2

X

X

X

X

Retea multiacces

de la

s

p

r

e

RT7

N3

RT7

X

N3

X

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.




Document Info


Accesari: 5695
Apreciat: hand-up

Comenteaza documentul:

Nu esti inregistrat
Trebuie sa fii utilizator inregistrat pentru a putea comenta


Creaza cont nou

A fost util?

Daca documentul a fost util si crezi ca merita
sa adaugi un link catre el la tine in site


in pagina web a site-ului tau.




eCoduri.com - coduri postale, contabile, CAEN sau bancare

Politica de confidentialitate | Termenii si conditii de utilizare




Copyright © Contact (SCRIGROUP Int. 2025 )