# Piattaforme e Software per la rete - lezione 9
#### Giacomo Verticale
###### 12 April 2016
## Router pt.2

Dei pacchetti che arrivano nel router viene separata l'intestazione che viene inviata al meccanismo di lookup.
Le code nell'algoritmo take-a-ticket sono negli ingressi, le uscite sono molto semplici.
Negli algoritmi tipo *pim* in cui si usano meccanismi di speedup interni, alzando la velocità della
matrice di commutazione rispetto alla velocità degli ingressi/uscite

### Gestione delle code in uscita
#### Gestione del buffer
I buffer sono di capacità finita quindi prima o poi si riempono e serve scartare i pacchetti.
La politica di __scheduling__ determina quale pacchetto viene spedito sull'interfaccia di uscita
che può essere quello più vecchio ma non necessariamente.

__Soluzione base__
- Gestione buffer __tail drop__: accetto pacchetti finchè il buffer è pieno
- Scheduling fifo
Questa soluzione base va bene per carichi leggeri.
Il caso di test tipico è una connessione TCP perchè sono molto diffuse in internet.
```
|
|
|       -
|     -
|   -   
|  /
| /
|-
|
---------------------->
slow
start
```
La crescita è esponenziale durante slow start e lineare una volta superata SSTHRESH
- Fase esplorativa: congestion avoidance
La differenza fra TCP Tahoe e TCP Rhyno è che a seguito di una perdita di un pacchetto
in Tahoe si aspetta il TimeOut e si va a velocità 1, Rhyno usa un meccanismo di __fast recovery__
che controlla il pacchetto perso nella sequenza e dimezza la velocità e abbassando SSTHRESH
si riparte con crescita lineare.

Il meccanismo di __crescita additiva__ e __decrescita moltiplicativa__ raggiunge
un buon compromesso tra aggressività ed efficienza.

I pacchetti TCP vengono inviati a burst, e arrivati ad una cerca velocità il nodo inizia a *scartare pacchetti*
Il buffer impiega del tempo per svuotarsi, e c'è un alta possibilità che i pacchetti persi siano della stessa
connessione, questo crea problemi al meccanismo di fast retrasmit che riesce a recuperare solo buchi di pochi pacchetti.
Il risultato è che avendo perdite multiple si disattiva __fast recovery__, scatta Timeout e si va a velocità 1.

Quindi la gestione __taildrop__ porta a perdite multiple di una stessa connessione, inoltre una volta
che avviene un *buffer overflow* vengono penalizzate anche le sorgenti che non hanno causato la perdita
di pacchetti.
Inoltre ho sincronizzato la forma del throughput delle sorgenti, quindi le sorgenti si sommano nei picchi
e negli avvallamenti e quindi non posso raggiungere una velocità elevata.
L'ultimo problema è che la notifica della perdita di pacchetti avviene dopo quest'ultima,
in questo modo è impossibile evitare la perdita riducendo la velocità.

__Obiettivi__ per un buffer scheduling
- Segnalare una congestione immminente alle sorgenti tcp più attive.
- Garantire *fairness* tra sorgenti anziane e giovani (anziane hanno priorità)
- Fornire garanzie di banda e ritardo per flusso (QoS)

 ### Random Early Detection (RED)
è un algoritmo di gestione del buffer, decide quali pacchetti ammettere nel buffer.
- Scarto pacchetto con probabilità p
THR equilibrio TCP è proporzionale a MSS/(RTT* sqrt(p))*
Se il nodo è il collo di bottiglia, il punto di lavoro rimane sulla retta lineare della threshold.
```
|
|
|
|
|        /
|       /
|      /
|_____/
|-----------------------
     min   max
    thresh thresh
```

Il problema è che tutte le connessioni piccole, ad esempio quelle per richiedere una pagina web
non sfruttano il meccanismo di congestion window TCP

#### Varianti
- Stimatori autoreferenti
occupazione media(t)
(1-alpha)*occupazione media(t-1)
+ alpha*occupazione attuale

- Una variante di questo modello è un meccanismo che utilizza curve diverse per ogni classe di applicazioni
e si chiama __Weighted RED__
- __RED for in and out__

### Politiche per allocazione di banda
__FIFO__
- Allocazione proporzionale alla richiesta di banda
- Nessuna protezione da sorgenti greedy
- Semplice da implementare

__Priorità semplice__
- Richiede code multiple
- Richiede un classificatore
- Serve in ordine di priorità
- Servizio può essere interrompibile o non interrompibile
Nel caso di collegamenti lenti (~10Kbit/s) ha senso distinguere tra trasmissioni interrompibili o non.
Nelle reti moderne non viene effettuato il blocco della trasmissione di un pacchetto per trasmetterne
un altro perchè il tempo richiesto a trasmettere il pacchetto è poco.

Funziona abbastanza male se le priorità sono tante perchè i pacchetti a priorità bassa
soffrono di starvation.
Per risolvere questo problema, alla alta priorità viene associato un limite sulla banda utilizzata

__Round Robin__
- Necessita di un classificatore
- Una coda per classe
- Servo un pacchetto per ogni coda.
- Se i pacchetti hanno lunghezza variabile funziona molto male.
Per rendere fair round robin con dimensioni variabili si cerca di di simulare il round robin bitwise che
è fair per definizione, ad esempio si effettua un round robin bitwise e quando viene selezionato il bit finale
di una coda, viene inviato il pacchetto corrispondente, in questo modo si ottiene una distribuzione uniforme.