# Piattaforme e Software per la rete - lezione 10
#### Giacomo Verticale
###### 15 April 2016
## Scheduler Deficit Round Robin (DRR)
Lo scheduler round robin classico risulta iniquo nel caso ho pacchetti 
di dimensione variabile, una delle implementazioni per simulare un round 
robin su pacchetti di dimensione variabile è il __Deficit Round Robin__

Ho una serie di code su cui accumulo ad ogni turno una serie di permessi
Se i permessi sono sufficienti a trasmettere, posso trasmettere,
altrimenti li accumulo.
Per ogni coda ho:
- Qi (quanto) costante nel tempo
- Di (deficit) variabile nel tempo

Quando visito la coda i-esima calcolo il nuovo Di
Di = Di + Qi
Finchè Di >= Li (Li= lunghezza primo pacchetto)
trasmetto il primo pacchetto.
Quando la coda che sto servendo non ha più pacchetti, non accumula deficit,
La mia idea è di trasmettere qualcosa ad ogni iterazione, per questo posso
fare il quanto grande come il più grande pacchetto possibile.
Faccio in modo che rimangano nella lista solo le code attive:
- Le code che hanno trasmetto vengono messe in fondo alla coda dopo la visita
- Le code che non hanno più pacchetti da trasmettere vengono rimosse dalla lista.

### Esempio
CODE:
- 20,750,200
- 500,500
- 200,600,100
- 50,700,180
Qi=500 per ogni i
Simulare DRR indicando ad ogni tempo Di quali pacchetti sono trasmessi

Round | Coda | Di iniziale | Di finale | L pacchetto Tx | FineTx
---   | ---  | --- | --- | --- | ---
1     | 1    | 0   | 300 | 200 | 200
1     | 2    | 0   | 0   | 500 | 700
1     | 3    | 0   | 400 | 100 | 800
1     | 4    | 0   | 320 | 180 | 980
2     | 1    | 300 | 50  | 750 | 1730
2     | 3    | 400 | 300 | 600 | 2850
2     | 3    | 300 | 0   | 200 | 3050
2     | 4    | 120 | 0   | 50  | 3800

## Esercizi
### Esercizio Algoritmo RED
Assumendo lunghezza media della coda costante, calcolare
la distribuzione di probabilità e valore atteso
del numero di pacchetti tra due eventi di scarto successivi
nei due casi:
- il nodo scarta con probabilità p
- il nodo scarta con probabilità pd = p /1-cp  con c= numero di pacchetti da ultimo scarto

a: chiamo X il numero di pacchetti tra due scarti
`Pr(X=x) = (1-p)^X*p`
x | Prob
--- | ---
0 | p
1 | (1-p)p
2 | (1-p)^2p

è una distribuzione di tipo geometrico (quanti fallimenti prima di un successo)

b: Pr(X=x) = p / 1-(x-1)p
$ p/(1-(x-1)p) /sigma^(x-2)_(c=0) (1-p/(1-cp)) =$ //p se 1<=x<= 1/p


### Esercizio di classificazione
_p
- Definire il bitvector per ogni campo
- Applicare l'algoritmo a (A,D,80,23,TCP)
Ip Src | IP Dst | Port Src | Port Dst | Prot
---    | ---    | ---      | ---      | ---
A      |    *   |   53     |    80    | UDP
B      |    C   |   123    |    80    | *
A      |    D   |   80     |    *     | TCP
*      |    E   |   *      |    25    | TCP

Il __bitvector__ indica su quali regole matcha il pacchetto
IP sorgente | bitvector
--- | ---
A | 1011
B | 0101
* | 0001

IP destinazione | bitvector
--- | ---
C | 1100
C | 1010
E | 1001
* | 1000

Port Src | bitvector
--- | ---
53 | 1001
123 | 0101
80 | 0011
* | 0001

Resta da effettuare l'AND dei bitvector dei campi
Campi | bitvector
--- | ---
A | 1011
D | 1010
80 | 0011
23 | 0010
TCP | 0111
res | 0010

### Esercizio prefissi IP
Per codificare un prefisso di lunghezza variabile usando 33 bit
usiamo il seguente algoritmo:
Scriviamo i bit del prefisso seguiti da 1 e poi zeri fino a 33 bit
- Dire quanti sono i possibili prefissi di 32bit
- Codificare 128.0.0.0/2 128.0.0.0/3 128.0.0.0/4

### Esercizio Unibit Trie
Mostrare che il massimo numero di nodi è O(NW)
con 
- N = numero di prefissi e 
- W= lunghezza massima prefisso
Suggerimento: costruire un trie con log2N livelli e poi aggiungere
a ogni foglia una stringa di W-log2N bit

(W-log2N)N/2+N/2-1
O(W*N)