Basi di Network Calculus

Basi di Network Calculus

Il Network calculus `e uno strumento di calcolo che permette di valutare le prestazioni real time delle reti di comunicazione e si basa sui lavori “pio-nieristici” di Cruz [12] e [13]. In tali lavori viene sviluppato un calcolo per ottenere un bound sul ritardo e sulla quantit`a di memoria richiesta nei nodi di una rete di comunicazione che opera a commutazione di pacchetto (packet

switched). Il modello preso in considerazione prevede l’interconnessione di

alcuni elementi di rete e una strategia di routing prefissata, il che significa che ogni traffico si origina in un dato nodo, termina in un altro dato nodo e segue un ben determinato percorso tra i due. Le informazioni che derivano da una tale analisi risultano utili per il dimensionamento degli elementi della rete.

La novit`a di questo approccio consiste nell’uso di un modello non proba-bilistico per caratterizzare i flussi di traffico, laddove la tradizionale teoria delle code fa riferimento a processi stocastici e distribuzioni di probabilit`a. In particolare, viene posto un limite sulla burstiness del traffico in un in-tervallo, in funzione della lunghezza dell’intervallo stesso. `E quello che nel

gergo del Network Calculus viene detto curva d’arrivo di un flusso di traffico. In pratica il network calculus pu`o essere visto come l’applicazione del-la min e max -algebra ai problemi legati al networking e in particodel-lare aldel-la gestione della Qualit`a del Servizio in Internet. Esso appartiene all’insie-me degli struall’insie-menti matematici a volte indicati coall’insie-me “algebre esotiche” e permette di effettuare calcoli deterministici usando pochi semplici concetti. Alcuni esempi di risultati importanti sono le propriet`a “shapers keep arrival constraints” e “pay bursts only once” che verranno esaminate pi`u avanti. L’analisi deterministica porta a calcolare dei limiti superiori sul ritardo spe-rimentato da un pacchetto che attraversa una rete o sulla dimensione del buffer richiesta. Si tratta cio`e di risultati che si riferiscono al cosiddetto

worst case (caso peggiore) e sono dunque di tipo conservativo.

Di seguito vengono presentati il formalismo, la nomenclatura e gli ele-menti di base del Network Calculus.

1.1

Basi del Calcolo Min-plus

In questo paragrafo vengono introdotte le definizioni e le operazioni di base dell’algebra min-plus; per una trattazione dettagliata si rimanda a [5, 3].

Le funzioni con cui si avr`a a che fare sono, data la causalit`a dei sistemi reali, principalmente funzioni nulle per valori negativi della variabile indi-pendente e inoltre, poich´e si tratti di flussi di traffico che arrivano in un nodo oppure di servizio offerto in un dato intervallo, saranno anche crescenti in senso lato.

Una funzione f `e crescente in senso lato se e solo se f (s) ≤ f(t) per ogni s≤ t. L’insieme delle funzioni crescenti in senso lato e nulle per t ≤ 0

(dove t `e la variabile indipendente) viene indicato con F . Il parametro t pu`o essere continuo o discreto, in quest’ultimo caso sarebbe pi`u corretto parlare di sequenza piuttosto che di funzione.

Nei casi pratici risulta conveniente usare modelli tempo-discreti quando si ha a che fare con pacchetti di dimensione fissa, mentre nel caso di pacchetti con dimensione variabile `e preferibile ricorrere a modelli tempo-continui.

In ambito min-plus vengono usate spesso le seguenti notazioni:

inf per l’estremo inferiore di un insieme;

il simbolo ∧ equivalentemente per l’estremo inferiore o il minimo, qualora quest’ultimo esista;

sup per l’estremo superiore di un insieme;

il simbolo ∨ equivalentemente per l’estremo superiore o il massimo, qualora quest’ultimo esista;

1.1.1 Alcune funzioni di F

Prima di passare al network calculus vero e proprio `e opportuno a questo punto introdurre alcune funzioni appartenenti all’insieme F e di particolare interesse pratico.

Funzione Peak rate

λ_C(t)

Ct se t > 0

0 altrimenti

per qualche C≥ 0.

Funzione Burst delay

δ_T(t)

+∞ se t > T

per qualche T ≥ 0.

λ_C

bit

t Figura 1.1: Funzione Peak rate

δ_T

bit

t T

Figura 1.2: Funzione Burst delay

Funzione Rate-latency β_R,T(t)

R(t− T ) se t > T 0 altrimenti per qualche R≥ 0 e T ≥ 0. Funzione Affine γ_r,b(t)

rt + b se t > 0 0 altrimenti per qualche r≥ 0 e b ≥ 0.

Combinando le funzioni di base appena introdotte `e possibile ottenere funzioni pi`u generali, lineari a tratti, appartenenti ad F , come mostrato nel semplice esempio di figura 1.5, dove si ha:

h(t) = (β_R,T∧ γ_r,b)(t)

con1 R ≥ r; il punto di intersezione tra β_R,T e γ_b,r ha ascissa t = (b +

RT )/(R− r).

β_R,T

bit

t T

R

Figura 1.3: Funzione Rate-latency

γr,b bit

t

b

Figura 1.4: Funzione affine

γr,b βR,T bit t t T b h

Figura 1.5: Combinazione di funzioni

Per le funzioni crescenti in senso lato non si pu`o definire una funzione inversa, ma risulta comunque utile definire una pseudo-inversa secondo la seguente:

pseudo inversa `e la funzione

f−1(x) = inf{t tale che f(t) ≥ x}.

1.1.2 Operazioni di base

Per la caratterizzazione, mediante il network calculus, dei sistemi di rete e dei traffici che li attraversano `e fondamentale la seguente operazione:

Definizione 1.1.2 (Convoluzione min-plus) Date due funzioni f e g appartenenti all’insieme F , si definisce convoluzione min-plus tra f e g la funzione

(f ⊗ g)(t) = inf

0≤s≤t{f(t − s) + g(s)} (1.1)

Notare che per t < 0, (f ⊗ g)(t) = 0.

Si pu`o dare un’interpretazione grafica di f ⊗ g osservando che per un dato valore s, il grafico di f (s) + g(t−s) si ottiene traslando il grafico di g(t) in modo da spostare l’origine degli assi nel punto (s, f (s)), la convoluzione si ottiene prendendo il minimo puntuale di tutte le traslazioni (fig. 1.6).

La convoluzione min-plus ⊗ gode di alcune importanti propriet`a, di cui ne vengono elencate solo alcune [5]; date le funzioni f, g, h ∈ F valgono le seguenti propriet`a:

1. la chiusura rispetto all’insieme F , f⊗ g ∈ F 2. l’associativit`a, (f⊗ g) ⊗ h = f ⊗ (g ⊗ h) 3. l’esistenza dell’elemento neutro δ<sub>0</sub>, f ⊗ δ<sub>0</sub> = f 4. la commutativit`a, f⊗ g = g ⊗ f

5. l’isotonicit`a, se f ≤ g allora f ⊗ h ≤ g ⊗ h `

E interessante notare che:

 la convoluzione di una generica funzione f di F con una funzione burst delay equivale ad operare una traslazione verso destra di un valore pari

a T :

(f ⊗ δ_T)(t) = inf

0≤s≤t{f(t − s) + δT(s)} = f(t − T ).

 la funzione , definita come (t) = +∞ se t ≥ 0 e (t) = 0 se t < 0,

risulta essere assorbente, f ⊗  = .

Esempio di convoluzione

Si introduce a scopo esemplificativo un esempio di calcolo:

Dalla definizione di convoluzione: h(t) = inf 0≤s≤t  γ_r,b(t− s) + (λ_R⊗ δ_T)(s) = inf 0≤s≤t  γ_r,b(t− s) + inf 0≤u≤s(λR(s− u) + δT(u)) 

Per semplicit`a di notazione si riporta separatamente il calcolo della convoluzione interna distinguendo due casi:

caso 1a: 0≤ s ≤ T

inf

0≤u≤s{λR(s− u) + δT(u)} = inf0≤u≤s{R(s − u) + 0} = 0

essendo δ_T(s) = 0 per s≤ T.

caso 2a: s > T

inf

0≤u≤s{λR(s− u) + δT(u)} = inf0≤u≤s{R(s − u) + δT(u)} = R[s − T ]

globalmente il risultato si pu`o scrivere: inf

0≤u≤s{λR(s− u) + δT(u)} = R[s − T ] +_{= β}

R,T(s)

il risultato `e rappresentato nella figura 1.7. Dunque la convoluzione esterna sar`a:

h(t) = γ_r,b(t)⊗ β_R,T(t)

e anche questa volta conviene dividere in due casi il calcolo.

Caso 1b: 0≤ t ≤ T γ_r,b(t)⊗ β_R,T(t) = inf 0≤s≤t{γr,b(t− s) + R[s − T ] + = inf 0≤s≤t{γr,b(t− s) + 0} = 0

δ_{T λ} R _β R,T = λR⊗ δT bit t T

Figura 1.7: Semplice convoluzione (λ_R⊗ δ_T)(t)

caso 2b: t > T γ_r,b(t)⊗ β_R,T(t) = inf 0≤s≤t{γr,b(t− s) + βR,T(s)} = inf 0≤s≤T{b + r(t − s) + R[s − T ] +_{} ∧ inf} T ≤s<t{b + r(t − s) + R[s − T ] +_} ∧ inf s=t{γr,b(t− s) + R[s − T ] +_} = inf 0≤s≤T{b + r(t − s) + 0} ∧ infT ≤s<t{b + (R − r)s + rt − RT } ∧ {0 + Rt− T} ={b + r(t − T )} ∧ {b + (R − r)T + rt − RT } ∧ {Rt− T} ={b + r(t − T )} ∧ {Rt− T}.

γ_r,b β_R,T bit t T b b− rT h = β_R,T ⊗ γ_r,b Figura 1.8: Convoluzione h = γ_r,b⊗ (λ_R⊗ δ_T) `

E da notare che nel calcolo sono stati considerati separatamente2 gli intervalli su cui almeno una delle due funzioni risulta nulla ed `e par-ticolarmente importante considerare il caso in cui s = t poich`e non si deve dimenticare che γ_r,b(0) = 0.

Definizione 1.1.3 (Funzione sub-addittiva) Data una funzione (o una sequenza) f di F si dice che essa `e sub-additiva se e solo se f (t + s) ≤ f (t) + f (s) per ogni s, t≥ 0.

`

E interessante notare che tale definizione equivale a imporre che sia f ≤ f ⊗f in cui vale il segno di uguaglianza se f (0) = 0.

Data una funzione f ∈ F , se f(0) = 0 allora f ≥ f ⊗ f ≥ 0 infatti (f ⊗ f)(t) = inf

0≤s≤t{f(t − s) + f(s)}

2_{Tale separazione `e possibile grazie alla validit`a della formula di Fubini per l’estremo}

inferiore, per cui dato un sottoinsieme non vuoto S di R e una funzione f : S → R, se {S_n}_n∈N `e un insieme di sottoinsiemi di S la cui unione coincide con S, allora infs∈S˘f(s)¯= infn∈N

n

= f (t)∧ inf

0<s≤t{f(t − s) + f(s)} ≤ f(t).

Da questa osservazione deriva la seguente:

Definizione 1.1.4 (Chiusura sub-addittiva) Data una funzione (o una sequenza) f di F , la sua chiusura sub-additiva f , definita come

f = δ₀∧ (f ⊗ f) ∧ (f ⊗ f ⊗ f) ∧ · · · = inf

n≥0{f

(n)_{} (1.2)}

dove con f(n) si `e indicata la funzione ottenuta operando (n− 1) volte la convoluzione di f con se stessa e per convenzione si `e assunto f(0) = δ₀ e f(1) = f .

In maniera immediata, dalla definizione, deriva che f ≤ f, f ∈ F e f `

e sub-additiva. Inoltre si pu`o dimostrare che f `e la pi`u grande funzione sub-additiva pi`u piccola di f tale che f (0) = 0 (teorema 3.1.10 [5]).

Definizione 1.1.5 (Deconvoluzione min-plus) Date due funzioni (o se-quenze) f e g appartenenti all’insieme F , si definisce deconvoluzione min-plus tra f e g la funzione

(f g)(t) = sup

u≥0{f(t + u) − g(u)}. (1.3)

`

E da notare che tale operazione non gode n´e della propriet`a di chiusura in

F , perch´e il risultato non `e necessariamente nullo per t≤ 0, n´e ovviamente della propriet`a commutativa.

Esempio di deconvoluzione

Si d`a il seguente come semplice esempio di calcolo:

nell’ipotesi che 0 < r < R. Dalla definizione di convoluzione: h(t) = sup u≥0  γ_r,b(t + u)− β_R,T(u) = sup u≥0  γ_r,b(t + u)− R[u − T ]+ = sup 0≤u≤T  γ_r,b(t + u)− R[u − T ]+ ∨ sup u>T  γ_r,b(t + u)− R[u − T ]+ = sup u≥0  γ_r,b(t + u) ∨ sup u>T  γ_r,b(t + u)− Ru + RT =γ_r,b(t + T ) ∨ sup u>T  γ_r,b(t + u)− Ru + RT.

Distinguiamo a questo punto due casi:

caso 1: t≤ −T essendo γ_r,b(t + T ) = 0 si ha (γ_r,b β_R,T)(t) = 0 ∨ sup T <u≤−t{γr,b(t + u)− Ru + RT } ∨ sup u>−t{γr,b(t + u)− Ru + RT } = 0 ∨ sup

T <u≤−t{0 − Ru + RT } ∨ supu>−t{b + r(t + u) − Ru + RT } = 0 ∨ 0 ∨ {b + Rt + RT } = [b + R(t + T )]+

caso 2: t >−T

(γ_r,b β_R,T)(t) ={b + r(t + T )} ∨ sup

u>T{b + r(t + u) − Ru + RT } ={b + r(t + T )} ∨ {b + r(t + T ) − RT + RT } = b + r(t + T ).

Il risultato `e mostrato nella figura 1.9.

Due ulteriori parametri importanti nell’ambito del network calculus, in particolare nel calcolo di alcuni bound, sono la massima deviazione verticale e orizzontale tra i grafici di due funzioni (fig. 1.10).

γ_r,b β_R,T bit t T −T b b + rT −T − b R β_R,T⊗ γ_r,b Figura 1.9: Deconvoluzione h = γ_r,b β_R,T

Definizione 1.1.6 Date due funzioni (o sequenze) f e g di F , si definiscono le seguenti quantit`a: Deviazione verticale v(f, g) = sup t≥0{f(t) − g(t)} (1.4) Deviazione orizzontale h(f, g) = sup

t≥0{inf{d ≥ 0 tale che f(t) ≤ g(t + d)}}. (1.5) Prima di passare alle nozioni base del network calculus `e utile infine introdurre una classe di funzioni di cui si far`a uso:

Definizione 1.1.7 (Funzioni “good”) Una funzione α∈ F si dice “good” se soddisfa una delle seguenti condizioni equivalenti:

1. α `e sub-additiva con α(0) = 0. 2. α = α⊗ α

t bit h(α, β) v(α, β) β α

Figura 1.10: deviazione orizzontale e verticale

3. α = α α

4. α = α (ovvero α coincide con la sua chiusura subadditiva).

1.2

Curve di Arrivo

Dopo aver introdotto le operazioni di base della min-plus algebra, si passa ora alla caratterizzazione dei flussi di traffico.

Nell’ambito del network Calculus, piuttosto che fare riferimento al rate istantaneo di un flusso, risulta pi`u comodo descrivere i traffici per mezzo della funzione cumulativa R(t), definita come il numero di bit osservati a partire da un’origine temporale arbitraria fino all’istante t. Per convenzione si assume R(0) = 0 e, naturalmente, nel caso di traffici reali R(t) sar`a una funzione crescente in senso lato, quindi appartenente all’insieme F definito nel paragrafo 1.1 a pag. 3.

Come gi`a accennato, l’approccio seguito per la caratterizzazione dei flussi `

e di tipo deterministico. I sistemi reali presentano sempre una certa granu-larit`a, quindi sarebbe giustificabile l’assunzione di un modello discreto per la funzione R(t), tuttavia dal punto di vista della trattazione matematica spesso risulta pi`u semplice avere a che fare con funzioni tempo-continue, se inoltre R(t) `e anche continua, si parla di “modello fluido”. In generale `

e comunque sempre possibile passare da un modello tempo-continuo a uno tempo-discreto mediante un processo di campionamento.

Per essere in grado di fornire delle garanzie di servizio ai flussi dati `e ovviamente necessario che vengano introdotte delle limitazioni sugli stes-si. Ci`o pu`o essere ad esempio ottenuto usando il meccanismo del token (o

leaky) bucket (tecnica utilizzata sia nel mondo Intserv che Diffserv per

de-finire flussi conformi). Esso consiste nel risagomare il flusso, per mezzo di un apposito dispositivo, che pu`o essere un policer o uno shaper, in modo che soddisfi determinati requisiti. Nel senso sopra specificato le limitazioni imposte derivano dagli accordi contrattuali tra i fonitori di servizio Internet (ISP) e gli utenti. Ma limitazioni sui flussi possono derivare anche dai limiti fisici dei dispositivi di rete.

In generale le limitazioni cui un flusso `e soggetto possono essere descritte mediante il concetto di curva d’arrivo, che pone un limite alla quantit`a di dati su una finestra temporale, in funzione della dimensione della finestra stessa.

Definizione 1.2.1 (Curva d’arrivo) Data una funzione α ∈ F (dunque nulla per t < 0 e crescente in senso lato), si dice che un flusso R `e α-smooth

o equivalentemente ha α come curva d’arrivo se e solo se per ogni s≤ t:

R(t)− R(s) ≤ α(t − s). (1.6)

Figura 1.11: Definizione di curva d’arrivo

Dire che un flusso dati ha α(t) = rt come curva d’arrivo (fig. 1.11) significa che i bit osservati su una finestra temporale di dimensione arbitraria

τ sono limitati dalla quantit`a rτ . Se ad esempio si sa che un flusso arriva attraverso un link con bit-rate pari a C bit/s, a livello di bit (cio`e con un modello fluido) si pu`o dire che il flusso `e α-smooth con α(t) = Ct. Poich`e nei casi pratici quello che si osserva al ricevitore sono pacchetti e non bit `e necessario tener conto anche di un effetto dovuto alla pacchettizzazione (vedi par.1.7 di [5]). Se M `e la massima dimensione dei pacchetti allora la curva d’arrivo assume la forma α(t) = Ct+M . D’altra parte una limitazione di tipo leaky bucket impone una curva d’arrivo del tipo α(t) = rt + b dove

r coincide con il rate medio di lungo termine e b con il burst massimo

ammissibile. Dalla combinazione dei due deriva la tipica caratterizzazione

T-SPEC dei flussi Intserv, per i quali α(t) = min{Ct + M, rt + b}.

tanto migliore quanto pi`u il limite `e vicino alla massima quantit`a di dati che pu`o realmente essere osservata su un intervallo di una data durata, ovvero quanto pi`u il bound `e stretto. Intuitivamente dunque la minima curva d’arrivo per un flusso R(t) sar`a data da:

α_min(t) = sup

u≥0{R(t + u) − R(u)}

dove t indica proprio la durata dell’intervallo. Ci`o pu`o essere formalmen-te dimostrato usando gli strumenti dell’algebra min-plus e viene espresso dicendo che la minima curva d’arrivo per un flusso R(t) coincide con la deconvoluzione di R(t) con se stesso (cfr. teorema 1.2.2 in [5]), in formule:

α_min(t) = (R R)(t).

Questa propriet`a pu`o essere utile praticamente per determinare la curva d’arrivo di una traccia reale nota da misure sperimentali.

1.3

Curve di Servizio

Al fine di poter valutare la qualit`a del servizio che pu`o essere effettivamente garantita ai vari utenti di una rete e gestire adeguatamente le risorse a di-sposizione, `e necessario disporre, oltre che della caratterizzazione dei traffici, di un modello degli elementi di rete, che sia allo stesso tempo il pi`u possibile accurato e semplice da trattare. Il concetto di curva di servizio nasce pro-prio per astrarre il comportamento di ciascun nodo componente una rete di comunicazione.

In questo capitolo viene presentata solo la definizione pi`u generale di cur-va di servizio, essenziale per enunciare i primi risultati del network calculus. Si rimanda ai capitoli successivi per una panoramica pi`u esaustiva sulla sua

evoluzione in letteratura e alcune considerazioni sulla sua interpretazione pratica.

Il concetto di curva di servizio viene espresso nella sua forma pi`u generale ([14], [15] [16]) secondo la seguente definizione:

Definizione 1.3.1 (Curva di servizio) Dato un sistema S (ovvero un ele-mento di rete, che pu`o essere un singolo server, ma anche un’intera sotto-rete) e un flusso attraverso S con funzione cumulativa d’ingresso e d’uscita rispettivamente R e R∗. Sia β(t) una funzione non-negativa crescente in senso lato con β(0) = 0; si dice che il sistema S offre al flusso considerato una curva di servizio β se e solo se:

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

s≤t{R(s) + β(t − s)}. (1.7)

Figura 1.12: Definizione di curva di servizio

In termini pratici, tale definizione significa se β(t) `e continua, che esiste

s≤ t tale che R∗(t)≥ R(s) + β(t − s). Il concetto di curva di servizio rim-piazza l’analisi per busy period tipica della teoria delle code con il vantaggio

di potersi applicare anche a sistemi complessi in quanto gode di semplici propriet`a di concatenazione.

A volte si parla anche di elemento curva di servizio per indicare un dispositivo generico che pu`o essere usato per descrivere il comportamento di una variet`a di elementi di rete quali ad esempio link, shaper (regolatori di flusso) o router. La curva di servizio sopra definita fornisce una misura della quantit`a di servizio allocata ad un dato flusso e viene in particolare anche detta “curva di servizio minima” in quanto permette di ottenere un bound inferiore del servizio ricevuto dal flusso stesso.

Un concetto meno generale, ma pi`u intuitivo risulta essere quello di strict

service curve (letteralmente “curva di servizio stretta”), che definisce un

limite inferiore al numero di bit serviti in un dato intervallo durante il quale la coda del flusso considerato non `e mai vuota:

Definizione 1.3.2 (Strict service curve) Si dice che un sistema S offre una strict service curve ad un dato flusso se, in un qualunque intervallo di durata u durante il quale il glusso abbia ininterrottamente backlog, vengono serviti almeno β(u) bit, in formule:

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

Come anticipato, tale concetto `e pi`u restrittivo di quello di curva di servizio, infatti si pu`o agevolmente dimostrare che se un sistema offre ad un flusso una data funzione come curva di servizio in senso stretto, allora offre allo stesso flusso la stessa funzione anche come curva di servizio. Un nodo

GPS offre ad esempio una strict service curve della forma β(t) = rt dove r

`

Per poter schematizzare adeguatamente tutti gli elementi di una rete `e utile introdurre anche il concetto di curva di servizio massima che permette, in particolare, di tener conto di ritardi costanti e rate massimi ammissibili.

Definizione 1.3.3 (Curva di servizio massima) Dato un sistema S e un flusso attraverso S con funzione cumulativa d’ingresso e uscita rispetti-vamente R ed R∗, si dice che S offre una curva di servizio massima γ se e solo se γ∈ F e vale:

R∗(t)≤ (R ⊗ γ)(t) = inf

s≤t{R(s) + γ(t − s)}. (1.8)

1.4

Bound Fondamentali

Prima di poter presentare i primi semplici, ma importanti, risultati del

net-work calculus `e necessario introdurre ancora un paio di grandezze di utilit`a pratica: il backlog e il virtual delay (ritardo virtuale).

Il backlog (letteralmente “lavoro arretrato”) di un sistema rappresenta la quantit`a di bit che ad un dato istante sono presenti all’interno del sistema in attesa di essere serviti. Se R ed R∗ sono rispettivamente le funzioni cumulative dei flussi in ingresso e in uscita, il backlog B(t) all’istante t si esprime, per un sistema senza perdite, come:

B(t) = R(t)− R∗(t).

Il virtual delay d(t) calcolato ad un istante t `e il ritardo che verrebbe sperimentato da un bit che arriva all’istante t stesso nell’ipotesi che tutti i bit arrivati precedentemente vengano serviti prima: in pratica il virtual

In First Out). In formule:

d(t) = inf{τ ≥ 0 : R(t) ≤ R∗(t + τ )}.

Nel caso particolare in cui le funzioni d’ingresso e d’uscita siano continue,

d(t) coincide con il pi`u piccolo valore per cui R∗t + d(t)= R(t).

A questo punto `e possibile introdurre i tre bound fondamentali del

net-work calculus che riguardano il backlog, il ritardo e il flusso d’uscita di un

sistema senza perdite e con garanzie sul servizio.

Teorema 1.4.1 (Bound fondamentali) Dato un sistema che offra β co-me curva di servizio e un flusso in ingresso con funzione cumulativa R(t) che abbia α come curva d’arrivo, valgono i seguenti bound:

Bound sul Backlog. Per ogni t il backlog `e limitato dalla deviazione ver-ticale tra la curva d’arrivo e quella di servizio:

B(t) = R(t)− R∗(t)≤ sup

s≥0{α(s) − β(s)} = (α  β)(0). (1.9)

Bound sul Ritardo. Il virtual delay `e, per ogni t, minore o uguale della deviazione orizzontale tra α e β, ovvero:

d(t)≤ h(α, β). (1.10)

Nel caso in cui la curva d’arrivo α sia “good” e la curva di servizio β sia crescente in senso lato e tale che β(0) = 0, allora i due bound sopra elen-cati risultano “tight” (letteralmente stretti) nel senso che esiste un sistema causale che offra una curva di servizio β e che, per un dato ingresso R(t) li-mitato da α, ammetta un’uscita R∗(t) tale da raggiungere entrambi i bound.

In particolare ci`o si verifica per R(t) = α(t) (la sorgente `e in tal caso detta

Bound sul Flusso d’Uscita. Il flusso d’uscita presenta la seguente fun-zione come curva d’arrivo:

α∗(t) = (α β)(t). (1.11)

Tale bound si dimostra (Teorema 1.4.5 [5]) essere “tight” se sono veri-ficate insieme le seguenti condizioni:

 α `e “good” e continua a sinistra,

 β `e crescente in senso lato con β(0) = 0,  αα non `e limitata superiormente3.

Se si suppone anche che il sistema offra una curva di servizio massima pari a γ, il bound sul flusso in uscita pu`o essere ridotto a:

α∗(t) =(α⊗ γ)  β(t). (1.12)

Nella figura 1.13 sono riportati i bound relativi ad un semplice esempio: un nodo con curva di servizio β_R,T serve un flusso limitato da un leaky bucket che ha quindi α = γ_r,b come curva d’arrivo.

I bound sopra enunciati possono essere particolarmente utili per il dimen-sionamento degli elementi di rete; ad esempio quello sul backlog permette di determinare la massima dimensione del buffer richiesto in un sistema.

Ancora, possono essere d’aiuto per l’implementazione di algoritmi di

admission control. In uno scenario Intserv in particolare, si assume che i

nodi sul percorso del flusso offrano una curva di servizio β_Rn,Tn del tipo

3_{Con il simbolo si intende la deconvoluzione max-plus definita, per f, g ∈ F , come}

γ_r,b β_R,T bit t b b + rT d = T + b/R B = b + rT α∗

Figura 1.13: Bound per un flusso limitato da una curva affine servito in un elemento del tipo rate-latency

rate-latency [17]. Una volta noti i parametri T-SPEC del flusso che richiede

il servizio, il bound sul ritardo pu`o essere espresso in funzione di un rate

R incognito che pu`o essere determinato in base ai limiti sul ritardo

end-to-end richiesti dal flusso. Tale rate dovr`a poi essere garantito in tutti i nodi intermedi; se ci`o non `e possibile il flusso verr`a rifiutato (Si rimanda al paragrafo 2.2 di [5] per dettagli sull’argomento).

1.5

Concatenazione di elementi

Quando `e stata introdotta la curva di servizio `e stato anche sottolineato il fatto che tale concetto si possa applicare con notevoli vantaggi a sistemi complessi. In particolare un sistema ottenuto dal collegamento in cascata di pi`u elementi, gode di un’importante propriet`a, nota sotto il nome di Pay

Teorema 1.5.1 (Concatenazione di Nodi) Dato un flusso che attraver-si due attraver-sistemi S₁ e S₂ in cascata (fig. 1.14), che offrano come curva di servizio rispettivamente β₁ e β₂, il sistema concatenato offre al flusso una curva di servizio β pari alla convoluzione tra le due: β = β₁⊗ β₂.

Figura 1.14: concatenazione di due nodi

Infatti all’uscita del primo nodo si ha R₁≥ R⊗β₁e all’uscita del secondo nodo

R∗≥ R₁⊗ β₂ ≥ (R ⊗ β₁)⊗ β₂ = R⊗ (β₁⊗ β₂).

Ovviamente il teorema pu`o essere iterato nel caso di n nodi, per cui β = β₁⊗

. . .⊗ β_n. Inoltre, poich`e la convoluzione gode della propriet`a commutativa, si pu`o anche affermare che il ritardo end-to-end non dipende dall’ordine in cui i nodi sono concatenati.

In maniera del tutto analoga si dimostra che tale propriet`a di concate-nazione vale anche per la curva di servizio massima:

Pay bursts only once

Nella maggior parte dei casi pratici si assumono curve di servizio del tipo

Rate-latency, che, essendo β_R,T = δ₀⊗ λ_R, possono essere interpretate co-me la concatenzione di un nodo con ritardo garantito ≤ T e uno con rate garantito R. Considerando dunque un sistema costituito dalla concatena-zione di due nodi, come mostrato in figura 1.15 (dove α = γ_r,b `e la curva d’arrivo del flusso in ingresso e β_Ri,Ti con i = 1, 2 le curve di servizio dei due nodi) e procedendo al calcolo del bound sul ritardo prima come somma dei ritardi dei due nodi, poi sfruttando la curva di servizio β risultante dalla concatenazione si ottengono i risultati di seguito riportati.

Figura 1.15: pay bursts only once

Somma di ritardi: il bound sul ritardo al primo nodo `e banalmente (vedi fig. 1.13) D₁ = b₁/R₁ + T₁. Applicando la formula del bound sul flusso d’uscita si trova che il flusso uscente dal primo nodo soddisfa

la curva d’arrivo α∗(t) = [γ_r,b  β_R1,T1]+ = b + rT₁+ rt = γ_r,b+rT1 (vedi esempio a pag. 11). Quindi il ritardo al secondo nodo sar`a

D₂ = (b + rT₁)/R₂+ T₂ e il ritardo totale la somma dei due:

D₁+ D₂ = b₁/R₁+ T₁+ (b + rT₁)/R₂+ T₂.

Concatenazione: calcolando la curva di servizio risultante, che da semplici

passaggi risulta

β_R,T(t) = (β_R1,T1⊗ β_R2,T2)(t) = β_{min(R1,R2),T1+T2}(t) il bound sul ritardo assume la forma

D = b/R + T

dove si `e assunto R = min(R<sub>1</sub>, R<sub>2</sub>) e T = T<sub>1</sub>+ T<sub>2</sub>. `

E immediato verificare che D < D₁+ D₂, ovvero il bound calcolato conside-rando la curva di servizio globale risulta essere migliore di quello ottenuto considerando ogni elemento singolarmente. Il principio va sotto il nome di

pay bursts only once perch´e nella formula del ritardo D globalmente calco-lato compare un solo termine del tipo b/R contrariamente a quanto accade nel caso in cui il ritardo complessivo sia calcolato come somma, in cui com-paiono due termini dello stesso tipo oltre ad un termine ulteriore dovuto all’aumento di burstiness nel primo nodo. Dall’espressione di D si deduce che tale termine di fatto non influenza il ritardo globale.

1.6

Shaper

Naturalmente non ci si pu`o aspettare che il traffico generato dalle sorgenti soddisfi i limiti imposti da curve d’arrivo fissate a priori, d’altra parte, come

gi`a accennato, per la corretta gestione della QoS `e fondamentale che ven-gano presi degli accordi tra i fornitori di servizio e gli utenti. Da qui nasce l’esigenza di avere dispositivi in grado di sagomare opportunamente il traffi-co in modo che le sorgenti possano descrivere mediante un inviluppo il flusso per il quale richiedono un certo servizio. Solitamente nei punti di accesso alla rete vengono compiute operazioni di controllo, anche dette di policing, atte a verificare che un utente non invii pi`u traffico di quanto non abbia concordato. Il traffico in eccesso pu`o essere scartato oppure “marcato”, in modo che ad esso venga associata una pi`u alta probabilit`a di perdita, ma trasmesso comunque. Si rende quindi necessario forzare in qualche modo il flusso perch´e soddisfi determinate limitazioni.

A volte `e anche necessario che un traffico venga risagomato all’interno della rete perch´e, in seguito all’attraversamento di alcuni nodi, non risulta pi`u conforme. Un dispositivo che forza la sua uscita ad avere una data curva d’arrivo σ, ritardando l’inoltro di eventuali bit (memorizzati in un buffer ) che violerebbero tale costrizione, viene detto shaper (regolatore) con curva di shaping σ.

Un tale dispositivo viene in particolare detto greedy shaper se, pur nel rispetto dei limiti stabiliti, invia in uscita i bit memorizzati non appena possibile.

Un caso pratico particolarmente importante, come gi`a sottolineato, `e quello del controllore leaky bucket, schematizzato come un bucket (letteral-mente “secchio”) di dimensione b in cui arrivano token ad un rate costante r (fig. 1.16). Questo meccanismo permette di smussare (“smooth”) il traffico e forzare l’uscita ad avere come curva d’arrivo una funzione affine γ(t) = b+rt. La dimensione del bucket b coincide praticamente con la massima quantit`a

di bit che possono essere trasmessi “contemporaneamente”. b l_i l_i R _R∗ r

Figura 1.16: Leaky bucket

Con gli strumenti del network calculus, si pu`o dimostrare (vedi sezione 1.5.2 in [5]) che se il buffer di un greedy shaper, con curva di shaping σ, `e vuoto all’istante t = 0 ed `e grande abbastanza da impedire perdite, allora, detta R(t) la funzione cumulativa del flusso al suo ingresso, quella del flusso d’uscita risulta:

R∗(t) = (R⊗ σ)(t) (1.13) dove σ `e la chiusura sub-additiva di σ. Tale espressione verifica inoltre la propriet`a della curva di servizio con β = σ.

Altre propriet`a delle curve d’arrivo

Prima di enunciare importanti propriet`a di interesse pratico dei greedy

sha-per `e opportuno fare alcune precisazioni sulle curve d’arrivo. Un risultato fondamentale consiste nel fatto che una qualunque curva d’arrivo α pu`o essere sostituita dalla sua chiusura sub-additiva α, il che deriva dalle due seguenti osservazioni:

(segue direttamente dalla definizione stessa di convoluzione e di curva d’arrivo).

2. Se α₁ e α₂ sono entrambe curve d’arrivo per un flusso R, allora lo `e anche α₁⊗ α₂ (segue dalla chiusura dell’operatore di convoluzione in

F dall’associativit`a e dall’isotonicit`a).

Dalle due precedenti osservazioni segue che se α `e curva d’arrivo allora lo `e anche α = inf_n≥0α(n). L’opposto `e ovvio essendo α≤ α.

Propriet`a dei greedy shaper

Poich´e, come `e stato appena mostrato, una qualunque curva d’arrivo pu`o es-sere sostituita dalla sua chiusura sub-additiva, nell’enunciare le propriet`a dei

greedy shaper si pu`o fare riferimento, senza perdita di generalit`a, a funzioni di shaping σ che siano good.

 Se un flusso α-smooth attraversa un greedy shaper con curva di shaping σ, l’uscita sar`a ancora α-smooth (vedi fig. 1.17).

R∗(t) = (R⊗ σ)(t) ≤ (R ⊗ α ⊗ σ)(t) = (R∗⊗ α)(t)

dove la disugualianza segue dalla propriet`a di isotonicit`a dell’operatore di convoluzione. I greedy shaper dunque preservano le curve d’arrivo, ci`o pu`o anche essere espresso dicendo che l’effetto di uno shaper non pu`o essere annullato da un altro shaper.

 Se si introducono sul percorso del flusso dei greedy shaper con curva

di shaping σ maggiore o uguale della curva d’arrivo α del flusso al-l’ingresso della rete, ovvero la risagomatura `e solo parziale, allora non

Figura 1.17: shaper

aumenta n´e il ritardo end-to-end n´e il fabbisogno totale di memoria (vedi teorema 1.5.2 in [5]). Tali shaper possono essere necessari per controllare l’eventuale “accumulo” di burstiness4.

 Regolatori con curva di shaping σ(t) = min_m=1,...,M(r_mt + b_m) (fig. 1.18) possono essere implementati come una serie di regolatori leaky

bucket. Questo deriva dal fatto che M shaper collegati in cascata, di

cui l’m-esimo con curva σ_m good, sono equivalenti, per la propriet`a associativa dell’operazione di convoluzione, ad un unico shaper con curva σ = σ<sub>1</sub>⊗. . .⊗σ<sub>M</sub>. Infatti se R `e la funzione cumulativa d’ingresso all’intero sistema e R∗ quella d’uscita, vale R∗ = ((R⊗ σ₁)⊗ . . .) ⊗

σ_M = R⊗ (σ₁ ⊗ . . . ⊗ σ_M). Nel caso particolare di funzioni affini

γ_rm,bm, che sono star shaped5 e nulle nell’origine, vale (teorema 3.1.6 [5]) γ_r1,b1 ⊗ . . . ⊗ γ_rM,bM = min{γ_rm,bm}.

Quando la caratterizzazione ingresso-uscita di un sistema `e della forma

R∗ = R⊗ β, nell’ambito dell’algebra min-plus si dice che il sistema `e lineare

4_{Per rendersi conto di come si possano originare aumenti di burstiness basta considerare}

l’esempio di fig. 1.13 a pag. 23 e vedere che il burst (b+rT ) della curva d’arrivo dell’uscita risulta maggiore di quello (b) della curva d’arrivo dell’ingresso.

5_{Una funzione f∈ F si dice star shaped se e solo se f(t)/t `e crescente in senso lato per}

Figura 1.18: Curva di shaping di una serie di leaky bucket

tempo-invariante. In tal senso la caratterizzazione ingresso-uscita di un

greedy shaper `e del tutto analoga a quella che si pu`o ottenere per un circuito elettrico mediante la teoria dei sistemi, la curva di shaping che risulta essere anche la curva di servizio del sistema `e di fatto l’analogo della risposta impulsiva di un circuito elettrico. In particolare, come `e stato osservato, valgono analoghe propriet`a di concatenazione.

1.7

Packetizer

In generale nei casi pratici si deve tener conto del fatto che i pacchetti di un flusso hanno dimensione variabile. Ci`o avr`a naturalmente un impatto sia sulla caratterizzazione dei flussi che su quella del sistema e quindi sui bound che ne derivano.

Si assuma di osservare i flussi di ingresso e d’uscita quando l’ultimo bit di un pacchetto `e stato rispettivamente ricevuto o trasmesso. Se T<sub>i</sub> `e l’istante di arrivo dell’i-esimo pacchetto e l_i la sua lunghezza in bit, allora la funzione

cumulativa d’ingresso assume la forma:

R(t) =

i

l_i· 1_{Ti≤t}

dove 1_{{espressione}} `e una funzione indicatrice, che vale 1 se l’espressione `e vera e 0 se l’espressione `e falsa.

Data una sequenza L(n) con n ∈ N crescente in senso lato e tale che

L(0) = 0, ottenuta come somma cumulativa delle dimensioni dei

pacchet-ti (vale a dire che L(n)− L(n − 1) `e la dimensione dell’n-esimo pacchet-to), si definisce come versione pacchettizzata di un flusso R(t) la seguente espressione:

PLR(t)= sup

n∈N{L(n) · 1{L(n)≤R(t)}} (1.14) calcolata per ogni t∈ R; chiaramente, data la cusalit`a dei flussi, PLR(t)= 0 per t < 0.

In modo equivalente:

PLR(t)= L(n) ⇐⇒ L(n) ≤ R(t) < L(n + 1). (1.15)

Per packetizer (pacchettizzatore) si intende un dispositivo che trasforma l’ingresso R(t) nella sua forma pacchettizzata. Se si indica con

l_max= sup

n∈N{L(n) − L(n − 1)}

la dimensione massima che i pacchetti possono assumere, allora dalla defi-nizione stessa di flusso pacchettizzato, si ricava semplicemente la seguente propriet`a:

R(t)− l_max< PLR(t)≤ R(t).

In generale si dice che un flusso R(t) `e pacchettizzato se PLR(t)= R(t) per ogni t e la sua curva d’arrivo dovr`a presentare una discontinuit`a

nell’o-rigine pari alla dimensione massima dei pacchetti. Infatti, dato un flus-so R(t) continuo, se si suppone che la dimensione del generico pacchetto

n− esimo sia proprio l_max (ne deve esistere almeno uno se tale `e la di-mensione massima) e che t = min{t ≥ 0 tale che R(t) = L(n)} allora sar`a lim
_→0+{PLR(t)− PLR(t− )= l_max}.

Gli effetti della pacchettizzazione (ampiamente discussi in [18]) sono par-ticolarmente significativi nell’ambito della teoria relativa agli shaper e poich´e questi sono fondamentali per la gestione della QoS `e importante valutare l’entit`a di tali effetti.

Semplici relazioni si ricavano facilmente tenendo conto della massima dimensione dei pacchetti: dato un sistema combinato costituito da un siste-ma bit-by-bit e da un pacchettizzatore come in figura 1.19, assumendo che entrambi i sistemi siano di tipo FIFO e senza perdite, valgono le seguenti propriet`a:

Figura 1.19: Schematizzazione di un sistema con pacchettizzatore

1. Il per-packet delay (ritardo di un pacchetto) per il sistema combinato `

e definito come il sup_i(T_i−T_i) dove T_i e T_i sono l’istante di arrivo e di partenza dell’i-esimo pachetto e risulta essere pari al massimo virtual

delay del sistema bit-by-bit senza pacchettizzatore. Questo vuol dire

2. Detti B∗e Bil massimo backlog rispettivamente del sistema bit-by-bit e di quello combinato si avr`a B∗ ≤ B ≤ B∗+ l_max.

3. Se il sistema bit-by-bit offre al flusso una curva di servizio massima

γ e una curva di servizio minima β allora il sistema combinato

of-fre al flusso una curva di servizio massima pari a γ e una curva di servizio minima β(t) = [β(t)− l_max]+. Ci`o significa che la pacchet-tizzazione indebolisce la curva di servizio garantita di una quantit`a pari alla massima dimensione dei pacchetti. Ad esempio se un si-stema offre una curva si servizio del tipo rate latency β_R,T, inse-rendo un pacchettizzatore in cascata si avr`a una curva di servizio

β(t) = [β_R,T(t)− l_max]+ = β_{R,T +lmax/R}, quindi l’effetto `e quello di aumentare la latency di una quantit`a pari a l_max/R. Una curva di

ser-vizio del tipo rate latency `e una schematizzazione molto diffusa per

scheduler generici.

4. Se un flusso S(t) ha σ(t) come curva d’arrivo, allora la sua forma pacchettizzata PLS(t) soddisfa σ(t) + l_max1_{t > 0} come curva

d’arrivo.

A questo punto appare naturale chiedersi come mai viene data tanta enfasi alle distorsioni introdotte dalla pacchettizzazione, considerando che queste sembrano essere limitate dalla dimensione di un pacchetto. I motivi sono almeno due: in prima istanza la sagomatura di flussi con pacchetti variabili occorre ai punti di accesso della rete sia nel caso di architetture

Diffserv che Intserv, quindi `e importante capirne gli effetti dal punto di vista teorico; in secondo luogo le distorsioni possono accumularsi lungo il percorso nella rete e portare a discrepanze significative.

`

E opportuna una precisazione a proposito della prima propriet`a, in base alla quale mettere un packetizer in cascata ad un nodo non incrementa il ritardo del pacchetto in tale nodo: ci`o comunque non vuol dire che non aumenti il ritardo end-to-end in una concatenazione di pi`u nodi (fig. 1.20).

Figura 1.20: Cascata di sistemi combinati

In realt`a in una cascata di nodi combinati, quello che si pu`o trascurare ai fini del ritardo `e soltanto il packetizer dell’ultimo nodo. Ci`o pu`o essere interpretato osservando che la pacchettizzazione ritarda il primo bit di un pacchetto, il che a sua volta ritarda il processo di elaborazione nei nodi successivi (downstream). In generale si pu`o dire dunque che un packetizer non incrementa il ritardo massimo nel nodo, ma comunque incrementa il ritardo end-to-end.

In maniera del tutto analoga a quanto fatto per i sistemi bit a bit, anche nel caso di flussi pacchettizati viene definito un sistema che forza la sua uscita ad essere σ-smooth e pacchettizata secondo una data sequenza cumulativa L. Nel caso in cui tale dispositivo ritardi i pacchetti che violerebbero i vincoli imposti da σ, ma li trasmetta non appena possibile, viene detto greedy shaper pacchettizzato. La realizzazione pratica di un tale oggetto non `e immediata, ma nel caso particolare in cui la funzione di shaping σ sia “good” ed esista

una funzione σ₀ sub-additiva tale che

σ(t) = σ₀(t) + l· 1_t>0

con l > l_max, allora, considerando solo ingressi pacchettizzati, il greedy

sha-per pacchettizato pu`o essere realizzato come concatenazione di un greedy

shaper con curva di shaping σ e un pacchettizatore con sequenza L (fig.

1.21).

Figura 1.21: Realizzazione di un greedy shaper pacchettizzato in un caso particolare

In generale, purtroppo, non vale nel caso pacchettizzato la conservazione della curva d’arrivo dell’ingresso a meno che α e σ non siano concave e tali che α(0+) ≥ l_max e σ(0+) ≥ l_max. Sotto tali condizioni continuano a valere le regole di composizione degli shaper : una serie di M greedy shaper pacchettizzati di cui l’m-esimo con curva di shaping σm concava e tale che

σm(0+) ≥ l_max `e equivalente ad un greedy shaper pacchettizzato con curva di shaping σ = min_mσm.

Una definizione pratica di regolatore basato sui pacchetti, con curva di

pacchetto pu`o essere trasmesso se nel bucket c’`e uno spazio libero almeno pari alla dimensione l_i del generico pacchetto da trasmettere.

b l_i

l_i

R R∗

r

Figura 1.22: Buffered leaky bucket

Il principio di funzionamento, illustrato in figura 1.22, `e sostanzialmente duale a quello del token da spendere: il bucket perde fluido con un rate costante pari ad r, quando il livello scende al di sotto della quantit`a b− l_i (essendo b la dimensione del bucket ) il pacchetto di dimensione l_i pu`o essere trasmesso e contestualmente il bucket viene riempito di un’uguale quantit`a. Un tale dispositivo viene detto buffered leaky bucket controller basato sul riempimento del bucket [18]. Una variante di tale dispositivo, sebbene non perfettamente equivalente, era stata precedentemente definita da Cruz in [12].

A voler essere rigorosi, si dovrebbe indicare con leaky bucket un disposi-tivo la cui uscita `e sempre limitata dal rate r di perdita del bucket senza la possibili`a di trasmettere burst di dati, mentre si dovrebbe chiamare token