Progetto di Reti di Telecomunicazioni - Parte I (per "tutti")

Appunti sulla risoluzione degli esercizi diProgetto di reti di telecomunicazioni

Ing. Pazzo

8 giugno 2010

2

Si consiglia di affiancare il materiale presente in questo riassunto agli appunti presi a lezione. Que-sto perché (ovviamente!) non si vuole avere alcuna presunzione di esaustività, né di assoluta corret-tezza: nonostante le revisioni fin’ora effettuate, potrebbero infatti essere ancora presenti molti errori eimprecisioni.

2

Indice

1 Nozioni di base 51.1 Teorema di Little . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 La notazione di Kendall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3 Processo di Poisson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3.1 Proprietà di composizione e decomposizione . . . . . . . . . . . . . . . . . . . . . . . 61.3.2 Tempo interarrivo in un processo di Poisson . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4 Variabile aleatoria esponenziale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.4.1 Caratterizzazione del tempo di servizio . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.4.2 La crescita esponenziale del traffico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.5 Catene di Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.5.1 Processi di nascita e di morte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 I sistemi a coda 112.1 Parametri e notazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2 SistemaM/M/∞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.3 SistemaM/M/m/0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.4 SistemaM/M/m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.5 SistemaM/M/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.6 SistemaM/M/1/L . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3 Altri esercizi 293.1 Esercizio 4.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.2 Esercizio 5.12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.3 Esercizio 5.13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303.4 Esercizio 5.16 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.5 Esercizio 5.15 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.6 Esercizio 5.17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.7 Esercizio 5.18 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.8 Esercizio 5.19 (il gemello del 5.17) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4 Esercizi del prof. Callegati 414.1 Esercizio 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5 Un brevissimo esempio di sistemaM/G/1 43

3

4 INDICE

4

Capitolo 1

Nozioni di base

1.1 Teorema di Little

Il teorema di Little stabilisce un legame fra tre fondamentali quantità della teoria del traffico:

• A: il traffico offerto;

• λ: la frequenza d’arrivo degli utenti;

• δ̄: il tempo medio speso nel sistema.

Si ha:A = λδ̄

In altre parole, il traffico è dato dal prodotto fra la frequenza media di arrivo per il tempo medio cheogni utente spende nel sistema stesso. Se facciamo riferimento alle grandezze riportate nel paragrafo 2.1possiamo scrivere le seguenti (e utilissime negli esercizi) versioni del teorema di Little:

• per il traffico offerto: A0 = λϑ̄;

• per il traffico smaltito: As = λsϑ̄;

• per il traffico perduto: Ap = λpϑ̄.

Tra l’altro, siccome λ = λs + λp, si ricava immediatamente:

A0 = As + Ap

ESERCIZIO:

In un fast food entrano mediamente 2 clienti al minuto. Ciascun cliente impiega mediamente 7minuti alla cassa per ottenere quanto ordinato. Quindi il 60% dei clienti lascia il locale, mentre il 40%rimane a mangiare impiegando mediamente 20 minuti. Volendo dimensionare la ripartizione dello spaziofra casse e tavoli all’interno del locale si vuole calcolare:

• Il numero medio di clienti presenti nel locale.Il numero di clienti all’interno del locale sarà pari a:

A = Acassa + Atavoli = λcassaϑ̄cassa + λtavoliϑ̄tavoli = 2 · 7 + 2 · 0, 4 · 20 = 14 + 16 = 30

• Il numero medio di clienti che stanno mangiando all’interno del locale.In realtà l’abbiamo già calcolato, perché tale quantità è pari a:

λtavoliϑ̄tavoli = 2 · 0, 4 · 20 = 16

5

6 CAPITOLO 1. NOZIONI DI BASE

1.2 La notazione di Kendall

La notazione di Kendall1 consiste in una breve e sintetica sigla per indicare le peculiarità dei sistemi acoda. Ci interesseranno in realtà solo i primi quattro simboli (dei sei che caratterizzano la formulazionecompleta):

A/B/m/n→ processo degli arrivi / processo di servizio / servitori / coda

I simboli A e B saranno quasi sempre pari ad M, ad indicare un processo di Poisson (vedi paragrafo1.3): l’unica eccezione si ha quando si considerano processi generici (G), dei quali cioè non si hannoinformazioni complete relativamente alla distribuzione di probabilità del tempo d’interarrivo. Le quantitàm ed n sono invece fondamentali per inquadrare bene la situazione:

• se assenti si sottintende che la grandezza in questione ha valore infinito;

• m indica il numero di servitori: lo status di servitore può essere assunto da qualsiasi tipo di entità,dunque non bisogna fossilizzarsi nel pensare che sia necessariamente un elaboratore. Potrebbe infattitrattarsi di una linea di trasmissione dati, di un router, di una memoria che ha una certa velocità discrittura, di un essere umano, di un macchinario industriale, etc. . . Un router a cui sono collegate trelinee a diversa velocità, attraverso le quali vengono smistati i pacchetti da e verso la rete pubblica, èun esempio sistema a tre servitori;

• n indica la lunghezza della coda. Per noi sarà quasi sempre infinita.

1.3 Processo di Poisson

Il processo di Poisson viene ampiamente utilizzato per la modellizzazione dell’arrivo delle richieste diservizio nello studio di problemi di teletraffico. Si tratta di un processo tempo-continuo a valori discretiche soggiace alle ipotesi di:

• invio di richieste di servizio al sistema indipendenti da parte degli utenti;

• utenti tutti uguali fra loro;

• richieste del singolo utente distribuite uniformemente nel periodo T con densità di probabilità f (t) =1/T.

Fatta l’ipotesi di processo di Poisson, la probabilità di avere k arrivi in T secondi, detta λ la frequenzamedia d’arrivo, è:

P (k, T) =(λT)k

k!e−λT

Il valor medio e la varianza di un processo stocastico di Poisson sono uguali e pari a λT.

1.3.1 Proprietà di composizione e decomposizione

Dati due processi di Poisson caratterizzati dai parametri λ1 e λ2, la loro somma corrisponde ancora aun processo di Poisson con λ = λ1 + λ2 (proprietà di composizione).Preso invece un processo di Poisson con frequenza media di arrivo λ, se gli arrivi vengono separati inN gruppi, con scelta casuale arrivo per arrivo e probabilità P1, P2, . . . , PN , i flussi risultanti sono anche essiprocessi di Poisson con frequenza media di arrivo data dalla formula:

λi = Piλ ∀i ∈ [1; N]

1Per una trattazione esaustiva si rimanda al testo indicato dal prof. Callegati, mentre in questa sede esamineremo solo ciò cheriguarda la prova scritta d’esame.

6

CAPITOLO 1. NOZIONI DI BASE 7

1.3.2 Tempo interarrivo in un processo di Poisson

In un processo stocastico Poissoniano la funzione densità di probabilità del tempo interarrivo, cioè deltempo che intercorre fra due arrivi, può essere facilmente trovata. Vediamo come.Dire che l’intervallo di tempo intercorso fra due arrivi è maggiore di t significa dire che non vi sono statiarrivi in t. La probabilità che il tempo interarrivo sia minore di t è dunque:

Pr {τ 6 t} = 1− Pr {τ > t} = 1− P (0, t)

In men che non si dica abbiamo già ricavato la funzione cumulativa (per t ≥ 0) del tempo interarrivo:

Fτ (t) = Pr {ti 6 t} = 1− e−λt

Dunque, se deriviamo, otteniamo la PDF (sempre valida per t ≥ 0):

fτ (t) = λe−λt

Quella appena trovata viene detta densità di probabilità esponenziale.

1.4 Variabile aleatoria esponenziale

Il valor medio e la varianza della distribuzione esponenziale, poco sopra enunciata, sono pari a:

valor medio =1λ

varianza =1

λ2

Una delle principali proprietà della variabile aleatoria esponenziale è la sua assenza di memoria. Al contrariodi quanto si potrebbe intuire, la conoscenza del fatto che non sono avvenuti eventi fino a T0 non influenzail tempo di attesa dell’arrivo successivo. La distribuzione esponenziale è l’unica distribuzione tempo-continua che gode di questa proprietà.

1.4.1 Caratterizzazione del tempo di servizio

Dato un sistema a coda, se ϑ̄ è il tempo medio di servizio, si definisce frequenza media di servizio:

µ =1ϑ̄

Nel caso di variabile aleatoria esponenziale si ha:

fϑ (t) = µe−µt

Fϑ (t) = 1− e−µt

ESERCIZIO:

Sistema a coda con 5 servitori indipendenti e occupati all’istante t0 = 0, distribuzione esponenzialenegativa per il tempo di servizio, ϑ̄ = 10 minuti, nessun ulteriore arrivo.

Probabilità che nessuno abbia completato il servizio dopo 10 minuti?

Possiamo effettuare le considerazioni che riportiamo di seguito in virtù dell’assenza di memoria della v.a.esponenziale. La probabilità che nessun cliente abbia finito dopo 10 minuti si ricava tenendo conto che:

Pr {Nessun servito dopo 10 minuti} = 1− Pr {Almeno un servito dopo 10 minuti}

Tenendo conto che si ha, per la distribuzione cumulativa del tempo di servizio

Fϑ (t) = 1− e−µt

7


e che la presenza di cinque servitori indipendenti e occupati fa sì che la frequenza di morte sia2

µ′ = 5µ =5ϑ̄

abbiamo chePr {Nessun servito dopo 10 minuti} = 1− (1− e−5µt) = 0, 0067

La probabilità che dopo 20 minuti tutti abbiano completato il servizio?

La probabilità che dopo 20 minuti tutti abbiano completato il servizio è calcolabile mediante una probabilitàcongiunta:

Pr {fine 5 utenti entro 20 min} = Pr {fine primo utente entro 20 min} ·Pr {fine secondo utente entro 20 min} · etc... =

=(1− e−µt)5 =

(1− e−20µ

)5= 0, 483

Determinare la densità di probabilità del tempo di servizio dell’ultimo cliente che esce.

Ovviamente l’istante d’uscita dell’ultimo cliente equivale all’istante in cui tutti i clienti sono stati serviti. Perciòla distribuzione di probabilità di ϑ̄5 è, come abbiamo appena trovato,

Fϑ5(t) = (1− e−µt)5

La relativa densità di probabilità si ottiene per derivazione:

fϑ5(t) = 5µ(1− e−µt)4

1.4.2 La crescita esponenziale del traffico

Ogni tanto capita che, nei testi d’esame e negli esercizi, si faccia l’ipotesi di crescita esponenziale deltraffico in X giorni/mesi/anni. . .

ESEMPIO:

In data odierna si prevede un traffico offerto pari ad A0 = 11 E. Si prevede un raddoppio in untriennio con andamento esponenziale. Calcolare l’andamento nel tempo del traffico offerto.

Utilizzando gli anni come unità di misura del tempo, la locuzione ’in data odierna’ si riferisce ovviamente at = 0. Il raddoppio deve invece avvenire in t = 3, cioè allo scadere del terzo anno (o all’inizio del quarto, che dirsi voglia). Siccome l’andamento esponenziale ha forma

x = Aetτ

dovrà verificarsi:2 · Ainiziale

0 = Ainiziale0 e

3τ

Da cui:τ = 4.33 anni

A questo punto basta effettuare il calcolo in t ∈ [0, 3] e, sfruttando i risultati già calcolati, si hanno i risultati intabella 1.1 e in figura 1.1.

2Scrivere tale relazione è possibile solo in virtù del fatto che, se nessuno muore entro 10 minuti, significa anche che i servitoririmarranno tutti occupati in questo lasso di tempo. Ciò rende invariante la frequenza di morte complessiva del nostro sistema.Se essa variasse, in seguito all’uscita di un cliente, non potremmo unificare la densità di probabilità in un unico esponenziale con,all’esponente, 5µ, come viene fatto di seguito.

8

CAPITOLO 1. NOZIONI DI BASE 9

Anno Traffico0 A0e0/4.33 = 111 A0e1/4.33 = 13.92 A0e2/4.33 = 17.53 A0e3/4.33 = 22

Tabella 1.1: Crescita esponenziale del traffico (raddoppio in un triennio)

Figura 1.1: Rappresentazione grafica della esponenziale del traffico (raddoppio in un triennio)

1.5 Catene di Markov

Un processo aleatorio è detto catena di Markov se la sequenza dei valori che esso assume nel tempoè tale per cui lo stato del processo nell’istante n-simo è condizionato unicamente dallo stato all’istanteimmediatamente precedente a quello considerato. Una catena di Markov si dice omogenea se le probabilitàdi transizione da uno stato all’altro, ovvero

Pij (n) = Pr {Xn = j |Xn−1 = i}

non dipendono dall’istante di tempo considerato ma solamente dagli stati di partenza e di arrivo. In altreparole si deve avere:

Pij(n) = Pij ∀n

Una catena di Markov tempo-omogenea può essere graficamente rappresentata tramite il cosiddetto dia-gramma degli stati: ogni cerchio rappresenta uno stato e le frecce indicano la transizione da uno stato adun altro con associata la probabilità che tale transizione avvenga.

La probabilità di trovarsi nello stato k all’istante n si dice probabilità di stato:

πj(n) = Pr{Xn = j}

1.5.1 Processi di nascita e di morte

Si dicono processi di nascita e morte dei processi di Markov in cui le transizioni di stato possonoavvenire solo tra stati adiacenti. Limitandoci al caso di processi tempo omogenei, nel caso dei processi dinascita e di morte si è soliti indicare con una simbologia ’ad hoc’ le frequenze di transizione fra stati. Siainfatti:

• λk la frequenza di transizione dallo stato k allo stato k + 1;

9


• µk la frequenza di transizione dallo stato k allo stato k− 1.

I parametri λk e µk sono anche dette ritmo (o frequenza) di nascita e ritmo (o frequenza) di morte dallo stato k.All’equilibrio, in particolare, si ha:

Pk = P0

k−1

∏i=0

λiµi+1

, i > 0, P0 =1

1 + ∑k>0

k−1∏i=0

λiµi+1

Questa formula viene utilizzata per ricavare tutte le formule ’di stato’ relative ai casi che vedremo diseguito (la dimostrazione non verrà tuttavia riportata).

10

Capitolo 2

I sistemi a coda

2.1 Parametri e notazione

Siano:

• m il numero di servitori;

• δ̄ il tempo medio di servizio, ovvero il tempo che il nostro cliente trascorre all’interno del sistema. Perdefinizione il tempo medio di servizio comprende:

– il tempo medio impiegato in coda (η̄);

– il tempo medio impiegato ad essere serviti (ϑ̄);

Dunque si ha:δ̄ = η̄ + ϑ̄

Il tempo medio di servizio è spesso - ma non sempre - una quantità nota o una specifica vincolantesulle prestazioni del nostro sistema da far assolutamente rispettare (e dalla quale partire per ricavarel’incognita dell’esercizio);

• ε̄ il tempo medio impiegato in coda sapendo di essere effettivamente entrati in coda. Non si confon-da questo parametro con η̄: quest’ultimo valore è tanto minore rispetto a ε̄ tanto più bassa è laprobabilità di finire in coda, visto che in questo caso si tiene conto dei casi in cui l’attesa è nulla;

• µ = 1ϑ̄

la frequenza di servizio;

• A0 = λϑ̄ il traffico offerto. Tale parametro è la somma di

– traffico smaltito: As = λsϑ̄;

– traffico perduto: Ap = λpϑ̄;

Tutte queste quantità sono adimensionali, ma si misurano comunque in Erlang [E] in onore almatematico danese precursore degli studi sulla teoria del teletraffico.

• ρ = Asm l’utilizzazione dei servitori. Indica quanto efficacemente viene utilizzato il sistema: l’ideale

sarebbe avere questo parametro il più possibile vicino ad 1;

• Pk la proprietà di stato relativa al parametro k, ovvero la probabilità che nel sistema vi siano kservitori occupati.

2.2 SistemaM/M/∞

Sono i sistemi più semplici: il numero di servitori si assume infinito, e quindi ogni volta che un clientesi presenta al sistema trova sicuramente un servitore pronto a soddisfare la sua richiesta. Siccome si viene

11

12 CAPITOLO 2. I SISTEMI A CODA

serviti immediatamente, lo spazio di attesa è nullo e non vi sono utenti rifiutati; il traffico servito e iltraffico offerto, dunque, coincidono:

λϑ̄ =λ

µ= A0 = As

Il ritmo di nascita, ovvero la velocità con cui gli utenti entrano nel sistema, è costante e pari al ritmo diarrivo del processo di Poisson:

λ = λk

La frequenza di morte, invece, dipende da quanti utenti sono all’interno del sistema; in maniera intuitiva,se in un certo istante sono presenti molti utenti, è alta la probabilità che siano piuttosto numerosi anchequelli in procinto di uscire. Se invece gli utenti sotto servizio sono pochi, saranno altrettanto pochi quellia dover lasciare il sistema. Infatti si ha:

µk = kµ

Questa proprietà è valida in generale e non solo per questo tipo di sistema. La probabilità di stato, ovverola probabilità che vi siano k servitori impegnati, è

Pk =Ak

0k!

e−A0

Il numero medio di utenti presenti nel sistema coincide ovviamente con il numero medio di servitorioccupati:

A = λδ̄ = λθ̄ = A0 = As

Dicevamo che il sistema non si troverà mai in stato di congestione: in ogni caso una sorta di misura dellivello di occupazione del sistema può essere il calcolo della probabilità di trovare m o più di m servitoriimpegnati:

πm = 1−m−1

∑k=0

Ak0

k!e−A0 = A (m, A0)

La sopraccitata A viene detta formula A di Erlang.Sistemi di questo tipo sono poco frequenti negli esercizi. . . C’è ben poco da calcolare!

2.3 SistemaM/M/m/0

Finalmente un sistema più serio: l’M/M/m/0 ha m servitori e nessuno spazio di coda. Dunque,qualora una chiamata giunga ad una centrale avente tutti i circuiti in uscita impegnati, essa viene rifiutata obloccata. Per questo tale sistema viene detto a chiamate bloccate cancellate. Per quanto riguarda le frequenzedi nascita e di morte si ha:

λ = λk → finché c’è qualche servitore libero, 0 altrimenti

µk = kµ

La probabilità di stato è:

Pk =Ak

0k!

(m

∑l=0

Al0

l!

)−1

Contrariamente al sistema M/M/∞, questo non può riempirsi all’infinito, ma solamente fino ad m.Dunque la probabilità di blocco è data dalla probabilità che tutti i servitori siano occupati e - dunque -che un utente arrivi e trovi pieno il sistema:

πp = Pm =Am

0m!

(m

∑k=0

Ak0

k!

)−1

= B(m, A0)

Questa formula è nota come la B di Erlang. Essa può essere ricavata anche ricorsivamente:

B (m, A0) =A0B (m− 1, A0)

m + A0B (m− 1, A0), con B (0, A0) = 1

La cosa bella della B di Erlang è la sua insensibilità alla distribuzione del tempo di servizio: in pocheparole, può essere usata per calcolare la probabilità di blocco nei sistemiM/G/m/0.

12

CAPITOLO 2. I SISTEMI A CODA 13

A B EsternoA - 5 5B 3 - 2

Esterno 4 1 -

Tabella 2.1: Schema del traffico offerto

ESERCIZIO:

Il tipico esercizio in cui si richiede l’applicazione della B di Erlang è quello in cui si considerano una o piùcentrali collegate fra di loro e/o con l’esterno (PSTN = Public Switched Telephone Network). Spesso vienefornita una tabellina come la 2.1: in essa è riportato il traffico offerto A0 da ogni centrale (v. riga) ad ognialtra (v. colonna). Ovviamente la diagonale non contiene valori, visto che non ha senso definire un traffico dauna locazione verso sé stessa. In tal caso viene specificato che B, per andare verso l’esterno, deve passare da A.Questo particolare non è di poco conto, visto che influenza le caratteristiche del flusso di traffico attraverso lelinee: per questo è sempre importante scindere le informazioni che vengono date in tabelle come la 2.1 rispetto allatopologia di maglia con coi abbiamo a che fare. Il traffico infatti può imboccare diverse vie in base ai collegamentilungo i quali è possibile dipanare i pacchetti: in una rete a maglia completa, ad esempio, ogni centrale è connessaa tutte le altre, dunque non ci sarà bisogno di passare tramite altre locazioni. Non è questo il caso dell’esercizioche stiamo esaminando: considerando infatti che il traffico è bidirezionale abbiamo

• tra A e l’esterno (E): il traffico (A→ E) + (E→ A) +(B→ E) + (E→ B). In totale: 5 + 2 + 4 + 1 =12 E. Visto che A è responsabile ’dei rapporti col mondo esterno’ si poteva pensare di rispondere a questoquesito sommando il traffico della colonna più a destra della tabella 2.1 con quello dell’ultima riga.

• tra A e B: il traffico (A→ B) + (B→ A) +(B→ E) + (E→ B). In totale: 5 + 3 + 2 + 1 = 11 E.

A questo punto ci viene richiesto di dimensionare il numero di servitori presenti fra E ad A nonché fra A e B.Niente di più semplice: il sistema è a chiamate bloccate cancellate, dunque dobbiamo usare la B di Erlang. Ilcalcolo della B di Erlang è parecchio palloso, quindi si consiglia l’uso delle tabelle o di un bello scriptino Matlab:

% Questa funzione restituisce il numero minimo m di servitori nel caso di% sistema M/M/m/0, data una certa probabilità di blocco massima p% (specifica di progetto) e un traffico offerto A0.

function [m] = bErl(A0,p)

m = 0;B = 1;while (B > p)

m = m+1;B = (A0*B)/(m+A0*B);

end

Abbiamo come risultato:B (m, 11) 6 0.01⇒ m = 19

B (m, 12) 6 0.01⇒ m = 20

Il numero medio di utenti nel sistema è pari al numero medio di servitori occupati, e quindi al trafficosmaltito, per cui:

A = As =(1− πp

)A0 = [1− B (m, A0)] A0

Si ha inoltre:λs =

(1− πp

)λ

δ̄ =Aλs

=A0

λ=

1µ

= ϑ̄

L’utilizzazione dei servitori è pari a:

ρ =As

m=

A0(1− πp)m

13


Si ha inoltre che, a parità di qualità di servizio, un sistema di grandi dimensioni fa un migliore uso deisuoi servitori. Per questo è sempre conveniente raggruppare il traffico.

ESERCIZIO:

Scenario: centralino. Utenti da servire pari a 100, traffico per utente pari a 0,05 Erlang, modello aperdita, probabilità di perdita/blocco da mantenere inferiore all’1%.

Numero di collegamenti per il centralino?Il traffico totale, cioè il traffico offerto, è banalmente:

100 · 0, 05 = 5 Erlang

A questo punto dobbiamo calcolare m a partire dalla:

B(m, 5) < 0, 01

Utilizzando lo script già sperimentato nell’esercizio precedente, oppure calcolando per tentativi la B di Erlang, siha:

m = 11

Utilizzazione dei collegamenti?

L’utilizzazione dei servitori, cioè dei collegamenti, è:

ρ =As

m=

A0(1− πp)m

=A0(1− B(11, 5))

m

Calcoliamo la B di Erlang con lo scriptino magico seguente:

function [p] = bErlang(m,A0)

p = 1;for i=1:m

p = (A0*p)/(i+A0*p);end

e otteniamo:

ρ =A0(1− B(11, 5))

m=

5 · (1− 0, 0083)11

= 0, 4508

Probabilità di blocco e rendimento nel caso di un collegamento fuori servizio?

In pratica si chiede di rieffettuare i calcoli del punto precedente con m = 10. Senza bisogno di una granimmaginazione:

• La probabilità di blocco aumenterà. E che caspita: è morto un servitore!

• L’utilizzazione dei servitori aumenterà, perché quelli rimasti dovranno in parte sopperire alla scomparsa diuno di loro. É infatti vero che in ρ è presente, al numeratore, il parametro (1− πp) (e dunque l’aumentodi πp contribuisce a diminuire ρ), tuttavia m - al denominatore - è passato da 11 a 10!

E infatti. . .πp = B (10, 5) = 0, 0183

ρ =A0(1− πp

)m

=5 (1− 0, 0183)

10= 0, 49

Probabilità di blocco e rendimento nel caso di aumento del 10% del traffico?

Torniamo al caso m = 11. Il traffico offerto questa volta è:

A′0 = A0 · 1, 1 = 5, 5

14


Dunque:B(11, 5.5) = 0, 0144

ESERCIZIO:

Due centrali telefoniche collegate da m = 80 canali, sistema a perdita. A un certo punto il trafficosale a A0 = 80 Erlang. Obiettivo di qualità: mantenere il traffico perduto Ap < 1 Erlang. Quanti canalibisogna aggiungere nel caso di:

1. canali aggiuntivi indistinguibili da quelli pre-esistenti: in questo caso, per garantire il requisito di qualità,dobbiamo applicare la B di Erlang e moltiplicare per il traffico offerto.

Ap = B(m + x, A0) · A0 < 1

Utilizzando lo script in Matlab già esposto in altri esercizi oppure consultando le tabelle si ha:

m + x = 95

Da cui, sapendo noi che m = 80:x = 15

2. canali aggiuntivi contenuti in un fascio separato (ipotesi di traffico Poissoniano anche su di loro):in questo caso, anzitutto, dobbiamo capire quanti Erlang vengono mediamente rifiutati (ricordiamo che ilsistema è a chiamate bloccate/cancellate) sulla linea avente m = 80, dopodiché utilizzeremo tale parametroper dimensionare l’altro fascio di collegamenti. Volenti o nolenti, ci serve nuovamente la B di Erlang:

traffico perso nella prima linea: Ap1 = A0B (m, A0) = 80 · B (80, 80) = 6, 73

Con la stessa formula calcoliamo le linee che servono nel secondo collegamento, imponendo:

Ap = B (x, 6.73) · 6.73 < 1

Si ottene infine:x = 9

Ma come! - verrebbe da sbottare - abbiamo sempre detto che conviene concentrare il traffico e ora inveceappare più conveniente separarlo? Bisogna però tenere presente che questo punto soggiace all’ipotesi ditraffico Poissoniano su entrambe le vie: nella realtà quest’ipotesi è errata, in quanto si dimostra che il trafficosul secondo fascio di cavi è di tipo peaky (cioè con una varianza maggiore del valor medio). Questo si deveal fatto che, se un utente trova il sistema occupato, gli utenti che lo seguono hanno maggior probabilità ditrovare anche loro occupato rispetto ad utenti scelti a caso: ne risulta perciò un traffico molto più correlatodi quello Poissoniano. Il numero di giunzioni che - nel mondo reale - sarebbe necessario fornire in questosecondo punto dell’esercizio continua dunque ad essere pari a 15. Pazienza.

2.4 SistemaM/M/m

Rispetto al sistema precedente, questo dispone di una bella coda infinita in cui porre gli utenti chearrivano nel sistema ma non trovano nessuno pronto a servirli. Il sistema è dunque senza perdita e si ha:

As = A0

La frequenza di nascita è pari aλk = λ

La frequenza di morte è invece: {kµ per k < m

mµ per k > m

15


ESERCIZIO:

Sistema a coda con 5 servitori indipendenti e occupati all’istante t0 = 0, distribuzione esponenzialenegativa per il tempo di servizio, ϑ̄ = 10 minuti, nessun ulteriore arrivo.

Tempo medio necessario per il completamento del servizio del primo cliente?Domanda che a una prima lettura sembra banale ma che invece nasconde un sottile trabocchetto. Si potrebbeinfatti pensare che tale tempo medio sia pari a ϑ̄ = 10 minuti, ma questo non è vero perché abbiamo in campo nonuno, bensì cinque servitori indipendenti e tutti quanti impegnati (non si sa da quanto). La variabile esponenzialenegativa è senza memoria, certo, ma risulta intuitivo il fatto che a un maggiore numero di utenti all’interno delsistema farà da controcanto una maggiore probabilità di ’veder uscire presto’ qualcuno, ovvero colui che nel testodell’esercizio viene chiamato ’il primo cliente’. Se all’interno del sistema è presente un solo utente, questo usciràmediamente dopo 10 minuti; ma se gli utenti fossero un milione, e giungendo noi ad esaminare il sistema in unqualsiasi istante, è molto probabile che il primo termini di essere servito lì a pochi millisecondi. Numericamenteabbiamo che, siccome k = 5, la frequenza di morte sarà 5µ e dunque:

ϑ̄1 =1

5µ= 2 minuti

Tempo medio necessario per il completamento dell’ultimo cliente?Anche qui si potrebbe d’impulso rispondere che tale tempo è pari a ϑ̄ = 10 minuti. In realtà anche questa voltanon è così; ϑ̄ è infatti il tempo di servizio medio, mentre il nostro quesito ci chiede quanto tempo impiega adessere servito il più lento dei cinque clienti nel sistema (cioè l’ultimo). Risulta quindi ben difficile pensare chetale quantità sia pari al tempo medio in senso stretto, cioè 10 minuti! Per arrivare al risultato bisogna dunqueragionare nel seguente modo: il primo cliente uscirà mediamente dopo 1

5µ minuti, come abbiamo visto nel puntoprecedente. Dopodiché dobbiamo fare finta di giungere ad esaminare il sistema in quell’esatto istante: questonon cambia nulla, visto che la distribuzione esponenziale gode di assenza di memoria, senonché questa volta iservitori occupati sono quattro e non cinque. Dunque il cliente successivo uscirà dal sistema mediamente dopo 1

4µ

minuti. Possiamo ripetere il ragionamento precedente e immaginare di giungere in quell’esatto momento, nonchédi sfruttare nuovamente l’assenza di memoria. Per farla breve, il risultato è:

ϑ̄5 =1

5µ+

14µ

+1

3µ+

12µ

+1µ

= 22, 83 minuti

Risulta chiaro che sistemi del genere, non avendo un numero infinito di servitori, non possono reggerequalunque tipo di frequenza d’arrivo da parte degli utenti: se questi arrivano troppo velocemente, infatti,non si è abbastanza veloci per servirli tutti e si finisce per ingrossare la coda fino all’infinito. Il limite entroil quale ciò non accade, e per cui il sistema è stabile, è il seguente:

ρ =A0

m=

λ

mµ< 1

Quest’ultima viene detta condizione di stabilità e deve essere verificata perché il sistema non collassi. Spessoquesta condizione è utilizzata negli esercizi, dunque è bene tenerla a mente.

Le probabilità di stato sono:

Pk =

(m−1

∑l=0

Al0

l!+

Am0

m!m

m− A0

)−1Ak

0k!

per 0 ≤ k < m

(m−1

∑l=0

Al0

l!+

Am0

m!m

m− A0

)−1Ak

0m!mk−m per k ≥ m

La probabilità di congestione, ovvero l’eventualità che un cliente entri nel sistema e trovi tutti i servitoriimpegnati venendo quindi messo in attesa, è pari a:

πr =Am

0m!

mm− A0

(m−1

∑k=0

Ak0

k!+

Am0

m!m

m− A0

)−1

= C (m, A0)

16


Tale funzione è altresì denominata formula C di Erlang. Può essere ricorsivamente ricavata nel seguentemodo:

C (m, A0) =[

1 +m− A0

m

(m− 1− A0C (m− 1, A0)

(m− 1− A0) C (m− 1, A0)

)]−1

Acquisendo pratica negli esercizi si noterà che, per qualunque valore di m e A0, la C di Erlang ha valorisuperiori alla B di Erlang. Ciò si può intuitivamente spiegare dicendo che nel sistema con attesa il trafficorisulta superiore, per cui maggiore sarà la probabilità di trovare i servitori impegnati.

Il numero medio di utenti in coda è

Ac = C (m, A0)A0

m− A0

mentre il numero medio di utenti in coda condizionato al fatto di fare coda è:

Ac|coda =A0

m− A0

Il tempo medio speso in coda sarà:

η̄ =Ac

λ= C (m, A0)

ϑ̄

m− A0

Infine, il seguente è il tempo medio di permanenza nel sistema:

δ̄ =Aλ

= ϑ̄ +ϑ̄

m− A0C (m, A0)

Come già abbiamo detto (vedi paragrafo 2.1), il tempo medio speso in coda condizionato al fatto chefacciamo la coda sarà leggermente più alto di η̄ e pari a:

ε̄ =ϑ̄

m− A0

Concludiamo questa parte sui sistemiM/M/m dando le seguenti funzioni cumulative:

• per il tempo medio speso in coda:

Fη (t) = 1− C (m, A0) e−(mµ−λ)t

• per il tempo medio speso in coda da chi la coda sicuramente la fa:

Fε (t) = 1− e−(mµ−λ)t

ESERCIZIO:

Tempo medio di servizio ϑ̄ = 3 minuti, traffico offerto A0 = 21 Erlang, coda infinita, probabilità dipassare meno di ε0 = 3 minuti in coda (sapendo di essere in coda) maggiore o uguale al 90%. Trovarem, cioè il numero di servitori, e il tempo medio speso in coda η̄ (non sapendo a prescindere se andremoin coda)

Bene bene, questo è il tipico esempio di sistema M/M/m. Siccome non è sicuramente di tipo M/M/1(vedi paragrafo 2.5), visto che m è in maniera intuitiva molto maggiore di 1, dovremo giocoforza utilizzare la Cdi Erlang. In particolare, faremo riferimento alla formula:

Fε (t) = 1− e−(mµ−λ)t < 0, 9

17


Questa funzione cumulativa permette di ricavare la probabilità di passare meno di t minuti in coda: sostituendoi dati otteniamo

1− e−(mµ−λ)t > 0, 9

e−(mϑ̄−1−A0ϑ̄−1)ε0 < 0, 1

−(

mϑ̄−1 − A0ϑ̄−1)

ε0 < ln 0, 1

− (m · 0, 3̄− 21 · 0, 3̄) · 3 < ln 0, 1

7−m · 0, 3̄ <ln 0, 1

3

m >7

0, 3− ln 0, 1

3 · 0, 3̄=

70, 3− ln 0, 1 = 23, 34

m > 24

Ora che abbiamo una specifica su m possiamo lanciarci nel calcolo di η:

η̄ = C(m, A0)ϑ̄

m− A0

Per calcolare la C di Erlang può essere utile il seguente script Matlab:

function [C] = cErlang(m,A0)

sum = 0;for i=0:(m-1)

sum = sum + (A0^i)/factorial(i);endC = (((A0^m)/factorial(m))*(m/(m-A0)))/(sum+(((A0^m)/factorial(m))*(m/(m-A0))));

Sfruttando a piene mani i potenti mezzi informatici per risolvere la nostra equazione abbiamo:

η̄ = 0, 4249 · 324− 21

= 0, 4249 minuti

ESERCIZIO:

Scenario: centralino a commutazione di circuito (sistema a coda con numero finito di servitori →sistema M/M/m). Utenti: 500. Traffico/utente = 0.01 Erlang. Durata media della chiamata ϑ̄ = 5minuti. Servitori: 11.

1. Probabilità di ritardo?

Anzitutto calcoliamo il traffico offerto:

A0 = 500 · 0, 01 = 5 Erlang

A questo punto, per calcolare la probabilità di ritardo, è sufficiente applicare la C di Erlang:

C(11, 5) = 0, 0151

2. Lunghezza media della coda?Il numero di utenti in coda risulta essere:

Ac = C (11, 5)A0

m− A0= 0, 011

Intuitivamente, tanto maggiore è il numero di servitori rispetto al traffico offerto e tanti meno utentitroveremo in coda.

18


3. Lunghezza media della coda quando un utente va in coda?Al punto precedente abbiamo calcolato il numero medio di utenti in coda moltiplicando la probabilità diandare in coda (la C di Erlang), per il termine A0

m−A0. La domanda cui stiamo rispondendo è simile a

quella precedente, ma questa volta sappiamo di essere in coda: dunque sfrutteremo la seguente proprietàdel calcolo probabilistico

P (A) = P (A |B )︸︷︷︸quella che stiamo cercando

· P (B)︸︷︷︸probabilità della condizione

⇒ Ac =A0

m− A0· C (11, 5)

per ottenere

Ac|coda =A0

m− A0= 0, 83

4. Tempo medio di attesa in coda?Altra domanda a cui rispondere seccamente, con una formula. Non c’è un granché da capire, basta applicarela regola:

η̄ =ϑ̄

m− A0C (11, 5) = 0, 65 secondi

5. Tempo medio di attesa di un utente che attende in coda?Le domande 4 e 5 sono analoghe alle 2 e 3. Sapendo che si è verificata la condizione ’andare in coda’,possiamo scrivere:

ε̄ =ϑ̄

m− A0= 50 secondi

6. Probabilità di disservizio nei casi di 1 e 6 collegamenti fuori servizio?Nel caso di un collegamento fuori servizio dobbiamo calcolare la C(10,5) invece che la C(11,5):

C(10, 5) = 0, 0361

Nel caso di 6 collegamenti fuori servizio dovremmo calcolarci la C(5,5), ma non ha neppure senso provarci:è infatti intuitivo che il sistema, in tal caso, è instabile e presenta una coda che si allunga all’infinito (iservitori sono troppo pochi). La prova matematica di quanto detto è la non sussistenza della seguentedisequazione di stabilità/stazionarietà:

ρ <A0

m

ESERCIZIO:

Commutatore a pacchetto, 10 uscite, coda infinita d’attesa sulle uscite, ogni uscita è servita da 2linee a C = 64.000 bit/s, arrivi poissoniani sulle linee di ingresso: λi = 1 pacchetti/secondo, pacchettidistribuiti uniformemente sulle uscite, lunghezza media dei pacchetti D = 64.000 bit.

Numero massimo Nmax di linee in ingresso al commutatore affinché il tempo medio di permanenzanon superi i 2 secondi?Esercizio un po’ meno convenzionale del solito, questo. Qualche considerazione preliminare:

• il commutatore a pacchetto ha un numero finito di servitori e una coda infinita: tutto questo dice a granvoce ’C di Erlang’;

• la cosa ’difficile’ di questo esercizio è comprendere la topologia del nostro dispositivo: abbiamo un commu-tatore con Nmax (da dimensionare) linee di ingresso e 10 linee di uscita, ognuna con 2 servitori. Modellareil sistema come unM/M/20/∞ è però un po’ scomodo. . .

• . . . e infatti, siccome tutti i buffer d’uscita sono uguali ed il traffico viene equiripartito in modo uniforme, ilδ̄ nel sistema coincide con il δ̄ di ogni buffer. Per questo conviene scindere il sistema in dieci sotto-sistemidi tipoM/M/2/∞;

19


• a questo punto l’unica accortezza è quella di ’scalare’ i parametri λ, per renderli conformi ai sotto-sistemi,e di procedere con le solite formule.

Ciò che dobbiamo trovare ha espressione:

δ̄ =Aλ

= ϑ̄ +ϑ̄

m− A0C (2, A0)︸︷︷︸

sistema M/M/2

Il tempo medio di servizio ϑ̄ possiamo ricavarlo: esso è pari a

ϑ̄ =DC

=64.00064.000

= 1 s

Pure m l’abbiamo; l’unica cosa che ci manca è A0: dal traffico offerto desumeremo infatti quante linee d’ingressocaratterizzate da λi = 1 è possibile fornire al commutatore senza ingozzarlo. Sostituendo un po’ di parametri:

δ̄ =2− A0 + C (2, A0)

2− A0

Ora bisogna fare lo sforzo di ricordarsi la formula letterale della C di Erlang:

C (2, A0) =A2

02!

22−A0

1∑

k=0

Ak0

k! + A20

2!2

2−A0

=A2

02−A0

1 + A0 + A20

2−A0

=A2

02− A0 + (2− A0) A0 + A2

0=

=A2

02− A0 + 2A0 − A2

0 + A20

=A2

02 + A0

Il tempo medio speso nel sistema assume quindi la forma:

δ̄ =2− A0 + A2

02+A0

2− A0=

(2− A0) (2 + A0) + A20

(2− A0) (2 + A0)=−A2

0 + 4 + A20

−A20 + 4

=4

−A20 + 4

A questo punto è necessario esplicitare il nostro Nmax in funzione di A0:

A0 = λi Nmaxϑ̄ = 1 · Nmax · 1 = Nmax

Dopodiché, siccome abbiamo precedentemente ragionato sul sistema M/M/2, scaliamo questo parametro inbase al numero di code d’uscita:

A′0 =A0

10Quello calcolato è il traffico offerto in ingresso ad ognuno dei 10 sotto-sistemi in uscita che, ricordiamo, dispongonociascuno di due code e due servitori; sostituendo nell’equazione del tempo medio δ̄, riarrangiata col parametroA′0:

δ̄ =4

4− A′02 =

11− 0, 25A′0

2 =1

1− N2max

400

< 2

Ora dobbiamo assicurarci che il traffico proveniente dalle Nmax vie d’ingresso non ingozzi le linee d’uscita, ovesono presenti i servitori. Imponendo la stabilità sulle linee d’uscita:

ρ =A0

m=

Nmax

20< 1

Abbiamo quindi impostato un bel sistemozzo: 1

1− N2max

400

< 2

Nmax < 20

Tra l’altro la disequazione di stazionarietà (Nmax < 20) ci assicura che il denominatore della relazione in Nmaxsia sicuramente positivo! Possiamo quindi gioiosamente scrivere:

1 <N2

max200

N2max < 200⇒ Nmax < 14, 1⇒ 14 linee in ingresso

20


2.5 SistemaM/M/1

Come si intuisce bene, questo è un caso particolare di sistemaM/M/m. Vale tuttavia la pena soffer-marcisi in quanto spesso conviene scomporre sistemi complessi in più sistemi di questo tipo da analizzaresingolarmente.Le frequenze di nascita e di morte (rispettivamente λ e µ) coincidono con le frequenze di arrivo e dipartenza). Inoltre si ha che:

A0 = ρ =A0

m=

A0

1Tale parametro è inoltre pari alla probabilità di andare in coda:

ρ = πr

Le probabilità di stato sono invece:

Pk =ρk

+∞∑

k=0ρk

ρ<1−−→ (1− ρ) ρk

Il numero medio di utenti nel sistema è:A =

ρ

1− ρ

Il tempo medio speso nel sistema risulta essere:

δ̄ =Aλ

=ϑ̄

1− ρ=

1µ− λ

Il numero medio di utenti in servizio è As = ρ, per cui il numero di utenti in coda risulta:

Ac =ρ2

1− ρ

Infine si ha:η̄ =

Ac

λ= ϑ̄

ρ

1− ρ

ε̄ =ϑ̄

1− ρ=

1µ− λ

Anche se può sembrare strano, le seguenti densità di probabilità per e δ coincidono:

fε (t) = fδ (t) = (µ− λ) e−(µ−λ)t ⇒ Fε (t) = Fδ (t) = −e−(µ−λ)t

Questo risultato non ha una semplice spiegazione fisica, ed è comunque limitato al caso particolare disistemaM/M/1.

Enunciamo infine il teorema di Burke, in base al quale le partenze da un sistema M/M/1 sono unprocesso di Poisson con valor medio pari a λ−1. Questo ci permette di utilizzare tale tipo di sistemi perstudiare multiplatori statistici: essi si compongono di un insieme di linee di ingresso, sulle quali vengonotrasmesse informazioni a pacchetto, che vanno inoltrate su di una unica linea di uscita (a divisione ditempo). Per risolvere i casi in cui un pacchetto arriva su di una linea quando un altro è in corso ditrasmissione è necessario prevedere una coda d’attesa. Se gli arrivi dei pacchetti si possono rappresentarecome un processo di Poisson ed i tempi di trasmissione sono approssimativamente esponenziali, allora ilmodello aM/M/1 è perfetto per studiare il comportamento del multiplatore.

ESERCIZIO:

Multiplatore a pacchetto, due linee d’uscita a C = 2 Mbit/s, due ingressi con arrivi poissonianiλ1 = 10 pacc/s e λ2 = 20 pacc/s, code di lunghezza infinita, pacchetti di lunghezza media D = 40 Kbit.

21


1. CASO 1: una linea ↔ una coda. Pacchetti in ingresso distribuiti in maniera uniforme sulle duecode. Tempo medio speso nel sistema?

Una cosa che possiamo anzitutto calcolare è il tempo medio di servizio: esso è pari a

ϑ̄ =DC

=40 Kbit2 Mbit

= 20 ms

Il trucco per risolvere quest’esercizio è quello di scindere il nostro sistema in due sottosistemi M/M/1.Questa metodologia - quando può essere applicata - è super-consigliata, per più di un motivo:

• le formule da ricordare sono molto più elementari;

• ridurre un sistema a più sottosistemi è semplice perché basta rimodulare i parametri λ ed eventualmenteA0;

• è l’unica scelta possibile quando vi sono servitori che lavorano con ritmi e traffici diversi;

• non c’è bisogno di calcolare la pallosissima C di Erlang;

• NOTA: questo trucchetto è possibile solo quando ogni servitore dispone di una propria coda!

Nel nostro caso, per ricomporre il sistema di partenza, sarà poi necessario effettuare delle medie pesate peri parametri in gioco.In questo primo punto ogni pacchetto, qualsiasi sia l’effettiva coda d’ingresso, ha un 50% di probabilità difinire in una delle due code d’uscita. Questo significa che si ha:

in 1 50%→ → out 150%↘ ↗50%↗ ↘

in 2 50%→ → out 2

Dunque ogni uscita riceverà pacchetti con una frequenza:

λ̃ =10 + 20

2= 15 pacc/s

Ecco che possiamo quindi determinare δ̄:

δ̄ =1

µ− λ̃= 0, 0286

2. CASO 2: una linea ↔ una coda. Pacchetti in arrivo da un prefissato ingresso finiscono semprenella stessa coda. Tempo medio speso nel sistema?

Questa volta la situazione è la seguente:

in 1 100%→ → out 1

in 2 100%→ → out 2

Dobbiamo quindi conservare i λi che ci vengono dati nel testo ed effettuare due conti distinti:

δ̄1 =1

µ− λ1= 0, 025 s

δ̄2 =1

µ− λ2= 0, 034 s

Infine, effettuiamo la media pesata:δ̄ = P1δ̄1 + P2δ̄2

Siccome dalla linea 1 e dalla linea 2 arrivano rispettivamente 1/3 e 2/3 dei pacchetti totali si ha:

δ̄ =13

1µ− λ1

+23

1µ− λ2

= 0, 0306 s

22


3. CASO 3: unica coda in cui vengono memorizzati e dalla quale vengono tratti tutti i pacchetti.Tempo medio speso nel sistema?In questo caso non è possibile scindere il sistema in due M/M/1 perché i due servitori fanno capo adun’unica coda. Rassegnamoci quindi alM/M/2, che avrà

λ = λ1 + λ2 = 30 pacc/s

Il traffico offerto è:A0 = λϑ̄ = 0, 6 E

La C di Erlang dà come risultato:C(2, 0.6) = 0, 1385

Il tempo medio speso nel sistema sarà infine:

δ̄ = ϑ +ϑ

m− A0C(2, 0.6) = 0, 022 s

Cosa abbiamo imparato? Che la condivisione dei servitori, per mezzo di un’unica coda di attesa, risulta vantaggiosain termini di prestazioni. Questo è quindi un altro esempio che rientra nel risultato generale che ci dice che lacondivisione delle risorse risulta in generale conveniente rispetto ad una loro ripartizione.

ESERCIZIO:

Sistema a coda con un’unica coda d’attesa di lunghezza infinita. Due flussi di traffico:

• ϑ̄1 = 0, 1, λ1 = 6 pacc/s;

• ϑ̄2 = 0, 08, λ2 = 10 pacc/s.

Due servitori: S1 serve solo i clienti di tipo 1, S2 solo quelli di tipo 2. Ciascun servitore può servire ipacchetti a lui corrispondenti indipendentemente dal fatto che vi siano o meno pacchetti dell’altro tipoin attesa di essere serviti.Probabilità che nel sistema siano presenti k1 = 4 clienti di tipo 1 e k2 = 2 clienti di tipo 2?Il fatto che l’esercizio specifichi l’esistenza di un’unica coda di lunghezza infinita potrebbe indurre a credere chesia obbligatorio l’uso delle formule per la risoluzione dei sistemiM/M/m (con m > 1 e pari a 2, nello specifico).In realtà ogni servitore, trattando solo una tipologia di pacchetti e potendo lavorare indipendentemente dallapresenza in coda di pacchetti dell’altro tipo, è come se fosse virtualmente dotato di coda (di lunghezza infinita).Dunque è opportuno scindere il sistema in due sotto-sistemi più semplici di tipoM/M/1. I traffici offerti sono:

• A01 = ρ1 = λ1ϑ̄1 = 0, 1 · 6 = 0, 6 E;

• A02 = ρ2 = λ2ϑ̄2 = 0, 08 · 10 = 0, 8 E.

La probabilità di avere k1 = 4 clienti di tipo 1 e, contemporaneamente, k2 = 2 clienti di tipo 2, si può ricavaremoltiplicando le probabilità riferite ai due sistemi presi singolarmente; ricordando che la probabilità di avere kutenti all’interno del sistema è1

Pk = ρk(1− ρ)

si ha:

• sistema 1: P4 = ρ41(1− ρ1)

• sistema 2: P2 = ρ22(1− ρ2)

1Formula valida se ρ < 1, cioè se il sistema è stazionario.

23


Dunque la soluzione al primo quesito è:

P4 · P2 = ρ41(1− ρ1)ρ2

2(1− ρ2)

Probabilità di avere complessivamente KT = 5 clienti di tipo qualsiasi all’interno del sistema?

Punto un po’ più arduo da dipanare, questo: siccome i clienti possono essere di qualunque tipo dovremoconsiderare la probabilità

5

∑k=0

Psistema 1k · Psistema 2

5−k =5

∑k=0

(1− ρ1) ρk1 (1− ρ2) ρ5−k

2

Il più, ora, è fare i calcoli.

ESERCIZIO:

Due tipi di dati per l’Unibo:

• traffico scientifico: λ1 = 100 pacc/s, requisito: δ̄ < 0, 5 s;

• traffico amministrativo: λ2 = 2 pacc/s, requisito: ε̄ > 0, 5 s con probabilità inferiore all’uno permille. Pacchetti di 8000 bit, noleggiati C = nC0 bit/s (C0 = 64000 bit/s) al prezzo di 6 milioni divecchie lire ogni C0. Offerta speciale: 32C0 (2,408 Mbit/s) a soli 90 milioni.

Due possibili scelte:

• unire i due flussi in un unico collegamento (opzione 1);

• separare i due flussi in parallelo (opzione 2). In questo caso si aggiungono 6 milioni di spesa perle apparecchiature di interfaccia. Si scelta l’opzione più vantaggiosa.

Mbé, intrigante ’sto esercizio.

1. consideriamo l’opzione 1: l’aggregazione del traffico è di per sé un fattore positivo, come ben sappiamo.Qui però abbiamo due flussi caratterizzati da diversi requisiti di qualità; trattarli nello stesso modo pre-supporrebbe che venisse soddisfatto il requisito più stringente (cioè quello del traffico amministrativo), eciò potrebbe compromettere la competitività di questa scelta. Ma buttiamo giù qualche numerello, perchéfinché non si fanno i conti rimane tutto per aria: sfruttiamo la distribuzione cumulativa di probabilità perε e imponiamo la condizione sul tempo speso in coda (sapendo di stare in coda!).

Fε (t) = 1− e−(µ−λ)t

1− Fε (0, 5) 6 0, 001

e−(µ−λ)0,5 6 0, 001

Il parametro µ possiamo ricavarlo facilmente

µ = ϑ−1 =CD

=nC0

D= 8n pacc/s

mentre λ sarà ovviamente la somma di λ1 e λ2. Dunque:

Fε (t) = 1− e−(µ−λ)t

1− Fε (0, 5) 6 0, 001

e−(8n−(λ1+λ2))0,5 6 0, 001

102− 8n 6ln 0, 001

0, 5102− 8n 6 −13,82

n >115, 82

8⇒ n > 15

24


Questa prima opzione costa quindi

6 · 15 = 90 milioni del vecchio conio

Tanto paga l’Unibo. Si noti che sia in questo punto che nel prossimo abbiamo avuto e avremo a che farecon due sistemiM/M/1.

2. Separiamo ora i due flussi, considerando due diversi parametri di qualità. Iniziamo col traffico dati:

µ1 = 8n1

δ̄ =1

µ1 − λ1=

18n1 − λ1

6 0, 5

n1 > d12, 75e = 13

Fin’ora, quindi, il costo è di:

6 (per le apparecchiature d’interfaccia)+ 13 · 6 = 78 milioni di lire

Passiamo ora al traffico amministrativo: il vincolo che dobbiamo adottare è quello già usato nel puntoprecedente.

µ2 = 8n2

e−(µ2−λ2)0,5 6 0, 001

...

n2 >⌈−1

8

(ln 0, 001

0, 5− 2)⌉

= 2

Dunque dobbiamo aggiungere altri 12 milioni al nostro conto, che s’ingrossa fino a 96 milioni.

In conclusione l’opzione 1 risulta migliore: l’aggregazione del traffico, come regola di buona progettazione, prevaleancora! Tra l’altro si può, sempre per quanto riguarda l’opzione 1, propendere per l’offerta speciale (2,408 Mbit/sa soli 90 milioni): tale portata corrisponde a 32 linee, mentre per soddisfare i requisiti ne basterebbero - comeabbiamo visto - solo 15. Questo, com’è evidente, comporta un notevolissimo beneficio in termini di qualità.

2.6 SistemaM/M/1/L

Questi sistemo è analogo al M/M/1, con la differenza della coda a lunghezza finita. La frequenzadi nascita è λ fino a che ci sono posti in coda e nulla altrimenti, mentre la frequenza di morte è sempre µperché c’è un solo servitore. Le probabilità di stato sono:

Pk = P0 Ak0 = P0

(λ

µ

)kcon P0 =

1− A0

1− AL+20

per A0 6= 1

1L + 2

per A0 = 1

La probabilità di congestione è di conseguenza:

πp = PL+1 =

1− A0

1− AL+20

AL+10 per A0 6= 1

1L + 2

per A0 = 1

Il numero medio di utenti in servizio risulta:

As = A0(1− πp

)= 1− P0

Il numero medio di utenti nel sistema è invece:

A =A0

1− A0

1− (L + 2) AL+10 + (L + 1) AL+2

0

1− AL+20

25


ESERCIZIO:

Centralino aziendale con operatore. Tempo medio di servizio = 15 secondi. Frequenza delle chia-mate in arrivo λ = 3, 2 chiamate/minuto.

1. Probabilità di rifiuto? (Hp: chiamate bloccate/cancellate)

2. Funzione di messa in attesa (coda lunga L). Trovare L perché la probabilità di perdita sia inferioreal 5%.

3. Il traffico aumenta: 4,8 chiamate/minuto. Meglio un sistema a chiamate bloccate/cancellate oun sistema con coda lunga L (con L preso dal punto precedente)?

4. Conviene aumentare L?

1. Il traffico offerto è2 A0 = λϑ̄ = 0, 4 · 3, 2 = 0, 8 E. Siccome il sistema è a chiamate bloccate/cancellate,bisogna usare la B di Erlang:

B (1, 0.8) =A0

1 + A0= 0, 44

Quella trovata è la probabilità di perdita. Un po’ altina, a dire la verità.

2. Per rispondere al secondo quesito basta applicare bovinamente le formule e invertire:

πp =1− A0

1− AL+20

AL+10

Indi per cui:

0, 05 =1− 0, 8

1− 0, 8L+10

AL+10

poniamo: AL+10 = 0, 8AL

0 = k

0, 05 =0, 2k

1− 0, 8k⇒ 0, 2k− 0, 05 + 0, 04k

1− 0, 8k= 0⇒ 0, 24k− 0, 05

1− 0, 8k= 0

dunque: k = 0, 8AL0 = 0, 2083

0, 8L = 0, 26⇒ L = log0,8 0, 26 =log10 0, 26log10 0, 8

= 6, 03

Per L ≥ 7 la specifica è soddisfatta e noi con lei.

3. In questo caso il traffico offerto è A0 = λϑ̄ = 0, 4 · 4, 8 = 1, 2. Le probabilità di blocco saranno:

• per il sistema a chiamate b/c: B(1,1.2) = 0,5455

• per il sistema a coda con L = 7:

πp =1− 1, 21− 1, 29 1, 28 = 0, 207

Il sistema con attesa va decisamente meglio.

4. Consideriamo la probabilità di blocco per i sistemiM/M/1/L:

πp =1− A0

1− AL+20

AL+10

Provando a mandare L all’infinito:

πp =1− A0

1− AL+20

AL+10

L→∞,A0>1−−−−−−→(1− A0) AL+1

0

−AL+20

=A0 − 1

A0

2Abbiamo convertito ϑ̄ in minuti.

26


Nel caso A0 = 1, 2 otteniamo:πp = 0, 16

Non cambia un granché rispetto al calcolo del punto precedente (πp ≈ 0, 21), quindi un aumento anchecospicuo di L non porta un sostanziale miglioramento della qualità di servizio. Per avere benefici consistentibisognerebbe aumentare m!

27


28

Capitolo 3

Altri esercizi

3.1 Esercizio 4.8

Multiplatore statistico, M terminali in ingresso ognuno contribuente con λi = 15 pacchetti/minuto,terminali indipendenti, ϑ̄ = 0, 2 s.

1. Numero massimo di terminali che si possono collegare al multiplatore affinché il valore mediodel tempo di permanenza nel sistema non superi 0,5 secondi?Il sistema è ovviamente di tipoM/M/1. Il vincolo viene rispettato se si ha:

δ̄ =1

µ− λ=

1ϑ̄−1 − λ

=1

5− λ< 0, 5 s

1 6 0, 5 (5− λ)1 6 2, 5− 0, 5λ

−1, 5 6 −0, 5λ

3 > λ = λi M

M 63λi

=3

15/60= 12

Come si nota, si poteva cadere nel tranello non notando che λi viene dato in pacchetti/minuto,mentre noi facciamo riferimento ai secondi.

2. Probabilità di perdita nel caso di capacità del buffer pari a 3 pacchetti?Anzitutto calcoliamo il traffico offerto1. . .

A0 = ϑ̄λ = 0, 2 · 0, 25 · 12 = 0, 6 E

. . . perché ci servirà nella seguente formula:

πp =1− A0

1− AL+20

AL+10 = 5, 6%

3.2 Esercizio 5.12

Linea di trasmissione con capacità C = 64 kbit/s, frequenza d’arrivo λ = 8 pacc/s, dimensione mediadei pacchetti D = 6400 bit. Determinare:

• Il numero medio Ac di pacchetti in coda e la quantità b̄ di memoria mediamente occupata.Per trovare Ac basta applicare la formula:

Ac =ρ2

1− ρ

1Scegliamo ovviamente M = 12.

29

30 CAPITOLO 3. ALTRI ESERCIZI

Dove ρ = A0 = λϑ̄ = 8 · DC

= 0, 8 E. Sostituendo i numerelli:

Ac =0, 64

1− 0, 8= 3, 2

Dunque b̄ è 6400 · 3, 2 = 20480.

• La densità di probabilità fb|k(x) della quantità di memoria occupata b, condizionata alla presenzadi k pacchetti nel sistema.Ecco, questa è una domanda cazzuta. Anzitutto dobbiamo discriminare due casi:

– k ≤ 1: questo significa che il numero di pacchetti all’interno del sistema è pari a zero (e quindinon c’è nessuno, ma proprio nessuno!) oppure che è presente un pacchetto, che tuttavia nonsarà in coda perché è in servizio. In questo caso la distribuzione di probabilità per la funzionefb|k(x) sarà una delta di Dirac centrata in zero. Abbiamo infatti probabilità 1 che la memoriaoccupata sia nulla e probabilità nulla per tutte le altre evenienze di b ∈]0, +∞];

– k ≥ 1: in tal caso la quantità di memoria impegnata è una variabile aleatoria pari alla sommadi k − 1 variabili aleatorie identiche ed esponenziali di valor medio D. La relativa densità diprobabilità è, in questo caso:

fb|k (x) =(

1D

)k−1 xk−2

(k− 2)!e−

xD

• La densità di probabilità fb(b) della variabile b.Questo punto può essere risolto solo dopo aver risposto al quesito precedente. Sfrutteremo infatti laproprietà tale per cui:

pA (x) =∞

∑k=−∞

pA|B (x) pB ⇒ fb (x) =∞

∑k=0

fb|k (x) Pk

Si ha quindi:

fb (x) = (P0 + P1) · δ (x) +∞

∑k=2

(1− ρ) ρk ·(

1D

)k−1 xk−2

(k− 2)!e−

xD

• La probabilità di avere la memoria impegnata per più di B = 32678 bit.Si tratta di integrare adeguatamente la funzione cumulativa:

Psoluzione =∞∫

32678

Fb (x) dx = 1−32678∫0

Fb (x) dx

Teoricamente dovremmo trovare l’espressione analitica di Fb(x) e integrarla opportunamente. Prati-camente, invece, non ne abbiamo voglia. Tanto volete che all’esame ci sia una roba così?

3.3 Esercizio 5.13

Si vuole progettare la rete telefonica di un’azienda, composta da 3 sedi (A,B,C). Si intende installareun centralino per ogni sede, con eventuali collegamenti dedicati fra i centralini. I valori di traffico sonoriportati nella tabella 3.1. Garanzia di qualità: probabilità di blocco inferiore all’1%. Tariffe:

• Ca = 30000 lire/mese per le linee urbane verso l’esterno;

• Cg = 150000 lire/mese per il canone di noleggio delle linee di giunzione fra centralini;

• Ct = 250000 lire/Erlang/mese per il traffico di utente.

Confrontare le seguenti scelte:

1. tutto il traffico interaziendale solo su linee di giunzione dedicate;

30

CAPITOLO 3. ALTRI ESERCIZI 31

A B C Esterno (E)A - 5 3 30B 10 - 2 12C 10 2 - 12

Esterno (E) 30 12 12 -

Tabella 3.1

2. come sopra, ma B e C non possono essere collegati direttamente fra loro e devono appoggiarsi adA;

3. no linee dedicate, tutto sulla linea pubblica.

1. In questo caso dobbiamo calcolare diverse B di Erlang basandoci sulla tabella. Il sistema è a magliacompleta quindi ogni centralino è collegato con tutti gli altri e con l’esterno. I calcoli sono riportatiin tabella 3.2.

Traffico DA –> A B di Erlang Risultato (m)A –> B + B –> A B(m, 10 + 5) 24B –> C + C –> B B(m, 2 + 2) 10A –> C + C –> A B(m, 10 + 3) 22A –> E + E –> A B(m, 30 + 30) 75B –> E + E –> B B(m, 12 + 12) 35C –> E + E –> C B(m, 12 + 12) 35

Tabella 3.2

Il costo totale risulterà quindi essere:

C1 = Ca (mA + mB + mC)︸︷︷︸affitto verso l’esterno

+ Cg (mAB + mAC + mBC)︸︷︷︸affitto linee inter - aziendali

+ Ct (30 + 12 + 12)︸︷︷︸traffico verso l’esterno

=

= 145 · 30000 + 56 · 150000 + 54 · 250000 = 26250000 lire/mese

2. In questo caso vengono aggregati alcuni flussi (che prendono a passare per A). I calcoli sono riportatiin tabella 3.3. Il costo totale risulterà quindi essere:

Traffico DA –> A B di Erlang Risultato (m)A –> B + B –> A B(m, 10 + 5 + 2 + 2) 29A –> C + C –> A B(m, 10 + 3 + 2 + 2) 27A –> E + E –> A B(m, 30 + 30) 75B –> E + E –> B B(m, 12 + 12) 35C –> E + E –> C B(m, 12 + 12) 35

Tabella 3.3


+ Cg (mAB + mAC)︸︷︷︸affitto linee inter - aziendali

+ Ct (30 + 12 + 12)︸︷︷︸traffico verso l’esterno

=

= 145 · 30000 + 56 · 150000 + 54 · 250000 = 26250000 lire/mese

Apparentemente questo risultato può sorprendere. In realtà non c’è nulla di sbagliato, in quanto ilfatto che ciascuna chiamata da B a C impegni due linee dedicate invece che una (fattore di aumentodel congestionamento) viene compensato dall’affasciamento del traffico (fattore di contenimento delnumero di servitori). Con i valori in gioco, e in questo caso, si ottiene il medesimo risultato numerico.

3. In questa terza e ultima scelta si delega alla rete esterna lo smistamento di tutti i pacchetti. I calcolisono riportati in tabella 3.4.

31


Traffico DA –> A B di Erlang Risultato (m)A –> E + E –> A B(m, 30 + 30 + 10 + 5 + 10 + 3) 105B –> E + E –> B B(m, 12 + 12 + 10 + 2 + 5 + 2) 56C –> E + E –> C B(m, 12 + 12 + 10 + 2 + 3 + 2) 54

Tabella 3.4

Il costo totale risulterà quindi essere:


+ Ct (30 + 12 + 12 + 10 + 10 + 5 + 2 + 3 + 2)︸︷︷︸traffico verso l’esterno

=

= 215 · 30000 + 54 · 250000 = 27450000 lire/mese

3.4 Esercizio 5.16

Sistema a singolo operatore, λ = 30 chiamate/ora, ϑ̄ = 2 min. I clienti che trovano l’operatoreoccupati ricevono un avviso e vengono messi in attesa. La durata dell’attesa è una variabile aleatoriacon distribuzione esponenziale negativa a valor medio ξ̄ = 2 min, dopodiché chi non riesce ad essereservito mette giù la cornetta e se ne va dal sistema senza essere servito. Calcolare:

1. Frequenze di nascita λk e di morte µk.Non c’è nessuna ragione perché non sia:

λk = λ ∀k

Per la frequenza di morte. . . bisogna stare attenti! Si potrebbe pensare di rispondere

µk = µ ∀k

tuttavia questo sarebbe esatto solo se quelli che si trovano in coda attendessero all’infinito. In realtà,com’è giusto che sia, coloro che vengono messi in attesa dopo un po’ si rompono le scatole e se nevanno dal sistema con le pive nel sacco, senza essere serviti dall’operatore. Dunque quelli che esconodal sistema sono in maggior numero rispetto a quelli che avremmo se fosse vero che µk = µ, ∀k.Come, quindi, andare avanti? L’approccio corretto è anche quello più intuitivo: bisogna immaginareche coloro che si trovano in coda siano in realtà serviti da una moltitudine2 di servitori fittizi chesi occupano. . . di condurli alla ’morte’. Il tempo medio di servizio (dove il servizio è l’attesa primadella morte o dell’accesso all’operatore) è pari a ξ̄ = 2 min, che guarda caso è lo stesso tempo diservizio di chi viene servito veramente, dunque si ha:

ϑ̄ = ξ̄ ⇒ µcoda = µin servizio = µ

µk = 1︸︷︷︸chi è servito davvero

·µ + (k− 1)︸︷︷︸coloro che sono in coda

µ

Quindi alla fine si ha:µk = kµ ∀k

2. Probabilità di stato al’equilibrio Pk del sistema.Visto che alla fine abbiamo un servitore vero, ma anche un servitore fittizio per ogni utente in coda, econsiderato il fatto che tutti questi servitori sono caratterizzati dalla stessa distribuzione per il tempodi servizio e dallo stesso valor medio (ϑ̄ = ξ̄) per quest’ultima, possiamo - solo teoricamente e soloin virtù di questo caso particolare - vedere il tutto come un sistemaM/M/∞. Quindi le probabilitàdi stato sono le solite:

Pk =Ak

0k!

e−A0

2Che possiamo considerare infinita, anche se a voler essere rigorosi bisognerebbe specificare che questi servitori stanno in rapporto1:1 con coloro che si trovano in coda.

32


3. Numero medio A di utenti nel sistema e numero medio Ac di utenti in coda.

Tenendo presente quanto appena detto, cioè che possiamo vedere il sistema a un servitore concoda come un sistema a infiniti servitori dove solo chi ha il servitore giusto (quello vero) vieneservito davvero mentre gli altri se ne vanno incazzati neri, il numero medio di utenti nel sistema èsemplicemente:

A = A0 =3060· 2 = 0, 5 · 2 = 1 E

Quanti sono gli utenti mediamente in coda? Dobbiamo sfruttare la definizione:

ζ̄ =∞

∑ζ=−∞

ζPζ

Si deve però prestare attenzione al fatto che, se consideriamo la probabilità di stato k-sima, abbiamo:

• k utenti complessivamente nel sistema;

• k− 1 utenti in coda. E dobbiamo effettuare la media rispetto a questo parametro!

Dunque si ha:

Ac =∞

∑k=1

(k− 1) Pk =∞

∑k=1

kPk −∞

∑k=1

Pk = A0 − (1− P0) = 1− 1 + e−A0 = e−1

4. La probabilità di blocco πr, il traffico servito As, la probabilità di perdita πp.In primis dobbiamo distinguere fra la probabilità di blocco, cioè la probabilità di dover attendereprima di ricevere il servizio - e la probabilità di perdita, ovvero quella di lasciare il sistema. Laprima, banalmente, è:

πr = 1− Pr{non trovare nessuno e - quindi - di essere serviti subito} = 1− P0

La seconda è pari al rapporto fra gli utenti perduti, cioè quelli che abbandonano il sistema senzaaver ricevuto il servizio, e quelli totali. Dunque:

πp =A0 − As

A0=

A0 − (A0 − Ac)A0

= 1− 0, 632 = 0, 368

Si noti che abbiamo così esplicitato anche As! Piccola precisazione: si potrebbe protestare asserendoche

πb + πp = 1

e che dunque o si viene bloccati o si esce dal sistema, dunque non si viene mai serviti. In realtà nonè così: essere bloccati ed andarsene dal sistema non sono eventi fra di loro indipendenti e dunquela probabilità dell’unione non è l’unione delle probabilità (bensì bisogna sottrarre la probabilitàdell’intersezione, che non è l’insieme vuoto visto che chi viene bloccato può doversene andare senzaessere servito).

3.5 Esercizio 5.15

Abbiamo un router che gestisce flussi di traffico di pacchetti diretti alle reti A, B e C. Il router èperò connesso direttamente solo ad A e B mentre, per arrivare a C, deve necessariamente passare -giustappunto - per A o B. Queste ultime hanno capacità C = 2, 048 Mbit/s. Grandezza media dei pac-chetti D = 8192 bit; ritmi degli arrivi: λA = 200 pacchetti/s, λB = 150 pacchetti/s, λC = 25 pacchetti/s.I pacchetti verso C, instradati attraverso A e B, costituiscono un traffico poissoniano che supponiamotrascurabile ai fini del calcolo dello stato delle code sulle due linee.

1. Hp: il router instrada verso C scegliendo il sistema (fra A e B) con meno pacchetti in coda, oppuresceglie B se le due code sono eguali. Determinare la probabilità Qk che il suddetto pacchettovenga accodato in un sistema contenente già k pacchetti.

Iniziamo calcolandoci alcuni parametri che ci saranno sicuramente utili:

33


• il tempo medio di servizio (trasmissione): ϑ̄ = DC = 8192

2048000 = 4 ms;

• la frequenza di servizio: µ = ϑ̄−1 = 250 pacchetti/s;

• il traffico offerto verso le reti A e B è:

AA0 = ρA = ϑλA = 0, 8 E

AB0 = ρB = ϑλB = 0, 6 E

A questo punto possiamo considerare i due sottosistemi M/M/1 costituiti rispettivamente dallelinee A e B, che hanno probabilità di stato:

PAk = ρk

A (1− ρA)

PBk = ρk

B (1− ρB)

La probabilità Qk si riferisce ad un evento che avviene:

• quando A ha k pacchetti in coda e B ne ha almeno k + 1;

• quando B ha k pacchetti in coda e A ne ha almeno k.

Dunque:

Qk = ρkA (1− ρA)

∞

∑i=k+1

ρiB (1− ρB) + ρk

B (1− ρB)∞

∑i=k

ρiA (1− ρA)

Scritta così è bruttina, ma c’è un barbatrucco micidiale (che non avrei mai individuato senza lesoluzioni): spezziamo la seconda sommatoria

Qk = ρkA (1− ρA)

∞

∑i=k+1

ρiB (1− ρB) + ρk

B (1− ρB)∞

∑i=k+1

ρiA (1− ρA) + ρk

A (1− ρA) ρkB (1− ρB)

sfruttiamo la serie geometrica3

∞

∑i=k+1

ρi (1− ρ) = ρk+1∞

∑i=0

ρi (1− ρ) = ρk+1 (1− ρ)1

1− ρ= ρk+1

per ottenere infine:

Qk = ρkA (1− ρA) ρk+1

B + ρkB (1− ρB) ρk+1

A + ρkA (1− ρA) ρk

B (1− ρB) =

= ρkA

[(1− ρA) ρk+1

B + (1− ρA) ρkB (1− ρB) + ρAρk

B (1− ρB)]

=

= ρkAρk

B [(1− ρA) ρB + (1− ρA) (1− ρB) + ρA (1− ρB)] =

= ρkAρk

B [ρB − ρAρB + 1− ρA − ρB + ρAρB + ρA − ρBρA] =

= (ρAρB)k (1− ρAρB)

Come si vede, l’espressione di Qk ha la proprietà di essere formalmente analoga all’espressione dellaprobabilità di stato di un sistemaM/M/1 in cui ρ = ρAρB.

2. Calcolare la probabilità di blocco πc ed il tempo medio complessivo speso nel router δ̄C per ipacchetti diretti a C.

A questo punto la probabilità di blocco per un pacchetto diretto a C è banale: trattasi infatti dellaprobabilità che vi siano entrambe le linee occupate con almeno un pacchetto in entrambe, dunque

πc = 1−Q0 = ρAρB = 0, 48

Per quello che riguarda il tempo medio speso in coda, dobbiamo utilizzare l’ipotesi tale per cuiil traffico diretto verso C è trascurabile se confrontato con quello di A e B4. Questo significa che i

3TA-DAAAH!4Inoltre esso viene diluito fra entrambe le vie, dunque il suo apporto è effettivamente piuttosto ridotto.

34


pacchetti verso C sono accodati praticamente solo con pacchetti diretti ad A o a B. Dunque dobbiamoapplicare la formula

ζ̄ =∞

∑ζ=−∞

ζPζ

nella seguente maniera, ricordando cioè che il parametro (k + 1) inserito tiene conto dei k pacchettidi A o B e di quello (+1) di C:

δ̄C = ϑ̄k̄coda = ϑ̄∞

∑k=0

Qk (k + 1) = ϑ̄∞

∑k=0

(ρAρB)k (1− ρAρB) (k + 1) = ϑ̄ (1− ρAρB)∞

∑k=0

(ρAρB)k (k + 1) =

k+1=h−−−−→ ϑ̄ (1− ρAρB)∞

∑h=0

h (ρAρB)h−1 = ϑ̄ (1− ρAρB)1

(1− ρAρB)2 =ϑ̄

1− ρAρB

3. Determinare la densità di probabilità fδ(t) del tempo speso nel router dai pacchetti diretti a C ecalcolare la probabilità Pd che un pacchetto spenda nel router più di 20 ms.Per quest’ultimo quesito si ha:

fδ =∞

∑k=0

Qk fδ|k (t) =∞

∑k=0

(ρAρB)k (1− ρAρB)µ(µt)k

k!e−µt =

= µ (1− ρAρB) e−(1−ρAρB)µt primitiva−−−−−→ e−(1−ρAρB)µt

Dunque:

Pδ = Pr {δ > t = 20 ms} =[e−(1−ρAρB)µt

]∞

20 ms= 0, 0743

3.6 Esercizio 5.17

Due centralini connessi con due linee a 64.000 bit/s ognuna con quattro canali-voce da 16.000 bit/s.Necessari 16.000 bit/s per gestire le comunicazioni (canale di segnalazione in grado di far capo a 7canali vocali). In assenza di chiamate no collegamento fra centralini, in presenza di chiamata vocale icentralini impegnano una prima linea a 64 Kbit/s sulla quale aprono un canale di segnalazione e uncanale vocale (le chiamate successive sfruttano sempre quel canale di segnalazione). Più di tre chia-mate –> impegnata una nuova linea vocale da 64 Kbit/s. Centralini possono reinstradare le chiamate,trasferendole dalla seconda linea alla prima quando su questa si libera un canale. Canone d’affittodelle giunzioni: CM = 320.000 lire/centralina/mese. Costo delle chiamate: c = 1 lira/s. Traffico pari alvalore massimo per 150 ore/mese, nulla altrove. Calcolare:

1. Valore di traffico A0 fra centralini compatibile con πp < 0, 01 E.Nonostante si abbia spazio per 8 canali vocali, ne potremo allocare al massimo 7 per via del fattoche uno lo usiamo per la segnalazione. Possiamo perciò considerare il sistema come unM/M/7 eimporre che sia soddisfatta la seguente relazione:

B(7, A0) < 0, 01

Da cui si ha A0 ≤ 2, 5 E.

2. Valutare il costo di: 1. giunzioni tutte affittate, 2. affitto in una centralina e traffico a consumonell’altra, 3. tutto traffico a consumo.

Nel caso le giunzioni siano tutte affittate, il costo è banalmente calcolabile:

C2affitto = 320.000 · 2 = 640.000

Gli altri due casi sono più complessi, perché bisogna calcolare il tempo medio d’utilizzazione peril calcolo del traffico a consumo. Per farlo dobbiamo sfruttare l’ergodicità del sistema: siccome le

35


statistiche sul tempo d’uso devono essere uguali alle statistiche sulla presenza di utenti, calcoliamola probabilità che vi siano k utenti all’interno del sistema (cioè le probabilità di stato):

Pk = P0Ak

0k!

La P7 è semplicemente la B(7,2.5) = 0,01 (dalle tabelle). Per le altre probabilità si è usato Matlab e ilseguente script

clear all; close all; clc;k = 7; temp = 0; P=zeros(1,k); T = 2.5;for i=0:(k-1)

temp = temp + (T^i)/factorial(i);endtemp = temp + (k/(k-T))*((T^k)/factorial(k));P(1,1) = (temp)^(-1);for i=1:(k-1)

P(1,i+1) = P(1,1)*((T^i)/factorial(i));endP

che, una volta eseguito, ha restituito:

P[0..6] = 0.0820 0.2050 0.2562 0.2135 0.1334 0.0667 0.0278

In base al numero di utenti avremo:

• nessuna centralina impegnata se non è presente alcun utente. Probabilità:

P0c = P0 = 0, 082

• una centralina impegnata se è presente almeno un utente. Probabilità:

P1c = 1− P0 = 0, 918

• due centraline impegnate se vi sono almeno quattro utenti. Probabilità:

P2c = P4 + P5 + P6 + P7 = 0, 1334 + 0, 0667 + 0, 0278 + 0, 01 = 0, 2379

Dunque il numero medio di secondi in cui saranno occupate le due centraline è pari a:

T1 = 150 · 60 · 60 · P1c = 495.720

T2 = 150 · 60 · 60 · P2c = 128.466

I costi complessivi saranno quindi quelli riportati in tabella 3.5. Come mai la seconda delle tretariffe è la più conveniente? Perché la grande utilizzazione della prima centralina rende convenienteil pagamento del canone d’affitto, mentre la più scarna utilizzazione della seconda fa sì che siapreferibile optare per il traffico a consumo.

TOPOLOGIA COSTO (lire)Pagamento di 2 canoni 640.000

Pagamento di 1 canone + pagamento a consumo 128.466+320.000 = 448.466Pagamento unicamente a consumo 495.720

Tabella 3.5

36


3.7 Esercizio 5.18

Richieste di calcolo: λ = 4 richieste/s. La durata delle elaborazioni ha distribuzione esponenzialenegativa con valore medio ϑ̄ = 0, 2 s. Trasmissione dei dati ad intervalli regolari T0 = 1 s, cosicchéun evento rilevato dal sensore deve attendere, prima di essere trasmesso, un tempo δ1 distribuitocasualmente fra 0 e T0 e poi un tempo δ2, comprensivo di attesa in coda e elaborazione. Sia ξ = δ1 + δ2.

1. Densità di probabilità f1(t) e f2(t) (di δ1 e δ2)?

Si dice che δ1 è distribuito casualmente fra 0 e T0: non c’è ragione perché sia più probabile che ilpacchetto debba attendere per determinati periodi di tempo piuttosto che per altri. Dunque consi-dereremo la distribuzione di probabilità f1(t) uniforme in [0, T0]. Per quanto riguarda il tempo δ2,dobbiamo scrivere quello tipico del sistemaM/M/1:

f2(t) = (µ− λ)e−(µ−λ)t

2. Valor medio di ξ?Il valor medio di δ1 sarà 0,5 mentre quello di δ2 sarà 1

µ−λ . Il valor medio di ξ sarà la somma deivalori medi di δ1 e δ2:

ξ̄ =T0

2+

1µ− λ

= 1, 5 secondi

3. Densità di probabilità di ξ?Siccome abbiamo sommato due variabili aleatorie indipendenti, la distribuzione di probabilità dellasomma sarà la convoluzione delle densità di probabilità.

fζ (t) = f1 (t) ∗ f2 (t) =

1T0

t∫0

(µ− λ) e−(µ−λ)(t−x) dx, da 0 a T0

1T0

T0∫0

(µ− λ) e−(µ−λ)(t−x) dx, oltre T0

=

µ− λ

T0︸︷︷︸=1

e−(µ−λ)t

µ− λ︸︷︷︸=1

e(µ−λ)x

t

0

µ− λ

T0

[e−(µ−λ)t

µ− λe(µ−λ)x

]T0

0

=

e−t (et − 1)

, per t 6 T0

e−t(

eT0 − 1)

, per t > T0

4. Densità di probabilità cumulativa per ξ?Integriamo la PDF e non se ne parli più:

∫1− e−t dt, per t 6 T0∫e−t (e− 1) dt, per t > T0

=

t + e−t − e0 = t + e−t − 1

e−1 + (e− 1)(

e−1 − e−t)

= 1− (e− 1) e−t

3.8 Esercizio 5.19 (il gemello del 5.17)

Centralini connessi con linee a 64.000 bit/s ognuna con quattro canali-voce da 16.000 bit/s. Necessari16.000 bit/s per gestire le comunicazioni (canale di segnalazione in grado di far capo a 7 canali vocali).In assenza di chiamate no collegamento fra centralini, in presenza di chiamata vocale i centraliniimpegnano una prima linea a 64 Kbit/s sulla quale aprono un canale di segnalazione e un canalevocale (le chiamate successive sfruttano sempre quel canale di segnalazione). Più di tre chiamate inuna linea –> impegnata una nuova linea vocale da 64 Kbit/s. Più chiamate di quelle smaltibili dai

37


centralini –> si finisce nella rete pubblica e si occupano 64 Kbit/s per ogni chiamata (traffico noncompresso). Traffico fra gli stabilimenti: A0 = 3 Erlang. Canone d’affitto delle giunzioni: CM =1.400.000 lire/centralina/anno. Costo delle chiamate: c = 1 lira/s. Traffico pari al valore massimo per150 ore/mese, nulla altrove.

1. Costo dell’esercizio mensile C0 in assenza di apparati di compressione?Considerando l’uso delle linee per 150 ore/mese:

CE = 150 · 60 · 60 = 540.000 lire/mese

Dunque il costo totale in assenza di apparati sarà:

C0 = CE · A0 = 1.620.000 lire/mese

Ma allora, si potrà dire, perché non abbiamo moltiplicato per il traffico in Erlang anche le cifredell’esercizio 5.17? Il fatto è che non ve n’era bisogno, in quanto l’informazione sul traffico era giàpresente all’interno delle probabilità di stato Pk (per le quali anche allora abbiamo moltiplicato ilnumero di secondi in 150 ore).

2. Caso di una sola linea equipaggiata con sistema di compressione. Calcolare il traffico smaltitodalla rete e quello che finisce nella rete pubblica.

Questo caso è equivalente ad un sistemaM/M/∞: nessuno viene infatti rifiutato e, tuttavia, vi saràchi occuperà 16 Kbit/s e chi 64 Kbit/s. In questo caso la probabilità di stato è:

Pk = P0Ak

0k!

Quanto traffico viene smaltito? Bisogna ricordare che nel casoM/M/m (il sottosistema della lineacompressa, caratterizzato da m = 3) il traffico medio smaltito è pari al numero medio di utentiserviti. Si ha quindi:

AS = P1 + 2 · P2 + 3 ·∞

∑i=3

Pk = P1 + 2 · P2 + 3 · (1− P0 − P1 − P2) = 2, 33 E

Il traffico che finisce sulla rete pubblica è quindi, banalmente:

At1 = 3− 2, 33 = 0, 67 E

3. Stessa cosa del punto precedente, ma prima con 2 e poi con 3 linee a compressione.Non cambia nulla di nulla: grazie al fatto che si ha il call packaging possiamo considerare il sistemacome un M/M/m (con m = 6; 9 rispettivamente) e impostare una relazione simile a quella delpunto precedente.

AS2 =5

∑i=0

iPi + 6 ·∞

∑i=6

Pk =5

∑i=0

iPi + 6 ·(

1−5

∑i=0

Pi

)= 2, 95 E⇒ AT2 = 0, 05 E

AS3 =8

∑i=0

iPi + 9 ·∞

∑i=9

Pk =8

∑i=0

iPi + 9 ·(

1−8

∑i=0

Pi

)≈ 3 E⇒ AT2 ≈ 0

4. Soluzione più economica?

Calcoliamo la probabilità di utilizzare:

• una linea di compressione: 1− P0 = 0, 9502;

• due linee di compressione: 1− P0 − P1 − P2 − P3 = 0, 3528;

• tre linee di compressione: 1− P0 − P1 . . .− P6 = 0, 0336.

38


I costi mensili saranno dunque:

C = #centraline · affitto centraline +

{∑

iprob. usare centralina i

}·CE + {traffico verso l’esterno} ·CE

Nella formula sopra si è tenuto conto del fatto che una linea a compressione genera una frazione diErlang pari alla percentuale di tempo per il quale viene utilizzata, indipendentemente dalla quantitàdi traffico che smaltisce (questa è una diretta conseguenza dell’ergodicità del sistema: le statistiched’utilizzazione sono anche uguali alle statistiche temporali), mentre il traffico che trabocca sulla retepubblica viene tariffato in Erlang. I tre costi saranno dunque:

C1 =Cc

12+ P1 linea · CE + Aesterno · CE

C2 = 2 · Cc

12+ (P1 linea + P2 linee) · CE + Aesterno · CE

C3 = 3 · Cc

12+ (P1 linea + P2 linea + P3 linee) · CE + Aesterno · CE

Sostituendo i valori ci si accorge che la soluzione conveniente è quella con due linee di compressione.

39


40

Capitolo 4

Esercizi del prof. Callegati

4.1 Esercizio 11 Due router che interconnettono due sedi e in cui viaggiano, separati, i flussi di traffico dati e voce;

ciascun router dispone di due interfacce (una per i dati e una per la voce) aventi ciascuna due canali Ba 64 Kbps (equivalenti ad un collegamento full-duplex a 128 Kbps). Ciascuna sede è frequentata da 50utenti, 0.1 Erlang per utente. Ciascun utente attivo: λv = 30 pacchetti/s, lunghezza dei pacchetti espo-nenziale con valor medio Dv = 64 byte. Traffico dati stimabile in un flusso di pacchetti rappresentabilecon un processo di Poisson avente frequenza media di arrivo dei pacchetti λd = 25 pacchetti/s e lun-ghezza dei pacchetti esponenziale con valore medio Dd = 512 byte. Accodamento sulla coda d’uscitadei router. Si determinino:

1. Traffico dati: ritardo medio totale e tempo medio d’attesa in coda per i pacchetti che fanno coda.Per quanto riguarda il traffico dati, possiamo considerare il sistema come un M/M/1 e quindiapplicare le ben note relazioni:

δ̄ =1

µ− λ=

1CD − λ

=1

128K512·8 − 25

=1

6, 25= 0, 16 s

Il tempo medio di attesa per i pacchetti che fanno la coda (sapendo che andranno in coda) è parial tempo medio speso nel sistema. Questa peculiarità, poco intuitiva ma assolutamente veritiera, ètipica di questo genere di sistemi.

2. Traffico dati: utilizzazione della linea di interconnessione dedicata.

Si ha ρ = A0 = λϑ̄ = 25 · DC = 25 · 512·8

128.000 = 0, 8.

3. Numero massimo di telefonate attive fra le due sedi tali che il tempo medio di attesa per i pac-chetti che vanno in coda sia inferiore a 50 ms (una telefonata implica un traffico bidirezionale).

Anche in questo caso prendiamo in considerazione le formule del sistemaM/M/1: sappiamo che

ε =1

µ− λ< 0, 05⇒ 1

CD − 30 · N

< 0, 05⇒ 1250− 30 · N < 0, 05

10, 05

< (250− 30 · N)⇒ 20− 250 < −30N ⇒ −230 < −30N

N <23030

= 7, 67⇒ N 6 7

1Questo esercizio, soprattutto per quanto riguarda la sua seconda parte, ha suscitato molti dubbi. Mi hanno detto che il prof.Callegati stesso ha accennato al fatto che vi fosse qualche errore nelle sue soluzioni, dunque prendete il tutto con le molle perché misono basato esattamente su di esse.

41

42 CAPITOLO 4. ESERCIZI DEL PROF. CALLEGATI

4. La probabilità di perdita per chiamata (traffico voce) nell’ipotesi che i router siano in grado dibloccare le chiamate quando un loro aumento di numero comporterebbe una violazione del vin-colo sui ritardi.Ora sappiamo che, affinché siano soddisfatti i requisiti di qualità, devono esserci al massimo 7 utentiattivi chiamanti all’interno del sistema. I 50 utenti che sono all’interno del sistema, tuttavia, nonsono sempre e necessariamente attivi: sappiamo anzi che il traffico medio per utente è pari a 0,1Erlang, mentre gli

A0 = ϑ̄λv =DC

λv = 30 · 64 · 8128000

= 0, 12 Erlang

di traffico offerto si riferiscono a un chiamante pienamente attivo in un certo istante (sono, quindi, gliErlang/chiamata, mentre gli 0.1 sono Erlang/utente). Quindi, facendo la soprastante ipotesi di poterbloccare l’ottavo chiamante ’pienamente attivo’, abbiamo trasformato il sistema in un M/M/7/0:così facendo immaginiamo di avere un servitore pienamente dedicato ad ogni chiamante fino alnumero massimo stabilito nel punto precedente. Il fatto che gli utenti non siano mai pienamenteattivi, e l’utilizzazione di un traffico di tipo VoIP (a commutazione di pacchetto e non a commuta-zione di circuito), ci permette di vedere il problema in quest’ottica e allo stesso tempo di sfruttare laformulazione offertaci dalla B di Erlang. Dunque la probabilità di perdita è:

πp = B (m, A0) = B (7, 50 · 0.1) = 0.12

5. Utilizzazione della linea di interconnessione dedicata al traffico voce.Anzitutto troviamo il traffico smaltito:

As = A0(1− πp

)= 5 · (0, 88) = 4, 4 E

E poi? Dividiamo per 7? Eh no! Il traffico smaltito appena calcolato, infatti, viene riportato intermini di numero di chiamate (si noti che, nel caso di commutazione di circuito, non aveva sensoun numero di chiamanti non intero) mentre noi vogliamo quello in termini di numero di pacchetti.Quindi:

{Traffico smaltito (→ numero di chiamate)} · {Erlang /chiamata} = 4, 4 · 0, 12 = 0, 53 E

Dunque la banda viene utilizzata per il 53%.

4.2 Un brevissimo esempio di sistemaM/G/1

Ebbene, per i sistemi di questo tipo (non poissoniani e, dunque, con memoria!) si ha:

• tempo medio residuo ξ̄ =E[ϑ2]

2ϑ;

• tempo medio speso nel sistema η̄ = ξ̄ρ

1− ρ;

• tempo medio speso in coda sapendo di fare coda η̄ = ξ̄1

1− ρ;

• probabilità di andare in coda: ρ = 1− P0;

• traffico in coda: AC = λη̄.

ESERCIZIO:

Collegamento con protocollo di linea stop-wait. Il TX invia una trama e aspetta l’ACK prima dispedire quella dopo. Tempo di ricezione ACK: T = 2, 5 ms. Qualora si verifichi un errore di trasmissionela trama viene ritrasmessa dopo un tempo T0 = 3 ms. Sia T0 che T vengono misurati a partire dall’istanted’inizio trasmissione della trama. Probabilità d’errore per trama PF = 0, 1.

42

CAPITOLO 4. ESERCIZI DEL PROF. CALLEGATI 43

• Scrivere l’espressione del tempo ϑ necessario per la corretta trasmissione di una trama in funzionedel numero di errori di trasmissione e la relativa probabilità.Il tempo ϑ necessario alla corretta trasmissione di una trama è:

ϑ(Nerrori) = 2, 5 ms + Nerrori · 3 ms

La probabilità di avere k errori di trasmissione è invece:

P {Trasmissione corretta} · (P {Trasmissione non corretta})k

Pk = (1− PF)PkF

• Calcolare il tempo medio di trasmissione per trama ϑ̄.Mettendo insieme i risultati del punto precedente e sfruttando le serie notevoli:

ϑ̄ = ∑k

ϑk · Pk = ∑k

(T + kT0) · (1− PF) PkF = (1− PF)

[∑k

TPkF + kT0Pk

F

]= (1− PF)

[∑k

TPkF + kT0Pk

F

]=

= (1− PF)

[T ∑

kPk

F + T0 ∑k

kPkF

]= (1− PF)

[T

11− PF

+ T0PF

(1− PF)2

]= T +

T0PF

(1− PF)= 2, 834 ms

Processo di arrivo delle trame: poissoniano con frequenza media di arrivo λ trame/s. Si approssimi ϑcome v.a. esponenziale (valor medio ϑ̄). Coda di dimensioni infinite. Calcolare:

• Massima frequenza di arrivo λM compatibile con la stabilità del sistema.Fatta l’ipotesi poissoniana, il nostro sistema è unM/M/1, dunque si deve avere, per la stabilità:

A0 = ρ < 1

Sfruttiamo il teorema di Little:A0 = λMϑ̄ = 1

λM =1ϑ̄

= 352, 8 trame/s

• Il tempo medio d’attesa in coda per le trame e il tempo medio totale necessario per trasmettereuna trama qualora λ = 0, 8λM, arrotondata alla decina.Abbiamo:

η̄ =ρ

1− ρϑ̄ =

A0

1− A0ϑ̄ =

0, 8λMϑ̄

1− 0, 8λMϑ̄ϑ̄ =

(0, 8 · 353)arr. decine · 0, 002831− (0, 8 · 353)arr. decine · 0, 00283

· 0, 00283 =

=0, 792

1− 0, 792· 0, 00283 =

0, 002240, 208

= 10, 8 ms

Tempo medio totale per trasmettere una trama:

δ̄ = η̄ + ϑ̄ = 10, 8 + 2, 83 = 13, 63 ms

• La probabilità che una trama impieghi più di 20 millisecondi per essere trasmessa correttamente.Per quest’ultimo punto sfruttiamo la solita cumulativa:

e−(µ−λ)0,02 = e−(353,3−280)0,02 = 0, 2308

43

Progetto di Reti di Telecomunicazioni - Parte I (per "tutti")

Documents

Transcript of Progetto di Reti di Telecomunicazioni - Parte I (per "tutti")