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

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)