Algoritmi d’instradamento
Generalmente, un host è connesso direttamente al cosiddetto router predefinito (default router), chiamato anche router di primo hop, cui trasferisce tutti i pacchetti. Faremo riferimento al router di default dell’host origine come router origine, mentre il router predefinito dell’host di destinazione sarà il router destinazione.
Il problema di instradare un pacchetto tra origine e destinazione si riconduce chiaramente al problema d’instradare il pacchetto tra questi due router. Dato un insieme di router interconnessi, lo scopo di un algoritmo d’instradamento è quello di trovare un “buon percorso” tra quello d’origine e quello di destinazione. Solitamente, un percorso ottimale è quello di costo inferiore.
Il grafo di instradamento
Per formulare i problemi d’instradamento si utilizza un grafo. Ricordiamo che un grafo G=(N,E) è un insieme N di nodi e un insieme E di lati (o archi), ove ciascun arco è una coppia di nodi di N.
Nel contesto dell’instradamento a livello di rete, i nodi del grafo rappresentano i router, che prendono decisioni sull’inoltro dei pacchetti, e gli archi che connettono tali nodi rappresentano i collegamenti fisici tra i router.
Come in figura, a un arco è associato un valore che ne indica il costo. In genere, questo può riflettere la lunghezza fisica del collegamento corrispondente, ad esempio un collegamento transoceanico può avere un costo superiore rispetto a un collegamento a breve raggio terrestre, la velocità del collegamento o il prezzo richiesto.
Per ogni arco (x,y) in E, denotiamo con c(x,y) il suo costo. Se la coppia (x,y) non appartiene ad E, poniamo c(x,y)=∞. Inoltre, consideriamo sempre e solo grafi non orientati, cioè con archi bidirezionali, ragion per cui l’arco (x,y) è uguale all’arco (y,x) e c(x,y)=c(y,x).
Inoltre, un nodo y viene detto adiacente (vicino) a un nodo x se (x,y) è un lato di E.
Cammini a costo minimo
Un obiettivo naturale di un algoritmo d’instradamento è l’individuazione dei percorsi meno costosi tra origini e destinazioni. Ricordiamo che un cammino in un grafo G=(N,E) è una sequenza di nodi (x1, x2, …., xp) tali che ciascuna delle coppie (x1, x2), (x2, x3), …., (xp-1, xp) sia un lato di E.
Il costo di un cammino (x1, x2, …., xp) è semplicemente la somma di tutti i costi degli archi lungo il cammino, ossia c(x1,x2)+c(x1,x3)+…+c(xp-1,xp).
In generale, dati due nodi qualsiasi x e y, esistono più percorsi che li congiungono, ciascuno con il proprio costo. Uno o più di tali percorsi rappresenta un cammino a costo minimo.
Il problema è quindi chiaro: determinare un cammino tra l’origine e la destinazione che abbia il costo minimo. In figura, ad esempio, il cammino a costo minimo tra il nodo origine u e il nodo destinazione w è (u, x, y, w), il cui costo vale 3.
Si noti che se tutti gli archi del grafo hanno lo stesso costo, il percorso a costo minimo rappresenta anche il cammino più breve.
Classificazione degli algoritmi d’instradamento
In generale gli algoritmi d’instradamento possono essere classificati come globali o decentralizzati.
Un algoritmo d’instradamento globale calcola il cammino a costo minimo tra un’origine e una destinazione avendo una conoscenza globale e completa della rete.
In altre parole, l’algoritmo riceve in ingresso tutti i collegamenti tra i nodi e i loro costi. In pratica gli algoritmi con informazioni di stato globali sono spesso detti algoritmi a stato del collegamento, dato che l’algoritmo deve essere conscio del costo di ciascun collegamento della rete.
In un algoritmo d’instradamento decentralizzato, il cammino a costo minimo viene calcolato in modo distribuito e iterativo. Nessun nodo possiede informazioni complete sulla rete.
Inizialmente i nodi conoscono soltanto i costi dei collegamenti a esso incidenti. Pertanto, attraverso un processo iterativo e lo scambio di informazioni con i nodi adiacenti, un nodo gradualmente calcola il percorso a costo minimo verso una destinazione o un insieme di destinazioni.
L’algoritmo d’instradamento decentralizzato è chiamato algoritmo a vettore distanza, DV, poiché ogni nodo elabora un vettore di stima dei costi (distanze) verso tutti gli altri nodi nella rete.
Algoritmi statici e dinamici
Un secondo criterio per classificare gli algoritmi d’instradamento riguarda il fatto di essere statici o dinamici.
Negli algoritmi d’instradamento statici i cammini cambiano molto raramente. Gli algoritmi d’instradamento dinamici invece determinano gli instradamenti al variare del volume di traffico o della topologia della rete.
Gli algoritmi dinamici rispondono meglio ai cambiamenti della rete, ma sono anche più soggetti a problemi.
Algoritmi sensibili al carico
Un terzo modo per classificare gli algoritmi d’instradamento è il fatto di essere sensibili al carico o meno.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
