Lacaratterizzazionedelservizio Capitolo2

(1)

La caratterizzazione del

servizio

Nel capitolo introduttivo sul network calculus `e stata riportata solo la defini-zione generale di curva di servizio, ma non sempre tale modello risulta essere ottimale per l’analisi delle prestazioni. In ambito Diffserv ad esempio, nel quale si ha tipicamente scheduling aggregato, si possono avere situazioni di servizio non FIFO, per cui il bound sul virtual delay che si pu`o ricavare dalla conoscenza della curva di sevizio non è strettamente connesso a quello sul ritardo reale. In tali casi è sufficiente approcciare il problema da un punto di vista duale prendendo in esame gli istanti di partenza e d’arrivo anziché le funzioni cumulative. In altre situazioni anche quest’ultimo approccio risulta insufficiente.

In presenza di traffici generati da applicazioni adattative non è possibi-le fornire una caratterizzazione mediante curva d’arrivo dei flussi, quindi è necessario trovare un modo per determinare bound sul ritardo che ne siano indipendenti. Un modo per farlo `e legare il ritardo al backlog istantaneo,

(2)

ma ciò non è possibile con un’astrazione del sistema basata sulla curva di servizio, la quale in generale non dà alcuna garanzia su un intervallo tem-porale di lunghezza arbitraria. Di seguito viene presentata una panoramica dei modelli di servizio sviluppati nell’ambito del Network Calculus e una caratterizzazione generale, detta Latency Rate, dei pi`u diffusi algoritmi di

scheduling.

2.1 Il concetto di curva di servizio

La nozione di curva di servizio trova le sue radici nel lavoro di Parekh e Gal-lager [6], in cui vengono analizzate le prestazioni di un server GPS

(Gene-ralized Processor Sharing) con ingressi sagomati da controllori leaky bucket.

L’analisi condotta si focalizza in particolare sulle garanzie di throughput e

worst-case packet delay che `e possibile fornire. Sebbene il ritardo in una rete derivi dalla somma di diversi termini, quali i tempi di processing, di trasmis-sione, di propagazione e di accodamento, l’analisi prende in considerazione solo il termine dovuto all’accodamento, che praticamente è l’unico su cui si possa agire per differenziare il servizio. In tale contesto viene introdotto il concetto di “universal service curve”, in base al quale durante un qualunque intervallo in cui il backlog per un dato flusso `e non nullo, il nodo offre al flusso stesso un rate r di servizio almeno pari a quello allocato.

Il concetto viene ripreso e ampliato da Cruz in [20] per caratterizzare il servizio che una connessione riceve in un generico elemento di una rete a commutazione di circuito virtuale. In particolare si procede partendo dal-l’idea che una curva di servizio possa essere “allocata” per una connessione anzich´e semplicemente indotta da una particolare disciplina di scheduling

(3)

sotto opportune assunzioni riguardanti il traffico. Una volta determinate le curve di servizio che è necessario allocare per garantire le prestazioni volute si può sintetizzare una disciplina che supporti tale allocazione, indipendente-mente dalle assunzioni sul traffico. Ne deriva che le curve di servizio possono essere un valido strumento per la gestione di garanzie deterministiche sulla qualità del servizio, in quanto permettono di quantificare abbastanza facil-mente le prestazioni end-to-end. La definizione data da Cruz in [20] di fatto equivale a quella di “strict service curve”, di cui la curva di servizio risulta essere un’astrazione.

In maniera indipendente Agrawal, Cruz, Okino e Rajan in [14] e Le Boudec in [16] introducono la forma pi`u generale di curva di servizio e la applicano con l’ausilio del network calculus allo studio della classe di servizio

guaranteed service deﬁnita dall’IETF (Internet Engineering Task Force)

nel-l’ambito dell’architettura IntServ (Integrated Service). Tale classe di servizio `

e pensata per soddisfare le limitazioni stringenti sul ritardo e sulle perdite di applicazioni che siano comunque in grado di specificare limiti opportuni sul proprio traffico, in quanto nessuna garanzia viene fornita per il traffico fuori profilo.

Sfruttando l’operazione di convoluzione min-plus si pu`o deﬁnire l’“elemento

curva di servizio” come un dispositivo generico il cui flusso d’uscita `e com-preso appunto tra le convoluzioni del flusso d’ingresso con le curve di servizio minima e massima, come mostrato in figura 2.1. Tale elemento può essere usato per descrivere le operazioni di una varietà di elementi di rete quali

link, regolatori di traﬃco e router con un qualche meccanismo di scheduling

(4)

Figura 2.1: Esempio di regione d’uscita per un sistema con curve di servizio min β e max γ in corrispondenza di un dato ingresso R.

2.2 Alcuni elementi di rete

Di seguito si discute brevemente la schematizzazione mediante curva di ser-vizio dei principali elementi di una rete di comunicazione [14]. Salvo diverso avviso, si indicheranno con R ed R∗ rispettivamente la funzione cumulativa d’ingresso e d’uscita dei ﬂussi di traﬃco considerati.

2.2.1 Elementi di ritardo

Dato un ﬂusso che attraversa un elemento di rete, per il quale il ritardo sia limitato superiormente da dmax e inferiormente da dmin, si pu`o scrivere:

R(t − dmax)≤ R∗(t) ≤ R(t − dmin)

(5)

Poich´e per una generica funzione f ∈ F vale (f ⊗ δT)(t) = f (t − T ) (vedi

par. 1.1.2 a pag. 7), la relazione sopra menzionata per l’elemento di ritardo pu`o essere riscritta nel seguente modo:

(R ⊗ δdmax)(t) ≤ R∗(t) ≤ (R ⊗ δdmin)(t).

Dalle rispettive deﬁnizioni deriva che δdmax risulta essere la minima curva di

servizio e δdmin quella massima. Per un elemento con un ritardo costante di

propagazione la minima e la massima curva di servizio coincidono, vale a dire

δdmax = δdmin ≡ δdprop, dove dprop `e appunto il tempo di propagazione. Un

tale sistema risulta quindi essere anche lineare tempo-invariante (secondo la deﬁnizione dell’algebra min-plus).

`

E interessante notare come per gli elementi di ritardo mal si presti il concetto di strict service curve. Per rendersi conto di ci`o si consideri un sistema di cui si sappia soltanto che il ritardo `e limitato da un valore T e si assuma di inviargli in ingresso un flusso con rate d’ingresso costante, ma arbitrariamente piccolo . Il sistema risulta continuamente “al lavoro”, ma il rate d’uscita non può che essere , quindi l’unica curva di servizio in senso stretto che potrebbe essere data è identicamente nulla. Per tale motivo la

strict service curve non `e una valida caratterizzazione nemmeno per i sistemi complessi che in casi di interesse pratico non possono non contenere elementi di ritardo.

2.2.2 Link

Se si suppone di avere un collegamento con una capacit`a di C bit/s, allora per ogni ﬂusso che vi passa deve valere R∗(t) − R∗(s) ≤ C · (t − s) per ogni s ≤ t. Poich`e per la causalit`a del sistema deve essere inoltre R∗(t) ≤ R(t) per ogni

(6)

t, risulter`a anche R∗(t) ≤ R(s) + C · (t − s) per ogni s ≤ t e quindi R∗(t) ≤ (R ⊗ λC)(t), dove con1 λC(t) = C[t]+ si `e indicata la funzione peak rate.

Questo vuol dire che un elemento di rete con una capacit`a di C bit/s presenta una curva di servizio massima pari a λC; inoltre se il ﬂusso in questione `e

anche l’unico sul collegamento considerato allora nella disugualianza vale il segno uguale e l’elemento oﬀre λC sia come massima che come minima curva

di servizio.

Si può osservare tra l’altro che il comportamento sopra descritto è anche quello di un server che lavora ad un rate fissato e che nel caso di processore scarico [21] le due curve coincidono.

In generale, il throughput di un elemento di rete che offre una curva di servizio massima pari a γ è limitato dal coefficiente angolare asintotico di γ:

lim t→∞ R∗(t) t ≤ limt→∞ (R ⊗ γ)(t) t ≤ limt→∞ R(0) + γ(t) t = limt→∞ γ(t) t

Questo giustiﬁca il nome di peak rate dato alla funzione che descrive il comportamento di un link con capacit`a C.

2.2.3 Regolatori di traﬃco

I regolatori di traﬃco o shaper sono stati ampiamente descritti nel paragrafo 1.6, qui si vuole solo ricordare che l’ingresso e l’uscita, per uno shaper con curva di shaping σ sono legati dalla relazione (1.13 a pag. 28)

R∗ = R ⊗ σ

quindi anche in questo caso la minima e la massima curva di servizio coin-cidono e risultano essere pari a σ.

(7)

Più in generale si può dire che la minima e la massima curva di servi-zio coincidono sempre per un qualunque sistema “lineare tempo invariante” in senso min-plus (par. 1.6 pag. 30). Si ritiene opportuno osservare che tale proprietà è molto più forte della pura caratterizzazione mediante cur-va di servizio in quanto permette di operare un semplice procedimento di inversione a partire dalle funzioni cumulative d’ingresso R e d’uscita R∗.

Infatti, detta β la curva di servizio, per ogni t ≥ 0, vale

R∗(t) = (R ⊗ β)(t) = inf

0≤s≤t{R(t − s) + β(s)}

=⇒ R∗(t) ≤ R(t − s) + β(s) per ogni t ≥ 0 e per ogni 0 ≤ s ≤ t =⇒ β(s) ≥ R∗(t) − R(t − s) per ogni t ≥ 0 e per ogni 0 ≤ s ≤ t in particolare sar`a vero per il valore di t per cui si raggiunge l’estremo superiore =⇒ β(s) ≥ sup t≥s{R ∗_{(t) − R(t − s)}} posto t − s = u → u ≥ 0, t = s + u si avr`a β(s) ≥ sup u≥0{R

∗_{(s + u) − R(u)}} _{per ogni s ≥ 0}

e con un formale cambio di variabile per omogeneit`a di notazione

β(t) ≥ sup

u≥0{R

∗_{(t + u) − R(u)}} _{per ogni t ≥ 0}

=⇒

β(t) ≥ (R∗ R)(t) per t ≥ 0

β(t) = 0 per t < 0 (2.1)

Questo significa che la deconvoluzione tra l’ingresso e l’uscita costituisce un bound inferiore per la curva di servizio del sistema. Purtroppo questa proprietà non è di grande aiuto nei casi pratici in quanto in generale di un sistema reale non si può dire che sia “lineare tempo invariante”.

(8)

2.2.4 Scheduler

La curva di servizio minima può essere usata anche per caratterizzare il livello di servizio fornito da uno scheduler a ciascun flusso che condivide il link cui lo scheduler stesso regola l’accesso. Tale caratterizzazione pu`o riflettere un’azione attiva dello scheduler per l’isolamento dei flussi (come `e ad esempio il caso del GPS ) oppure pu`o derivare da un’attenta analisi della capacit`a dello scheduler in relazione alle curve d’arrivo degli altri flussi (quando ad esempio più flussi condividono la capacit`a di uno scheduler di tipo FIFO o PQ, Priority Queueing).

Uno dei modelli pi`u generali atto a caratterizzare il funzionamento di uno

scheduler, adottato anche dall’Integrated Services Working Group dell’IETF,

`e quello detto del tipo latency rate. Se un elemento di rete offre un servizio almeno pari a quello offerto dalla concatenazione di un server a rate fissato con capacit`a C bit/s e di un elemento con ritardo costante pari a T , allora esso offre una curva di servizio del tipo Rate Latency βC,T = λC⊗ δT.

Esistono purtroppo forme di scheduling che non possono essere ben mo-dellate con una curva del tipo Rate Latency, quindi la restrizione imposta dall’IETF comporta una certa perdita in ﬂessibilit`a.

D’altra parte è forte l’esigenza di disporre di uno strumento unico che permetta di valutare le prestazioni di reti eterogenee in cui i singoli server implementino diversi algoritmi di scheduling e i modelli di traffico siano vari. È fondamentale dunque avere un modello che sia indipendente nella forma dalle peculiarit`a del singolo scheduler, ma ne tenga comunque conto nei valori specifici dei parametri.

(9)

2.3 Server LR

Un modello generale per l’analisi del comportamento relativo al caso peggio-re, rispetto ai singoli flussi, di una vasta gamma di algoritmi di scheduling viene ampiamente sviluppato in [22] da Stiliadis e Varma, che definiscono una classe di scheduler detta classe dei server Latency-Rate (LR). Gli stessi autori dimostrano infatti che molti degli algoritmi più comuni appartengono alla classe LR e in particolare tutti gli scheduler che forniscono garanzie sul-la banda, quali ad esempio WFQ (Weighted Fair Queuing), Virtual Clock,

Weighted Round Robin e Deﬁcit Round Robin.

La teoria dei server LR si basa sul concetto di busy period di un ﬂusso, un intervallo temporale durante il quale il rate medio di arrivi risulta maggiore o uguale del rate ρi riservato al ﬂusso considerato. Il requisito per cui

un algoritmo di scheduling si dice appartenere alla classe LR è che il rate medio di servizio offerto a ciascun flusso, in un intervallo che inizia dopo un tempo Θ dall’inizio del suo busy period, sia almeno pari al rate ad esso riservato. Il parametro Θ, che può essere diverso per ciascun flusso, viene detto latency dello scheduler e per un particolare algoritmo pu`o dipendere dai suoi parametri interni, dal rate di trasmissione sul collegamento d’uscita e dal rate allocato ai vari flussi. Il comportamento di uno scheduler LR `e determinato dunque da due parametri per ogni flusso i servito: la latency Θi

e il rate ρiallocato. La latency di un server LR pu`o essere in particolare vista

come il worst-case delay (ritardo relativo al caso peggiore) sperimentato dal primo pacchetto di un busy period, ovvero da un pacchetto che arriva quando la coda corrispondente al suo flusso di traffico è vuota.

(10)

2.3.1 Deﬁnizione formale di server LR

Si assume che i server considerati siano dispositivi non cut-through2 e si in-dicano con Ai(τ, t) e Wi(τ, t) rispettivamente gli arrivi del ﬂusso i e il servizio

ricevuto dallo stesso durante l’intervallo (τ, t]. Tali quantit`a equivalgono se-condo la simbologia del network calculus introdotta nel primo capitolo alle seguenti:

Ai(τ, t) = R(t) − R(τ )

Wi(τ, t) = R∗(t) − R∗(τ )

Si danno inoltre le seguenti deﬁnizioni:

periodo di backlog di un ﬂusso i : `e un qualunque intervallo di tempo

durante il quale il traffico appartenente al flusso considerato è costan-temente accodato nel sistema; se si indica con Qi(t) la quantità di

traffico del flusso i accodato nel server all’istante t, sarà

Qi(t) = Ai(0, t) − Wi(0, t) = R(t) − R∗(t)

e in formule si pu`o dire che il ﬂusso ha backlog all’istante t se Qi(t) > 0;

busy period di un ﬂusso i : `e ciascuno degli intervalli massimi (τaj, τzj]3,

definiti in successione a partire dall’istante in cui inizia il traffico, tali che il totale degli arrivi dall’inizio dell’intervallo fino ad un qualunque istante t dell’intervallo stesso non scenda al di sotto del servizio che ver-rebbe ricevuto nell’ipotesi che il rate garantito fosse esattamente pari 2_{Si dice che un nodo `}_{e cut-through se implementa una forma di switching o} forwar-ding per cui un pacchetto inizia ad essere trasmesso verso un’uscita prima d’essere stato

completamente ricevuto dal nodo stesso.

3_Poich´_{e deﬁniti in successione `}_{e possibile un ordinamento dei busy period e}_{j altro non}

(11)

a quello allocato ρi, si confronti la ﬁgura 2.2 per una visualizzazione

graﬁca. In formule, per ogni t ∈ (τaj, τzj] deve valere:

Ai(τaj, t) ≥ ρi· (t − τaj). 000 000 000 000 000 111 111 111 111 111 000 000 000 000 000 111 111 111 111 111 0 0 1 1 0000 0000 0000 0000 1111 1111 1111 1111 000000 000000 000000 000000 111111 111111 111111 111111 000000 000000 000000 000000 000000 111111 111111 111111 111111 111111 00000 00000 00000 00000 11111 11111 11111 11111 00000 00000 00000 00000 00000 11111 11111 11111 11111 11111 000 000 000 000 000 000 111 111 111 111 111 11101 0000 0000 0000 0000 0000 0000 0000 1111 1111 1111 1111 1111 1111 1111 ρi ρi R(t) τa1 τz1 τa2 τz2 bit t

Figura 2.2: Deﬁnizione di busy period

`

E bene puntualizzare la distinzione basilare tra le due quantità appena definite: i busy period corrispondono ai periodi di backlog che si avrebbero in un sistema ipotetico che servisse il flusso con un rate costante ρi; i periodi di

backlog, in generale, si riferiscono invece ad un sistema reale in cui il servizio

pu`o variare istantaneamente in base allo stato del sistema stesso e pertanto possono dipendere fortemente dalla strategia di scheduling. Ne segue che un

busy period di un ﬂusso pu`o contenere intervalli durante i quali il backlog `

e nullo e/o il ﬂusso non riceve alcun servizio. L’inizio di un busy period `e sempre determinato dall’arrivo di un pacchetto nel sistema. Il fatto che il

backlog e il servizio possano essere contemporaneamente nulli su intervalli

(12)

figura 2.3 mostra che una tale situazione, sebbene per particolari andamenti del traffico in ingresso, può realmente verificarsi. Si vede infatti che durante l’intervallo δ sia il backlog che il servizio ricevuto dal flusso i risultano nulli.

0000000 0000000 0000000 0000000 0000000 1111111 1111111 1111111 1111111 1111111 0000 0000 0000 0000 1111 1111 1111 1111 00 00 11 11 0 1 00 00 00 00 11 11 11 11 00 00 00 00 11 11 11 11 000000 000000 111111 111111 000000 000000 000000 000000 000000 111111 111111 111111 111111 111111 00 00 00 00 11 11 11 11 00000 00000 00000 00000 11111 11111 11111 11111 ρi δ R(t) R∗(t) τa1 τz1 bit t

Figura 2.3: Backlog nullo e assenza di servizio in un busy period `

E importante sottolineare che, per quanto osservato in relazione alla de-finizione di backlog, uno stesso flusso applicato a scheduler diversi determina in generale periodi di backlog differenti, anche quando l’allocazione delle ri-sorse è la stessa. Questo è il motivo fondamentale per cui la definizione dei server LR si basa sui busy period, che dipendono dalla funzione d’arrivo del flusso e dal rate allocato; ma risultando indipendenti dall’algoritmo di

scheduling ben si prestano alla deﬁnizione di un modello generale.

Detto (τaj, τzj] il j-esimo busy period del ﬂusso i, si indica con Wi,jS(τaj, t)

il servizio totale fornito dal server al traffico del flusso i che è arrivato du-rante il j-esimo busy period fino all’istante t e con τ_j∗ l’istante in cui l’ultimo

(13)

bit del traﬃco arrivato durante il j-esimo busy period lascia il sistema. Si

deve notare che il servizio totale Wi(τaj, t) fornito dal sistema al ﬂusso i

du-rante l’intervallo (τaj, t] pu`o eﬀettivamente essere maggiore di Wi,jS(τaj, t) in

quanto potrebbe essere servito anche del traﬃco appartenente a precedenti

busy period ed eventualmente ancora in coda.

Deﬁnizione 2.3.1 (Server LR) Si dice che un server S appartiene alla classe LR se e solo se si pu`o determinare una costante non negativa C_iS tale che per ogni t ∈ (τaj, τj∗] di un generico busy period j valga:

W_i,jS(τaj, t) ≥ max(0, ρi· (t − τaj − CiS)) (2.2)

Il minimo valore di CS

i che soddisfa tale disugualglianza viene deﬁnito come

la latency del server per il ﬂusso i e viene indicata con ΘS_i.

`

E interessante notare che da questa definizione e da quella di busy period segue immediatamente che tutti i pacchetti di un busy period completano il servizio non più tardi di un tempo ΘS_i dopo la fine del busy period stesso.

La restrizione che definisce la classe LR impone che il servizio fornito ad un flusso dall’inizio del suo busy period sia limitato inferiormente da una curva del tipo rate latency. Ci`o equivale a chiedere, come già osservato, che il rate medio del servizio offerto dallo scheduler ad un traffico busy4 in un qualunque intervallo che inizi dopo un tempo ΘS_i dall’inizio del busy period `

e almeno pari al rate ad esso riservato. Questa condizione `e molto meno restrittiva di quella imposta per un GPS in cui viene praticamente posto un limite sulla banda istantanea. Il limite inferiore sul rate imposto dal

GPS deve valere per ogni intervallo (τ, t] in cui si ha backlog per il ﬂusso

4_{Si pu`}_{o dire che un traﬃco}_{i `e busy durante gli intervalli del tipo (τ}

(14)

corrispondente, mentre nel caso LR la restrizione `e limitata ad intervalli legati ai busy period, il GPS risulta quindi essere un caso particolare dei

server LR.

Uno dei risultati fondamentali della teoria consiste nel fatto che una ca-scata di pi`u server appartenenti alla classe LR pu`o essere sostituita, ai fini dell’analisi, da un unico server LR equivalente con rate pari al minimo tra quelli allocati nei vari server della cascata e con latency pari alla somma delle latency. Tale risultato coincide con la propriet`a di concatenazione del-le curve di servizio (vedi teorema 1.5.1 a pag. 23) e permette ad esempio di determinare bound deterministici sul ritardo end-to-end semplicemente analizzando un unico sistema equivalente. Ciò oltre ad essere una semplifi-cazione permette, come sottolineato dal principio del pay bursts only once, di ottenere bound migliori.

Va ricordato che l’idea di collassare una catena di elementi di una rete in un singolo nodo equivalente, al ﬁne di analizzarne il comportamento

end-to-end nei confronti di un singolo ﬂusso, `e stata inizialmente proposta in [23] da Parekh e Gallager in relazione ad uno scenario GPS.

2.3.2 Il modello LR come curva di servizio rate latency

Si pu`o dimostrare agevolmente, in ipotesi di servizio FIFO, che un server di classe LR con rate ρi e latency Θi oﬀre di fatto una curva di servizio βρi,Θi.

Dimostrazione

Dato un generico istante t si indichi con m il busy period con il pi`u grande numero d’ordine che termina il servizio prima di t. Per semplicit`a di nota-zione si indicher`a con τj l’inizio del j-esimo busy period. Siano inoltre Ri(t)

(15)

e R_i∗(t) le funzioni cumulative d’ingresso e d’uscita relative al ﬂusso i. Detto

t < t l’istante in cui l’m-esimo busy period termina il servizio e assumendo

che Ri(t) sia continua a sinistra, come `e lecito fare per ﬂussi

pacchettizza-ti che vengano osservapacchettizza-ti, come accade di solito, quando l’ulpacchettizza-timo bit di un pacchetto `e stato ricevuto, si ha:

R∗_i(t) = Ri(τm+1− )

infatti per deﬁnizione e per l’ipotesi FIFO all’istantet risultano serviti tutti

i pacchetti arrivati prima dell’inizio dell’ (m + 1)-esimo busy period.

Si noti che in generale il servizio di un busy period pu`o terminare anche dopo l’inizio di un busy period successivo, come pu`o essere facilmente evi-denziato dall’analisi della figura 2.4. Ciò può essere spiegato osservando che i busy period sono definiti solo in relazione al rate allocato, mentre il servizio sarà sempre affetto da un termine di ritardo che nella peggiore delle ipotesi risulter`a uguale alla latency Θ_i.

Il servizio totale durante l’intervallo (t, t] pu`o essere scritto, essendo

l’unico busy period sotto servizio proprio l’ (m + 1)-esimo, come:

Wi(t, t) = Wi,m+1(t, t) = Wi,m+1(t, t) + Wi,m+1(τm+1, t)

l’ultima uguaglianza deriva dal fatto che il secondo termine a destra è nullo poich`e il busy period (m + 1)-esimo non riceve servizio fino all’istante t in cui termina il servizio del busy period precedente, quindi risulta, dalla definizione di server LR:

Wi(t, t) = Wi,m+1(τm+1, t) ≥ ρi(t − τm+1− Θi)+

(16)

00000 00000 00000 00000 11111 11111 11111 11111 00000 00000 11111 11111 00 11 00000000 0000 1111 1111 1111 00000 00000 00000 00000 11111 11111 11111 11111 00000 00000 00000 00000 11111 11111 11111 11111 000 000 111 111 000 000 111 111₀₁ 000 000 111 111 0 1 00 00 00 00 11 11 11 11 000 000 000 000 111 111 111 111 000 000 111 111 00 00 00 00 11 11 11 11 0 0 0 1 1 1 00000 00000 00000 00000 11111 11111 11111 11111 00000 00000 00000 00000 00000 11111 11111 11111 11111 11111 ρi ρi t R(t) R∗(t) τa1 Θi τz1 τa2 τz1+ Θiτa2 + Θi τz2 bit t

Figura 2.4: Server LR come elemento curva di servizio

del busy period (m + 1)-esimo. Per concludere si noti che:

R∗_i(t) − R∗_i(t) = Wi(t, t) ≥ ρi· (t − τm+1− Θi)+,

quindi dall’uguaglianza R∗_i(t) = Ri(τm+1− ) segue la conclusione:

R_i∗(t) ≥ Ri(τm+1−) + ρi· (t − τm+1− Θi)+≥ Ri⊗ βρi,Θi (2.3)

risulta cos`ı veriﬁcata la propriet`a di curva di servizio per βρi,Θi.

♦

Il risultato principale, su cui si basano le prove atte a dimostrare che molti algoritmi di scheduling ben noti appartengono alla classe LR e che consente inoltre di determinare un limite superiore alle loro latency, `e il seguente:

(17)

Lemma 2.3.1 Dato un intervallo (sj, tj] in cui il ﬂusso i ha costantemente

un backlog non nullo nel server S, se il servizio oﬀerto dal server stesso ai pacchetti che sono arrivati nel medesimo intervallo pu`o essere limitato ad ogni istante t, con sj ≤ t ≤ tj, come:

Wi(sj, t) ≥ max(0, ρi(t − sj− Θi)) (2.4)

allora il server S appartiene alla classe LR e ha una latency minore o uguale a Θ_i.

Purtroppo non vale il viceversa, vale a dire un limite ﬁnito di Θ_i su un periodo di backlog potrebbe non esistere anche nel caso in cui il server appartenga alla classe LR. Quindi in generale il limite che si ottiene usando il lemma 2.3.1 non `e stretto. Un modo per dimostrare eventualmente che il

bound trovato sia stretto `e quello di fornire almeno un esempio in cui venga raggiunto. Ciò è fondamentale nei casi pratici perché, se l’eventuale curva di servizio determinata `e molto lontana da quella reale, anche i bound che ne derivano risultano essere molto larghi e quindi poco significativi.

Generalmente quando si analizza il comportamento di uno scheduler in base ai suoi periodi di backlog non si tiene conto di eventuali ritardi costanti, dovuti ad esempio al processing (i ritardi di propagazione sono normalmente comunque trascurabili). Si veriﬁca comunque facilmente che i risultati del-l’analisi restano validi se tali componenti costanti vengono inglobati come termini aggiuntivi nelle latency.

2.4 Server Guaranteed Rate

Per l’analisi delle discipline di scheduling pu`o risultare comodo aﬀrontare il problema della caratterizzazione del servizio da un punto di vista duale

(18)

rispetto all’approccio seguito per la definizione della curva di servizio. Si prendono in considerazione gli istanti di arrivo e di partenza dei pacchetti anzich´e la funzione cumulativa R(t) di un flusso e si definisce il concetto di nodo “guaranteed rate”. Un simile approccio determina l’uso dell’algebra

max-plus, che gode di proprietà analoghe a quelle della min-plus. Esso ri-sulta spesso più appropriato a trattare flussi con dimensione dei pacchetti variabile, ma funziona bene solo quando le curve di servizio sono del tipo

rate latency.

Il procedimento appena citato è inoltre utile quando un dispositivo non possa essere adeguatamente descritto con un modello di tipo FIFO come pu`o accadere nel caso di architetture Diffserv. Anche quando, ad esempio, tutti i pacchetti di un aggregato condividano una singola coda FIFO all’uscita (una tipica assunzione Diffserv ), i pacchetti dell’aggregato che giungono da diverse porte d’ingresso possono sperimentare un ritardo variabile prima di essere consegnati all’uscita. Ciò può determinare un riordinamento di arrivo alla coda d’uscita rispetto a quello che era l’ordine degli arrivi alle porte d’ingresso.

Deﬁnizione 2.4.1 (Nodo GR) Sia dato un nodo che serve un ﬂusso. Si indichino con an≥ 0, dn≥ 0 gli istanti di arrivo e di partenza dell’ n-esimo

pacchetto in ordine d’arrivo. Sia inoltre ln la lunghezza in bit dell’n-esimo

pacchetto. Si dice che il nodo `e del tipo guaranteed rate con rate r e latency

e, GR(r,e), se esso garantisce che valga:

(19)

dove fn `e deﬁnita nel seguente modo:

f0= 0

fn= max{an, fn−1} +l_rn per ogni n ≥ 1

(2.5)

Praticamente la variabile fn, virtual ﬁnish time o “guaranteed rate clock”,

pu`o essere interpretata come l’istante di partenza del pacchetto n-esimo da un server FIFO con rate r costante. Il parametro e indica quanto di fatto il nodo GR diﬀerisce da tale comportamento. Si ricordi comunque che un nodo GR non deve essere necessariamente FIFO.

La ricorsione dell’equazione (2.5) pu`o essere risolta facilmente sfruttando le propriet`a dell’algebra max-plus. In particolare, adottando le stesse nota-zioni della deﬁnizione 2.4.1 e ponendo per convenzione d0 = 0, si dimostra

che:

un nodo `e GR se e solo se per ogni n esiste un k ∈ {1, . . . , n} tale che:

dn≤ ak+lk

+· · · + l_n

r + e (2.6)

questa relazione duale rispetto a quella che deﬁnisce la curva di servizio βr,e(t) = r(t − e)+.

Dimostrazione. Deﬁnita la quantit`a

An_j aj+ lj

+· · · + l_n

r ∀ 1 ≤ j ≤ n

si ottiene facilmente

fn= max{Ann, Ann−1, . . . An1}.

Infatti per deﬁnizione e per ogni n ≥ 1, si ha:

fn= max{an, fn−1} + l_rn = an+l_rn ∨fn−1+l_rn

(20)

= an+ l_rn ∨an−1+ ln−1_r + l_rn ∨fn−2+ln−1_r +l_rn .. . = a1+l1+· · · + l_r n ∨a2+l2+· · · + l_r n ∨ · · · ∨an+l_rn

esister`a dunque un k tale che fn= Ank.

(⇒) Dire che un nodo `e GR(r,e) signiﬁca che d_n≤ f_n+ e = An_k+ e. (⇐) Viceversa se esiste k tale che d_n≤ An

k+ e, allora sar`a anche

dn≤ max{Ann, Ann−1. . . An1} + e = fn+ e.

♦ Il concetto di guaranteed rate `e un modo alternativo di descrivere la propriet`a di curva di servizio di tipo rate latency, ma si deve precisare che i due modelli non sono perfettamente equivalenti. In particolare si pu`o dimostrare [5] che un nodo GR con rate r e latency e, nell’ipotesi di ingresso pacchettizzato, pu`o essere decomposto come un elemento curva di servizio βr,e(t) = r(t−e)+

seguito da un packetizer ; quindi per le propriet`a del packetizer, un nodo

GR(r,e) oﬀre una curva di servizio minima βr,e+lmax/r (punto 3 pag. 34).

Viceversa, ma solo per nodi FIFO, un elemento con curva di servizio βr,e(t) =

r(t − e)+`e anche un nodo GR con rate r e latency e.

Si dimostra inoltre che anche nel caso di nodi non FIFO vale un bound sul ritardo analogo a quello presentato nel paragrafo 1.4. In particolare pu`o essere formulato come segue:

(21)

il ritardo di un qualunque pacchetto di un ﬂusso α-smooth servito da un nodo GR (anche non-FIFO ) `e limitato da

sup t>0 _α(t) r − t + e (2.7)

Per nodi GR che risultano FIFO per ciascun ﬂusso si applicano le propriet`a di concatenazione ottenute con l’approccio della curva di servizio:

la concatenazione di I nodi GR (FIFO per ﬂusso) con rate ri e

latency ei equivale ad un unico nodo GR con rate r = mini∈Iri

e latency e = _i=1,...,Iei +

i=1,...,I−1Lmax/ri, dove Lmax `e

la dimensione massima per i pacchetti del flusso. Il secondo termine della latency è l’effetto dovuto al packetizer e nel caso in cui ri = r per ogni i è pari a (I − 1)Lmax/r.

Purtroppo tale propriet`a non continua a valere per nodi non-FIFO [24].

2.5 Adaptive Service Guarantee

I concetti di curva di servizio o guaranteed rate mal si adattano in presenza di applicazioni adattative, che generano un carico di traffico dipendente dalle condizioni di utilizzazione della rete. Poiché risulta problematico caratteriz-zare tali tipi di traffici mediante un inviluppo tipo curva d’arrivo, Cruz et al. in [25] definiscono la nozione di “adaptive service guarantee” che permette di ricavare limiti superiori sul ritardo di rete anche quando non siano noti i profili di traffico. In particolare tali limiti sono ottenuti in termini di

bac-klog (che pu`o essere controllato mediante meccanismi di retroazione quali il

(22)

La caratterizzazione mediante adaptive service guarantee non risulta necessaria al fine di determinare limiti inferiori sul throughput, sebbene permetta di ricavarli, perché si possono ottenere, indipendentemente dalle caratteristiche del traffico, anche a partire dalla curva di servizio.

Il motivo per cui una curva di servizio risulta non appropriata alle appli-cazioni adattative risiede nel fatto che, per come è definita, non dà alcuna garanzia di servizio su un intervallo di lunghezza arbitraria, neanche nel caso in cui si abbia continuamente backlog. Praticamente pu`o accadere che un flusso riceva più servizio, durante un qualche intervallo di tempo, di quel-lo minimo richiesto e venga successivamente penalizzato. Ciò impedisce che possa essere dedotto un bound sul ritardo cui un determinato pacchetto sar`a soggetto, noto che sia il backlog nell’istante di arrivo del pacchetto stesso nel sistema.

Figura 2.5: Limitazioni della curva di servizio

La figura 2.5 permette di avere un’idea visiva della situazione nel caso di un nodo che offra una curva di servizio λC e riceva in ingresso un flusso

con funzione cumulativa R(t) = B per t > 0. Nella ﬁgura `e mostrata una delle possibili uscite, la quale evidenzia come il sistema possa servire subito

(23)

un’elevata quantit`a di dati pari a B − (con arbitrariamente piccolo) e rimanere poi inattivo ﬁno all’istante B−_C , dando origine ad un fenomeno a

volte riferito come “sindrome degli scheduler pigri”.

Considerazioni analoghe valgono per il modello guaranteed rate perch´e, anche in tal caso, i pacchetti possono essere serviti prima di quanto richiesto, col rischio di penalizzare quelli successivi.

Una possibile soluzione al problema esposto potrebbe venire dall’uso della strict service curve, ma purtroppo, come precedentemente osservato, essa non permette di caratterizzare gli elementi di ritardo.

Definizione 2.5.1 (Curva di servizio adattiva) Date due funzioni β, β di F e un sistema S attraversato da un un flusso con funzioni cumulative d’ingresso e d’uscita rispettivamente R e R∗, si dice che il sistema offre la garanzia adattiva ( β, β) se per ogni s ≤ t vale:

R∗(t) ≥R∗(s) + β(t − s) ∧ inf

u∈[s,t]

R(u) + β(t − u). (2.8)

Per esprimere questa relazione si usa la notazione R −→ (β, β) −→ R∗. Se β = β si dice che il nodo oﬀre la garanzia adattiva β e si scrive R −→ (β) −→ R∗.

Nel caso in cui β sia continua e R sia continua a sinistra, la deﬁnizione equivale a dire che per ogni s ≤ t vale una tra:

1. R∗(t) − R∗(s) ≥ β(t − s)

2. ∃ u ∈ [s, t] tale che R∗(t) ≥ R(u) + β(t − u).

Vediamo adesso con semplici esempi come il concetto di adaptive service

(24)

Elemento di ritardo: se un sistema S garantisce che il ritardo virtuale

sia limitato ad un valore d, allora il sistema oﬀre una garanzia adattiva

δd, infatti per ogni s ≤ t, se t − s ≤ d vale banalmente:

R∗(t) ≥ R∗(s) + δd(t − s)

essendo il secondo termine a destra nullo. Se invece t − s > d allora la propriet`a relativa al ritardo virtuale implica che

R∗(t) ≥ R(t − d) ≡ inf

u∈[s,t][R(u) + δd(t − u)].

Strict service curve: se un sistema S offre ad un flusso una strict service curve β allora esso offre allo stesso flusso anche la garanzia adattiva β. Si assuma che β sia continua e si consideri un dato istante (scelto

arbitrariamente) s ≤ t. Se l’intervallo [s, t] `e compreso in un periodo di tempo in cui si ha continuamente backlog, allora per deﬁnizione di

strict service curve si ha

R∗(t) ≥ R∗(s) + β(t − s)

altrimenti, detto t0 ≥ s l’inizio dell’ultimo periodo di backlog prima di t, si ha

R∗(t) ≥ R(t0) + β(t − t0)≥ inf

u∈[s,t]

R(u) + β(t − u)

quindi in ogni caso

R∗(t) ≥ R∗(s) + β(t − s) ∧ inf

u∈[s,t]

R(u) + β(t − u).

Greedy shaper: un greedy shaper con curva di shaping σ, con σ good5

5_{Notare che non si tratta di una restrizione in quanto una curva d’arrivo}_{σ pu`o essere}

(25)

oﬀre la garanzia adattiva (σ, σ) con σ(t) (σσ)(t) = inf

u≥0

σ(t + u) − σ(u).

La relazione ingresso-uscita per un greedy shaper `e data da:

R∗(t) = (R ⊗ σ)(t) = inf

u≤t

R(u) + σ(t − u).

Dividendo il calcolo dell’inf sui due intervalli per cui u < s e u ≥ s si ha: R∗(t) = inf u<s R(u) + σ(t − u)∧ inf u∈[s,t] R(u) + σ(t − u).

Dalla deﬁnizione di σ segue: σ(t − s) = inf

w≥0

σ(t − s + w) − σ(w)≤ σ(t − s + s − u) − σ(s − u)

avendo calcolato l’argomento dell’inf per w = s − u e nell’ipotesi che

u < s, quindi: σ(t − u) ≥ σ(s − u) + σ(t − s) da cui deriva: inf u<s R(u) + σ(t − u)≥ R∗(s) + σ(t − s) e in conclusione R∗(t) ≥R∗(s) + σ(t − s) ∧ inf u∈[s,t] R(u) + σ(t − u).

La relazione fra il ritardo e il backlolg, che la caratterizzazione di un sistema mediante adaptive service guarantee permette di ricavare, `e espressa nel seguente:

(26)

Teorema 2.5.1 (Legame ritardo backlog) Se R −→ (β, β) −→ R∗, al-lora il ritardo virtuale al tempo t `e limitato da β−1Q(t) , dove Q(t) `e il

backlog all’istante t e β−1 `e la pseudo-inversa di β.

Si ricordi che se il sistema `e FIFO il virtual delay all’istante t coincide con il ritardo di un eventuale bit che arrivi nello stesso istante.

2.6 Packet Scale Rate Guarantee

Cos`ı come il modello GR `e il corrispondente max-plus del concetto

min-plus di curva di servizio, il PSGR (packet scale rate guarantee) lo `e per quello di adaptive service curve e quindi, come questo, permette di derivare informazioni sul ritardo a partire dal grado di riempimento del buﬀer.

Il modello PSGR viene praticamente introdotto per risolvere alcuni pro-blemi insiti nella deﬁnizione stessa della classe EF(Expedited Forwarding) dell’architettura Diﬀserv [26, 27, 28, 29].

L’intento del PHB (per hop behavior)6 della classe EF `e quello di fornire un certo rate all’aggregato EF con una granularit`a temporale la più piccola possibile; ciò può essere espresso in maniera rigorosa introducendo il concetto di packet scale rate guarantee.

Deﬁnizione 2.6.1 (Packet Scale Rate Guarantee) Dato un nodo che serve un ﬂusso di pacchetti, siano an, dn rispettivamente gli istanti di arrivo

e di partenza del pacchetto n-esimo (in ordine di arrivo) con a1 ≥ 0. Si dice

6_{A ciascuna classe diﬀserv corrisponde un dato valore del campo DSCP(Diﬀerentiated} Service Code Point, 101110 nel caso EF ) dell’header IP. A ciascuno di tali valori risulta

(27)

che il nodo oﬀre al ﬂusso un servizio del tipo packet scale rate guarantee, con rate r e latency e, se gli istanti di partenza soddisfano la seguente:

dn≤ fn+ e (2.9)

dove fn `e cos`ı deﬁnita:

f0= d0 = 0 fn= max an, min(dn−1, fn−1) +ln r per ogni n ≥ 1 (2.10)

in cui ln `e la lunghezza in bit dell’n-esimo pacchetto.

Si noti che l’unica diﬀerenza tra le deﬁnizioni di un nodo GR e di uno

PSGR consiste nella presenza del termine dn−1nella ricorsione che deﬁnisce

il virtual finish time (cfr. le equazioni 2.5 e 2.10). Di fatto quello che avviene per un PSGR è che la deadline7 viene ridotta nel caso in cui un pacchetto venga servito prima del dovuto (vedi fig. 2.6). Ciò permette di superare le limitazioni legate al concetto di curva di servizio evidenziate nel paragrafo precedente, inoltre implica che la propriet`a di PSGR `e più forte. Infatti un nodo PSGR con parametri r ed e risulta essere anche GR con gli stessi parametri.

In particolare quel che pi`u interessa `e che un nodo PSGR gode delle stesse propriet`a di uno GR:

quando sia nota la curva d’arrivo dei traﬃci d’ingresso si possono

calcolare bound sul ritardo mediante l’equazione (2.7);

7_{Col termine deadline si intende genericamente l’istante entro il quale un certo}

(28)

Figura 2.6: Diﬀerenza tra un PSGR e un GR

soddisfa la propriet`a di una curva di servizio del tipo rate-latency che

pu`o essere usata per il dimensionamento dei buﬀer.

In maniera del tutto analoga a quanto fatto per il GR, sfruttando le propriet`a dell’algebra max-plus, si pu`o ottenere una caratterizzazione del

PSRG che non contiene il virtual ﬁnish time fn, per cui dire che un nodo `e

PSRG con rate r e latency e equivale a dire che per ogni n e ogni 0 ≤ j ≤ n − 1 vale una tra le seguenti:

1. dn≤ e + dj+lj+1 +· · · + l_n r (2.11) 2. ∃k ∈ {j + 1, . . . , n} tale che dn≤ e + ak+lk +· · · + l_n r (2.12)

(29)

Quanto appena esposto si traduce nel dire che un nodo PSGR garantisce un rate r su qualunque scala temporale, il che si riconduce a quella che come gi`a osservato `e l’esigenza primaria della classe di servizio EF.

Il modello PSGR pu`o riferirsi ad un nodo comunque complesso e non necessariamente work conserving ; nel caso di un semplice scheduler si veriﬁca l’equazione (2.11) nel caso in cui dj e dn siano nello stesso intervallo di

backlog, altrimenti sar`a soddisfatta l’equazione (2.12) dove ak `e l’inizio del

periodo di backlog. `

E interessante confrontare, per un semplice scheduler, le conclusioni che si possono trarre rispettivamente dall’equazione (2.6) corrispondente ad un modello GR e dalle (2.11, 2.12) relative al modello PSGR. Se per sempli-cit`a si assume che la latency e sia nulla, PSGR significa che durante un qualunque periodo di backlog lo scheduler garantisce un rate almeno pari ad r, mentre GR vuol dire che solo durante il periodo di backlog che inizia quando un pacchetto trova il sistema vuoto (praticamente quello che viene detto busy period nella teoria delle code) il rate medio è almeno r. Quindi, come pi`u volte sottolineato, il modello GR consente che lo scheduler serva alcuni pacchetti ad un rate maggiore di r per poi avvantaggiarsene servendo altri pacchetti ad un rate inferiore fin tanto che il rate medio sia almeno r; ciò non `e possibile con un modello PSGR.

Un nodo PSGR con rate r e latency e = 0 viene detto minimum rate

server (server a rate minimo) e soddisfa:

d0 = 0

di ≤ max{ai, di} + l_ri per ogni i ≥ 1

(2.13)

Ci`o signiﬁca che un minimum rate server garantisce, durante un qualunque

(30)

Una delle caratteristiche fondamentali del modello PSGR `e che analoga-mente alla adaptive service guarantee permette di legare il ritardo al backlog istantaneo e che il bound che ne deriva vale invariabilmente sia per nodi

FIFO che non.

Teorema 2.6.1 (Ritardo-backlog per un PSGR) Sia dato un nodo PSGR con rate r e latency e, non necessariamente FIFO e si indichi con Q il backlog all’istante t. Tutti i pacchetti che sono presenti nel sistema all’istante t lasceranno il sistema non pi`u tardi dell’istante t + Q/r + e.

Per una dimostrazione si rimanda al paragrafo 7.7 di [5].

Il teorema precedente permette di calcolare un semplice bound sul ritardo in un nodo m che oﬀra un servizio EF. Se il nodo `e di tipo PSGR con rate

rm e latency em assumendo che la dimensione del buﬀer sia limitata da Bm

un bound sul ritardo, valido per qualunque livello di utilizzazione, `e dato da

Bm/rm+ em.

Sebbene non sia possibile aspettarsi una perfetta equivalenza tra i con-cetti di packet scale rate guarantee e adaptive service guarantee, sfruttando il concetto di packetizer si pu`o dimostrare, per un nodo S con ingresso R pacchettizzato e uscita R∗, che:

Se R −→ (β) −→ R∗, con β = βr,e e se S `e FIFO, allora S risulta

essere, per il ﬂusso, PSGR con rate r e latency e.

Viceversa se S è del tipo PSGR con rate r e latency e e se R∗ è pacchettizzato, allora S risulta essere la concatenazione di un nodo S che offre la adaptive service guarantee βr,e e di un packetizer. Se S è

(31)

La diﬀerenza sostanziale tra i concetti di PSGR e adaptive service

gua-rantee `e che il primo viene specificato in riferimento agli istanti di arrivo e di partenza dei pacchetti, rendendo più agevole il trattamento di flussi con dimensione dei pacchetti variabile; il secondo, più generale, fa invece uso delle funzioni cumulative in bit.

(32)