Scheduling Capitolo3

(1)

Capitolo 3

Scheduling

Attualmente Internet è basato sul protocollo IP (Internet Protocol) e sup-porta solo servizi di tipo best effort. Una pura rete best effort, in cui si cerchi semplicemente di far in modo che l’accesso alle risorse sia il più possi-bile fair (letteralmente “leale”), risulta inadeguata per soddisfare le esigenze di applicazioni con limitazioni stringenti sul ritardo end to end o sul delay

jitter. I principali problemi di gestione di una rete in cui si voglia

differen-ziare il servizio sono legati all’allocazione delle risorse (buffer e banda). Una quantità limitata di risorse deve essere condivisa tra diversi flussi di traffico in modo da realizzare un buon compromesso tra due esigenze contrastanti: buone prestazioni per i flussi ed elevata utilizzazione.

Uno dei motivi per cui le reti a commutazione di pacchetto sono state introdotte come alternativa a quelle a commutazione di circuito è stato pro-prio per risolvere il problema legato allo spreco di risorse derivante dalla non efficiente utilizzazione della banda. L’inefficienza deriva da un’allocazione delle risorse in termini di rate di picco, che per traffico dati o real time pu`o essere molto maggiore del rate medio.

(2)

Il principio chiave per un’allocazione pi`u eﬃciente consiste nel multiplex statistico (statistical multiplexing), le cui prestazioni possono per`o essere degradate da fenomeni di congestione, rendendo quindi necessario un mec-canismo di controllo del servizio oﬀerto alle diverse connessioni in tutti gli

switch o router1 lungo il percorso della comunicazione.

Il diﬀondersi dunque di applicazioni multimediali (video on demand,

videoconferencing) accanto alle classiche applicazioni di trasferimento dati (ftp, email) ha posto la forte esigenza di realizzare meccanismi di controllo

che permettano di soddisfare richieste eterogenee di QoS pur mantenendo un elevato livello di utilizzazione delle risorse.

I meccanismi di controllo possono in generale dividersi in due categorie [4]:

open loop: richiede che ogni applicazione speciﬁchi le caratteristiche del suo

traﬃco in una fase di set up della connessione.

closed loop: le applicazioni degli end point sondano lo stato della rete e

regolano il traffico di conseguenza, si tratta cioè di un sistema di con-trollo in feedback (es. window flow control ). E quello che fanno le` applicazioni che nel capitolo precedente sono state definite adattative.

Per diﬀerenziare il servizio `e necessario controllare le azioni compiute dai

router sui pacchetti dei diversi ﬂussi, meccanismi fondamentali [30] in tal

senso sono: la classificazione dei pacchetti, le tecniche di admission control e sagomatura del traffico, le discipline di scheduling e accodamento, le tecniche di scarto. Si veda la fig. 3.1

1_{In letteratura si usa il termine switch in riferimento alle reti ATM e il termine router} nel contesto di reti IP.

(3)

3.1 Caratteristiche generali degli algoritmi di scheduling 73 Scheduler Policer/ Shaper Classifier Link d’uscita

Figura 3.1: Funzioni di classiﬁcazione e scheduling

3.1 Caratteristiche generali degli algoritmi di

sche-duling

La funzione di uno scheduler è quella di selezionare, per ogni link d’usci-ta, sulla base di una precedente classificazione, il pacchetto che di volta in volta deve essere trasmesso. L’algoritmo di scheduling rappresenta dunque uno degli elementi chiave per la gestione della QoS in quanto consente di differenziare il servizio offerto a pacchetti appartenenti a classi di servizio diverse.

In generale gli scheduler possono essere distinti in due categorie:

work conserving: se il server non `e mai idle (letteralmente “silenzioso”)

quando almeno un pacchetto `e immagazzinato nel sistema. Ne sono alcuni esempi il GPS, il WFQ o PGPS e il DRR.

non work conserving: se il server pu`o rimanere idle anche nel caso in

cui ci siano pacchetti pronti ad essere trasmessi. Ritardare alcuni pacchetti pu`o infatti rivelarsi utile per ridurre il delay jitter.

(4)

Una diversa classiﬁcazione pu`o essere data in riferimento alla strut-tura interna degli scheduler, in base alla quale si possono distingure due architetture principali:

sorted priority: viene tenuta una variabile globale, solitamente riferita

come virtual time per ogni link d’uscita del nodo. Tale variabile viene aggiornata ogni volta che un pacchetto arriva o viene servito. Per ogni pacchetto viene calcolato in funzione del virtual time un timestamp in base al quale i pacchetti vengono ordinati e trasmessi.

frame based: l’asse temporale viene suddiviso in frame2 che possono

es-sere di lunghezza fissa o variabile. Ad ogni flusso viene associata una quantità massima di dati che pu`o trasmettere durante ciascun frame in modo da limitare la banda ad esso assegnata. Nel caso di frame con lunghezza fissa lo scheduler sarà di tipo non work conserving. Se invece la dimensione del frame pu`o variare fino ad un valore massimo, quando un flusso non ha traffico da trasmettere il frame successivo inizia in anticipo e il meccanismo risulta work conserving.

Nelle due classiﬁcazioni sopra riportate non si tiene conto delle esigenze delle applicazioni, ma solo dei principi di funzionamento degli algoritmi. In generale per un qualunque algoritmo di scheduling deve poter soddisfare i seguenti requisiti:

Divisione il più possibile fair della banda; quando una risorsa viene contesa è fondamentale che essa venga allocata nel modo pi`u fair possi-2_{E bene puntualizzare, per evitare ambiguit`}` _{a, che nell’ambito dello scheduling si usa} il termine frame in riferimento agli intervalli temporali che definiscono la granularit`a dello scheduler, da non confondersi dunque con il concetto di trama dei protocolli di comunicazione.

(5)

3.1 Caratteristiche generali degli algoritmi di scheduling 75

bile evitando che sorgenti “scorrette” (ill-behaved) possano in qualche modo penalizzare quelle “corrette” (well-behaved).

Basso ritardo end-to-end; in generale ci`o si riﬂette anche in una minore

richiesta di buﬀer per garantire l’assenza di perdite.

Buon isolamento tra i ﬂussi; l’algoritmo deve essere in grado di isolare

il traffico di un’applicazione da eventuali effetti indesiderati dovuti all’interazione con altri flussi e di mantenere le garanzie di QoS per un dato flusso anche in presenza di flussi con un comportamento scorretto

(misbehaving).

Elevato coeﬃciente di utilizzazione della banda; l’algoritmo deve

cer-care di trarre il massimo vantaggio dal multiplex statistico e deve essere in grado di gestire eﬃcientemente sorgenti molto bursty3.

Semplicit`a d’implementazione, in modo che sia facilmente realizzabile

in hardware quando si opera a velocit`a molto elevate, oppure che un’e-ventuale implementazione software, quando le velocit`a lo permettono, sia comunque tale da garantire che le decisioni di scheduling vengano prese in un tempo prossimo a quello d’interarrivo dei pacchetti.

Scalabilit`a; l’algoritmo deve essere in grado di gestire adeguatamente

un elevato numero di connessioni e link che spaziano su un elevato

range di velocit`a.

Sulla base delle caratteristiche sopra elencate `e possibile deﬁnire tre gran-dezze, di seguito analizzate, che permettono di valutare e confrontare le

(6)

stazioni dei diversi algoritmi di scheduling : le garanzie di ritardo end to end, la complessit`a e la fairness.

Garanzie sul ritardo end to end

`

E fondamentale che un algoritmo di scheduling permetta di fornire a ciascun flusso determinate garanzie sul ritardo end to end, senza per`o determinare una sotto-utilizzazione delle risorse. In particolare è auspicabile che il ritar-do sperimentato da un certo flusso sia insensibile al comportamento degli altri flussi, ovvero che i bound sul ritardo siano indipendenti dal numero di flussi che condividono un link. Il grado con cui ci`o si verifica dà una misura del livello di isolamento che l’algoritmo è capace di garantire ed è partico-larmente importante quando un nodo deve trattare un elevato numero di flussi.

Complessit`a di implementazione

La complessità di un algoritmo è un parametro di cui si deve tener conto per valutarne la scalabilità. Nelle reti ad elevata velocità può essere neces-saria una implementazione hardware degli algoritmi di scheduling, per cui una complessità contenuta è essenziale. A tal proposito è necessario distin-guere tra quella che è la complessità computazionale legata al calcolo di un

timestamp che definisce l’ordine di servizio, da quella che `e la complessità temporale necessaria per il servizio stesso, ovvero legata al tempo di acco-damento e disaccoacco-damento dei pacchetti. In particolare è desiderabile che ques’ultima sia indipendente dal numero di connessioni attive.

(7)

condividere un link, uno scheduler sorted-priority richiede fondamentalmen-te tre passi:

1. il calcolo del timestamp, che nel caso peggiore, come accade per un

PGPS, pu`o avere una complessit`a O(V );

2. l’accodamento (enqueuing) di un pacchetto tramite l’inserimento in una lista sorted priority;

3. l’operazione di disaccodamento (dequeuing) mediante la selezione del pacchetto con timestamp minimo.

Le operazioni di enqueuing e dequeuing di un pacchetto in un nodo pos-sono essere entrambe di complessit`a O(log V ). Shreedhar e Varghese in [10] hanno dato il nome di work dell’algoritmo alla massima tra le due com-plessit`a e hanno assunto tale parametro come una misura della complessit`a temporale di un algoritmo di accodamento.

3.1.1 Fairness

Un’attenzione particolare merita il concetto di fairness, che sebbene risulti abbastanza intuitivo, non è altrettanto semplice da definire in modo rigoroso. In generale è desiderabile che un sistema serva i flussi in maniera propor-zionale a quelle che sono le porzioni di banda loro riservate e che la la banda in eccesso, lasciata inutilizzata da eventuali traffici idle, venga distribuita tra i flussi attivi in proporzione ai loro rispettivi pesi. Sembrerebbe inoltre opportuno che un traffico non venga penalizzato per l’eventuale porzione di banda aggiunta che ha ricevuto mentre altri flussi erano idle. `E da notare comunque che nel caso di flussi pacchettizzati una certa unfairness sul breve

(8)

termine è inevitabile, perché comunque in un sistema reale ogni pacchetto dovrà essere servito singolarmente.

Vale la pena osservare che, anche nel caso in cui non si voglia differen-ziare il servizio offerto ai vari flussi, un semplice meccanismo a livello di

router che cerchi di garantire un accesso fair ai traﬃci provenienti da link

diversi può rivelarsi inefficace. Infatti assegnare la banda solo sulla base del link d’ingresso pu`o dare origine ad un fenomeno noto come problema del parking lot [10], per analogia con la situazione che si pu`o determinare in un parcheggio affollato e con una sola uscita: la porzione di banda al-locata ad un dato flusso può decrescere esponenzialmente con il numero di nodi attraversati (fig. 3.2). Anche nel caso in cui non si voglia diversificare il trattamento riservato ai vari flussi è comunque opportuno identificarli e trattarli separatamente piuttosto che fare riferimento alla topologia.

f1 f2 f3

Na Nb Nc

Figura 3.2: ﬁgura parking lot

Una soluzione approssimativa di tale problema, proposta da Nagle [31], prevede di discriminare i vari ﬂussi e quindi servirli in modalit`a round robin per ogni link d’uscita. Ci`o risolve anche il problema, tipico degli scenari con disciplina FIFO e meccanismi di controllo della congestione di tipo source

based, per cui una sorgente scorretta possa incrementare arbitrariamente la

sua banda. Se le code d’uscita sono separate ciascun ﬂusso incrementa solo la propria coda, senza incidere su quelle degli altri ﬂussi. Il problema del

(9)

semplice round robin tra i ﬂussi `e che esso ignora le lunghezze dei pacchetti, quindi in generale non risulter`a fair.

Detto n il numero di flussi che si contendono un link d’uscita, Shreedar e Varghese in [10] definiscono un indice di fairness in condizioni di traffico

heavy (pesante), cio`e nell’ipotesi che ciascuno degli n ﬂussi produca una sequenza continua di pacchetti di dimensione arbitraria.

Supponendo di cominciare ad inviare pacchetti all’istante zero, si indichi con senti,t il numero di byte inviati dal ﬂusso i ﬁno all’istante t e con sentt

il numero totale di byte inviati dagli n flussi fino allo stesso istante t. Si definisce “quoziente di fairness” la quantità:

F Qi= max( lim_t→∞senti,t

sentt )

dove il max `e preso tra tutte le possibili distribuzioni delle dimensioni dei pacchetti per i flussi d’ingresso, ciò significa che esprime la frazione di servizio ricevuta dal flusso i nel cosiddetto worst case.

Detta fi la porzione ideale di banda che si vorrebbe assegnare al ﬂusso i il “quoziente di fairness” ideale sarebbe

fi

_n

j=1fj.

Il rapporto tra l’indice di fairness reale e quello ideale di un ﬂusso i esprime di quanto l’implementazione pratica si discosti dal comportamento ideale:

F airnessIndexi= F Qi·

_n

j=1fj

fi (3.1)

Ovviamente per un algoritmo perfettamente fair tale rapporto sar`a pari a uno.

(10)

Un altro modo per misurare la fairness di un algoritmo di scheduling viene proposto da Golestani in [8] per analizzare la disciplina (SCFQ) Self

Clocked Fair Queueing e si basa sulla diﬀerenza di servizio normalizzato

oﬀerto a due qualunque connessioni in un qualsiasi intervallo di tempo in cui abbiano backlog.

Ricordando la notazione introdotta a proposito dei server LR (par. 2.3) si definisce con W_iS(τ, t)/ρi il servizio normalizzato offerto al flusso i

du-rante l’intervallo (τ, t]. Si dice che uno scheduler è perfettamente fair se la differenza tra il servizio normalizzato offerto a due qualunque flussi i, j che abbiano continuamente backlog durante l’intervallo (τ, t] è nulla; ossia, in formule, se vale la seguente:

⏐ ⏐ ⏐WiS(τ, t) ρi − W_jS(τ, t) ρj ⏐ ⏐ ⏐ = 0 (3.2)

Tale equazione non può comunque essere verificata da alcun algoritmo che operi a livello di pacchetto in quanto, come già osservato, in un sistema reale ogni pacchetto deve essere servito singolarmente. Una condizione che può essere imposta nel caso di sistemi che operino su flussi pacchettizzati `e che la differenza tra i servizi normalizzati ricevuti da due flussi i, j su un qualunque intervallo (τ, t] in cui essi abbiano continuamente backlog sia limitata da una costante:

⏐ ⏐ ⏐WiS(τ, t) ρi − W_jS(τ, t) ρj ⏐ ⏐ ⏐ ≤ FS (3.3)

dove FS `e appunto una costante, dipendente dall’algoritmo di scheduling, detta fairness del server S. Chiaramente quanto minore sar`a il valore di tale costante tanto pi`u fair risulter`a l’algoritmo preso in considerazione.

Dalla definizione di FS emerge subito una difficoltà legata al confron-to della fairness di algoritmi diversi per i quali, come gi`a sottolineato nel

(11)

capitolo precedente, i periodi di backlog possono essere differenti anche in corrispondenza di uno stesso flusso. Un modo per operare comunque un paragone consiste nel far riferimento a condizioni di traffico pesante per cui qualunque sia l’algoritmo di scheduling i flussi abbiano continuamente

backlog.

La misura della fairness definita da FS, che fa riferimento alla differenza di servizio normalizzato ricevuto da due flussi in uno stesso scheduler, `e anche nota come Relative Fairness Bound (RFB) in contrapposizione a quella che va sotto il nome di Absolute Fairness Bound (AFB), definita come il limite superiore della differenza tra il servizio ricevuto da un flusso nello scheduler che si vuole analizzare e il servizio che riceverebbe in uno scheduler ideale

GPS.

Quello deﬁnito dall’equazione (3.1), calcolato come lim_t→∞, pu`o essere considerato un indice di fairness assoluto sul lungo termine, ma in genera-le il parametro AFB deve costituire un bound su un qualunque intervallo temporale.

La grandezza definita da AFB viene solitamente ritenuta pi`u accurata di quella definita da RFB, ma purtroppo spesso risulta pi`u difficile da valuta-re. In [32] viene dimostrato che per una qualunque disciplina di scheduling di tipo work conserving esiste una relazione tra le due, in particolare AFB pu`o essere limitato sia inferiormente che superiormente in funzione di RFB. Inoltre il limite superiore risulta essere tight per molte discipline di

sche-duling reali tra cui WFQ e DRR. Dalla forma dei bound (vedi Teorema 1

in [32]) segue anche che per siﬀatte discipline, per cui il bound superiore `e

tight, le due misure (AFB e RFB ) si avvicinano l’una all’altra al crescere

(12)

una buona misura della fairness.

Quella relativa alla deﬁnizione di una misura soddisfacente della

fair-ness sembra comunque essere una questione ancora aperta. Un diﬀerente

approccio per la valutazione della fairness istantanea viene proposto in [33], in cui gli autori prendono in prestito e adattano ai propri scopi una tecnica di valutazione delle disuguaglianze che si basa sui concetti di Lorenz curve e Gini index [34]. Una delle peculiariat`a notevoli di quest’ultima rispetto alle definizioni precedenti è quella di essere significativa anche in presenza di flussi idle.

3.2 Discipline di scheduling

`

E chiaramente impossibile trovare una disciplina di scheduling che soddisﬁ contemporaneamente i criteri di ottimalit`a di fairness, complessit`a e pre-stazioni. In gnerale sar`a necessario scendere a compromessi. Di seguito si discutono le caratteristiche di alcune politiche di scheduling proposte in letteratura.

3.2.1 FCFS

La disciplina pi`u ampiamente implementata nei tradizionali router IP `e la FCFS (First Come First Served) o FIFO (First In First Out), spesso associata con una politica di scarto di tipo tail drop (ﬁg. 3.3) [35]. Si tratta di una disciplina work conserving ed `e la pi`u semplice tra quelle di tipo

sorted priority: il timestamp che determina l’ordine di servizio dei pacchetti

(13)

3.2 Discipline di scheduling 83 Flusso 5 Flusso 4 Dropped Multiplexer Link d’uscita Flusso 1 Flusso 2 Flusso 3

Figura 3.3: Disciplina FIFO con tail drop

Il grande pregio della disciplina FCFS `e la sua semplicità implementati-va, mentre il suo grosso difetto consiste nell’impossibilità di isolare i diversi flussi di traffico. Ciò significa che un eventuale aumento del ritardo di ac-codamento causato dalla presenza di un flusso con traffico molto bursty si ripercuote indistintamente anche sugli altri flussi che condividono la stessa coda, impedendo il calcolo di un qualunque bound deterministico, in termini di ritardo end to end o di delay jitter, che risulti indipendente dallo stato della rete e dalle caratteristichi dei flussi concorrenti. Da qui le difficoltà riscontrate anche nell’ambito del Network Calculus nel determinare bound significativi relativi a scenari con scheduling aggregato.

Un altro problema che può originarsi dall’utilizzo di una semplice tec-nica FIFO è una situazione di estrema unfairness nel caso in cui la coda sia condivisa da flussi di applicazioni congestion-responsive (sensibili alla congestione), quali possono essere quelle che usano il protocollo di traspor-to TCP (Transmission Control Protraspor-tocol) e flussi di applicazioni che non lo

(14)

siano, basate ad esempio sul protocollo UDP(User Datagram Protocol). Poi-ch´e nei router non viene eﬀettuato nessun controllo sui ﬂussi, applicazioni che non implementino alcun tipo di meccanismo di controllo della conge-stione sono in grado di impadronirsi di una frazione arbitraria della banda a disposizione.

Il pi`u semplice meccanismo di scheduling diverso da FCFS e che per-metta di fornire una qualche diﬀerenziazione del servizio `e costituito dal

Priority Queuing (PQ). L’idea `e quella di implementare più code FIFO, cia-scuna associata ad una classe di servizio con un diverso livello di priorità. Il principale svantaggio di un tale approccio consiste nella possibilità che i flussi a priorità pi`u alta esercitino un vero e proprio “monopolio” delle risor-se determinando quella che viene detta starvation (letteralmente “inedia”) dei flussi a bassa priorità.

`

E da notare anche che la tecnica PQ non risolve il problema legato all’interazione tra ﬂussi congestion-responsive e non che appartengano alla stessa classe di servizio.

3.2.2 Fair Queueing

La soluzione più semplice per isolare i flussi consiste nell’usare code separate e trasmettere un pacchetto di ciascuna coda in modalit`a round robin [31], nel qual caso si parla anche di Packet-Based Round Robin (PBRR). Ma un siffato procedimento risulta evidentemente inefficiente (unfair) nel caso in cui i pacchetti abbiano dimensione variabile.

Muovendo dalle precedenti considerazioni, in [7] viene proposta una pri-ma emulazione pratica di quello che sarebbe il meccanismo ideale, pri-ma pale-semente poco realistico: un bit by bit round robin. Solitamente le tecniche

(15)

3.2 Discipline di scheduling 85

che si basano su tale concetto vengono riferite come algoritmi Fair Queuing. Si pu`o dimostrare [36] che essi offrono un isolamento e una fairness quasi perfetti, ma purtroppo risultano essere estremamente complessi, determi-nando elevati costi implementativi e seri problemi di scalabilità. In parti-colare, se V è il numero di flussi contemporaneamente attivi, la complessità dell’elaborazione richiesta per ogni pacchetto `e O(log(V )).

Flusso 1 Flusso 2 Flusso 3 Link d’uscita Robin Round

Figura 3.4: Fair queueing

3.2.3 Il modello GPS

Molte delle discipline di scheduling sviluppate negli ultimi anni prendono come riferimento il modello ideale GPS (Generalized Processor Sharing) deﬁnito da Parekh e Gallager [6, 23].

Si tratta di una disciplina di scheduling di tipo work conserving che garantisce l’isolamento tra i flussi e soddisfa il criterio di fairness max min [37], secondo il quale la condivisione di una risorsa tra più richiedenti con uguali diritti, ma differenti richieste, `e fair se [38]:

la risorsa `e allocata in ordine di domanda crescente;

nessuno dei richiedenti riceve una frazione della risorsa superiore a

(16)

i richiedenti con domande insoddisfatte ricevono frazioni uguali della risorsa. Flusso 3 Flusso 1 Flusso 2 Link d’uscita

Figura 3.5: Schema ideale del GPS

Il GPS `e definito in relazione ad un modello fluido in cui i pacchetti vengono considerati infinitamente divisibili. La porzione di banda riservata al flusso i è proporzionale ad un peso φi. Se r è il rate totale d’uscita

dal nodo, in un qualunque istante t l’algoritmo garantisce ad un ﬂusso i, che abbia backlog, un rate istantaneo pari a P φi

j∈B(t)φjr. I ﬂussi vengono

idealmente serviti in parallelo proporzionalmente al loro peso (ﬁg. 3.5). Se si indica con J(t) l’insieme dei ﬂussi che hanno backlog all’istante t, preso

i ∈ J(t), la funzione cumulativa in uscita del ﬂusso i sar`a: R∗_i(t) = _t 0 φi j∈B(s)φjr · 1{i∈B(s)}ds

Detto V il numero massimo di flussi che un server può servire, dalla definizione stessa segue che l’algoritmo GPS offre al flusso una strict service

curve e quindi anche una curva di servizio β = λri con ri = PφVi

j φjr in

quanto il rate minimo garantito ad un flusso i è quello che si ha quando tutti i flussi hanno backlog. La banda in eccesso, resa disponibile da flussi che lasciano inutilizzata la porzione ad essi riservata, viene ridistribuita tra quelli che hanno backlog in maniera proporzionale al loro peso. Ci`o porta ad un perfetto isolamento, una fairness ideale e basso ritardo end-to-end.

(17)

Data la natura teorica del concetto di GPS, esso non risulta praticamen-te implementabile, ma si dimostra comunque utile perch´e, oltre che come modello di riferimento, viene spesso assunto come termine di paragone per valutare le prestazioni di algoritmi reali, come gi`a osservato parlando di AFB

(Absolute Fairness Bound).

L’idea pi`u ovvia per una possibile emulazione dell’algoritmo consiste nel calcolare i virtual ﬁnish time e inviare i pacchetti in uscita solo in tali istanti, ma ne deriva uno scheduler non work conserving [5].

Probabilmente la pi`u nota implementazione pratica `e costituita dal PGPS

(Packet by packet Generalized Processor Sharing) o WFQ (Weighted Fair Queuing). Un dispositivo di rete, ovviamente, elabora un pacchetto per

vol-ta trasmettendolo con un rate r pari a quello del link d’uscivol-ta. Il WFQ prevede che per ogni pacchetto debba essere calcolato il virtual time come l’ipotetico finish time che avrebbe in un GPS. Ogni volta che si finisce di trasmettere un pacchetto si inizia a trasmetterne un altro, quello con finish

time minore, in modo che lo scheduler risulti work conserving.

Bennett e Zhang in [9] hanno dimostrato che le discrepanze relative al ritardo e alla fairness tra gli algoritmi WFQ e GPS sono maggiori di quanto si potesse immaginare, a partire da tale risultato hanno quindi proposto un algoritmo detto WF₂Q (Worst-Case Fair Weighted Fair Queueing) che in

ultima analisi, lavorando a livello di pacchetto, `e quanto di meglio si possa ottenere per la fairness [38].

La differenza tra il finish time reale del PGPS e quello ideale del GPS `e quantificabile nel termine L/r, dove L è la dimensione massima dei pacchetti (Proposizione 2.1.1 in [5]).

(18)

A fronte delle buone propriet`a di fairness e d’isolamento, l’algoritmo ha una complessit`a O(V ), il che rende i costi proibitivi e pone grossi problemi di scalabilità. Una alternativa proposta per ridurre la complessit`a del WFQ `e costituita dal SCFQ (Self Clock Fair Queuing) [8], ma sebbene la complessit`a venga enormemente ridotta il prezzo da pagare è un più basso livello di isolamento [4].

3.2.4 Algoritmo SCED

`

E chiaramente impossibile dare un elenco esaustivo delle innumerevoli di-scipline di scheduling proposte per conseguire una gestione eﬃciente della

QoS in Internet, ma vale la pena in questa sede accennare al principio di

funzionamento di una politica di scheduling, proposta da Cruz [39, 40], che si basa sul concetto di curva di servizio e perci`o intrinsecamente legata alla teoria del network calculus.

L’algoritmo in questione va sotto il nome di SCED (Service Curve based

Earliest Deadline ﬁrst) e rappresenta una generalizzazione4 del concetto di

EDF (Earliest Deadline First).

Come già più volte osservato, la maggior parte delle applicazioni multi-mediali `e soggetta a limitazioni sul massimo ritardo end to end, d’altra parte numerose politiche di gestione delle risorse proposte in letteratura (tra cui anche WFQ e DRR) si basano sull’allocazione di un dato rate (e quindi una certa banda) a ciascun flusso. Sebbene le garanzie sulla banda comportino, a patto che il traffico inviato in rete venga opportunamente limitato, anche determinate garanzie sul ritardo, un tale approccio può portare ad una so-4_{Anche l’algoritmo VC (Virtual Clock) si pu`}_{o ricondurre allo SCED come caso} particolare.

(19)

vrallocazione delle risorse, soprattutto nel caso in cui il traﬃco sia molto

bursty. Per un’allocazione delle risorse pi`u eﬃciente sarebbe quindi oppor-tuno progettare discipline di scheduling in grado di disaccoppiare i due ter-mini e massimizzare il numero di traﬃci che possono essere simultaneamente serviti.

Anzich´e caratterizzare il servizio ricevuto da ciascun ﬂusso soltanto in relazione al minimo rate oppure al massimo ritardo garantito, la politica

SCED si propone di usare il concetto pi`u generale di curva di servizio. Ciò farà s`ı che l’allocazione delle risorse si riveli molto più flessibile e la regione di schedulabilità5, per un singolo server, risulti massimizzata una volta fis-sate le specifiche sul ritardo massimo ammissibile e la burstiness (le curve d’arrivo) del traffico. La chiave vincente deriva dalla possibilità di allocare curve di servizio di forma arbitraria.

L’algoritmo SCED pu`o essere visto come una tecnica per deﬁnire le

deadline dei pacchetti di un ﬂusso in modo che al ﬂusso venga garantita una

curva di servizio minima βi, detta target service curve e tale da soddisfare

le limitazioni sul ritardo end to end imposte dall’applicazione che genera il flusso stesso. Per un flusso non pacchettizzato ciò può essere formalmente espresso nel modo seguente:

Definizione 3.2.1 (SCED) Si indichi con an_i l’istante d’arrivo dell’n-esimo pacchetto del flusso i e si definisca la funzione

Rn_i(t) inf

s∈[0,an

i]

{Ri(s) + βi(t − s)}.

5_{Per schedulabilit`}_{a si intende la condizione che un insieme di ﬂussi deve soddisfare} perch´e possano essere serviti tutti contemporaneamente e nel rispetto delle garanzie di servizio richieste.

(20)

La deadline per il pacchetto n-esimo `e deﬁnita dalla pseudo-inversa della funzione Rn_i secondo la seguente:

Dn_i = (Rn_i)−1(n) = min{t ∈ N : Rn_i(t) ≥ n} (3.4) La funzione Rn_i `e deﬁnita in maniera analoga alla convoluzione min-plus, ma il fatto che venga calcolata solo sugli istanti temporali ﬁno all’arrivo dell’n-esimo pacchetto consente all’algoritmo di essere implementato in real

time.

Dato uno scheduler che implementi una disciplina SCED, detto V il nu-mero di flussi che pu`o servire e C il rate totale d’uscita, la sua schedulabilità, nel caso di flussi non pacchettizzati, può essere espressa nel seguente modo (Teorema 2.3.1 in [5]): se ciascun flusso i è limitato da una curva d’arrivo

αi e inoltre vale V

i=1

(αi⊗ βi)(t) ≤ Ct per ogni t ≥ 0 (3.5)

allora tutti i pacchetti vengono serviti prima della propria deadline e il ﬂusso

i riceve βi come curva di servizio6.

Nel caso in cui non si possano fare assunzioni sulle caratteristiche del traffico, si può ricorrere a una più semplice condizione sufficiente di schedu-labilit`a, che si basa solo sulle target service curve βi secondo la seguente:

V

i=1

βi(t) ≤ Ct per ogni t ≥ 0 (3.6)

con le stesse implicazioni dell’equazione (3.5).

Dalle propriet`a della convoluzione, per cui se α(0) = 0 vale (α ⊗ β)(t) ≤

β(t), si deduce che conoscere le curve d’arrivo dei ﬂussi in ingresso

permet-te di ampliare la regione di schedulabilit`a. Infatti una curva d’arrivo pu`o 6_{con la notazione}_{x si intende la parte intera di x.}

(21)

sempre essere ricondotta alla sua chiusura subadditiva, quindi non `e una limitazione assumere αi(0) = 0 e in generale sar`a:

V i=1 (αi⊗ βi)(t) ≤ V i=1 βi(t) .

La deﬁnizione dello SCED si estende per i ﬂussi pacchettizzati come segue:

Definizione 3.2.2 (Packet SCED) Detto an_i l’istante d’arrivo dell’n-esimo pacchetto del flusso i e definita la funzione

Rn_i(t) inf

s∈[0,an

i]

{Ri(s) + βi(t − s)}

uno scheduler PSCED `e un scheduler EDF non preemptive per cui la

deadline del pacchetto n-esimo `e deﬁnita da

Dn_i = (Rn_i)−1(Li(n)) = min{t ∈ N : Rin(t) ≥ (Li(n))} (3.7)

dove Li(n) è la lunghezza cumulativa dei pacchetti del flusso i fino al

pac-chetto n-esimo. Chiaramente gli effetti della pacchettizzazione si riflettono anche sulle condizioni di schedulabilità (vedi proposizione 2.3.3 in [5]).

Per un algoritmo come il GPS, che si basa sull’allocazione di un rate ρi

per ogni flusso i, la condizione di schedulabilità è banalmente V_i=1ρi≤ C.

La differenza fondamentale tra strategie di scheduling basate sull’alloca-zione di un rate e quelle delay based consiste nel fatto che per le prime la condizione di schedulabilità `e imposta sulla somma dei rate allocati, indi-pendentemente dal traffico d’ingresso, mentre per le altre si deve imporre una condizione sulle curve d’arrivo. In ogni caso, comunque, per calcolare il bound end-to-end sul ritardo `e necessario conoscere le curve d’arrivo dei flussi.

(22)

`

E intuitivo che se un insieme di ﬂussi `e schedulabile per un qualche algoritmo di calcolo della deadline, lo sar`a anche per un qualunque altro che produca deadline maggiori o uguali.

L’aspetto negativo degli algoritmi che prevedono il calcolo di una

dead-line consiste nel fatto che, tranne alcuni casi particolari [39], in generale

presentano una elevata complessit`a.

Le propriet`a dello SCED possono anche essere sfruttate in combinazione con un elemento di rete, detto damper, il cui scopo `e quello di rallentare il flusso di un traffico al fine di limitare il delay jitter end to end e sfruttare i vantaggi dello statistical multiplex per migliorare il servizio offerto ai flus-si a bassa priorit`a [39]. Il damper pu`o essere visto come una tecnica per implementare una maximum service curve [40].

3.3 Deﬁcit Round Robin

Lo schema pi`u generale di algoritmo round robin appartiene alla classe di

scheduler frame based con dimensione del frame F ﬁssa. I diversi ﬂussi

vengono serviti a turno (round robin), a ciascuno di essi viene assegnato un

credit counter (contatore di crediti) o quantum che viene decrementato, ogni

volta che un pacchetto viene trasmesso, di una quantità pari alla dimensione del pacchetto stesso. Un flusso non può trasmettere alcunch´e se il suo credit

counter `e nullo.

All’inizio di ciascun frame i valori dei credit counter vengono reimpostati alla massima quantità di dati che ciascun flusso pu`o trasmettere nel frame stesso. La mole di lavoro richiesta per la trasmissione di un pacchetto in uno scheduler con disciplina frame based è tipicamente O(1), almeno nel

(23)

3.3 Deﬁcit Round Robin 93

caso in cui il quantum associato a ciascun flusso sia maggiore della massima dimensione dei pacchetti. L’estrema semplicità dell’algoritmo fa s`ı che pos-sa essere facilmente implementato in hardware per applicazioni ad elevata velocità.

Il principale difetto degli algoritmi frame based risiede nel fatto che il ritardo massimo con cui un flusso inizia il servizio (quello a volte indicato con il nome di Start Up Latency [38]) è proporzionale alla lunghezza del frame. Poiché in generale `e richiesta una lunghezza del frame tanto maggiore quanto più si desidera allocare la banda in maniera fine, ciò risulterà in elevati ritardi

end to end.

Il puro e semplice round robin risulta inadeguato nei casi in cui le dimen-sioni dei pacchetti siano variabili. Se size_max e size_min sono rispettivamente la dimensione massima e minima, nel worst case un ﬂusso pu`o ricevere una banda pari ad una frazione sizemin

sizemax rispetto a quella di un altro. Poich´e pra-ticamente non `e possibile interallacciare i bit di pacchetti diversi in modo da realizzare un bit by bit round robin, `e necessario individuare un procedi-mento che permetta di migliorare la fairness pur continuando a lavorare a livello di pacchetto.

Il modo migliore per farlo dal punto di vista della fairness consiste nel mantenere una coda di pacchetti ordinati in base agli istanti di partenza teorici che avrebbero in un bit by bit round robin. Purtroppo il miglior algo-ritmo possibile per una tale operazione ha una complessit`a pari a O(log(V )), dove V è il numero massimo di flussi che si può avere.

Parekh e Gallager [6] hanno dimostrato che una disciplina di tipo FQ in combinazione con una tecnica di shaping di tipo leaky bucket permette anche di fornire garanzie deterministiche sul ritardo, il che signiﬁca che un

(24)

algoritmo fair queueing fornisce qualcosa in pi`u che il semplice isolamento tra flussi. Purtroppo nessuna soluzione viene prospettata per la complessità. Il round robin ordinario può essere eseguito in un “tempo costante”, ma come gi`a osservato si rivela unfair quando i pacchetti non hanno tutti le stesse dimensioni. Il Deficit Round Robin permette di eliminare tale difetto continuando a richiedere un tempo di esecuzione costante. Il problema viene risolto introducendo una variabile di stato, detta Deficit Counter, che tiene conto del servizio effettivamente ricevuto da ciascun flusso. Da qui il nome dato all’algoritmo, ottenuto dal classico round robin con una semplice mo-difica. Il grosso vantaggio consiste nell’ottenere una fairness soddisfacente in termini di throughput pur mantenendo una complessit`a di elaborazione per pacchetto pari a O(1).

L’unica diﬀerenza con il tradizionale algoritmo round robin consiste nel fatto che se durante un round una coda risulta impedita ad inviare un pac-chetto perch´e il credit counter residuo `e inferiore alla sua dimensione, allora tale valore residuo viene assegnato al Deﬁcit Counter associato alla coda in questione e aggiunto al quantum del round7 successivo.

Pacchetti che arrivano da flussi diversi vengono accodati su code diver-se. Per ogni flusso i viene dunque specificata una quantità Quantumi che individua la banda ad esso assegnata e viene definita una variabile di stato

DeficitCounter_i che tiene conto del servizio effettivamente fornito a ciascu-na coda. Nel caso più semplice in cui a tutti i flussi sia riservata la stessa banda sar`a chiaramente Quantum_i = Quantum_j, dove i e j indicano due flussi qualsiasi.

(25)

3.4 Un modello LR per l’algoritmo DRR 95

Detto bytes_i,k il numero di byte della coda i trasmessi durante il round

k-esimo, deve valere per ogni coda e per ogni i, k bytesi,k< Quantumi. Per

evitare di esaminare le code vuote viene anche tenuta una lista dei flussi attivi (ActiveList), cio`e degli indici delle code che contengono almeno un pacchetto. Se alla fine del suo turno di servizio la coda associata al flusso i è vuota, il suo Deficit Counter viene posto a zero e il suo indice rimosso dalla lista dei flussi attivi, altrimenti DeficitCounter_i assume il valore Quantum_i−

bytes_i,k. Durante il round successivo la coda potr`a inviare una quantit`a di

byte pari a Quantum_i+ DeﬁcitCounter_i.

3.4 Un modello LR per l’algoritmo DRR

Come accennato nel capitolo precedente, il modello di server LR (Latency

Rate) permette di derivare generici bound deterministici sul ritardo end-to-end, la fairness, le esigenze di buﬀer e la burstiness in una rete.

Facendo uso del lemma 2.3.1 (pag. 55), Stiliadis in [4] dimostra che molti degli algoritmi di scheduling più conosciuti appartengono alla classe LR e in particolare anche il WFQ, che cosituisce una delle soluzioni migliori in termini di ritardo e fairness. I numerosi tentativi fatti per trovarne una implementazione efficiente hanno portato spesso a soluzioni che degradano le propriet`a di isolamento, incidendo sui delay bound, oppure non risolvono il problema della complessit`a (O(V ) per uno scheduler WFQ che serve V flussi).

Come sottolineato nel paragrafo precedente, il DRR sembra avere buone caratteristiche di fairness e complessit`a e per tale motivo si ritiene opportuno approfondirne l’analisi.

(26)

Inizializzazione dello scheduler

for (i = 0; i < n; i = i + 1)

DeﬁcitCounter_i = 0;

Modulo di accodamento (Enqueue):

viene invocato ogni volta che arriva un pacchetto p i = QueueInWhichPacketArrive(p);

if (ExistsInActiveList(i) == FALSE ) then

AddToActiveList(i); DeﬁcitCounter_i = 0 Enqueue(i,p);

Modulo di disaccodamento Dequeue:

cuore dell’algoritmo perch´e schedula i pacchetti

while (TRUE ) do

if Active List not empty then

i = HeadOfActiveList;

DeﬁcitCounter_i = Quantum_i+ DeﬁcitCounter_i;

while(DeﬁcitCounter_i ≥ 0)and Queue_i not empty do

PacketSize = Size(Head(Queue_i));

if (PacketSize ≤ DeﬁcitCounter_i) then Send(Dequeue(Queue_i))

DeﬁcitCounter_i = DeﬁcitCounter_i− PacketSize;

else break; (* loop *) if (Empty(Queue_i)) then

DeﬁcitCounter_i = 0; AddToActiveList(i);

Tabella 3.1: Pseudocodice relativo all’algoritmo DRR

Propriet`a dell’algoritmo DRR

Si enunciano di seguito alcune propriet`a [10] dell’algoritmo DRR che risulta-no utili al calcolo di un bound sulla latency per la deﬁnizione di un modello

(27)

Detta size_max la massima dimensione possibile dei pacchetti, dalla deﬁ-nizione stessa dell’algoritmo segue:

Lemma 3.4.1 Per ogni ﬂusso i e per una qualunque esecuzione

dell’algo-ritmo, al termine di un round DRR vale sempre:

0≤ DeﬁcitCounter_i < sizemax

Un secondo risultato importante è costituito dal fatto che la discrepanza tra l’allocazione di risorse idealmente desiderata per un dato flusso i e quella realmente ottenuta mediante un algoritmo DRR `e sempre limitata dal valore della dimesione massima (size_max) dei pacchetti, in particolare ciò sarà vero anche su intervalli temporali arbitrariamente piccoli.

Prima di enunciare formalmente la proprietà appena descritta conviene definire le seguenti quantità:

DeficitCounter_i,k, valore del DeficitCounter_i del il flusso i alla fine del

round k.

bytes_i,k, byte inviati dal ﬂusso i durante il round k.

sent_i,k, la somma dei byte inviati dal ﬂusso i nei round dall’1 al k. Chia-ramente sent_i,K=K_k=1bytes_i,k.

Teorema 3.4.1 (Fairness DRR) Si consideri un’esecuzione

dell’algorit-mo DRR durante la quale il ﬂusso i ha continuamente backlog8. Dopo K

round vale

0≤ K · Quantum_i− sent_i,K ≤ size_max. (3.8) 8_{Si ricorda che un ﬂusso}_{i si dice essere in un periodo di backlog se la sua coda non `e} mai vuota.

(28)

L’equazione può essere espressa dicendo che la differenza tra i byte che il flusso i avrebbe dovuto mandare e quelli che effettivamente ha mandato è limitata da sizemax.

Dal teorema appena enunciato segue facilmente che la massima diﬀe-renza tra i byte inviati da due ﬂussi (con lo stesso quantum) che abbiano continuamente backlog dopo un qualunque numero di round `e limitata da

size_max.

Si pu`o dimostrare che per il DRR in condizioni di traﬃco heavy risulta

FairnessIndex_i = 1 e inoltre che nel caso in cui Quantum_i ≥ size_max il work (vedi pag. 77) `e O(1).

Sulla base del lemma 2.3.1, che `e bene ribadire non fornisce necessaria-mente un bound tight per la latency, si pu`o dimostrare il seguente:

Lemma 3.4.2 Detto t0 l’inizio di un periodo di backlog per il ﬂusso i in un

server che opera secondo l’algoritmo Deﬁcit Round Robin, per ogni t > t0 appartenente al periodo di backlog vale

Wi(t0, t) ≥ max0, ρi(t − t0−3F − 2φ_r i) (3.9)

dove F è la dimensione del frame e φi il peso associato al flusso i, prati-camente φi = Quantumi. Se r è il rate totale del link d’uscita risulterà

ρi = φ_Fir.

Dal lemma appena enunciato e dal gi`a citato lemma 2.3.1 segue imme-diatamente il seguente:

Corollario 3.4.1 L’algoritmo Deﬁcit Round Robin appartiene alla classe

degli scheduler LR e la sua latency Θ_i soddisfa la seguente:

Θ_i ≤ 3F − 2φi

(29)

Per quanto dimostrato nel paragrafo 2.3.1 a pagina 52, la propriet`a del-l’algoritmo DRR di appartenere alla classe LR permette anche di aﬀermare che uno scheduler DRR soddisfa la seguente curva di servizio:

β(t) = βρi,Θi(t) = ρi[t −

3F − 2φi

r ]

+ _(3.11)

Questo risultato sar`a alla base delle veriﬁche simulative condotte nel-l’ambito del lavoro di tesi.

Si pu`o dimostrare che la disciplina DRR soddisfa l’equazione (3.3) che de-finisce il Relative Fairness Bound con un valore della costante FS = 3F/r. Si rimanda a [4] per una trattazione esaustiva e un confronto tra vari algoritmi. Come tutti gli algoritmi frame based, il DRR ha come effetto indeside-rato la proporzionalit`a della latency alla dimensione F del frame, che viene determinata dalla granularità con cui si vuole allocare la banda e dalla di-mensione massima Li dei pacchetti di ciascun flusso. Ciò significherà che la

latency di uno scheduler DRR `e anche funzione del numero V di ﬂussi che condividono il link d’uscita in quanto in generale V_i=1Li ≤ F. Tale

aspet-to rivela di fataspet-to una bassa capacit`a di isolamento dell’algoritmo ai ﬁni del ritardo. Con la terminologia del network calculus la relazione V_i=1Li ≤ F

può essere riferita come condizione di schedulabilità. È evidente se si pensa agli scheduler basati sul concetto di Earliest Deadline First (EDF), cui ap-partiene l’algoritmo SCED, che le condizioni di schedulabilit`a non risultano sempre cos`ı semplici.

Eﬀetti della pacchettizzazione sulla latency `

E stato precedentemente osservato che nel caso di ﬂussi pacchettizati soli-tamenete si assume che un pacchetto lasci un server come un impulso, si

(30)

considera cio`e che sia stato servito solo quando il suo ultimo bit lascia il

server. Ci`o `e necessario per definire gli arrivi nel nodo successivo di una catena di server, in in modo che anche l’arrivo di un pacchetto possa essere modellato come un impulso. Poiché infatti i dispositivi presi in considerazio-ne sono di tipo non cut through, un pacchetto pu`o essere servito solo dopo che il suo ultimo bit `e stato ricevuto. È immediato osservare che in tali casi la minima differenza tra il servizio Wi,j(τaj, t) fornito al flusso i durante l’intervallo (τaj, t] con τaj ≤ t ≤ τzj + Θi e la funzione ρi(t − τaj − Θi)+ che definisce i parametri del modello LR si raggiunge subito prima che un pacchetto del flusso i lasci il sistema.

bit t ρi Θ_i Θ_i− Li ρi R(t) R∗(t)

Figura 3.6: Eﬀetto del pacchettizzatore sulla latency

Ci`o significa di fatto che la latency viene calcolata in tali punti, ma quan-do si calcola il ritarquan-do end to end di un flusso in realt`a si è interessati solo a determinare l’istante in cui l’ultimo bit di un pacchetto lascia il server. Se ne deduce che per l’ultimo server della catena si può calcolare la latency facendo riferimento agli istanti immediatamente successivi a quelli in cui

(31)

3.4 Un modello LR per l’algoritmo DRR 101

un pacchetto viene servito. L’eﬀetto sar`a una riduzione della latency per il sistema risultante e quindi un bound sul ritardo end to end pi`u tight. In molti casi [4], in particolare anche per l’algoritmo DRR, la distanza tempo-rale tra l’inviluppo che si riferisce a punti arbitrari dell’intervallo di servizio di un busy period e quello che invece `e valido solo in corrispondenza dei punti in cui un pacchetto lascia il sistema `e pari a Li/ρi. In termini pratici

questo vuol dire che la latency ΘS_i dell’ultimo di una catena di server pu`o essere diminuita di una uguale quantit`a rispetto al valore teorico calcolato considerando i ﬂussi pacchettizzati.

(32)