2.2 L’uso delle metriche per la ricostruzione della to-
2.2.2 Metriche ottenute con la tecnica packet
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
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 la relazione 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 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.
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
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
tempo pari a l1/Ci il terzo pacchetto sarà stato completamente
trasmesso e sarà accodato dietro al secondo nella coda del nodo a valle, come mostrato in figura 2.8b); l’incremento ∆d della distanza temporale fra il primo e il terzo pacchetto sarà pari al tempo trascorso dal pacchetto in tale coda, che sarà uguale a l2/Ci+1− l1/Ci. Da tale espressione è possibile calcolare la me-
trica d relativa ad un path di N hop composto da N nodi ni(con
i compreso fra 1 e N), ognuno dei quali è connesso al successivo con un link di capacità Ci: la distanza temporale iniziale fra i
primi bit dei due pacchetti più corti del sandwich sarà pari a l2/C1+ l1/C1, valore che verrà incrementato di una quantità
l2/Ci+1 − l1/Ci in corrispondenza di ogni nodo ni interno al
path, con l’eccezione del nodo con indice N (il branching point), il quale contribuirà soltanto con un termine l2/Ci+1. Il valore
totale di d registrato dal nodo ricevitore sarà allora dato da
l2/C1+ N −1X
i=2
(l2− l1)/Ci+ l2/CN
Si può notare come la metrica calcolata in questo modo non dipenda dal verso della misura, a meno che la capacità di un link non sia diversa nei due sensi di percorrenza. Al contrario le metriche legate alla covarianza dipendono dalle statistiche del traffico che sollecita le diverse code associate ai link sul path ed è quindi dipendente dal verso della misura: una probe speri- menterà infatti in ritardo di accodamento sulla coda a monte di ogni link del path, mentre la probe che viaggia nel senso opposto attenderà nelle code a valle.
non richiedere alcuna sincronizzazione fra sender e receiver: la distanza temporale ∆d viene infatti misurata dal ricevitore sen- za bisogno di informazioni da parte della sorgente e quindi non c’è bisogno di confrontare misure ottenute da due orologi diversi. Questa tecnica incontra comunque delle difficoltà nel caso in cui i link della rete siano molto veloci: infatti un link di alta capacità introduce un ∆d piccolo, che diventa difficilmente apprezzabile se è presente anche il rumore dovuto al cross traffic.