Il sistema M/G/1 mantiene gli arrivi di Poisson ma abbandona l'ipotesi che il tempo di servizio sia senza memoria. È il passo che avvicina il modello alla realtà: i pacchetti di una rete non hanno lunghezza esponenziale, hanno lunghezze fissate dai protocolli, spesso concentrate su pochi valori tipici.
Il prezzo di questa generalizzazione è alto e va capito subito. Se il tempo di servizio non è senza memoria, allora per caratterizzare lo stato del sistema in un certo istante non basta più il numero k di utenti presenti: occorre conoscere anche il tempo di servizio già trascorso dell'utente attualmente in servizio, se presente. E con quell'informazione in più cade l'ipotesi di catena di Markov, insieme a tutta la macchina dei capitoli 4, 5 e 6.
Non si tratta di una difficoltà tecnica aggirabile: l'M/G/1 non è un processo di nascita e morte. Non esistono un diagramma degli stati con le frequenze λk e μk e una formula ricorsiva. Servono strumenti nuovi, e sono i due che occupano le prossime tre sezioni: un ragionamento diretto sul tempo di attesa, e una catena di Markov nascosta negli istanti di partenza.
Restano invece invariate le premesse strutturali: singolo servitore e coda infinita, quindi non si ha mai perdita, λs = λ e A0 = ρ = λ&thetas;̄. Il sistema è stabile solo se ρ < 1, e la probabilità di congestione, cioè di trovare il servitore occupato, vale πr = 1 − P0 = ρ per il risultato generale sui sistemi a singolo servitore dimostrato nel capitolo 6.
Il ragionamento che porta alla formula chiave è puramente contabile, e per questo è robusto. Si assumono disciplina di coda FIFO e valor medio e varianza del tempo di servizio finiti. Il generico utente che entra nel sistema deve attendere la somma di due contributi:
| Contributo | Che cos'è | Valor medio |
|---|---|---|
| T′ | il tempo di servizio residuo dell'utente attualmente in servizio, se presente | ρ ⋅ E[&thetas;²]/(2&thetas;̄) = λE[&thetas;²]/2 |
| T″ | la somma dei tempi di servizio di tutti gli altri utenti già presenti in coda | Aq&thetas;̄ = λη̄&thetas;̄ = ρη̄ |
Il primo termine mette insieme due risultati già noti: la probabilità che ci sia effettivamente qualcuno in servizio (che è ρ, dal capitolo 6) e il tempo di servizio residuo medio (che è E[&thetas;²]/(2&thetas;̄), dal capitolo 3). Il secondo usa il teorema di Little sulla sola coda, più l'ipotesi che il numero di utenti in coda e i loro tempi di servizio siano indipendenti tra loro.
Mettendo insieme i due contributi si ottiene un'equazione in cui η̄ compare da entrambe le parti:
η̄ = E[T′] + E[T″] = λE[&thetas;²]/2 + ρη̄
⇒ η̄(1 − ρ) = λE[&thetas;²]/2Risolvendo si ottiene la formula di Pollaczek–Khinchine, il risultato centrale del capitolo:
λ E[&thetas;²]
η̄ = ———————————
2 (1 − ρ)Da η̄ discendono al solito tutti gli altri indici, con il teorema di Little e la scomposizione del tempo di permanenza:
tempo medio di permanenza δ̄ = &thetas;̄ + η̄
numero medio di utenti in coda Aₜ = λη̄
traffico medio nel sistema A = ρ + AₜLa formula dice una cosa sola, ma fondamentale: a parità di tempo medio di servizio, il tempo di attesa dipende dalla variabilità del servizio attraverso E[&thetas;²]. Due interfacce di router con lo stesso throughput medio possono avere ritardi molto diversi se una trasporta pacchetti tutti uguali e l'altra un misto di pacchetti minuscoli e giganteschi. La media non basta: conta la coda della distribuzione.
Le slide precisano che la formula di Pollaczek–Khinchine è valida per qualunque disciplina di coda, non solo per la FIFO. L'ipotesi FIFO è servita per costruire il ragionamento, ma il risultato sui valori medi non ne dipende. È lo stesso fenomeno visto nel capitolo 6, e nella sezione 8 diventerà un teorema con un nome.
La formula di Pollaczek–Khinchine dà i valori medi, ma non le probabilità di stato. Per ottenere anche quelle esiste un secondo strumento, elegante e sorprendente: si rinuncia a guardare il sistema in un istante qualsiasi e lo si guarda solo negli istanti di partenza degli utenti serviti.
Si definiscono tn l'istante di partenza dell'n-esimo utente, kn = k(tn) il numero di utenti rimasti nel sistema dopo quella partenza, e an il numero di arrivi avvenuti durante il servizio dell'n-esimo utente. Vale allora una relazione di ricorrenza:
kₙ₊₁ = max(kₙ − 1, 0) + aₙ₊₁Lo stato in tn+1 dipende solo dallo stato in tn e dal numero di arrivi fra tn e tn+1: negli istanti di partenza il sistema torna a essere una catena di Markov, sia pure «nascosta». La ragione profonda è che in un istante di partenza non c'è nessun servizio in corso, quindi non c'è nessun tempo di servizio già trascorso da ricordare: l'informazione che mancava non serve più.
Le probabilità di stato all'equilibrio si ricavano da questa catena con l'uso delle trasformate. Il passaggio conclusivo è però il più importante:
Si dimostra che le probabilità di stato negli istanti di partenza sono uguali a quelle negli istanti di arrivo e, con arrivi di Poisson, a quelle in un qualsiasi istante.
La prima uguaglianza discende dal fatto che il sistema cambia stato di una unità alla volta: fra due passaggi consecutivi per il livello k ce n'è sempre uno in salita (un arrivo) e uno in discesa (una partenza). La seconda è ancora una volta PASTA. Il risultato è che la catena nascosta, definita su un sottoinsieme molto particolare di istanti, descrive in realtà il sistema in ogni istante.
Il modo migliore per capire la formula di Pollaczek–Khinchine è vederla degenerare nei casi particolari. Il capitolo 3 ci ha già consegnato i valori quadratici medi; basta sostituirli.
| Sistema | E[&thetas;²] | η̄ | Rapporto con M/M/1 |
|---|---|---|---|
M/M/1 |
2&thetas;̄² |
ρ&thetas;̄/(1−ρ) |
riferimento |
M/D/1 |
&thetas;̄² |
ρ&thetas;̄/(2(1−ρ)) |
la metà |
M/Er/1 |
(1+1/r)&thetas;̄² |
(1+1/r) ρ&thetas;̄/(2(1−ρ)) |
fra il deterministico e l'esponenziale |
M/G/1 con varianza σ² |
&thetas;̄² + σ² |
λ(&thetas;̄²+σ²)/(2(1−ρ)) |
cresce con la varianza |
Il caso M/M/1 restituisce esattamente la formula del capitolo 6: è la verifica di coerenza che il modello generale deve superare. Il caso M/D/1 è quello istruttivo: rendere il servizio perfettamente regolare dimezza il tempo di attesa, a parità di tutto il resto. È il guadagno che si ottiene, per esempio, uniformando la dimensione dei pacchetti.
La seconda metà del capitolo abbandona la FIFO. Il sistema M/G/1/PRIO riceve arrivi provenienti da R flussi separati, cioè da R classi di traffico, ciascuna con i propri parametri: λr, &thetas;̄r, E[&thetas;r²] e ρr = λr&thetas;̄r.
La disciplina di coda non è più FIFO ma la seguente:
Resta da decidere che cosa succeda quando un utente prioritario arriva mentre il servitore è occupato da uno meno prioritario. Le due scelte sono:
| Modalità | Comportamento |
|---|---|
| non-preemptive | il servitore completa il servizio in corso prima di servire l'utente prioritario |
| preemptive | il servitore interrompe il servizio in corso per servire immediatamente l'utente prioritario |
Nel mondo delle reti a pacchetto la modalità realistica è quasi sempre la non-preemptive: una volta che un'interfaccia ha cominciato a trasmettere un pacchetto sul mezzo fisico, interromperlo significherebbe sprecare tutti i bit già inviati. La preemptive è invece il modello giusto per risorse interrompibili senza perdita, come una CPU. Nel capitolo 4 abbiamo già incontrato un caso preemptive: l'operatore che interrompe la chiamata di tipo B per rispondere alla A.
Il ragionamento è lo stesso della sezione 2, ma con tre contributi invece di due, perché adesso può capitare di essere scavalcati mentre si aspetta. Il generico utente di classe r che entra nel sistema deve attendere:
| Contributo | Che cos'è | Valor medio |
|---|---|---|
| T′ | il tempo di servizio residuo dell'utente attualmente in servizio, se presente, di qualunque classe | &thetas;̄P = ½ ∑i=1R λiE[&thetas;i²] |
| Ti″ | la somma dei tempi di servizio degli utenti di classe i già presenti in coda, per ogni classe i ≤ r | ∑i≤r ρiη̄i |
| Ti‴ | la somma dei tempi di servizio degli utenti di classe i che arrivano mentre io aspetto, per ogni classe i < r | η̄r ∑i<r ρi |
Il terzo contributo è la novità, ed è la ragione per cui una classe poco prioritaria può soffrire molto: mentre aspetto, chi ha priorità più alta di me continua ad arrivare e mi passa davanti. Sommando i tre termini e riordinando si ottiene il tempo di attesa medio per un utente di classe r. Introducendo la notazione σr = ∑i=1r ρi (con σ0 = 0), il risultato si scrive in due forme equivalenti:
forma chiusa &thetas;̄ᵖ
η̄ᵣ = ———————————————————
(1 − σᵣ₋₁)(1 − σᵣ)
formula ricorsiva di Cobham &thetas;̄ᵖ + ∑ᵢ₋₁ᶜᵣ₋₁ ρᵢη̄ᵢ
η̄ᵣ = —————————————————————
1 − σᵣCon due sole classi le formule diventano immediate e sono quelle che compaiono nei compiti:
η̄₁ = &thetas;̄ᵖ / (1 − ρ₁)
η̄₂ = &thetas;̄ᵖ / [ (1 − ρ₁)(1 − ρ₁ − ρ₂) ]L'esempio con due classi di priorità mostrato a lezione porta a una conclusione operativa netta:
La priorità dà vantaggio efficace alla classe prioritaria e ha effetto limitato sul traffico a bassa priorità solo se il traffico prioritario rappresenta una bassa percentuale del totale. Se si dichiara prioritario metà del traffico, non si è dato la precedenza a nessuno: si è solo complicato lo scheduler.
Resta da capire quanto costa alle classi svantaggiate ciò che si regala a quelle prioritarie. La risposta è un teorema di conservazione, e la sua costruzione merita attenzione.
Si definisce funzione lavoro rimanente U(t) del servitore il tempo richiesto per smaltire il servizio degli utenti presenti nel sistema all'istante t. Essa è composta esattamente dai contributi già noti, ma stavolta estesi a tutte le classi:
E[U] = &thetas;̄ᵖ + ∑ᵢ₁ᶜᵛ ρᵢ η̄ᵢIl passaggio decisivo è il seguente: se il servitore è di tipo conservativo, cioè non altera il tempo di servizio di ciascun utente, allora U(t) è indipendente dalla disciplina di coda. Cambiare l'ordine in cui si servono gli utenti non cambia il lavoro totale da smaltire: cambia solo chi lo aspetta.
Nel caso FIFO, per la proprietà PASTA, il lavoro rimanente medio coincide con il tempo di attesa medio, che vale &thetas;̄P/(1 − ρ). Uguagliando le due espressioni si ottiene la legge di conservazione di Kleinrock:
ρ &thetas;̄ᵖ
∑ᵣ₁ᶜᵛ ρᵣ η̄ᵣ = —————— = costante
1 − ρÈ l'invarianza della somma pesata dei tempi medi di attesa delle varie classi al variare della politica di accodamento. Quantifica esattamente l'effetto che la riduzione del tempo medio di attesa di una classe di utenti ha su quello delle altre: ciò che si toglie a una classe si deve aggiungere alle altre, con pesi pari ai rispettivi ρr. Lo scheduling non crea capacità, la ridistribuisce.
La legge di Kleinrock è anche un ottimo strumento di verifica: dopo aver calcolato η̄1 e η̄2 con Cobham, controlla che ρ1η̄1 + ρ2η̄2 coincida con ρ&thetas;̄P/(1−ρ), cioè con ρη̄FIFO. Se il conto non torna, uno dei due valori è sbagliato.
Con la priorità preemptive i contributi all'attesa cambiano in un punto cruciale. Il generico utente di classe r deve attendere:
La differenza sta tutta nella clausola «solo se di classe i ≤ r»: se in servizio c'è un utente meno prioritario, non lo si aspetta affatto, lo si interrompe. Da questa modifica discende il risultato più importante della modalità preemptive:
La classe a priorità massima non subisce alcun effetto da parte delle altre classi:
η̄₁ = &thetas;̄ᵖ₁ / (1 − ρ₁) con &thetas;̄ᵖ₁ = λ₁E[&thetas;₁²]/2che è l'espressione di η̄ per un sistema M/G/1 soggetto al solo traffico di classe 1. La classe prioritaria vede il sistema come se fosse dedicato esclusivamente a lei.
È esattamente lo stesso fenomeno osservato nel capitolo 4 con l'esercizio dell'operatore: le chiamate di tipo A, potendo interrompere quelle di tipo B, vedevano un sistema a singolo servitore soggetto al solo traffico A, e la loro probabilità di blocco coincideva con B(1, A0A). Preemptive significa isolamento perfetto della classe più alta.
Per le classi meno prioritarie, invece, l'analisi si complica: l'effetto sul loro tempo di servizio dipende dalla modalità di ripresa (resume) del servizio interrotto. Se il servizio deve ricominciare da capo, o se la ripresa comporta un costo, il servitore non è più conservativo e la legge di conservazione di Kleinrock non si applica. In una rete a pacchetto è il caso tipico: un pacchetto la cui trasmissione viene interrotta va ritrasmesso per intero, e i bit già inviati sono lavoro perso.
Un protocollo di livello data link implementa un controllo di flusso stop-and-wait: il trasmettitore invia una trama alla volta e attende l'ACK prima della successiva. In condizioni normali l'ACK arriva dopo T = 2.5 ms dall'inizio dell'invio della trama. Se non arriva alcun ACK entro To = 3 ms, la trama si assume persa e viene ritrasmessa immediatamente. La probabilità di errore per trama è PF = 0.1, indipendente da trama a trama.
La parte istruttiva è che il tempo di servizio del sistema a coda non è la trasmissione di una trama, ma l'intera procedura di consegna con le sue ritrasmissioni. Con k errori:
&thetas;ₖ = k Tₒ + T (k tentativi falliti + uno riuscito)
pₖ = Pᴴᵏ (1 − Pᴴ) (probabilita di esattamente k errori)
&thetas;̄ = ∑ₖ &thetas;ₖ pₖ = T + Tₒ Pᴴ/(1 − Pᴴ) = 2.5 + 3⋅0.1/0.9 = 2.833 msLa condizione di stabilità ρ = λ&thetas;̄ < 1 impone allora λ < λM = 352.9 trame/s. Scegliendo λ = 0.8λM = 282 trame/s si ha ρ = 0.8, e il trasmettitore si può studiare come un sistema M/G/1. Il valore quadratico medio si calcola sommando la serie:
E[&thetas;²] = ∑ₖ &thetas;ₖ² pₖ = ∑ₖ (T + kTₒ)² Pᴴᵏ(1 − Pᴴ)
= (1 − Pᴴ) [ T²/(1−Pᴴ) + Tₒ² Pᴴ(1+Pᴴ)/(1−Pᴴ)³ + 2T Tₒ Pᴴ/(1−Pᴴ)² ]
= 9.14 ⋅ 10⁻⁶ s²
η̄ = λE[&thetas;²] / (2(1 − ρ)) = 6.44 msLe due serie usate nel calcolo sono quelle fornite nel testo dell'esercizio: ∑n n xn = x/(1−x)² e ∑n n²xn = x(1+x)/(1−x)³, entrambe per 0 ≤ x < 1.
Vale la pena notare che il tempo di attesa (6.44 ms) è più del doppio del tempo di servizio (2.83 ms), pur essendo ρ = 0.8. La ragione è la varianza: il tempo di servizio è una miscela di 2.5 ms, 5.5 ms, 8.5 ms, … e questa dispersione entra in E[&thetas;²]. È un caso concreto in cui la sola media avrebbe dato una risposta ottimistica e sbagliata.
Questo quesito viene dal terzo compito d'esempio ed è il modello tipico della prova scritta. Un router instrada pacchetti provenienti da un sistema di monitoraggio su un canale dedicato di capacità C = 128 kbit/s, con coda praticamente infinita. Arrivano due tipologie di pacchetti, entrambe di Poisson, entrambe con lunghezza esponenziale di media D = 64 byte, con λ1 = 30 pacchetti/s e λ2 = 180 pacchetti/s. I pacchetti di tipo 1 hanno priorità non-preemptive.
Passo 1 — tempo residuo medio. Poiché la distribuzione delle lunghezze è la stessa per le due classi, il tempo medio di trasmissione è comune:
&thetas;̄ = D/C = 64⋅8 / (128⋅10³) = 4 ms E[&thetas;²] = 2&thetas;̄²
&thetas;̄ᵖ = ½ ∑ᵢ λᵢE[&thetas;ᵢ²] = ½(λ₁+λ₂) 2&thetas;̄² = (30+180) ⋅ 16⋅10⁻⁶ = 3.36 msLa soluzione ufficiale mostra anche una via alternativa molto più rapida, che sfrutta l'assenza di memoria: essendo il tempo di trasmissione esponenziale, il tempo residuo medio di un pacchetto in servizio è pari all'intero &thetas;̄; moltiplicandolo per la probabilità che ci sia qualcuno in servizio, cioè 1 − P0 = ρ, si ottiene direttamente &thetas;̄P = ρ&thetas;̄ = 0.84 ⋅ 4 = 3.36 ms.
Passo 2 — ritardi in coda con Cobham.
ρ₁ = λ₁&thetas;̄ = 0.12 E ρ₂ = λ₂&thetas;̄ = 0.72 E ρ = 0.84
η̄₁ = &thetas;̄ᵖ/(1 − ρ₁) = 3.36/0.88 = 3.82 ms
η̄₂ = &thetas;̄ᵖ/[(1−ρ₁)(1−ρ₁−ρ₂)] = 3.36/(0.88⋅0.16) = 23.86 ms
FIFO senza priorità: η̄ = ρ&thetas;̄/(1−ρ) = 0.84⋅4/0.16 = 21 msIl commento della soluzione è la lezione da portare a casa: la bassa percentuale di traffico prioritario (circa il 14.3% del totale) fa sì che la disciplina a priorità abbia un effetto limitato sull'aumento del ritardo dei pacchetti meno prioritari (+2.86 ms rispetto alla FIFO), riducendo però significativamente il ritardo di quelli prioritari (−17.18 ms). Un ottimo affare, che sarebbe stato pessimo se le proporzioni fossero state invertite.
Passo 3 — priorità preemptive. Con la preemptive il traffico a bassa priorità non ha alcun effetto sulle prestazioni di quello prioritario, che quindi si comporta come se il sistema fosse soggetto al solo traffico di tipo 1:
η̄₁ = ρ₁&thetas;̄/(1 − ρ₁) = 0.12⋅4/0.88 = 0.55 msDa 21 ms (FIFO) a 3.82 ms (non-preemptive) a 0.55 ms (preemptive): tre discipline, un ordine di grandezza e mezzo di differenza, a parità assoluta di capacità installata.
Perché con tempo di servizio non senza memoria, per caratterizzare lo stato del sistema in un certo istante non basta il numero k di utenti presenti: occorre conoscere anche il tempo di servizio già trascorso dell'utente in servizio. Lo stato futuro dipende quindi da un'informazione che non è contenuta nel solo k, e cade l'ipotesi di Markov.
η̄ = λE[&thetas;²] / (2(1−ρ)). Si ricava osservando che chi arriva attende T′ (residuo del servizio in corso, di media λE[&thetas;²]/2) più T″ (somma dei servizi in coda, di media Aq&thetas;̄ = ρη̄). Da η̄ = λE[&thetas;²]/2 + ρη̄ si isola η̄. Vale per qualunque disciplina di coda, non solo FIFO.
Perché il contributo T′, cioè il tempo di servizio residuo dell'utente in servizio, vale E[&thetas;²]/(2&thetas;̄): campionando un istante a caso è più probabile cadere dentro un servizio lungo che dentro uno corto. A parità di media, un servizio molto variabile produce residui molto più lunghi, e quindi attese più lunghe.
Esattamente la metà. Per M/M/1 si ha E[&thetas;²] = 2&thetas;̄² e η̄ = ρ&thetas;̄/(1−ρ); per M/D/1 si ha E[&thetas;²] = &thetas;̄² e η̄ = ρ&thetas;̄/(2(1−ρ)). Rendere il servizio perfettamente regolare dimezza l'attesa, a parità di tempo medio di servizio e di carico.
È la catena che si ottiene osservando il sistema solo negli istanti di partenza. Detti kn il numero di utenti rimasti dopo la partenza dell'n-esimo e an gli arrivi durante il suo servizio, vale kn+1 = max(kn−1,0) + an+1: lo stato futuro dipende solo dal presente. Funziona perché in un istante di partenza non c'è alcun servizio in corso, quindi non c'è tempo trascorso da ricordare. Si dimostra poi che le probabilità di stato negli istanti di partenza sono uguali a quelle negli istanti di arrivo e, con arrivi di Poisson, a quelle in un istante qualsiasi.
Se un utente di classe i < r arriva mentre il servitore è occupato da un utente di classe r: con la non-preemptive il servitore completa il servizio in corso prima di servire l'utente prioritario; con la preemptive lo interrompe e serve subito il prioritario. Nelle reti a pacchetto la modalità realistica è la non-preemptive, perché interrompere una trasmissione già iniziata sul mezzo fisico sprecherebbe i bit già inviati.
1) T′, il tempo di servizio residuo dell'utente in servizio, di qualunque classe; 2) Ti″, i tempi di servizio degli utenti di classe i ≤ r già in coda; 3) Ti‴, i tempi di servizio degli utenti di classe i < r che arrivano mentre io aspetto. Il terzo è la novità rispetto alla FIFO ed è la ragione per cui una classe bassa può soffrire molto.
Forma chiusa: η̄r = &thetas;̄P / [(1−σr−1)(1−σr)], con σr = ∑i=1rρi. Forma ricorsiva: η̄r = [&thetas;̄P + ∑i<rρiη̄i] / (1−σr). Il termine &thetas;̄P = ½∑iλiE[&thetas;i²] è il tempo di servizio residuo medio, comune a tutte le classi.
∑rρrη̄r = ρ&thetas;̄P/(1−ρ) = costante: la somma pesata dei tempi medi di attesa delle varie classi è invariante al variare della politica di accodamento. Vale se il servitore è conservativo, cioè se non altera il tempo di servizio di ciascun utente; sotto questa ipotesi la funzione lavoro rimanente U(t) non dipende dalla disciplina di coda. Quantifica esattamente quanto costa alle altre classi ciò che si regala alla classe prioritaria.
Perché può interrompere qualunque servizio in corso di classe inferiore, e quindi non attende mai per colpa loro: né il residuo del servizio in corso, né gli utenti in coda, né quelli che arrivano dopo. Il suo tempo di attesa è η̄1 = &thetas;̄P1/(1−ρ1) con &thetas;̄P1 = λ1E[&thetas;1²]/2, che è l'espressione di un M/G/1 soggetto al solo traffico di classe 1: la classe prioritaria vede il sistema come se le fosse dedicato.
Perché l'effetto sul tempo di servizio delle classi meno prioritarie dipende dalla modalità di ripresa (resume) del servizio interrotto. Se riprendere costa, o se il servizio deve ricominciare da capo, il servitore non è più conservativo: altera il tempo di servizio dei singoli utenti, e quindi la funzione lavoro rimanente dipende dalla disciplina di coda. In una rete a pacchetto è il caso tipico, perché un pacchetto interrotto va ritrasmesso per intero.
ρ1 = 0.12, ρ2 = 0.72 e &thetas;̄P = 3.36 ms, quanto valgono i ritardi delle due classi e quello FIFO?η̄1 = 3.36/0.88 = 3.82 ms; η̄2 = 3.36/(0.88⋅0.16) = 23.86 ms; FIFO η̄ = ρ&thetas;̄/(1−ρ) = 21 ms. Verifica di Kleinrock: 0.12⋅3.82 + 0.72⋅23.86 ≈ 17.64 = 0.84⋅21. Il traffico prioritario è solo il 14.3% del totale, per cui guadagna 17.18 ms al prezzo di soli 2.86 ms in più per l'altra classe.
Non è la trasmissione di una singola trama, ma l'intera procedura di consegna, ritrasmissioni comprese: &thetas;k = kTo + T con probabilità pk = PFk(1−PF). Il tempo medio è &thetas;̄ = T + ToPF/(1−PF). Poiché questo tempo è una miscela di valori distanti fra loro, la sua varianza è alta e il tempo di attesa risultante può superare abbondantemente il doppio del tempo di servizio medio.