• Non ci sono risultati.

Tecniche tomografiche per la rivelazione della topologia e delle capacità dei link di una rete

N/A
N/A
Protected

Academic year: 2021

Condividi "Tecniche tomografiche per la rivelazione della topologia e delle capacità dei link di una rete"

Copied!
215
0
0

Testo completo

(1)

Tecniche tomografiche per la

rivelazione della topologia e delle

capacità dei link interni di una rete

(2)

Indice

1 Il problema della network tomography 6 1.1 Introduzione alla network tomography . . . 6 1.1.1 Motivazioni . . . 7 1.1.2 Possibili usi delle tecniche tomografiche . 8 1.1.3 L’algoritmo expectation maximization (EM) 9 1.2 Esempi di tecniche tomografiche proposte in

let-teratura . . . 11 1.2.1 Tecniche di scoperta della loss rate . . . . 12 1.2.2 Tecniche di stima della distribuzione del

ritardo . . . 14 1.2.2.1 Tecniche basate sulla stima ML 14 1.2.2.2 La stima a massima pseudo-likelihood 17 1.2.2.3 Tecniche di stima della

distribu-zione del ritardo nel dominio tra-sformato . . . 19 1.2.3 Tecniche “algebriche” di network

(3)

1.2.4 Tecniche di stima delle matrici di traffico 27

2 Il problema della topology discovery 33

2.1 Introduzione alla topology discovery . . . 33

2.1.1 Metodi non tomografici di topology disco-very . . . 34

2.1.1.1 Traceroute . . . 34

2.1.1.2 Doubletree . . . 40

2.1.1.3 Listening OSPF . . . 41

2.1.1.4 Soluzioni basate su SNMP . . . 44

2.1.2 Introduzione ai metodi tomografici di to-pology discovery . . . 47

2.2 L’uso delle metriche per la ricostruzione della to-pologia . . . 49

2.2.1 La covarianza dei ritardi . . . 52

2.2.2 Metriche ottenute con la tecnica packet sandwich . . . 55

2.3 Ricostruzione di una topologia ad albero a partire dalle metriche misurate . . . 61

2.3.1 Albero binario e tree pruning . . . 61

2.3.2 Tecniche basate sulla stima dell’albero com-plessivamente più verosimile . . . 65

2.4 Topology discovery con sorgenti multiple . . . 68

2.4.1 Individuazione dei punti di innesto di due topologie ad albero . . . 69

2.4.2 Tecniche di probing per la ricostruzione di una topologia a più sorgenti . . . 73

2.4.3 Altre possibili soluzioni per la tomografia da sorgenti multiple . . . 78

(4)

3 Topology discovery con la conoscenza delle possi-bili capacità dei link 83 3.1 Ricostruzione dell’albero relativo ad una sorgente

di probe . . . 84 3.1.1 Introduzione . . . 84 3.1.2 Strategie di decisione . . . 87

3.1.2.1 Probe packet sandwich con in-cremento lineare del Time-To- Li-ve . . . 89 3.1.2.2 Decisioni separate per i path tra

due branching point . . . 91 3.1.2.3 Decisioni coerenti su di un path

end-to-end . . . 92 3.1.3 Precisione ed efficienza delle tecniche

pro-poste . . . 97 3.1.4 Ricostruzione dell’albero a partire dalle

sequenze dei valori di capacità stimati . . 100 3.1.5 La ricostruzione della topologia

comple-ta a partire dagli alberi relativi a sorgenti diverse . . . 110

4 Analisi del disturbo da cross traffic e metodi di

filtraggio 123

4.1 Il disturbo nelle misure di tipo packet-sandwich . 123 4.1.1 Modalità di simulazione utilizzate . . . . 123 4.1.2 Caratterizzazione del rumore . . . 127 4.1.2.1 Valutazione del modello gaussiano127 4.1.2.2 Caratterizzazione di alcuni

(5)

4.2 Metodi di filtraggio delle misure affette da disturbo144 4.2.1 Illustrazione degli algoritmi . . . 144 4.2.2 Risultati simulativi . . . 152

5 Case study: ricostruzione della topologia di una

possibile rete reale 155

5.1 Scenario di simulazione . . . 155 5.1.1 Scelta della topologia e motivazioni . . . . 155 5.1.2 Topologia utilizzata in sede di simulazione 158 5.1.3 Modalità di simulazione del cross traffic . 160 5.2 Ricostruzione degli alberi con tecniche tomografiche162

5.2.1 Risultati dell’applicazione delle diverse stra-tegie di decisione . . . 163 5.2.1.1 Strategia di decisione basata

sul-l’incremento lineare del TTL . . 163 5.2.1.2 Strategia di decisione basata

sul-la coerenza delle sequenze di link e filtraggio dei dati rumorosi . . 170 5.2.1.3 Decisioni a partire dall’albero a

branching point . . . 175 5.2.1.4 Strategia di decisione basata su

decisioni indipendenti e clustering 178 5.2.2 Risultati ottenuti con modalità diverse di

probing . . . 180 5.2.2.1 Simulazioni eseguite con packet

sandwich con lunghezza ridotta del pacchetto centrale . . . 180

(6)

5.2.2.2 Ricostruzione dell’albero a bran-ching point sfruttando la cova-rianza dei ritardi . . . 185 5.3 Ricostruzione della topologia completa a partire

dagli alberi . . . 188

(7)

Capitolo 1

Il problema della

network tomography

1.1

Introduzione alla network

tomogra-phy

La network tomography comprende tutte quelle tecniche che consentono di ottenere informazioni sullo stato interno di una rete di computer senza necessitare di collaborazione da parte dei nodi interni della rete.

Le informazioni di interesse vengono generalmente ricavate dall’analisi di misure ottenute da un processo di active probing, che consiste nell’invio di pacchetti ad un gruppo di nodi della

(8)

rete a cui possono essere richieste diverse forme di collaborazio-ne. Le tecniche di network tomography permettono di ricavare, ad esempio, la topologia interna di una rete, la distribuzione del ritardo di accodamento sui vari link, la probabilità di perdita ad essi associata o la matrice di traffico end-to-end della rete.

1.1.1

Motivazioni

L’uso di tecniche di misura che non richiedano collaborazione da parte dei nodi interni della rete si presenta vantaggioso sotto diversi punti di vista.

Esso, infatti, come sottolineato in [6], può limitare l’entità delle risorse di rete necessarie ad effettuare il processo di misu-ra: i router non devono eseguire altre funzioni oltre al normale forwarding dei pacchetti e non devono utilizzare tempo e capa-cità di processing per rispondere a particolari interrogazioni. E’ inoltre possibile ottenere informazioni sullo stato interno della rete anche nel caso di malfunzionamento di uno o più router Questo aspetto rende attrattivo l’uso delle tecniche tomogra-fiche anche per gli amministratori di un dominio, che hanno così a disposizione degli strumenti di trouble shooting che in-terferiscono in modo marginale con il traffico ordinario della rete e che permettono di individuare le cause del suo cattivo funzionamento.

Le tecniche di network tomography consentono inoltre di esplorare lo stato interno di reti appartenenti ad un dominio am-ministrativo in cui non si hanno i privilegi necessari per interro-gare direttamente i nodi interni e in cui i router sono configurati con accorgimenti tali (firewall, ICMP rate limiter) da rendere

(9)

inefficaci le soluzioni tradizionali. In questo modo è possibile ve-rificare, per esempio, se i service level agreements stipulati con un altro amministratore siano effettivamente rispettati. Un’al-tro possibile campo di applicazione di queste soluzioni, come evidenziato in [37], è quello delle applicazioni multicast, che pos-sono beneficiare delle conoscenza della rete acquisit tramite la network tomography: in questo caso i pacchetti inoltrati ai vari receiver costituiscono implicitamente delle probe e i protocolli di controllo della sessione multicast (come RTCP) costituiscono un canale ideale per comunicare al sender i risultati delle misure effettuate end-to-end.

1.1.2

Possibili usi delle tecniche tomografiche

Come già accennato nell’introduzione, vi sono diversi tipi di informazioni sullo stato interno di una rete che possono esse-re estratte mediante tecniche di network tomography; è quindi possibile classificare le diverse soluzioni proposte in letteratura in base al dato che si vuole estrarre dalle misure effettuate. Al-la luce di questa considerazione si possono individuare diverse classi di soluzioni tomografiche:

• soluzioni per l’individuazione della topologia interna di una rete (topology discovery)

• soluzioni per la scoperta della loss rate sui diversi link di una rete

• soluzioni per la scoperta della distribuzione del ritardo di accodamento sui link della rete

(10)

• metodi “algebrici” che consentono di ricavare diversi tipi di informazione

Nella prossima sezione verranno illustrate alcune delle tecniche proposte per ciascuna di queste classi, ad eccezione della topolo-gy discovery che verrà trattata approfonditamente nel capitolo 2 e sviluppata in quelli successivi.

1.1.3

L’algoritmo expectation maximization (EM)

L’algoritmo expectation maximization è alla base di molte delle tecniche tomografiche che verranno illustrate in seguito e ne ver-rà quindi fornita una breve illustrazione; si rimanda ad esempio a [11] per una trattazione completa.

L’algoritmo EM (1)fornisce una procedura di tipo iterativo per ottenere la stima a massima verosimiglianza di un parame-tro Θ a partire da un set di dati che sono in parte noti (known data, raccolti nel vettore y) e in parte incogniti (unknown da-ta, raccolti nel vettore x); formalmente l’algoritmo permette di individuare bΘ = argmaxΘlog(p(x, y; Θ)).

Dato un valore iniziale arbitrario di Θla procedura iterativa proposta permette di ottenere una sequenza di valori Θi a

ve-rosimiglianza crescente, ma non è garantito che tale sequenza abbia come limite il punto di massimo assoluto della funzione di verosimiglianza: è possibile che tale algoritmo individui un punto di massimo relativo, a seconda del valore iniziale che si è scelto per il parametro.

L’algoritmo EM si presta molto bene a risolvere problemi di network tomography: in tali casi, infatti, si hanno a

(11)

disposizio-Algoritmo 1Algoritmo EM

• Inizializzazione: si sceglie un valore iniziale arbitrario Θ0

• E-step: si calcola la media della funzione di logverosimi-glianza degli unknown data condizionata al valore dei dati noti ed in corrispondenza del valore corrente di Θ

Q(Θ, Θi) = E[log(p(x, y; Θ)|y]Θi

• M-step: si aggiorna il valore di Θimassimizzando rispetto

a Θla quantità precedentemente calcolata

Θi+1= argmaxΘiQ(Θ, Θi)

• Si prosegue in modo iterativo fino a che il valore di Θinon

(12)

ne delle misure osservate (i known data y) che sono combinazio-ni lineari di quantità che sono dipendenti dai parametri che si vogliono stimare, ma che non possono essere misurate tramite probe end-to-end. Si supponga , ad esempio, di voler stimare la media Θ del ritardo di accodamento sui link della rete: i dati che si hanno a disposizione sono le misure y dei ritardi end-to-end, ma esse sono composte dalla somma dei ritardi x sperimentati su ciascun link, che hanno una stretta relazione statistica con il parametro Θ ma che non è possibile misurare direttamente.

1.2

Esempi di tecniche tomografiche

pro-poste in letteratura

Le tecniche che verranno trattate in questo paragrafo si propon-gono di stimare differenti caratteristiche prestazionali associate ai vari link della rete, nota a priori la topologia della stessa. In particolare, salvo eccezioni che verranno messe in evidenza, tali soluzioni ipotizzano che la topologia della rete sia descrivi-bile come un albero che ha radice nel nodo che esegue l’active probing e le cui foglie sono costituite dai nodi della rete a cui i pacchetti di probe vengono indirizzati; come verrà esposto in modo approfondito nella sezione 2.1.2, questo tipo di visione della rete porta ad ignorare la presenza di alcuni nodi interni.

In un contesto reale si può ammettere di conoscere la topo-logia della rete in esame, nel caso in cui si disponga dei provilegi di amministratori di tale rete o in quello in cui si siano effettua-te in precedenza indagini di topology discovery basaeffettua-te su altre

(13)

tecniche (sono disponibili soluzioni tomografiche o altri metodi più invasivi come traceroute). Si consideri comunque che le in-formazioni topologiche di cui si dispone potrebbero non essere più aggiornate, dato che la struttura logica di una rete può va-riare nel tempo a causa di malfunzionamenti degli apparati e di altri fattori (ad esempio nel caso in cui i protocolli di routing usino funzioni di costo dipendenti dalle condizioni di carico della rete).

1.2.1

Tecniche di scoperta della loss rate

Vi sono diverse proposte per stimare la loss rate associata ad alcuni dei link della rete; fra queste una delle più interessanti è quella di Lo Presti e Duffield, che presuppone però la possi-bilità di inoltrare probe multicast . Gli autori individuano una relazione deterministica fra alcune misure di probabilità di per-dita effettuabili end-to-end e le probabilità di perper-dita associate ai link della rete. In particolare essi propongono di misurare end-to-end:

• La probabilità che un pacchetto arrivi dalla sorgente del-l’albero ad una data foglia i

• La probabilità, per ciascun nodo interno k, che una probe multicast raggiunga almeno una delle foglie del sottoalbero che ha radice in k

• La probabilità che, per ogni figlio j del nodo k, una pro-be multicast raggiunga almeno una foglia appartenente al sottoalbero che ha radice in j

(14)

A partire da tali quantità, che sono misurabili end-to-end una volta che sia nota la topologia ad albero della rete, è possibile ot-tenere tramite un algoritmo di deconvoluzione le probabilità che una probe raggiunga un determinato nodo interno m, indicata con αm; dato che αm=Q(1 − pj) , dove pjindica la probabilità

di perdita sul link j a monte del nodo interno m, conoscendo αm

per ogni m è possibile ricavare in modo ricorsivo le probabilità di perdita pj per ogni link della rete.

L’uso di probe multicast è comune a molte proposte; è pos-sibile tuttavia, in alcuni casi, sostituire ad una probe multicast una serie di pacchetti back-to-back inviati a diversi receiver; tale procedura introduce alcune imprecisioni nel processo di misura, che sono quantificate in [16].

Altri algoritmi, piuttosto che ricavare una espressione espli-cita della probabilità di perdita per ogni link effettuano delle stime di tali probabilità: è il caso dell’algoritmo, illustrato in [2], che fa uso dell’algoritmo Expectation Maximization. Tale soluzione è anche particolarmente interessante in quanto per-mette di sfruttare misure effettuate a partire da diverse sorgenti e dunque, relative ad alberi diversi.

Un’altra soluzione degna di nota nell’ambito della stima della probabilità di perdita è quella proposta in [22]: essa non neces-sita infatti dell’esecuzione di una procedura di active probing, ma ricava la probabilità di perdita end-to-end osservando la fre-quenza con cui le connessioni TCP ritrasmettono i pacchetti; a partire dalla probabilità di perdita end-to-end, gli autori pro-pongono tre modalità di inferenza della probabilità di perdita sui vari link. Una prima soluzione (random sampling) consiste nell’assegnare più volte ad ogni link una probabilità di

(15)

perdi-ta random che sia compatibile con la misura toperdi-tale riscontraperdi-ta end-to-end e nel fare una media delle diverse realizzazioni: ta-le metodo non garantisce una stima precisa delta-le probabilità di perdita, ma per la sua semplicità, può essere utile per localizzare velocemente quali link siano congestionati. Gli autori riportano altre due soluzioni, una basata su tecniche di ottimizzazione li-neare e una basata sulla ricerca di una soluzione ottima in senso MAP tramite la tecnica del Gibbs sampling; tali metodi garanti-scono una precisione notevolmente maggiore di quella ottenibile con il random sampling, ma al prezzo di un consistente aumento della complessità computazionale. Anche la soluzione proposta in [31] usa una stima della probabilità di perdita end-to-end ricavata dall’osservazione dei flussi TCP, ma elabora tale dato tramite un algoritmo di tipo Expectation Maximization.

1.2.2

Tecniche di stima della distribuzione del

ritardo

1.2.2.1 Tecniche basate sulla stima ML

Il modo più intuitivo di affrontare il problema della stima della distribuzione del ritardo di accodamento sui link della rete è quello di dividere il range di possibili valori che tale ritardo può assumere su un link in un numero finito di intervalli (bin) e di associare un valore di probabilità a ciascuno di essi. In questo modo il problema si riduce dalla stima di una funzione di distribuzione a quella del valore di un numero finito di parametri (per questa ragione si parla di tecniche parametriche), a scapito di una perdita di precisione dovuta alla “quantizzazione” dei

(16)

possibili valori del ritardo. La figura 1.1 mostra in linea continua una possibile distribuzione del ritardo e in linea tratteggiata la sua stima parametrica ottenuta dividendo in bin l’intervallo dei possibili valori. Si noti come un modello del ritardo di questo tipo presupponga la stazionarietà della rete almeno per la durata del processo di misura.

In [14] è proposta una soluzione per la stima parametrica dei ritardi basata sull’algoritmo expectation maximization. In questo caso i parametri da stimare sono le quantità

α(i)k = p(ritardo k − esimo link i − esimo bin)

Gli unknown data sono invece i termini n(i)k che indicano

il numero delle probe (N in totale) che hanno incontrato sul link k un ritardo di accodamento compreso all’interno dell’i-esimo bin, mentre i dati noti sono i ritardi misurati end-to-end. Per semplificare l’analisi si suppone che tutti i valori del ritardo appartenenti allo stesso bin siano approssimabili con il valore centrale di tale intervallo; si introduce in questo modo un ulteriore errore di quantizzazione.

Con queste definizioni è possibile scrivere gli step dell’algo-ritmo EM • E-step Q(θ, θ0) =X k X i b n(i)k∗ log(α(i)k)

con bn(i)k= E[n(i)k|y]

• M-step

(17)

Figura 1.1: Effetti della suddivisione in bin dei possibili valori del ritardo su un link

L’espressione di bn(i)k è più complessa e viene dunque omessa.

Si può notare come l’M-step corrisponda banalmente alla stima empirica della probabilità di un evento discreto, con la differenza che il numero di eventi favorevoli non è un numero effettivamente osservato, ma, essendo parte degli unknown data, è sostituito con la sua media condizionata alle misure disponibili. Anche l’E-stepcorrisponde semplicemente al logaritmo del prodotto di termini del tipo αi(k)n(i)k, sempre a meno della sostituzione dei

termini ignoti n(i)k con la loro media condizionata.

Gli stessi autori in [2] estendono tale approccio in modo da sfruttare le misure ottenute da più sorgenti.

Le stime di tipo parametrico della d.d.p del ritardo presen-tano talvolta alcune rigidità, soprattutto nel caso in cui le di-stribuzioni su link diversi siano molto differenti l’una dall’altra; in tal caso, infatti, la scelta di rappresentare distribuzioni molto diverse tra loro con lo stesso set di bin porta appare una

(18)

ap-prossimazione molto pesante. Per superare questo problema, in [34] si propone di non fissare a priori il numero e l’estensione dei bin che approssimano la distribuzione del ritardo su ciascun link della rete, ma di considerarli fra i parametri ignoti dell’algoritmo Expectation Maximization.

Un altro metodo non parametrico per la stima della distri-buzione dei ritardi è proposto in [28]: gli autori propongono di rappresentare tale distribuzione come una combinazione lineare con parametri incogniti di componenti scelte all’interno un set di funzioni note (tipicamente si tratta di una massa di proba-bilità e di una serie di variabili aleatorie gaussiane). La scelta delle componenti e la stima dei parametri di tale combinazione per ogni link della rete avviene con una procedura di tipo EM.

Entrambe queste soluzioni, d’altra parte, considerando igno-to l’ordine del modello (il numero di parametri da stimare), soffrono del problema dell’overfitting, che verrà affrontato suc-cessivamente in 2.2.2.

Un’ultima proposta degna di nota è quella contenuta in [7]: si tratta dell’unica soluzione, per quanto è stato possibile ri-velare nell’ambito di questa ricerca bibliografica , pensata per la stima della distribuzione dei ritardi su reti con condizioni di traffico non stazionarie e capace dunque di rivelare la variazio-ne temporale della distribuziovariazio-ne del ritardo di accodamento sui link interni della rete.

1.2.2.2 La stima a massima pseudo-likelihood

Si è visto nei precedenti esempi come gli algoritmi tomografici necessitino di frequente di massimizzare funzioni di

(19)

verosimi-glianza molto complesse: tale compito, anche con l’aiuto del-l’algoritmo Expectation Maximization, comporta spesso calcoli di complessità proibitiva. Per risolvere questo problema in [20] viene proposto di modificare la funzione di likelihood in modo da renderne più veloce la massimizazione: per tale ragione gli autori definiscono tale approccio maximum pseudo-likelihood.

Si consideri, infatti, che molti problemi di network tomogra-phy possono essere modellati tramite un sistema lineare sotto-determinato del tipo AX = Y : in particolare Y rappresenta il vettore delle prestazioni misurate end-to-end verso ogni pos-sibile destinazione, mentre X è il vettore di quelle, incognite, sperimentate su ogi link; (l’esempio più banale è quello dei ri-tardi end-to-end che sono una combinazione lineare dei riri-tardi sperimentati su ogni singolo link); il generico termine ai,jdella

matrice A vale invece 1 se il link j appartiene al path con desti-nazione i, 0 diversamente . Una modellizzazione di questo tipo può essere adattata anche a rappresentare parametri di presta-zioni che non sono legati, originariamente, una relazione di tipo lineare. Si consideri, per esempio, la probabilità di perdita di un pacchetto: la probabilità di perdita osservata end-to-end non è di certo pari ad una combinazione lineare delle probabilità di perdita sui singoli link, ma se si considera invece il logaritmo della probabilità di corretta ricezione del pacchetto osservata end-to-end, si può notare immediatamente come esso sia legato da una relazione lineare al logaritmo della proprietà di corretta trasmissione sui singoli link. Nel sottoparagrafo successivo sarà mostrato come si possa ricondurre ad un modello lineare anche il problema della stima della densità di probabilità dei ritardi sui link.

(20)

E’ chiaro che le variabili aleatorie del vettore Y saranno in generale dipendenti tra di loro, in quanto i path seguiti dalle pro-be avranno un certo numero di link in comune: di conseguenza l’espressione della densità di probabilità congiunta p(Y |Θ) ri-sulterà, a causa dell’alto grado di correlazione tra le variabili, notevolmente complessa. L’approccio del tipo pseudo-likelihood consiste nel semplificare tale funzione trasformandola in un pro-dotto di termini indipendenti del tipo p(yi, yj|Θ), per ogni

cop-pia (i,j) di possibili destinazioni. Tale semplificazione porta di fatto a considerare la rete come l’unione di path indipendenti verso ogni coppia di destinazioni, come indicato in figura 1.2 ; dal punto di vista algebrico si tratta di sostituire al sistema AX = Y un insieme di sistemi indipendenti ottenuti conside-rando ogni possibile coppia di righe del sistema originario. Tale approccio è naturalmente approssimativo, in quanto trascura le correlazioni, effettivamente presenti nel problema reale, tra i di-versi sottoproblemi; gli autori, tuttavia, dimostrano che la sem-plificazione introdotta porta ad una stima comunque consistente ed asintoticamente gaussiana del parametro Θ.

1.2.2.3 Tecniche di stima della distribuzione del ritar-do nel ritar-dominio trasformato

Un’alternativa alla divisione in bin del range dei possibili va-lori del ritardo è quella di cercare di risolvere il problema in un dominio trasformato, avvalendosi della notevole semplifica-zione illustrata in [27]. Si consideri infatti il sistema lineare che lega, come illustrato nel precedente sottoparagrafo, i ritardi end-to-end Y ai ritardi sperimentati sui link X: la distribuzione

(21)

Figura 1.2: semplificazione introdotta con l’approccio pseudo likelihood

di probabilità del riardo end-to-end è data dalla convoluzione delle distribuzioni dei ritardi sperimentati sui singoli link della rete, supposti tra loro indipendenti. Se si considerano, però, le Cumulant Generating Function di tali distribuzioni, si no-ta facilmente che esse sono legate dalla stessa relazione lineare AX = Y che lega tra loro le singole realizzazioni dei ritardi. Più formalmente, sia f (xi)la d.d.p. del ritardo xie sia Gxila sua

cumulant generating function: si può notare che f (yi) = f (x1) ⊗ f (x3)...f (xn) Gyi = Gx1+ Gx3+ ...Gxn= n X j=1 ai,jGxj

(22)

Il vettore Gy può essere direttamente stimato a partire dai

ritardi misurati end-to-end; sia yi(k) il k-esimo campione del

ritardo end-to-end misurato dal ricevitore i e sia N il nume-ro totale dei campioni disponibili: si può stimare facilmente la cumulant generating function del ritardo yi come

b Gyi(t) = log( N X k=1 ejtyi(k)/N )

Sarebbe dunque possibile, in linea di principio, risolvere il sistema e ricavare le cumulant generating function della densità di probabilità del ritardo su ogni link, e da esse, per antitrasfor-mazione, le densità stesse. Questo approccio si scontra con il fatto che nella quasi totalità dei casi la matrice A ha determi-nante nullo, in quanto il sistema è largamente sottodeterminato (il numero di link interni di una rete è molto maggiore di quello delle destinazioni verso le quali si esegue il probing), ma conserva comunque una sua attrattività in vista di sviluppi successivi.

Un’altra proposta che raccoglie l’idea di studiare i ritardi nel dominio trasformato è quella illustrata in [5]: d.d.p. del ritardo su ogni link viene modellata come una combinazione lineare di diverse funzioni di parametri incogniti (gli autori suggeriscono di usare una massa di probabilità, una serie di bin a distribuzione uniforme e una coda a decadimento esponenziale). La funzione caratteristica Mxjdi tale distribuzione è facilmente calcolabile,

in quanto l’operazione di trasformazione non cambia i parametri della combinazione lineare; siano φn le componenti della d.d.p.

, Mφn le relative funzioni caratteristiche e a

i

n i pesi della

(23)

i: si avrà che

Mxj =

X

n

ainMφn

La funzione caratteristica del ritardo end-to-end è stimabile dai campioni del ritardo misurato:

c Myi(t) = N X k=1 ejtyi(k)/N

I coefficienti della combinazione lineare caratteristica di ogni link vengono stimati imponendo la minimizzazione di una “di-stanza” fra la funzione caratteristica stimata dai dati e quella ottenuta come prodotto delle funzioni caratteristiche di tutti i link sul path: più formalmente

θ = argmin(dist( cMyi,

Y

j

Mxj))

Tale operazione di minimizzazione è condotta con tecniche di tipo stocastico.

1.2.3

Tecniche “algebriche” di network

tomo-graphy

Si è già descritto come i problemi di network tomography possa-no essere visti come l’estrazione di informazioni sulle prestazioni X dei singoli link, che sono legate alle prestazioni Y osservabili end-to-end tramite la relazione lineare AX=Y. Si è già accenna-to, d’altra parte, come tale sistema sia nella quasi totalità dei

(24)

casi sottodeterminato. Le tecniche che verranno descritte cerca-no, nell’impossibilità di risolvere il sistema e di ricavare il valore di tutte le componenti del vettore X, di “estrarre” dal vettore dei dati Y più informazioni possibile: in pratica esse cercano di ricavare la somma dei parametri prestazionali X per sequenze di link consecutivi, riuscendo così ad ottenere informazioni sullo stato di alcuni subpath interni alla rete.

Una prima soluzione di questo tipo è illustrata in [35] ; si ipotizzi che A sia una matrice di m righe e n colonne con m<n: è possibile, mediante l’ algoritmo di eliminazione di Gauss, trovare una matrice T tale che A0 = A ∗ T , dove la matrice A’ è una

matrice m*n con la struttura rappresentata in basso.

A0= 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 ∗ 1 0 0 0 0 0 0 0 ∗ ∗ 1 0 0 0 0 0 0 ∗ ∗ ∗ 1 0 0 0 0 0 ∗ ∗ ∗ ∗ 1 0 0 0 0 ∗ ∗ ∗ ∗ ∗ 0 0 0 0 ∗ ∗ ∗ ∗ ∗ 0 0 0 0 ∗ ∗ ∗ ∗ 0 0 0 0 ∗ ∗ ∗ ∗ ∗ 0 0 0 0

Il sistema da risolvere, introducendo un nuovo vettore inco-gnito B tale che X = T ∗ B, può essere trasformato

AX = AT B = A0B = Y ⇒ A0B = Y

Dato che le ultime n-m righe di A’ sono composte soltanto di 0, è possibile risolvere il sistema e ricavare i primi m elementi

(25)

del vettore B; non è però possibile ricavare da B il valore di una qualche componente di X perchè gli unltimi n-m elementi di B non sono noti. Si consideri allora un vettore C composto da 0 e 1 e tale che X

cjTi,j= 0 ∀i > m

Si moltiplichino poi entrambi i membri di X = T ∗ B per tale vettore C: per la proprietà enunciata questo procedimento consente di ricavare il valore della somma degli xitali che ci= 0,

dato che gli ultimi n-m elementi di B vengono moltiplicati per 0 e non sono dunque rilevanti. Scegliendo opportunamente il vettore C si è dunque in grado di ricavare il valore della somma dei parametri prestazionali di alcune sequenze di link, pur in presenza di un sistema sottodeterminato.

Un altro approccio a tale problema è presentato in [36] ed è basato sulla formalizzazione del concetto di MILS (Minimum Identifiable Link Sequence) . I MILS sono insiemi di link della rete consecutivi tali che:

1. Essi sono di lunghezza minima, nel senso che non possono essere decomposti in una ulteriore sequenza di MILS 2. Le loro prestazioni possono essere determinate

univoca-mente a partire da misure end-to-end

Si noti che, anche in questo caso, non si fa riferimento ad una particolare misura prestazionale: anche questo metodo può es-sere applicato a qualsiasi parametro per il quale la relazione fra valore a livello di link e valore misurato end-to-end sia esprimibi-le sotto forma di un sistema lineare. Nel seguito della trattazione

(26)

si assumerà anche che tutti i link siano bidirezionali e che la mi-sura ad essi associata non dipenda dal verso di percorrenza: gli autori dimostrano che, in presenza di link monodirezionali, non è possibile isolare MILS di lunghezza inferiore a quella dei per-corsi end-to-end , anche se propongono in seguito un’euristica per risolvere tale problema.

Per capire meglio il concetto di MILS si faccia riferimento alla figura 1.3 e si indichino con XV la somma delle misure

relative ai link appartenenti al MILS V e con YIJla misura

end-to-end relativa al path che collega i nodi I e J: la sequenza E composta dal link 3 è un MILS il quanto non è individuabile come sequenza di altri MILS e si può ricavare X3 come (Y15+

Y24− Y12− Y45)/2. Anche il path end-to-end B è un MILS,

nonostante al suo interno sia isolabile il MILS E, dato che non è comunque possibile coprire l’intero path come combinazione di altri MILS (in questo caso XB coincide con Y24ed è quindi

ovviamente ricavabile da misure end-to-end).

Gli autori propongono un algoritmo iterativo per identificare i MILS della rete che prende in esame tutti i possibili subpath presi in ordine di lunghezza crescente; tale algoritmo è riportato in 2.

Tale soluzione si presenta non come un metodo tomografico a se stante, ma come un modo per rendere più efficienti altre tecniche tomografiche: si può pensare infatti di ottenere da es-sa delle informazioni sulle misure globali associate ai MILS e di servirsi poi di altre soluzioni per ottenere un’analisi più fine dello stato della rete all’interno dei MILS stessi. In un contesto in cui le tecniche tomografiche siano usate come strumenti di troubleshooting, si può pensare di usare tale tecnica per

(27)

indivi-Algoritmo 2Identificazione dei MILS in una rete di topologia nota

• Partire dai subpath di lunghezza V=1 link

• Fino a che non si sono esaminati tutti i possibili subpath

– Per ogni subpath di lunghezza V:

∗ Se il primo link del subpath è anche il primo di un MILS con lunghezza minore di V tale subpath non è un MILS

∗ In caso contrario controllare che la misura as-sociata a tale subpath sia ricavabile da una combinazione lineare di misure end-to-end ∗ Se sono stati esaminati tutti i subpath di

(28)

Figura 1.3: Topologia della rete esemplificativa (a sinistra) e MILS individuabili (a destra)

duare la zona della rete in cui nascono i problemi e di utilizzare tecniche più invasive per isolare, in quella zona, il bad link che è causa della degradazione delle prestazioni.

1.2.4

Tecniche di stima delle matrici di traffico

La stima delle matrici di traffico, a differenza degli altri proble-mi risolvibili con metodi di network tomography, comporta la necessità di stimare misure di performance end-to-end a partire da misure locali riguardanti i singoli link della rete. Il problema consiste infatti nel riuscire a stimare l’intensità del traffico end-to-end per ogni coppia origine-destinazione della rete a partire dalla conoscenza dell’intensità del traffico cumulativa (ovvero re-lativa alla somma dei singoli flussi di dati) registrata sui diversi link. Si tratta di un campo di indagine di grande ricaduta

(29)

appli-cativa: la conoscenza delle matrici di traffico è molto importante ai fini della configurazione e del design di una rete, ma la misu-ra diretta di tali gmisu-randezze richiederebbe l’uso di una quantità significativa delle risorse a disposizione (capacità di processing, capacità trasmissiva). Una delle soluzioni più avanzate a tale problema è illustrata in [3]. La modellizzazione matematica di tale problema sfrutta ancora un sistema lineare del tipo Y=AX, dove Y è il vettore delle misure note e X quello delle presta-zioni da stimare. In questo caso, tuttavia, le componenti del vettore Y sono le misure dell’intensità di traffico misurate sui singoli link e quelle del vettore X sono invece le intensità misu-rate end-to-end per ogni possibile coppia origine-destinazione. La matrice A è invece composta da componenti aij che valgono

1 se il link i-esimo è attraversato dal flusso di dati relativo alla j-esima coppia origine-destinazione, 0 altrimenti. In particolare le componenti dei vettori sono dei byte-counts, ovvero registrano il numero di byte transitati in una certa unità di tempo.

Per dare un’idea della soluzione proposta si assumerà la sta-zionarietà completa dei flussi di traffico, e si ipotizzerà di avere un numero T di misure indipendenti dell’intensità del traffico sui link. Si modelleranno inoltre le intensità Y dei flussi di traffico come variabili aleatorie gaussiane ed indipendenti. In partico-lare il generico flusso di traffico sarà una variabile aleatoria xi

con distribuzione:

xi∼ N (λi, ϕλci)

La quantità da stimare sarà λ, mentre gli altri due parametri saranno fissati a priori. Sotto queste ipotesi è possibile scri-vere l’espressione della logverosimiglianza del vettore λ, dato

(30)

che l’osservato Y è dato dalla trasformazione lineare del vettore gaussiano X attraverso la matrice A. Infatti, indicando con λil vettore dei valori medi dei flussi di traffico λi e con Σla matrice

diagonale delle rispettive varianze σ2

i) si può scrivere:

Y ∼ N (Aλ, AΣA0)

A partire da tale espressione si può calcolare la logverosimi-glianza di λ, ma non è possibile ricavare un’espressione analitica per trovare il massimo di tale funzione.

Gli autori propongono allora di cercare tale punto di mas-simo con metodi numerici, usando l’algoritmo Expectation Ma-ximization e considerando le misure end-to-end xi gli

unkno-wn data del problema. La funzione di verosimiglianza ottenuta sfruttando i complete data, ovvero p(X, Y |λ) , assume infatti una forma particolarmente semplice, a causa della dipendenza deterministica di Y da X. Si può esprimere infatti il logaritmo di tale funzione come

−log(|Σ|)/2 − 1/2 ∗ (X − λ)0∗ Σ−1∗ (X − λ)

L’espressione esplicita dell’E-step è più complessa e non ver-rà riportata, mentre l’M-step saver-rà compiuto in generale con metodi numerici.

Una volta stimato il valore di λ a partire da un insieme di T campioni indipendenti yi, è possibile usare tale conoscenza per

stimare i valori dei corrispondenti xi. Estendendo questo

ap-proccio si può immaginare di applicare l’algoritmo in situazioni reali, in cui il traffico è non stazionario. Si può infatti pensare che, all’interno di una finestra temporale di ampiezza fissata, i

(31)

flussi di traffico siano stazionari e dunque, prelevando una serie di campioni all’interno di tale finestra, si può applicare ad essi il procedimento appena descritto. Una moving window di osser-vazioni può quindi permettere di seguire le evoluzioni temporali della rete.

Gli stessi autori propongono altre soluzioni più elaborate per la stima delle matrici di traffico in condizioni non stazionarie, che sono illustrate in [3].

In figura 1.5 è mostrato un esempio dei risultati dell’applica-zione sperimentale dei metodi proposti alla rete rappresentata in figura 1.4 ; i grafici all’interno della matrice rappresentano l’andamento dei flussi di traffico end-to-end reali (in nero) e sti-mati (in viola), mentre i grafici ai lati rappresentano le misure ricavate a livello di link.

(32)

Figura 1.4: Scenario di applicazione delle tecniche di stima delle matrici di traffico

(33)

Figura 1.5: Esempio di risultati sperimentali ottenuti con gli algoritmi di stima delle matrici di traffico

(34)

Capitolo 2

Il problema della

topology discovery

2.1

Introduzione alla topology

discove-ry

La topology discovery è la rivelazione della struttura logica di una rete. Il legame tra la struttura logica che può essere rica-vata dalle diverse tecniche di topology discovery e la struttura fisica effettivamente sottostante dipende dal livello di astrazione a cui tali tecniche agiscono: le tecniche basate sulle risposte for-nite dai router ad alcuni pacchetti di tipo ICMP forniscono una visione della rete a livello di protocollo IP, mentre la topologia

(35)

logica fornita da molte tecniche tomografiche si basa sul concet-to di branching point e può rivelare apparati fisici che agiscono su layer diversi dello stack protocollare. Saranno illustrate in se-guito alcune tra le principali metodologie di topology discovery, che comprendono soluzioni estremamente diverse tra di loro. La scelta dell’una o dell’altra tecnica non può essere fatta a prio-ri, ma dipende strettamente dall’uso al quale sono destinate le informazioni topologiche da ricavare.

2.1.1

Metodi non tomografici di topology

di-scovery

I metodi non tomografici di topology discovery, al contrario di quelli fino ad ora descritti, necessitano di un certo grado di colla-borazione da parte dei nodi interni della rete; tale collacolla-borazione può essere di natura diversa a seconda della soluzione usata e del livello di privilegio del soggetto che esegue le operazioni di topology discovery.

In ogni caso, anche le soluzioni più semplici appartenenti a questa classe possono incontrare, al contrario di quelle tomogra-fiche, limitazioni nell’applicazione causate da particolari confi-gurazioni degli apparati di rete (presenza di ICMP rate limiters, firewall, router anonimi).

2.1.1.1 Traceroute

Traceroute è uno degli strumenti più diffusi di topology disco-very, tanto che lo si trova implementato nei più diffusi sistemi operativi. Il principio del traceroute è semplice: un nodo esegue

(36)

Figura 2.1: Informazione topologica ricavata dall’esecuzione del traceroute da una singola sorgente

l’active probing inviando ad un altro nodo destinatario pacchetti IP con valori del campo TTL che vengono incrementati in cor-rispondenza di ogni probe, fino a che tale campo non raggiunge un valore abbastanza elevato da permettere al datagramma di raggiungere la propria destinazione. In questo modo ognuno dei router situati sul path che connette i due nodi riceverà, ad un certo istante del processo di probing, un pacchetto con un valore del campo TTL pari a 1 e sarà costretto a scartarlo, inviando al nodo sorgente del pacchetto (quello che esegue l’active probing) un messaggio ICMP time exceeded; tale messaggio riporterà, ov-viamente, l’indirizzo di una delle interfacce del router. In questo modo il nodo che esegue l’active probing ricaverà una lista di indirizzi corrispondenti alle interfacce dei router presenti sul pa-th verso una determinata destinazione. La figura 2.1 mostra le informazioni topologiche ricavate dall’esecuzione di traceroute a partire dal sender verso il receiver . Una rappresentazione grafica di tale processo di probing può essere vista in figura 2.2. Eseguendo questo tipo di operazione con diverse destinazio-ni e mettendo in relazione tra loro i set di indirizzi ricavati in ciascuna osservazione è possibile ottenere una ricostruzione ad albero della topologia di una rete, in cui la radice rappresenta

(37)

Figura 2.2: Rappresentazione grafica del processo di probing di Traceroute

il nodo che esegue l’active probing ed ogni nodo interno cor-risponde ad un particolare router. Con l’uso di informazioni topologiche ottenute facendo eseguire Traceroute a diversi no-di della rete (monitors) è possibile tuttavia avere una visione più completa della rete stessa. In tempi relativamente recen-ti, diversi progetti di ricerca hanno sfruttato questa possibilità per cercare di ricavare una “mappa” di Internet, sviluppando tool basati sulla procedura di probing appena descritta; ne è un esempio Mercator (descritto in[17]).

Il processo di topology discovery basato su Traceroute incon-tra però alcune consistenti difficoltà. Una delle maggiori è quella causata dalla presenza di anonymous nodes, ossia di router che non rispondono al pacchetto di probe con un messaggio di tipo TTL time exceeded, o che, pur rispondendo, non inseriscono nel pacchetto di reply un’informazione che permetta di identificarli. Queste difficoltà è causata da diversi fattori, alcuni dei quali sono illustrati in [33]: alcuni router hanno ICMP disabilitato, oppure limitato da un ICMP rate limiter, alcuni firewall scar-tano il tipo di pacchetti usati da traceroute (tanto che è stato proposto di “mascherare” la procedura di probing inserendo nei pacchetti di probe segmenti di tipo TCP syn). Queste misure

(38)

sono in genere adottate dagli amministratori di rete sia con lo scopo esplicito di mantenere segrete le informazioni topologiche relative al loro dominio amministrativo, sia per il fatto che pos-sono essere dei malicious user a cercare di sollecitare un router a produrre una grande quantità di ICMP reply in modo da pre-giudicarne il normale funzionamento. Possono risultare anonimi a Traceroute, inoltre, anche i router alle cui interfacce siano as-segnati indirizzi privati di tipo IPv6. Si noti, d’altra parte, che Traceroute riesce a rivelare comunque la presenza dei router anonimi, pur non riuscendo ad associare loro un identificativo.

Anche in assenza di anonymous routers, si possono comun-que incontrare problemi nella ricostruzione della topologia della rete nel caso in cui si voglia fare un merging delle topologie vi-ste da più nodi. In fase di merging, infatti, è necessario trovare una corrispondenza tra i nodi presenti nelle diverse topologie: è necessario, in pratica, riuscire a capire se due nodi interni appar-tenenti ad alberi con radici diverse corrispondano, nella realtà, allo stesso router. I nodi interni, come si vede in figura 2.1, sono identificati dall’indirizzo sorgente inserito dal router nel pacchetto ICMP reply: due pacchetti di probe che raggiungono lo stesso router su interfacce diverse possono generare, dunque, ICMP reply con indirizzi sorgente diversi. Durante il processo di merging si corre dunque il rischio di considerare come distinti nodi interni che rappresentano in realtà lo stesso router: si pone il problema, dunque, di capire se due nodi, appartenenti a topo-logie diverse e identificati da indirizzi differenti corrispondano in realtà allo stesso apparato fisico, come illustrato in figura 2.3; tale problema viene indicato con il nome di alias resolution.

(39)
(40)

soluzione di tale problema, alcune delle quali sono indicate in [29, 33].

Un metodo intuitivo si basa sul fatto che, nella maggioranza dei casi, il campo seqnum dei messaggi di ICMP reply gene-rati da un router è ricavato da un contatore che è lo stesso per tutte le interfacce della macchina: se due interfacce ap-partengono allo stesso router, dunque, inviando due pacchetti back-to-back ai rispettivi indirizzi, si otterranno in risposta due pacchetti ICMP con numeri di sequenza consecutivi (o almeno “abbastanza vicini”).

Un’altra soluzione sfrutta il fatto che spesso i router rispon-dono ai messaggi indirizzati direttamente a loro con pacchetti che riportano un source adress unico, indipendente dall’interfac-cia su cui il messaggio originale è stato ricevuto. Inviando a due indirizzi alias un messaggio (ad esempio un segmento UDP indi-rizzato ad una porta inesistente) si dovrebbere quindi ottenere due pacchetti di risposta con lo stesso valore del campo source address.

Altre euristiche proposte sfruttano la struttura degli indirizzi letterali associati da un server DNS agli indirizzi IP in esame, o particolari pattern che, riscontrati nei grafi ottenuti dal merging di diverse topologie, rivelano la presenza di alias. Questo ultimo approccio è sfruttato anche in [33] per mettere in corrspondenza con uno stesso nodo fisico nodi anonimi presenti su topologie diverse.

(41)

2.1.1.2 Doubletree

Questo tipo di soluzione, illustrata in [12], si presenta come una versione migliorata di Traceroute, di cui condivide il principio (il processo di probing eseguito con pacchetti con valori crescenti del campo TTL). In particolare essa si propone di ridurre il numero di probe necessarie per la ricostruzione della topologia di una rete con Traceroute: questa ultima soluzione, infatti, prevede che ogni monitor invii una probe ad ogni router del path diretto verso ogni possibile destinazione, generando, nel caso di topologie con molti nodi, una mole considerevole di traffico di probing.

Doubletree cerca di ridurre il numero delle probe evitando di esplorare nuovamente subpath che sono già stati esaminati da altri monitor o che sono già stati analizzati dallo stesso mo-nitor nel processo di probing verso un’altra destinazione. A tale scopo si assume che, se ad un nodo che esegue il probing arri-va una ICMP reply con l’indirizzo di un router già individuato da un altro monitor, la topologia del subpath che conduce da tale router alla destinazione sia già nota e dunque non sia ne-cessario proseguire il probing. Se, invece, si rivela un router il cui indirizzo era già stato individuato dallo stesso monitor che sta eseguendo il probing si assume che sia noto il subpath dalla sorgente delle probe a tale router.

In pratica Doubletree prevede il mantenimento di due liste di indirizzi rivelati: il global stop set e il local stop set. La prima è condivisa da tutti i monitor e include l’insieme degli indirizzi riscontrati da tutti i monitor sul percorso verso una stessa destinazione, la seconda è invece caratteristica di ogni

(42)

singolo monitor e comprende tutti gli indirizzi da esso incontrati nel processo di probing.

Ogni singolo monitor, scelta una destinazione per il probing, comincia ad inviare pacchetti con il valore del TTL che parte da una soglia intermedia h e viene incrementato ad ogni probe; non appena riceve una reply da un indirizzo incluso nel global stop set, il monitor riporta il valore del TTL ad h-1 e, successi-vamente, lo decrementa ad ogni probe. Se il nodo che esegue il probing riceve una risposta da un indirizzo appartenente al local stop set, assume che la topologia del path verso la destinazione in esame sia ormai completamente nota e ricomincia il probing verso un’altra destinazione.

L’algoritmo è illustrato in maniera più formale in 3. L’implementazione effettiva di tale soluzione incontra alcune difficoltà relativamente alla scelta del parametro h (valori trop-po piccoli o troptrop-po grandi rischiano di rendere trascurabile la riduzione di complessità raggiungibile) e alla necessità di tenere aggiornata in modo coerente una struttura dati condivisa tra più nodi della rete come il global stop set.

Doubletree è stato comunque effettivamente implementato in programma funzionante denominato traceroute@home.

2.1.1.3 Listening OSPF

Un’altra possibile soluzione nel campo della topology discove-ry, che permette di ricavare la topologia della rete e di rilevare velocemente le sue variazioni è quella che sfrutta le informazio-ni topologiche diffuse ai vari router per mezzo del protocollo OSPF.

(43)

Algoritmo 3Procedura di probing di Doubletree

• Si sceglie una destinazione D verso la quale si vuole esplorare il path

• Si sceglie un numero di hop intermedio h e si imposta a tale valore il TTL della prima probe

• Si inviano pacchetti verso D con valore di TTL che viene incrementato per ogni probe fino a che:

– Non si riceve una risposta da un indirizzo incluso nel global stop set ed associato alla destinazione D – Non si raggiunge D

• Si imposta il valore del TTL ad h-1

• Si inviano pacchetti verso D con valore di TTL che viene decrementato per ogni probe fino a che:

– Non si riceve una risposta da un indirizzo incluso nel local stop set

– Il valore del TTL non raggiunge lo 0

(44)

Tale protocollo prevede che, a determinate scadenze o in cor-rispondenza di mutamenti della struttura della rete, ogni router invii a tuttigli altri un messaggio di Link State Advertisement (LSA), con cui comunica la lista dei router adiacenti. Ogni rou-ter mantiene in un database tutte le informazioni acquisite dalla ricezione degli LSA, e le usa per ottenere una ricostruzione della topologia della rete che gli consenta di compiere le decisioni di forwarding. Accedendo a tali informazioni si può dunque avere una visione completa ed aggiornata della topologia di un domi-nio amministrativo. In [26] è proposta una soluzione implemen-tativa per accedere al database delle informazioni topologiche di un router OSPF: è necessario configurare un host della rete in modo che esso sia riconosciuto dai router adiacenti come un loro peer, a cui inoltrare tutti i messaggi LSA a disposizione, ma bisogna assicurarsi, al contempo, che esso non diventi mai parte attiva del processo di routing (essendo tale host soltanto una sonda, esso non deve ricevere pacchetti da inoltrare). Tale effetto può essere ottenuto sfruttando le funzioni del protocollo OSPF che servono a stabilire l’adiacenza bidirezionale tra due router: quando le due macchine si riconoscono a vicenda come adiacenti, infatti, prima di cominciare ad inoltrarsi i pacchet-ti da commutare, esse devono assicurarsi che i propri database topologci siano sincronizzati. A questo scopo essi si scambiano dei messaggi di Link State Update (LSU) fino a che le infor-mazioni in possesso dei due router non coincidono. Gli autori suggeriscono di configurare la sonda in modo da attivare la pro-cedura di stabilimento della adiacenza con un router OSPF, ma di non inoltrare mai un proprio LSU: in tal modo il router tie-ne costantemente aggiornato il database della sonda, ma non

(45)

gli inoltra mai pacchetti di dati da commutare nè ne notifica la presenza agli altri router della rete, perchè l’adiacenza tra le due macchine non viene mai stabilita completamente.

Per applicare questo tipo di soluzione è necessario però essere in possesso di privilegi amministrativi: per essere accettato come pari da un router l’host dovrà, verosimilmente, autenticarsi (il protocollo OSPF, al contrario del più semplice RIP, comprende anche funzioni di sicurezza).

Un altro limite di questa soluzione è legato al fatto che, in caso di domini molto estesi, un router non sempre ha una visione completa della rete: il protocollo supporta infatti la suddivisione di un dominio amministrativo in aree più piccole. Ogni router ha una visione completa della topologia all’interno di ognuna di queste aree, ma ha a disposizione, per quanto riguarda le altre aree, solo informazioni topologiche parziali.

Per far fronte a tale problema in [26] viene proposto di tenere attiva in ogni area una sonda denominata LSAR (LSA Reflector) che invii le informazioni ad un host unico a livello di dominio, detto LSAG (link state Aggregator), responsabile dell’estrazio-ne da esse di una visiodell’estrazio-ne topologica completa della rete. Tale soluzione è illustrata in figura

2.1.1.4 Soluzioni basate su SNMP

SNMP è un protocollo di gestione che consente ad un un’appli-cazione remota (il manager) di configurare e monitorare tutti gli apparati di rete in grado di implementare tale protocollo (è possibile anche usarlo per controllare apparati di livello 2). Su ogni apparato controllabile con SNMP sono presenti un agente

(46)

Figura 2.4: Sonde (LSAR) e host incaricato del processing (LSAG) in un dominio OSPF organizzato per aree

(47)

di gestione (master agent) che fornisce l’interfaccia fra il ma-nager e i diversi sottosistemi di cui è composto l’apparato (ad esempio i processi relativi al routing, gli elementi di controllo dei link a layer 2), ad ognuno dei quali è associato uno speci-fico sub-agent. Ogni subagent dispone di un proprio database, denominato MIB (Management Information Base), in cui sono raccolte le informazioni di stato relative al sottosistema con-trollato. Il manager può configurare gli agent in modo che essi gli inviino dei messaggi di notifica (TRAP) ogni volta che essi riscontrano il verificarsi di un determinato evento.

In particolare il subagent che si occupa del routing OSPF mantiene all’interno del suo MIB alcune strutture dati che con-tengono le informazioni di interesse per la topology discovery ([26]):

• ospf_IfTable che contiene le informazioni di stato relative allo stato delle interfacce del router

• ospf_NbrTable che contiene l’elenco dei router che hanno una relazione di adiacenza bidirezionale con quello con-trollato

• ospf_AreaTable che contiene le informazioni topologiche relative all’area di appartenenza del router

Uno dei vantaggi di questo approccio è la sua semplicità: un solo server SNMP può monitorare la topologia di tutta la rete inter-rogando, tramite le apposite procedure definite dal protocollo SNMP, router appartenenti ad aree diverse, senza aver bisogno, come nel caso del listening OSPF, di mantenere sonde in tutte

(48)

le aree. Per questo motivo SNMP è alla base di molti software commerciali di topology discovery ([1]): ad esempio Openview della HP o Tivoli della IBM.

La possibilità di accesso alle informazioni topologiche con-tenute nei MIB è determinata dall’appartenenza o meno ad un determinato gruppo di host denominato comunità: solo un ma-nager che fa parte della stessa comunità dell’apparato e che è in possesso delle necessarie autorizzazioni può essere autorizzato ad accedere alle strutture dati degli agent.

Per utilizzare SNMP come strumento di topology discovery è dunque necessario usare un host che sia registrato come ap-partenente alle comunità di tutti i router di interesse e che abbia in ognuna di esse l’autorizzazione ad accedere ai dati.

Tale necessità, oltre al fatto che non tutte le reti adottano questo protocollo di gestione, rendono il campo d’applicazione delle soluzioni basate su SNMP più ristretto rispetto a quello delle altre soluzioni finora presentate.

2.1.2

Introduzione ai metodi tomografici di

to-pology discovery

La ricostruzione della topologia interna di una rete a partire dalle misure effettuate fra i nodi appartenenti ad un certo set e senza collaborazione alcuna da parte degli altri nodi della rete è una delle applicazioni tipiche della network tomography.

Le soluzioni proposte in letteratura per questo problema pre-vedono in generale l’individuazione di un certo set di nodi della rete definiti end-nodes, che partecipano in varie forme al pro-cesso di misura (alcune soluzioni prevedono soltanto che essi si

(49)

limitino a rispondere ad un ping, altre necessitano di forme di collaborazione più complesse); tipicamente un end-node viene selezionato per inviare agli altri una serie di pacchetti di probe. Tramite l’elaborazione delle misure ottenute si cerca di compie-re un’infecompie-renza della struttura logica della compie-rete che connette i diversi end-nodes; gli algoritmi proposti in letteratura permet-tono, nella maggior parte dei casi, di ottenere una ricostruzione della topologia della rete ad albero binario. Applicando succes-sivamente altri algoritmi, che possono comportare anche l’invio di ulteriori pacchetti di probing in rete, si può però giungere ad una ricostruzione che, a meno di alcuni limiti che verranno mes-si in evidenza caso per caso, rispecchi l’esatta topologia logica della rete.

I nodi interni di tale albero corrispondono ai punti della rete in cui il percorso tra la radice dell’albero e due foglie (o due set di foglie) incontra una biforcazione: per tale motivo essi sono chiamati branching point. Tali nodi possono rivelare la presenza di un router, ma, talvolta, anche di un apparato store-and-forward di livello 2; se l’algoritmo restituisce in uscita un albero binario tali nodi possono anche non corrispondere ad un determinato apparato fisico presente sulla rete. Si può notare che con gli algoritmi tomografici non è possibile rivelare nodi in-terni della rete che non costituiscono branching point: pertanto gli archi che connettono due nodi dell’albero non corrispondono ad un singolo hop a livello 3, ma all’intera sequenza degli hop che costituiscono il percorso fra i due nodi.

La figura 2.5 mostra i risultati dell’applicazione di un algo-ritmo di topology discovery in cui è il nodo PE1 ad eseguire l’active probing; si può notare come la topologia ricostruita non

(50)

Figura 2.5: Ricostruzione della topologia interna di una rete da misure effettutate su un certo set di end-nodes

sia ad albero binario, segno che le misure ottenute dalle probe inviate in rete sono state sottoposte a diverse fasi di processing.

2.2

L’uso delle metriche per la

ricostru-zione della topologia

Ricostruire una topologia ad albero equivale a raggruppare in cluster gerarchici gli end-nodes: i nodi che appartengono ad un determinato cluster sono quelli che hanno lo stesso progenitore nell’albero e a loro volta i cluster così individuati possono venire aggregati in cluster più ampi che corrispondono ai progenitori posti ad un livello gerarchico superiore nell’albero.

Per ricostruire l’albero gli algoritmi tomografici si basano su una metrica γ che può essere associata ad una coppia (i,j) di end-nodes o ad un nodo interno dell’albero ed in base alla quale

(51)

si esegue la procedura di clustering degli end-nodes che porta a ricostruire la topologia ad albero. In particolare tale metrica fornisce un’indicazione dell’estensione del path condiviso fra la radice dell’albero ed una coppia di end nodes e può quindi essere associata sia alla coppia (i,j) che al nodo interno k che costituisce il più vicino progenitore comune di i e j.

Più formalmente, si può imporre che,per poter permettere di eseguire correttamente il clustering la metrica scelta deve soddisfare determinate proprietà:

1. γi> γj se j è progenitore di i nell’albero

2. γ(i,j) = γkdove il nodo interno k è il più vicino progenitore

comune degli end-nodes i e j

3. γ(i,j) = γ(m,n)se per le coppie di end-nodes (i,j) e (m,n) il

più vicino progenitore comune è lo stesso

In pratica si può notare come la metrica così definita sia un indice di quanto due end-nodes si trovino vicini nella topologia ad albero: quanto più i due end-nodes saranno vicini, tanto più il loro più vicino progenitore comune si troverà nella parte periferica dell’albero e la metrica ad esso associata sarà alta.

Essendo le quantità γ(i,j) ottenute da misure rumorose le

relazioni di uguaglianza precedentemente enunciate vanno intese in senso lato: per due coppie di nodi con lo stesso progenitore le metriche misurate non saranno mai esattamente uguali, ma, se le misure sono effettuate correttamente, saranno più “vicine” delle metriche associate a coppie di nodi con progenitore diverso.

(52)

Ci sono varie metriche proposte in letteratura tali da soddi-sfare i requisiti esposti precedentemente: la covarianza del ritar-do, la distanza temporale di due pacchetti in un packet sandwich e la differenza del ritardo misurato da due end-nodes.

Le prime due saranno descritte in modo più approfondito in quanto saranno il punto di partenza della trattazione successiva; la tecnica basata sulla differenza del ritardo, illustrata ad esem-pio in [4], è invece stata ritenuta meno interessante in quanto presuppone una sincronizzazione molto precisa di sender e re-ceiver, complessa da ottenere per un numero alto di sonde. Un offset anche costante fra i clock di due sonde, infatti, si tradu-ce in un equivalente errore nella misura della metrica, capatradu-ce di alterare in modo consistente il processo di ricostruzione della to-pologia. Gli algoritmi proposti si basano inoltre sull’assunzione che la differenza dei ritardi sia una variabile aleatoria gaussiana; tale ipotesi è, come verrà motivato più in seguito, difficilmen-te verificata, soprattutto nei casi in cui vi sia un consisdifficilmen-tendifficilmen-te cross-traffic ad interferire con i pacchetti di probing.

Altre tecniche descritte in letteratura, ad esempio in [13], sfruttano come indicatore della vicinanza di due end-nodes la correlazione fra le perdite di pacchetti sperimentate dai due ri-cevitori; con questa tecnica è necessario inviare in rete numero di probe tale da registrare una serie cospicua di perdite per ave-re dei dati affidabili da elaboraave-re. Con probabilità di perdita contenute questa tecnica appare a nostro avviso troppo invasiva per la rete e quindi meno promettente delle altre.

(53)

2.2.1

La covarianza dei ritardi

Con questa tecnica ci sono due modi di svolgere le operazioni di probing: se la rete sotto osservazione supporta il multicast ogni probe è costituita da un pacchetto inviato multicast dalla radice dell’albero a tutti gli end-nodes, che registrano il relativo ritardo; alternativamente (nel caso in cui il multicast non sia supportato) è possibile inviare una coppia di pacchetti back-to-back ad ogni possibile coppia di end-nodes.

Lo scopo di questa modalità di misura è quello di ottenere, per ogni coppia di nodi (A, B), due misure di ritardo composte da una componente comune, che non varia per le due probe (il ritardo sperimentato sul path comune dalla radice dell’albero ai due ricevitori) e da una componente legata al path dal bran-ching point ad ogni ricevitore; le due componenti caratteristiche dei singoli end-nodes sono supposte statisticamente indipenden-ti. Per questo si usano probe multicast (che viaggiano come un solo pacchetto sul path comune e vengono duplicate in corri-spondenza dei branching point) o back-to-back (che, viaggiando con un breve scarto temporale l’uno dall’altro, incontreranno un ritardo pressappoco uguale sui link comuni).

L’uso della covarianza dei ritardi end to end registrati da due end-nodes come metrica per la ricostruzione della topolo-gia è possibile grazie alla relazione che lega, nelle condizioni di misura sopra descritte, tale quantità alla varianza del ritardo sperimentato dai pacchetti sul path condiviso verso i due ri-cevitori; definiti yr1e yr2 i ritardi end-to-end misurati dai due

ricevitori, si ha che σ2

rshared = cov(yr1, yr2). La metrica

(54)

raggiunge k dalla radice dell’albero.

Se si considerano indipendenti i ritardi sui diversi link si può notare come tale varianza sia la somma delle varianze di tutti i link che costituiscono lo shared path; sotto questa ipotesi è facile dimostrare che la covarianza è una metrica che soddisfa tutte le proprietà precedentemente richieste. Si prenda ad esempio in considerazione la prima proprietà: se j è progenitore di i allora σ2

0→i= σ20→j+ σ2j→i> σ20→j e dunque è vero che γi> γj.

Una volta nota la topologia, è inoltre possibile calcolare la varianza del ritardo per ogni segmento dell’albero. Si pren-da ad esempio in considerazione la topologia in figura 4: no-ti cov(yA, yB),cov(yA, yC), cov(yC, yB), le varianze del ritardo

end-to-end σ2

A, σB2e σ2C (ricavabili direttamente dai dati) e

pre-so come riferimento il nodo interno N1si può notare ad esempio

che σ2

N1→A= σ 2

A− cov(yA, yB) .

Un aspetto molto positivo di questa metrica è il fatto che essa non necessita di una sincronizzazione estremamente precisa tra sender e receiver: infatti è immediato dimostrare che, se la mancata sincronizzazione comporta solo un offset tra gli orologi delle due sonde che rimane costante durante tutto l’arco della misura, la stima della covarianza non ne è disturbata.

Da questo punto di vista è interessante anche una variante di questa tecnica proposta in [32]e denominata network radar: essa consiste nel misurare la covarianza non a partire dai ritardi end-to-end ma dal round trip time. Nell’ipotesi che anche i ri-tardi dovuti al percorso sul reverse path dai ricevitori alla radice dell’albero siano indipendenti, le forme e le proprietà della me-trica sono analoghe a quelle enunciate. Questa tecnica permette di usare come end-nodes nel procedimento di misura apparati di

(55)

Figura 2.6: Topologia esemplificativa per l’inferenza della va-rianza del ritardo sui diversi link a partire dalle misure end-to-end. Le due frecce rappresentano i path a cui vengono associate le metriche indicate sulle label

(56)

rete che non sono stati in alcun modo configurati appositamente per collaborare al probing.

Per stimare la covarianza di due ritardi end-to-end a partire da una collezione di N campioni indipendenti yiè possibile usare

uno stimatore non polarizzato: cov(x, y) =PN

i=0(yi−y)(xi−x)/N ∗

(N − 1). Per un numero alto di misure è possibile, utilizzando il teorema limite centrale, dimostrare che tale stima tende ad una variabile aleatoria gaussiana che ha media pari alla covarian-za reale dei ritardi e variancovarian-za calcolabile tramite un ulteriore stimatore, riportato in [32]. Una volta calcolate queste due sta-tistiche, si può ricavare l’intervallo di confidenza dello stimatore della covarianza e avere un’idea della precisione della misura.

Si noti che con le tecniche basate sulla covarianza la presenza di un livello di cross traffic tale da far variare il ritardo end-to-end tra una probe e l’altra è essenziale per ottenere una metrica precisa; si prenda in considerazione lo stimatore: se i campioni di ritardo non variano in modo apprezzabile rispetto al loro valor medio, la covarianza misurata avrà un valore molto basso e l’informazione in essa contenuta sarà sommersa dal rumore.

2.2.2

Metriche ottenute con la tecnica packet

sandwich

L’uso di questa metrica è stato proposto in [8] e il suo funziona-mento è illustrato in figura 2.7; nello specifico tale illustrazione mostra il processo di probing per la misura della metrica γ(2,3).

Il nodo che esegue l’active probing invia un treno di pacchetti back-to-back composto da un primo pacchetto piccolo destinato all’end-node 3, un pacchetto più grande (di solito si sceglie la

(57)
(58)

massima lunghezza non sottoposta a frammentazione) destinato al nodo 2 e un ultimo pacchetto piccolo nuovamente destinato al nodo 3; la misura di interesse è la distanza temporale d fra il primo bit del primo pacchetto e il primo bit del terzo pacchetto. Se, per ogni coppia (i,i+1) di link di livello 2 consecutivi del-la rete, è verificata del-la redel-lazione l2

l1 >

bi+1

bi (b è la banda del link,

l1 e l2sono rispettivamente la lunghezza del pacchetto piccolo e

di quello grande del packet sandwich) ad ogni link attraversato da tutti e tre i pacchetti (e dunque condiviso dai path verso i nodi 2 e 3) la distanza d viene incrementata di un valore ∆d inversamente proporzionale alla capacità del link, a causa del-la presenza del pacchetto grande che ritarda del-la trasmissione del terzo pacchetto del sandwich; l’ipotesi sulla capacità di link con-secutivi è generalmente verificata, dato che, scegliendo opportu-namente le lunghezze dei due pacchetti, il vincolo da rispettare diventa bi+1

bi < 25. Una volta raggiunto il branching point dei

due path, il secondo pacchetto del sandwich viene inoltrato su di un link diverso rispetto al primo e al terzo e la distanza tem-porale d non incrementa più, a condizione che sul percorso dal branching point la capacità di ogni link sia maggiore del rap-porto l1

d; se tale condizione non è rispettata, infatti, è possibile

che il terzo pacchetto, giungendo ad un determinato nodo, trovi il primo sempre in fase di trasmissione e subisca quindi un ritar-do di accodamento che altera la distanza temporale d tra i due pacchetti. La quantità d aumenta dunque con il numero di link condivisi tra i path verso i due end-nodes ed è facile rendersi conto che essa soddisfa le proprietà richieste ad una metrica per la ricostruzione della topologia.

(59)

Questo tipo di metrica presenta alcune interessanti proprietà che la rendono attrattiva per l’utilizzo in molti scenari.

In primo luogo, mentre nel caso della covarianza il cross traf-fic è un elemento essenziale nella misura, in questo caso invece esso ha solo un ruolo di disturbo e il suo effetto appare co-me un processo di rumore sovrapposto alla misura utile; questa tecnica è dunque utilizzabile anche nel caso in cui la rete sia scarsamente carica. Il rumore è inoltre considerabile a media nulla, perchè l’effetto del cross traffic può essere sia quello di incrementare d, nel caso in cui un pacchetto estraneo si intro-metta fra due pacchetti del sandwich, sia quello di ridurlo: se il primo pacchetto viene accodato e deve apettare la trasmis-sione di pacchetti appartenenti ad altri flussi, esso perde parte del vantaggio acquisito sugli altri componenti del sandwich che “recuperano” una frazione del ritardo d. Applicando il teore-ma limite centrale, si può modellare una misura rumorosa della metrica come x(i,j) ∼ N (γ(i,j), σ2(i,j)); d è infatti determinata

dalla somma dei ∆d associati ad ogni link, che possono esse-re considerati variabili aleatorie indipendenti ed identicamente distribuite, come affermato in [9].

Per calcolare analiticamente l’incremento ∆d in corrispon-denza di due link consecutivi di capacità Ci e Ci+1si faccia

rife-rimento alla figura 2.8a): non appena il secondo pacchetto del sandwich è stato trasmesso sul link a capacità Ci, esso comincia

ad essere serializzato sul link successivo (non si considerano i ri-tardi di propagazione, che, essendo costanti per i due pacchetti, risultano ininfluenti) con rate Ci+1; contemporaneamente inizia

la trasmissione del terzo pacchetto del sandwich, che era acco-dato back-to-back al secondo, sul link con capacità Ci. Dopo un

(60)

Figura 2.8: Situazione del secondo e terzo pacchetto di un packet sandwich nel momento in cui il pacchetto più lungo comincia ad essere trasmesso sul link di capacità Ci+1 (a) e nel momento in

cui l’ultimo bit del pacchetto più corto è stato trasmesso sul link di capacità Ci

Figura

Figura 1.5: Esempio di risultati sperimentali ottenuti con gli algoritmi di stima delle matrici di traffico
Figura 2.7: Funzionamento della tecnica packet sandwich
Figura 2.8: Situazione del secondo e terzo pacchetto di un packet sandwich nel momento in cui il pacchetto più lungo comincia ad essere trasmesso sul link di capacità C i+1 (a) e nel momento in
Figura 2.11: Possibili transizioni fra due stati della catena di Markov
+7

Riferimenti

Documenti correlati

Com- portamento della propriet` a di locale connessione rispetto al passaggio al prodotto, al quoziente, ai sottospazi.. Locale connessione per cammini Equivalenza tra connessione

La sfera ` e il quoziente che si ottiene dal disco chiuso mediante la riduzione ad un punto della circonferenza di bordo.. Altri modelli topologici del piano proiettivo reale:

Classificazione delle superfici in topologia algebrica: Teoremi di classificazione delle superfici connesse compatte mediante il gruppo fondamentale (per le superfici (I) e per

Le famiglie, anche quelle più problematiche, comprendono subito questo sforzo, perché la presenza è l’unica vera azione che permette di far percepire che qualcuno si sta prendendo

La formazione linguistica è certificata dalle Università per stranieri di Siena e Perugia a seguito di esame. Ogni utente sottoscrive un contratto formativo assumendosi l’impegno

Per formarsi un’idea più precisa della struttura degli aperti di R e per comprendere meglio la relazione che intercorre tra intervalli aperti e insiemi aperti è molto utile

Se il raggio è grande, c’è un valore critico della velocità, al di sopra del quale il moto cessa di essere laminare. Grandi variazioni di velocità ortogonalmente alla direzione

Per trasferire un file usando il protocollo ftp occorre avere a disposizione un'applicazione ftp chiamata client ftp (ce ne sono diverse anche di tipo freeware) che viene