Sistemi di servizio orientati al ritardo

Prec Sezione 17.3: Sistema di servizio orientato alla perdita Su Capitolo 17: Sistema di servizio, teoria del trafficoe delle reti Sezione 17.5: Reti per trasmissione dati Segue

17.4 Sistemi di servizio orientati al ritardo↓

Mentre i sistemi orientati alla perdita rappresentano il modo di operare delle reti di telecomunicazione a commutazione di circuito, in cui ogni connessione impegna in modo esclusivo alcune risorse di rete, che una volta esaurite producono un rifiuto della richiesta di connessione, i sistemi orientati al ritardo sono rappresentativi di reti a commutazione di pacchetto↓, in cui i messaggi sono suddivisi in unità elementari (detti pacchetti, appunto) la cui ricezione non deve più avvenire in tempo reale, e che condividono le stesse risorse fisiche (degli organi di commutazione e di trasmissione) con i pacchetti di altre comunicazioni. Pertanto, l’invio di un pacchetto può essere ritardato se il sistema di servizio è in grado di gestire delle code di attesa↓, in cui accumulare le richieste che eccedono il numero di serventi a disposizione, e da cui prelevare (con ritardo) i pacchetti stessi non appena si rendano disponibili le risorse trasmissive necessarie.

In questo caso il grafico che mostra la ripartizione dei flussi di richieste si modifica come in figura, dove è evidenziato come la frequenza di richieste λ_o si suddivide tra la frequenza delle richieste perse λ_p, quelle servite con ritardo λ_sr, e quelle servite immediatamente λ_si, in funzione della probabilità di perdita P_p e di ritardo P_r. Nei termini di queste quantità, valgono le relazioni:

λ_p = P_pλ_o; λ_sr = P_r(1 − P_p)λ_o; λ_si = (1 − P_r)(1 − P_p)λ_o

Indicando con τ_S = (1)/(μ) il tempo medio di servizio di ogni richiesta, (che non comprende quindi il tempo di accodamento), si definisce, come già noto, una intensità di traffico offerto A_o = (λ_o)/(μ) = λ_oτ_S, che deve risultare

A_o = A_p + A_sr + A_si e quindi A_sr = (λ_sr)/(μ), A_si = (λ_si)/(μ)

Considerando il caso in cui la coda abbia una lunghezza finita e pari ad L, osserviamo che, a prima vista, anche le L richieste successive all’impegno di tutti gli M serventi sono accolte (e poste in coda), come se i serventi fossero divenuti M + L. In realtà l’analisi fornisce risultati differenti, in quanto le richieste accodate devono essere ancora servite, e quindi il calcolo della P_p non è una diretta estensione dei risultati ottenuti per i sistemi orientati alla perdita. E’ comunque abbastanza semplice verificare [862] [862] Se P_B è la probabilità di blocco derivante dalla disponibilità di M serventi, una frequenza di richieste pari a P_B⋅λ_o non può essere servita immediatamente; adottando una coda, la frequenza delle richieste non servite immediatamente P_B⋅λ_o è uguale a λ_o(P_p + P_r(1 − P_p)), ed eguagliando le due espressioni si ottiene P_p = (P_B − P_r)/(1 − P_r), che è sempre minore di P_B. che ora la P_p risulta inferiore alla P_B del caso senza coda, e pertanto l’intensità di traffico smaltito A_s = A_sr + A_si = (1 − P_p)A_o aumenta, a parità di offerta.

17.4.1 Risultato di Little↓

Si tratta di un risultato molto generale, valido per qualsiasi distribuzione dei tempi di interarrivo e di servizio, la cui applicazione può tornare utile nell’analisi, e che recita:

Il numero medio N di utenti contemporaneamente presenti in un sistema di servizio è pari al prodotto tra frequenza media di smaltimento delle richieste λ_s ed il tempo medio di permanenza τ_p dell’utente nel sistema

e quindi in definitiva N = λ_s⋅τ_p. Nell’applicazione al caso di servizi orientati alla perdita, si ha τ_p = τ_S, mentre nei servizi a coda risulta τ_p = τ_c + τ_S in cui τ_c rappresenta il tempo medio di coda.

17.4.2 Sistemi a coda infinita↓ ed a servente unico

Prima di fornire risultati più generali, svolgiamo l’analisi per questo caso particolare, in cui la frequenza di richieste perse λ_p è nulla, dato che una coda di lunghezza infinita le accoglie comunque tutte. Da un punto di vista statistico, un tale sistema è descritto

Sistema a coda infinita ed a servente unico

mediante il diagramma di nascita e morte riportato a fianco, in cui ogni stato S_k rappresenta k richieste nel sistema, di cui una sta ricevendo servizio e k − 1 sono accodate.

Per procedere nell’analisi, si applica lo stesso principio di equilibrio statistico già adottato a pag. 1↑ dove si asserisce che, esaurito un periodo transitorio iniziale, la frequenza media delle transizioni tra S_k e S_k + 1 deve eguagliare quella da S_k + 1 ad S_k. Indicando con p_k = Pr(S_k) la probabilità che il sistema contenga k richieste, l’equilibrio statistico si traduce nell’insieme di equazioni

(19.9) λ_op_k = μp_{k
+ 1} con k = 0, 1, 2, …, ∞

Infatti, in base alle stesse considerazioni svolte nella prima parte della nota 17.3.3↑ di pag. 1↑, λ_op_k è pari alla frequenza media (frazione di λ_o) con cui il numero di richieste accolte passa da k a k + 1; essendo il servente unico, la frequenza di servizio è sempre μ = (1)/(τ_S), indipendentemente dal numero di richieste accodate, e dunque μp_{k
+ 1} è proprio la frequenza media con cui il sistema passa da k + 1 a k richieste accolte.

La relazione (19.9↑) è di natura ricorsiva, e può esprimersi come

p_k = ⎛⎝(λ_o)/(μ)⎞⎠^kp₀ = A^k_op₀

Per determinare il valore p₀ = Pr(S₀), uguale alla probabilità che il sistema sia vuoto, ricordiamo [863] [863] Nella derivazione del risultato si fa uso della relazione ∑^∞_{k
= 0}α^k = (1)/(1 − α), nota con il nome di serie geometrica, e valida se α < 1, come infatti risulta nel nostro caso, in quanto necessariamente deve risultare A_o = (λ_o)/(μ) < 1; se il servente è unico infatti, una frequenza di arrivo maggiore di quella di servizio preclude ogni speranza di funzionamento, dato che evidentemente il sistema non ha modo di smaltire in tempo le richieste che si presentano. che deve risultare

1 = ^∞⎲⎳_{k
= 0}p_k = ^∞⎲⎳_k = 0p₀A^k_o = p₀(1)/(1 − A_o)

da cui otteniamo p₀ = 1 − A_o e dunque

p_k = (1 − A_o)A^k_o

che corrisponde ad una densità di probabilità esponenziale discreta.

Siamo ora in grado di determinare alcune grandezze di interesse:

Probabilità di ritardo↓ P_r: risulta pari alla probabilità che il sistema non sia vuoto, e cioè che ci sia già almeno una richiesta accolta, ed è pari a [864] [864] Ricordiamo che p₀ è la probabilità che il sistema sia vuoto, e dunque 1 − p₀ quella che non sia vuoto.

P_r = 1 − p_o = 1 − (1 − A_o) = A_o

Ricordiamo di aver già definito l’efficienza come il rapporto ρ = (A_s)/(M) tra il traffico smaltito ed il numero dei serventi; nel nostro caso M = 1 e A_s = A_o: dunque ρ = A_o. Pertanto, il risultato P_r = A_o = ρ indica come, al tendere ad 1 dell’efficienza, la probabilità di ritardo tenda anch’essa ad 1.

Lunghezza media di coda↓ indicata con L: risulta essere semplicemente il valore atteso del numero di richieste presenti nel sistema, ovvero [865] [865] si fa uso della relazione ∑^∞_k = 0kα^k = α∑^∞_{k
= 0}kα^k − 1 = α(∂)/(∂α)∑^∞_k = 0α^k = α(∂)/(∂α)(1)/(1 − α) = (α)/((1 − α)²)

L = E{k} = ^∞⎲⎳_{k = 0}kp_k = (1 − A_o)^∞⎲⎳_{k
= 0}kA^k_o = (A_o)/(1 − A_o)

da cui risulta che per A_o → 1 la coda tende ad una lunghezza infinita.

Tempo medio di permanenza indicato con τ_p, e scomponibile nella somma τ_p = τ_S + τ_c tra il tempo medio di servizio ed il tempo medio di coda. Possiamo applicare qui il risultato di Little N = λ_s⋅τ_p, che esprime la relazione tra numero medio N di richieste presenti, frequenza di smaltimento (qui pari a quella di offerta [866] [866] Non può essere λ_s > λ_o, perché si servirebbero più richieste di quante se ne presentano. Se fosse invece λ_s < λ_o, la coda crescerebbe inesorabilmente e sarebbe quindi inutile.), e tempo medio di permanenza; infatti accade che N = L, ed utilizzando il risultato L = (A_o)/(1 − A_o) si ottiene

τ_p = (N)/(λ_s) = (L)/(λ_o) = (A_o)/(1 − A_o)(1)/(λ_o) = (λ_o)/(μ)(1)/(λ_o)(1)/(1 − λ_o ⁄ μ) = (1)/(μ − λ_o)

da cui si osserva che, se la frequenza di offerta tende al valore della frequenza di servizio, il tempo medio di permanenza tende ad ∞.

Tempo medio di coda si calcola come

τ_c = τ_p − τ_S = (1)/(μ − λ_o) − (1)/(μ) = (μ − μ + λ_o)/(μ(μ − λ_o)) = (A_o)/(μ(1 − A_o)) = (1)/(μ)(ρ)/(1 − ρ) = τ_S(ρ)/(1 − ρ)

Questo risultato mostra che il tempo medio di coda è legato al tempo medio di servizio e all’efficienza di giunzione, confermando ancora i risultati per ρ → ∞.

La fig. 17.13↓ mostra l’andamento delle grandezze appena calcolate.

Figura 17.13 Grandezze di interesse per il sistema a coda infinita ed unico servente

17.4.3 Sistemi a coda finita↓ e con più serventi

Riportiamo solo i risultati, validi se entrambi i processi di ingresso e di servizio sono esponenziali con frequenza media λ_o e μ, la coda è lunga L, i serventi sono M e le sorgenti infinite.

Probabilità di k richieste nel sistema

p_k(A_o) = ⎧⎨⎩ (A^k_o)/(k!α(A_o)) 0 ≤ k ≤ M (A^k_o)/(M^{k
− M}M!α(A_o)) M ≤ k ≤ M + L

in cui α(A_o) = (1)/(p₀(A_o)) = ∑^M + L_{k
= 0}(A^k_o)/(k!) e A_o = (λ_o)/(μ). Si noti come per 0 ≤ k ≤ M ed L = 0 si ottenga lo stesso risultato già esposto per i sistemi orientati alla perdita, mentre per M = 1 ed L = ∞ ci si riconduca al caso precedentemente analizzato.

Probabilità di ritardo↓

P_r = ^{M + L}⎲⎳_k = Mp_k(A_o) = p_M(A_o)(1 − ρ^L + 1)/(1 − ρ) in cui ρ = (A_o)/(M)

Probabilità di perdita

P_p = p_{M
+ L}(A_o) = (A^{M
+ L}_o)/(M^LM!⋅α(A_o))

Tempo medio di coda↓

τ_c = τ_S(P_r − L⋅P_M + L(A_o))/(M − A_o)

La Figura 17.14↓ descrive la probabilità di perdita per un sistema a servente singolo (a sinistra) e con 10 serventi (a destra), in funzione dell’intensità di traffico offerto e della lunghezza di coda, così come risulta dalla applicazione delle formule riportate. Nel caso di trasmissione di pacchetti di lunghezza fissa, per i quali il tempo di servizio è fisso e non a distribuzione esponenziale [867] [867] In una trasmissione a pacchetto, operata a frequenza binaria f_b e con pacchetti di lunghezza media L_p bit, il tempo medio di servizio per un singolo pacchetto è pari a quello medio necessario alla sua trasmissione, e cioè τ_S = L_p ⁄ f_b., i risultati ottenuti costituiscono una stima conservativa delle prestazioni del sistema (che potranno cioè essere migliori). L’analisi delle curve permette di valutare con esattezza il vantaggio dell’uso di una coda (a spese del tempo di ritardo). Infatti, aumentando il numero di posizioni di coda si mantiene una probabilità di blocco accettabile anche per traffico intenso.

Figura 17.14 Probabilità di perdita per un sistema a coda finita con uno o dieci serventi

Ad esempio, per P_b = 1% ed M = 1, osserviamo che una coda con L = 20 posizioni gestisce un traffico di A_o = 0.83 Erlang, contro gli A_o = 0.11 Erlang del caso senza coda. Ciò corrisponde ad un aumento dell’efficienza di (0.83)/(0.11) = 7.54 volte. D’altra parte ora il tempo medio di coda (calcolato in modo conservativo applicando la relazione per coda infinita) è τ_c = τ_S(ρ)/(1 − ρ) = (0.83)/(1 − 0.83)τ_S = 4.9τ_S, ed è quindi aumentato (rispetto a τ_S) di quasi 5 volte.

Esercizio Un nodo di una rete per dati effettua la multiplazione di pacchetti di dimensione media di 8 KByte [868] [868] 1 byte = 8 bit, 1 K = 2¹⁰ = 1024. Il “K” in questione è “un K informatico”. Nel caso invece in cui ci si riferisca ad una velocità di trasmissione, il prefisso K torna a valere 10³ = 1000. su collegamenti con velocità binaria f_b = 100 Mbps [869] [869] In virtù di quanto esposto alla nota precedente, in questo caso 1M = 10⁶ = 1000000.

1) Determinare il tempo medio di servizio di ogni singolo pacchetto;

2) determinare il tempo medio di interarrivo τ_a tra pacchetti corrispondente ad un traffico di ingresso di 1200 pacchetti/secondo, e l’associata intensità A_o;

3) assumendo che la dimensione dei pacchetti sia una v.a. con densità esponenziale negativa, così come il tempo di interarrivo tra pacchetti, e che la memoria del multiplatore sia così grande da approssimare le condizioni di coda infinita, determinare il ritardo medio di un pacchetto, ossia il tempo medio trascorso tra quando un pacchetto si presenta in ingresso al nodo e quando ne esce;

4) calcolare la quantità di memoria necessaria ad ospitare i dati che si accumulano in un intervallo temporale pari al ritardo medio, considerando pacchetti di lunghezza fissa e pari alla media.

Risposte

1) Il tempo medio di servizio di un pacchetto è pari al tempo occorrente per trasmetterlo: τ_S = (1)/(μ) = durata di un bit⋅(bit)/(pacchetto) = (1)/(10⁸)⎡⎣(secondi)/(bit)⎤⎦⋅1024⎡⎣(byte)/(pacchetto)⎤⎦⋅8⎡⎣(bit)/(byte)⎤⎦≃655 μsec;

2) τ_a = (1)/(λ) = (1)/(1200) = 833 μsec; A_o = (λ)/(μ) = 1200⋅655⋅10^− 6 = 0.786 Erlang;

3) Le condizioni poste corrispondono a quelle di traffico poissoniano e sistema a singolo servente e coda infinita, per il quale la teoria fornisce per il tempo di permanenza il risultato τ_p = (1)/(μ − λ_o) = (1)/((10⁶)/(655) − (10⁶)/(833)) = (1)/(326)≃3 msec;

4) La memoria necessaria è pari al prodotto tra il tempo medio di permanenza ed il numero di bit che si accumulano in quel periodo, ovvero 3⋅10^− 3[sec]⋅1200⎡⎣(pacch)/(sec)⎤⎦⋅1024⎡⎣(byte)/(pacch)⎤⎦≃3.7 Kbyte.

Prec Sezione 17.3: Sistema di servizio orientato alla perdita Su Capitolo 17: Sistema di servizio, teoria del trafficoe delle reti Sezione 17.5: Reti per trasmissione dati Segue