Algoritmi de dirijare

Problema dirijarii apare la nivelul retea, si consta in a determina calea pe care o vor parcurge pachetele de la calculatorul sursa la calculatorul destinatie. Software-ul nivelului retea trebuie sa asigure desfasurarea a doua procese distincte:

• retransmitere (forwarding): ceea ce se intampla cand un pachet ajunge la ruter, si acesta trebuie sa stabileasca, prin consultarea unei tabele de rutare, linia de iesire pe care va transmite pachetul mai departe
• dirijare (routing): este procesul de construire si actualizare a tabelei de rutare - adica de stabilire a cailor pe care vor fi transmise pachetele

Referitor la algoritmii ce tin de procesul de dirijare, putem distinge doua categorii de algoritmi: algoritmi neadaptivi (ce realizeaza o dirijare statica - toate rutele sunt determinate initial si nu se tine cont de modificarile ulterioare de trafic si topologie ce apar in retea) si algorimi adaptivi (rutele sunt modificate ca urmare a schimbarilor de topologie si de trafic din retea).

Dintre algoritmii neadaptivi fac parte:

• dirijarea pe calea cea mai scurta (shortest path routing): subreteaua este reprezentata ca un graf, in care ruterele sunt noduri, si se aplica un algoritm (de exemplu Dijkstra) pentru a determina caile cele mai scurte dintre noduri; se pot folosi diverse metrici, cum ar fi numarul de rute intermediare, distanta geografica, intarzierile medii de transmisie
• inundarea (flooding): ruterul trimite fiecare pachet receptionat pe toate liniile de iesire, in afara de cea pe care a venit pachetul; varianta: inundarea selectiva (selective flooding)

Algoritmii adaptivi cel mai des utilizati sunt:

• dirijarea cu vectori distanta (distance vector routing): fiecare ruter mentine o tabela cu calea cea mai buna pentru fiecare destinatie si linia de iesire corespunzatoare acestei cai; tabelele sunt actualizate pe baza informatiilor primite de la celelalte rutere
• dirijarea folosind starea legaturilor (link state routing): fiecare router determina costurile asociate cailor catre vecini, apoi trimite aceste informatii in toata subreteaua; dupa schimburile de informatii, fiecare ruter are informatii complete despre graf si poate determina caile minime

Exemple de protocoale de dirijare:

• RIP (Routing Internet Protocol) - utilizeaza algoritmul distance vector
• OSPF (Open Shortest Path First Protocol) - utilizeaza algoritmul link state
• BGP (Border Gateway Protocol)

Programul de mai jos citeste dintr-un fisier un numar n reprezentand dimensiunea unei matrici de adiacenta a unui graf cu nodurile retelei, precum si aceasta matrice. Initial creeaza o tabela de rutare pentru fiecare nod, care contine informatii despre toate nodurile retelei, sub forma : Destinatar , Cost (=valoarea asociata muchiei dintre acel nod si destinatar), Next_Hop (=nodul urmator de urmat pentru a ajunge la destinatar). Apoi, pentru fiecare nod se vor actualiza informatiile despre celelalte noduri combinand informatiile gasite in fiecare tabela de rutare cercetata.


#include "stdio.h"
#include "stdlib.h"
#define INF 1000

int **a, n;

typedef struct tabela {

int *dest;
int *cost;
int *next_hop;

} Tabela;

void printTabela(Tabela t) {

int i;
for(i=0; i < n; i++)
printf("%d\t%d\t%d \n", t.dest[i], t.cost[i], t.next_hop[i] );
}

int find_dest(Tabela t, int poz) { // prima dest incepand cu poz

int i=poz;
while(t.cost[i] == INF && i<=n-1)
i++;
if (i<=n-1)
return t.dest[i];
return -1; // nu a gasit
}

int main () {

FILE * f = fopen ("in", "r");
fscanf(f, "%d",&n);
int i,j,k;
a = (int **)malloc(n*sizeof(int));

for(i=0; i < n ; i++)
a[i] = (int *)malloc(n*sizeof(int));
for(i=0; i < n ; i++)
for(j=0; j < n ; j++)
fscanf(f, "%d", &a[i][j]);

Tabela * tab = (struct tabela *)malloc(sizeof(struct tabela)*n);
for(i=0; i < n ; i++) {
tab[i].dest = (int *)malloc(n*sizeof(int));
tab[i].cost = (int *)malloc(n*sizeof(int));
tab[i].next_hop = (int *)malloc(n*sizeof(int));
}

// constructia tabelei in forma initiala
for (i=0; i < n ; i++) { // pt fiecare tabela
for(j=0; j < n ; j++)
if (a[i][j]) {
tab[i].dest[j] = j;
if(i!=j)
tab[i].cost[j] = 1;
else
tab[i].cost[j] = 0;
tab[i].next_hop[j] = j;
}
else {
tab[i].dest[j] = j;
tab[i].cost[j] = INF;
tab[i].next_hop[j] = -1;
}
}

printf("Tabela 5 inainte de aplicarea algoritmului:\n");
printTabela(tab[5]); // printam un anumit nod


for(i=0; i < n ; i++) // pt fiecare tabela

for(j=0; j < n ; j++) { // pt fiecare destinatie din tabela
k = find_dest(tab[j],0);
while(k!=-1) {
if (tab[i].cost[k] > tab[j].cost[k] + tab[i].cost[j]) {
tab[i].cost[k] = tab[j].cost[k] + tab[i].cost[j];
tab[i].next_hop[k] = tab[j].dest[j];
}
k = find_dest(tab[j],k+1);
}
}

printf("Tabela finala 5 cu drumuri optime:\n");
printTabela(tab[5]);

return 0;

}