Si chiama teletraffico il traffico (dati, voce, altro) che attraversa un apparato o una rete di telecomunicazioni. Un sistema soggetto a traffico è allora un sistema caratterizzato da un insieme di utenti che entrano nel sistema per usufruire di un servizio, vi permangono per un certo periodo occupando una risorsa messa a disposizione dal sistema stesso, e alla fine del servizio escono.
La definizione è volutamente astratta: un utente può essere una chiamata telefonica, un pacchetto IP, un paziente in un centro vaccinale. Le ipotesi di lavoro sono quattro e vanno prese sul serio, perché tutto il resto ne discende:
La seconda ipotesi («ciò che entra esce») è la legge di conservazione su cui poggia l'intera teoria. Se in un intervallo lungo T entrano a(T) utenti e ne escono d(T), in condizioni di equilibrio statistico deve valere a(T) = d(T). Il teorema di Little e le formule di Erlang non sono che modi diversi di scrivere questa uguaglianza.
Il traffico istantaneo k(t) è una funzione a gradini che salta di +1 a ogni ingresso e di −1 a ogni uscita. Per farne una grandezza maneggevole se ne prende la media su un intervallo T e poi il limite:
A = lim (T → ∞) (1/T) ∫₀ᵀ k(t) dtSe questo limite esiste, A si dice traffico medio nel sistema. Se non esiste, il sistema non ha un comportamento stabile nel tempo e non può essere studiato con i semplici modelli che useremo: è un avvertimento importante, perché in rete i regimi non stazionari sono la norma e la teoria vale solo a tratti.
Per definizione A è adimensionale: è un numero di utenti, non un numero di utenti al secondo. Ciò nonostante è stata definita una unità di misura del traffico, l'Erlang (simbolo E). Un traffico di 40 E significa che in media 40 utenti occupano contemporaneamente una risorsa.
Se k(t) è un processo ergodico, allora A esiste sempre ed è uguale al valor medio statistico di k(t) in un istante generico. Da qui le tre ipotesi di lavoro semplificative dichiarate a lezione:
Il punto 3 è la chiave del dimensionamento reale: non si progetta una rete sul traffico medio della giornata, ma sull'ora di punta. Gli esercizi del corso lo fanno sistematicamente, parlando di «periodi di traffico di punta» o suddividendo la giornata in fasce con valori di A diversi.
Si introducono tre grandezze contatore: a(t) è il numero totale di arrivi al sistema fino all'istante t, d(t) il numero totale di partenze, δn il tempo speso nel sistema dall'utente n-esimo. Da esse si ricavano:
frequenza media di arrivo λₛ = lim (t → ∞) a(t) / t
tempo medio speso nel sistema δ̄ = lim (n → ∞) (1/n) ∑ₙ δₙSi può dimostrare che esiste un legame semplice, ma fondamentale per la teoria del traffico, tra i valori medi di traffico, frequenza di arrivo e tempo di permanenza, purché questi valori medi esistano. È il teorema di Little:
A = λₛ ⋅ δ̄Due proprietà lo rendono uno degli strumenti più usati del corso:
Un sistema a coda è un sistema soggetto a traffico in cui ciascun utente è servito da un servitore (una risorsa); se i servitori sono tutti occupati l'utente resta in attesa all'interno di una coda; e se la coda ha dimensione finita, un utente che la trova piena viene rifiutato e non entra nel sistema.
Alle ipotesi generali se ne aggiungono quattro specifiche dei sistemi a coda:
| Simbolo | Significato |
|---|---|
| λ | frequenza media di arrivo al sistema |
| λs | frequenza media di ingresso nel sistema (arrivi accettati) |
| λp | frequenza media di rifiuto di accesso al sistema |
| δ̄ | tempo medio di permanenza di un utente generico |
| η̄ | tempo medio speso in coda da un utente generico |
| &thetas;̄ | tempo medio speso in servizio |
| Aq | numero medio di utenti in coda |
| As | numero medio di utenti in servizio |
Poiché arrivo ≠ ingresso, vale λ = λs + λp. Applicando il teorema di Little al sistema complessivo e ai suoi due sottosistemi — la coda e l'insieme dei servitori — si ottengono tre relazioni, e dal fatto che il tempo di permanenza è la somma del tempo in coda e del tempo in servizio se ne ricava una quarta:
A = λₛ δ̄ (sistema)
Aₜ = λₛ η̄ (coda)
Aₛ = λₛ &thetas;̄ (servitori)
δ̄ = η̄ + &thetas;̄ ⇒ A = Aₜ + AₛQueste quattro righe risolvono da sole metà dei quesiti di teletraffico. Nel tipico esercizio si conosce λ, si calcola &thetas;̄ dalla lunghezza dei pacchetti e dalla capacità del collegamento, si ricava una probabilità di stato dalla formula di Erlang appropriata, e tutto il resto arriva da qui. Attenzione al pedice: in Little compare sempre λs, la frequenza di ingresso, non quella di arrivo.
Le tre definizioni successive introducono una piccola finzione contabile che vale la pena capire fino in fondo.
A₀ = λ &thetas;̄ traffico offerto al sistema
Aₛ = λₛ &thetas;̄ traffico smaltito dal sistema (throughput)
Aₚ = λₚ &thetas;̄ traffico perduto dal sistema
A₀ = Aₛ + AₚLe slide sottolineano che A0 e Ap sono grandezze fittizie, definite per analogia attribuendo un tempo medio di servizio anche ai clienti rifiutati dal sistema. Più precisamente:
Si definisce infine l'utilizzazione dei servitori:
ρ = Aₛ / m con 0 ≤ ρ ≤ 1In un sistema ergodico l'utilizzazione dei servitori coincide con la percentuale media di tempo in cui un generico servitore risulta essere occupato. È la lettura che rende ρ immediatamente misurabile su un apparato reale: basta osservare per quanta frazione del tempo l'interfaccia di uscita sta trasmettendo.
Confondere A0 con A è l'errore più frequente. A0 = λ&thetas;̄ è il traffico offerto, si calcola sempre con la frequenza di arrivo e il tempo di servizio, e nei sistemi a perdita è maggiore del traffico effettivamente smaltito. A è invece il numero medio di utenti presenti, che in un sistema con attesa include anche chi sta aspettando e quindi può essere molto maggiore di A0.
La notazione di Kendall permette di esprimere in maniera compatta le caratteristiche di un sistema a coda con sei campi:
A / B / m / n / p / SI simboli usati per i processi di arrivo e di servizio sono quattro:
| Simbolo | Processo |
|---|---|
M | processo aleatorio senza memoria (Poisson per gli arrivi, esponenziale per i tempi) |
D | processo deterministico |
U | processo aleatorio con distribuzione uniforme |
G | processo aleatorio generale |
Per la disciplina di coda si usano:
Valgono infine due convenzioni di omissione che è indispensabile ricordare: se uno dei valori numerici (m, n, p) non è specificato si assume infinito; se la disciplina di coda non è specificata si assume FIFO. Così M/M/1 significa in realtà «arrivi di Poisson, servizio esponenziale, un servitore, coda infinita, popolazione infinita, disciplina FIFO».
Il processo degli arrivi è un processo stocastico discreto nei valori e tempo-continuo. Lo si caratterizza in due modi equivalenti: attraverso la probabilità P(k,T) di avere k arrivi in un intervallo T, oppure attraverso la statistica del tempo inter-arrivo τ, che è una variabile aleatoria continua.
Il processo di Poisson descrive arrivi casuali non contemporanei provenienti da una popolazione molto grande di utenti indipendenti. La derivazione mostrata a lezione parte da quattro ipotesi e da un passaggio al limite:
Il risultato è la formula di Poisson di parametro λ, la frequenza di arrivo:
P(k,T) = (λT)ᵏ e⁻ᵏᵀ / k!
E[k] = λT σ²ᵏ = λTMedia e varianza coincidono: è la firma della distribuzione di Poisson. Si dimostra inoltre che il tempo inter-arrivo in un processo di Poisson ha distribuzione esponenziale con lo stesso parametro λ: è precisamente il ponte fra questo capitolo e l'assenza di memoria studiata nel capitolo 2.
Due proprietà rendono il processo di Poisson lo strumento di modellazione più comodo che esista, e sono usate in quasi tutti gli esercizi del corso.
Composizione. Il processo che risulta dalla composizione di due processi di Poisson con parametri λA e λB è ancora un processo di Poisson con parametro λ = λA + λB. Il risultato vale in generale: componendo N processi di Poisson si ottiene un processo di Poisson di parametro pari alla somma dei parametri.
Decomposizione. Vale anche il procedimento inverso. Si considerino N probabilità Pi la cui somma sia pari a 1; la decomposizione di un processo di Poisson di parametro λ in N processi distinti, attribuendo casualmente ciascun arrivo al processo i-esimo con probabilità Pi, genera N processi ancora di Poisson, ciascuno di parametro λi = Piλ.
La decomposizione è ciò che rende risolubili gli esercizi sul bilanciamento di carico: un router che smista i pacchetti su tre interfacce con probabilità p1, p2, p3 si studia come tre sistemi M/M/1 indipendenti, ciascuno con la propria frequenza di arrivo piλ. Senza questa proprietà servirebbe un modello congiunto molto più complicato.
Il processo di servizio è un processo stocastico tempo-continuo caratterizzato dalla statistica del tempo di servizio &thetas; di un utente generico, che è una variabile aleatoria continua. Si definisce la frequenza media di servizio:
μ = 1 / &thetas;̄Le slide passano poi in rassegna cinque famiglie di distribuzioni. Ciò che le distingue davvero, ai fini del corso, non è la forma della densità ma il loro valore quadratico medio E[&thetas;²], perché è quello che entrerà nella formula di Pollaczek–Khinchine del capitolo 7.
| Tempo di servizio | Descrizione | E[&thetas;²] |
|---|---|---|
| Esponenziale | senza memoria, parametro μ | 2 &thetas;̄² |
| Deterministico | &thetas; sempre uguale a &thetas;̄ | &thetas;̄² |
| Uniforme | equiprobabile in un intervallo | intermedio fra i due precedenti |
| Erlang di grado r | somma di r esponenziali i.i.d. di media &thetas;̄/r | (1 + 1/r) &thetas;̄² |
| Pareto | heavy tailed, parametri di posizione t0 e forma α | può divergere |
Il tempo di servizio di Erlang si ottiene come somma di r variabili aleatorie esponenziali indipendenti e identicamente distribuite. Poiché la densità di una somma di variabili indipendenti è la convoluzione delle densità (capitolo 2), la densità di Erlang di grado r si ricava dalla convoluzione di r densità esponenziali. Al crescere di r la densità si concentra attorno alla media: per r = 1 si ritrova l'esponenziale, per r → ∞ si tende al caso deterministico. È il parametro che permette di modellare un servizio «quasi regolare ma non del tutto».
Il tempo di servizio di Pareto ha un comportamento di tipo heavy tailed: la probabilità di avere tempi di servizio molto lunghi rispetto alla media non è trascurabile. La densità è definita da due parametri positivi, la posizione t0 e la forma α, e il comportamento heavy tailed si manifesta per 1 < α ≤ 2.
Non è un esercizio di stile: le slide citano il celebre lavoro di W. E. Leland e colleghi, On the Self-similar Nature of Ethernet Traffic (IEEE/ACM Transactions on Networking, vol. 2 n. 1, febbraio 1994), che ha mostrato come il traffico Ethernet reale sia auto-simile e non descrivibile con i modelli poissoniani classici. È il promemoria che i modelli del corso sono approssimazioni, ottime per il dimensionamento ma non fedeli in ogni regime.
Si chiama tempo di servizio residuo T′ il tempo di servizio ancora da trascorrere a partire da un istante di osservazione t1 scelto a caso. Se ne ricavano densità di probabilità e valor medio:
fₜ′(t) = [ 1 − Fᵗ(t) ] / &thetas;̄
E[T′] = E[&thetas;²] / (2 &thetas;̄)La seconda formula è quella che conta, e contiene una sorpresa: il tempo residuo medio non è metà del tempo di servizio medio, se non nel caso deterministico. Dipende dal valore quadratico medio, cioè dalla variabilità.
| Tempo di servizio | E[&thetas;²] | E[T′] |
|---|---|---|
| Deterministico | &thetas;̄² | &thetas;̄/2 |
| Erlang di grado r | (1+1/r) &thetas;̄² | (1+1/r) &thetas;̄/2 |
| Esponenziale | 2 &thetas;̄² | &thetas;̄ |
La riga dell'esponenziale è la conferma dell'assenza di memoria: arrivando in un istante qualsiasi e trovando un servizio in corso, il tempo che resta da aspettare ha media pari all'intero tempo di servizio medio. È come se il servizio ricominciasse da capo — che è esattamente ciò che significa non avere memoria.
Il paradosso del tempo residuo è una domanda classica: «se i pacchetti durano in media 1 ms e arrivo in un istante a caso, quanto devo aspettare che finisca quello in corso?». Con servizio deterministico 0.5 ms; con servizio esponenziale 1 ms; con servizio molto variabile anche molto di più. Il motivo intuitivo è che, campionando un istante a caso, è più probabile cadere dentro un servizio lungo che dentro uno corto.
Gli esercizi proposti sul foglio «Esempi ed esercizi sulla teoria del teletraffico» mettono alla prova esattamente le sei relazioni viste finora. Ecco i primi quattro, con la traccia della soluzione.
Testo. Il numero medio di chiamate effettuate attraverso una stazione radio base è λ = 20 chiamate/min e la durata media di una chiamata è &thetas;̄ = 120 s. La stazione ha risorse sufficienti per accettare immediatamente qualsiasi chiamata in arrivo, senza rifiutarla né metterla in attesa. Trovare il numero medio di chiamate attive, cioè il traffico medio A.
Nessun rifiuto ⇒ λₛ = λ = 20 ch/min
Nessuna attesa ⇒ δ̄ = &thetas;̄ = 120 s = 2 min
Little: A = λₛ δ̄ = 20 ⋅ 2 = 40 EIl passaggio delicato è uno solo: rendere omogenee le unità di tempo prima di moltiplicare. Il risultato è adimensionale.
Testo. Il numero medio di utenti presenti nell'arco della giornata è approssimabile con 200 E dalle 8 alle 17, 50 E dalle 17 alle 20, 18 E dalle 20 alle 8. Il tempo di permanenza medio è rispettivamente 8 min, 5 min e 6 min. Trovare la frequenza media di ingresso λs nei tre intervalli.
Little invertito: λₛ = A / δ̄
8–17 λₛ = 200 / 8 = 25 utenti/min
17–20 λₛ = 50 / 5 = 10 utenti/min
20–8 λₛ = 18 / 6 = 3 utenti/minNota il metodo: la giornata viene spezzata in tre finestre, e dentro ciascuna si assume un comportamento ergodico. È esattamente l'ipotesi di lavoro dichiarata nella sezione 2.
Testo. Una struttura medica ha 10 punti di vaccinazione; esattamente ogni minuto viene ammesso un nuovo paziente; la sala d'attesa ospita fino a 50 pazienti e chi la trova piena viene invitato a ripresentarsi; il numero totale di pazienti è così grande da potersi considerare infinito. Quando un punto si libera, i pazienti di età pari o superiore a 60 anni hanno la precedenza sui più giovani. Il tempo di vaccinazione è aleatorio ma ipotizzabile senza memoria, con media 15 minuti. Descrivere il sistema in notazione di Kendall e calcolare il traffico offerto.
arrivi esattamente ogni minuto → A = D (deterministico)
servizio senza memoria → B = M (esponenziale)
10 punti di vaccinazione → m = 10
50 posti in sala d attesa → n = 50
popolazione infinita → p = ∞
precedenza agli over 60 → S = PRIO
D / M / 10 / 50 / ∞ / PRIO
λ = 1 paziente/min &thetas;̄ = 15 min
A₀ = λ &thetas;̄ = 15 EIl traffico offerto vale 15 E contro 10 servitori: il sistema è sovraccarico e la sala d'attesa lavorerà quasi sempre satura. Il conto di Kendall serve proprio a rendere immediatamente visibile questo squilibrio.
Testo. Un centralino PABX è collegato alla rete pubblica tramite m = 20 linee. La frequenza media di arrivo delle chiamate verso la PSTN è 3 chiamate/min e la durata media è 5 min. Sapendo che la probabilità che una chiamata trovi tutte le linee occupate e venga rifiutata è pari al 5%, calcolare il traffico smaltito e l'utilizzazione media delle linee.
A₀ = λ &thetas;̄ = 3 ⋅ 5 = 15 E (traffico offerto)
πₚ = 0.05
Aₛ = A₀ (1 − πₚ) = 15 ⋅ 0.95 = 14.25 E (traffico smaltito)
Aₚ = A₀ − Aₛ = 0.75 E (traffico perduto)
ρ = Aₛ / m = 14.25 / 20 = 0.7125 → 71.25%Il sistema è a perdita: non c'è spazio di attesa, e la probabilità di blocco del 5% si traduce direttamente in traffico che non viene mai smaltito. Nel capitolo 5 vedremo come calcolare quel 5% invece di riceverlo in dote.
Nell'esercizio 5 dello stesso foglio si chiede l'utilizzazione dell'interfaccia di un router con pacchetti di lunghezza mista (64 byte al 40%, 1500 byte al 60%) su un collegamento a 10 Mbit/s con λ = 800 pacchetti/s. Il metodo è identico: si calcola la lunghezza media 0.4⋅64 + 0.6⋅1500 = 925.6 byte, da cui &thetas;̄ = 8⋅925.6 / 10⋅10⁶ ≈ 740 µs e ρ = λ&thetas;̄ ≈ 0.59. Sul singolo servitore l'utilizzazione coincide con il traffico smaltito.
A = λs ⋅ δ̄: il traffico medio nel sistema è il prodotto della frequenza media di ingresso per il tempo medio di permanenza. Vale purché i valori medi coinvolti esistano, ed è indipendente dal tipo di processo degli arrivi e dal tipo di servizio. Si applica in modo analogo a qualunque sottosistema: alla sola coda dà Aq = λsη̄, ai soli servitori As = λs&thetas;̄.
Perché il traffico medio A è un numero di utenti mediato nel tempo, quindi privo di dimensioni fisiche. L'Erlang è un'unità convenzionale introdotta per dare un nome a quella grandezza e distinguerla, nella lettura di un risultato, da un numero puro qualsiasi. Un traffico di 40 E significa 40 risorse mediamente occupate.
A0 = λ&thetas;̄ è il traffico offerto, calcolato con la frequenza di arrivo: rappresenta il numero medio di utenti in servizio in un sistema con infinite risorse. As = λs&thetas;̄ è il traffico smaltito (throughput), calcolato con la frequenza di ingresso. Ap = λp&thetas;̄ è il traffico perduto. Vale A0 = As + Ap. A0 e Ap sono grandezze fittizie: si attribuisce un tempo di servizio anche a chi non è stato servito.
ρ = As/m, con 0 ≤ ρ ≤ 1. In un sistema ergodico coincide con la percentuale media di tempo in cui un generico servitore risulta occupato. Su un'interfaccia di router è la frazione di tempo in cui l'interfaccia sta effettivamente trasmettendo.
M/D/4/0/∞/LIFO. Ricorda le convenzioni: i valori numerici non specificati si assumono infiniti e la disciplina non specificata si assume FIFO. Poiché qui la coda è nulla e la disciplina non è quella di default, entrambi i campi vanno scritti esplicitamente. Con coda nulla, però, la disciplina è irrilevante: nessuno aspetta mai.
P(k,T) = (λT)k e−λT / k!, con E[k] = σ²k = λT: media e varianza coincidono. Equivalentemente, il tempo inter-arrivo ha distribuzione esponenziale di parametro λ, con media 1/λ. Le due caratterizzazioni sono due modi di descrivere lo stesso processo.
Composizione: la somma di N processi di Poisson di parametri λi è ancora Poisson, di parametro λ = ∑λi. Decomposizione: assegnando ciascun arrivo al ramo i con probabilità Pi (con ∑Pi = 1) si ottengono N processi ancora di Poisson, di parametro λi = Piλ. È il modello del load balancing statistico.
È la somma di r variabili aleatorie esponenziali indipendenti e identicamente distribuite. La sua densità si ottiene dalla convoluzione di r densità esponenziali. Il suo valore quadratico medio vale (1 + 1/r)&thetas;̄²: per r = 1 si ritrova l'esponenziale (2&thetas;̄²), per r → ∞ si tende al deterministico (&thetas;̄²).
Significa che la probabilità di avere tempi di servizio molto lunghi rispetto alla media non è trascurabile: la coda della distribuzione decade lentamente. La densità è definita dai due parametri positivi t0 (posizione) e α (forma), e il comportamento heavy tailed si ha per 1 < α ≤ 2. È la distribuzione associata al carattere auto-simile del traffico Ethernet reale documentato da Leland et al. nel 1994.
E[T′] = E[&thetas;²] / (2&thetas;̄). Con servizio esponenziale E[&thetas;²] = 2&thetas;̄², quindi E[T′] = &thetas;̄. È la conseguenza diretta dell'assenza di memoria: il tempo già trascorso non porta informazione, quindi il residuo è distribuito come un servizio appena iniziato. Con servizio deterministico invece E[T′] = &thetas;̄/2, cioè metà.
Lunghezza media: 0.4⋅64 + 0.6⋅1500 = 925.6 byte, cioè 7404.8 bit. Tempo medio di servizio: &thetas;̄ = 7404.8 / 10⋅10⁶ ≈ 740.5 µs. Utilizzazione: ρ = λ&thetas;̄ = 800 ⋅ 740.5⋅10−6 ≈ 0.59. Su un singolo servitore senza perdite l'utilizzazione coincide con il traffico offerto.
Perché se il limite non esiste, il sistema non ha un comportamento stabile nel tempo e non può essere studiato con i modelli del corso. È un avvertimento sostanziale: si sceglie una finestra temporale in cui il traffico sia effettivamente ergodico, si analizza il comportamento statistico in quella finestra, e si assume che il sistema si comporti sempre così, tipicamente scegliendo la condizione di caso peggiore (l'ora di punta).