Facultatea de Electronică, Telecomunicații și Tehnologia InformațieiUniversitatea Politehnica București

Algoritmi de rutare

Barbu CătălinBălăucă DragoșCrăciun George

Ismail BirkanMuntean Andrada

Grupa 443A

Cuprins:

Crăciun George: [6][7][8]

1. Introducere1.1 Flooding2. Principiul de Optimalitate

Muntean Andrada: [1][2][4]

3. Algoritmul "Shortest Path"3.1 SPF3.1 CSPF3.2 WSPF4. Rutarea vectorilor de distanta4.1 Algoritmul Bellman-Ford

Bălăucă Dragoș: [1][2][3]

5. Rutarea Broadcast 6. Rutarea Multicast 7. Rutarea Anycast

Barbu Cătălin: [2][4][5]

8. Rutarea in retele Ad-HocIsmail Birkan: [1][2][4] [5][6][7]

9. Concluzii9.1 Avantaje9.2 Dezavantaje

Bibliografie:

[1] “Metode de livrare Multi- , Uni-, Broad- si Anycast “, profesor C. M. Niculae[2] “Retele de calculatoare Editia a 4-a” , Andrew S. Tanenbaum[3] “ Communication as Culture”, Routledge, pag. 201–30 Carey, James (1989)[4] “Documents of American Broadcasting, fourth edition “ - Kahn, Frank J.[5] “CCNA Exploration: Routing Protocols and Concepts Computer Networks Infoacademy Bucharest”[6] "Retele de Calculatoare", Peter Norton, Dave Kearns, Editura Teora, 1999[7] „Retelele locale de calculatoare - Proiectare si Administrare” , Munteanu, A., Greavu–Serban, A., Editura Polirom, 2006;[8] Scripcariu, L., Scripcariu, I., „Retelele de calculatoare”, Editura “Tehnopress” Iaşi, 2003;

1. Introducere

Sistemul Internet este format dintr-un număr de reţele interconectate care suportă comunicaţii între calculatoare folosind un set de protocoale Internet. Aceste protocoale includ Internet Protocol (IP), Internet Control Messages Protocol (ICMP), Internet Grup Management Protocol (IGMP), şi o varietate de protocoale de nivel aplicaţie şi transport ce depind de acestea.

Toate protocoalele Internet folosesc IP ca mecanism de bază pentru transportul datelor. IP este un protocol de comunicaţie de tip datagramă sau care nu se bazează pe conexiune şi include facilităţi pentru adresare, specificaţii despre tipul serviciului, fragmentarea şi reasamblarea pachetelor şi securitate. ICMP şi IGMP sunt considerate ca fiind părţi integrante ale IP, de altfel ele sunt arhitectural, nivele peste IP. ICMP furnizează rapoarte privind erorile de transmisie, controlul fluxului, primul gateway şi alte funcţii privind mentenanţa şi controlul comunicaţiei. IGMP furnizează mecanisme prin care host-urile şi router-ele se alătură şi părăsesc un grup multicast.

Siguranţa transferurilor de date este dată în Internet de protocoalele nivelului transport şi anume de Transmission Control Protocol (TCP), care furnizează retransmisia între sursă şi destinaţie, resegmentarea şi controlul conexiunii. Serviciile care nu se bazează pe conexiune de nivel transport sunt oferite de User Datagram Protocol (UDP).

Figura 1 Suita de protocoale Internet acoperă toate nivelele modelului OSI.

Protocoalele Internet au fost dezvoltate la mijlocul anilor 1970, când DARPA (Defense Advanced Research Projects Agency) a devenit interasată de realizarea unei reţele cu comutarea pachetelor care ar fi facilitat comunicaţia între diverse sisteme informatice ale instituţiilor de cercetare. Având în minte scopul unei conectivităţi heterogene, DARPA a finanţat cercetarea Universitaţii Stanford şi a companiei BBN (Bolt, Beranek şi Newman). Rezultatul acestui efort de cercetare a fost suita de protocoale Internet, completată la sfârşitul anilor 1970.

TCP/IP a fost inclus mai târziu cu Berkeley Software Distribution (BSD) UNIX şi a devenit apoi fundamentul pe care se bazează Internetul şi World Wide Web (WWW).

Documentaţia despre protocoalele Internet (incluzând protocoalele noi sau revizuite) şi politici este specificată în raportul tehnic numit Request For Comments (RFCs), ce a fost publicat şi apoi revizuit de comunitatea Internet. Protocolul revizuit a fost publicat din nou în RFCs. Pentru a ilustra scopul protocoalelor Internet, Figura 1 reprezintă o schemă a protocoalelor din suita protocolului Internet şi nivelele corespunzătoare lor din modelul OSI.

In reţelele de calculatoare, termenul rutare se referă la selectarea căilor într-o reţea, pe care să se trimită anumite date.

Rutarea constă în transmiterea informaţiei printr-o reţea de la o sursă către o destinaţie. De-a lungul căii parcurse, este întâlnit cel puţin un nod intermediar. Rutarea este adesea în contrast cu funcţia de bridge care aparent realizează acelaşi lucru. Diferenţa principală între cele 2 este aceea că “bridging” (switching) are loc în cadrul nivelului 2 (Data link layer) al modelului de referinţă OSI, în timp ce rutarea are loc la nivelul 3 (network layer). Această diferenţă constă în utilizarea de informaţie diferită pentru rutare şi respectiv bridging, informaţie necesară în procesul transmiterii pachetelor de la sursă la destinaţie, deci aceste 2 funcţii îşi îndeplinesc rolurile în moduri diferite.

Un router dispune de 2 sau mai multe interfeţe de comunicaţie (figura 2), conectate la subreţele IP sau la linii de tip punct-la-punct. Cu toate acestea, există cel puţin o interfaţă fizică. Expedierea unei datagrame IP necesită în general ca un router să aleagă interfaţa şi adresa router-ului următor (next-hop) sau (în cazul ultimului router de pe traseu), host-ul destinaţie. Această alegere, (numită “relaying”) se face în funcţie de o bază de date care se află pe router conţinând rute. Această bază de date se mai numeşte şi tabelă de rutare. Temenul de “router” derivă din modul în care se construieşte această bază de date conţinând rute (căi); protocoalele de rutare şi configurare interacţionaeză în cadrul unui proces numit rutare.

Figura 2 Interconectarea a 2 reţele printr-un router

Baza de date conţinând rute trebuie să fie dinamică pentru a reflecta topologia curentă a sistemului de reţele interconectate. În mod normal, un router îndeplineşte acest lucru prin interacţiune cu alte routere pe baza unor algoritmi de rutare.

Ruterele furnizează numai transportul de datagrame, şi caută să reducă la minim informaţia de stare necesară efectuării acestui serviciu, avînd ca scop flexibilitatea şi robusteţea rutării.

Un sistem autonom (AS) este reţea ce constă dintr-o colecţie de subreţele (avînd ataşate host-uri) interconectate printr-un set de routere. E de preferat ca subreţelele şi routerele să fie sub controlul unei singure organizaţii ce realizează operarea şi administrarea. Într-un sistem autonom, routerele pot folosi unul sau mai multe protocoale de rutare internă, şi câteodată câteva seturi de metrici. Este de aşteptat ca un sistem autonom să dispună de un plan de rutare interioară coerent. Un sistem autonom este identificat cu un număr de sistem autonom.

Exiztă două mari tipuri de rutare care stau la baza tuturor celorlalte tipuri de rutare: rutarea statică şi rutarea dinamică.Rutarea statică descrie un sistem care ruteazăîntr-o reţea de date in funcţie de căi fixe. Rutarea dinamică construieşte dinamic tabelele de rutare, bazându-se pe informaţiile purtate de protocoale, permiţand reţelei să acţioneze în mod aproape automat pentru a evita erori şi blocaje în reţea. Datorită proprietăţilor sale, rutarea dinamică domină în momentul actual internetul.

Avantajele rutării dinamice faţa de cea statică sunt scalabilitatea si adaptibilitatea. O reţea rutată dinamică poate creşte mult mai repede şi este capabilăsăse adapteze schimbărilor din topologia reţelei aduse tocmai de această creştere sau de erorile din una sau mai multe componente ale reţelei. Într-o reţea dinamică, ruterele invaţă despre topologia reţelei comunicând cu alte rutere. Rutarea dinamică are însă şi dezavantaje, cum ar fi creşterea complexitătii.

Routarea implică două activităţi de bază: determinrea căilor optime de routare şi transportarea grupurilor de informaţii (numite pachete) prin reţea. În contextul procesului de routare, acest transport de pachete este referit caswitching. Deşi activitatea de switching de pachete este mai directă, determinarea drumului poate fi foarte complexă.

Protocoalele de routare folosesc diferite metrici pentru a evalua ce drum este optim pentru transportul unui pachet. O metrică este o măsură standard, ca de exemplu lăţimea de bandă. Pentru determinarea drumului, algoritmii de routare, iniţializează şi administrează tabele de routare, în care se află informaţii despre rute. Informaţiile din aceste tabele de routare conţin asocieri de destinaţii şi următorul "hop" ce trebuie parcurs pentru a ajunge la acea destinaţie. Când un router primeşte un pachet va încerca să asocieze adresa destinaţie a pachetului cu o adresă a unui hop imediat următor în calea acelei destinaţii, dacă nu reuşeşte probabil va distruge pachetul. În figura de mai jos se observă un scenariu de aflare a următorului hop.

Tot tabelele de routare conţin date despre starea legăturilor din reţea. Routerele comunică între ele şi îşi administrează tabelele de routare prin transmiterea unor varietăţi de mesaje. Un astfel de mesaj este mesajul updatecare conţine o parte sau toată tabela de routare a unui router. Prin analizarea acestor informaţii un router poate să-şi construiască o imagine a topologiei unei părţi din reţea (sau chiar a întregii reţele).

Metrici

Algoritmii de routare utilizează diverse metrici pentru determinarea rutei optime. Algoritmi sofisticaţi de rutare pot să facă selecţia rutelor pe baza mai multor metrici, combinându-le într-o singură metrică hibridă.

Tipuri de metrici

Lungimea drumului (length path)Este cea mai folosită metrică. De obicei este suma costurilor legăturilor drumului.

Siguranţă (reliability)Rata de erori, cât de repede se restabileşte o legătură căzută.

Întârziere (delay)Cât durează să ajungă un pachet de la o sursă la o destinaţie. Depinde de lăţimea de bandă, congestie, distanţa fizică parcursă.

Lăţimea de bandă (bandwidth)Cât trafic poate să suporte o legătură.

Încărcare (load)Se referă la gradul în care o resursă a reţelei este folosită, de exemplu un router.

Costul comunicaţiei (communication cost)Este important mai ales în companii care pot folosi liniile proprii (cost scăzut) faţă de folosirea altor linii (probabil un cost mai mare).

Protocoale de routare

Cele mai cunoscute protocoale de routare sunt:

Routing Information Protocol (RIP) Interior Gateway Routing Protocol (IGRP) Enhanced Interior Gateway Routing Protocol (Enhanced IGRP) Open Shortest Path First (OSPF) Intermediate System to Intermediate System (IS-IS) Border Gateway Protocol (BGP) Exterior Gateway Protocol (EGP) Simple Multicast Routing Protocol (SMRP) Novell RIP / Service Advertisement Protocol (SAP)

Routing Information Protocol (RIP)

Protocolul RIP este unul dintre cele mai vechi şi mai durabile protocoale. Sunt o mare varietate de protocoale asemănătoare sau bazate pe RIP. Protocolul foloseşte vectori de distanţă pentru a calcula rutele şi a alege ruta optimă. Algoritmii folosiţi în implementare au fost descoperiţi prin cercetare academică ce datează din 1957.

Standardul versiunii actuale RIP este definit în două documente: Request For Comments (RFC) 1058 şi Internet Standard (STD) 56. Odată cu creşterea numărului de reţele bazate pe adrese IP şi creşterea mărimii lor, Internet Engineering Task Force (IETF) a observat că RIP trebuie înnoit. IETF a publicat RFC 1388 în 1993, iar în 1994 a publicat RFC 1723, care descriu protocolul RIP 2 (a doua

versiune de RIP). Aceste două documente RFC descriu extensii ale protocolului, dar nu scot din uzanţă versiunea anterioară RIP. RIP 2 a mărit cantitatea de informaţii transportată de mesajele RIP, şi a permis folosirea unei metode simple de autentificare pentru securizarea operaţiei de update a tabelelor de routare. RIP 2 suportă şi măşti de reţea, o caracteristică foarte importantă pe care RIP nu o suporta.

Mesajele update

RIP trimite mesaje update la intervale regulate şi în momentul în care topologia reţelei se schimbă. Când un router primeşte un mesaj update care include schimbări pentru o rută, îşi schimbă propria tabelă de rutare pentru a reflecta schimbările din reţea. Metrica pentru lungimea acelei rute este incrementată cu 1 şi expeditorul mesajului update devine noul hop în acea rută. Routerele RIP menţin numai ruta cea mai bună (cu metrica lungimii minimă) către o destinaţie. Apoi routerul trimite mesaje update pentru a informa alte routere din reţea de schimbări. Aceste mesaje se trimit independent de mesajele regulate trimise la un interval de timp.

Metrica RIP

RIP foloseşte o singură metrică (numărul de hopuri) pentru a măsura distanţa dintre sursă şi destinaţie. Fiecare hop are asociată o valoare (în mod uzual 1). Când un router primeşte un update adaugă 1 la metricile destinaţiilor cu rute schimbate. Adresa IP a expeditorului este folosită ca următorul hop pentru acele rute.

Stabilitatea RIP

RIP previne routing loops prin implementarea unei limite a numărului maxim de hopuri permise într-o rută. Acest maxim este 15. Dacă un router primeşte un mesaj update care conţine o rută cu o metrică 15, destinaţia este considerată neaccesibilă (unreachable). Deficienţa acestei trăsături este limita maximă a diametrului unei reţele RIP. RIP mai implementează mecanisme de stabilitate care sunt comnune multor protocoale de routare: split horizon şi holddown. Acestea asigură stabilitate chiar dacă sunt posibile schimbări rapide în topologia reţelei.

RIP Timers

RIP foloseşte timere (cronometre) pentru a-şi regla parametrii. Acestea includ routing-update timer, route-timeout timer, route-flush timer. Routing-update timer măsoară intervalul de timp scurs între update-uri. De obicei este 30 secunde. Fiecare intrare dintr-o tabelă de routare are un route-timeout timer asociat. Când acesta expiră, ruta este marcată ca invalidă, dar rămâne în tabelă până când expiră şi route-flush timer.

2. Algoritmul inundarii (Flooding)

Inundarea (Flooding) este un algoritm static, in care orice pachet de intrare este emis pe toate liniile de iesire din nod, cu exceptia liniei pe care a sosit. Inundarea genereaza astfel un numar excesiv de mare de pachete duplicate, care, daca nu sunt luate masuri de prevedere speciale, pot conduce la aparitia unor situatii nedorite de blocare a intregi retele.

Prin aplicarea algoritmului de inundare a iesirilor probabilitatea ca orice pachet sa ajunga in final la destinatia sa este suficient de mare, desi pachetele nu sunt orientate direct de sursa prin ruta optima. Totusi nu trebuie eliminat riscul congestionarii retelei in ansamblu, prin migrarea haotica a copiilor de pachete in speranta atingerii destinatiilor adecvate, si chiar a nodurilor particulare, care primesc in mod repetat aceleasi pachete.

Au fost create diferite mecanisme care limiteaza multiplicarea pachetelor prin procesul de inundare a iesirilor:

1. Limitarea drumului prin retea. Sursa introduce in eticheta pachetului o informatie de contorizare, care reprezinta numarul maxim de salturi (de noduri traversate) ce pot fi efectuate in retea. Acest contur va fi decrementat la fiecare tranzit suferit de pachet intr-un nod pe ruta sa spre destinatie. Cand valoarea contorului devine nul, pachetul este distrus.

In mod ideal, contorul se initializeaza cu lungimea drumului dintre sursa si destinatie (exprimata in numar de salturi si cunoscuta eventual cu ajutorul algoritmului de autoinvatare). Daca sursa nu cunoaste cat de mare este aceasta lungime, atunci contorul poate fi initializat pentru cazul cel mai defavorabil: distanta cea mai mare din retea.

Pentru a preintampina situatiile critice, cand o parte a retelei este in deranjament si este scoasa din functiune, valorile respective ale contorului, se pot majora cu un coeficient de siguranta. In plus, la destinatie este necesara tinerea unei evidente a pacheteleor receptionate, pentru a putea elimina copiile.

2. Verificarea identitatii pachetelor primite. Fiecare sursa numeroteaza secvential pachetele pe care le introduce in retea. De asemenea, fecare nod isi construieste liste pentru fiecare sursa, continand numerele pachetelor deja primite. Daca un pachet se afla pe o asemenea lista, atunci el va fi distrus.

Pentru ca listele sa nu creasca nelimitat, trebuie ca fiecare din ele sa fie asociata cu un contor k. Contorul precizeaza ca toate pachetele cu un numar secvential sub k au fost deja primite, deci lista completa a acestora nu mai este necesara.

3. Inundare selectiva. Nodul de tranzit nu trimite un pachet pe orice linie de iesire, ci doar pe acelea care “conduc” pachetul pe directia aproximativ buna. Metoda poate fi aplicata doar in cazul retelelor cu o structura regulata; un pachet sosit dinspre vest este orientat in directia estica a retelei.

4. Rutarea aleatoare. Pe directia aproximativ buna, nodul de tranzit alege la intamplare o singura iesire (se utilizeaza superior diferitele trasee; algoritmul este foarte robust).

Inundarea nu este o metoda practica pentru orice aplicatie. Pentru retelele militare ea asigura o garantie sporita a mentinerii momunicatiilor, daca ne gandim ca in situatii conflictuale in orice moment rutele optime pot fi “distruse” si exact atunci mentinerea legaturilor este deosebit de importanta. De asemenea, inundarea este recomandata aplicatiilor de baze de date distribuite, in care este necesara uneori reactualizarea tuturor datelor concurente. poate cea mai importanta utilizare a algoritmului de inundare este aceea de a furniza o masura de comparare cu alti algoritmi: inundarea alege totodata calea cea mai scurta dintre mai multe cai paralele.

3. Principiul optimalitătii (optimality principie)

Consecinta directa a principiului de optimizare este aceea ca setul cailor optime care pleaca de la toate sursele din retea si care sunt relative la o destinatie data, formeaza un arbore cu radacina in nodul destinatie. Acesta este numit arbore colector si nu este cu necesitate unic.

Principiul optimalitătii stabileşte că dacă ruterul J este pe calea optimă de la ruterul I către ruterul K, atunci calea optimă de la J la K este pe aceeaşi rută. Pentru a vedea aceasta, să notăm cu r, partea din cale de la I la J, iar cu r2 restul rutei. Dacă ar exista o rută mai bună decât r2 de la J la K, ea ar putea fi concatenată cu r1 şi ar îmbunătăţi ruta de la I la K, ceea ce ar contrazice presupunerea că r 1 r 2 este optimală.

Figura 3 (a) O subreţea. (b) Un arbore de scufundare pentru ruterul B.

Acest arbore se numeşte arbore de scufundare (sink tree) ,unde distanţa metrica aleasă este numărul de salturi. Arborele de scufundare nu este unic, putând exista şi alţi arbori cu aceeaşi lungime a căii.

Scopul tuturor algoritmilor de dirijare este de a descoperi şi folosi arborii de scufundare pentru toate ruterele. El nu conţine bucle, deci fiecare pachet va fi livrat într-un număr finit şi limitat de salturi. în practică viaţa nu este chiar aşa de uşoară. Legăturile şi ruterele pot să se defecteze şi să-şi revină în timpul operaţiilor, astfel încât diferite rutere pot avea imagini diferite asupra topologiei curente. De aceea este imperios necesar ca nodurile sa culeaga si sa foloseasca informatii reale asupra relatiei, in scopul stafilirii unor rute optime pentru indrumarea pachetelor proprii sau ale celor tranzitate.

In raport cu informatiile primite, nodul are posibilitatea sa creeze rute de indrumare adaptate conditiilor reale, adica sa realizeze o indrumare adaptiva. Pe toata perioada de mentinere a valabilitatii informatiilor se pastreaza acelasi set de rute, care conduc la efectuarea unei indrumari fixe (permanent sau numai pe un timp limitat). Daca nodurile nu pot cunoaste sau nu pot tine seama de conditiile de trafic si de ocupare a retelei, ele vor folosi asa numitii algoritmi statistici, bazati pe elementele constructive fixe ale retelei (topologie si distante fixe intre noduri).

Fiecare nod detine o tabela de costuri, in care coloanele corespund nodurilor vecine, iar liniile se completeaza pentru nodurile de destinatie. Continutul fiecarei locatii din tablou reprezinta costul drumului catre destinatie de-a lungul arborelui colector care contine nodul vecin corespunzator.

4. Algoritmul Bellman-Ford

Algoritmul Bellman - Ford este un algoritm care calculează cea mai scurtă cale de la un singur nod sursă la toate celelalte nodurile dintr-o digraph ponderat . Este mai lent decât algoritmul lui Dijkstra pentru aceeași problemă , dar mai versatil , deoarece este capabil de manipulare grafice în care unele dintre greutățile de margine sunt numere negative . Algoritmul este , de obicei, numit după doi dintre dezvoltatori , Richard Bellman și Lester Ford , Jr. , care a publicat în 1958 și 1956 , respectiv , cu toate acestea , Edward F. Moore a publicat , de asemenea, același algoritm în 1957 , și pentru acest motiv, este de asemenea, uneori numit algoritmul Bellman - Ford - Moore . Greutăți margine negative sunt găsite în diverse aplicații de grafice , prin urmare, utilitatea acestui algoritm . În cazul în care un grafic conține un " ciclu negativ " ( de exemplu, un ciclu al cărui sumă margini la o valoare negativă ) , care este accesibil de la sursa , atunci nu există nici o cale mai ieftină : orice cale poate fi mai ieftin cu mai mult de o plimbare în jurul ciclu negativ . În acest caz ,algoritmul Bellman - Ford poate detecta ciclurile negative și raportează existența lor . Ca si Algoritmul lui Dijkstra , Bellman - Ford se bazează pe principiul de relaxare , în care o aproximare la distanța corectă este înlocuită treptat cu valori mai precise până la atingerea în cele din urmă soluția optimă . În ambele algoritmi , distanța aproximativă a fiecărui vârf este întotdeauna o supraestimaredistanța reală , și se înlocuiește cuminimul valorii sale vechi culungimea unui traseu nou găsit . Cu toate acestea , algoritmul lui Dijkstra selectează lăcomienodul - greutate minimă care nu a fost încă prelucrate , și realizează acest proces relaxare pe toate marginile sale de ieșire , în contrast , algoritmul Bellman - Ford pur și simplu relaxează toate marginile , și face acest lucru | V | - 1 ori , unde | V | este numărul de vârfuri în grafic . În fiecare dintre aceste repetiții , numărul de noduri cu distanțe calculate corect crește , din care rezultă că în cele din urmă toate nodurile vor avea distanțele lor corecte . Această metodă permitealgoritmul Bellman - Ford pentru a fi aplicat la o clasă mai largă de intrări decât Dijkstra .

O variantă distribuită a algoritmului Bellman - Ford este folosit în protocoale de rutare distanță prin vectori , de exempluRouting Information Protocol ( RIP ) . Algoritmul este distribuit deoarece implică un număr de noduri ( routere ), în cadrul unui sistem autonom , o colecție de rețele IP de obicei, deținută de un ISP . Se compune din următoarele etape :

    1)Fiecare nod calculează distanțele dintre sine și toate celelalte noduri din cadrul auxiliar și stochează această informație ca un tabel .    2)Fiecare nod trimite tabelul care toate nodurile vecine .    3)Atunci când un nod primește mese distanta de la vecinii săi , se calculează rutele cele mai scurte la toate celelalte noduri și actualizează propria masă pentru a reflecta orice schimbări .  Modificări în topologie de rețea nu sunt reflectate repede, deoarece actualizările sunt răspândite - nod - de nod .    Numără până la infinit ( în cazul în care link-ul sau nod eșecuri face un nod de neatins de la un anumit set de alte noduri , aceste noduri pot petrece totdeauna în creștere treptat estimările lor privind distanța de ea , și în același timp s-ar putea fi de rutare bucle ) .

5. Rutarea Broadcast. Rutarea Multicast. Rutarea Anycast.

BroadcastIn unele aplicatii calculatoarele gazda au nevoie sa trimita mesaje catre mai multe sau catre toate

celelalte calculatoare gazda. Trimiterea simultana a unui pachet catre toate destinatiile se numeste difuzare (broadcast)l mai multe metode pentru realizarea ei au fost propuse.

O metoda de difuzare care nu are cerinte speciale pentru subretea este ca sursa sa trimita un pachet distinct catre fiecare destinatie. Metoda este nu numai consumatoare de latime de banda, dar ea cere ca sursa sa detina o lista completa a tuturor destinatiilor. S-ar putea ca in practica aceasta sa fie singura metoda utilizabila, insa ea este metoda cea mai putin dorita.

Exista un numar de adrese care sunt utilizate pentru broadcast IP. Toate utlizeaza conventia cu toti bitii 1 indica catre toti. Adresele broadcast nu sunt niciodata valide ca adrese sursa, ci numai ca adrese destinatie. Diferitele tipuri de adrese broadcast sunt listate in continuare.

Adresa broadcast limitata:

Adresa 255.255.255.255 este utilizata in retele care suporta broadcasting-ul precum LAN si se refera la toate calculatoarele din subretea. Nu necesita ca hostul sa cunoasca vreo informatie despre configurarea IP. Toate calculatoarele din reteaua locala vor recunoaste adresa, dar ruterele nu vor trimite niciodata mai departe aceste mesaje. Esista o singuga exceptie de la aceasta regula, numita

BOOTP forwardin. Protocolul BOOTP utiizeaza adresa broadcast limitata pentru a permite statiilor de lucru fara disc sa contacteze un server de boot. BOOTP forwarding este o optiune de configurare disponibila pe anumite rutere de a face o exceptie pentru datagramele UDP pentru portul 67 (utilizat de protocolul BOOTP). Fara aceasta facilitate, fiecare subretea ar trebui dotata cu un server BOOTP. Totusi, aceasta nu este un simplu forwarding deoarece ruterul are si alt rol in protocolul BOOTP.

Adrese broadcast pentru o retea specificata (Network-Directed Broadcast Adress)

Daca numarul de retea este un numar valabil, reteaua nu este divizata in subretele si bitii numarului host sunt toti 1, atunci adresa se refera la toate calculatoarele din reteaua specificata. Ruterele trebuie sa trimita mai departe aceste mesaje broadcast cu exceptia situatiei cand sunt configurate altfel. Acest tip de adresa este utilizat in cererile ARP in retele subdivizate.

Adrese broadcast pentru o subretea specificata (Subnet-Directed Broadcast Adress)

Daca numarul de retea este un numar valabil de retea, numarul de subretea este un numar de subretea valabil si bitii numarului de host sunt toti 1, atunci adresa se refera la toate calculatoarele host din subreteaua specificata. Deoarece subreteaua emitentului si subreteaua destinatie pot avea diferite mastri de subretea, emitentul trebuie, intr-un mod oarecare, sa afle masca de subretea in uz de destinatie. Broadcastul efectiv este afectat de catre ruterul care primeste datagrama in subretea.

Inundarea (Flooding) este un alt candidat evident. Desi inundarea este nepotrivita pentru comunicatia obisnuita capat la capat, pentru difuzare ar trebui luata in serios in considerare mai ales daca nici una dintre metodele ce vor fi descrise in continuare nu este aplicabila. Problema folosirii inundarii ca metoda de difuzare este aceasi cu problema ivita la folosirea sa ca algoritm de dirijare capat la capat: genereaza prea multe pachete si consuma latime de banda prea mare.

6. Multidestination

Al treilea algoritm este dirijarea multidestinatie (multidestination routing). Daca se foloseste aceasta metoda, fiecare pachet contine fie o lista a destinatiilor, fie o harta de biti care indinca destinatiile dorite. Atunci cand un pachet ajunge la un ruter, ruterul verifica toate destinatiile pentru a determina setul liniilor de iesire pe care trebuie trimis pachetu. O linie de iesire este selectata daca este calea cea mai buna pentru cel putin o destinatie. Ruterul genereaza o noua copie a pachetului pnetru fiecare linie de iesire folosita si include in fiecare pachet doar acele destinatii care folosesc linia respectiva. Efectul este partitionarea multimii destinatiilor intre liniile de iesire. Dupa un numar suficient de salturi, fiecare pachet va contine o singura destinatie si poate fi tratat ca un pachet normal. Dirijarea multidestinatie este asemanatoare trimiterii separatate a mai multor pachete catre adresele destinatie, cu exceptia faptului ca atunci cand mai multe pachete trebuie sa urmeze aceasi cale, unul dintre ele plateste tot drumul, iar celelalte calatoresc gratuit.

Unele aplicatii necesita ca procese aflatela mari distante unele de altele sa lucreze in grup, de exemplu, un grup de procese care implementeaza o baza de date distribuite. In aceste situatii, este adesea necesar ca un proces sa trimita un mesaj catre toti ceilalti membri ai grupului. Daca grupul este mic, el poate trimite fiecarui partener un mesaj capat la capat. Daca grupul este mare, aceasta strategie este costisitoare. Uneori se poate folosi difuzarea, dar folosirea difuzarii pentru a anunta 1000 de masini intr-o retea cu un milion de noduri este ineficienta, deoarece majoritatea receptorilor nu sunt interesati de

mesaj. De aceea, avem nevoie de o modalitate de a trimite mesake spre grupuri bine definite, care contin un numar mare de noduri, dar totusi redus fata de dimensiunea intregii retele.

7. Multicast

Trimiterea unui mesaj catre un astfel de grup se numeste multicasting, iar algoritmul de dirijare asociat se numeste dirijare multicast (multicast routing). In aceasta sectiune, vom descrie o modalitate de a realiza dirijarea multi-cast.

Dirijarea multicast necesita managementul grupului. Trebuie sa existe modalitati de a crea si distruge grupuri si de a permite proceselor sa intre in grupuri sau sa le paraseasca. Cum se realizaeaza aceste functii nu este treaba algoritmului de dirijare. Important pentru algoritmul de dirijare este ca atunci cand un proces se atasaza unui grup el trebuie sa informeze gazda sa despre aceasta. Este important ca ruterele sa stie caror grupuri le apartin calculatoarele gazda asociate. Fie calculatoarele gazda trebuie sa anunte ruterul asociat la producerea unei modificari in alcatuirea grupurilor, fie ruterul trebuie sa interogheze periodic aceste calculatoare gazda. In ambele cazuri, ruterul afla din ce grupuri fac parte calculatoarele gazda. Ruterele isi informeaza vecinii, astfel ca informatia se propaga prin subretea.

Pentru a realiza dirijarea multicast, fiecare ruter calculeaza arborele de acoperire care acopera toate celelalte rutere din retea. De exemplu, in figura de mai jos avem doua grupuri 1 si 2. Unele rutere sunt atasate la calculatoarele gaza care apartin unuia sau ambelor grupuri, asa cum se iundica in figura. Un arbore de acoperire pentru cel mai din stanga ruter este prezentat in figura b).

Atunci cand un proces trimite un pachet multicast catre un grup, primul ruter isi examineaza arborele de acoperire si il reteaza, eliminand toate liniile care nu conduc catre calculatoarele gazda, membre ale grupului. In exemplul nostru, figura arata arborele de acoperire retezat pentru grupul 1. Similar, figura b) arata arborele de acoperire retezat pentru grupul 2. Pachetele multicast sunt dirijate doar de-a lungul arborelui de acoperire corespunzator.

Sunt posibile mai multe moduri de retezare a arborelui de acoperire. Cel mai simplu se poate folosi daca se utilizeaza dirijarea bazata pe starea legaturilor si fiecare ruter cunoaste intreaga topologie a subretelei, inclusiv apartenenta calculatoarelor gazda la grupuri. Atunci arborele poate fi retezat pornind de la sfarsitul fiecarei cai, mergand spre radacina si eliminand toate ruterele care nu apartin grupului respectiv.

In cazul dirijarii folosind vectori distanta , poate fi aplicata o alta strategie de retezare a arborelui. Algoritmul de baza folosit este trimiterea pe calea inversa. Oricum, ori de cate ori un ruter fara nici un calculator gazda interesat de un anume grup si fara nici o conexiune la alte rutere primeste un mesaj multicast pentru acel grup el va raspunde cu un mesaj PRUNE (retezare), anuntand expeditorului sa nu ii mai trimita mesaje multicast pentru acel grup. Cand un ruter care nu are printre calculatoarele gazda nici un membru al vreunui grup primeste astfel de mesaje pe toate liniile sale, el poate de asemenea sa raspunda cu un mesaj PRUNE. In acest fel subreteaua este retezata recursiv.

Un potential dezavantaj al acestui algoritm este acela ca se comporta deficitar in cazul retelelor extinse. Sa presupunem ca o retea are n grupuri, fiecare cu un numar mediu de m membri. Pentru fiecare grup, trebuie memorati m arbori de acoperire retezati deci un total de mn arbori. Daca exista multe grupuri mari, atunci, pentru a memora toti arborii, este necesar un spatiu de memorie considerabil.

Pentru a putea transmite multicast este nevoie atat de infrastructura de nivel 3 multicast, cat si de suport din partea nivelului de aplicatie. Cu alte cuvinte atat la sursa cat si la destinatie este instalata aplicatia de multicast care sa trimita pachete cu adresa destinatie adresa grupului de multicast si care sa

stie sa primeasca si sa interpreteze aceste pachete la destinatie. Transmisia multicast are nevoie de urmatoarele componeste pentru a functiona corect:

O clasa speciala de adrese din care se vor delega adrese pentru fiecare grup multicast. Aceasta este identificata ca fiind clasa D din protocolul IP: 224.0.0.0 – 239.255.255.255. Adresele calsei D pot fi usor recunoscute prin primii 4 biti ai primului octet: 1110;

Fiecare grup trebuie sa fie identificat de o adresa din spatiul clasei D. O astfel de adresa nu poate fi folosita decat ca adresa destinatie, niciodata ca adresa sursa. Fata de IP unicast, multicast nu este folosit pentru a identificatii sau echipamente, ci doar grupuri destinatie;

Aplicatia multicast trebuie instalata pe toate statiile ce doresc sa primeasca stream-ul de la server. De asemenea, acesta trebuie configurata sa asculte pe aceasi adresa IP pe care serverul trimite traficul;

O metoda standard de a calcula o adresa de nivel 2 dintr-o adresa de multicast de nivel 3 . Pentru ca in stiva TCP/IP se verifica mai intai adresa MAC, trebuie sa existe o asociere intre o adresa multicast de nivel 3 si adresa multicast de nivel 2. Cu alte cuvinte, cand o aplicatie client de multicast porneste si este configurata cu adresa IP a grupului de multicast, ea va deduce in mod standard o adresa MAC din adresa IP si va configura placa de retea sa asculte pe acea adresa MAC pentru traficul de la server.

Un mecanism prin care statiile dintr-o retea locala sa poata semnala router-ului gateway faptul ca doresc sa primeasca trafic pentru un grup semnalat. Totodata, trebuie sa existe o metoda prin care o statie sa poata parasi un grup de multicast. Aceste functionalitati sunt oferite prin intermediul protocolului Internet Group Management Protocol (IGMP).

Un protocol de rutare multicast care sa transmita streamul peste infrastructura de nivel 3. Cele mai cunoscute protocoale ce indeplinesc acest scop sunt: Distance Vector Multicast Routing Protocol (DVMRP), Protocol Independent Multicast (PIM), Multicast OSPF.

7.1 Adresarea Multicast

Existenta unui spatiul de adrese IP alocat transmisiilor multicast este vitala in functionarea conceptului de IP Multicast. In paradigma uniscat, o adresa IP reprezenta un nod de aceea se realizeaza asignarea acesteia pe o interfata a respectivului nod. In contrast, o adresa multicast reprezinta un grup de destinatari si nu este niciodata asignata unui dispozitiv. Singurul loc in care acest tip de adresa este folosita este campul de IP destinatie din antetul IP pentru ca dispozitivele de rutare sa recunoasca acel pachet ca facand parte dintr-un stream de la sursa: IP_SURSA si destinat grupului: IP_DESTINATIE

7.2 Rutarea Unicast

Principalul atribut al unui protocol de rutare unicast este propagarea rutelor in mod dinamic intre mai multe rutere. Pentru a atinge acest scop, orice IGP (Interior Gateway Protocol) porneste prin a anunta retelele sale direct conectate tuturor vecinilor sai pentru ca acestia sa le anunte mai departe. Astfel dupa un anumit timp de convergenta ce depinde de protocolul folosit, toate ruterele vor cunoaste cea mai scurta cale catre orice destinatie, pe baza metricii folosite.

Din acest comportament reiese faptul ca un protocol de rutare IGP unicast nu ar putea niciodata sa directioneze trafic multicast din cauza faptului ca adresele de multicast nu se asigneaza niciodata pe interfete.

Un protocol de rutare multicast nu este interesat de propagarea retelelor direct conectate, cide construirea celei mai bune cai de la sursa de multicast la destinatia de multicast peste o retea de nivel 3. Exista doua tipuri de protocoale de rutare multicast folosite in implementari reale:

Protocoale dense – sunt preferate in momentul in care exista cel putin un destinatar in fiecare subretea dintr-o anumita arie geografica

Protocoale sparse – sunt preferate in momentul in care destinatarii multicast sunt grupati in putine subretele dintr-o anumita arie geografica

In prezent cele mai cunoscute protocoale de rutare multicast sunt: Protocol Independent Multicast Dense Mode (PIM-DM), Protocol Independent Multicast Sparse Mode (PIM-SM), Multicast OSPF (MOSPF), Distance Vector Multicast Routing Protocol (DVMRP). Dintre acestea PIM-SM si PIM-DM conduc detasat in topul de popularitate, MOSPF si DVMRP nefiind nici macar suportate complet pe rutere Cisco.

7.2.1 Adresarea Unicast

Adresarea unicast este elementul fundamental al oricarui tip de transmisie in internet. O adresa Ipv6 are o dimensiune de 128bit iar o structura de adresare plata pentru Ipv6 ar insemna ca fiecare ruter din Internet sa tina toate adresele destinatie din lume, o solutie complet nescalabila. In mod evident, ca si in cazul Ipv4, exista nevoia unei structuri de adresare ierarhica in Ipv6 folosind conceptul de masca de retea. Din cauza dimensiunii mari ai unei adrese Ipv6 singura solutie acceptata pentru masca de retea este folosind simbolul „/” urmat de un numar de la 0 la 128 ce semnifica numarul de biti setati la valoarea „1” de la inceputul mastii, ca si in cazul IPv4.

Exemplu: 2001:410:0:1::/64

Adresele unicast pot fi de 3 tipuri, in functie de domeniul lor de vizibilitate in retea:

Global unicast – IP-urile din aceasta categorie poarta numele de global unicast addresses (GUAs)

Link-local – IP-urile din aceasta categorie poarta numele de link local addresses

Unique-local – IP-urile din aceasta categorie poarta numele de unicast local addresses (ULAs)

8. Rutare si protocoale de rutare in retele ad-hoc

Reţelele ad hoc reprezintă reţelele mobile,dinamice care nu necesită o arhitectură fixă sau procese de configurare. Implementarea unor astfel de reţele reprezintă o direcţie deosebită în care se îndreaptă noile generaţii de comunicaţie. Aplicaţiile sunt diverse şi se bazează foarte mult pe proprietăţile de mobilitate şi auto organizare. Cum intersul pentru astfel de reţele creşte pe zi ce trece,este nevoie şi de o creştere de performanţă . Performanţa unei reţele ad hoc este dată în principal de modul în care protocoalele de rutare organizează comunicarea. Este nevoie de protocoale de rutare dinamice, rapide, care să facă faţă cu succes schimbărilor dese de topologie.

Tipuri de Retele ad-hoc

Rețelele ad-hoc pot fi clasificate în mai multe tipuri în functie de aplicațiile în care acestea sunt folosite:

- Retele ad-hoc mobile (MANET - Mobile Ad-hoc NETworks) .

- Reţele wireless de tip plasă (WMN - Wireless Mesh NETworks ).

- Reţele wireless de senzori (WSN - Wireless Sensor NETworks) .

Rețelele ad-hoc mobile (MANET)

O reţea mobila ad-hoc ( MANET) este un tip descentralizat de reţea formată din dispozitive mobile care se deplasează independent în orice direcţie, prin urmare îşi va schimba frecvent conexiunile cu celelalte dispozitive din reţea. Rețelele ad-hoc mobile pot fi implementate cu diverse tehnologii wireless cum ar fi standardul 802.11/WiFi , transmisia celulară sau prin satelit. Principala provocare în construirea unei MANET este echiparea fiecărui dispozitiv astfel încât să menţină în permanență informațiile necesare pentru a ruta traficul în mod corespunzător. Aceste rețele pot funcționa separat sau poate fi conectate la Internet.

Reţelele ad-hoc moblile (MANET) se împart în trei categorii:

-Reţele ad-hoc Vehiculare (VANET): sunt utilizate pentru comunicarea între vehicule şiechipamentele instalate la marginea drumului.

-Reţele ad-hoc Vehiculare Inteligente (InVANET): sunt un fel de inteligență artificială, care ajută vehiculele să se comporte în mod inteligent în timpul ,coliziunilor vehicul-vehicul,accidente etc.

-Reţele ad-hoc mobile bazate pe Internet (iMANET): acest tip de reţea face legătura dintre dispozitivele mobile din cadrul uni MANET şi Internet.

Rețelele wireless de tip plasă (WMN)

O rețea wireless de tip plasă (WMN) este o rețea de comunicații formată din noduri radio organizate într-o topologie de tip plasă (mesh). O rețea plasă este de încredere și oferă redundanță. Când un nod nu mai poate funcționa, restul de noduri pot comunica încă între ele, în mod direct sau prin noduri intermediare. Rețelele wireless de tip plasă pot fi implementate cu diverse tehnologii wireless , respectiv 802.11 , 802.15 , 802.16 sau tehnologiile celulare.

Reţele wireless de senzori (WSN)

O rețea de senzori wireless (WSN) este alcătuită din senzori autonomi distribuiţi spaţial cu scopul de a monitoriza condițiile fizice sau de mediu, cum ar fi temperatura, sunetul, presiunea,umiditatea etc. și pentru a transfera datele rezultate prin intermediul reţelei la o locație principală. Cele mai multe rețele de senzori moderne sunt bidirecţionale, cu rolul de a permite controlul activităţii senzorilor. Dezvoltarea de rețele de senzori wireless a fost motivată de aplicaţiile militare, cum ar fi supravegherea câmpului de luptă; astăzi aceste rețele sunt folosite în multe aplicații industriale și de consum, cum ar fi monitorizarea stării de sănătate. În informatică și telecomunicații, rețele de senzori wireless sunt un domeniu de cercetare activ cu numeroase ateliere de lucru și conferințe organizate în fiecare an .

În reţelele ad hoc, nu există staţii de bază fixe, modul DCF fiind cel utilizat.Principiul de funcţionare al modului DCF constă în ascultarea mediului pentru a vedea dacă o altă staţie va emite. Staţia trebuie să se asigure că mediul este liber pentru o anumită durata în ainte de a emite. Dacă mediul este liber în acest timp, sursa poate începe emiterea datelor, iar în caz contrar transmisia este amânată pentru o perioadă de timp aleasa aleatoriu, după care staţia va reîncerca să trasmita din. Totuşi, dacă cel puţin două staţii emit simultan, poate apărea o coliziune care din păcate nu poate fi detectată de staţia emitentă. Pentru această situaţie se utilizează o "confirmare" (ACK-acknowledgement) cu scopul de a informa staţia emitentă că a fost recepţionat cu succes cadrul.Staţia emitentă trimite mai întâi un mesaj scurt RTS (Request To Send) conţinând destinaţia şi durata transmisiei. Celelalte staţii ştiu astfel că mediul va fi ocupat în timpul acesta. Destinaţia, dacă mediul este liber, va permite sursei să transmită, emiţând un mesaj scurt CTS (Clear To Send) care indică sursei că poate începe să emită datele fără riscul unei coliziuni.

Caracteristicile reţelelor ad-hoc sunt următoarele:

-Mobilitatea: amplasarea rapidă a reţelei în zone în care nu exista o infrastructură fixa. Putem avea mobilitate individuală aleatorie, mobilitate de grup, mișcare de-a lungul rutelor pre-planificate etc. Mobilitatea poate avea un impact major asupra selecției unui sistem de rutare și poate astfel să influențeze performanţa.

-Rețea de tip multihop: este o rețea în care calea unui pachet de date trimis de la sursă parcurge un număr de noduri intemediare pentru a ajunge la destinaţie.

-Auto-organizare: rețeaua ad-hoc trebuie să îşi stabilească în mod independent parametrii proprii de configurare cum ar fi: adresarea, rutarea, poziția de identificare, controlul puterii etc. În unele cazuri,

nodurile speciale (de exemplu nodurile de baza mobile) se pot coordona în mişcare astfel încât să fie distribuite dinamic în arii geografice pentru care pot furniza acoperire porţiunilor de reţea deconectate.

-Conservarea energiei: cele mai multe noduri ad-hoc (de exemplu, laptop-uri, PDA-uri, senzori etc.) au o alimentare limitată și nu au capacitatea de a-şi genera singure energie (de exemplu,panouri solare). Un protocol eficient de conservare a energiei (de exemplu rutarea, descoperirea resurselor etc.) este esențial pentru longevitatea misiunii.

-Scalabilitate: în unele aplicații o rețea ad-hoc pot ajunge la câteva mii de noduri, această caracteristică dovedindu-se a fi destul de problematică. Pentru o reţea wireless scalabilitatea rețelelor este simplu de manipulat folosind o structură ierarhică.

-Securitatea: Reţelele wireless sunt relativ mai puţin sigure decât cele cablate, datorită accesului mai facil la reţea al persoanelor neautorizate aflate în zonele de acoperire ale punctelor de acces. Există implicit în implementarea reţelelor wireless diferite bariere care formează aşa numita securitate de bază a reţelelor wireless, care împiedică accesul neintenţionat al persoanelor străine de reţea, aflate în aria de acoperire a unui punct de acces.

-Conexiune la Internet: Reţelele ad hoc pot fi configurate astfel încât să poată comunica şi cu reţele externe care au conexiune la Internet, precum reţele wireless locale, prin intermediul unor dispozitive de tranziţie. Un exemplu de astfel de dipozitiv este routerul.

Probleme intalnite in retelele ad hoc

Într-o reţea fără fir, doua mobile pot comunica prin emitere de unde radio. Ele se partajează într-un mediu unic, însă nu pot emite în acelaşi timp. Astfel, protocolul de acces mediu a fost definit în scopul de a gestiona accesul concurent la acelaşi mediu partajat. Acest protocol face parte din familia protocoalelor de gestiune cu acces multiplu prin detectarea purtătorilor şi a coliziunilor (Carrier Sense Multiple Access with Collision Avoidance / CSMA/CĂ). El asociază un mecanism de detectare a purtătorilor înaintea transmisiei unui mecanism de aşteptare aleatorie ce permite limitarea numărului şi impactului coliziunilor.

În plus, standardul defineşte un mecanism suplimentar RTS/CTS (Request To Send/Clear To Send) pentru a evita coliziunile şi problemele nodurilor ascunse.Problema staţiei ascunse apare când două staţii nu se pot recepţiona reciproc din cauza distanţei sau a obstacolelor.

Protocoale de rutare bazate pe vectori distanta in retele ad hoc

Dezvoltarea unui suport pentru rutare în rețele ad-hoc este una dintre cele mai importante provocări și este esențială pentru operațiunile de bază din rețea. Anumite combinaţii unice decaracteristici fac rutarea în rețele ad-hoc să fie interesantă.În primul rând, nodurilor dintr-o rețea ad-hoc li se permite să se miște într-un mod necontrolat.Aceste noduri mobile alcătuiesc o rețea extrem de dinamică, în care se produc schimbări rapide de topologie şi din această cauză apar frecvent probleme de rutate a pachetelor. Un bun protocol de rutate pentru acest tip de reţea trebiue să se adapteze dinamic în funcţie de schimbările care pot să apară în topologie.

În al doilea rând, accesul la mediu este partajat, canalul wireless de bază oferind o lățime de bandă mult mai mică și mai variabilă decât la rețelele cu fir. Din acest punct de vedere protocoalele de rutare trebuie să folosească eficient lăţimea de banda astfel încât o mare parte din restul lăţimii de banda trebuie să rămână disponibilă pentru comunicațiile de date reale.

În al treilea rând, nodurile din reţea folosesc baterii care au o alimentare cu energie limitată. Pentru ca nodurile să rămână și să comunice pentru perioade mai lungi, este de dorit ca un protocol de rutare să fie eficient din punct de vedere energetic.

În cadrul releleor ad-hoc protocoalele de rutare folosite se împart în trei categorii : protocoale de rutare proactive , protocoale de rutare reactive şi protocoale de rutare hibride.

-Protocoalele de rutare proactive oferă performante bune în găsire rapidă a rutei şi sunt bazate pe tabela de rutare. Avantajul acestui tip de protocol de rutate este că, după stabilirea rutelor,acestea vor fi întotdeauna disponibile şi au ca dezavantaj supraîncărcarea continuă a reţelei din cauza traficului de control.

-Protocoale de rutare reactive sunt stabilite la cerere, acestea nu îşi actualizează permanent tabela de rutare şi nu au o tabelă de rutare permanentă. Principalul dezavantaj al folosirii unui protocol reactiv constă în inundarea reţelei cu mesaje trimise de către echipamente care nu au nici o posibilitate de a comunica cu echipamentul solicitat.

Protocoale de rutare proactive

Protocoalele de rutare proactive se mai numesc şi "table-driven" adică fiecare nod îşi poate construi singur tabela de rutare prin schimbul de informaţii intre nodurile din reţea. Acest lucru se realizează prin schimbul de mesaje de actualizare în mod regulat intre noduri pentru a menţine tabela de rutare a fiecărui nod actualizata. Apoi, când se iniţiază o transmisie nodul sursa îşi consultă propria tabela de rutare unde se afla informaţiile de rutare şi nu mai este nevoit să caute informaţii despre destinaţie , în acest fel evitându-se întârzierile cauzate de astfel de procedee.

Există două mari tipuri de protocoale de rutare folosite în Internet : bazate pe vectori distanta (de exemplu RIP,EIGRP) sau bazate pe starea legăturii (de exemplu OSPF), ambele tipuri fiind protocoale de tip proactiv. Cu toate acestea, aceste protocoale nu sunt potrivite pentru reţelele mobile ad-hoc care au resurse limitate din cauza cheltuielillor ridicate și a convergenței scăzute. Algoritmul de rutare bazat pe vectorul de distanţă, denumit şi Bellman-Ford, utilizează ca şi criterii de selectare a rutei optime distanţa dintre noduri (metrică). Metrica este numărul de noduri intermediare ("hop-uri") prin care le parcurge un pachet de la o un nod sursa până la un nod destinaţie.Nodurile de reţea care utilizează acest tip de protocol gestionează informaţiile despre metrica într-o tabelă de rutare. Nodurile dintr-o reţea trimit, în mod regulat, această tabelă de rutare fiecărui nod cu care sunt conectate direct. Aceste noduri îşi actualizează propriile tabele de rutare dacă este cazul, după care la rândul lor vor trimite şi ele propriile tabele de rutare celorlalte noduri din reţea direct conectate. Aceasta face că informaţiile despre metrica să se propage în întreaga reţea, astfel încât, în final, fiecare nod să dispună de informaţii despre toate nodurile din întreaga reţea. Protocoalele de rutare bazate pe vectori distanţă sunt oarecum limitate

în capacitatea de alegere a celei mai bune rute. Principalul lor avantaj constă în simplitate şi îndelungata lor folosire . În ultimii ani au fost depuse multe eforturi de a adapta algoritmul Bellman-Ford în contextul reţelelor ad-hoc , o soluţie des întâlnită în reţele ad-hoc fiind protocolul DSDV(Destination-Sequenced Distance-Vector).

Algoritmul de rutare „Vector Distanţă cu Destinaţie Dinamică Ordonată” sau DSDV (Dynamic Destination Sequenced Distance Vector) a fost unul dintre cele mai vechi protocoale dezvoltate de către C. Perkins şi P. Bhagwat pentru rețele ad-hoc. Principal obiectiv de proiectare de DSDV a fost de a dezvolta un protocol care păstrează simplitatea protocolului de rutare RIP bazându-se pe ideea algoritmului distribuit de Bellman-Ford la care au mai fost introduce unele îmbunătăţiri.

La baza protocolului DSDV se aflată transferul de mesaje de control intre routerele (sau nodurile) din reţea. În acest tip de mesaje se găseşte întreaga tabela de rutare pe care o deţine fiecare nod. Traficul de control este trimis fie folosind o adresare MAC de nivel 2 sau o adresare de nivel 3 (IP). Algoritmii bazaţi pe starea legăturilor selectează rutele optime pe baza utilizării dinamice a metodei celui mai scurt drum (Shortest Path First). Fiecare nod gestionează o “hartă” ce descrie topologia curentă a reţelei. Această hartă este actualizată regulat prin testarea posibilităţii de a accesa diferite părţi ale reţelei şi prin schimbul de informaţii cu alte rutere. Determinarea celei mai bune căi (shortest path) poate fi făcută pe baza unor metrici diferite care indică adevăratul cost al trimiterii unei datagrame pe o anumită rută. Algoritmii bazaţi pe starea conexiunii sunt mult mai puternici decât cei bazaţi pe vectori de distanţă. Ei se adaptează dinamic atunci când apar schimbări de topologie în reţea şi, de asemenea, permit selectarea rutelor pe baza unor metrici mult mai reale decât numărul de hop-uri, dar sunt mult mai complicat de instalat şi utilizează mai multe resurse pentru procesare decât cele bazate pe vectori distanţă

Protocoalele de rutare proactive combina principiile algoritmilor bazaţi pe vectori distanta şi ai algoritmilor bazaţi pe starea legăturilor , încercând o adaptare a acestora în cadrul reţelelor ad-hoc.

Protocoale de rutare reactive

Protocoalele de rutare reactive se mai numesc şi protocoale de rutare la cerere ("on demand"),procesul de rutare trebuie să descopere un traseu ori de câte ori un pachet pornește de la o sursă și trebuie să ajungă la o destinație. Aici nodurile nu au o tabelă de rutare pre-construita (sau alte informaţii despre alte noduri din reţea) pe baza căreia să poată lua decizii de dirijare a infromatiilor.

Într-o reţea reactivă, procesul de descoperire al rutelor se întâmplă mai des, schimbul de mesaje se face hop cu hop, nodul sursa inundând reţeaua cu mesaje de cerere de ruta, dar acest proces necesită un trafic scăzut de control în comparație cu rutarea proactiva. Când comunicarea dintre nodul sursă şi nodul destinaţie ia sfârşit, ruta este ştearsă din tabela de rutare a dispozitivelor participante. Prin urmare, o rutare reactivă este considerată a fi mai scalabilă decât una proactiva. În plus, atunci când un nod încearcă să trimită un mesaj folosind o rutare de tip reactiv acesta trebuie să aştepte ca procesul de descoperire a căii pe unde va urma să fie trimisă informaţia să se termine, din această cauză intazierea de ansamblu va creşte.

Protocoale hibride

Protocoalele hibride combină caracteristicile protocoalelor proactive şi reactive, cu scopul principal de folosire a avantajelor acestor două tipuri de protocoale. Acest tip de reţele este împărţit în zone în interiorul cărora sunt folosite protocoale proactive iar în exterior protocoale reactive. Printre cele mai cunoscute protocoale hibride pot fi enumerate ZRP (ZoneRouting Protocol) şi ZHLS (Zone based Hierarhical Link State routing).

Protocoale de rutare AODV

Protocolul de rutare AODV ("Ad Hoc Ondemand Distance Vector") sau “Rutare cu Vector Distanţa la Cerere” a fost conceput pentru a îmbunătăţi performanţele protocolui de rutare DSDV şi de a reduce numărul de mesaje de broadcast şi latentă în transmisie, probleme des întâlnite la protocoalele de rutare bazate pe vectori distanta. Protocolul de rutare AODV este un protocol de rutare reactiv, prin urmare rutele sunt determinate numai atunci când este nevoie, de exemplu procesul de rutare trebuie să descopere un traseu ori de câte ori un pachet porneşte de la o sursă și trebuie să ajungă la o destinație. Pentru a detecta şi monitoriza nodurile vecine protocolul de rutare AODV dispune de mai multe tehnici, una dintre cele mai folosite fiind schimbul de mesaje de tip "hello". Dacă se folosesc mesaje de tip "hello", fiecare nod activ va emite periodic către toți vecinii săi un mesaj de tip ''hello". În cazul în care un nod nu mai primeşte o perioadă de timp mesaje de tip ''hello'' de la vecinul său, atunci înseamnă că legătura s-a defectat. Tabela de rutare a nodurilor vecine este organizată să optimizeze timpul de răspuns atunci când topologia se schimbă şi să ofere un răspuns foarte rapid cererilor de stabilire a unei noi rute.

Protocolul de rutare TORA - Temporally Ordered Routing Algoritm

Algoritmul de Rutare Ordonat Temporal sau TORA a fost conceput în principal pentru a minimiza efectul schimbărilor de topologie care sunt frecvente în reţelele ad hoc. Algoritmul se adaptează la mobilitatea acestor medii prin stocarea de cai multiple către aceeaşi destinaţie, ceea ce face ca multe din schimbările de topologie să aibă un impact minor asupra rutării.

Un concept ce stă la baza design-ului său este acela că mesajele de control implică în general un număr mic de noduri. Salvarea cailor între o pereche (sursa, destinaţie) dată, nu se efecueaza într-o manieră permanentă. Căile sunt create şi stocate după nevoie, aşa cum este cazul tuturor protocoalele din această categorie. Optimizarea drumurilor are o importanţă secundară, căile lungi pot fi utilizate în scopul evitării declanşării unui nou proces de descoperire de noi rute.

TORA garantează că nicio rută nu prezintă bucle (bucle temporare s-ar putea totuşi forma), şi în general asigură mai multe rute pentru o pereche sursă-destinaţie. Acest protocol furnizează doar mecanismul de rutare, şi depinde de IMEP (Internet MANET Encapsulation Protocol) pentru alte funcţii. TORA poate fi separat în trei funcţii principale: crearea traseelor, menţinerea legăturilor , şi ştergerea legăturilor. Crearea rutelor se bazează pe asignarea de direcţii legăturilor, într-o reţea unidirecţională (sau sub-reţea unidirecţională), construind un graf aciclic direcţionat (DAG) cu destinaţia ca rădăcină.

TORA asociază un grad fiecărui nod din reţea. Toate mesajele în reţea circulă de la un nod cu rang mai mare către un nod cu rang mai mic. Rutele sunt descoperite flosind pachete de tip Query sau Update. Când un nod fără legături inferioare necesită o legătură către destinaţie, acesta va difuza un

pachet Query. Pachetul QRY va circula în reţea până când va ajunge la un nod ce are o rută către destinaţie, sau chiar la destinaţie. Acel nod va difuza apoi un pachet Update ce conţine gradul nodului. Orice nod primeşte acest pachet îşi va seta gradul la o valoare mai mare decât a nodului de la care provine pachetul. Nodul va difuza apoi propriul pachet UPD. Procedura va conduce la crearea unui număr de legături directe sursă-destinaţie.

Protocolul de rutare DSR

Protocolul DSR (Dynamic source routing) se bazează pe utilizarea tehnicii de rutare prin sursă.În această tehnică sursa determină secvenţa completă de noduri prin intermediul cărora pachetele de date vor fi trimise. Înainte de a trimite pachetul de date către un alt nod, emiţătorul difuzează un pachet RREQ( Request Route ). Dacă operaţia de descoperire a traseului este reuşită, emiţătorul va primi un pachet RREP(Response Route) care conţine o secvenţă de noduri prin care se poate ajunge la destinaţie. Pachetul RREQ conţine un câmp de înregistrare a traseelor, în care va fi acumulată secvenţa de noduri vizitate în timpul propagării interogării în reţea. Utilizarea tehnicii de rutare prin sursă permite trimiterea de pachete de date fără ca nodurile de tranzit să aibă nevoie să păstreze informaţiile de actualizare.

Rutarea asimetrica

Există multe cazuri în care presupunerea simetriei legăturilor dintre noduri vecine să nu fie validă. În astfel de reţele AODV prezintă un avantaj şi anume o extensie a pachetului Hello care include lista vecinilor cunoscuţi ai nodului respectiv. Dacă un nod primeşte un astfel de mesaj Hello, dar care nu conţine adresa să IP, atunci acesta realizează că legătura cu acest nod este unidirecţională şi nu trebuie să trimită nici un pachet nodului respectiv. Rutarea asimetrică pune probleme serioase la translatarea unei adrese IP într-o adresă MAC (deci de nivel 2). Deoarece ARP (Address Resolution Protocol), protocolul care stabileşte corespondenţele între adresele IP şi adresele MAC, presupune existenţa unei conectivităţi bidirecţionale, prin urmareca şi în cazul rutării asimetrice rezoluţia de adrese trebuie stabilită după algoritmi speciali. Totuşi, stabilirea rutelor asimetrice este importantă, iar AODV se doreşte a fi configurat pentru a oferi această funcţionalitate.

Pentru a favoriza legăturile simetrice prin dezactivarea celor asimetrice, este necesară o strategie de înştiinţare. Fiecare nod care recepţionează un pachet RREP trimite apoi un pachet RREP-ACK (o confirmare a primirii pachetului) înapoi către nodul care a trimis pachetul iniţial. Dacă un nod primeşte pachetul RREP, atunci ştie că legătura este bidirecţionala deoarece pachetul RREP răspunsul la cererea de rută. Iar pachetul de confirmare, RREP-ACK garantează bidirecţionalitatea către următorul nod.

Modelarea retelei ad hoc

Cele mai importante componete folosite în construirea unei reţele ad hoc sunt prezentate în acest subcapitol. Plecand de la nivelul 7 al stivei OSI în jos, cea mai importantă componentă analizată va fi cea de aplicaţie. Având în vedere faptul că în realitate ceea ce ne interesează este să avem posibilitatea de a folosi aplicaţii uşor şi rapid , configuraţia aplicaţiei are un rol important în conceperea

unei reţele. Unele dintre cele mai uzuale aplicaţii de reţea care sunt destinate folosirii în Internet sunt: pagini web, mail, servere etc. În spatele acestor aplicaţii există un protocol al nivelului aplicaţie. Traficul de date folosit în simulările care vor urma este de tip FTP. Nivelul transport (nivel 5 OSI) este responsabil cu generarea şi recepţionarea pachetelor.

La nivel rețea vom folosi pe rând protocoalele DSR, AODV, TORA, aceste protocoale sunt utilizate pentru a dirija pachetele de date de la sursă către destinație în rețele ad-hoc.

Nivelul legătură (LL-Link Layer) se ocupă cu fragmentarea şi reasamblrea pachetelor, la ceste nivel rulează protocolul ARP, folosit pentru a crea corespundeţe între adresele IP ale nodurilor şi adresele MAC ale acestora. Nivelul Mac foloseşte drept protocol IEEE 802.11 care a fost descris in capitolul care utilizeaza mesaje de tip RTS/CTS/DATA/ACK.Interfeţele de reţea constu în ineterfeţe hardware folosite de nodurile mobile pentru a accesa canalul. Prin acestea se simulează integritatea semnalului, coliziunile.Modelul de propagare radio foloseşte atenuarea de tip Two ray ground pentru distanţe mari. Decide dacă pachetele pot fi sau nu recepţionate de nodul mbil, dată fiind o anumită destanţă , o anumită putere de transmisie şi o anumită lungime de undă. Modelul de reflexie Two ray ground ia în considerare atât calea directă cât şi calea reflectată.

Concluzii si probleme cunoscute

Lucrarea prezenta scoate in evidenta faptul ca procesul de rutare este o problema foarte importanta, dar dificila in retele. Algoritmii de rutare traditionali nu pot indeplini cerințele unei retele ad-hoc, datorita topologiei dinamice și latimii de bandă limitata, care caracterizează aceste retele. Din acest motiv, se realizeaza cercetari multiple care se ocupa cu extinderea algoritmilor de rutare existenti sau cu descoperirea de algoritmi noi și mai eficienti de rutare.

Desi este clar ca nici unul dintre algoritmi sau clasa de algoritmi nu este cel mai bun pentru toate condițiile de retea, fiecare protocol are avantaje și dezavantaje clare și are anumite situatii pentru care este bine adaptat.

Retele ad-hoc sunt utile pentru furnizarea suportului de comunicare in cazul in care nu exista infrastructura fixa sau implementarea unei infrastructuri fixe nu este profitabila din punct de vedere economic, si deplasarea entitatilor ce comunica este permis. Aplicatii ale retelelor ad-hoc includ operatiuni militare (de comunicare intr-un mediu ostil), operatiuni de salvare (desfasurarea rapida a unei retele de comunicatii in care infrastructuri nu exista sau au fost deteriorate), si sporadice de acoperire intâmplari (utilizarea intensa a unei retele de comunicatii pentru o foarte perioada limitata de timp). Datorita mobilitatii, rutele care leaga doua noduri se pot schimba. Prin urmare, nu este posibil sa se stabileasca apriori trasee fixe pentru livrarea de mesaj prin intermediul retelei. Ca o consecinta, rutarea in retele fara fir ad-hoc este grea si reprezinta o problema dificila.

IP-ul ofera un grad uimitor de flexibilitate in construirea retelelor arbitrare de complexitate mare. Routerele ce colucreaza, capabile de o rata de transmitere de date in domeniul multigigabitilor si terabitilor pe secunda sunt necesare in dezvoltarea mediilor retelistice de inalta performanta. Aceasta lucrare a prezentat o evaluare a abordarilor tipice propuse pentru proiectarea rutarilor de mare viteza. Ne-am concentrat in primul rand pe modelul arhitectural, initial pe prezentarea diferitelor arhitecturi, iar

pe urma asupra componentelor ce au cel mai mare efect asupra performantei si folosirea diferitilor algoritmi.

In primul rand , am observat ca router-ele de mare viteza trebuie sa aiba suficienta latime de banda interna pentru a transmite pachetele intre interfetele sale la viteze de multigigabiti si terabiti.

Experienta ne arata ca in timp ce rutarea IP trebuie, in general, sa efectueze o multitudine de functii, in practica, marea majoritate a pachetelor au nevoie doar de cateva operatiuni efectuate in timp real. Astfel, functiile critice de performanta, pot fi puse in aplicare prin intermediul hardware-ului (calea rapida), iar restul (necesar, dar mai putin critice), prin functii software (calea lenta). IP-ul contine multe caracteristici si functii care, fie sunt rar folosite sau pot fi efectuate in fundalul expedierii de mare viteza a datelor (de exemplu, operarea protocolul de rutare si de gestionare a retelei). Arhitectura de rutare ar trebui sa fie optimizata pentru acele functii, care trebuie sa fie efectuate in timp real, pe lagaturile pachet-pachet, pentru majoritatea pachetelor. Acest lucru creeaza o solutie optima de rutare, ce transmite pachetele la viteza mare, cu un cost rezonabil.

Au fost realizate progrese semnificative in modele de rutare pentru a aborda problemele cele mai exigente ale clientilor, in ceea ce priveste transmiterea de pachete de mare viteza (de exemplu, algoritmi ai tabelelor de rutare, nuclee de comutare de mare viteza si mecanisme de expediere), la preturi mici per port, caracterizate de flexibilitate si programabilitate, fiabilitate si usurinta in configurare. In timp ce aceste progrese au fost facute in proiectarea de rutare IP, unele probleme importante raman inca deschise si asteapta sa fie rezolvate. Acestea includ clasificarea de pachete si gestionarea resurselor, imbunatatirea arhitecturi de rutare pentru a creste rata pret/performanta, "retea activa" si usurinta de configurare, fiabilitate si modalitati multiple de comercialiazare pe internet. Se desfasoara lucrari ample, atat in comunitatea de cercetare, cat si in industrie pentru a aborda aceste probleme.