polimd/Piattaforme Software per la Rete/MOD1/lesson_11.md

Piattaforme e Software per la rete - lezione 11

Giacomo Verticale

19 April 2016

Misura del traffico internet

La rete internet funziona abbastanza per quanto riguarda la consegna a destinazione dei pacchetti, per quanto riguarda le prestazioni, c'è bisogno di lavoro per ingegnerizzare la rete Fasi:

• Misura del traffico: è necessario effettuare aggiornamenti della rete per tenere il passo con la richiesta sempre maggiore, l'aggiornamento viene effettuato tenendo conto di alcune priorità
  • input A: pianificazione della capacità
  • accounting (billing): classificare il traffico
  • analisi del traffico

Matrice di traffico

Il routing di internet è topology driven, ed è una limitazione in quanto non c'è la possibilità di bilanciare l'utilizzo delle risorse, ad esempio sfruttando link paralleli.

è una tabella che riporta per ogni coppia di nodi, quanto traffico entra da un nodo per andare all'altro (bit/s) Questa matrice viene costruita per i nodi che stanno sul confine della rete da considerare. Con N nodi sul confine abbiamo una tabella di N^2 nodi, con gli elementi sulla diagonale nulli, quindi N(N-1) incognite. Il traffico è un parametro che cambia nel tempo quindi la matrice sarà in funzione del tempo, anche se in questo caso consideriamo un tempo fissato. Viene sfruttato il meccanismo dell' interface counting che è una feature presente in tutti i router e indica quanti byte o pacchetti sono transitati per ogni interfaccia. Ogni interfaccia porta a due equazioni di N incognite (una per il traffico in ingresso e una per quello in uscita) In totale ho 2N equazioni in N^2 incognite, quindi non posso risolvere le equazioni Dato che il numero di incognite è praticamente fisso, mi serve aumentare il numero delle equazioni e posso farlo aumentando i contatori per interfaccia (es: differenziandoli per ip o servizio)

• Questo può portare a milioni di contatori.
• Un pacchetto fa incrementare più di un contatore
• lunghezza dei contatori

Normalmente per ogni contatore si considerano 64bit, per milioni di contatori la memoria occupata diventa molta e non è possibile tenerli in memoria cache. Una strategia efficace è tenere in cache i c bit più significativi di tutti i contatori, suddividendoli in verticale La probabilità di andare in overflow avendo pochi bit è elevata, quindi serve resettare periodicamente i contatori piccoli e trasferire il conteggio sui contatori lunghi. Ogni b accessi scelgo un contatore corto, sommo il valore al corrispondente contatore lungo e resetto il contatore corto Quale contatore scelgo? largest count first Copio per primo il contatore corto che ha il valore più grande, perchè è il più vicino all'overflow

c deve essere circa log2log2bN (N=numero contatori) Quel valore garantisce che usando l'algoritmo largest count first, non si ha mai overflow. Il problema dell'algoritmo lcf è che trovare il massimo impiega tempo lineare. Sarebbe possibile tenere memorizzato l'indice e il valore del contatore più grande, ma questo vale finchè non viene resettato.

Algoritmo semplificato

• Sia cj il contatore con il valore massimo aggiornato nel ciclo precedente di b accessi
• Se cj >= b aggiorna e resetta cj.
• Altrimenti aggiorna e resetta un contatore a caso perchè valga almeno b

Conteggio randomizzato All'arrivo di un pacchetto aggiorna il relativo contatore con probabilità 1/c Mettere l'intervallo di campionamento a distanza casuale riduce il rischio di aliasing, Cioè la sincronizzazione dell' osservazione con i fenomeni (esempio zebra nella gabbia) Se un contatore vale x allora il valore atteso del numero di pacchetti è x*c La deviazione standard è pari a qualche c

• Se x >> c alta precisione
• Se x ~~ c contatore inutile In particolare la misura degli eventi occasionali è totalmente trascurabile, Voglio evitare che nella misurazione si confondano eventi rilevanti ed eventi casuali. Un esempio di techica utilizzata è quella dell' aggregazione a soglia Esempio: ``` Si presenta un pacchetto con IDflusso = F ID flusso per connessione TCP = IPsrg||IPdst||proto||portsrg||portdst ID flusso per servizi destinazione = IPdst||proto||portdst Dall'ID del pacchetto calcolo tre funzioni di hash e inserisco i tre risultati in array diversi Se A1[h1(f)>T e così via per tutte le funzioni e array, allora salvo il flusso F Se il numero di pacchetti nel flusso F supera T allora Ai[hi(f)>T