Riquadro 1
Il Routing dal punto di vista algoritmico: il problema dei cammini minimi.
Dal punto di vista algoritmico, il routing su di una rete può essere ricondotto ad un problema di ottimizzazione su grafi. In questo riquadro descriveremo in maniera introduttiva il problema; per un approfondimento si rimanda all’ottimo testo di [R.Tarajan]. Si consideri il seguente problema:
l
CAMMINI MINIMI: "Sia dato un grafo orientato G = (N, A) dove N rappresenta l’insieme dei nodi del grafo ed A l’insieme degli archi con pesi interi relativi. Sia dato un nodo r Î N, trovare un cammino da r ad u, per ogni nodo u Î N, tale che la somma delle lunghezze degli archi nel cammino sia la più piccola possibile."Una soluzione ammissibile al problema è un insieme di n-1 cammini, ciascuno dei quali parte dal medesimo nodo r ma giunge ad uno ed uno solo dei rimanenti nodi. In generale non è detto che esista un cammino r ad un qualsiasi altro nodo u, semplicemente perché u potrebbe non essere raggiungibile da r. Nel caso di una rete di router, questa condizione viene però garantita dalla natura stessa del problema affrontato. Un altro problema da tenere presente affrontando la questione dal punto di vista algoritmico è l’esistenza di cicli il cui costo sia negativo (dove il costo di un cammino è la somma dei costi presenti degli archi che lo formano). In tal caso la lunghezza minima di un qualsiasi cammino comprendente questo ciclo non sarebbe limitata inferiormente. Anche questa volta il problema da affrontare per una rete di router è semplificato in quanto i costi sono valori interi e positivi o nulli.
Si osservi che due cammini distinti possono avere un tratto comune, da r sino ad un certo nodo s, e poi divergere verso le rispettive destinazioni u e v (che devono essere distinte). Non può invece accadere che due cammini inizialmente distinti convergano verso lo stesso nodo s, perché in questo caso esisterebbero due cammini distinti verso s partendo da r (mentre per definizione il problema ne richiede solo uno). Ne consegue che una soluzione ammissibile è un albero di copertura, con radice in r, che include un cammino da r ad ogni altro nodo. Abbiamo sin qui caratterizzato l’insieme delle soluzioni ammissibili al problema; diamo adesso le condizioni per scegliere la soluzione ottima tra quelle ammissibili. Sia T un albero di copertura del grafo G (soluzione ammissibile); sia d
i il costo associato al generico nodo i di T (pari al costo del cammino che parte da r ed arriva in G al nodo i). Consideriamo un generico arco (i, j) Î A e sia cij la sua lunghezza e supponiamo che T sia un albero di copertura ottimo; ne segue che:l
Se (i, j) Î T allora per costruzione di + cij = dj.l
Se invece (i, j) Ï T deve risultare di + cij ³ dj, affiché la soluzione rappresentata da T sia ottima. In caso contrario esisterebbe in G un cammino tra r ed j più corto di quello in T ovvero il cammino tra r ed i seguito dall’arco (i, j).Supponiamo adesso che (punto A) sia d
i + cij = dj per ogni (i, j) Î T e che si verifichi (punto B) che di + cij ³ dj per ogni (i, j) Ï T.Se per assurdo il cammino da r ad u in T non è ottimo, allora esiste un altro cammino in G da r ad u tale che la distanza d
u1 tra la radice r ed il nodo u sia minore di du [ (punto C) du1 < du ]. Sia dj1 la distanza su tale cammino dal nodo radice r ad un generico nodo j.Poiché per costruzione d
r1 = dr = 0 e du1< du ne consegue che esiste un arco (h, k) su questo cammino per cui vale dh1>dh ed dk1< dk [ ovvero (punto D) prima di quell’arco il costo è minore, dopo di quell’arco maggiore ].Per costruzione vale che d
h1 + chk = dk1 mentre, considerando che (h, k) non sta in T e ricordando l’ipotesi del punto B, abbiamo che dh + chk ³ dk. Combinando le relazioni otteniamo che: dk1 = dh1 + chk ³ dh + chk ³ dk e di conseguenza dk1> dk che contraddice l’ipotesi fatta al punto D.Con questi passaggi abbiamo dimostrato in modo matematico quelle che in letteratura informatica sono note con il nome di
:Condizioni di Bellman: una soluzione ammissibile T è ottima se e solo se valgono le seguenti condizioni
l di + cij = dj per ogni (i, j) Î T
l di + cij ³ dj per ogni (i, j) Ï T ed (i, j) Î A.
Le condizioni di Bellman sono il fondamento di ogni algoritmo di routing dinamico. Nel corso dell’articolo è illustrato come esse vengano applicate nel caso dell’algoritmo di Dijkstra.
Glossario:
l
Grafo Orientato G=(N,A). Un grafo orientato è una coppia di insiemi N ed A, dove N è un insieme finito di elementi detti nodi ed A è un insieme finito di coppie ordinate di nodi.l
Albero di copertura T=(N,A). Un albero di copertura è un albero cotruito visitando un grafo G=(N1, A1). Durante la visita ciascun nodo è attraversato solo una volta.Bibliografia: [R.Tarajan] "Data Structures and Network Algorithms", SIAM Philadelphia , 1983