Algoritmi de rutare a mesajelor (pachetelor) in retea

Extras din referat Cum descarc?

Pentru a putea vorbii despre algoritmi de rutare trebuie sa amintim despre nivelul retea din modelul OSI. Nivelul retea este raspunzator de, dirijarea pachetelor de la calculatorul sursa la cel destinatie. 
Dupa modul in care se transmit informatiile intr-o retea avem :
- Retele ce folosesc datagrame ;
- Retele bazate pe circuite virtuale.
In cazul rutarii bazata pe datagrame fiecare pachet (datagrama) este rutat individual, astfel este posibil ca pachetele sa nu urmeze aceeasi cale de la sursa catre destinatie.
La rutarea bazata pe circuite virtuale decizia de rutare se ia la stabilirea circuitului virtual, astfel fiecare pachet va urma aceeasi cale dinspre sursa spre destinatie.
Compararea celor doua moduri de transmitere a informatiilor dintr-o retea:
Retea datagrame Retea circuit-virtual
Adresarea Fiecare pachet contine adresa completa atat a sursei cat si a destinatiei Fiecare pachet contine un numar de circuit virtual
Informatii de rutare Reteaua nu pastreaza nici o informatie Fiecare circuit virtual este trecut intr-un tabel de rutare
Rutarea Fiecare pachet este rutat independent Odata stabilit circuitul virtual fiecare pachet va urma acel traseu
In cazul defectarii unui ruter (nod) Nu se intampla nimic, doar ca pachetele aflate in acel nod se pierd Toate circuitele virtuale ce trec prin acel nod se pierd
Controlul congestiei Dificil Usor de realizat daca de la initializare se aloca destule resurse (memorii tampon)
Exista insa un compromis intre cele doua moduri de functionare (datagrama, curcuit virtual) in cazul folosirii datagramelor din cauza ca fiecare pachet trimis contine adresele sursei, destinatiei in cazul in care pachetul transmis este scurt se iroseste latime de banda pentru transmiterea acelor adrese. In cazul circuitelor virtuale avand in vedere ca ruta, circuitul virtual este ales o singura data trebuie sa se i-a in calcul capacitatea de memorie ruterului. Astfel exista acest compromis intre largimea benzii de transmisie si capacitatea memorie ruterelor.
Algoritmii de rutare sunt parte componenta din softul nivelului retea si sunt responsabili de luarea deciziei privind dirijarea pachetelor.
Un algoritm de rutare trebuie sa indeplineasca anumite proprietati:
- corect
- robust
- optim
- simplu
- eficient
- stabil
Algoritmii de rutare se impart in doua clase:
- algoritmi neadaptivi
- algoritmi adaptivi
Algoritmii neadaptivi nu isi bazeaza deciziile de rutare pe masuratori, incarcarea retelei, topologie, ci se bazeaza pe calcule facute dinainte si care sunt incarcate la initializare retelei. Aceasta procedura este numita uneori rutare statica.
Algoritmii adaptivi in schimb se bazeaza pe pe calcule facute in timp real, se bazeaza pe modificarile ce survin in topologie si trafic.
In continuare voi prezenta cativa algoritmi de rutare.
Algoritmul Dijkstra sau algoritmul drumului cel mai scurt.
Se da imaginea alaturata pentru a se putea exemplifica algoritmul Dijkstra.
Fiecare litera reprezinta un nod in rezea. Se doreste gasirea drumului cel mai scurt de la nodul A la nodul D. Reteaua este exemplificata printr-un graf etichetat, iar deasupra arcelor este cate o cifra ce reprezinta distanta dintre noduri. Se observa ca distantele nu sunt numere negative.
In continuare voi explica pasii care sunt urmati. Nodul A este marcat ca permanent, printr-o cerculet plin. Astfel nodul A devine nodul de lucru. In continuare se analizeaza toate nodurile invecinate lui A si se noteaza distanta pana la nodul A. Ex. nodul B(2,A) de la B la A distanta 2. Dupa ce au fost identificate toate nodurile adiacente lui A se cauta nodul cu cea mai mica distanta, pondere, in cazul de fata B. Acum nodul B va fi nodul de lucru de la care vom repeta pasul anterior. Din nodul B se poate ajunge in E si C. Nodului C i se rescrie eticheta astfel E(2+2,B), adica se face suma dintre ponderea inscrisa in eticheta nodului de lucru si valoarea distantei dintre B si E. Astfel se rescrie si eticheta nodului C(9,B). Examinand cele doua etichete se realizeaza ca nodul E va fi urmatorul nod de lucru, de la care se vor repeta pasii anteriori, iar nodul B va fi nod permanent.


Fisiere in arhiva (1):

  • Algoritmi de rutare a mesajelor (pachetelor) in retea.DOC

Imagini din acest proiect Cum descarc?

Bibliografie

1. ,,Computer networks, fourth edition" - Andrew S. Tanenbaum, editura: Prentice Hall, anul 2003, ISBN: 0-13-066102-3.


Promoție: 1+1 gratis

După plată vei primi prin email un cod de download pentru a descărca gratis oricare alt referat de pe site.Vezi detalii.


Descarcă aceast referat cu doar 4 € (1+1 gratis)

Simplu și rapid în doar 2 pași: completezi adresa de email și plătești. După descărcarea primului referat vei primi prin email un alt cod pentru a descărca orice alt referat.

1. Numele, Prenumele si adresa de email:

Pe adresa de email specificata vei primi link-ul de descarcare. Daca nu gasesti email-ul, verifica si directoarele spam, junk sau toate mesajele.

2. Alege modalitatea de plata preferata:


* La pretul afisat se adauga 19% TVA, platibil in momentul achitarii abonamentului / incarcarii cartelei.

Hopa sus!