Tecniche di schedulazione - telematica.polito.it · – FIFO, processor sharing, round robin,...

Pag. 1

Telematica

TECNICHE DI SCHEDULAZIONE - 1

Tecniche di schedulazione

Gruppo Reti TLC [email protected]

http://www.telematica.polito.it/


N ingressi

OUTPUTBUFFER

Algoritmi di scheduling• Scheduling: scegliere un pacchetto da

trasmettere su un canale di uscita, tra i tanti disponibili in un nodo (punto di multiplazione)

Pag. 2

Telematica


Architettura output buffer• Permette di eseguire algoritmo di

schedulazione per ottenere QoS operando in modo indipendente canale per canale

• In architetture con memorie in ingresso problemi si complicano– scheduling per QoS e scheduling per trasferire

dati da ingresso ad uscita hanno esigenze contrastanti


Algoritmi di scheduling• Operano su punti di multiplazione• Devono essere implementabili in hardware• Regolano interazione tra flussi

• singola relazione di traffico (1VP/1VC)• insieme di relazioni (+VC/1VP o +VC con uguali

richieste di QoS)• classi di QoS

• Sono strettamente legati e dipendenti da algoritmi di gestione delle memorie

• Per studio di algoritmi, si ipotizzano memorie infinite

Pag. 3

Telematica


QoS-capable router

Classificazione

Shaping

Policing

Input link

Output link

PolicerVerifica che il flusso in ingressorispetti determinate condizioni

ClassificatoreIdentifica il flusso a cui appartiene il pacchetto in arrivo

Buffer di accettazioneAccetta o rifiuta un pacchettoin arrivo

ShaperRitarda flussi che nonrispettano determinatecondizioni

Strategia di codaOrganizzazione localedel buffer del router

SchedulerSeleziona il pacchettoche deve essere inviatoper primo sul link di uscita


Algoritmi di scheduling: proprietà• Isolamento tra flussi

– i flussi “mis-behaving” non devono danneggiare quelli “well-behaved”

– PER-FLOW queuing, ovvero partizione di risorse• scheduler sceglie da quale coda trasmettere

• Garanzie end-to-end statistiche o deterministiche– banda

• uguale per tutti i flussi (utile per best effort)• specifica per flusso

– ritardo

Pag. 4

Telematica


Classificazione algoritmi di scheduling

• Work-conserving scheduler– Trasmettono sempre un pacchetto, purché ce ne

sia almeno uno nella memoria del commutatore– prestazioni ottime in termini di throughput

• Non-work-conserving scheduler– Possono ritardare la trasmissione di pacchetti

anche se ci sono pacchetti in coda– Possono fornire migliori garanzie di jitter di

ritardo– Funzionale in teoria, poco implementato


Obiettivi algoritmi di scheduling• Scheduler per traffico best-effort

– tutti flussi attivi hanno diritto alla stessa quantità di servizio

– possibilmente max-min fair– nessuna garanzia di ritardo– FIFO, processor sharing, round robin, deficit round

robin• Scheduler per traffico con requisiti QoS

– garanzie di banda specifiche per flusso– garanzie di ritardo specifiche per flusso– priorità secca, Generalized processor sharing,

weighted round robin, weighted fair queueing

Pag. 5

Telematica


FIFO

• Unica coda• Unità dati accodate nell’ordine di arrivo e

servite in tale ordine


FIFO: proprietà• Work-conserving• Completa condivisione di memoria e banda:

non protegge da flussi non conformi • Tutti i flussi osservano la stessa QoS in

termini di ritardo• Nessuna garanzia di banda e probabilità di

perdita, che dipendono da quantità di traffico di ingresso di ogni singolo flusso

• Premia flussi aggressivi

Pag. 6

Telematica


[ ]attiviflussi

ratejrate link

.#=

Flow 2Flow 1

Flow 3

Flow 4Scheduler

Processor Sharing• Scheduler work-conserving ideale per best

effort• Ogni coda è servita dallo scheduler come se

contenesse un flusso fluido• All’istante t la coda j è servita con rate


Flow2 (2L) Flow1(L)

Flow3 (L)

100%

50%

33%

Solo flusso 1 attivo

Flussi 1 e 2 attivi

Rate diservizio flusso 1 Flussi 1,2 e 3 attivi

Flussi 1 e 2 attivi

Tempi di completamento per pacchetti dei tre flussi:F1 : 1, 3, 5, 8, 10, 11, 12 F2 : 5, 10F3 : 8

11 10 9 8 7 6 5 4 3 2 1 0

Output rate = L/s

0 1 2 3 4 5 6 7 8 9 10 11

Processor Sharing: esempio

Pag. 7

Telematica


Processor Sharing• Vantaggi

– Se nessun pacchetto è scartato, una rete di scheduler PS può fornire max-min fairness

• La fairness non dipende dai meccanismi di controllo di congestione

• Se avvengono scarti di pacchetti, lo scarto deveessere eseguito in modo equo

• Svantaggi– Soluzione matematica ideale, non

implementabile in pratica (i pacchetti non sonofluidi!)

• Implementare approssimazioni


Round Robin• Approssimazione processor sharing• Si separa la memoria in K code, ciascuna

gestita in modo FIFO • Si esegue un ciclo di servizio tra code,

servendo un pacchetto da ogni coda

Flusso 1

Scheduler

F1

F2

F3F4

F5

Flusso 2

Flusso 4Flusso 3

Flusso 5

Pag. 8

Telematica


Round Robin• Per avere migliore equità, ad ogni tempo si

può iniziare la scansione delle code da quella successiva all’ultima servita

• al tempo 0 scandisco le code: 1,2,3,..,K• al tempo 1 scandisco le code: 2,3,..,K,1


Round Robin: proprietà• Facile da implementare in hardware• Garantisce isolamento• Velocità di servizio su ogni coda:

– C/K, se pacchetti di dimensione fissa– altrimenti dipende dalla dimensione del

pacchetto– tenere conto della dimensione dei pacchetti

rende le cose più complicate

Pag. 9

Telematica


Round Robin: esempio

Flow2 (2L) Flow1(L)

Flow3 (L)

F1

F2F3

T In F1 In F2 In F3 Q(F1) Q(F2) Q(F3) Schedulati0 P10[1] P20[2] - P10 P20 - F1:P101 P11[1] - - P11 P20 - F2:P202 P12[1] P22[2] - P11,P12 P22 - F2:P20 (cont)3 P13[1] - - P11,P12,P13 P22 - F1:P114 P14[1] P24[2] - P12,P13,P14 P22,P24 - F2:P225 P15[1] - P35[1] P12,P13,P14,P15 P24 P35 F2:P22 (cont)6 P16[1] P26[2] P36[1] P12,P13,P14,P15,P16 P24,P26 P35,P36 F3:P357 - - P37[1] P12,P13,P14,P15,P16 P24,P26 P36,P37 F1:P128 - P28[2] - P13,P14,P15,P16 P24,P26 P36,P37 F2:P249 - - - P13,P14,P15,P16 P26,P28 P36,P37 F2:P24

10 - P2A[2] - P13,P14,P15,P16 P26,P28 P36,P37 F3:P36

11 10 9 8 7 6 5 4 3 2 1 0


Deficit Round Robin• Realizza round robin con pacchetti

dimensione variabile• Si associa contatore d[i] ad ogni coda[i]

– aumento d[i] di un quantum quando coda[i] è visitata

• if (first_packet di coda[i] > d[i]){ packet resta in coda[i] }

• else{packet trasmesso su output link;d[i]=d[i]- packet_length;if (coda[i] è vuota) { d[i]=0; }

}

Pag. 10

Telematica


Deficit Round Robin: esempio

Flow2 (2L) Flow1(L)

Flow3 (L)

F1

F2F3

T Inc. D[1] D[2] D[3] Q(F1) Q(F2) Q(F3) Scheduled0 F1 0+1-1 0 0 P10 P20 - F1:P101 F2,F1 0+1-1 0+1 0 P11 P20 - F1:P112 F2 0 1+1-2 0 P12 P22 - F2:P203 - 0 0 0 P12,P13 P22 - F2:P20(cont)4 F1 0+1-1 0 0 P13,P14 P22,P24 - F1:P125 F2,F3 0 0+1 0+1-1 P13,P14,P15 P22,P24 P35 F3:P356 F1 0+1-1 1 0 P14,P15,P16 P22,P24,P26 P36 F1:P137 F2 0 1+1-2 P14,P15,P16 P22,P24,P26 P36,P37 F2:P228 - 0 0 0 P14,P15,P16 P24,P26 P36,P37 F2:P22(cont)9 F3 0 0 0+1-1 P14,P15;P16 P24,P26 P36,P37 F3:P36

10 F1 0+1-1 0 0 P15,P16 P24,P26 P37 F1:P1411 F2,F3 0 0+1 0+1-1 P15,P16 P24,P26 P37 F3:P37...

11 10 9 8 7 6 5 4 3 2 1 0


Algoritmo a priorità secca• Separo la memoria in K code • A ciascuna coda si associa priorità diversa• Unità dati memorizzate nella coda

dell’opportuno livello di priorità• Servo la coda a priorità maggiore. Solo se

vuota, passo a priorità inferiore• All’intero di ciascuna coda, le unità dati sono

servite in ordine FIFO

Pag. 11

Telematica


Algoritmo a priorità secca• Work-conserving• Facile da realizzare• Isolamento perfetto tra code, ma rischio di

starvation delle priorità inferiori• No garanzie di banda e ritardo• All’interno di una coda non ho nessuna

protezione tra flussi


[ ]∑

=

=

esactivequeui

linkiw

jwratejrate][

][

Generalized Processor Sharing• Sistema di riferimento fluido ideale• Ogni coda è servita dallo scheduler come se

contenesse un flusso fluido ovvero per una frazione infinitesima di tempo

• Si associa un peso w[i] alla coda i-esima• All’istante t, la coda j è servita con rate:

– Una coda è “attiva” se contiene pacchetti– Se il numero di connessioni attive diminuisce, la banda in

eccesso viene ridistribuita in modo proporzionale al rate

Pag. 12

Telematica


Generalized Processor Sharing• Proprietà

– Garanzie di banda per flusso• Usando un singolo scheduler GPS• Usando una rete di scheduler GPS

– Fornisce garanzie di ritardo end-to-end per flussilimitati da token bucket (r,b)

– Fornisce bound sulla dimensione dei buffer– Fornisce protezione tra flussi– “semplice” garanzia di jitter del ritardo ([0,Dmax])

• Scheduler ideale non implementabile


Approssimazioni di GPS• Frame-based

– si definisce un ciclo (frame) di servizio– si allocano porzioni di frame ad ogni flusso – Esempio: Weighted-Round Robin

• Sorted priority– Calcolo un timestamp (tag) e lo associo ad ogni

pacchetto– I pacchetti sono ordinati per timestamp

crescente• Esempio: Weighted Fair Queueing, Virtual Clock,

SCFQ

Pag. 13

Telematica


WRR: Weighted Round Robin

• Se tutti i flussi sono attivi, – F1 ottiene 4/9 di banda – F2 ottiene 2/9– F3, F4 e F5 ottengono1/9

Flusso 1

Scheduler

Flusso 2

Flusso 4Flusso 3

Flusso 5

F3

F4

F1

F1F5

F2

F1

F2

F1W1=4

W5=1

W2=2W3=1

W4=1


w1

w2

wN

1

2

N

WRR: Weighted Round Robin• Approssimazione GPS• Si separa la memoria in K code, ciascuna gestita in

modo FIFO • Si associa ad ogni coda un peso wi ∝ bit rate

richiesto• Si esegue un ciclo di servizio tra code, servendo

ogni coda in modo proporzionale al peso, ovvero wiper ciclo

Pag. 14

Telematica


WRR: proprietà• Work-conserving• Garantisce isolamento tra flussi• Per ogni coda i:

– bit-rate = wi / (Σjwj) se pacchetti di dimensione fissa

• Facile da implementare con pochi flussi• Deficit Round-Robin può essere esteso per il

supporto di pesi


WRR: problemi• Ciclo che può diventare molto lungo in

presenza di – molti flussi– flussi con velocità diverse

• Il servizio erogato ai singoli flussi è molto bursty (rimediabile ma complesso)

• Ad ogni variazione dei flussi attivi la schedulazione delle trasmissioni nell’intero ciclo deve essere rivalutata

Pag. 15

Telematica


Algoritmi famiglia WFQ• Code separate per flusso • Servo code sulla base di velocità negoziate e

tempo di arrivo delle celle• Si assegna una tag ad ogni unità dati • Si inserisce unità dati in una Sorted Priority

Queue in ordine di tag• Si serve in ordine di tag (urgenza)• Diverse versioni: virtual clock, WFQ o PGPS,

SCFQ


Virtual Clock• Tende ad emulare il Time Division

Multiplexing• Per ogni flusso j si conosce il rate di servizio

rj

• Ad ogni unità dati di ogni flusso si assegna una tag (l’etichetta), che rappresenta il tempo di servizio in un sistema TDM:

Aux VCjK = Aux VCj

K-1 + —Lj

k

rj

Pag. 16

Telematica


Virtual Clock: esempio 1Esempio:

r1=1/3

9876543210

r2=1/3

r3=1/3

3 6 9 12 15 18

3 6 9

9

12

12

1815

3 6

Ordine di servizio:3 3 3 6 6 6 9 9 9


Virtual Clock: esempio 1

1

Flusso 1 (r1=1/3)

T AV(F1) Q(F1) AV(F2) Q(F2) AV(F3) Q(F3) Scheduled flow

0 0+3 3 0+3 3 0+3 3 F11 3+3 6 3+3 3,6 3 3 F3 2 6+3 6,9 6+3 3,6,9 3 - F2 3 9+3 6,9,12 9+3 6,9,12 3+3 6 F1 4 12+3 9,12,15 12+3 6,9,12,15 6 6 F3 5 15+3 9,12,15,18 15+3 6,9,12,15,18 6 - F2 6 18+3 9,12,15,18,21 18+3 9,12,15,18,21 6+3 9 F1 7 21+3 12,15,18,... 21+3 9,12,15,18,21 9 9 F3 8 24+3 12,15,18,... 24+3 9,12,15,18,... 9 - F2 9 ....

Flusso 2 (r2=1/3)Flusso 3 (r3=1/3)

Pag. 17

Telematica


3 6 9 12 15

3 6 9 12

Virtual Clock: problemaProblema:

r1=1/3

r2=1/3

r3=1/3

9876543210

15

3 6

13121110

9 12 15


Virtual Clock: problema

1

T AV(F1) Q(F1) AV(F2) Q(F2) AV(F3) Q(F3) Scheduled flow

0 0 - 0+3 3 0+3 3 F2 1 0 - 3 - 3 3 F3 2 0 - 3 - 3 - -3 0 - 3+3 6 3+3 6 F2 4 0 - 6 - 6 6 F3 5 0 - 6 - 6 - -6 0 - 6+3 9 6+3 9 F2 7 0 - 9 - 9 9 F3 8 0 - 9 - 9 - -9 0+3 3 9+3 12 9+3 12 F110 3+3 6 12 12 12 12 F111 6+3 9 12 12 12 12 F112 9+3 12 12+3 12,15 12+3 12,15 F113 12+3 15 15 12,15 15 12,15 F2

Flusso 1 (r1=1/3)Flusso 2 (r2=1/3)Flusso 3 (r3=1/3)

Pag. 18

Telematica


Virtual Clock• Si ottiene equità a lungo termine

– flussi inattivi recuperano il tempo perduto, ma a scapito di altri flussi attivi

• Se un flusso è inattivo per molto tempo, quando si riattiva può mandare in starvationaltri flussi (conformi)

• Si modifica il calcolo della tag:

• dove a è tempo di arrivo

Aux VCjK = max (Aux VCj

K-1, ajk) + —

Ljk

rj


Virtual Clock modificatoProblema:

r1=1/3

r2=1/3

r3=1/3

9876543210 13121110

3 12 21 30 39

15 18

6 9 15 18 24 27 33 36

3 12 21 30 396 9 15 18 24 27 33 36

Pag. 19

Telematica


WFQ (Weighted Fair Queueing) o PGPS (Packetized GPS)

• Algoritmi che approssimano il GPS – la granularità con cui si può erogare servizio in

realtà non può essere inferiore al tempo necessario per trasmettere una cella, poiché la trasmissione di una cella non può venire interrotta

• Si sceglie all’istante τ di servire il pacchetto che completerebbe per primo il servizio in un sistema GPS se non arrivassero altri pacchetti dopo τ– Si deve emulare sistema GPS


WFQ o PGPSEsempio:• 1 flusso con rate 0.5

– arrivano 10 pacchetti a rate 1 a partire da tempo 0• 10 flussi con rate 0.05

– arriva 1 pacchetto a tempo 0Sistema fluideale

Ordine di servizioP1

P11

P20

P1 P10P2 P3 P4 P5 P6 P7 P8 P9

P11 P12 P13 P14 P15 P16 P17 P18 P19 P20P2 P3 P4 P5 P6 P7 P8 P9 P10

...

Pag. 20

Telematica


WFQ o PGPS• Calcolo della tag

– Sarebbe importante poterlo effettuare nel momento in cui si riceve unità dati

– Dovrei conoscere il futuro, poiché il tempo di fine servizio nel sistema reale dipende dall’attivarsi nel futuro di nuovi flussi

– Semplice se flussi sempre attivi perché conosco rate di servizio


WFQ o PGPS• Calcolo della tag:

• V(t) è detto tempo virtuale o potenziale di sistema:

• Se flussi tutti sempre attivi, tempo virtuale coincide con tempo reale

Fjk = max { Fj

k-1, Vj(aj) } + —Lj

k

ϕj

– — = —–∂Vj

∂τ1

Σjϕj

– Vj(0) = 0

Pag. 21

Telematica


WFQ o PGPS• Molto complesso da realizzare• Valgono le stesse proprietà del GPS

– WFQ è in grado di emulare un sistema ideale con uno scarto di al massimo un pacchetto!

• Modifica per migliorare similitudine con GPS (WF2Q):– Si sceglie il pacchetto con tag minore, ma solo

tra quelli che nel sistema ideale GPS sarebbero in servizio in quell’istante


SCFQ (Self Clocked Fair Queueing)

• Approssimazione di PGPS• Non richiede emulazione sistema GPS• Usa un “tempo virtuale” semplificato

– tempo virtuale è sempre uguale alla tag del pacchetto in corso di trasmissione

Pag. 22

Telematica


RB

∑=

+⋅+ n

i iCP

RPnB

1

maxmax

∑=

+⋅+ n

i iCP

RPnB

1

maxmax

∑=

⋅+⋅+ n

i i

i

CPk

RPnB

1

maxmax

• Ci rate di uscita dell’i-esimo switch

• ki numero di flussi• Pmax dimensione massime dei pacchetti

Garanzie di ritardo• Calcolabili per flussi limitati da token bucket (R,B)• Garanzie indipendenti da comportamento di altri flussi• Ritardo massimo attraverso una serie di n scheduler

(esclusi i ritardi fissi):– GPS

– WFQ / PGPS

– Virtual Clock

– SCFQ


Algoritmi non work-conserving• Throughput inferiori• Ritardi medi maggiori ma maggiore controllo

sulla variabilità dei ritardi

STOP&GO

Ki

Ki

Ki pacchetti per flusso i

Pag. 23

Telematica


Bibliografia• H. Zhang, “Service Disciplines for Guaranteed Performance

Service in Packet-Switching Networks”, Proc. IEEE, vol. 83, Oct. 1995, pp.1374-96

• A. Varma, D. Stiliadis, “Hardware Implementations of Fair Queueing Algorithms for Asynchronous Transfer Mode Networks”, IEEE Communications Magazine, Dec. 1997, pp. 54-68

• A. Parekh, R. Gallager, “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: the Single Node Case”, IEEE/ACM Trans. On Networking, vol. 1, no.3, June 1993

Tecniche di schedulazione - telematica.polito.it · – FIFO, processor sharing, round robin,...

Documents

Transcript of Tecniche di schedulazione - telematica.polito.it · – FIFO, processor sharing, round robin,...