lesson_12.md 2.0 KB
Piattaforme e Software per la rete - lezione 12
Giacomo Verticale
22 April 2016
Schema identificativo a soglia
L'ideale sarebbe avere una batteria di contatori, uno per ogni identificatore di flusso, e potrei avere un blocco che estrae gli id dei flussi sopra la soglia, però questa soluzione è inefficiente.
Una soluzione migliore è un insieme di vettori riempiti da funzioni di hash
Esercizio
Suppondendo di avere un link con capacità C=100Mbit/s e N=100'000 flussi contemporanei (1 pacchetto alla volta, tdm statistico), finestra di misura =1s Output: elenco flussi che superano 1% di C Scelte di progetto: 4 array, ogni array di 1000 elementi
Calcolare la probabilità che flusso da 100kbit/s sia inserito nell'elenco
Il caso peggiore dell'architettura a bucket è quando ho pochi flussi molto pieni e i restanti quasi vuoti, se il flusso va a finire in uno dei bucket pieni, ho un falso positivo. Se il livello di riempimento dei bucket è uniforme, ho una bassa probabilità di avere un falso positivo La probabilità massima di falso positivo la ho quando ho tanti flussi piccoli in pochi bucket, perchè questi faranno scattare la soglia. x=(N-1)/900kbit = 111 bucket p.falso positivo = 11,1% (risultato su un array) falso positivo con 4 array 0 (11,1%)^4
Contare i flussi
Per ogni pacchetto calcolare F(flowID) Calcolare H = hash(F) perchè flowID in se non è uniformemente distribuito Contiamo il numero di 0 consecutivi del bit meno significativo Chiamiamo x il numero massimo di 0 osservati consecutivi Lo stimatore di N numero flussi distinti è N=2^x
Campionamento delle traiettorie
Può essere utile effettuare il consistent hashing, che consiste nel fare in modo che tutti i nodi della rete campionino gli stessi pacchetti e ignorino gli stessi. Il primo nodo che campiona un pacchetto scegliendono a caso utilizza una firma del pacchetto, usando una concatenazione dei campi del pacchetto (che non cambiano da nodo a nodo) in modo da ottenere un valore specifico di quel pacchetto.