Algoritmi de rutare a mesajelor (pachetelor) în rețea

Pentru a putea vorbii despre algoritmi de rutare trebuie sa amintim despre nivelul rețea din modelul OSI. Nivelul rețea este răspunzător de, dirijarea pachetelor de la calculatorul sursă la cel destinație.

După modul în care se transmit informațiile intr-o rețea avem :

- Rețele ce folosesc datagrame ;

- Rețele bazate pe circuite virtuale.

În cazul rutării bazată pe datagrame fiecare pachet (datagramă) este rutat individual, astfel este posibil ca pachetele să nu urmeze aceeași cale de la sursă către destinație.

La rutarea bazată pe circuite virtuale decizia de rutare se ia la stabilirea circuitului virtual, astfel fiecare pachet va urma aceeasi cale dinspre sursă spre destinație.

Compararea celor două moduri de transmitere a informațiilor dintr-o rețea:

Rețea datagrame Rețea circuit-virtual

Adresarea Fiecare pachet conține adresa completă atât a sursei cât și a destinației Fiecare pachet conține un numar de circuit virtual

Informații de rutare Rețeaua nu păstrează nici o informație Fiecare circuit virtual este trecut intr-un tabel de rutare

Rutarea Fiecare pachet este rutat independent Odată stabilit circuitul virtual fiecare pachet va urma acel traseu

În cazul defectării unui ruter (nod) Nu se întâmpla nimic, doar că pachetele aflate în acel nod se pierd Toate circuitele virtuale ce trec prin acel nod se pierd

Controlul congestiei Dificil Ușor de realizat dacă de la inițializare se alocă destule resurse (memorii tampon)

Există însă un compromis între cele două moduri de funcționare (datagramă, curcuit virtual) in cazul folosirii datagramelor din cauză că fiecare pachet trimis conține adresele sursei, destinației in cazul în care pachetul transmis este scurt se iroseste lățime de bandă pentru transmiterea acelor adrese. În cazul circuitelor virtuale având în vedere că ruta, circuitul virtual este ales o singură dată trebuie să se i-a în calcul capacitatea de memorie ruterului. Astfel există acest compromis între largimea benzii de transmisie și capacitatea memorie ruterelor.

Algoritmii de rutare sunt parte componentă din softul nivelului rețea și sunt responsabili de luarea deciziei privind dirijarea pachetelor.

Un algoritm de rutare trebuie să îndeplinească anumite proprietăți:

- corect

- robust

- optim

- simplu

- eficient

- stabil

Algoritmii de rutare se împart în două clase:

- algoritmi neadaptivi

- algoritmi adaptivi

Algoritmii neadaptivi nu își bazează deciziile de rutare pe măsuratori, încărcarea rețelei, topologie, ci se bazează pe calcule făcute dinainte și care sunt încărcate la inițializare rețelei. Această procedură este numită uneori rutare statică.

Algoritmii adaptivi în schimb se bazează pe pe calcule făcute în timp real, se bazează pe modificările ce survin în topologie și trafic.

În continuare voi prezenta câțiva algoritmi de rutare.

Algoritmul Dijkstra sau algoritmul drumului cel mai scurt.

Se dă imaginea alăturată pentru a se putea exemplifica algoritmul Dijkstra.

Fiecare literă reprezintă un nod în rezea. Se dorește găsirea drumului cel mai scurt de la nodul A la nodul D. Rețeaua este exemplificată printr-un graf etichetat, iar deasupra arcelor este câte o cifră ce reprezintă distanța dintre noduri. Se observă că distanțele nu sunt numere negative.

În continuare voi explica pașii care sunt urmați. Nodul A este marcat ca permanent, printr-o cerculeț plin. Astfel nodul A devine nodul de lucru. În continuare se analizează toate nodurile învecinate lui A si se notează distanța până la nodul A. Ex. nodul B(2,A) de la B la A distanța 2. După ce au fost identificate toate nodurile adiacente lui A se caută nodul cu cea mai mică distanță, pondere, în cazul de față B. Acum nodul B va fi nodul de lucru de la care vom repeta pasul anterior. Din nodul B se poate ajunge în E și C. Nodului C i se rescrie eticheta astfel E(2+2,B), adică se face suma dintre ponderea înscrisă în eticheta nodului de lucru și valoarea distanței dintre B și E. Astfel se rescrie și eticheta nodului C(9,B). Examinând cele două etichete se realizează că nodul E va fi următorul nod de lucru, de la care se vor repeta pașii anteriori, iar nodul B va fi nod permanent.