A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 11
Politecnico di Milano Politecnico di Milano –– Sede di CremonaSede di CremonaA.A. 2008/09A.A. 2008/09
Corso di Corso di RETI DI COMUNICAZIONE E INTERNETRETI DI COMUNICAZIONE E INTERNET
(Modulo 1(Modulo 1))
Martino De MarcoMartino De Marco([email protected], [email protected])([email protected], [email protected])
ESERCITAZIONEESERCITAZIONEVALUTAZIONE DELLE PRESTAZIONIVALUTAZIONE DELLE PRESTAZIONI
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 22
IndiceIndice
• Sistemi di accodamento– Processo degli arrivi– Processo di servizio– Disciplina di servizio
• Applicazioni alle telecomunicazioni– Condizione di stabilità– Occupazione media– Tempo di transito
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 33
Sistemi di accodamentoSistemi di accodamento• Un sistema di accodamento è un sistema deputato
all’erogazione di un servizio, per accedere al quale gli utenti possono entrare in competizione tra loro
• Anche se magari non ce ne rendiamo conto, noi abbiamo a che fare quotidianamente con sistemi di accodamento :– quando aspettiamo di pagare la spesa alla cassa di un supermercato– quando attendiamo che il semaforo si disponga al verde– quando andiamo dal barbiere o dal parrucchiere...
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 44
Sistemi di accodamento nelle retiSistemi di accodamento nelle reti• Sistemi di accodamento sono presenti anche negli apparati
per reti di telecomunicazione e la loro efficienza determina le prestazioni complessive di una rete– Nelle reti a commutazione di pacchetto, i buffer presenti nel nodo
consentono di accodare le unità informative in attesa della trasmissione sulla linea di uscita (multiplazione asincrona)
– Nelle reti a commutazione di circuito (multiplazione sincrona), fenomeni di accodamento sono visibili nella fase di instaurazione dei circuiti, quando le richieste di una apertura della connessione competono per l’assegnamento di risorse di rete
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 55
Teoria delle CodeTeoria delle Code• Per valutare le prestazioni di sistemi di accodamento si
applicano risultati derivanti dalla Teoria delle Code• La teoria delle code consente di studiare le prestazioni dei
sistemi di accodamento– Ritardo: distribuzione dei ritardi sperimentati dagli utenti– Perdita: esclusione di utenti dal servizio a causa di eccessiva domanda– Throughput: frequenza massima di servizio
Fila d’attesa ServentePopolazione
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 66
Modello del sistema di accodamentoModello del sistema di accodamento• Possiamo modellare un sistema di accodamento con i
seguenti elementi:– la popolazione: gli utenti potenziali del servizio– la fila d’attesa (o coda): l’insieme degli utenti in competizione per
accedere al servizio– il servente: l’entità deputata all’offerta del servizio (la cassiera del
supermercato, il sistema semaforico, il barbiere, ecc.).
Fila d’attesa ServentePopolazione
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 77
Parametri di un sistema di accodamentoParametri di un sistema di accodamento• Parametri che caratterizzano un sistema di accodamento sono:
– la numerosità della popolazione (N): il numero totale di utenti potenziali
– la distribuzione degli arrivi: come sono distribuiti nel tempo gli arrivi di nuovi utenti
– Il tempo di servizio: il tempo che il servente impiega per servire un utente
– il numero di serventi (M), contemporaneamente attivi– la disciplina di servizio: l’ordine con cui sono serviti gli utenti– la capacità della fila d’attesa (L): la capacità della coda di ospitare
utenti in attesa del servizio
N L m
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 88
Il processo degli arrivi alla codaIl processo degli arrivi alla coda• Se la popolazione è infinita e gli arrivi generati dagli utenti
sono indipendenti tra loro, il processo degli arrivi èriconducibile alla legge di Poisson– In tal caso, la probabilità che si presentino al sistema n clienti durante
un intervallo di durata t è data da:
• Il processo degli arrivi è descritto unicamente dalla variabile λ,che indica la frequenza media di arrivo (utenti al secondo)
N L m
[ ] ( )P t
tn
en
nt= −λ λ
!
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 99
Il processo degli arrivi alla coda (2)Il processo degli arrivi alla coda (2)• Se la popolazione di utenti che possono accedere al sistema
viene ipotizzata infinita, l’intervallo temporale tra un arrivo ed il successivo (tempo di interarrivo) sarà modellato matematicamente con una funzione di densità di probabilitàesponenziale negativa λ λe t−
Questa funzione rappresenta la frequenza normalizzata con cui si verificano tempi di interarrivo pari a t
λ =0,5 arrivi al secondo
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 1010
Il processo di servizioIl processo di servizio• In generale i serventi possono essere più di uno
– Per semplicità si considereranno sempre sistemi a singolo servente
• Occorre conoscere anche il tempo che il servente impiega per servire un cliente (tempo di servizio)
• Se il processo di servizio obbedisce alla Legge di Poisson, il tempo di servizio è una variabile casuale descritta da una funzione di densità di probabilità esponenziale negativa, con valore medio Ts
• La variabile μ indica il numero medio di utenti che il servente riesce a soddisfare nell’unità di tempo (frequenza media di servizio): μ= 1/ Ts
N L m
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 1111
Disciplina di servizioDisciplina di servizio• Vi sono diversi modi con cui un servente può soddisfare i suoi
utenti: – FIFO (First In First Out): servire per primo chi è arrivato per primo– LIFO (Last In First Out): servire per primo chi è arrivato per ultimo
(stack)– SJF (Shortest Job First): servire per primo quello che richiede meno
tempo per essere serviti – PQ (Priority Queueing): servire per primo che ha più priorità più elevata– ...
• In seguito adotteremo il criterio del “primo arrivato primo servito” (FIFO)
N L m
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 1212
CapacitCapacitàà della fila ddella fila d’’attesaattesa• Per quanto riguarda la fila d’attesa essa, nella realtà, ha
capacità tutt’altro che infinita (anche se a volte può sembrarlo!)
• Se però la capacità della coda è molto grande (L>>λ Ts), si può approssimare la trattazione al caso della fila d’attesa con capacità infinita (più semplice da descrivere analiticamente)
• Si considereranno nel seguito solamente file d’attesa aventi capacità infinita
N L m
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 1313
Notazione formaleNotazione formale• Notazione formale per esprimere le caratteristiche di un sistema
a code: M/M/m/L/N– Il primo campo indica come sono distribuiti gli interarrivi dei clienti: M
rappresenta una distribuzione esponenziale negativa– Il secondo campo serve a rappresentare la distribuzione del tempo di
servizio del servente– m è il numero di serventi presenti nel sistema considerato– L rappresenta la capacità massima della fila d’attesa– N indica la numerosità della popolazione degli utenti
• In seguito si considereranno sistemi di tipo M/M/1/∞/∞ (M/M/1)– Questi sistemi sono completamente descritti se si conosce il numero di
utenti presenti in un dato istante in fila d’attesa ed occupati col servente– Il tempo che un cliente ha già trascorso nel servente non interessa,
poiché la distribuzione esponenziale negativa non lo considera: si dice che non ha memoria
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 1414
Applicazione alle telecomunicazioni (1)Applicazione alle telecomunicazioni (1)• Le considerazioni fatte nel caso generale si possono applicare
alle reti di telecomunicazioni a commutazione di pacchetto– I clienti sono i pacchetti generati da uno o più terminali– il servente è rappresentato da un trasmettitore (multiplatore, in caso di
più linee d’ingresso) che inoltra i pacchetti su una linea di trasmissione– In sede di calcolo si dovrà considerare il tempo di servizio dovuto alla
capacità della linea– il ritardo introdotto dal trasmettitore è, solitamente, trascurabile
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 1515
Applicazione alle telecomunicazioni (2)Applicazione alle telecomunicazioni (2)• Se nella coda non sono segnati i posti per gli utenti,
intenderemo che il sistema è del tipo a coda infinita• La lunghezza dei pacchetti, essendo una variabile casuale
con distribuzione esponenziale negativa, ha un valore medio pari a [bit]
• Nota la capacità C della linea [bit/s], si può calcolare il tempo medio di servizio del trasmettitore come:
• Il numero medio di pacchetti processati nell’unità di tempo dal trasmettitore è:
[ ]~lC
s
[ ]Cl
s~ −1
~l
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 1616
Sistemi di nascita e morteSistemi di nascita e morte• Assumiamo come variabile di stato S(t) del sistema il numero
di pacchetti presenti nel sistema (coda+trasmettitore) all’istante t– Se il sistema non contiene alcun pacchetto, si dice che è nello stato 0
(zero)– Se ora arriva un pacchetto il sistema passa dallo stato 0 allo stato 1– Quando il pacchetto viene trasmesso, il sistema ritorna nello stato 0
• Un sistema in cui le sole transizioni di stato possibili sono quelle che portano a stati adiacenti viene chiamato sistema di nascita-morte
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 1717
Diagramma degli statiDiagramma degli stati• Probabilità stazionaria
– pk è la probabilità stazionaria che il sistema si trovi nello stato k– Diamo una definizione intuitiva del concetto di probabilità
• pk rappresenta la frazione di tempo che il sistema trascorre nello stato k nel corso di un periodo di osservazione motlo lungo
• pk indica analogamente la frequenza relativa (normalizzata) in cui il sistema viene osservato nello stato k in un gran numero di ispezioni casuali
• Frequenze di transizione– La frequenza con cui il sistema passa dallo stato k allo stato k+1 è λ pk
– Analogamente, la frequenza con cui il sistema transita dallo stato k+1 allo stato k è μ pk+1, in cui pk+1 è la probabilità stazionaria che il sistema si trovi nello stato k+1
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 1818
Principio di bilanciamento dettagliatoPrincipio di bilanciamento dettagliato– Affinché il sistema sia stabile, cioè la sua coda non cresca
indefinitamente, la frequenza di transizione dallo stato k allo stato k+1 dev’essere uguale alla frequenza di transizione da k+1 a k (Principio di bilanciamento dettagliato)
– Quindi λ pk=μ pk+1 , cioè ad esempio:
– si può ricavare p2 in funzione di p0 ottenendo:
– Generalizzando:
λ μλ μ
p pp p
0 1
1 2
==
p p p2 1
2
0= =⎛⎝⎜
⎞⎠⎟
λμ
λμ
p p pk
kk=
⎛⎝⎜
⎞⎠⎟ =
λμ ρ0 0
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 1919
Condizione di stabilitCondizione di stabilitàà• ρ = λ/ μ prende il nome di intensità di traffico o carico del
sistema, perché indica la frazione di tempo per cui il servente è occupato – es.: λ =1, μ =2 ⇒ ρ =0,5, cioè per il 50% del tempo il servente sta
lavorando e per il restante 50% è inattivo
• Se λ > μ il sistema si dice instabile, in quanto il servente soddisfa mediamente meno utenti di quanti ne arrivano
• Occorrerà quindi che, affinché un sistema possa funzionare, λsia sempre minore di μ
• Affinché λ < μ (sistema stabile), ρ <1
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 2020
Distribuzione di probabilitDistribuzione di probabilitàà stazionariastazionaria• Poiché la somma delle probabilità (frequenze normalizzate)
deve essere 1:
dato che la sommatoria di ρk costituisce una serie geometrica di ragione ρ <1
• In definitiva abbiamo che:p0=1-ρ
e quindi: pk=ρk(1-ρ)
p p pkk
k
k=
∞
=
∞
∑ ∑= =−
=0
00
01
11ρ
ρ
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 2121
Occupazione media del sistemaOccupazione media del sistema
• Il numero medio di pacchetti nel sistema (N) sarà:
λμλ
ρρ
−=
−=
1N
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 2222
Occupazione media del sistemaOccupazione media del sistema• Il numero medio di pacchetti nel sistema (N) sarà quindi:
• Poiché:
risulta:
( ) ( ) ( ) ( )N kp k k dd
ddk
k
kk
k
k
k
k
k
k
= = − = − = − = −⎛⎝⎜
⎞⎠⎟
=
∞
=
∞−
=
∞
=
∞
=
∞
∑∑ ∑ ∑ ∑1 1 1 100
1
0 0 0
ρ ρ ρ ρ ρ ρ ρρ
ρ ρ ρρ
ρ
( )dd
dd
k
kρρ
ρ ρ ρ=
∞
∑⎛⎝⎜
⎞⎠⎟ =
−⎛⎝⎜
⎞⎠⎟ =
−02
11
11
( )( )
N = −−
=−
1 11 12ρ ρ
ρρρ
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 2323
Occupazione media del servente e della codaOccupazione media del servente e della coda
• Il numero medio di pacchetti che il trasmettitore sta processando (NT) equivale alla frazione di tempo in cui il servente non sia vuoto, cioè:
NT =ρ
• Il numero medio di pacchetti in attesa di essere processati (NA) può essere calcolato come il numero totale di pacchetti nel sistema meno il numero di pacchetti nel trasmettitore, cioè:
NA= ρρ
ρ ρρ1 1
2
−− =
−
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 2424
Principio di Little (1)Principio di Little (1)• Per conoscere il tempo medio di transito nel sistema (coda +
trasmettitore), dobbiamo applicare un’equazione dimostrata per la prima volta da D. C. Little nel 1961
• Spiegazione intuitiva: – si indichi con T il tempo medio trascorso da un utente nell’intero
sistema (cioè l’intervallo di tempo che intercorre tra l’arrivo e l’uscita dal sistema di un pacchetto)
– Il numero medio di arrivi di nuovi pacchetti durante l’intervallo T è λ T– Poiché il numero medio di pacchetti nel sistema è N, si ha N= λ T
(Principio di Little)
• Il Principio di Little, può essere utilizzato per calcolare T:
. T N= = − =
−=
−λ
ρρ
λμ
ρ μ λ1
1
11
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 2525
Principio di Little (2)Principio di Little (2)• Il principio di Little può essere applicato a qualsiasi superficie
chiusa, permettendoci di ricavare altri parametri interessanti del sistema
• tempo medio di transito nella fila d’attesa (TA) – in questo caso NA è il numero medio di pacchetti in coda, quindi:
• tempo medio di transito nel trasmettitore (TT)
TN
AA= =
−=
−λ
ρρ
λρ
μ λ
2
1
T NT
T= = =λ
ρλ μ
1
A.A. 2008/09 A.A. 2008/09 –– Corso di Corso di Reti di Comunicazione e Internet (Modulo 1) Reti di Comunicazione e Internet (Modulo 1) –– M. De MarcoM. De MarcoESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONIESERCITAZIONE: VALUTAZIONE DELLE PRESTAZIONI Slide Slide 2626
Dimensionamento del serventeDimensionamento del servente• Il Principio di Little consente di dimensionare una sistema di
trasmissione• Sostituendo a μ la sua espressione in funzione della capacita
C della linea di trasmissione e della lunghezza media dei pacchetti si ottiene:
~l
T Cl
lC l
=−
=−
=−
1 1μ λ λ λ~
~~