1

Aulas 5 & 66.263/16.37

Introdução a Teoria das Filas

Eytan ModianoMIT, LIDS

2

3

Sistemas de Filas

• Usados para analise de desempenho de redes.

• Em redes a pacote, eventos são aleatórios,– Chegada de pacotes aleatória,– Comprimento dos pacotes aleatório.

• Enquanto que na camada física estamos interessados com taxa de erro por bit, na camada de rede nosso interesse são os atrasos.– Quanto tempo um pacote gasta esperando em uma fila?– Qual é o tamanho dos buffers?

• Em redes comutadas a circuito queremos determinar a probabilidade de bloqueio de chamada.– Quantos circuitos precisamos para limitar a probabilidade de

bloqueio?

4

Eventos Aleatórios

• Taxa de chegada– Pacotes chegam de acordo com um processo aleatório.– Tipicamente o processo de chegada é modelado como Poisson.

• O processo de Poisson– Taxa de chegada de λ pacotes por segundo.– Sobre um pequeno intervalo δ.

• P(exatamente uma chegada) = λδ + ο(δ)

• P(0 chegadas) = 1 -λδ + ο(δ)

• P(mais de que uma chegada) = 0(δ)

• Onde 0(δ)/ δ −> 0 δ −> 0.– Pode ser mostrado que:

( )!

)int(n

eTervalTnnarrivalsiPTn λλ −

=

5

The Poisson Process

( )!

)int(n

eTervalTnnarrivalsiPTn λλ −

=

• n =número de chegadas no intervalo T

• Pode ser mostrado que,E[n] = λTE[n2] = λT +(λT)2

σ2= E[(n-E[n])2] = E[n2]-E[n]2 = λT

6

Tempos de Inter-Chegada

• Tempo entre chegadas (IA)P(IA <= t) = 1 -P(IA > t)= 1 -P(0 chegada no tempo t)= 1 -e-λt

• Isto é conhecido como distribuição exponencial:– Função de Distribuição Acumulada das Inter-chegadas

(CDF)= FIA(t) = 1 -e-λt

– Função Densidade de Probabilidade das Inter-chegadas(PDF) = d/dt FIA(t) = λe-λt

• A distribuição exponencial é freqüentemente usada para modelar os tempos de serviço (ou seja, a distribuição dos comprimentos dos pacotes).

7

Propriedade de Markov(Sem memória - Memoryless)

• Prova

• História anterior não ajuda em predizer o futuro!• A distribuição do tempo até a próxima chegada é independente de quando

a última chegada ocorreu!

)()|( 00 tTPtTttTP ≤=>+≤

)()()|(

0

0000 tTP

ttTtPtTttTP>

+≤<=>+≤

)(

)()(1

0

00

00

0

0

0

0

t

ttt

tt

tt

t

t

t

tt

eee

e

e

dte

dte

λ

λλ

λ

λ

λ

λ

λ

λ

−

−+−

∞−

+−

∞−

+−

+−=

−

−=

∫

∫

)(1 tTPe t ≤=− −λ

8

Exemplo

• Suponha que um trem chegue a uma estação de acordo com um processo de Poisson com tempo de inter-chegada médio igual a 20 minutos.

• Quando um passageiro chega na estação o tempo médio de espera para a próxima chegada é de 20 minutos, – Não importa quando o trem anterior chegou.

• O tempo médio decorrido desde a última saída é 20 minutos!• Paradoxo: Se uma média de 20 minutos passa desde a chegada do

último trem e uma média de 20 minutos é necessária para que chegue o próximo trem, então teremos um intervalo de 40 minutos entre trens.– Mas supomos uma média de inter-chegadas de 20 minutos! – O que acontece?

9

Propriedades do Processo de Poisson

• Propriedade de Agregação

• Sejam A1, A2, … Ak processos de Poisson independentes com taxas λ1, λ2, … λk

A = ∑Ai é também Poisson se a taxa = ∑λi

• Propriedade da divisão– Suponha que cada chegada é aleatoriamente roteada com

probabilidade P para o fluxo 1 e ( 1-P) para o fluxo 2.– Fluxos 1 e 2 são Poisson se as taxas são Pλ e (1-P)λ respectivamente.

10

Modelos de Filas - Clientes Fila /Buffer

• Modelo para:– Clientes em fila de espera;– Linha de montagem;– Pacotes em uma rede (linha de transmissão).

• Queremos saber:– Número médio de clientes no sistema;– Atraso médio experimentado por um cliente.

• Quantidades obtidas em termos de:– Taxa de chegada dos clientes (número médio de clientes por unidade

de tempo);– Taxa de Serviço do servidor (número médio de clientes que o servidor

pode servir por unidade de tempo).

11

Teorema de Little• λ pacotes por segundo

• N =número médio de pacotes no sistema• T = tempo médio de um pacote no interior do sistema• λ =taxa de chegada dos pacotes ao sistema (não necessariamente

Poisson )• Teorema de Little: N = λT

– Pode ser aplicado no sistema inteiro ou em partes dele.– Sistema carregado → longos atrasos.

• Em dia de chuva as pessoas dirigem mais devagar e as ruas se tornam mais congestionadas!

12

Prova do Teorema de Little

• α(t) =número de chegadas no instante t • β(t) = número de saídas no instante t• ti = instante de chegada do i-ésimo usuário • Ti = tempo que o i-ésimo cliente fica no sistema• N(t) = número de clientes dentro do sistema no instante t = α(t) -β(t)• Prova similar ao “non first-come-first-serve”

13

Prova do Teorema de Little

= número médio de usuários na fila ao longo do tempo(média temporal)

- N = Limitt→∞ Nt = estado estacionário da média temporal

- λt =α(t)/ t, λ= Limitt→∞λt = taxa de chegada

= atraso médio no sistema ao longo do tempo, T=Limitt →∞ Tt

Suponha que os limites acima existam , suponha que o sistema é ergodigo.

ττ dNt

Nt

t ∫=0

)(1

)(

)(

0

t

Tt

i

ii

t α

α

∑=

tT

NtttNt

i it∑==⇒−=

)(

1)()()(α

βα

tT

Nt

i it∑=

∞→=)(

1limα

∑∑=

=∞→ =⇒=

)(

1

)(

1 )()(

lim t

i i

t

i it TtT

tT

T αα

αα

Tt

Ttt

tT

Nt

i it

i i λα

ααα

=

== ∑∑ ==

)()(

)(

1

)(

1

14

Aplicação do Teorema de Little

• O teorema pode ser aplicado para a maioria dos sistemas ou em partes deles.

• Exemplo:

1) O transmissor: DTP = tempo de transmissão do pacote .– Número médio de pacotes no transmissor = λDTP = ρ = utilização

do enlace.2) A linha de transmissão: Dp = atraso de propagação.

– Número médio de pacotes que estão sendo transportados (ainda não chegaram ao destino) = λDp.

3)O buffer: Dq = atraso médio de enfileiramento.Transmissor + buffer

• Número médio de pacotes = ρ + Nq

15

Aplicação Para Sistemas Mais Complexos

• Temos uma rede complexa com diferentes fluxos que a atravessam interagindo arbitrariamente.

• Para cada fluxo i individual, Little afirma que Ni = λiTi.• Para a coleção dos fluxos, Little diz que N = λT onde:

N = ∑iNi & λ = ∑i λi i= k

• A partir do Teorema de Little: ∑∑

=

=

=

== ki

i i

ki

i iiTT1

1

λ

λ

16

Filas Com Um Único Servidor - λ pacotes por segundo

Taxa de entrada

Taxa de saída

• M/M/1 µ pacotes por Segundo Tempo de serviço = 1/µ.– Chegadas de Poisson , tempo de serviço exponencial.

• M/G/1– Chegadas de Poisson , tempo de serviço genérico.

• M/D/1– Chegadas de Poisson , tempo de serviço determinístico (fixo).

17

Cadeia de Markov Para o Sistema M/M/1

• Estado k ⇒ k clientes no sistema.• P(I,j) =probabilidade de transição do estado I para o estado j.

– Como δ⇒ 0, obtemos:P(0,0) = 1 - λδ, P(j, j+1) = λδP(j, j) = 1 - λδ − µδ P(j, j-1) = µδ

P(I,j) = 0 para todos os outros valores def I, j.

• Cadeia de Nascimento-Morte: Transições existem somente entre estados adjacentes T.– λδ, µδ são as taxas dos fluxos entre estados.

18

Análise no Equilíbrio

• Queremos obter P(n) = a probabilidade de estar no estado n.• No equilíbrio λP(n) = µP(n+1) para todo n.

– Equações de balanceamento local entre dois estados (n, n+1).– P(n+1) = (λ/µ)P(n) = ρP(n), ρ = λ/µ.

• Então segue que:P(n) = ρn P(0) ∑i ∞= 0 P(n) = 1

• Agora pelo axioma da probabilidade:

1)(0

=∑∞

=inP

11

)0()0(0

=−

=⇒∑∞

= ρρ PP

in

ρ−=⇒ 1)0(P

)1()( ρρ −= nnP

19

Tamanho Médio da Fila

• N = Número médio de clientes no sistema. • Tempo médio que um cliente fica no sistema pode ser obtido a partir

da formula de Little (N=λT => T = N/λ). • T inclui o atraso na fila mais o tempo de serviço (service time = DTP =

1/µ).– W = Tempo gasto na fila = T -1/µ

• Finalmente, o número médio de clientes no buffer pode ser obtido a partir da formula de Little.

ρρρρ−

=−== ∑∑∞

=

∞

= 1)1()(

00 n

n

nnnnPN

λµλ

µλµλ

ρρ

−=

−=

−=

11N

ρµλ

λµλλ −=−−

== NWNQ

20

Exemplo (restaurante de fast food)

• Clientes chegam ao restaurante fast food a uma taxa de 100 por hora e leva 30 segundos para cada cliente ser servido.

• Quanto tempo os clientes ficam no restaurante?– Taxa de serviço = µ = 60/0,5=120 clientes por hora.– T = 1/µ−λ = 1/(120-100) = 1/20 horas = 3 minutos.

• Quanto tempo ficam esperando na fila?– W = T -1/µ = 2,5 minutos

• Quantos clientes estarão aguardando no restaurante?– N = λT= 5

• Qual é utilização do servidor?– ρ = λ/µ = 5/6

21

Comutação a Pacote vs Comutação a Circuito 1

Multiplexação por divisão de tempo. Cada usuário pode enviar com µ/N pacotes por segundo e tem um taxa de chegada de λ/N pacotes por segundo.

Multiplexador Estatístico

22

Circuito (tdm/fdm) vs Comutação a Pacotes

Multiplexação

por divisão de

Tempo de 20 fontes

MultiplexaçãoEstatística ideal (fila M/D/1)

23

Sistemas de M servidores: M/M/m buffer

(taxa de entrada)

• Taxa de decida é proporcional ao número de servidores em uso. • Semelhante à Cadeia de Markov:

24

M/M/m Fila• Equações de Balanceamento:

→ →

• Resolvendo para P(0):

T=W+1/µ, N=λT=λ/µ+NQ

)()1( nPnnP µλ =− mn ≤)()1( nPmnP µλ =− mn >

=!/))(0(

!/))(0()(

mmPnmP

nPnn

n

ρ

ρmnmn

>≤ 1≤=

µλρ

m

11

0 )1(!)(

!)()0(

−−

=

−

+= ∑m

n

mn

mm

nmP

ρρρ

)1(!))(0()(ρρ

−== ∑

∞=

= mmPnPP

mn

mnQ

−

=

=+=

+∞=

=

∞=

=∑∑ ρ

ρρ1!

)0()(00

Q

nmmn

n

n

nQ P

mmnPmnnPN

λQN

W =

25

Aplicações da M/M/m • Banco com m terminais.• Rede com linhas de transmissão paralelas.

• Quando o sistema não é muito carregado, PQ~0, e o servidor único é m vezes mais veloz;

• Quando o sistema é bastante carregado, o atraso de enfileiramento domina e os sistemas são a grosso modo os mesmos.

26

M/M/Infinita• Servidores sem limite => clientes não tem atraso de fila.• O número de clientes no sistema representa o número de clientes que estão

sendo servidos.

• N = Número médio no sistema =λ/µ, T = N /λ=1/ µ= tempo de serviço.

!)/)(0()(1

nPnP

n

nµλ

=⇒>∀)()1( nPnnP µλ =−

[ ] µλµλ /1

1!/)/(1)0( −−∞

==+= ∑ enP

nn

!/)/()( / nenP n µλµλ −= ⇒ Distribuição de Poisson!

27

Probabilidade de Bloqueio• Uma rede comutada a circuito pode ser vista como um sistema de filas com

múltiplos servidores.– As chamadas são bloqueadas quando não há servidores disponíveis -

“sinal de ocupado”;– Para redes comutadas a circuito estamos interessados na probabilidade de

bloqueio.• Sistema M/M/m/m

– m servidores => m circuitos;– O último m indica que o sistema não pode atender mais que m usuários.

• Formula Erlang B – Fornece a probabilidade de um usuário achar todos os circuitos ocupados;– É válida para chegadas de chamadas com distribuição genérica (muito

embora provamos aqui somente para o caso de Markov).

∑ =

= m

nn

m

Bn

mP0

!/)/(!/)/(

µλµλ

28

Sistema M/M/m/m: Formula de Erlang B

!)/)(0()(,1

nPnPmn

nµλ=⇒≤≤)()1( nPnnP µλ =−

[ ]∑ ==

m

nn nP

0!/)/()0( µλ

∑ =

=== m

mn

m

Bn

mmPBlockingPP0

!/)/(!/)/()()(

µλµλ

29

Formula Erlang B• Carga no sistema é geralmente expressa em Erlangs

– A = λ/µ = (taxa de chegada)*(duração média da chamada) = carga média PB = (mA)m/m!

– Formula independe de λ e µ depende somente de – sua razão ∑n= 0( A)n / n!

• Usado para dimensionar linhas de transmissão – Quantos circuitos um satélite precisa suportar?– O número de circuitos é uma função da probabilidade de bloqueio que pode ser

tolerada. Sistemas são projetados para uma determinada carga e probabilidade de bloqueio (tipicamente pequena).

• Exemplo– Taxa de chegada = 4 chamadas por minuto, 3 minutos em média por chamada =>

A=12.– Quantos circuitos são necessários? Depende da probabilidade de bloqueio tolerada.

∑ =

= m

nn

m

Bna

mAP0

!/)(!/)(

30%7

8%15

1%20

PBCircuitos

30

Cadeia de Markov Multidimensional• K classes de clientes

– Classe j: taxa de chegada λj; taxa de serviço µj.

• Estado do sistema: n = (n1, n2, …, nk); nj = número de clientes da classe j no sistema.

• Se equações de balanceamento são válidas para estados adjacentes, então a solução em formato de produto existe, onde:– P(n,.n2, …, nk) = P1(n1)*P2(n2)*…*Pk(nk)

• Exemplo: K sistemas independentes M/M/1 , ρi =λi / µi

• O mesmo é válido para outras cadeias de nascimento-morte independentes,– Por ex.: M.M/m, M/M/Inf, M/M/m/m.

)1()( iniiii nP ρρ −=

31

Truncamento• Eliminação de alguns estados.

– Por ex., para a fila K M/M/1, elimina-se todos os estados onde n1+n2+…+nk > K1 (alguma constante).

• A cadeia resultante deve permanecer irredutível.– Todos os estados devem se comunicar.

Forma produto para distribuição estacionária do sistema truncado.

• Por ex.: K filas independentes M/M/1.

• Por ex.: K filas independentes M/M/inf.

– G é uma constante de normalização que torna P(n) uma distribuição.– S é o conjunto de estados no sistema truncado.

GnnnP

knk

nn

kρρρ ...),...,,(

2121

21 = ∑∈Sn

nk

nn kG ρρρ ...2121

Gnnn k )!/)...(!/)(!/(),...nn ,P(n

k21 nk2

n21

n1

k21ρρρ

=)!/...()!/)(!/( 2211

21k

nk

Sn

nn nnnG kρρρ∑∈

=

32

Exemplo• Duas classes de sessões num sistema comutado a circuito.

– M canais de igual capacidade. • Dois tipos de sessões:

Tipo 1: taxa de chegada λ1e taxa de serviço µ1Tipo 2: taxa de chegada λ2 e taxa de serviço µ2• O sistema pode suportar até M sessões de cada classe.

– Se µ1= µ2, considere o sistema como uma fila M/M/m/m com taxa de chegada λ1+ λ2.

– Quando µ1=! µ2 é necessário conhecer o número de chamadas que estão sendo atendidas para cada tipo de sessão.

– Cadeia de Markov a duas dimensões = (n1, n2).– Queremos P(n1, n2): n1+n2 <=m.

• Pode ser visto como filas truncadas M/M/Inf .– Observe que as taxas de transição na fila M/M/Inf são as mesmas que aquelas na

fila truncada M/M/m/m.

– Observe que na somatória dupla são considerados somente os termos em que j+i <= m.

Gnn )!/)(!/()n ,P(n 2

n21

n1

21

21 ρρ= ∑ ∑

=

=

−=

=

=mi

i

imj

j

ii nnG0 0

2211 )!/)(!/( ρρ

33

PASTA: Poisson Arrivals See Time Averages

• O estado de uma fila M/M/1 é o número de clientes no sistema.

• Sistemas de fila mais gerais podem ter um estado mais geral que pode incluir quanto serviço um usuário já tem recebido.

• Para chegadas de Poisson, as chegadas em qualquer instante futuro são independentes das passadas e para muitos sistemas de interesse, são também independentes do estado presente S(t) (isto é verdadeiro para M/M/1, M/M/m, e M/G/1).

• Para tais sistemas, P{S(t)=s|A(t+δ)-A(t)=1} = P{S(t)=s}– (onde A(t)= # chegada desde t=0)

• No estado estacionário, as chegadas vão encontrar as probabilidades no estado estacionário.

34

Distribuição da Ocupação Após a Chegada

• Chegadas não sempre vão encontrar o estado estacionário médio.

• Exemplo:– Chegadas determinísticas 1 por segundo;– Tempo de serviço determinístico 3/4 de segundos.

λ = 1 pacote/segundo T = 3/4 segundos (não há fila) N = λT = Ocupação média = ¾.

• Contudo, observe que uma chegada sempre encontra o sistema vazio!

35

Ocupação Após Chegada Para a Fila M/M/1 an = Lim t → inf (P (N(t) = numa chegada ocorreu logo após o instante t ))Pn = Lim t→ inf (P(N(t) = n))

Para sistemas M/M/1 an = Pn

Prova: Seja A(t, t+δ) o evento em que uma chegada ocorreu entre t e t+δ.an (t) = Limt→inf (P (N(t) = n A(t, t+δ) )= Limt→inf (P (N(t) = n, A(t, t+δ) )/P(A(t, t+δ) )= Limt→ inf P(A(t, t+δ) N(t) = n)P(N(t) = n)/P(A(t, t+δ))

• Sendo que chegadas futuras são independentes do estado do sistema, P(A(t, t+δ) N(t) = n)= P(A(t, t+δ)).

• Portanto, an (t) = P(N(t) = n) = Pn(t).

• Tomando o limite quando t→ infinito, obtemos an = Pn.

• Resultado válido também para sistema M/G/1.