Altre possibili soluzioni per la tomografia

Una delle limitazioni della soluzione esposta nel paragrafo pre- cedente è il fatto che essa mantiene un certo grado di ambigui- tà per quanto riguarda i punti di innesto di due alberi e che essa può rivelare dei nodi che non sono effettivamente presen- ti. Tale soluzione si presenta inoltre adatta a contesti in cui le sonde che eseguono l’active probing sono poche in relazione agli end-nodes: infatti, come riportato in [24], il numero delle probe necessarie aumenta in modo quadratico con il numero dei sender e linearmente con quello dei receiver;a queste probe, inol- tre, vanno sommate quelle necessarie per ricavare la topologia dell’albero visto da ogni singolo sender.

Qui si propone un approccio alternativo, da applicare in uno scenario diverso e sotto opportune ipotesi, e che potrebbe risol- vere sia il problema delle ambiguità legate ai punti di innesto che quello dell’oneroso processo di probing supplementare. Perchè questa soluzione possa funzionare, è necessario che:

• il routing nella rete in esame sia simmetrico, ovvero che il path dal nodo A verso il nodo B attraversi esattamente gli

stessi link del path dal nodo B verso il nodo A, per ogni coppia di nodi A e B coinvolti nel processo di probing • ogni nodo coinvolto nel processo di probing partecipi sia

come sender che come receiver, costituendo la radice di una delle topologie ad albero della rete e risultando come foglia in tutte le altre

• sia possibile misurare una metrica che, per un dato path, sia inavariante al verso di percorrenza (è stato evidenziato come le metriche ottenute con i packet sandwich soddisfino questo requisito)

L’idea alla base di questa soluzione è che il punto di innesto dei percorsi fra due sorgenti ed uno stesso destinatario, in caso di routing simmetrico, corrisponde con il branching point del percorso fra tale destinatario e le due sorgenti. Nel caso in cui la metrica sia indipendente dal verso di percorrenza, questa os- servazione consente di identificare in modo univoco la metrica del percorso fra il punto di innesto dei path da due sorgenti diverse a uno stesso destinatario e il destinatario stesso; in tal modo, avendo a disposizione delle misure arbitrariamente preci- se, è possibile individuare in modo esatto la locazione del punto di innesto e capire se tale punto coincide con uno dei branching point già presenti negli alberi di cui si sta facendo il merging.

Si prenda in considerazione, a titolo esemplificativo, la topo- logia di figura 2.16a, che rappresenta due alberi visti dai sender S1 e S2. Si supponga di voler individuare il punto di innesto dei due alberi verso il ricevitore A: osservando l’albero con sor- gente A (in figura 2.16b) si noterà che la metrica del path da

A al branching point fra verso S1 e S2 sarà uguale a quella del percorso da n1 ad A misurata sui due alberi con radici S1 e S2. Si potrà così dedurre non solo, come sarebbe stato possibile con le tecniche descritte prededentemente, che il punto di innesto si trova a monte di n1, ma che esso coincide proprio con n1. Al contrario, volendo trovare il punto di innesto dei due alberi ver- so il nodo C, si vedrà che la metrica associata al percorso da C al branching point verso S1 e S2, misurata sull’albero con radi- ce C (mostrato in figura 2.16c), sarà minore di quella, misurata sugli alberi di radici S1 e S2, che caratterizza il percorso tra C e il primo nodo interno a monte; se ne dedurrà che il punto di innesto dei due alberi verso il ricevitore C si trova, in questo caso, a valle di qualunque nodo interno.

Naturalmente rimane da investigare il modo in cui tale me- todo potrà gestire i dati rumorosi provenienti dalle misure. Una situazione problematica può essere, ad esempio, quella in cui il punto di innesto coincida con uno dei nodi della topologia, come nel caso del nodo n1 in figura 2.16; in questo caso un errore nel calcolo delle metriche può indurre l’algoritmo di ricostruzione, per esempio, a localizzare il punto di innesto a valle di n1. Nel caso teorico, inoltre, si è considerato che le metriche associate al percorso da n1 ad A fossero esattamente uguali su tutti gli alberi: questo sarebbe difficilmente riscontrabile nella realtà, in quanto su ogni albero la metrica associata a quel dato path sa- rebbe dedotta a partire da un set di dati diverso (ogni sender manda le sue probe per stimare la topologia e le metriche). Di conseguenza è necessario stabilire un criterio in base al quale decidere se una serie di punti della topologia che le metriche localizzano come “vicini” tra loro corrispondano o no allo stesso

Figura 2.16: a) alberi visti dalle sorgenti S1 e S2 b)albero visto dal ricevitore A c)albero visto dal ricevitore C

nodo interno. Un criterio potrebbe essere quello di considerare come corrispondenti allo stesso nodo punti la cui distanza sia minore della minima metrica associabile ad un link; nel caso di misure effettuate con i packet sandwich tale metrica di soglia corrisponde a l2/Cmin.

Questo tipo di approccio presenta dunque anche esso alcuni inconvenienti nell’applicazione ad alberi ottenuti con i criteri di clustering fino ad ora descritti; esso sarà tuttavia alla base del metodo di tree merging che verrà illustrato nel prossimo paragrafo, e che opererà su alberi in cui saranno rivelati tutti i nodi interni e non solo i branching point.

Capitolo 3

Topology discovery con

la conoscenza delle

possibili capacità dei

link

3.1

Ricostruzione dell’albero relativo ad

una sorgente di probe

3.1.1

Introduzione

rete sulla quale vengono effettuate le misure; ciò permette a tali soluzioni di poter inferire anche la topologia di una rete appar- tenente ad un dominio di cui non si è amministratori e riguardo la quale non si ha alcuna informazione. Tuttavia, nel caso in cui si vogliano applicare le tecniche tomografiche di topology discovery ad una rete appartenente al proprio dominio ammini- strativo, ad esempio a scopo diagnostico, si hanno generalmente a disposizione alcune conoscenze a priori sulla rete che possono essere sfruttate per migliorare la ricostruzione della topologia.

Sarà possibile, in particolare, sapere quali siano le capacità dei link presenti sulla rete; esse formeranno un insieme finito che sarà indicato come C. Nella soluzione che verrà adesso illustra- ta questa informazione a priori sarà sfruttata per ottenere una visione più precisa della topologia .

Come illustrato in 2.2.2 la metrica d misurata con la tecni- ca del packet sandwich è direttamente proporzionale (a meno di due termini additivi relativi al primo e all’ultimo link del path condiviso) alla somma degli inversi delle capacità dei link condivisi. Tali capacità, come osservato, non sono grandezze continue, ma appartengono ad un insieme discreto e finito i cui elementi sono supposti noti: in una buona percentuale di casi sarà quindi possibile ricavare dalla metrica dijcalcolata a par-

tire da misure end-to-end quali siano le capacità dei link che costituiscono il path condiviso da un certo sender ai receiver i e j. Ci si può rendere conto della concretezza di tale possibilità prendendo in considerazione il seguente esempio: si ipotizzi che una rete sia costituita da link a 1, 10 e 100 Mbps, che il suo diametro sia pari a 9 link e che la sommatoria degli inversi delle capacità su un certo percorso sia pari a 1,34 µs: si può dedur-

re in modo univoco che il path in esame è costituito da 1 link a 1 Mbps, 3 link a 10 Mbps e 4 link a 100Mbps. Sfruttando questo principio si può pensare di capire, tramite le probe di tipo packet sandwich, le capacità dei link che costituiscono il path condiviso; in questo modo è possibile avere una visione più completa della rete e rivelare anche nodi interni che non siano branching point dell’albero . Si può inoltre pensare ad altri e più efficaci metodi di merging degli alberi con diverse radici che tengano conto delle ulteriori informazioni a disposizione.

Si può facilmente notare, d’altra parte, che un’inferenza di questo tipo è soggetta ad un certo grado di ambiguità: dato un valore della somma dei termini 1/Ciricavato dai dati misurati, è

infatti possibile, in certi casi, trovare diverse sequenze di Ciche

generino quello stesso risultato. La probabilità di tali ambiguità dipende dal valore e dal numero degli elementi dell’insieme C, ma anche dal diametro della rete; è possibile comunque creare off-line una tabella che associa a tutte le possibili sequenze di link la relativa metrica e rendersi conto di quali siano i casi in cui c’è ambiguità. Proponiamo di seguito due tabelle di questo genere, calcolate per alcune combinazioni delle capacità stan- dard della gerarchia OC ed Ethernet; il calcolo è effettuato per diametri di 6 link in tabella 3.1 e di 4 link in tabella 3.2. Inoltre sono riportate in tali tabelle anche le differenze medie tra le cop- pie di metriche più vicine associate a sequenze di link diverse; tale dato, come sarà chiarito in seguito, assume una rilevante importanza ai fini della determinazione della probabilità di er- rore in fase di decisione. Il primo caso è realistico nell’ipotesi di un dominio di qualche decina di nodi, mentre il secondo è utile per capire quanto sia possibile ridurre la probabilità di incon-

Possibili capacità % ambiguità ∆d media gerarchia OC (da OC-1 ad OC-765) 23% 1.6*10^-6 10Mb-100Mb-1Gb e OC (max OC-48) 4.5% 4.1*10^-6 Ethernet (10Mb-100Mb-1Gb-10Gb) 0% 44*10-6

Tabella 3.1: Percentuali di sequenze di link ambigue e distanza media tra metriche ∆d (espressa in secondi) su path di 6 link con diversi set di possibili capacità

Possibili capacità % ambiguità ∆d media gerarchia OC (da OC-1 ad OC-765) 5.4% 3.7*10^-6 10Mb-100Mb-1Gb e OC (max OC-48) 0.6% 11*10^-6 Ethernet (10Mb-100Mb-1Gb-10Gb) 0% 65*10^-6 Tabella 3.2: Percentuali di sequenze di link ambigue e distanza media ∆d tra metriche (espressa in secondi) su path di 4 link con diversi set di possibili capacità

trare ambiguità con le tecniche di segmentazione che saranno illustrate nei paragrafi successivi.

3.1.2

Strategie di decisione

Come già evidenziato in 2.2.2, le misure ricavate end-to-end tra- mite le probe di tipo packet sandwich sono modellabili come una variabile aleatoria gaussiana con media pari al valore reale della metrica di,j. La strategia di decisione più elementare consiste

sibile sequenza di link e di scegliere quella che genera la metrica più vicina al valore misurato.

Tale approccio è però molto vulnerabile agli errori di misura; sia N il diametro della rete e k il numero di elementi dell’insieme C: il numero di possibili sequenze di link (considerando che le sequenze che hanno nel complesso gli stessi valori delle capacità ma in un diverso ordine non sono distinguibili tramite misure end-to-end) crescerà come kN _{ed è dunque prevedibile che tali}

sequenze generino in molti casi metriche vicine tra loro, che possono portare ad una probabilità di errore considerevole.

All’aumentare del numero massimo di link della sequenza, d’altra parte, aumenta anche la probabilità di avere due se- quenze che generino la stessa metrica. In questi casi è possibile avvalersi di alcune euristiche per superare le ambiguità: si può pensare, ad esempio, di osservare le sequenze di link associati a path che hanno alcuni hop in comune con quello in esame e di accorgersi in questo modo di eventuali incoerenze di alcune delle soluzioni proposte. Nessuna di queste euristiche dà però la garanzia di riuscire a sciogliere tutte le ambiguità: è necessario dunque ideare una strategia alternativa.

L’idea alla base delle soluzioni che saranno illustrate in 3.1.2.1 e 3.1.2.2 è quella di suddividere lo shared path fra due nodi in sezioni più piccole e di compiere separatamente le decisioni sulle capacità dei link che le compongono; in questo modo si ottiene il duplice effetto di avere una probabilità di errore più bassa, in quanto il numero totale delle possibili metriche fra cui scegliere è minore e quindi tali valori saranno in generale più distanti l’u- no dall’altro, e di rendere più rare le ambiguità. Per un numero basso di link consecutivi non è però garantito che le misure spe-

rimentali della metrica di,j siano variabili aleatorie gaussiane:

tale proprietà è infatti caratteristica delle misure end-to-end a causa del fatto che esse sono costituite dalla somma di un nume- ro elevato di contributi indipendenti dovuti ai diversi link, ma non è estendibile alle metriche relative a sezioni del path, che sono la sommatoria di pochi termini (talvolta anche uno solo). Si può tuttavia immaginare che la media aritmetica di un nu- mero elevato di misure indipendenti relative alla stessa sezione del path abbia comunque una densità di probabilità gaussiana. Un’altra possibile strategia di decisione, che sarà illustrata in, cerca di sfruttare le relazioni fra le diverse sequenze di link che costituiscono un path end-to-end per ottenere delle sequenze di link che siano coerenti con la topologia da ricostruire.

3.1.2.1 Probe packet sandwich con incremento lineare del Time-To- Live

Una prima soluzione può essere quella di usare packet sandwich in cui al pacchetto centrale (quello di lunghezza maggiore, che determina l’incremento di d in corrispondenza di ogni link) ven- gano asegnati valori crescenti del campo time-to-live: indicato con m il valore del TTL, è possibile in questo modo ricavare la metrica relativa ai primi m hop a livello 3 del path condi- viso, poichè, arrivato all’m-esimo hop, il secondo pacchetto del sandwich sarà scartato e non determinerà più l’incremento del- la distanza temporale fra il primo e il terzo. La differenza fra le misure ottenute con due valori di TTL consecutivi è pari al contributo 4d dei link che collegano due nodi interni successivi a livello 3; nel caso in cui ad un hop di livello 3 corrispondesse

un solo link, varrebbe dunque la relazione di− di−1 = l2 Ci − l1 Ci−1

sarebbe quindi possibile ricavare in modo ricorsivo le capacità di tutti i link appartenenti allo shared path effettuando decisio- ni locali senza possibilità di ambiguità (lo spazio delle ipotesi coinciderebbe con l’insieme C). Il processo di probing si ar- resterebbe una volta raggiunto un numero di hop n tale che dn− dn−1 = 0; tale valore corrisponderebbe al numero di hop

del path condiviso.

Più formalmente, data una stima di di, ottenuta dalla media

aritmetica delle misure sperimentali e distribuita secondo una d.d.p gaussiana, e note le misure di tutte le capacità Cj con j

compreso tra 1 e i-1 si sceglierà il valore di Ci che massimizza

la funzione di logverosimiglianza espressa come

L(Ci) ∝ −( i−1

X

j=1

(l2− l1)/Cj+ l2/Ci− di)2

si può notare che il valore che massimizza tale funzione è quello che determina la metrica totale più vicina al valore misurato di di. Si noti che la varianza dell’osservato cresce linearmente

con i, dato che ad ogni nuovo hop si somma ad esso un nuovo termine rumoroso dovuto all’ultimo link: sarà dunque necessario far crescere linearmente anche il numero delle misure effettuate, in modo da mantenere costante la probabilità di errore su ogni decisione locale.

Purtroppo, però, è frequente che ad ogni hop a livello 3 cor- rispondano diversi link a livello 2: in questo caso è sempre pos- sibile utilizzare la tecnica appena illustrata, a patto di conoscere un bound superiore Nl sul numero di link a livello 2 che corri-

spondono ad un hop di livello 3. In tal caso ad ogni decisione locale sarà associato uno spazio delle ipotesi costituito da tutte le possibili sequenze di link di lunghezza massima Nle saranno

di nuovo possibili ambiguità fra due sequenze diverse; tuttavia si può immaginare che, per Nl non troppo elevato, tali ambiguità

siano piuttosto rare: in una rete composta da link di capacità 2.5 Gbps e 1 Gbps e con Nl= 4, ad esempio, non esistono due

sequenze di link che diano origine alla stessa metrica.

3.1.2.2 Decisioni separate per i path tra due branching point

Un altro possibile approccio al problema è quello di ricostruire una topologia ad albero sfruttando le tecniche illustrate nella sezione 2.3 e di inferire in seguito quali siano le capacità dei link che compongono i vari rami di tale albero. Si immagini di aver ricostruito la topologia di figura 3.1

Si avranno a disposizione le metriche d1,2 = l2/C1+Pn1−1_i=2 (l2− l1)/Ci+ l2/Cn1

d3,4 = l2/C1+Pn2−1i=2 (l2− l1)/Ci+ l2/Cn2

facendo la differenza di due termini si ottiene

d1,2− d3,4 = −l1/Cn2+P_i=n2+1n1−1 (l2− l1)/Ci+ l2/Cn1

A partire da tale differenza è possibile effettuare una decisio- ne locale sulle capacità dei link che compongono il path da n1 a n2. Anche in questo caso è necessario avere un bound Nbsul

Figura 3.1: Topologia ricostruita con le tecniche classiche

numero di link che compongono il path fra due branching point e le ambiguità saranno verosimilmente più probabili al crescere di tale bound. Si noti che, rispetto ai casi precedenti, l’osser- vato sarà probabilmente più rumoroso: esso infatti è dato dalla differenza di due misure end-to-end e avrà quindi una varianza pari alla somma delle loro varianze

3.1.2.3 Decisioni coerenti su di un path end-to-end Si consideri un path end-to-end della rete che connette il nodo che esegue il probing (corrispondente alla radice root della topo- logia ad albero) all’end-node i: i branching point bi,j, individuati

tramite le metriche misurate, saranno nodi interni attraversati da tale path egli insiemi di link Li,j, che costituiscono i path che

Figura 3.2: Relazioni tra le sequenze di link che connettono il nodo che esegue l’active probing (root) i diversi branching point attraversati dal path verso l’end-node k

connettono tali branching point alla radice dell’albero, saranno tutte sottoinsiemi dell’insieme di link Liche è associato al path

end-to-end. Fra tali insiemi Li,jvi saranno quindi delle relazioni

che possono essere sfruttate per compiere delle decisioni migliori a partire dalle misure a disposizione.

Per avere un’idea intuitiva delle relazioni che intercorrono tra le diverse sequenze di link si faccia ad esempio riferimen- to al path descritto in figura 3.2, che connette la radice root dell’albero al nodo k. Il branching point b3,k si trova a monte

del branching point b4,k e, pertanto, il path dalla radice b4,k

includerà anche il path tra la radice e b3,k: si avrà quindi che

L3,k⊂ L4,k

Volendo generalizzare tale concetto si può scrivere che, fis- sato un end node k, per ogni coppia di end-node i e j :

• Li,k⊂ Lj,k se bi,k è a monte di bj,knel path verso k

Si ponga dunque di conoscere in modo attendibile la composi- zione di un insieme Lk,m e l’ordinamento dei branching point:

è possibile utilizzare le relazioni scritte sopra per ottenere dei vincoli sui possibili valori delle altre sequenze Lk,l; è possibile

dunque, quando si andrà ad effettuare una decisione a partire dalle metriche misurate per ricavare la composizione degli insie- mi Lk,l, ridurre lo spazio delle ipotesi scartando tutte gli insiemi

di link che non rispettano tali vincoli. In questo modo, sfrut- tando le relazioni tra gli insiemi di link appartenenti allo stesso path end-to-end, si riescono a compiere decisioni più affidabili. Sul principio appena esposto si basa l’algoritmo 6.

Come si può notare, l’algoritmo 3.1.2.3 prende le prime de- cisioni sulla base delle metriche più affidabili e sfrutta i vincoli ricavati da tali decisioni per restringere lo spazio delle ipotesi relativo alle decisioni basate sulle misure meno affidabili.

Per eseguire correttamente tale algoritmo è però necessario conoscere sia l’ordinamento dei branching point, sia un indice dell’affidabilità di ogni stima relativa delle metriche.

L’ordinamento dei branching point è facilmente ricavabile da quello delle metriche dl,k, dato che, per le proprietà delle

metriche di tipo packet sandwich, dn,k > dm,k se m è a monte

di n; sarà realistico ipotizzare che, nonostante le stime di queste metriche siano affette dal disturbo dovuto al cross-traffic, esso non sia abbastanza forte da rendere l’ordinamento delle metriche stimate diverso da quello delle metriche reali.

Per quanto riguarda invece l’indice dell’affidabilità delle sti- me sono pensabili diverse soluzioni, che dipenderanno natural- mente dalla tecnica di stima adottata (oltre alla semplice media campionaria di tutte le misure disponibili verranno proposte,

Algoritmo 6Strategia di decisione delle sequenze di link che sfrutta le relazioni tra i diversi shared path