Appunti di Telecommunication Networks

Telecommunication Nwtworks

2022-2023

Indice

1 INTRODUZIONE 2

2 PROCESSI STOCASTICI 8

2.1 Processi di Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2 Processi Semi-Markoviani . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.3 Catene di Markov assorbenti . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.4 Processi di nascita e di morte . . . . . . . . . . . . . . . . . . . . . . . . 16

2.5 Processo di Poisson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.6 Funzione generatrice dei momenti . . . . . . . . . . . . . . . . . . . . . . 21

2.7 Distribuzione esponenziale . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3 SISTEMI A CODA 29

3.1 Sistemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

M/M/1

3.2 Sistemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

M/M/1/K

3.3 Sistemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

M/M/S

3.4 Sistemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

M/M/∞

3.5 Sistemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

M/M/S/S

3.6 Sistemi con arrivi scoraggiati . . . . . . . . . . . . . . . . . . . . 37

M/M/1

3.7 Sistema token bucket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.8 Sistemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

M/G/1

3.9 Sistemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

M/D/1

3.10 Sistema FDMA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

3.11 Problema HOL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

3.12 Sistemi con tempi di servizio differenziati . . . . . . . . . . . . . . . . . . 61

3.13 Processo di Poisson Composto . . . . . . . . . . . . . . . . . . . . . . . . 63

3.14 Sistema ad accesso TDM sincrono (STDM) . . . . . . . . . . . . . . . . 64

3.15 Sistema ad accesso TDM asincrono (ATDM) . . . . . . . . . . . . . . . . 65

3.16 Sistema di elaborazione con guasti . . . . . . . . . . . . . . . . . . . . . 66

3.17 Sistemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

M/G/1/K

3.18 Sistemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

M/D/K

3.19 Protocollo ALOHA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

3.20 Sistemi con priorità di servizio . . . . . . . . . . . . . . . . . . . 70

M/G/1

3.21 Sistemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

G/M/1

4 RETI DI CODE 89

4.1 Reti di Jackson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

4.2 Controllo della congestione . . . . . . . . . . . . . . . . . . . . . . . . . . 102

1

Capitolo 1

INTRODUZIONE

sistema a coda

Un è un sistema preposto all’erogazione di un servizio con capacità di

gestire l’attesa di richieste che non hanno accesso immediato al servizio da parte

dell’ambiente.

La studia analiticamente il comportamento dei sistemi a coda

teoria dei sistemi a coda

(processo di arrivo in coda, attesa e processo di servizio) e si rivolge verso due tipologie

di sistemi tradizionali:

deterministici,

• Sistemi ovvero catene di montaggio in cui si programmano a

priori i tempi di elaborazione. In questo modo possiamo conoscere istante per

istante tutti gli stati del processo.

stocastici,

• Sistemi ovvero sistemi casuali e aleatori in cui non sono noti a priori i

tempi e gli stati dei processi.

Componenti principali di un sistema a coda:

• rappresenta l’insieme delle richieste dei processi che vogliono accedere al

Arrivi:

servizio. Si individua come parametro di riferimento la distribuzione del tempo

che separa due arrivi consecutivi, ovvero quanto passa da un arrivo al suo

tempo di interarrivo

successivo. Tale parametro è detto e lo indichiamo con

di interarrivo ≤

= Pr{tempo

A(t) t}.

• rappresenta il numero di canali di servizio. Si individua come parametro

Serventi:

di riferimento la distribuzione del tempo che una richiesta trascorre nel servente

tempo di servizio

usufruendo del servizio richiesto. Tale parametro è detto e lo

indichiamo con di servizio ≤

= Pr{tempo

B(t) t}.

• serve per gestire l’attesa delle richieste per l’accesso al servizio. Esistono

Coda:

diverse politiche di gestione delle richieste:

– random,

Politica ovvero si sceglie tra tutte le richieste disponibili negli

arrivi quella da mandare in servizio in modo casuale. Più formalmente si

sceglie secondo un criterio statistico la richiesta da inviare in servizio.

– FIFO

Politica (First ovvero si serve la prima richiesta

In First Out),

arrivata (come un se le richieste venissero gestite in sequenza).

– LIFO

Politica (Last ovvero si serve l’ultima richiesta arrivata

In First Out),

(come se le richieste venissero impilate su uno stack). Tale politica privilegia

le ultime richieste. 2 3

– priorità,

Politica con ovvero si assegna alle richieste un livello specifico di

urgenza nell’accesso al servizio.

Analisi di un sistema a coda:

Analisi completa:

• riguarda la caratterizzazione statistica dei parametri del

sistema scelti come riferimento (di seguito descritti).

Analisi elementare:

• limita l’analisi alla definizione dei momenti statistici di

primo ordine (ovvero il valore medio) dei parametri del sistema scelti come

riferimento (di seguito descritti).

Parametri di riferimento di un sistema a coda (sono variabili aleatorie):

Tempo complessivo di permanenza nel sistema,

• ovvero il tempo che passa

da quando arriva una richiesta a quando viene servita.

Tempo di attesa in coda,

• ovvero il tempo che una richiesta deve attendere in

coda.

Numero di richieste complessivamente nel sistema,

• ovvero le richieste

totali presenti nel sistema (sia tra la coda degli arrivi che nel servizio).

Numero di richieste in coda,

• ovvero il numero di richieste presenti nella coda

degli arrivi.

Numero di richieste in servizio,

• ovvero il numero di richieste presenti nei

serventi.

N.B: probabilità di rifiuto.

nel caso di coda con capacità limitata è di interesse la

Notazione di Kendal. Si classifica ciascun sistema a coda mediante una stringa

alfanumerica del tipo dove le lettere maiuscole sono riferite a lettere e le

A/B/c/d/i

minuscole a numeri. In particolare:

• indica il processo di arrivo. Può assumere i seguenti valori valori:

A – M (Markoviana o senza memoria), indica una distribuzione di Possion.

– D (Deterministica), indica una distribuzione deterministica in cui i tempi

sono noti.

– G (Generica), indica una qualsiasi distribuzione.

• indica il processo di servizio. Può assumere i seguenti valori:

B – M (Markoviana o senza memoria), indica una distribuzione esponenziale.

– D (Deterministica), indica una distribuzione deterministica in cui i tempi

sono noti.

4 CAPITOLO 1. INTRODUZIONE

– G (Generica), indica una qualsiasi distribuzione.

• indica il numero di serventi (numero intero, maggiore o uguale ad

c 1).

• indica la capacità di coda in termini di numeri di richieste (numero intero),

d

ovvero quante richieste il sistema può accettare. Il vincolo è che la capacità di

coda non può essere minore del numero di serventi, ovvero deve essere ≥

d c

(altrimenti la coda non avrebbe senso di esistere). Tale capacità può essere

limitata o illimitata (nel caso in cui sia illimitata non si specifica nessun valore).

Se la capacità di coda è limitata, allora si avranno sistemi con perdite (una volta

riempita la coda dovremo rifiutare delle richieste), altrimenti, se la capacità di

coda è illimitata, allora si avranno sistemi senza perdite (possiamo sempre

accogliere nuove richieste).

• indica la dimensione della popolazione (numero intero). Può essere limitato o

i

illimitato (nel caso in cui sia illimitato non si specifica nessun valore).

ES: (processo di richieste in arrivo senza memoria, processo di servizio

M/G/1

generale, 1 solo servente, capacità e popolazione illimitate).

ES: (processo di richieste in arrivo senza memoria, processo di

M/M/3/8/12

servizio senza memoria, 3 serventi, 8 possibili richieste in code, 12 utenti).

diagramma temporale

Un rappresenta il processo temporale di occupazione del

servizio da parte delle richieste da quando arrivano a quando lasciano il servizio (in

c i

un tempo complessivo ) permettendo ad altre richieste che si trovano nella coda degli

k

i

arrivi di occupare il servizio. 5

Formula di Little (vale per sistemi di tipo senza perdita, ovvero sistemi in cui

G/G/1

il numero di richieste in arrivo è uguale a quelle che vengono servite). Dati il

α(t)

numero di richieste in ingresso contate nell’intervallo il numero di richieste in

[0, t], β(t)

uscita contate nell’intervallo il numero di richieste presenti nel

−

[0, (t) =

t], N α(t) β(t)

sistema al tempo e il tempo totale speso da tutte le richieste

t

R

= (τ )dτ

t γ(t) N

0

all’interno del sistema, allora a regime vale la relazione .

=

N λT

Dim: α(t)

Possiamo considerare poiché possiamo calcolare

t X

R

= (τ )dτ =

γ(t) N T

i

0 i=1

l’area come somma di rettangoli di altezza 1 e larghezza dove rappre-

T T

i i

senta il tempo complessivo trascorso da una richiesta all’interno del sistema

(da quando arriva a quando esce).

Definiamo quindi i valori medi:

• , indica la frequenza media (o tasso medio) di arrivo delle

α(t)

=

λ

t t

richieste. t

R

• , indica il tempo medio che una richiesta spende

N (τ )dτ

γ(t)

= =

T 0

t α(t) α(t)

nel sistema. t

R

• , indica il numero medio di elementi nel sistema.

N (τ )dτ

γ(t)

= =

N 0

t t t t t

R R

Allora possiamo facilmente calcolare .

N N

(τ )dτ (τ )dτ N

1

= = =

T t

0 0

t α(t)

α(t) t λ t

t

Di conseguenza otteniamo che e quindi .

N ·

= =

T λ T N

t

t t t t

λ

Ipotizzando che il sistema sia ergodico e stazionario, allora:

t

• lim =

λ λ

t

t→∞

6 CAPITOLO 1. INTRODUZIONE

• lim =

T T

t

t→∞

• lim =

N N

t

t→∞

Allora a regime si ottiene la formula di Little .

=

N λT

C.V.D.

Perciò essendo un parametro di sistema, se riusciamo a trovare un valore tra e

λ N T

allora possiamo trovare l’altra tramite tale relazione.

Ricordando che abbiamo definito il tempo complessivo come il tempo passato in coda

T

più il tempo di servizio, allora possiamo scrivere anche dove è il tempo

= +

T w x, w

medio di coda ed è il tempo medio di servizio. Perciò moltiplicando per otteniamo

x λ

, dove rappresenta il numero medio di richieste in coda e

= + = + =

λT λw λx Q s N Q

è il numero medio di richieste in servizio.

s

Fattore di utilizzazione dei serventi. Consideriamo:

frequenza media di arrivo delle richieste

• la (o ovvero il

tasso medio)

α(t)

=

λ t

numero medio di arrivi di richieste nel sistema nell’unità di tempo.

# richieste servite capacità di servizio

• la ovvero la capacità che ha un singolo

=

µ t

servente di fornire un servizio (rappresenta quindi il numero medio di richieste

servite nell’unità di tempo).

N.B: nel caso in cui il sistema disponga di un numero di serventi (> allora

1)

m

la sarà data da

capacità totale di servizio ·

m µ.

fattore di utilizzazione dei serventi

Allora si definisce il come:

tasso medio di arrivo delle richieste λ

= =

η capacità totale di servizio ·

m µ

Tale parametro rappresenta la frazione di tempo in cui i serventi risultano essere

occupati.

Fattore di carico. Supponendo che ogni singola richiesta necessiti di un tempo medio

fattore di carico

di servizio allora avremo e quindi dove è detto

λx

1

= =

x, µ η λx

x m

del sistema e si indica con ρ.

In particolare, dato un sistema a coda con serventi e fattore di utilizzazione dei

m

serventi allora definiamo il fattore di carico come:

η, λ

· ·

= = =

ρ λ x m η µ

Condizioni di stabilità. Un sistema risulta stabile se:

• 1

ρ<

• ·

λ<m µ 7

N.B: nel caso in cui si abbiano più serventi, allora si possono gestire un numero di

richieste maggiori.

Probabilità di servente libero. probabilità di servente libero

Definiamo la in

P 0

un sistema ovvero la probabilità di non avere richieste all’interno del sistema

G/G/1,

(poiché nel caso in cui fosse presente anche una sola richiesta allora il sistema sarebbe

occupato a servirla), come la probabilità che il sistema sia vuoto. In particolare, fissato

un tempo di riferimento indichiamo con:

t,

• l’intervallo di tempo per il quale il servente risulta essere occupato.

· −

(1 )

t P 0

• il tempo medio di servizio.

x

• il numero medio di richieste arrivate al sistema al tempo t.

·

λ t

Allora, imponendo la stabilità del sistema, otteniamo che la probabilità di servente

libero è definita come:

−

(1 )

P t

o ⇒ − − ⇒ −

A = = 1 = 1 = 1

λ

t P λx ρ P ρ

0 0

A

x

Capitolo 2

PROCESSI STOCASTICI

processo stocastico

Un (detto anche o è una

processo aleatorio processo casuale)

famiglia di variabili aleatorie così definite .

{X(t )}

i i

In particolare si distinguono due tipi di processi stocastici:

tempo continuo:

• Processo stocastico il parametro indice (ovvero non è

t)

soggetto a restrizioni per quanto riguarda i valori che può assumere (risulta essere

un processo continuo nel tempo).

tempo discreto:

• Processo stocastico il parametro indice può assumere solo

determinati valori (risulta essere un processo che si verifica solo per alcuni istanti

di tempo definiti). spazio

L’insieme di tutti i valori che il processo stocastico può assumere è detto

X(t)

degli stati.

N.B: catena.

se lo spazio degli stati è discreto allora si parla di

ES (lancio di una moneta):

Consideriamo il lancio di una moneta. Ad un certo istante di tempo il pro-

cesso genera una variabile aleatoria con distribuzione di Bernoulli (si ha la

stessa probabilità che esca testa o croce). In particolare:

1 1

Pr(testa) = Pr(croce) =

2 2

Quindi il processo di Bernoulli è un processo stocastico con spazio degli sta-

ti finito.

ES (passeggiata aleatoria o casuale): passeggiata aleatoria

Definiamo un processo stocastico detto (ad esem-

Z

pio pallina che si muove su degli intervalli fissati in una retta). Siano con

Z

i

variabili aleatorie ugualmente distribuite ed indipendenti con

= 1, 2,

i ... (indica la probabilità di muoversi in avanti dallo stato in cui

Pr(Z = 1) = p

i

ci troviamo) ed (indica la probabilità di muoversi

−1) −

Pr(Z = = 1 =

p q

i

all’indietro dallo stato in cui ci troviamo).

8 9

Il processo osservato al passo sarà definito come:

n n

X

=

X Z

n i

i=1

Tale processo indica lo spostamento unidimensionale casuale. distribuzione di

Dato un processo aleatorio osservato a , allora è una v.a. con

(t)

t X

1 1

probabilità definita da ≤ }.

(x ) = )

F , t P r{X(t x

X 1 1 1 1

Il valore medio di un processo aleatorio osservato al tempo rappresenta la media della

t

v.a. conseguente, ovvero (t) =

µ E[X(t)].

X stazionario

Un processo aleatorio si dice quando le v.a. realizzate con osservazioni

diverse del processo hanno tutte la stessa distribuzione di probabilità (ovvero quando la

distribuzione di probabilità delle v.a. del processo è costante). Formalmente:

(x, = (x, + ) = (x)

F t) F t τ F

X X X

Ovvero un processo aleatorio è stazionario se la distribuzione di probabilità non dipende

dall’istante di osservazione. stazionario in senso lato

Un processo aleatorio si dice se:

• costante (il valore medio delle v.a. è costante, ovvero non dipende dal

=

E[X(t)]

tempo).

• (la funzione di autocorrelazione del processo

−

(t, = = (s

R s) X(s)] R t)

E[X(t),

X X

non dipende in modo assoluto da e da ma solo dalla loro differenza −

s t s t).

ES:

Sia una sequenza di v.a. ugualmente distribuite ed indipenden-

{X ≥ 0}

, n

n

ti con media nulla e varianza unitaria. Dimostriamo che il processo dato è

stazionario in senso lato.

Dobbiamo quindi verificare le due condizioni viste in precedenza:

• costante è sempre verificata poiché per ipotesi abbiamo v.a.

=

E[X(t)]

indipendenti e con media nulla. Perciò il valore medio delle v.a. è

sempre costante e non dipende dal tempo per qualsiasi realizzazione

del processo.

• da cui otteniamo il sistema:

·

(n, + = ]