2. Routing in reti di comunicazione Capitolo 2 54 2.2 Il grafo della rete e i dati caratteristici...

2 . R o u t i n g i n r e t i d i c o m u n i c a z i o n e

ROC-00/01 Capitolo 2

52

2 . 1 Reti di comunicazione: aspetti tecnologici ed economici

2.1.1 Problemi di ottimizzazione nelle reti di comunicazione

La creazione, gestione e manutenzione di reti di comunicazione è uno dei campi più fecondi perle applicazioni della Ricerca Operativa, oltre alla sua importanza economica e strategica per losviluppo di un paese.

Dalle reti telefoniche a centrali elettromeccaniche e delle reti telegrafiche, che hanno caratte-rizzato i primi anni del 20º secolo, la realtà odierna ha subito una evoluzione notevole attra-verso la diversificazione dei sistemi a rete e l'applicazione di nuove tecnologie di comunica-zione. Si pensi alle reti telefoniche a commutazione elettronica, alle tecniche di gestione infor-matizzata, alle reti dei telefoni cellulari, alle reti mondiali di posizionamento e collegamentoattraverso grappoli di satelliti a bassa quota. Le stesse reti di comunicazione dei dati tra elabo-ratori hanno ricevuto un notevole impulso con l'uso pubblico di Internet e l'introduzione di retiIntranet in aziende e grosse società. Il sistema di comunicazione visiva, essenzialmenteanalogico per via etere o cavo, oggi dispone di sistemi digitali basati su satelliti geostazionari.

Il 21º secolo è iniziato con la forte integrazione dei diversi servizi di comunicazione:immagini, dati, parole viaggeranno sempre più su un insieme di reti interconnesse superando ladistinzione attuale tra telefono, telefono cellulare, fax, hi-fi, computer e televisore.L'integrazione delle reti permetterà un'esplosione delle attività svolte attraverso una rete,andando al di là delle attuali applicazioni legate alle teleconferenze, al telelavoro, al controllo adistanza, alle transazioni commerciali e finanziarie, al commercio elettronico, ecc. Anche le retielettriche e ferroviarie permettono di essere utilizzate per la comunicazione.

2.1.2 Progetto, gestione e manutenzione di reti

Facendo un'astrazione sugli aspetti tecnologici di una rete, si possono individuare diversicampi applicativi della Ricerca Operativa nelle tre fasi di progetto, gestione e manutenzione diuna rete.

Per progetto di una rete si intendono tutte le attività tese a stabilire:- lo sviluppo territoriale della rete stessa sia come punti (nodi) di ricezione-trasmissione sia

come canali di comunicazione tra nodi;- il dimensionamento dei nodi e dei canali, la selezione dei parametri alla metodologia di

trasmissione (dimensionamento dell'unità di trasmissione, velocità di trasmissione, banda difrequenza in cui è effettuata la trasmissione);

- la tecnologia di realizzazione dei nodi e dei canali;- le metodologie di autocontrollo sul funzionamento e di recupero dei malfunzionamenti;- il costo di realizzazione e di gestione della rete;- la flessibilità di aggiornamento della rete attraverso l'introduzione di tecnologie future;- l'interconnessione con reti complementari o concorrenti;- la definizione delle procedure per la salvaguardia dell'integrità dei dati trasmessi e della

privacy delle persone;- ecc.

Affronteremo solo alcuni, tra i più semplici, problemi legati al progetto di una rete, quali lalocalizzazione dei nodi e il progetto (o design) dei canali di connessione tra i nodi.


53

Per gestione di una rete si intendono tutte quelle attività legate alla ricezione di richieste dicomunicazione da parte dei clienti e alla loro effettuazione. In particolare, si possono individuareattività quali:- gestione del portafoglio clienti;- tariffazione dei servizi;- individuazione del (o dei) collegamento(i) più adatto(i) per ciascun servizio;- gestione on-line della comunicazione con terminali in movimento;- codificazione della comunicazione per protezione riservatezza e/o per riduzione della perdita

di informazione;- frammentazione della comunicazione in unità elementari;- istradamento delle unità elementari;- ricomposizione delle unità elementari per la ricostituzione del messaggio;- memorizzazione nei nodi di transito e nei nodi di destinazione;- comunicazione a ritroso di controllo-conferma e eventuali reistradamenti;- comunicazioni verso più utenti (broadcasting) della stessa comunicazione;- comunicazione contestuale bidirezionale;- controllo, previsione e gestione della congestione;- gestione dei malfunzionamenti;- gestione del personale;- ecc.

Delle attività di gestione affronteremo essenzialmente due aspetti: la ricerca del miglioreistradamento, anche sotto diversi criteri, e la frammentazione della comunicazione in unitàelementari. Alcuni aspetti legati alla simulazione del funzionamento di una rete saranno affrontatinella parte relativa alle reti di trasporto, in questo corso, e, più in generale, nel corso diSimulazione.

Per manutenzione di una rete si intendono tutte le attività legate alla previsione di possibilimalfunzionamenti, al controllo delle apparecchiature e agli interventi per il ripristino dellafunzionalità. In particolare, si possono individuare le seguenti attività:- definizione di piani di controllo e manutenzione periodica delle apparecchiature;- pianificazione di test di funzionalità;- effettuazione di interventi preventivi;- attuazione di procedure di autocontrollo;- immissione di nuovi nodi e/o canali temporanei per garantire la funzionalità della rete nelle

fasi di intervento;- attuazione di intervento sulle emergenze;- gestione delle squadre di intervento;- ecc.

Sui problemi legati alla manutenzione non saranno fatti riferimenti.Nei paragrafi seguenti affronteremo pertanto solo alcuni dei problemi di Ricerca Operativa

legati alle reti di comunicazione.Al fine di fornire gli elementi principali della modellistica, astrarremo dalle caratteristiche

fisiche delle reti, concentrandoci solo su alcuni dei parametri che le caratterizzano.Iniziamo dai problemi di istradamento (routing) dei messaggi.


54

2 . 2 Il grafo della rete e i dati caratteristici

Una rete di comunicazione può essere sempre rappresentata mediante un grafo orientatoG = (N, A), in cui N rappresenta l'insieme dei nodi e A rappresenta l'insieme dei canali, dettiarchi.

Quando le caratteristiche di un nodo i della rete di comunicazione lo richiedono, essoviene rappresentato mediante una coppia di nodi i' e i" ∈ N e un arco (i',i" ) ∈ A: i' rappresentail punto di arrivo delle comunicazioni al nodo i mentre i" rappresenta il punto di invio dellecomunicazioni da i; l'arco (i',i" ) serve per rappresentare tutte le operazioni relative al transitodelle comunicazioni attraverso i. Parleremo in tal caso di grafo esteso.

I dati caratteristici, per unità di tempo, di una rete di comunicazione che verranno presi inconsiderazione sono i seguenti. Per ogni nodo di comunicazione i, indicheremo con:ui: la capacità massima (di messaggi memorizzabili),ci: il costo unitario di memorizzazione,αi: la affidabilità,ti: il tempo di ritrasmissione della comunicazione;xi: la quantità di comunicazione (memorizzata).

Per ogni canale, rappresentato mediante l'arco (i,j) ∈ A, indicheremo con:uij : la capacità massima (di messaggi inviabili),cij : il costo unitario di trasmissione,αij : la affidabilità,tij : il tempo di trasmissione della comunicazione;xij : la quantità di comunicazione;qij : la dimensione massima dei singoli messaggi.

Nel grafo esteso i dati relativi al nodo di comunicazione i sono associati all'arco (i',i" ).Si ricorda che con FS(i) = {(x,y) ∈ A: x=i} e BS(i) = {(x,y) ∈ A: y=i} si indicano

rispettivamente la stella uscente e la stella entrante di i. Inoltre, con P = {( i0,i1), (i1,i2), …,(iq-1,iq)} indicheremo un cammino (orientato) dall'origine i0 alla destinazione iq formato da qarchi. Infine, si ricorda che un taglio del grafo, (N', N"), è una partizione di N in due sottoin-siemi non vuoti N' e N"; A(N',N") indica l'insieme degli archi del taglio mentre gli insiemidegli archi diretti e inversi del taglio sono indicati rispettivamente con A+(N',N") e A-(N',N").

2 . 3 Problemi di routing

Analizziamo ora alcuni dei più comuni problemi di routing nelle reti di comunicazione. Quandole misure sui nodi rientrano nella valutazione dei cammini, utilizzeremo il grafo esteso. Nonaffronteremo i problemi di determinare l'albero dei cammini di tempo o costo minimo in quantogià affrontati nel corso di Programmazione Matematica e approfonditi nel paragrafo 1.2.

Inizialmente studieremo i problemi di cammino ottimo rispetto a un singolo criterio,successivamente affronteremo il problema di determinare cammini ottimali per due o più criteri.

2.3.1. Il cammino di numero di “hop” minimo

L'obiettivo è di determinare l'albero dei cammini, da una radice r a tutti gli altri nodi, per cui siaminimo il numero di nodi di comunicazione attraversati, detti “hop”. È facile mostrare che ilnumero di hop è uguale alla cardinalità (numero di archi) di un cammino.


55

È stato già osservato che una visita ventaglio del grafo connette ciascun nodo alla radicemediante un cammino formato dal minimo numero di archi. Pertanto, mediante una semplicevisita si può determinare in O(m) l'albero dei cammini “hop” minimi.

Esercizio 2.3.1Descrivere l'algoritmo per la determinazione dell'albero dei cammini “hop” minimi.

2.3.2. Il cammino di affidabilità massima

Sia α ij la affidabilità dell'arco (i,j), espressa come probabilità che un messaggio inviato da ilungo (i,j) arrivi “integro” in j. Supponendo che gli eventi di malfunzionamento degli archisiano indipendenti, l'affidabilità di un cammino P, che indicheremo con α(P), è data da:

α(P) = ∏(i,j)∈ P

α i j .

È possibile modificare l'algoritmo SPT descritto in 1.2.3 per trattare le misure di camminodefinite dal prodotto delle misure di arco. Alternativamente, si osservi che, per la definizionedata, 0 ≤ α ij ≤ 1 per ogni (i,j) ∈ A; introduciamo come misura di ciascun arco l'opposto dellogaritmo della sua affidabilità:

βij = −log α ij , ∀ (i,j) ∈ A;

ovviamente βij ≥ 0. Il valore del cammino P, β(P), è ora la somma dei valori associati agliarchi. Si può pertanto applicare, senza modifiche, un qualsiasi algoritmo SPT_S per risolvere ilproblema dell'albero dei cammini di affidabilità massima. Al termine dell'algoritmo, per ogninodo i connesso alla radice r si ha l'etichetta minima di; è sufficiente effettuare la trasformazioneinversa per ottenere l'affidabilità δi del cammino ottimo da r a i: δi = exp(-di).

Esercizio 2.3.2Descrivere l'algoritmo per la determinazione dell'albero dei cammini di affidabilità massima senza effettuare latrasformazione delle affidabilità degli archi.

2.3.3. Il cammino di portata massima

Quando si vuole determinare il cammino che permetta la massima quantità di comunicazionedall'origine alla destinazione, si utilizza come misura dell'arco (i,j) la sua portata, o capacità,uij . La portata di un cammino P, u(P), è data dalla minima portata degli archi che lo formano:

(2.3.1) u(P) = min{uij : (i,j) ∈ P};

il problema consiste nel determinare l'albero dei cammini di portata massima. È facile adattare loschema algoritmico SPT per trattare questo caso.

L'etichetta di rappresenta, durante l'esecuzione, la massima portata dei cammini da r a iindividuata sino all'iterazione corrente, i = 1, …, n. Pertanto, l'inizializzazione consiste nelporre dr = +∞ e di = 0 per ogni i ≠ r.

Introduciamo ora la variante della condizione di Bellman ponendo a confronto il camminocorrente da r a j, di portata dj, con il cammino che si ottiene dal cammino da r a i aggiungendol'arco (i,j); la sua portata, per la (2.3.1), sarà min{di, uij }, la condizione di Bellman divienepertanto:

dj ≥ min{di, uij }, ∀ (i,j) ∈ A.


56

Se la condizione è violata, è sufficiente aggiornare l'etichetta di j (dj := min{di, uij}), ilsuo predecessore (pj := i) e, nel caso j non sia già contenuto, inserirlo in Q. Si noti che il valoredelle etichette è monotonicamente non decrescente e, se le portate (come è ovvio) sono valorinon negativi, vale la proprietà dimostrata nel Teorema di Dijkstra quando si seleziona a ogniiterazione il nodo di Q di etichetta massima.

Esercizio 2.3.3Descrivere l'algoritmo per la determinazione dell'albero dei cammini di portata massima.

Esercizio 2.3.4Estendere il Teorema di Dijkstra al caso dei cammini di portata massima e dimostrarlo.

2.3.4. Il cammino di frazionamento minimo

In questo paragrafo intendiamo determinare l'albero dei cammini che obblighino il minimofrazionamento in pacchetti dei messaggi. Ad ogni arco (i,j) ∈ A è associata la dimensionemassima qij del messaggio che può essere inviato lungo (i,j). Indichiamo con k la dimensionedel messaggio da inviare dall'origine r alla destinazione s e imponiamo che il frazionamento delmessaggio avvenga all'origine. Il numero di pacchetti in cui il messaggio dovrà esserefrazionato per transitare lungo (i,j) è dato da:

πij = k / qij .

1º caso: messaggi separatiSia P un cammino da r a s; il numero di pacchetti in cui il messaggio viene frazionato per essereinviato lungo p è π(P) = max{πij : (i,j) ∈ P}. L'obiettivo è di determinare un cammino P* da r as per cui π(P*) = min{π(P): P ∈ Prs}, dove con Prs indichiamo l'insieme dei cammini checonnettono r a s.

Analogamente a quanto effettuato nel paragrafo precedente, adattiamo lo schemaalgoritmico SPT a tale problema. Le etichette verranno inizializzate a M = k+1 per ogni nodosalvo la radice r per cui dr = 1.

La condizione di Bellman diviene:

dj ≤ max{di, πij }, ∀ (i,j) ∈ A.

Esercizio 2.3.5Descrivere l'algoritmo per la determinazione del cammino di frazionamento minimo.

Esercizio 2.3.6Estendere il Teorema di Dijkstra al caso dei cammini di frazionamento minimo e dimostrarlo.

Analizziamo il risultato che si ottiene al termine dell'algoritmo per l'intero albero deicammini minimi T = (N, AT). L'etichetta del nodo i ≠ r, di, rappresenta il massimo numero dipacchetti in cui deve essere suddiviso il messaggio da inviare da r a i. Se dall'origine r vengonospediti n-1 messaggi uguali, uno per ciascuna destinazione, e vengono frazionati prima dellaspedizione, allora l'albero dei cammini minimi fornisce la soluzione ottima per ciascunadestinazione i ≠ r.

Valutiamo ora la quantità di comunicazione che si svolge su ciascun arco (i,j) ∈ AT; datoun nodo j, indichiamo con T(j) = (N(j), A(j)) il sottoalbero di T avente j come radice (in altritermini, N(j) è l'insieme dei discendenti di j. La quantità di comunicazione, in numero dipacchetti lungo un arco (i,j) ∈ AT (i = pj) è:


57

(2.3.2) xij = ∑h∈ N(j)

dh.

Infatti, lungo tale arco transitano tanti pacchetti quanti devono arrivare al nodo j e a tutti glialtri suoi discendenti. Il traffico globale sulla rete è dato da:

(2.3.3) X = ∑(i,j)∈ AT

xij .

Un modo alternativo per contare il traffico globale è di ricavare, per ogni nodo i ∈ N, ilnumero di “hop” da r a i sull'albero T; indichiamo con hi tale valore, il traffico globale è dato da:

(2.3.4) X = ∑i∈ N

hidi .

Esercizio 2.3.7Dimostrare l'equivalenza della (2.3.3) e (2.3.4).

Esempio 2.3.1Si consideri il grafo in figura 2.3.1 in cui sono riportate le dimensioni massime qij dei pacchetti per ogni arco(i,j) e il conseguente numero di pacchetti πij per k = 210 = 1024 (gli archi sono bidirezionali).

1

2

3

4

5

6

7

8

20481

20001

7502

750 2

7502

1024 1

7502

380 3

450 3

6402

2505

1806

3803

Figura 2.3.1

L'albero ottimo è descritto in figura 2.3.2; i valori associati ai nodi sono le etichette mentre quelliassociati agli archi sono il numero di pacchetti che transitano attraverso di essi calcolati secondo la (2.3.2)

1

2

3

4

5

6

7

8

1

1 2

22

2

51 5

2

11

13

214

1

Figura 2.3.2

Come si può osservare, i messaggi inviati ai nodi 2 e 3 non vengono frazionati, quelli inviati ai nodi 4, 5,6 e 7 vengono frazionati in 2 pacchetti, mentre il messaggio per il nodo 8 è frazionato in 5 pacchetti. Il trafficoglobale, secondo la (2.3.3) è X = 14 + 1 + 13 + 11 + 2 + 2 + 5 = 48.

Se rileviamo il numero di hop per ogni nodo abbiamo h = [0, 1, 1, 4, 2, 3, 4, 4]; applicando la (2.3.4) siha X = 1·1 + 1·1 + 4·2 + 2·2 + 3·2 + 4·2 + 4·5 = 48.

Osservando il risultato dell'esempio 2.3.1, si può notare che l'obiettivo prefissatoci è statoquello di minimizzare il numero di pacchetti in cui ogni messaggio viene frazionato. Questoobiettivo non coincide con l'obiettivo di minimizzare il traffico globale X sulla rete; infatti, bastaosservare che se il nodo 4 fosse stato collegato al nodo 2, il messaggio da 1 a 4 sarebbe statofrazionato in 3 pacchetti che però avrebbero viaggiato solo su due archi ottenendo unadiminuzione del traffico globale da 48 a 46. Per minimizzare il traffico globale si dovràminimizzare per ogni nodo i il valore hidi, mettendo insieme i due criteri del numero di “hop”minimo e del numero di pacchetti minimo. Torneremo in seguito su questo tipo di problemi.


58

2º caso: messaggio in broadcastingDiverso è il caso in cui il messaggio è unico (messaggio in broadcasting), esso è frazionatoall'origine e viene replicato, sia all'origine che in ciascun nodo intermedio, in tante copie quantisono gli archi uscenti dal nodo dell'albero ottimo. Infatti, in tal caso, il numero di pacchetti incui il messaggio deve essere frazionato per transitare lungo un qualsiasi arco dell'alberobroadcasting T = (N, AT) è dato da π(T) = max{πij : (i,j) ∈ AT}.

Sia Tr l'insieme degli alberi broadcasting con radice r , cioè l'insieme degli alberi dicopertura di G (in questo problema ipotizziamo che il grafo sia non orientato, cioè che ognicanale di comunicazione sia bidirezionale); allora il problema della determinazione dell'alberobroadcasting ottimo consiste nel determinare l'albero T* = argmin{π(T): T ∈ Tr}.

Il problema equivale a determinare il più piccolo valore τ del numero di pacchetti associatiagli archi per il quale il grafo parziale Gτ = (N, Aτ), dove:

Aτ = {( i,j) ∈ A: πij ≤ τ},

sia un grafo connesso. Infatti, per qualunque valore τ' < τ, il grafo Gτ' non è un grafo connessoe quindi non può contenere un albero di copertura di G; essendo Gτ un grafo parziale connesso,un suo albero di copertura è un albero di copertura di G. Pertanto, si può dedurre che π(T*) =τ.

Esercizio 2.3.8Dimostrare la proprietà enunciata.

È facile mostrare che il problema è risolubile applicando la procedura Kruskal descritta nelparagrafo 1.4.4.

Per la valutazione del traffico globale X, si noti che su ciascun arco dell'albero transiteràuna unica copia del messaggio, frazionata in τ pacchetti; pertanto X = (n-1)τ.

Esempio 2.3.2Riprendendo il grafo in figura 2.3.1, è facile osservare che per τ < 5, il grafo Gτ non è connesso (il nodo 8 non èconnesso agli altri), mentre per τ = 5 si ottiene un grafo connesso; un albero di copertura di G5 è mostrato infigura 2.3.3. Il traffico globale è X = 7·5 = 35.

1

2

3

4

5

6

7

8

5

5

5

5

5

5

5

Figura 2.3.3

3º caso: frazionamento con minimo numero di pacchetti e minimo traffico globaleAnalizziamo una singola coppia origine/destinazione (o/d) r , s. Il problema che si vuoleaffrontare è di frazionare meno possibile il messaggio da r a s e, in conseguenza di talefrazionamento, minimizzare il traffico globale lungo il cammino da r a s. Il problema può essereaffrontato a due stadi.

Nel primo si risolve il problema dell'albero dei cammini di frazionamento minimo studiatoall'inizio del paragrafo. Indichiamo con δ = ds il numero di pacchetti minimo per il nodo didestinazione s e con (u,v) l'arco bottleneck (di valore quv minimo) che lungo il cammino da r a simpone il frazionamento, cioè tale che πuv = δ; indichiamo con ρ = quv la dimensione massima


59

dei pacchetti. Consideriamo il sottografo Gρ = (Nρ, Aρ) ottenuto rimuovendo da G tutti gli archi(i,j) ∈ A tali che qij < ρ.

Il secondo stadio del problema viene affrontato sul grafo Gρ; si noti che, per ogni arco (i,j)∈ Aρ, i pacchetti hanno una dimensione corretta. Il cammino che minimizza il traffico globale èun cammino da r a s formato dal minimo numero di “hop”; mediante una visita del grafo Gρ sidetermina in O(m) tale cammino. Indicando con hrs il numero minimo di “hop” da r a s, iltraffico globale è X = δhrs.

4º caso: frazionamento anche nei nodi intermediAnalizziamo ora il caso in cui sia possibile frazionare il messaggio non solo all'origine, maanche nei nodi intermedi; consideriamo la coppia o/d r, s. Si noti che le dimensioni dei pacchettiin cui il messaggio (o uno dei suoi pacchetti) viene suddiviso influenza sensibilmente ilproblema. Vediamolo attraverso un esempio. Si supponga che la dimensione del messaggio siak = 1024 e che esso venga spedito da i a j lungo l'arco (i,j) la cui dimensione massima sia qij =300; pertanto πij = k / qij = 1024 / 300 = 4. Adottiamo la politica di frazionamento a soglia,cioè produrre tutti i pacchetti, salvo eventualmente l'ultimo, di dimensione qij ; otteniamo 3pacchetti di dimensione 300 e un pacchetto di dimensione 124. L'arco successivo, (j,h), lungocui inviare il messaggio ha qjh = 130; il quarto pacchetto non necessita di ulteriori frazionamentimentre ciascuno dei primi tre dovrà essere frazionato a sua volta in tre pacchetti, due didimensione 130 e uno di dimensione 40. Pertanto, in h arriveranno in tutto 10 pacchetti: 6 didimensione 130, uno di dimensione 124 e 3 di dimensione 40. Se avessimo adottato la politicadi frazionamento bilanciato, cioè di produrre pacchetti di dimensione δ = k / πij , salvoeventualmente l'ultimo che avrà dimensione k - δ(πij -1), avremmo ottenuto un primofrazionamento in i consistente in 4 pacchetti di dimensione 256, e un successivo frazionamentoin j di ciascun pacchetto in due pacchetti di dimensione 128. Il risultato sarebbe stato di riceverein h 8 pacchetti tutti di dimensione 128.

Questo esempio mostra la difficoltà del problema per il quale esistono algoritmi per la suasoluzione nei casi più semplici in cui non viene tenuto conto del costo dei frazionamenti, dellaricomposizione del messaggio in nodi intermedi e del suo costo e di limitazioni sul numeromassimo di “hop” sul cammino.

Altri casiNello sviluppo del corso non è possibile analizzare tutti i possibili casi in cui si tiene conto delfrazionamento del messaggio. Se si generalizza il problema, i casi che si ottengono divengonosempre più difficili. È infatti possibile porsi l'obiettivo di minimizzare il traffico globale X, o ilcosto globale che ne consegue; si possono considerare costi di trasmissione, di frazionamento edi ricomposizione; si possono imporre vincoli sul numero massimo di frammenti in cui ilmessaggio può essere decomposto e sulla dimensione minima di ciascun pacchetto.

In diversi problemi si deve imporre il vincolo sul numero massimo di pacchetti chepossono transitare lungo i canali di comunicazione nell'unità di tempo, con la conseguenza che ipacchetti possono percorrere cammini differenti per raggiungere la destinazione.

Estremamente complicati sono i problemi in cui si vuole mantenere un determinato livellodi affidabilità dell'intero messaggio valutando l'affidabilità di ciascuno dei pacchetti; oppure iproblemi in cui viene monitorato l'intero traffico dei messaggi tra tutte le coppie o/d, il loroconseguente frazionamento e le situazioni di congestione lungo i canali di comunicazione o neibuffer nei nodi di comunicazione.


60

2.3.5. Cammini bicriterio ottimi

Analizziamo ora il problema di determinare un cammino che sia ottimale rispetto a due criteridistinti. Sia Prs l'insieme dei cammini che connettono r a s. Ad ogni cammino P da r a s;possiamo associare due valori, v1(P) e v2(P), che rappresentano due misure generiche di P chesi ha interesse a minimizzare.

Confrontiamo ora due diversi cammini P' e P" ∈ Prs; si dice che P' è dominato da P" sev1(P') ≥ v1(P") e v2(P') ≥ v2(P") in cui almeno una delle due disuguaglianze è verificatapropriamente (cioè o v1(P') > v1(P") oppure v2(P') > v2(P")). Infatti P" risulta preferibile a P'per almeno un criterio e non peggiore per l'altro. Se i due cammini hanno uguale valore perentrambi i criteri essi sono detti equivalenti.

Se nessuno dei due cammini (non equivalenti) è dominato dall'altro si avrà:

(2.3.5) v1(P') > v1(P") e v2(P') < v2(P"), oppure v1(P') < v1(P") e v2(P') > v2(P");

in tal caso si dirà che ciascuno è non dominato rispetto all'altro.Il problema della determinazione di un cammino ottimo rispetto a due criteri può non avere

soluzione se si hanno casi di non dominanza; per tale fatto si è interessati a determinare lacollezione dei cammini non dominati, cioè l'insieme PN

rs che risultano non dominati rispetto atutti gli altri cammini di Prs:

(2.3.6) PNrs = {P ∈ Prs: \∃ P' ∈ Prs che domina P}.

Per evitare di considerare un gran numero di cammini equivalenti, in PNrs ne verrà inserito

uno solo di essi. L'insieme PNrs è detto insieme delle soluzioni Pareto ottime e ogni cammino P

∈ Prs è detto una soluzione Pareto ottima del problema dei cammini bicriterio. Pertanto ilproblema dei cammini bicriterio consiste nella determinazione delle soluzioni Pareto ottime. Sinoti che in caso di più di due criteri, è possibile applicare l'i-esimo criterio all'insieme dellesoluzioni Pareto ottime rispetto a i-1 criteri.

L'insieme PNrs gode di una importante proprietà; si supponga di ordinare i q = |PN

rs| camminiin ordine crescente rispetto al criterio v1 (essendo un insieme di soluzioni non dominate privo disoluzioni equivalenti non è possibile che in PN

rs siano contenuti due cammini di uguale valorerispetto al criterio v1 e al criterio v2):

PNrs = {P1, P2,…, Pq}, con v1(Pi) < v1(Pi+1), i = 1,…, q-1.

Allora PNrs è tale che v2(Pi) > v2(Pi+1), i = 1,…, q-1; cioè i cammini sono ordinati in senso

decrescente rispetto all'altro criterio.

Esercizio 2.3.9Dimostrare la proprietà enunciata.

Per mostrare, anche graficamente il concetto di dominanza e di Pareto ottimalità ognicammino P ∈ Prs può essere rappresentato su un piano cartesiano mediante un punto dicoordinate (x,y) = (v1(P),v2(P)). In figura 2.3.4 vi è un esempio di tale rappresentazione.

Se si confrontano i cammini P8 e P9, essi risultano reciprocamente non dominati, mentreP10 è dominato da P9 (le proiezioni dei valori servono per rappresentare l'area dello spazio checontiene i cammini dominati da un determinato cammino). Il cammino P4 domina i cammini P8

e P10. Infine, l'insieme PNrs = {P1, P2,…, P6} in quanto si può verificare facilmente che

nessuno di essi è dominato dagli altri. Anche la proprietà di monotonia dei valori dei cammini


61

Pareto ottimi, crescente per v1 e decrescente per v2, è facilmente verificabile analizzando lecoordinate x e y dei punti che rappresentano tali cammini.

P1

P2P3

P4

P5

P6

P7 P8

P9

10P

v1

v2

Figura 2.3.4

Il problema della determinazione dei cammini Pareto ottimi è in generale un problema NP-arduo in quanto è possibile che la cardinalità q di PN

rs sia esponenziale nella dimensionedell'input, o che per ottenere i cammini Pareto ottimi, si analizzi un numero esponenziale dicammini. Però per problemi particolari, il problema può divenire pseudopolinomiale ofortemente polinomiale, come mostrato nei diversi casi che seguono.

1º caso: cammini di costo minimo e numero di “hop” minimoAnalizziamo ora il problema in cui v1(P) e v2(P) rappresentano rispettivamente il costo e ilnumero di “hop” del cammino P ∈ Prs. Supponendo che il grafo sia privo di cicli negativi, ilvalore che può assumere v2(P) è un valore intero ≤ n-1. A tal fine, adattiamo lo schemaalgoritmico SPT ad un utilizzo a più etichette (detto multilabel) associando, a ciascun nodo i ∈N, n diverse etichette dih, h = 0,…, n-1, in cui l'etichetta dih rappresenta il migliore costo(individuato sino all'iterazione corrente dell'algoritmo) dei cammini da r a i formati da h archi(numero di “hop”). La condizione di Bellman tra cammini formati da un uguale numero di archiè:

(2.3.7) dih + cij ≥ djh+1, ∀ (i ,j)∈ A, h = 0,…, n-2.

Associamo alle etichette i relativi predecessori: pjh indica il nodo che precede j lungo ilcammino (migliore fino ad ora) da r a j formato da h archi, esso verrà indicato dalla coppia⟨ i,h-1⟩. L'insieme dei predecessori descrive un albero contenente come nodi tutte le coppie ⟨ i,h⟩per le quali esiste un cammino da r a i formato da h archi. Per essi vale il seguente teorema:

Teorema 2.3.1L'albero descritto dalla funzione predecessore è un albero dei cammini minimi da r ai nodi delgrafo per ogni possibile valore del numero di archi se e solo se le etichette rappresentano i costidei cammini sull'albero e verificano le condizioni di Bellman (2.3.7).

L'insieme di nodi candidati Q contiene delle coppie ⟨ j,h⟩ che rappresentano il nodo j comedestinazione di cammini formati da h archi. La procedura SPT_multilabel è descritta nellafigura seguente.


62

Procedure SPT_multilabel(r, P, d):begin

for i := 1 to n do for h := 0 to n-1 dobegin P[i,h] := nil; d[i,h] := M end;

d[r,0] := 0; Q := {⟨r,0⟩}; {inizializzazione}repeat

select ⟨u,h⟩ from Q; Q := Q \ {⟨u,h⟩}; {selezione e rimozione di ⟨u,h⟩ da Q}for each (u,v) ∈ FS(u) do

if d[u,h] + c[u,v] < d[v,h+1] then {verifica cond. di Bellman per (u,v)}begin

d[v,h+1] := d[u,h] + c[u,v]; {aggiornamento di dvh+1 e di pvh+1}P[v,h+1] := ⟨u,h⟩ ;if ⟨v,h+1⟩ ∉ Q then Q := Q ∪ { ⟨v,h+1⟩} {inserimento di ⟨v,h+1⟩ in Q}

enduntil Q = Ø {Q = Ø ⇒ cond. di Bellman verificate}

end.

Figura 2.3.5 - La procedura SPT_multilabel

In caso di violazione della condizione di Bellman, il cammino da r a v formato dagli harchi del cammino da r a u e dall'arco (u,v) viene memorizzato mediante il predecessore (pvh+1

:= ⟨u,h⟩) e il suo costo viene memorizzato come nuova etichetta (dvh+1 := duh + cuv). Al termine,per ogni nodo i ∈ N si analizza la sequenza delle etichette dih, h = 0,…, n-1, eliminando siaquelle rimaste a valore M (ad esempio, di0) sia quelle non dominate: essendo la sequenzacrescente per il valore di h si estrae la sottosequenza di etichette a valori decrescenti.

Un possibile ordine nella selezione delle coppie ⟨ j ,h⟩ da Q è dato dall'ordine nondecrescente del numero di “hop” h. A tal fine è sufficiente implementare Q come una fila, infattiè facile verificare che, dopo la coppia ⟨r,0⟩ si estrarranno le coppie ⟨ j,h⟩ per h = 1, quindi quelleper h = 2, sino a vuotare Q. Alle coppie ⟨ j,h⟩ si può estendere il teorema di Dijkstra, infatti ognicoppia non verrà inserita ed estratta da Q più di una volta.

Esercizio 2.3.10Dimostrare il teorema di Dijkstra per il caso in esame.

Quindi ogni nodo verrà esaminato non più di n volte (quanti i possibili valori di “hop”); lacomplessità globale dell'analisi degli archi è pertanto O(mn). La fila Q fornisce implicitamentel'ordine desiderato e quindi la selezione e rimozione delle coppie è effettuata in tempo costante.Ne consegue che la complessità di SPT_multilabel è O(mn). Si noti però che i camminipossono contenere cicli se non si effettuano controlli per evitare ciò (con un aggravio dellacomplessità) o se i dati del problema escludono tali casi (disuguaglianze triangolarigeneralizzate).

Esercizio 2.3.11Applicare la procedura SPT_multilabel al grafo in figura 2.3.6 (con archi bidirezionali) per la radice r = 1 efornire le soluzioni Pareto ottime per il nodo 8.

1

2

3

4

5

6

7

8

1

1

4

4

3

1

3

4

3

4

56

4 4 6

1

1 1

2

Figura 2.3.6


63

Si noti che lo stesso algoritmo SPT_multilabel può essere utilizzato se si vuoledeterminare un cammino di costo minimo da r a i formato da non più di h− archi. La soluzione èinfatti il cammino di etichetta minima dih, h = 0,…, h−. Lo stesso approccio può essere utilizzatose al posto del costo si considera il tempo, l'affidabilità o la portata del cammino (facendoattenzione che in caso di criteri da massimizzare le proprietà di dominanza e di Pareto ottimalitàdevono essere opportunamente adattate).

2º caso: cammini di costo minimo e portata massimaAnche questo problema è polinomiale. Infatti, essendo la portata di un cammino la capacitàminima degli archi che lo formano, come definito in (2.3.1), la portata di un cammino puòassumere al più gli m valori di capacità degli archi.

Supponiamo di avere ordinato i k (≤ m) valori distinti di capacità degli archi nella sequenzaU = {u(1), u(2),…, u(k)}, con u(i) < u(i+1), i = 1,…, k-1. Analogamente al caso precedente,possiamo associare ad ogni nodo i ∈ N più etichette (in questo caso k): l'etichetta dih

rappresenta il costo del migliore cammino da r a i la cui portata è u(h), h = 1,…, k.Ricordando che si vuole minimizzare il costo e massimizzare la portata, la condizione diBellman tra cammini di uguale portata u(h) è:

(2.3.7) dih + cij ≥ djh, se uij > u(h) ,

dih' + cij ≥ djh, se uij = u(h), per ogni h' ≥ h,h = 1,…, k.

La procedura SPT_multilabel può essere adattata per risolvere il problema in esame. Sinoti che un possibile ordinamento di Q, su cui è possibile estendere il teorema di Dijkstra, è diesaminare le coppie in ordine decrescente delle portate (cioè in ordine decrescente dell'indice h).Per ottenere facilmente questo ordine è sufficiente implementare Q mediante k buckets (osecchielli) Q1, Q2,…, Qk: il bucket Qh conterrà le coppie ⟨ i,h⟩, relative al valore di portata u(h).Si inizia con l'esaminare Qk (che inizialmente contiene la sola coppia ⟨r,k⟩ mentre gli altribuckets sono vuoti) e si passa a esaminare il bucket precedente una volta che questi sia vuoto.La procedura ha termine dopo avere esaminato e rimosso tutte le coppie da Q1; per garantirsi chela coppia relativa ad uno stesso nodo sia inserita e estratta da ogni bucket Qh al più una volta,l'ordine di rimozione delle coppie dal bucket corrente avviene secondo il criterio della minimaetichetta. Per analizzare la complessità si osservi che la scansione dei bucket ha complessitàO(k), l'analisi delle condizioni di Bellman ha complessità globale O(mk) mentre la selezione (sei bucket sono implementati come sequenze non ordinate) ha complessità globale O(n2k).Essendo k = O(m), la complessità in tempo di SPT_multilabel per il problema di camminiPareto ottimi di costo minimo e portata massima è O(n2m).

Esercizio 2.3.12Enunciare e dimostrare il teorema di Dijkstra per il caso in esame.

Esercizio 2.3.13Adattare la procedura SPT_multilabel al caso in esame.

Al termine dell'algoritmo, i cammini Pareto ottimi per il nodo i ∈ N sono relativi allasottosequenza delle etichette crescenti sia per i costi che per l'indice relativo alla portata.

3º caso: cammini di costo minimo e affidabilità massimaIl problema risulta più complesso dei precedenti. Infatti, essendo l'affidabilità di un cammino ilprodotto delle affidabilità degli archi, come mostrato nel paragrafo 2.3.2, il numero di possibilivalori di affidabilità può crescere esponenzialmente col numero di nodi del grafo. È possibile


64

adottare un approccio multilabel con il rischio di dover prevedere un numero esponenziale dilabel per ciascun nodo.

4º caso: cammini di costo minimo e frammentazione minimaSi supponga di frazionare il messaggio solo alla radice e di trasmettere i vari pacchetti lungo lostesso cammino. Analogamente a quanto mostrato nel paragrafo 2.3.4, data la dimensione delmessaggio, possiamo ricavare il numero di pacchetti πij per ogni arco (i,j) ∈ A. Analogamenteal secondo caso, possiamo estrarre i k valori distinti Π = {π(1),…, π(k)} di numero di pacchettie adottare l'approccio multilabel.

Esercizio 2.3.14Adattare la procedura SPT_multilabel al caso in esame.

altri casiNella realtà si risolvono molti problemi di cammino multicriterio. Diversi sono legati alfrazionamento del messaggio in pacchetti; sia quando si trasmette in broadcasting sia quando ilmessaggio può essere frazionato anche nei nodi intermedi.

Per brevità di esposizione non affrontiamo questi problemi lasciando al lettore il compitodi approfondire i vari aspetti consultando la letteratura sia di ottimizzazione su reti sia di reti dicomunicazione.

2. Routing in reti di comunicazione Capitolo 2 54 2.2 Il grafo della rete e i dati caratteristici...

Documents

Transcript of 2. Routing in reti di comunicazione Capitolo 2 54 2.2 Il grafo della rete e i dati caratteristici...