# 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 log2log2b*N (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