|
==Descrizione==
[[File:Mminfinity-statespace.svg|thumb|upright=1.4|[[Catene di Markov]] per sistemi a coda con stati, transizione di stati e relative probabilità, usata per la modellazione dei sistemi a coda]] ▼=== Notazione di Kendall ===
[[File:Exponential_pdf.svg|thumb|[[Distribuzione esponenziale|Distribuzione esponenziale negativa]]]]
Nel [[1953]], [[David George Kendall]] introdusse la notazione '''A/B/C''', successivamente estesa come '''1/2/3/4/5/6''' al fine di fornire una descrizione immediata del modello del sistema a code: ▼[[File:Degenerate_distribution_PMF.png|thumb|[[Distribuzione degenere]]]]
[[File:Gamma_distribution_pdf.svg|thumb|[[variabile casuale Erlanghiana|Distribuzione di Erlang]]]]
▲Nel [[1953]], [[David George Kendall]] introdusse la notazione '''A/B/C ''', successivamente estesa come '''1/2/3/4/5/6 ''' al fine di fornire una descrizione immediata del modello del sistema a code:
# Un codice che descrive la distribuzione di probabilità dei tempi di arrivo dei ''jobs'' nel sistema; i codici più usati sono:
#* '''"M''' " per "di Markov", implicante una [[variabile casuale esponenziale negativa|distribuzione esponenziale negativa]] unilatera per i tempi di servizio o tra gli arrivi: ciò implica l'[[mancanza di memoria|assenza di memoria]] di questi ultimi;
#* '''"D'''" per [[variabile casuale degenere|distribuzione "degenere"]] o "deterministica" dei tempi di servizio;
#* '''"E<math>_{k}_k</math>'''" per una [[variabile casuale Erlanghiana|distribuzione di Erlang]] con <math>k</math> come parametro di forma;
#* '''"G'''" per una distribuzione "Generalegenerale".
# Un codice che rappresenta la distribuzione di probabilità dei tempi di servizio dei ''jobs'', usando gli stessi simboli precedenti.
# Il numero di canali di servizio, detti anche ''serventi'', o ''server'' (ad esempio gli sportelli alla posta).
# Le dimensioni massime del sistema, che corrisponde alla somma tra i ''jobs'' in coda e i ''jobs'' nei canali di servizio; quando il massimo viene raggiunto ulteriori arrivi vengono rifiutati. Se non indicata la dimensione si intende infinita.
# Le dimensioni della popolazione da cui possono arrivare i clienti; questo limita il ritmo di arrivi, tanti più ''jobs'' sono presenti nella coda tanti meno ne sono disponibili per entrare nel sistema. Se non indicata la dimensione si intende infinita.
# L'ordine con il quale sono serviti i ''jobs'' nella coda (per default è FIFO):
#* First Come First Served ('''FCFS''') (o First In First Out - [[FIFO]]) (il primo che arriva viene servito per primo);
#* Last Come First Served ('''LCFS''') (o Last In First Out - [[LIFO]]) (l'ultimo che arriva viene servito per primo);
#* Service In Random Order ('''SIRO''') (servizio in ordine casuale);
#* PRI (esiste un sistema di selezione degli utenti a priorità (un esempio è il pronto soccorso, con i codici bianco, verde e rosso).
I modelli più studiati sono i sistemi M/M/s<math>S</math>/<math>K</math>, con s<math>S</math> e k<math>K</math> che possono assumere diversi valori (il modello più semplice è l'[[Coda M/M/1|M/M/1]], con un servente e a capacità illimitata): questo perché la distribuzione esponenziale degli intertempi di arrivo e di servizio permette di studiare i sistemi a coda come dei [[processo di nascita e morte|processi di nascita e morte]].
=== Sistemi a coda e Teoriateoria del traffico ===
{{vedi anche|Traffico (telecomunicazioni)}}
[[File:FIFO-LIFO.svg|thumb|Confronto tra tecnica FIFO e LIFO.]]
I Sistemi a Coda sono modellizzabili tramite [[processo markoviano|catene di Markov]] tempo continue ovvero con [[sistema dinamico|sistemi dinamici]] caratterizzati da N Stati, Probabilità di Stato pari a P(Ni) e Probabilità di Transizione da uno stato ad un altro pari al prodotto tra la Frequenza di Transizione f e l'intervallo di tempo dt, dipendente solo dallo stato presente del sistema e non da quelli precedenti (sistema senza memoria). Lo stato rappresenta la situazione in cui si trova il sistema rispetto a variabili prese come riferimento (in linea di massima non univoche) e l'evoluzione del sistema è mappata con una sequenza di salti fra gli stati stessi. Note le frequenze di transizione, ovvero la probabilità di transizione di stato, è possibile derivare le probabilità di stato P(Si) risolvendo la catena di Markov; dalla conoscenza di queste probabilità si possono poi derivare i parametri prestazionali di interesse quali il traffico smaltito, la probabilità di rifiuto, il tempo di coda, ecc… ▼▲[[File:Mminfinity-statespace.svg|thumb|upright=1. 40|[[Catene di Markov]] per sistemi a coda con stati, transizione di stati e relative probabilità, usata per la modellazione dei sistemi a coda]]
▲I Sistemisistemi a Codacoda sono modellizzabili tramite [[processo markoviano|catene di Markov]] a tempo continuecontinuo ovveroossia con [[sistema dinamico|sistemi dinamici]] caratterizzati da <math>N </math> Statistati, Probabilitàprobabilità di Stato pari astato <math>P( NiN_i) </math> e Probabilità[[probabilità di Transizionetransizione]] da uno stato ada un altro pariuguale al prodotto tra la Frequenzafrequenza di Transizionetransizione <math>f </math> e l'intervallo di tempo <math>dt, </math> dipendente solo dallo stato presente del sistema e non da quelli precedenti (sistema senza memoria). Lo stato rappresenta la situazione in cui si trova il sistema rispetto a variabili prese come riferimento (in linea di massima non univoche) e l'evoluzione del sistema è mappata con una sequenza di salti fra gli stati stessi. Note le frequenze di transizione, ovveroossia la probabilità di transizione di stato, è possibile derivare le probabilità di stato <math>P( SiS_i) </math> risolvendo la catena di Markov; dalla conoscenza di queste probabilità si possono poi derivare i parametri prestazionali di interesse quali il traffico smaltito, la probabilità di rifiuto, il tempo di coda, ecc…
Definendo il flusso proveniente dallo stato <math>i</math>-esimo verso lo stato <math>k</math>-esimo come il prodotto <math>P(SkS_k)*qk\cdot q_k, i</math> tra la probabilità di stato in <math>k</math> e la frequenza di transizione verso lo stato <math>k,</math> per il calcolo della probabilità di stato si utilizza la condizione espressa dalla [[legge di conservazione]] dei flussi la quale afferma che la somma dei flussi entranti è uguale alla somma dei flussi uscenti da uno stato. Applicando tale principio ad ogni stato si ottiene un sistema di <math>S</math> equazioni in <math>S</math> incognite (le probabilità di stato) tante quante gli stati <math>S;</math> le equazioni non sono tutte indipendenti tra loro, quindi la soluzione del sistema è impossibile (determinante nullo) a meno di sostituire un'equazione con la somma delle probabilità degli stati pari ad uno.
Applicando tale principio ad ogni stato si ottiene un sistema di S equazioni in S incognite (le probabilità di stato) tante quante gli stati S; le equazioni non sono tutte indipendenti tra loro, quindi la soluzione del sistema è impossibile (determinante nullo) a meno di sostituire un'equazione con la somma delle probabilità degli stati pari ad uno.
Un tipo di Catenecatene di Markov sono le Catenecatene di Nascitanascita e Mortemorte dove sono ammesse transizioni solo tra strati '"adiacenti'" e per i quali è identificabile una linea di taglio di flusso. Un sistema a coda è detto Markoviano se è modellabile tramite una Catenacatena di Markov di Nascitanascita e Mortemorte con processo di arrivo e di servizio di tipo [[esponenziale]] negativo di parametri λ (nascita) e υ (morte) e valori attesi corrispondentemente pari a 1/λ e 1/υ.
In un sistema acon <math>S</math> Serventiserventi diventa fondamentale un parametro prestazionale detto Probabilitàprobabilità di Bloccoblocco, che dipende dal numero <math>S</math> di Serventiserventi e dal Trafficotraffico Offertoofferto Ao<math>A</math> in ingresso. Tale parametro si calcola facendo riferimento alla [[formula di Erlang B]] i cui valori, per <math>S</math> e <math>A</math> fissati, sono espressi in forma tabulata. Altrettanto di interesse è la probabilità di attesa in coda espressa in funzione del numero di serventi e del traffico offerto attraverso la [[formula di Erlang C]]. In una [[rete di telecomunicazione]] i sistemi a coda e i relativi problemi di gestione del traffico sono presenti all'interno dello ''stack'' protocollare dei sistemi di elaborazione, trasmissione e ricezione del flusso informativo ovveroossia i terminali [[host]] e i sottosistemi interni di commutazione ([[router]]) e più in generale in tutti gli [[apparato di rete|apparati di rete]] che presentano del traffico in ingresso.
== Voci correlate ==
== Altri progetti ==
{{interprogetto|preposizione=sulla}}
== Collegamenti esterni ==
| 