• Non ci sono risultati.

Uno scenario di simulazione

N/A
N/A
Protected

Academic year: 2021

Condividi "Uno scenario di simulazione"

Copied!
32
0
0

Testo completo

(1)

Uno scenario di simulazione

Il network calculus affronta elegantemente da un punto di vista teorico il problema della valutazione delle prestazioni di reti pi`u o meno complesse. In particolare offre un ottimo modello per l’analisi di uno o pi`u sistemi in cascata che servano i singoli flussi isolandoli l’uno dall’altro, come avviene nel caso dell’architettura Intserv (per una trattazione dell’argomento si rimanda al par. 2.2 di [5]).

La caratterizzazione di un sistema mediante curva di servizio prevede che l’uscita di un sistema reale possa essere limitata inferiormente da quella di un sistema lineare tempo invariante in senso min-plus secondo la relazione (vedi eq. (1.7) a pag. 18) R∗≥ R ⊗ β. Ci`o di fatto significa che un sistema che soddisfi la propriet`a di curva di servizio per una funzione β si comporta

almeno come il sistema lineare tempo invariante corrispondente, per il quale

si ricorda che la curva di servizio massima e minima coincidono per cui se ne pu`o determinare un limite inferiore una volta nota una coppia di funzioni cumulative ingresso-uscita (vedi eq. 2.1 a pag. 45).

(2)

che `e possibile fare ai morsetti esterni di un circuito misurando la risposta ad opportuni segnali di prova. Ci`o sarebbe chiaramente di grande utilit`a pratica per l’analisi e la progettazione di reti.

L’idea pi`u semplice `e quella di partire dalla definizione stessa di curva di servizio e tentare di ricavarne una possibile forma dall’osservazione di una o pi`u coppie ingresso-uscita. Purtroppo in generale ci`o non sar`a possibile per una black box (fig. 4.1), ovvero un oggetto di cui non si sappia assolutamente niente.

?

R R∗

Figura 4.1: Black box

Infatti, in generale, qualunque siano R e R∗, per un sistema reale, causale per cui R(t) = 0 per ogni t ≤ 0, la relazione

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

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

sar`a sempre banalmente soddisfatta da β(t) = 0.

Infatti nel caso in cui R sia una funzione crescente in senso lato, ovvero R ∈ F , come ovviamente avviene per un sistema reale, si avrebbe:

inf

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

Dalla definizione di curva di servizio segue che l’uscita sar`a nella peggiore delle ipotesi uguale a quella del sistema lineare tempo invariante che limita inferiormente il sistema. La tightness dei bound (vedi par. 1.4 a pag. 20)

(3)

permette di affermare che essi possono essere raggiunti, da sistemi reali causali, in corrispondenza di greedy source, ma comunque nel caso in cui il servizio offerto sia quello minimo. D’altra parte la qualit`a del servizio garantito pu`o dipendere dallo stato del sistema, ci`o significa che per poter trarre informazioni da una coppia ingresso-uscita di funzioni cumulative sar`a necessario fare in modo che il sistema si comporti nel peggior modo possibile.

Il problema della stima della curva di servizio di un sistema ignoto si sposta cos`ı sull’individuazione del cosiddetto “caso peggiore”, che in generale sar`a legato alla struttura interna, quindi al funzionamento del dispositivo sotto esame e per tale motivo pu`o dipendere da una serie innumerevole di fattori (ad esempio il numero di flussi e la dimensione dei pacchetti). Praticamente si tratterebbe di individuare la forma dell’ingresso che porti il sistema in una situazione critica spingendolo a comportarsi nel peggiore dei modi possibili1.

La semplice osservazione delle funzioni cumulative dell’ingresso e dell’u-scita non `e sufficiente per trarre conclusioni univoche sulla curva di servizio che un sistema offre ad un dato flusso. Se si facessero alcune osservazio-ni ipotizzando che il sistema si comporti come un sistema lineare tempo invariante in senso min-plus, ovviamente il bound inferiore che verrebbe de-terminato su una curva di servizio per cos`ı dire “effettiva” (βeff), tale cio`e

che R∗ = R ⊗ βeff, risulterebbe in generale maggiore di quella che `e la curva

di servizio minima del sistema. Infatti dalla definizione stessa di curva di servizio segue banalmente βeff ≥ β.

Dalle precedenti osservazioni emergono alcune delle problematiche

ti-1Per un approccio duale alla visione del mondo si pu`o far riferimento a Leibniz, Il

(4)

un sistema: l’esigenza, da un lato di una caratterizzazione che prescinda il pi`u possibile dalla particolare implementazione, dall’altro di una descrizio-ne sufficientemente accurata, tale da consentire la determinaziodescrizio-ne di bound realistici, praticamente misurabili e non eccessivamente conservativi.

Partendo proprio dalla generalit`a del modello LR (Latency Rate, descrit-to nel par. 2.3 a pag. 47), come primo passo per una verifica della propriet`a di curva di servizio sono state condotte alcune prove su un router software (linux based) in una configurazione del tutto analoga a quella presentata nei paragrafi successivi in relazione alle simulazioni (fig. 4.2). Purtroppo le misure effettuate hanno fornito valori della Start Up Latency estrema-mente variabili, con elevati picchi inverosimilestrema-mente legati al processing dei pacchetti e quindi poco attendibili come stima del caso peggiore.

Date dunque le difficolt`a insite nell’uso di una macchina general purpose, il cui comportamento `e determinato da numerosi fattori difficilmente con-trollabili o comunque ardui da mettere in conto, sembra opportuno, prima di passare ad effettuare riprove su architetture special purpose, che presentano in ogni caso incognite di tipo pratico di cui pu`o essere estremamente oneroso tener conto, ricorrere a strumenti simulativi, che permettono di valutare in maniera accurata la bont`a di bound ricavati per via teorica in relazione a dispositivi perfettamente noti.

Nelle sezioni che seguono l’attenzione viene focalizzata principalmente sullo scheduling, in riferimento specifico all’algoritmo DRR2 sulla base del-l’interesse riscontrato nella letteratura pi`u recente nei suoi confronti e in

2Una versione modificata di tale disciplina (M-DRR, Modified) viene implementata in

(5)

quelli di algoritmi simili ([38, 42, 43, 11]), cio`e frame based, per il buon compromesso raggiunto tra complessit`a e fairness.

Nel caso degli algoritmi di scheduling solitamente individuare gli ingres-si che producano il peggior comportamento posingres-sibile ingres-significa determinare, per il flusso che si vuole analizzare, la sequenza di pacchetti che, anche in relazione alle sequenze presenti sugli altri flussi trattati dallo scheduler, maggiormente stressa il sistema. Solitamente per dimostrare che determi-nati bound sulla Start Up Latency sono tight si ricorre ad opportune ipotesi sull’ordine con cui pacchetti di ben determinate dimensioni si presentano.

4.1

Verifica della propriet`

a di curva di servizio per

uno scheduler DRR

I PHB proposti per l’architettura DiffServ sono principalmente tre: EF (Ex-pedited Forwarding) [27, 28], AF (Assured Forwarding) [44] e il classico BE (Best Effort). Per tale motivo `e stato realizzato uno scenario di simulazione con tre classi di traffico. Ovviamente in generale il traffico di una certa classe di servizio non proviene da un’unica sorgente, ma ci`o `e ininfluente ai fini dell’analisi condotta, quindi si `e scelto, per semplicit`a, di identificare ciascuna delle tre classi con una ben determinata sorgente, come indicato in figura 4.2.

Nella tabella 4.1 sono riportati i valori dei parametri utilizzati per la simulazione. Purtroppo il modulo di NS (par. 4.2) che implementa lo scheduler DRR non permette di specificare valori diversi per i quantum delle varie classi, impedendo di fatto di differenziare la banda assegnata a ciascun flusso, come sarebbe invece plausibile in una situazione reale. In ogni caso

(6)

BE AF EF DRR Dest link out link 3 link 1 link 2

Figura 4.2: Scenario della simulazione

ci`o non `e una limitazione concettuale ai fini dell’analisi basata sulla nozione di curva di servizio, quello che si vuole verificare `e che sia garantito un certo servizio, qualunque esso sia.

Tabella 4.1: Parametri dello scenario

classe quantum (byte) rate di tra-smissione (Mb/s) propagation delay (ms) link 1 EF 1600 2 2 link 2 AF 1600 2.5 2 link 3 BE 1600 2.5 2 link out 6 10

Il valore del quantum `e stato scelto tenendo presente che, per ogni flusso i, deve valere3 φi ≥ sizemax affinch´e un generico algoritmo frame based sia di complessit`a O(1) (vedi par. 3.3 a pag. 92).

3Con φ

i si indica il valore del quantum associato al flusso i in accordo alla notazione usata nel capitolo 3.

(7)

L’obiettivo della simulazione condotta `e principalmete quello di verificare che la funzione (eq. (3.11) a pag. 99)

β(t) = βρi,Θi(t) = ρi[t −3F − 2φr i]+ (4.1)

soddisfi la propriet`a di curva di servizio R∗(t) ≥ (R⊗β)(t) ed eventualmente valutare la tightness dei bound che ne derivano.

Ai fini dello studio appena descritto si adotta, l’ipotesi estremamente semplificativa che il router implementi soltanto l’operazione di classificazio-ne e scheduling con un algoritmo di tipo DRR, si analizza quindi il com-portamento del sistema tra l’ingresso nello scheduler e l’arrivo nel nodo di destinazione, come indicato in figura 4.3.

dest EF

DRR dprop

Figura 4.3: Percorso analizzato

Dall’equazione (4.1) si deduce che assegnare lo stesso quantum alle di-verse classi di servizio significa di fatto che il nodo offre loro la stessa curva di servizio (βEF = βAF = βBE), la quale verr`a indicata per semplicit`a con βρ,Θ. Dai dati riportati nella tabella 4.1, si ricava (vedi eq. (3.10) a pag. 98):

(8)

Θ 3F − 2φi

r =

(3· 4800 − 2 · 1600) · 8

6· 106  0.015 s = 15 ms

dove r = 6 M b/s `e il rate del link d’uscita e F = φi = 3· 1600 byte la dimensione massima del frame per lo scheduling ; la moltiplicazione per 8 a numeratore tiene conto del fatto che il rate `e espresso in riferimento ai bit, mentre i quantum sono espressi in byte; il rate del link d’uscita riservato a ciascuna classe sar`a semplicemente ρ = r ·Fφ = r3 = 2 M b/s.

Il ritardo di propagazione sul link d’uscita pu`o essere tenuto in conto introducendo un “elemento curva di servizio” (par. 2.2.1) con β = δdprop,

con dprop = 10ms. βρ,Θ δdprop βρ,Θ+dprop 0 5000 10000 15000 20000 25000 30000 35000 40000 45000 0 500 1000 1500 2000 Numero di byte Asse temporale (0.1 ms) Curva di servizio β

Figura 4.4: Concatenazione scheduler e link d’uscita

Il modello completo della sezione sotto esame risulta dalla concatenazio-ne (fig. 4.4) dei due elementi appena descritti; pertanto la curva di servizio minima risultante, offerta a ciascuna classe, sar`a:

βC,T(t) = (βρ,Θ⊗ δdprop)(t) = βρ,Θ+dprop(t) (4.2)

La curva di servizio massima `e chiaramente determinata dal massimo rate di trasmissione in uscita dallo scheduler (r = 6 M b/s) e dal solo ritardo

(9)

di propagazione (dprop) sul link d’uscita:

γ(t) = (λr⊗ δdprop)(t) = βr,dprop (4.3)

4.2

Realizzazione delle simulazioni e analisi dei

risultati

Per la simulazione dello scenario descritto nel paragrafo precedente `e stato utilizzato il software open source NS (version 2) scritto in C++ e Otcl [45] e sviluppato alla UC Berkeley.

Scelta una classe di traffico rispetto alla quale si vogliono valutare le prestazioni, l’idea di base `e quella di individuare una situazione critica per cui il sistema offra alla classe considerata il “peggior servizio” possibile4.

Dalla simmetria dello scenario di figura 4.2 segue che le tre classi sono perfettamente equivalenti tra loro ai fini dell’analisi, per fissare le idee si faccia riferimento alla classe EF. Per quel che riguarda il rate si pu`o ipo-tizzare che saturando le classi “di disturbo” (AF e BE ), alla classe sotto esame (EF) venga garantito al pi`u il rate ad essa allocato e nel caso in cui lo scheduler sia efficiente sar`a proprio quello garantito, questo perch´e il traffico di tale classe non ha possibilit`a di usufruire di banda lasciata inutilizzata da sorgenti idle (non ce ne sono!).

Le condizioni appena descritte sono quelle realizzate dallo script ripor-tato di seguito, mediante il quale sono state condotte le prime simulazioni.

(10)

Script tcl

#Definizione simulatore

2 set ns [new Simulator]

4 #Definizione colori differenti per diverse classi

#di traffico per l’animazione con NAM

6 $ns color 1 Blue $ns color 2 VioletRed1 8 $ns color 3 Yellow

Tracefile set debug 0

10

#Istante di partenza random

12 ns-random [exec date +%]

14 #Definizione parametri globali utili set pksize 1500

16 set sizepkudp 1600

18 #Definizione parametri per lo scheduler

Queue/DRR set quantum 1600

20 Queue/DRR set buckets 5

Queue/DRR set blimit 500000

22

#Apertura file nam per l’animazione

24 set f [open anim.nam w] $ns namtrace-all $f

26

(11)

28 #Creazione nodi 30 set n0 [$ns node] set n1 [$ns node] 32 set n2 [$ns node] set n3 [$ns node] 34 set n4 [$ns node]

36 #Creazione link (bidirezionali) tra i nodi

$ns duplex-link $ns $n0 2Mb 2ms DropTail 38 $ns duplex-link $n2 $n0 2.5Mb 2 ms DropTail

$ns duplex-link $n3 $n0 2.5Mb 2 ms DropTail 40 $ns duplex-link $n0 $n4 6Mb 10ms DRR

42 #Definizione degli agenti

set null [new Agent/Null] 44 $ns attach-agent $n4 $null

set ef [new Agent/UDP]

46 $ef set packetSize $sizepkudp $ns attach-agent $n1 $ef

48 set af [new Agent/UDP]

$af set packetSize $sizepkudp

50 $ns attach-agent $n2 $af set be [new Agent/UDP]

52 $be set packetSize $sizepkudp $ns attach-agent $ n3 $be

54

#Associazione tra classi di traffico e colori per l’animazione

56 $ef set class 1

$af set class 2

(12)

60 #Connessione degli agenti

$ns connect $ef $null

62 $ns connect $ af $null $ns connect $ be $null

64

#Definizione traccia da file

66 set trfile1 [new Tracefile]

$trfile1 filename mytrace/ef1-conv.tr 68

#Associazione traccia all’applicazione

70 set app1 [new Application/Traffic/Trace] $app1 attach-tracefile $trfile1

72 $app1 attach-agent $ef

74 #Applicazioni con traffici a bit rate costante

set app2 [new Application/Traffic/CBR] 76 $app2 set rate 2.5Mb

$app2 set packet size $pksize

78 $app2 attach-agent $af

80 set app3 [new Application/Traffic/CBR] $app3 set rate 2.5Mb

82 $app3 set packet size $pksize $app3 attach-agent $be

84

#Definizione file per i dati della simulazione

86 set output [open out10.tr w] $ns trace-queue $n1 $n0 $output

88 set output [open out20.tr w] $ns trace-queue $n2 $n0 $output

(13)

90 set output [open out30.tr w] $ns trace-queue $n3 $n0 $output

92 set output [open out04.tr w] $ns trace-queue $n0 $n4 $output

94

#Avvio delle applicazioni

96 $ns at 0.0 ‘‘$app1 start’’

$ns at 0.0 ‘‘$app2 start’’

98 $ns at 0.0 ‘‘$app3 start’’

100 $ns at 50.0 ‘‘$ns flush-trace; $ns halt’’

102 #Avvio della simulazione

$ns run

Dalle linee [76 e 81] si vede che per saturare le classi di “disturbo” AF e BE viene inviato sui link corrispondenti un traffico a bit rate costante con rate (2.5 M b/s) maggiore di quello allocato (2 M b/s). Ci`o significa che, a meno che il rate della traccia inviata sul link corrispondente alla classe EF non sia sufficientemente basso da lasciare abbastanza banda libera per il traffico in eccesso, ci saranno presumibilmente delle perdite, ma ci si aspetta che siano limitate alle classi con traffico in eccesso.

Le linee [66-72] indicano che il traffico inviato sul link corrispondente alla classe EF viene letto da file.

Le tracce utilizzate nelle diverse simulazioni sono state ottenute collegan-do in modalit`a peer-to-peer, tramite un cavo Ethernet 100BaseT crossover, due PC con sistema operativo Linux (fig. 4.5). Alle schede di rete dei due

(14)

locali (192.168.xxx.xxx) ed `e stato usato il pacchetto Samba per la condivi-sione dei file tra le due macchine. In particolare, `e stato attivato un server smb su una delle due in modo che l’altra potesse avere accesso come client ad alcuni file risiedenti sul server e opportunamente condivisi; sono sta-ti quindi eseguista-ti dal client, mediante un’applicazione per la lettura di file multimediali (totem), alcuni file audio e video (wav e divx). Il traffico gene-rato in tal modo sul collegamento `e stato “catturato” mediante un software chiamato Lindump ([46, 47]).

192.168.3.19

192.168.3.23

Figura 4.5: Collegamento peer to peer

Le tracce cos`ı ottenute, una volta convertite opportunamente nel formato binario richiesto da NS, possono essere date in ingresso al simulatore come sorgenti di traffico.

Le linee [86-93] dello script hanno lo scopo di tracciare, nei file corri-spondenti, i dati della simulazione relativi al collegamento tra i nodi cui ciascun file `e associato.

La figura 4.6 mostra un istante dell’animazione prodotta dal Network Animator (NAM) mediante il file di tipo nam generato da NS (righe 24 e 25 dello script) durante una delle simulazioni eseguite ed analizzate nell’ambito del lavoro di tesi.

(15)

Figura 4.6: Istantanea dell’animazione di una simulazione

figura:

con il significato dei campi illustrato nella tabella 4.2.

Tabella 4.2: Formato dei trace-file creati da NS

event event time from node to node pkt type pkt size flags flow id src addr dst addr seq num pkt id

I file prodotti da NS possono essere agevolmente manipolati e filtrati usando alcune utility di shell (es. grep, cut) e semplici script awk in modo da estrarre gli elementi utili per l’analisi basata sulla teoria del Network Calculus.

Per l’analisi delle tracce sono stati inoltre utilizzati software sviluppa-ti nell’ambito della ricerca del laboratorio di resviluppa-ti di telecomunicazioni del

(16)

ticolare i programmi stats [48] e dump2stat per il calcolo delle statistiche e un programma, ncc, realizzato ad hoc per eseguire le operazioni (min-plus convolution, deconvolution...) tipiche del network calculus.

Tutti i grafici riprodotti di seguito sono stati ottenuti mediante il pro-gramma gnuplot (incluso in tutte le pi`u diffuse distribuzioni Linux ).

Nelle figure 4.7 e 4.8 sono mostrati i rate delle due diverse tracce, una di tipo audio e una di tipo video, inviate come traffico EF e per le quali sono stati analizzati i dati forniti dalle simulazioni.

I risultati delle successive elaborazioni sono rappresentati nelle figure (4.9, 4.10, 4.13, 4.15) per la traccia audio e nelle figure (4.11, 4.14, 4.16, 4.12) per la traccia video.

(17)

0 0.5 1 1.5 2 0 1 2 3 4 5 Rate (Mb/s) Asse temporale (s) Traccia audio Rate Valore medio

Figura 4.7: Andamento del rate della traccia audio

0 1 2 3 4 5 6 7 0 1 2 3 4 5 Rate (Mb/s) Asse temporale (s) Traccia video Rate Valore medio

(18)

0 200000 400000 600000 800000 1e+06 0 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 Numero di byte Asse temporale (0.1 ms) Ingresso-uscita R∗ R ⊗ β R

Figura 4.9: Risultati della prova con traccia audio

340000 360000 380000 400000 420000 440000 460000 480000 500000 520000 540000 560000 20000 22000 24000 26000 28000 30000 Numero di byte Asse temporale (0.1 ms) Particolare della curva di servizio, caso audio

R ⊗ β R R∗

(19)

0 100000 200000 300000 400000 500000 600000 700000 800000 900000 1e+06 0 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 Numero di byte Asse temporale (0.1 ms) Ingresso-uscita R∗ R ⊗ β R

Figura 4.11: Risultati della prova con traccia video

350000 400000 450000 500000 550000 600000 26000 28000 30000 32000 34000 Numero di byte Asse temporale (0.1 ms) Particolare della curva di servizio, caso video

R ⊗ β R R∗

(20)

priet`a di curva di servizio `e verificata sia per il caso audio che per quello video in quanto l’uscita R∗risulta essere sempre al di sopra del bound R ⊗β. Inoltre `e evidente dal confronto delle figure 4.10 e 4.12 che nel caso video, cui corrispondono un rate e una burstiness pi`u elevati, l’uscita risulta pi`u schiacciata sul bound.

Le figure 4.13 e 4.14 mostrano invece il bound determinato dalla curva di servizio massima γ ovviamente verificato in quanto si tratta di limitazioni fisiche del sistema.

340000 360000 380000 400000 420000 440000 460000 480000 500000 520000 540000 560000 20000 22000 24000 26000 28000 30000 Numero di byte Asse temporale (0.1 ms) Curve di servizio max e min

R ⊗ β R ⊗ γ R∗

Figura 4.13: Bound massimo e minimo sull’uscita per il caso audio

`

E comunque interessante notare che nel caso in cui il rate delle classi di “disturbo” venga ridotto a zero (ci`o si ottiene banalmente variando le linee 76 e 81 dello script ) la sezione del sistema che viene osservata si riduce di fatto ad un server a bit rate costante attraversato da un unico flusso che

(21)

350000 400000 450000 500000 550000 600000 26000 28000 30000 32000 34000 Numero di byte Asse temporale (0.1 ms) Curve di servizio max e min

R ⊗ βγ R∗

Figura 4.14: Bound massimo e minimo sull’uscita per il caso video

ha dunque λr sia come massima che come minima curva di servizio (vedi par. 2.2.2 a pag. 43), seguito da un elemento di ritardo δdprop. Dunque la

concatenazione dovrebbe offrire al flusso la curva di servizio

γ(t) = (λr⊗ δdprop)(t).

Le simulazioni danno i risultati rappresentati nelle figure 4.15 e 4.16. Il fatto che l’uscita R∗ sia sempre al di sotto del bound R ⊗γ `e dovuto all’effet-to della pacchettizzazione precedentemente discusso (si veda in particolare il par. 3.4 a pag. 99). Si nota infatti che negli istanti immediatamente successivi all’arrivo di un pacchetto le due curve coincidono.

(22)

435000 440000 445000 450000 455000 460000 465000 470000 475000 480000 24000 24500 25000 25500 26000 Numero di byte Asse temporale (0.1 ms) Curva di servizio max e sistema scarico

R ⊗ β R ⊗ γ R∗u

Figura 4.15: Uscita e servizio max a sistema scarico, caso audio

450000 460000 470000 480000 490000 500000 510000 520000 30000 30500 31000 31500 32000 Numero di byte Asse temporale (0.1 ms) Curva di servizio max e sistema scarico

R ⊗ β R ⊗ γ R∗u

(23)

`

E naturale aspettarsi che la curva di servizio offerta a ciascun flusso da uno scheduler di tipo work conserving possa dipendere anche da quelle che sono le curve d’arrivo degli altri flussi gestiti e non solo dal rate riservato.

Per rendersene conto si consideri un dispositivo con una certa capacit`a C di elaborazione che serva tre flussi, come indicato in figura 4.17. La curva di servizio offerta al flusso EF, immaginando che il nodo sia costituito dal solito scheduler DRR, sar`a quella massima tra βρ,Θ e βarr = λC− (αAF + αBE).

REF RAF RBE R∗ R = REF + RAF+ RBE C

Figura 4.17: Sistema con capacit`a d’elaborazione C costante

Con αAF e αBE sono state indicate le curve d’arrivo dei flussi AF e BE. Fissato un istante t e detto s l’inizio del busy period per il sistema, per cui R∗(s) = R(s), si avr`a:

R∗(t) − R∗(s) = R∗(t) − R(s) = C(t − s)

Detto inoltre t0 l’istante di inizio del periodo di backlog per la classe EF

si avr`a anche:

R∗(t)−R∗(s) = [R∗EF(t)−R∗EF(s)]+[R∗AF(t)−RAF (s)]+[R∗BE(t)−R∗BE(s)]

= [REF (t) − R∗EF(t0)] + [RAF (t) − RAF(s)] + [R∗BE(t) − RBE(s)]

(24)

anche R∗AF(t) ≤ RAF(t) e RBE∗ (t) ≤ RBE(t), allora sar`a:

R∗EF(t) − R∗EF(t0)

= R∗EF(t) − REF(t0)≥ C(t − t0)− [RAF(t) − RAF(s) + RBE(t) − RBE(s)] e dalla definizione di curva d’arrivo segue:

R∗EF(t) ≥ R(t0) + C(t − t0)− [αAF(t − s) + αBE(t − s)].

Poich`e le curve d’arrivo sono fuzioni appartenenti all’insieme F (wide sense increasing) si pu`o concludere:

R∗EF(t) ≥ R(t0) + C(t − t0)− [αAF(t − t0) + αBE(t − t0)].

Quindi, se la funzione G(u) = 

Cu − [αAF(u) + αBE(u)] +

`

e wide sense increasing, il flusso EF riceve una curva di servizio proprio pari a G. Il discorso `e perfettamente analogo per gli altri due casi.

Un’analisi simile a quella appena esposta viene presentata in [49] e in [5] in relazione ad uno scenario di scheduling basato su classi con priorit`a (Class-Based Priority Queueing). In particolare in [49] viene costruito, a partire dall’osservazione che le curve di servizio offerte ai flussi a bassa priorit`a dipendano dalle curve d’arrivo di quelle a priorit`a pi`u alta, un meccanismo di admission control che consente di dare garanzie sul ritardo e sul rate.

Considerazioni analoghe trovano riscontro anche in ambito di proble-matiche relative alla valutazione del servizio che viene garantito ai singoli µflussi in situazioni di scheduling aggregato [5, 50, 51].

Nei casi pratici non ci si pu`o aspettare di conoscere le curve di arrivo di un traffico BE per il quale non deve essere fornito alcun tipo di garanzia, ma

(25)

`

e ragionevole pensare di avere informazioni sulle classi EF e AF che invece richiedono una certa qualit`a del servizio.

Quanto esposto `e valido nel caso in cui risulti

G(u) = (λC − [αAF + αBE])(u) ≥ βρ,Θ

, perch´e in ogni caso, data la struttura dello scheduler, la curva di servizio βρ,Θ viene garantita.

I risultati di alcune simulazioni condotte utilizzando la solita traccia video sulla classe EF e abbassando (da 2.5 M b/sa 1 M b/s) il rate delle classi di “disturbo”, che di fatto significa agire sulle loro curve d’arrivo, hanno confermato le deduzioni teoriche sopra illustrate. Dalle figure 4.18 e 4.19, che riportano i risultati suddetti, si nota infatti che l’uscita si sposta verso il bound superiore γ ⊗ R determinato dalla curva di servizio massima.

(26)

215000 220000 225000 230000 235000 240000 245000 250000 255000 260000 265000 16000 16500 17000 17500 18000 Numero di byte Asse temporale (0.1 ms) R ⊗ β R∗u R∗l R ⊗ γ R∗

Figura 4.18: Dipendenza del servizio dagli arrivi dei flussi concorrenti (a)

850000 860000 870000 880000 890000 900000 910000 920000 46000 46500 47000 47500 48000 Numero di byte Asse temporale (0.1 ms)

Funzioni cumulative d’uscita in condizioni di carico diverse

R ⊗ β R∗u

R∗l R ⊗ γ R∗

(27)

4.3

Un esempio di concatenazione

Con semplici integrazioni dello script tcl `e possibile simulare lo scenario raffigurato in figura 4.20, che permette di verificare le propriet`a di concate-nazione della curva di servizio.

DRR link tipo 2 link tipo 3 link tipo 4 DRR dest link tipo 1 link tipo 2 EF Sezione analizzata link tipo 2 link tipo 2 link tipo 3

Figura 4.20: Concatenazione di due scheduler

Per dare un’idea visiva della situazione, viene visualizzata in figura 4.21 un’istantanea dell’animazione ottenuta con NAM a partire dai dati di simu-lazione relativi allo scenario con concatenazione.

Con i valori dei parametri indicati nella tabella 4.3 la curva di servizio offerta dalla sezione studiata risulta:

βconc= βρ,Θ⊗ δdprop⊗ βρ,Θ⊗ δdprop = βρ,2Θ+2dprop

con ρ = r · Fφ = r3 = 2 M b/s e 2Θ + 2dprop 50 ms.

Le figure 4.22 e 4.23, ottenute utilizzando come traccia d’ingresso per la classe EF ancora una volta la traccia video il cui rate `e mostrato in figura 4.8, dimostrano che la propriet`a di curva di servizio `e soddisfatta anche quando si consideri la concatenazione di pi`u nodi. Dalle figure 4.24 e 4.25 `e

(28)

Figura 4.21: Istantanea dell’animazione relativa alla simulazione dello scenario con concatenazione

Tabella 4.3: Parametri dello scenario con concatenzione

classe quantum (byte) rate di tra-smissione (Mb/s) propagation delay (ms) link tipo 1 EF 1600 2 2

link tipo 2 AF/BE 1600 2.5 2

link tipo 3 6 10

link tipo 3 4 8

per`o evidente che nel caso concatenato la funzione cumulativa dell’uscita `e mediamente pi`u distante dal bound inferiore (R ⊗ β) di quanto non avvenga nel caso di un solo scheduler. Ci`o `e probabilmente da imputare all’aumento di burstiness cui `e soggetto un flusso quando attraversa un nodo con curva di servizio βR,T (vedi es. di fig. 1.13 a pag. 23).

(29)

del-l’uscita α∗ = R∗ R∗, illustrata a titolo d’esempio in figura 4.27, abbia un burst maggiore di quello della curva d’arrivo minima dell’ingresso α = RR.

0 100000 200000 300000 400000 500000 600000 700000 800000 900000 1e+06 0 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 Numero di byte Asse temporale (0.1 ms) Concatenazione curve di servizio

R∗conc

R ⊗ β R

Figura 4.22: Risultati della prova per la concatenzione

260000 280000 300000 320000 340000 360000 380000 400000 420000 440000 460000 480000 20000 22000 24000 26000 28000 30000 Numero di byte Asse temporale (0.1 ms) Concatenazione curve di servizio

R ⊗ β R R∗conc

(30)

0 1000 2000 3000 4000 5000 6000 7000 0 5000 10000 15000 20000 25000 30000 35000 40000 45000 50000 Numero di byte Asse temporale (0.1 ms) R∗conc− R ⊗ βconc R∗− R ⊗ β

Figura 4.24: Confronto delle distanze dal bound nel caso di un singolo nodo e nel caso di concatenazione

0 1000 2000 3000 4000 5000 6000 7000 30000 32000 34000 36000 38000 40000 Numero di byte Asse temporale (0.1 ms)

Differenza tra uscita e bound, singolo nodo e concatenazione a confronto

R∗conc− R ⊗ βconc

R∗− R ⊗ β

(31)

0 500 1000 1500 2000 2500 3000 3500 0 5 10 15 20 25 30 35 40 45 50 Numero di byte Asse temporale (0.1 ms) Curve d’arrivo del flusso in ingresso e in uscita

αmin= R  R α∗min= R∗conc R∗conc

Figura 4.26: Confronto dei burst delle curve d’arrivo in ingresso e in uscita

0 5000 10000 15000 20000 25000 30000 0 200 400 600 800 1000 Numero di byte Asse temporale (0.1 ms) Esempio di curva d’arrivo minima

α∗min= R∗conc R∗ conc

(32)

Figura

Tabella 4.1: Parametri dello scenario
Figura 4.3: Percorso analizzato
Figura 4.4: Concatenazione scheduler e link d’uscita
Figura 4.5: Collegamento peer to peer
+7

Riferimenti

Documenti correlati

[r]

Possiamo trarre conclusioni molto simili a quelle tratte per il metodo di Kansa: la scelta migliore (per quanto riguarda errore e condizio- namento) è quella di

[r]

Una metodologia all’apparenza molto diversa è stata adottata dal gruppo di ricerca danese che, prendendo sempre come riferimento di base la (4.11b) ed esprimendo con relazioni

mobilità precedente al ricovero: ……..……….. condizioni area

[r]

All’interno del campione “PFCD” è stato possibile osservare, con l’ausilio del microscopio ottico polarizzatore, diverse masse opache irregolari contenti

• La stipula, con la stessa società, del contratto avente ad oggetto la fornitura di DPI scaduti per il personale delle Unità Operative Territoriali di Palermo, Messina e