Appunti di Telecommunication Networks

Telecommunication Networks 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 M/M/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
• 3.2 Sistemi M/M/1/K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
• 3.3 Sistemi M/M/S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
• 3.4 Sistemi M/M/∞ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
• 3.5 Sistemi M/M/S/S . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
• 3.6 Sistemi con arrivi scoraggiati M/M/1 . . . . . . . . . . . . . . . . . 37
• 3.7 Sistema token bucket . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
• 3.8 Sistemi M/G/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
• 3.9 Sistemi M/D/1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
• 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 M/G/1/K . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
• 3.18 Sistemi M/D/K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
• 3.19 Protocollo ALOHA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
• 3.20 Sistemi con priorità di servizio M/G/1 . . . . . . . . . . . . . . . . 70
• 3.21 Sistemi G/M/1 77
• 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:

• Sistemi deterministici, 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.
• Sistemi stocastici, 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

• Arrivi: rappresenta l’insieme delle richieste dei processi che vogliono accedere al servizio. Si individua come parametro di riferimento la distribuzione del tempo che separa due arrivi consecutivi, ovvero quanto passa da un arrivo al suo successivo. Tale parametro è detto tempo di interarrivo e lo indichiamo con A(t) = Pr{tempo di interarrivo ≤ t}.
• Serventi: rappresenta il numero di canali di servizio. Si individua come parametro di riferimento la distribuzione del tempo che una richiesta trascorre nel servente usufruendo del servizio richiesto. Tale parametro è detto tempo di servizio e lo indichiamo con B(t) = Pr{tempo di servizio ≤ t}.
• Coda: serve per gestire l’attesa delle richieste per l’accesso al servizio. Esistono diverse politiche di gestione delle richieste:

• Politica random, 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.
• Politica FIFO (First In First Out), ovvero si serve la prima richiesta arrivata (come un se le richieste venissero gestite in sequenza).
• Politica LIFO (Last In First Out), ovvero si serve l’ultima richiesta arrivata, (come se le richieste venissero impilate su uno stack). Tale politica privilegia le ultime richieste.

2 3

• Politica con priorità, 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

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: nel caso di coda con capacità limitata è di interesse la probabilità di rifiuto.

Notazione di Kendall

Notazione di Kendall. Si classifica ciascun sistema a coda mediante una stringa alfanumerica del tipo A/B/c/d/i dove le lettere maiuscole sono riferite a lettere e le minuscole a numeri. In particolare:

• A indica il processo di arrivo. Può assumere i seguenti valori valori:
• M (Markoviana o senza memoria), indica una distribuzione di Poisson.
• D (Deterministica), indica una distribuzione deterministica in cui i tempi sono noti.
• G (Generica), indica una qualsiasi distribuzione.
• B indica il processo di servizio. Può assumere i seguenti valori:
• 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.
• C indica il numero di serventi (numero intero, maggiore o uguale ad 1).
• D indica la capacità di coda in termini di numeri di richieste (numero intero), 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).
• I indica la dimensione della popolazione (numero intero). Può essere limitato o illimitato (nel caso in cui sia illimitato non si specifica nessun valore).

ES: M/G/1 (processo di richieste in arrivo senza memoria, processo di servizio generale, 1 solo servente, capacità e popolazione illimitate).

ES: M/M/3/8/12 (processo di richieste in arrivo senza memoria, processo di 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 un tempo complessivo c i k i) permettendo ad altre richieste che si trovano nella coda degli arrivi di occupare il servizio.

5

Formula di Little

Formula di Little (vale per sistemi di tipo G/G/1 senza perdita, ovvero sistemi in cui il numero di richieste in arrivo è uguale a quelle che vengono servite). Dati il numero di richieste in ingresso α(t) contate nell’intervallo [0, t], il numero di richieste in uscita β(t) contate nell’intervallo [0, t], il numero di richieste presenti nel sistema al tempo t N(t) = α(t) − β(t) e il tempo totale speso da tutte le richieste R = ∫ N(τ)dτ all’interno del sistema, allora a regime vale la relazione N = λT.

Dim:

Possiamo considerare R = ∫ N(τ)dτ = γ(t) = ∑ T i poiché possiamo calcolare l’area come somma di rettangoli di altezza 1 e larghezza T i dove T i rappresenta il tempo complessivo trascorso da una richiesta all’interno del sistema (da quando arriva a quando esce).

Definiamo quindi i valori medi:

• λ = α(t)/t, indica la frequenza media (o tasso medio) di arrivo delle richieste.
• T = ∫ N(τ)dτ / α(t) = γ(t) / α(t), indica il tempo medio che una richiesta spende nel sistema.
• N = ∫ N(τ)dτ / t = γ(t) / t, indica il numero medio di elementi nel sistema.

Allora possiamo facilmente calcolare T = ∫ N(τ)dτ / α(t) = (∫ N(τ)dτ / t) / (α(t) / t) = N / λ.

Di conseguenza otteniamo che T = N / λ e quindi N = λ · T.

Ipotizzando che il sistema sia ergodico e stazionario, allora:

• lim λt = λ per t → ∞

6 Capitolo 1. Introduzione

• lim Tt = T per t → ∞
• lim Nt = N per 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 N e T allora possiamo trovare l’altra tramite tale relazione.

Ricordando che abbiamo definito il tempo complessivo T come il tempo passato in coda più il tempo di servizio, allora possiamo scrivere anche T = w + x, dove w è il tempo medio di coda ed x è il tempo medio di servizio. Perciò moltiplicando per λ, otteniamo λT = λw + λx = Q + s = N, dove Q rappresenta il numero medio di richieste in coda e s è il numero medio di richieste in servizio.

Fattore di utilizzazione dei serventi

Fattore di utilizzazione dei serventi. Consideriamo:

• La frequenza media di arrivo delle richieste (o tasso medio) λ = α(t)/t ovvero il numero medio di arrivi di richieste nel sistema nell’unità di tempo.
• La capacità di servizio µ = # richieste servite / t ovvero la capacità che ha un singolo 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 m di serventi (> 1) allora la capacità totale di servizio sarà data da m · µ.

Allora si definisce il fattore di utilizzazione dei serventi 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

Fattore di carico. Supponendo che ogni singola richiesta necessiti di un tempo medio di servizio x, allora avremo x = 1 / µ e quindi η = λx / m, dove λx è detto fattore di carico del sistema e si indica con ρ.

In particolare, dato un sistema a coda con m serventi e fattore di utilizzazione dei serventi η, allora definiamo il fattore di carico come:

ρ = λ · x = λ / µ = m · η

Condizioni di stabilità

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 probabilità di servente libero P0 in un sistema G/G/1 ovvero la probabilità di non avere richieste all’interno del sistema, (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 t, indichiamo con:

• (1 − P0) · t l’intervallo di tempo per il quale il servente risulta essere occupato.
• X il tempo medio di servizio.
• λ · t il numero medio di richieste arrivate al sistema al tempo t.

Allora, imponendo la stabilità del sistema, otteniamo che la probabilità di servente libero è definita come:

A = (1 − P0)t / Ax = λt ⇒ 1 − P0 = λx ⇒ P0 = 1 − λx = 1 − ρ

Capitolo 2 Processi stocastici

Processo stocastico

Un (detto anche processo aleatorio o processo casuale) è una famiglia di variabili aleatorie così definite {X(t i)} i.

In particolare si distinguono due tipi di processi stocastici:

• Processo stocastico tempo continuo: il parametro indice t (ovvero non è soggetto a restrizioni per quanto riguarda i valori che può assumere (risulta essere un processo continuo nel tempo).
• Processo stocastico tempo discreto: il parametro indice può assumere solo determinati valori (risulta essere un processo che si verifica solo per alcuni istanti di tempo definiti).

L’insieme di tutti i valori che il processo stocastico X(t) può assumere è detto spazio degli stati.

N.B: se lo spazio degli stati è discreto allora si parla di catena.

ES (lancio di una moneta):

Consideriamo il lancio di una moneta. Ad un certo istante di tempo il processo genera una variabile aleatoria con distribuzione di Bernoulli (si ha la stessa probabilità che esca testa o croce). In particolare:

Pr(testa) = 1/2 Pr(croce) = 1/2

Quindi il processo di Bernoulli è un processo stocastico con spazio degli stati finito.

ES (passeggiata aleatoria o casuale):

Definiamo un processo stocastico detto passeggiata aleatoria Z (ad esempio pallina che si muove su degli intervalli fissati in una retta). Siano Z i con i = 1, 2, ... variabili aleatorie ugualmente distribuite ed indipendenti con Pr(Z i = 1) = p (indica la probabilità di muoversi in avanti dallo stato in cui ci troviamo) ed Pr(Z i = −1) = 1 − p = q (indica la probabilità di muoversi all’indietro dallo stato in cui ci troviamo).

8 9

Il processo osservato al passo n sarà definito come:

X n = ∑ Z i, i = 1

Tale processo indica lo spostamento unidimensionale casuale.

Distribuzione, valore medio e stazionarietà

Dato un processo aleatorio osservato a t1, allora X(t1) è una v.a. con distribuzione di probabilità definita da F X (x1, t1) = Pr{X(t1) ≤ x1}.

Il valore medio di un processo aleatorio osservato al tempo t rappresenta la media della v.a. conseguente, ovvero µX(t) = E[X(t)].

Un processo aleatorio si dice stazionario 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:

F X (x, t) = F X (x, t + τ) = F X (x)

Ovvero un processo aleatorio è stazionario se la distribuzione di probabilità non dipende dall’istante di osservazione.

Un processo aleatorio si dice stazionario in senso lato se:

• E[X(t)] = costante (il valore medio delle v.a. è costante, ovvero non dipende dal tempo).
• R X (t, s) = E[X(t), X(s)] = R X (s − t) (la funzione di autocorrelazione del processo non dipende in modo assoluto da s e da t ma solo dalla loro differenza s − t).

ES:

Sia {X n ≥ 0}, n una sequenza di v.a. ugualmente distribuite ed indipendenti con media nulla e varianza unitaria. Dimostriamo che il processo dato è stazionario in senso lato.

Dobbiamo quindi verificare le due condizioni viste in precedenza:

• E[X(t)] = costante è sempre verificata poiché per ipotesi abbiamo v.a. 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, + = ]