Rutele informatiei - trasee de rutare

In drumul sau de la o retea la alta, de la o sursa catre o destinatie, informatia intalneste cel putin un nod (sau un "hop"), adica un calculator care inlesneste transportul acesteia. Aceste noduri comunica deoarece, anterior, au fost supuse unei operatiuni de "bridging", adica unei alocari de adrese si creare de legaturi de comunicatie. Rutarea nu este insa un "bridging". Diferenta este foarte importanta: bridging-ul se face pe layer 2 (adica nivelul link-urilor), iar rutarea, cea care se ocupa efectiv de transferul informatiei, apare pe layer 3, cel dedicat structurii de retea. Bazele rutarii au fost explicate in literatura informatica acum mai bine de doua decenii, insa popularitatea comerciala si-a dobandit-o spre mijlocul anilor 1980. Aceasta pentru ca, relativ recent, internetworking-ul s-a dezvoltat pe scara larga. Rutarea implica doua activitati de baza: determinarea cailor de rutare optime si transportul grupurilor de informatii, in mod tipic denumite pachete. In contextul procesului de rutare, a doua sa parte poarta numele de switching. Desi switching-ul poate fi facut relativ simplu, determinarea caii optime poate fi foarte complexa.

Cum se determina un traseu de rutare?

Fara a sti prea multe despre procedurile de rutare, putem considera mai intai ca traseul optim este cel de lungi-me minima. Pentru aceasta se folosesc algoritmi de rutare care initializeaza si administreaza tabele de rutare in care sunt inscrise, printre altele, toate distantele dintre rutere. De exemplu, un ruter va memora asociatiile dintre o destinatie finala si cel mai apropiat ruter in calea optima catre care trebuie sa trimita pachetele de date. In momentul in care un ruter primeste un pachet de date, ii verifica adresa de destinatie si incearca o asociere a acesteia cu ruterul cel mai apropiat.
Tabelele de rutare pot contine si alte informatii, cum ar fi cele despre calita-tea unui anumit traseu. Ruterul com-para lungimile, le pondereaza cu gradul de performanta si determina calea op-tima. Dimensiunea rezultanta poate diferi in functie de algoritmul de rutare folosit. Vom descrie mai tarziu cateva dintre aceste metode de dimensionare. Ruterele comunica unul cu celalalt si se ajuta reciproc la mentinerea tabelelor de rutare prin transmisia multor tipuri de mesaje cum ar fi cele de "update" sau de "link-state". Analizand mesajele de "update" de la toate nodurile la care are acces, un ruter poate sa-si construiasca o imagine detaliata a topologiei retelei globale. Printr-un me-saj de "link-state", un ruter le informeaza pe toate celelalte despre starea si tipul conexiunilor expeditorului de mesaj. Acest mesaj poate fi folosit, de asemenea, in crearea tabelelor de rutare.

Switching

Algoritmii de switching (comutare) sunt relativ simpli si sunt fundamental aceiasi pentru majoritatea protocoale-lor de rutare. Pentru a ilustra mai bine acest proces sa ne imaginam ca dorim sa trimitem o scrisoare la o adresa din Japonia. Adresa de pe plic, cea a destinatarului, poate fi asociata adresei de protocol, sau de layer 3. Ea nu se modifica. Pe parcurs, scrisoarea va trebui sa treaca prin mai multe oficii postale (rutere). Sa zicem ca nu exista o legatura aeriana directa intre Bucuresti si Tokyo. Scrisoarea va trebui sa parcurga insa un drum optim, astfel incat sa ajunga intacta si cat mai rapid la destinatar. De aceea, oficiul postal (ruterul) din Bucuresti va trebui sa aleaga modalitatea in care sa trimita scrisoarea: fie folosind traseul Beijing-Seul-Tokyo, fie Amsterdam-New York-Los Angeles-Tokyo. Numarul de hop-uri este, in cazul al doilea, mai mare. Insa siguranta poate fi mai mare si timpul transferului mai redus, datorita eficientei oficiilor postale din orasele de pe parcurs. Odata facuta alegerea celui de-al doilea traseu, prin algoritmul de rutare bazat pe fiabilitate si intarziere minima, scrisorii i se va atasa o prima adresa de layer 2, cea a oficiului din Amsterdam.
Scrisoarea ajunge la ruterul din Amsterdam, care trebuie sa optimizeze la randul sau traseul. Analizand cu propriul algoritm de rutare legaturile posibile, ruterul din Amsterdam observa ca legatura cu New-York-ul este intrerupta. El va trebui sa decida trimiterea scrisorii pe primul traseu optim disponibil. Interogand toate ruterele (oficii postale) cu care este in legatura, ruterul din Amsterdam decide sa ruteze scrisoarea prin Sydney, stiind ca legatura Sydney-Tokyo este sigura. Pe scrisoare va aparea noua adre-sa de layer 2, cea a ruterului din Sydney, iar adresa de protocol, de layer 3 a destinatarului final, ramane neschimbata. Sa explicam acum si intr-un limbaj mai tehnic. In majoritatea cazurilor, primul ruter stabileste ca trebuie sa trimita un pachet unui alt ruter. Avand adresa de layer 3 a ruterului destinatie (presupunem ca o are in tabela de adrese), ruterul sursa trimite un pachet pe adresa fizica de tip MAC (Media Access Control) a urmatorului ruter, stabilita deja prin bridging. Acest mesaj contine adresa de protocol, sau de layer 3, a ruterului destinatie. In timp ce examineaza adresa de protocol a destinatiei finale pentru pachetul trimis, al doilea ruter determina daca poate sau nu sa inainteze pachetul catre urmatorul ruter (hop). Daca ruterul doi nu cunoaste cum sau unde sa trimita pachetul, atunci il elimina sau il trimite inapoi la primul ruter insotit de un mesaj de eroa-re. In caz contrar, modifica adresa fizica (de layer 2) pentru urmatorul hop si transmite pachetul. La un moment dat, ruterul care primeste pachetul de date este si destinatia finala a acestuia. In tot acest parcurs pachetul s-a deplasat de la un ruter la celalalt. Pe parcurs i s-a modificat numai adresa de pe nivelul fizic (layer 2), in timp ce adresa de protocol (layer 3) a ramas neschimbata. Discutia de mai sus descrie procesul de switching intre un sistem sursa si unul destinatie. Organizatia Internationala de Standardizare (ISO) a elaborat o terminologie ierarhizata folosita in descrierea acestui proces. Prin aceasta terminologie, dispozitivele de retea fara capacitatea de a inainta pachete intre subretele sunt denumite "End Systems" (ESs), in timp ce sistemele cu aceasta capacitate sunt denumite "Intermediate Systems" (ISs). Cele din urma sunt subdivizate in cele care pot comunica in interiorul domeniilor de rutare (intradomeniu) si cele care pot comunica atat in interiorul cat si intre domeniile de rutare (interdomeniu). Domeniile de rutare sunt denumite si sisteme autonome. Cu anumite protocoale, domeniile de rutare pot fi divizate in zone de rutare, dar protocoalele de rutare sunt inca folosite pentru switching atat in interiorul cat si intre zone.

Proiectarea algoritmilor de rutare

Algoritmii de rutare pot fi deosebiti dupa mai multe caracteristici. Mai intai, scopul principal al proiectarii algorit-mului poate afecta functionarea proto-colului rezultant. Apoi, exista mai multe tipuri de algoritmi de rutare, iar fiecare dintre acestia are un impact diferit asupra resurselor retelei si ruterului. In sfarsit, algoritmii de rutare folosesc o varietate larga de sisteme de masura care afecteaza calculul rutelor optimale. Algoritmii de rutare sunt proiectati avand in vedere una sau mai multe dintre urmatoarele criterii de performanta: optimalitate, simplitate si rapiditate, robustete si stabilitate, convergenta rapida, flexibilitate. Optimalitatea se refera la capacitatea algoritmului de a selecta cea mai buna cale, in functie de sistemul de masura a distantei si ponderile folosite in calcule. De exemplu, un algoritm poate folosi un numar de hop-uri si intarzieri prestabilit, dar poate pondera mai mult aceste intarzieri in calcule. Algoritmii de rutare trebuie proiectati cat mai simplu posibil. Cu alte cuvinte, un algoritm trebuie sa ofere o functionalitate eficienta, cu un software si putere de calcul minime.
Randamentul este in special important atunci cand software-ul algoritmului trebuie sa ruleze pe un computer cu resurse fizice limitate. Robustetea algoritmilor presupune functionarea corecta in conditiile celor mai neobisnuite si neprevazute circumstante, cum ar fi defectiuni hardware, supraincarcare, implementari incorecte. Toate aceste defectiuni apar, in general, datorita pozitionarii ruterelor in punctele de jonctiune ale retelelor, fapt ce cauzeaza probleme severe in cazul defectiunilor acestora. In plus, algoritmii de rutare trebuie sa convearga foarte rapid. Convergenta poate fi considerata ca un consens la care ajung toate ruterele asupra cailor optime. In cazul in care un eveniment face ca un ruter sa fie inaccesibil, celelalte rutere trebuie sa-si redistribuie mesajele de update si sa stimuleze, in acelasi timp, recalcularea cailor optimale, ajungand la un consens in ceea ce priveste noua structura a tabelului de rutare. Algoritmii de rutare care converg lent pot duce la formarea de bucle de rutare sau caderi ale retelei. Flexibilitatea algoritmilor de rutare inseamna adaptarea acestora rapida si precisa la cele mai diverse situatii survenite in retea. Sa presupunem, de exemplu, ca un segment de retea a cazut. In clipa in care ruterele sunt informate de problema, algoritmii vor selecta cat mai rapid urmatoarea cale optima pentru toate rutele care folosesc acel segment. Algoritmii de rutare pot fi programati, printre altele, sa se auto-adapteze la modificari ale latimii de banda a retelei, ale dimensiunii cozii de asteptare a ruterului si intarzierilor din retea.

Tipuri de algoritmi de rutare

Algoritmii de rutare sunt clasificati dupa urmatoarele criterii: statici sau dinamici, de cale unica sau multipla, orizontali sau ierarhici, de intra-domeniu sau de inter-domeniu, de legatura sau de distanta. Algoritmii statici nu sunt propriu-zis algoritmi, intrucat acestia nu calculeaza traseul minim, ci preiau pur si simplu o cale din tabelele introduse de administratorul de retea la instalarea ruterului. Aceste tabele nu se modifica decat prin interventia administratorului. Astfel ca ele pot fi utilizate numai intr-un trafic predictibil si o structura de retea relativ simpla. Datorita inertiei la modificarile survenite in retea, algoritmii statici sunt imposibil de folosit in retelele actuale, in continua extindere.

majoritatea algoritmilor de rutare existenti sunt de tip dinamic, care se autoajusteaza prin analizarea mesajelor de update primite in procesul rutarii. Daca mesajul indica o modificare a retelei, software-ul de rutare recalculeaza caile si trimite noi mesaje de update. Acestea penetreaza reteaua, stimuland ruterele din fiecare hop pentru a rula din nou algoritmii proprii si a-si schimba tabelele de rutare in consecinta. Algoritmii dinamici pot fi insotiti de rutari statice atunci cand este posibil. De exemplu, toate mesajele care nu pot fi rutate, sau contin adrese necunoscute, pot fi transferate catre un acelasi ruter care, de obicei, trimite un mesaj de eroare corespunzator. Unele protocoale de rutare sofisticate suporta transportul pe multiple cai catre aceeasi destinatie. Spre deosebire de algoritmii de cale unica, acesti algoritmi de cale multipla permit multiplexarea traficului prin mai multe linii. Avantajele lor sunt evidente: o viteza si o fiabilitate substantial imbunatatite. Intr-un sistem de rutare pe orizontala, toate ruterele sunt egale ca importanta, in timp ce intr-un sistem ierarhic unele rutere au o importanta mai mare fata de celelalte. Ruterele principale formeaza un backbone (trunchi) de rutare spre care se indreapta toate pachetele din ramurile adiacente. Odata ajunse la un ruter de backbone, pachetele sunt transferate prin algoritmi orizontali (peer-to-peer) catre un alt ruter de backbone care raspunde de setul de ramificatii pe care se gaseste destinatarul. Transmisia se va face acum pe calea calculata in sistem ierarhic descrescator, pe ramurile optime. Pentru a fi eficiente, sistemele de rutare isi desemneaza un grup logic de noduri, denumite domenii, sisteme autonome sau zone. In sistemele ierarhice unele rutere dintr-un domeniu pot comunica cu rutere din alte domenii, in timp ce toate celelalte rutere pot comunica numai cu ruterele din domeniul propriu. In retelele foarte mari pot exista nivele ierarhice suplimentare, in care ruterele de la cel mai inalt nivel ierarhic formeaza un backbone de rutare.
Avantajul principal al rutarii ierarhice este acela ca imita organizarea societatilor comerciale. Majoritatea comunicatiilor in retea apare in interiorul unor grupuri mici ale unei companii, denumite domenii. Fiindca ruterele de intra-domeniu trebuie sa cunoasca informatii numai despre celelalte rutere din interiorul domeniului, algoritmii lor de rutare pot fi simplificati si, in functie de algoritmul de rutare folosit, traficul de mesaje update poate fi redus corespunzator. Unii algoritmi de rutare presupun ca nodul sursa ("host") va determina toata calea de transmisie. Acest procedeu poarta denumirea de rutare la sursa. Ruterele care executa o astfel de rutare reactioneaza in principal ca dispozitive de stocare si retransmitere, trimitand pachetul catre urmatorul hop, fara nici un fel de grija suplimentara.
Alti algoritmi presupun ca host-ul nu stie nimic despre rutele disponibile. In acesti algoritmi, ruterele determina calea intre retele, bazandu-se pe ultimile calcule efectuate. In primul tip de sistem, host-ul este cel care poseda "inteligenta" in timp ce in al doilea sistem ruterele inglobeaza inteligenta. Sistemele bazate pe inteligenta sursei aleg mai des rutele optime, deoarece procesul de selectie se face inainte ca pachetul sa fie trimis efectiv. Insa tot acest efort de calcul al traiectoriei implica timp suplimentar si marirea traficului de update. Algoritmii de link-state (starea legaturii) transmit informatia de rutare catre toate nodurile de comunicatie inter-retea. Fiecare ruter, totusi, trimite numai portiunea tabelului de rutare care descrie starea propriilor sale legaturi. Celalalt tip de algoritmi, bazati pe vectorul de distanta, apeleaza fiecare ruter din imediata vecinatate si ii solicita o portiune sau intreg tabelul sau de rutare. Prin urmare algoritmii de link-state trimit mesaje scurte de update catre toate ruterele, in timp ce algoritmii de distanta trimit mesaje mai consistente catre toate ruterele vecine. Datorita convergentei lor mai rapide, algoritmii de tip link-state evita formarea de bucle de rutare, insa solicita mai multa putere a unitatii centrale si mai multa memorie, comparativ cu cei bazati pe distanta. Implementarea primului tip este, de aceea, mai scumpa si poate fi facuta doar pe sisteme performante.

Criterii de performanta pentru algoritmii de rutare

Tabelele de rutare contin informa-tiile folosite de software-ul de switching pentru a selecta cea mai buna cale. Ne intrebam insa: cum sunt efectiv elaborate aceste tabele? Care este informatia pe care o contin? Cum determina algoritmii de rutare care cale este preferabila celorlalte?
Pentru minimizarea drumului parcurs de date catre destinatie, algoritmii folosesc numeroase criterii de performanta. Cei mai sofisticati combina mai multe astfel de criterii intr-un sistem hibrid. Cele mai importante determinari se refera la lungimea caii de transport, fiabilitate, intarziere totala, latime de banda, incarcare, costul comunicatiei. Evident, lungimea traseului este criteriul de performanta cel mai folosit. Unele protocoale de rutare permit administratorilor de retea sa aloce costuri arbitrare pentru fiecare legatura. Alte protocoale de rutare determina numarul de hop-uri, adica numarul de treceri prin diverse elemente de redirectionare (rutere de exemplu) prin care pachetul trebuie sa treaca in drumul sau de la sursa spre destinatie. Fiabilitatea, in contextul algoritmilor de rutare, se refera la gradul de dependenta de fiecare conexiune, exprimat in general functie de rata de eroare pe bit. Unele legaturi pot avea caderi mai numeroase decat altele, timpul de repunere in functiune fiind, si el, diferit. Orice fac-tor de fiabilitate poate fi luat in consideratie. Cuantificarea se face in valori numerice arbitrare alocate segmentelor de retea de catre administratori. Intarzierile de rutare se refera la timpul necesar transportului unui pachet de la o sursa catre o destinatie si depind de multi factori, printre care latimea de banda a legaturilor intermediare, traseu, prin algoritmul de rutare bazat pe fiabilitate si intarziere minima, scrisorii i se va atasa cozile de asteptare la porturile fiecarui ruter accesat, congestionarea traficului in toate legaturile intermediare si distanta fizica de parcurs. Deoarece intarzierile reprezinta un conglomerat de mai multe variabile importante, ele reprezinta un criteriu de performanta foarte util.
Latimea de banda se refera la capacitatea de trafic al unei legaturi. Este de la sine inteles ca o retea Ethernet de 10 Mbps este superioara unei linii inchiriate de 64 Kbps, din acest punct de vedere. Desi latimea de banda este o valoare ce exprima viteza maxima posibila pe un anumit trunchi de retea, caile care trec prin retele cu latime de banda mare nu sunt intotdeauna mai bune decat cele realizate prin retele mai lente. De exemplu, daca o legatura cu latime de banda mare este ocupata, timpul real, necesar transmisiei pachetului catre destinatie, ar putea fi mai mare. Incarcarea se refera la gradul in care o resursa de retea, cum ar fi un ruter, este ocupata. Incarcarea poate fi calculata folosind, de exemplu, gradul de utilizare a procesorului sau numarul de pachete pe secunda servite. Monitorizarea acestor parametri in mod continuu poate fi in sine un proces consumator de resurse.
Marile retele, continand subretele, grupuri sau multiple computere host, creeaza probleme speciale pentru administratorii de sistem. Ca si managerii de retele locale, administratorii unor astfel de retele trebuie sa rezolve probleme aparute din cauza echipamentului de provenienta diferita, sisteme de operare multiple si costuri suplimentare datorate noilor servicii si aplicatii la care trebuie sa adereze. In acelasi timp administratorii acestor retele se afla in fata unor dificultati de selectie si mentinere in functionare a switch-urilor, ruterelor si gateway-urilor, care permit comunicarea unui numar mare de clustere de retea. Ruterele vor conecta retele separate din punct de vedere logic, functionand cu acelasi protocol de transport, cum este Transmission Control Pro- tocol/Internet Protocol (TCP/IP). Ruterele, operand la nivelul trei al retelei din modelul de referinta OSI (Open Systems Interconnection), sunt dispozitive bazate pe protocol. De aceea ele vor trebui sa suporte orice protocol de rutare din respectiva retea locala. La nivelul retelelor locale de intreprindere putem intalni o larga varietate de protocoale. Unele sunt universale, altele sunt implementate la nivel de hardware si dependente de elementele de retea folosite. Cele mai numeroase sunt "deschise" prin aceea ca au fost standardizate de catre agentiile oficiale. Dar despre protocoale vom vorbi intr-un numar viitor.