Esercitazione 2

Esercizio 1• Data la rete riportata con i costi indicati in

figura, si usi l’algoritmo di Dijkstra per calcolare il percorso più breve da F a tutti i nodi della rete. Si disegni l’albero di costominimo ottenuto.

H

G

D

B

C

A

E

F

14

63

1

1

11

12

4

2

94

3

Esercizio 2• Data la rete riportata in figura, si assuma che

ciascun nodo inizialmente conosca i costi verso ciascuno dei suoi vicini. Si usi l’algoritmodistance vector per calcolare gli ingressi dellatabella di instradamento per ciascun nodoquando l’algoritmo è andato a regime.

H

D

B

CE

2

210

15

1

5

1

Allocazione Deterministica (1/10)• In assenza del regolatore, una allocazione delle risorse di tipo

deterministico (cioè senza perdite di pacchetti) può essere fatta soltanto sulla base della ritmo di emissione di picco (Pmax) della sorgente, dato un multiplatore a pacchetto di capacità C:

• Tale criterio porta ad una scarsa efficienza di utilizzazione delle risorse (), ma assicura l’assenza di perdite di pacchetti: – non usa un modello di sorgente trasmissiva, ma utilizza l’approccio di

caso peggiore– rM è il ritmo di trasmissione medio

• La presenza di un buffer nel modello del multiplatore permette di calcolare il massimo ritardo di attraversamento del nodo:

B=Np*dim{pkt}, Dmax=B/C

nteella sorgeattività dPr

CrN

PCN MMp

pp

maxmax

,

Allocazione Deterministica (2/10)• Il DLB riduce la durata dei burst ad un valore

massimo prefissato

• permette di effettuare efficientemente una allocazione deterministica nel caso in cui il modello del multiplatore a pacchetto tenga conto anche della presenza di un buffer:– B: dimensione del buffer del multiplatore– C: capacità di uscita del multiplatore

Allocazione Deterministica (3/10)

• Il DLB permette di modellare una sorgente qualsiasi tramite i suoi 3 parametri:– rs: ritmo di trasferimento binario sostenibile (≥ rM, per

motivi di stabilità del regolatore);– BTS: profondità del bucket, indica la massima

tolleranza ammissibile sul ritmo binario sostenibile e permette di calcolare la dimensione massima di un burst;

– Ps: ritmo binario di trasferimento di picco, indica la massima velocità a cui i pacchetti possono uscire dal regolatore di traffico.

• La complessità dell’operazione è spostata a monte, nella scelta dei parametri del regolatore di traffico …

Allocazione Deterministica (3bis/10) Dual Leaky Bucket (DLB)

• Il primo elemento (token bucket) regola il ritmo binario di uscita, permettendo una certa tolleranza (data dalla profondità del bucket)

• Il secondo elemento (leaky bucket) regola il ritmo binario di picco.

rs Ps

BTS

c

b

b

Allocazione Deterministica (4/10)

• La presenza del DLB impone un limite al tempo massimo durante il quale i token sono consumati a ritmo Ps:

• Massima dimensione di un burst:ss

TSpicco rP

BT

ss

sTSP rP

PBW

Allocazione Deterministica (5/10)

• Obiettivo: allocare una quantità di banda e di buffer del link di uscita del multiplatore (c,b), frazione di (C,B)– con il vincolo imposto dal ritardo massimo, Dmax

– con il vincolo di assicurare un buffer (b) per flusso tale da evitare perdita di informazione

maxDcb

CB

)()( cPrP

BcPTb sss

TSspicco

Allocazione Deterministica (6/10)

• Riassumendo, il numero di flussi Ne:– impostando le equazioni su base risorse da

assegnare al flusso (b,c), si ottiene:

– impostando su base risorse aggregate si ottiene:

cC

bB

cC

bBN

Dcb

CB

cPrP

BcPTb

fisfise

sss

TSspicco

,min

)()(

max

max

)()(

DCB

CPNrP

BCPNTB sess

TSsepicco

Allocazione Deterministica (7/10)

• Risolvendo il secondo sistema, si ottiene:• Dal primo sistema:

• La quantità c0=C/Ne prende il nome di bandaequivalente. Si definisce allora il guadagno (g) rispetto all’allocazione di picco:

0

maxe

max )(1 ,)(1crrP

BD

Pr

CrNrP

BD

PCN M

ssTSs

MMess

TSse

)(1)(1 maxmax

p

esM

TSsM

TSM

M rPBDrP

BD

rrg

piccose T

DPCN max1

Allocazione Deterministica (8/10)

BTS

b

cPMrs

B/C=b/c=Dmax

b=Tpicco(Ps-c)

bo

co

0max0

max0 )(

cDbBrPD

BPcTSSS

TSS

Allocazione Deterministica (9/10)

• C=2048 Kb/s• B=8÷64 KB

0.05 0.1 0.15 0.2 0.2562

64

66

68

70

72

74

Dmax in secondi

Num

ero

di fl

ussi

Banda equivalenteBanda di picco

0 0.05 0.1 0.15 0.2 0.250.34

0.35

0.36

0.37

0.38

0.39

0.4

Dmax in secondi

Effi

cien

za

Banda equivalenteBanda di picco

• Ps=32 Kb/s• rs= 11.2 Kb/s• BTS=5 KB

Allocazione Deterministica (10/10)

• Parametri Multiplatore:C= 2048 Kb/s, B=32 KB

• parametri DLB: Ps=32 Kb/s, r= 11.2 Kb/s, BTS=5*8 Ktoken

• Dmax= 125 ms• Np= 2048 / 32 = 64• Tpicco=5000*8/(32000-11200)=

1.923 s• Ne= 2048 / 32 (1+

0.125/1.923)= 68.16 => 68• c0=C/Ne= 2048 Kb/s / 68 =

30.11 Kb/s

• Parametri Multiplatore:C= 10 Mb/s, B=256 KB

• parametri DLB: Ps=32 Kb/s, r= 11.2 Kb/s, BTS=5 KB

• Dmax= 205 ms• Np= 10000 / 32 = 312.5 => 312• Tpicco=5000*8/(32000-11200)=

1.923 s• Ne= 10000 / 32 (1+

0.205/1.923)= 345.81 => 345• c0=C/Ne= 10 Mb/s / 345 =

28.985 Kb/s

Allocazione Statistica (1/5)

• Consideriamo un multiplatore di capacitàC senza buffer (in pratica, equivale ad assumere che la lunghezza dei burst ègrande rispetto al buffer presente):– data una sorgente che emette ad una

capacità massima Pmax e con una certa attività a, calcolare il numero massimo di sorgenti K che posso accettare se si vuole mantenere la probabilità di overflow al di sotto di un certo valore prefissato

Allocazione Statistica (2/5)

• Se assumo che la sorgente sia on-off, possomodellarla come una variabile aleatoria a due valori {0, Pmax}, assunti rispettivamente con probabilità {1-a, a}

• Date K sorgenti, la probabilità che si verifichioverflow è pari alla probabilità che siano attivepiù di NP=C/Pmax sorgenti:

K

Nn

nKnoverflow

p

aanK

P1

)(1

Allocazione Statistica (3/5)• Consideriamo:

– C = 64 Kb/s, Pmax=32 Kb/s, – a = 0.35

• Si ottiene:– Np= 64 Kb/s / 32 Kb/s = 2– Nmax= C / rM = Np/a = 5.71 => 5 ≥ K

2351.035.0*165.0*35.0*565.0*35.0*10 ;155

;545

;1035 5423

lowProb_overf

1436.035.0*165.0*35.0*4 ;144

;434 43

lowProb_overf

0428.035.0 ;133 3

lowProb_overf

Allocazione Statistica (4/5)• → si deve quindi scegliere K (≤Nmax) in modo da

mantere la probabilità di overflow al di sotto di

• C = 2048 Kb/s• Pmax= 32 Kb/s• a = 0.35• Nmax= 182• a’=0.5• N’max= 128

60 80 100 120 140 160 180 20010-30

10-25

10-20

10-15

10-10

10-5

100

Numero massimo di sorgenti, K

Pro

babi

lità

di o

verfl

ow,

a = 0.35a = 0.5

Allocazione Statistica (5/5)• L’efficienza sarà tanto maggiore quanto più è

elevata sia l’attività della sorgente che la ammissibile

• C = 2048 Kb/s• Pmax= 32 Kb/s• a = 0.35• Nmax= 182• a’=0.5• N’max= 128

10-30

10-25

10-20

10-15

10-10

10-5

100

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Probabilità di overflow,

Effi

cien

za

Allocazione statistica, a = 0.35Allocazione statistica, a = 0.5Allocazione banda di picco, a = 0.35Allocazione banda di picco, a = 0.5

EsercizioSi consideri che un multiplatore di flussi informativi, realizzato mediante un buffer di memoria avente una dimensione uguale a 30 Mbyte, servito da un canale di comunicazione caratterizzato da una velocitàtrasmissiva uguale a 2 Mbit/s. Si calcoli il massimo numero di sorgenti ammissibili se si vuole che il tempo di permanenza nel multiplatore dei byte di informazione sia minore o uguale a 0,5 s e ogni flusso sia sagomato mediante un dual leaky bucketcaratterizzato dai seguanti descrittori di traffico: rate di picco Ps= 128 kbit/s, rate sostenibile rs=32 kbit/s, dimensione del token buffer=200 token.

Esercizio

Si usi l’algoritmo di Dijkstra per determinare il percorso dal nodo A a tutti i nodi della rete, mostrando in tabella i passi intermedi; si indichi in figura l’albero di costo minimo ottenuto e il costo per raggiungere i nodi.

A

B

C

D

E

F

G

H

I

L

M2

6

5

52

13

24

17

2

5

3

5

1

6

Passo 1 Passo 2 Passo 3 Passo 4 Passo 5 Passo 6 Passo 7

M

V(M)

Nodo prescelto

Passo 8 Passo 9 Passo 10 Passo 11 Passo 12 Passo 13 Passo 14

M

V(M)

Nodo prescelto

Esercizio• Si consideri un servizio di trasferimento con connessione. Si effettui

una operazione di multiplazione dinamica su un canale di capacitàC= 3 Mbit/s.

• In tale sistema dovranno essere multiplate due classi di sorgenti:– Sorgenti a ritmo binario costante pari a 128 kbit/s;– Sorgenti del tipo ON-OFF caratterizzate da una frequenza di emissione

durante il periodo di ON pari a 640 kbit/s, durata media del periodi di ON pari a 20 s e durata media del periodo di OFF pari a 40 s.

• Assumendo un criterio di assegnazione delle risorse di tipo statistico, con il vincolo che il coefficiente di utilizzazione della capacità C sia minore uguale a 0.5, si chiede di:– Individuare nel grafico di Figura 1 l'insieme delle coppie N1 e N2 di

sorgenti della classe 1 e 2 rispettivamente che possono essere accettate.

N2

N10