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.

lesson_09.md 5.1 KB 히스토리 Raw