2.4 Topology discovery con sorgenti multiple
2.4.2 Tecniche di probing per la ricostruzione d
Per eseguire la ricostruzione topologica con le modalità prece- dentemente descritte è necessario individuare una tecnica di pro- bing che permetta, a partire da misure end-to-end, di capire, per ogni possibile coppia di ricevitori, se il branching point relativo sia shared o unshared.
La tecnica proposta in [10] prevede l’utilizzazione di pro- be composte da quattro pacchetti e che seguono la procedura illustrata in figura 2.14. Ogni probe è composta da due pac- chetti per ognuna delle due destinazioni: al tempo t0 entrambe le sorgenti inviano un pacchetto al ricevitore 1, con uno offset temporale che è scelto in modo random da una distribuzione uniforme su un opportuno intervallo [−D, D]; dopo un tempo
Figura 2.14: struttura delle probe del processo di misura per eseguire il merging di alberi con diverse radici
∆t ,scelto opportunamente in modo da non avere interferenza tra le due coppie di pacchetti (gli autori suggeriscono di scegliere ∆t > l/Cmin, con Cminpari alla minima capacità dei link della
rete, in modo che le due probe inviate dalla stessa sorgente non si trovino mai nella stessa coda), entrambe le sorgenti inviano una seconda probe con lo stesso sfasamento, ma questa volta al ricevitore 2.
Si faccia ora riferimento alla figura 2.13a, in cui il branching point è shared: essendo i pacchetti appartenenti alle due coppie partiti con lo stesso offset temporale, essi arriveranno al bran- ching point nello stesso ordine e dunque, a meno di un impro- babile riordinamento sul path condiviso a valle del branching point, entrambi i ricevitori vedranno arrivare i due pacchetti nello stesso ordine (ad esempio entrambi i ricevitori vedranno arrivare per primo il pacchetto dalla sorgente A). Al contrario, in un caso di unshared branching point come quello di figura 2.13d , essendovi due punti di innesto diversi a seconda della
destinazione, non vi è alcuna garanzia che entrambi i ricevitori vedano arrivare le due probe nello stesso ordine. Si indichi in- fatti con dX,n il ritardo associato al path fra la sorgente X e il
punto di innesto dei due alberi verso il ricevitore n: i due rice- vitori vedono un diverso ordine dei pacchetti (evento di reverse ordering) se, ad esempio si verifica che
• of f set > dA,1-dB,1
• of f set < dA,2-dB,2
Nel caso di shared branching point il secondo termine delle due disequazioni è uguale e dunque non è possibile che si verifichi un evento di reverse ordering. Naturalmente, in una situazio- ne reale, i termini al secondo membro sono variabili aleatorie e dunque l’evento di reverse ordering può avvenire anche nel caso di shared branching point; gli autori dell’algoritmo dimostrano tuttavia che nel caso di shared branching point la probabili- tà di tale evento è comunque sensibilmente minore di quella sperimentata nel caso di unshared branching point.
Gli autori fanno notare come uno dei vantaggi di questa tecnica sia il fatto che non è necessario avere un meccanismo sincronizzazione dei nodi di altissima precisione: i ricevitori de- vono solo registrare l’ordine di arrivo dei pacchetti, mentre, per quanto riguarda i trasmettitori, un errore di sincronizzazione si somma all’offset che è comunque una variabile aleatoria. E’ im- portante comunque che l’offset non assuma valori troppo alti, in quanto in tali casi il reverse ordering dei pacchetti diverrebbe quasi impossibile a prescidere dalla topologia (se un pacchetto parte con un eccessivo anticipo rispetto all’altro arriverà molto
probabilmente per primo in ogni caso), ma per ottenere que- sto risultato basta una sincronizzazione grossolana, fornita, ad esempio, da un protocollo di tipo handshake.
Enunciato questo principio, è necessario sviluppare una stra- tegia di decisione che permetta di distinguere i due casi.
Un primo approccio a questo problema parte dall’osservare che nel caso di shared branching point, essendo dX,1 = dX,2, la
probabilità di reverse ordering rilevata è la stessa che si osserve- rebbe inviando entrambe le coppie di probe allo stesso ricevitore. Si considerino quindi le due sequenze binarie z1
n e zn2, associa-
te rispettivamente al caso in cui le due coppie di pacchetti che costituiscono una probe siano inviate allo stesso ricevitore e a quello in cui esse siano inviate a a ricevitori diversi e i cui ele- menti valgono 1 nel caso in cui in corrispondenza della probe n-esima si sia verificato un evento di reverse ordering e 0 altri- menti: nel caso di shared branching point zn1 e zn2 dovrebbero
essere due sequenze di prove di Bernoulli con gli stessi valori di p e q (la probabilità di successo sarebbe la stessa e coinci- derebbe con la probabilità di reverse ordering) mentre nel caso di unshared branching point z1
n e zn2 sarebbero due sequenze di
prove ripetute binarie con diverse probabilità di successo. La questione originale si riduce quindi ad un classico problema di decisione statistica tra due ipotesi, la cui soluzione è proposta in [10].
Una seconda soluzione sfrutta invece una versione modificata della tecnica di probing precedentemente esposta, che è illustra- ta in figura 2.15 e che consente con uno stesso processo di misura di capire per ogni coppia di end-nodes se il branching point sia shared o unshared e di ottenere informazioni sulle metriche della
Figura 2.15: Schema di probing modificato per la giunzione di diversi alberi
relativa topologia.
In questo secondo schema ad ognuno dei pacchetti della pro- cedura illustrata in figura 2.14 è sostituita una probe composta che permette, usando una delle tecniche esposte nel paragrafo precedente, di ottenere informazioni di tipo metrico; in figura 2.15, si fa uso di packet pairs che possono essere sfruttati, ad esempio, per ottenere informazioni sulla covarianza dei ritardi, ma si potrebbe anche immaginare di sostituire ad ogni pacchetto dello schema originale un packet sandwich (in questo caso per calcolare la probabilità di reverse ordering conterebbe l’ordine di arrivo dei primi pacchetti del sandwich).
A partire da tale schema è stata ideata una strategia di deci- sione che permette congiuntamente di scegliere le ipotesi (shared o unshared) e le metriche (ad esempio le varianze del ritardo sui vari link) a massima verosimiglianza date le osservazioni. Tale strategia è illustrata in modo approfondito in [25, 24].