Lei de Little
Lei de Little
Recursos limitados
Geração de filas
Tomada de decisões
Otimização de recursos
Ferramentas simples
Lei de Little
Lei de Little
Parâmetros de uma Fila
LS
L
LQ




L: número médio de usuários no sistema
LQ: número médio de usuários na fila
W: tempo médio que um usuário permanece no
sistema
WQ: tempo médio que um usuário permanece
na fila
Lei de Little
Idéia de custo:
S

Cada usuário que entra ao sistema paga uma
quantia de dinheiro, de acordo a certa regra.
Identidade de custo:
Velocidade média com que o sistema ganha dinheiro =
taxa média de chegada ao sistema multiplicada
pela quantia paga por cada usuário.
S
S
Lei de Little

Definições:
Vs: velocidade média com que o sistema ganha
dinheiro
a: taxa média de chegada de usuários ao sistema
: quantia paga por cada usuário

Identidade de custo em termos matemáticos:
V S  a 
Lei de Little

Demonstração intuitiva da identidade de custo:
T: período de observação
$(T): quantia média ganha pelo sistema em [0,T]
N(T): número de usuários que entra no sistema em
[0,T]
Lei de Little

Tem-se que:
$(T) = Vs T
$(T) = N(T).
N(T)  a.T
(1)
(2)
(3)
De (1), (2) e (3), tem-se que: VsT  aT
Portanto:
Vs  a
Lei de Little

Aplicações de identidade de custo: regra 1
Cada usuário paga $ 1 por unidade de tempo
em que está no sistema.
[$/ut]
W[$/pessoa]
Sistema
Lei de Little
Definição:
D: velocidade com que o sistema ganha
dinheiro
W: quantia paga por um usuário (já que ele
está há W unidades de tempo no sistema)
Então, da igualdade de custo :
D   a W [$ / ut ]
Lei de Little

Aplicações da identidade de custo:
outro enfoque
Ponto de vista do “caixa” à entrada do sistema,
que observa que há L usuários no sistema.
Sistema
L usuários
Lei de Little
Definição:
D: velocidade com que o sistema ganha
dinheiro [$/ut]
L: número médio de usuários no sistema
Cada usuário paga 1$ por unidade de tempo.
Então:
D  L.1[$ / ut ]
Juntando ambos pontos de vista:
L
a W
Lei de Little

Aplicações da identidade de custo: regra 2
Cada usuário paga $ 1 por unidade de tempo
em que está na fila.
Definição:
Dq: velocidade com que a fila ganha dinheiro.
Wq: quantia paga por um usuário (já que está
há W unidades de tempo na fila)
Então, valor que corresponde aos pagamentos
feitos pelos usuários:
Dq  aWq [$ / ut ]
Lei de Little

Aplicações da identidade de custo:
outro enfoque
Ponto de vista do “caixa” à entrada da fila,
que observa que há N usuários na fila.
Definição:
Dq: velocidade com que a fila ganha dinheiro
Lq: número médio de usuários na fila
Resumo da regra:
Dq  Lq .1[$ / ut ]
Juntando ambos pontos de vista:
Lq  aWq
Lei de Little

Aplicações da identidade de custo: regra 3
Cada usuário paga $ 1 por unidade de tempo
em que está no servidor.
Definição:
E[s]: tempo médio em que cada usuário está no
servidor
Ls: número médio de usuários em serviço
S
Então, da igualdade de custo:
LS  a E[s ]
Lei de Little
Lei de Little

Aplicações da identidade de custo:
outro enfoque
Ponto de vista do “caixa” à entrada da zona de
serviço, que observa que há N usuários em
serviço.
Definição:
Ds: velocidade com que o serviço ganha
dinheiro
Ls: número médio de usuários em serviço
Então, da igualdade de custo :
D  L .1[$ / ut ]
s
Juntando ambos pontos de vista:
s
Ls  a E[s]
Aplicações da Lei de Little
Transmissão de pacotes
Linha de transmissão
destino
fonte
Pode ser modelado por:

Pacotes em espera
Nq

X
Pacotes em
transmissão
: taxa média de chegada de pacotes a uma rede
de computadores
Nq: número médio de pacotes esperando na fila
X : tempo médio de transmissão
Transmissão de pacotes

Pergunta 1: qual é o tempo médio de
permanência de um pacote na fila?
Aplicando a Lei de Little: W 

Nq

Pergunta 2: qual é o número médio de pacotes
na linha de transmissão?
Seja  o número de pacotes na linha de

transmissão. Pela Lei de Little:
 X
Rede de computadores
1
1
2
i
n
2






Linha de transmissão
i






n
Rede de computadores
1,2,…,n: taxa de chegada de pacotes aos n nós
N: número médio de pacotes dentro da rede
Rede de computadores

Pergunta: qual é o atraso médio de um pacote?
Ao sistema chegam   1   2  ...   i  ...   n
pacotes por unidade de tempo. Aplicando a Lei
n
de Little:
T  N /  i
i 1
Além disso, N i   i T i
onde
Ni: número médio de pacotes no nó i
Ti: atraso médio de pacotes no nó i
Análise de outro concentrador
T E R M IN A L
T E R M IN A L
T E R M IN A L
CONCENTRADOR
T E R M IN A L
Um concentrador de dados possui 40 terminais
a ele conectados. Cada terminal gera pacotes
com comprimento médio de 680 bits. 40 bits
de informação de controle são agregados a
cada pacote antes deste ser transmitido ao
enlace de saída, que tem capacidade de 7200
b/s.
Análise de outro concentrador

20 terminais: um pacote a cada 10 s em média
10 terminais: um pacote a cada 5 s em média
10 terminais: um pacote a cada 2.5 s em média

Modelo: as estatísticas de entrada tem
distribuição de Poisson.
  20 
1


1
1
1
 10   10 
 8pacotes / seg
10
5
25
680  40
7200
 0.1seg



 0.8
Análise de outro concentrador
2
E (T ) 
 
2

 0
2(1   )
 0.4seg
  
2 2 
E ( n) 
1  (1    )  2.4

1   
2
2
E (T ) 
2
E (W ) 
2
1
2
E (T )
2
2
1

E (W )  0.2seg
2
E (n)  2.4
Linha de transmissão
N(t)
K <  K+P < 2K
3
Chegada
do primeiro
pacote
Chegada do
segundo
pacote
2
1
 K+P
K
Partida do
primeiro
pacote
2K
3K
t
Partida do
segundo
pacote
K: período de chegada de um pacote à linha
K: tempo de transmissão do pacote ( < 1)
P: atraso de processamento e propagação do
pacote
Linha de transmissão

Pergunta 1: qual é a taxa de chegada de
pacotes ao sistema?

Como os pacotes chegam com períodos iguais,
sua taxa de chegada será:

1
K
Linha de transmissão

Pergunta 2: qual é o número de pacotes no
sistema?

Cada pacote permanece dentro do sistema:
T  K  P
De acordo com a Lei de Little tem-se que:
N  T   
P
K
Linha de transmissão

Observação 1:
N(t) é determinístico e variável no tempo.

Observação 2:
A Lei de Little é correta, caso interprete-se
N(t) como uma média no tempo, ou seja:
t
N  lim
t 
0 N ( )d
t
Sistema fechado com K servidores
Considere um sistema de uma fila com K
servidores e com N ( K) usuários (seja na fila
ouem serviço). O sistema está sempre cheio,
isto é, o sistema começa com N usuários e
quando um usuário sai do sistema é
imediatamente substituído por um novo
usuário.
Sistema fechado com K servidores

Calcular T em função do tempo médio de
serviço E[x]
Aplicando a Lei de Little ao sistema:
N  T
Aplicando a Lei de Little ao servidor:
K  E[ x ]
Eliminando  das duas equações anteriores se
chega a :
NE[ x ]
T 
K
Sistema fechado
servidores
1
2



N-K
usuários
i



K
K: número de servidores no sistema
T: tempo médio de um usuário no sistema
 (N  K)
N: número de usuário no sistema
X : tempo médio de serviço por usuário
Sistema fechado

Hipóteses:



sistema começa com N usuários
sistema fechado
Qual é o tempo médio que um usuário
permanece no sistema?
Aplicando a Lei de Little no sistema:
N  T
(1)
Sistema fechado

Considerando-se que todos os servidores estão
sempre ocupados, aplicando a Lei de Little ao
subsistema do servidor:
K  X
de (i) e (ii) tem-se que:
T 
NX
K
(2)
Controle de fluxo pela janela
N
0
1
.
Transmissor
.
X
Receptor
2
4
3
N: largura da janela para cada sessão
: taxa de chegada de pacotes ao sistema
T: atraso médio de cada pacote
Controle de fluxo pela janela

Hipóteses:




A sessão sempre tem pacotes para enviar.
Os acks de resposta têm duração desprezível.
Quando o pacote i chega a destino, o pacote
i+N é imediatamente introduzido na rede.
Análise pela Lei de Little:
N  T


Se T aumenta, então  diminui
Para máximo  fixo um incremento no tamanho
da janela somente incrementa o atraso T
Análise de um computador a
tempo compartilhado
Arquitetura:
T1


T2
Computador
P
TN
R
D
Parâmetros do sistema






N: número de terminais
R: tempo médio de pensar em cada terminal
P: tempo médio de processamento de cada
tarefa
D: tempo médio desde que um trabalho é
submetido ao computador até que termine sua
execução
T = R+D: tempo médio de uma tarefa no
sistema
: throughput do sistema
Análise de um computador a
tempo compartilhado

Condição de sistema fechado:
N = constante no sistema

Condição máxima de utilização:
Sempre existe um usuário com uma tarefa
quando outro acaba de ser atendido.

Problema: encontrar os valores máximos e
mínimos de  e T.
Modelo
Time sharing:
TERMINAL
1
R
A
CPU

1/P
B

TERMINAL
2
R
TERMINAL
N
P
R
R
D
T
Análise de um computador a
tempo compartilhado

Análide: devido à hipotese, sempre existem N
terminais que estão processando. Aplicando a
Lei de Little entre os pontos (A) e (B):
  N /T


Atraso mínimo de um trabalho
Dmin = P
Atraso máximo de um trabalho
Dmax = NP
Análise de um computador a
tempo compartilhado

Conclusão
P  D  NP
Portanto,
R + P  T  R + NP
(1)
Aplicando a Lei de Little em (1)
N
R  NP

N
RP
(2)
Como o processamento de uma tarefa demora
P, tem-se que:
1

(3)
P
Análise de um computador a
tempo compartilhado
Combinando (2) e (3), obtem-se:
N
1
N
   min{ ,
}
R  NP
p RP
(4)
Usando-se a Lei de Little, chega-se aos limites
de tempo para o sistema
max{NP , RP }  T  R  NP
(5)
Atraso máximo e mínimo do
sistema
T
R+NP
NP
R+P
R
N Ú M E R O D E T E R M IN A IS
1
N
1/P
THROUGHPUT
Throughput máximo e mínimo
1+R/P
NÚMERO DE TERMINAIS
Processos de nascimento e
morte
Processos de nascimento e
morte

É o caso especial de uma cadeia de Markov na
qual as únicas transições permitidas (ou
possíveis) a partir de um estado Ek, são aos
estados Ek-1 ou Ek+1, se estes estados existem.
k-1
Ek-1
k
Ek+1
Ek
k
k+1
Definições

Nascimento: transição ao estado adjacente
superior (hipótese: num intervalo de tempo
(t,t+ t) pode chegar no máximo um usuário ao
Ek
Ek+1
sistema).

Morte: transição ao estado adjacente inferior
(hipótese: num intervalo de tempo (t,t+ t)
pode sair no máximo um usuário do sistema).
Ek
Ek-1
Definições

Razão de nascimento: número médio de
nascimentos por unidade de tempo. Esta razão
é dependente do estado, isto é, para o estado k:
k qk,k+1

Razão de morte: número médio de mortes por
unidade de tempo quando o sistema está num
determinado estado k: k qk,k-1

Como a EBG estabelece que
Então: qk,k = - (
k
+
k)
qk,i = 0
Solução dos PNM

Evolução temporal de um PNM no intervalo (t,
t+ t):
Ek+1
Ek
Ek
Ek-1
t

Deseja-se obter:
t+t
P N( t + t ) = Ek 
Solução dos PNM

Hipótese: quando se está no estado E0, não é
possível uma morte (0 = 0), mas é possível um
nascimento (0  0) (exemplo: geração
espontânea)
Solução dos PNM

Logo, as possibilidades de estar no estado Ek
no instante t + t, a partir do estado no
instante t, são:
Ek+1
Ek
Não mudou
Ek
Ek-1
t
t+t
Definições

B1(k,t) = P[um nascimento em (t,t+t) | N(t)=Ek]
= k t + o(t)

D1(k,t) = P[uma morte em (t,t+t) | N(t)=E k]
= k t + o(t)

B0(k,t) = P[nenhum nascimento em (t,t+t) |
N(t)=Ek]
= 1 - k t + o(t)

D0(k,t) = P[nenhuma morte em (t,t+t) | N(t)=E k]
= 1 - k t + o(t)
Definições

Sejam:
k(t) = P[N(t) = Ek]
pi,j(t,t+ t) = P[N(t+ t) = Ej | N(t) = Ei],
para |i-j| < 1
Definições

Logo:
pk,k(t,t+t) = B0(k,t) D0(k,t) + o(t)
pk-1,k(t,t+t) = B1(k,t) D0(k,t) + o(t)
pk+1,k(t,t+t) = B0(k,t) D1(k,t) + o(t)

Desenvolvendo:
pk,k(t,t+t) = 1 - (k + k)t + o(t)
pk-1,k(t,t+t) = k t + o(t)
pk+1,k(t,t+t) = k t + o(t)
Solução dos PNM
Ek+1
Ek
Não muda
Ek
Ek-1
t

t+t
Pelo teorema das probabilidades totais, tem-se
que:  ( t  t )   ( t )  p ( t , t  t )
k
k
k,k
  k-1 ( t )  pk-1,k ( t , t  t )
  k +1 ( t )  pk +1,k ( t , t  t )  o( t )
,
k1
 0 ( t  t )   0 ( t )  p0,0 ( t , t  t )
  1 ( t )  p1,0 ( t , t  t )  o( t )
,
k0
Solução dos PNM

Substituindo, agrupando e tomando
obtém-se:
d k (t )
 (
dt
d 0 (t )
dt
k
  k ) k (t )  
 
0 0 (t ) 

k 0
k -1 k -1(t )   k +1 k +1(t ),
 11(t ), k  0
Além disso,
 k (t )  1,
t0,
t  0
k 1
Solução dos PNM

Logo,obtém-se o seguinte sistema:
d k ( t )
dt
d 0 ( t )
dt

k
k
 (
 
(t)  1
k
0
  k ) k ( t )  
 0 ( t )   1 1 ( t )
k-1
 k -1 ( t )   k +1 k +1 ( t )
, k0
, k1
Solução dos PNM

Para uma cadeia de Markov qualquer:
d ( t )
dt

Para um PNM, tem-se que:
0


 1
Q = 0
 0



  ( t )Q
0
0
0
0
 ( 1  1 )
1
0
0
2
( 2   2 )
2
0
0
3
( 3   3 )
3







Observa-se que esta equação coincide com a
da transparência anterior.
Exemplo

Um processo de Poisson é um processo de
nascimento puro, onde:
k
k
k  k

As equações anteriores são reduzidas a:
d k ( t )
dt
d 0 ( t )
dt

    k ( t )    k -1 ( t )
   0 ( t )
Condição inicial:
, k0
 0 (0)  1
, k1
Exemplo

Resolvendo, se tem que:
0 (t ) = e
- t
 1 ( t ) = te
- t
Logo, por indução obtém-se:
k (t ) =
( t )
k!
k
e
- t
Processo de Poisson
Solução de um PNM em
equilíbrio

Em estado estacionário (t) é independente do
tempo, logo (t vai ser representado somente
por
A EBG se reduz a:
Q=0

Além disso:

k
k
1
Solução de um PNM em
equilíbrio

Logo:
0  (k  
k ) k
0  0 0 

k
k
1
 k -1 k -1  
11, k  0
k +1 k +1,
k 1
Solução de um PNM em
equilíbrio

O caso anterior visualiza-se da seguinte
maneira:
 k-1
Ek-1
k
Ek+1
Ek
k
 k+1
Fluxo que sai = Fluxo que entra
Solução de um PNM em
equilíbrio

O caso anterior visualiza-se da seguinte
maneira:
 k-1
Ek-1
k
Ek+1
Ek
k
 k+1
(k+k)k = Fluxo que entra
Solução de um PNM em
equilíbrio

O caso anterior visualiza-se da seguinte
maneira:
 k-1
Ek-1
k
Ek+1
Ek
k
 k+1
(k+k)k = k-1k-1 + k+1k+1
Solução de um PNM em
equilíbrio

Reorganizando-se:
k -1 k -1   k k

k k   k +1 k +1
Por outro lado, definindo-se gk como:
g k  k k   k +1 k +1
Solução de um PNM em
equilíbrio

Reconhecendo gk na EBG:

 k-1   k  k
k-1


k
 k   k +1 k +1
gk
com:
gk   k  k   k+1 k+1
Solução de um PNM em
equilíbrio

Reconhecendo gk na EBG :

 k-1   k  k
k-1
gk -1


k
 k   k +1 k +1
=
com
gk  
k
 k   k +1 k +1
gk
Solução de um PNM em
equilíbrio

Reconhecendo gk na EBG :

 k-1   k  k
k-1
gk-1


k
 k   k +1 k +1
=
logo,
gk
é constante com respeito a k
gk
Solução de um PNM em
equilíbrio

Além disso, num PNM:

-1
0
E0

0

1
E1
1
2
Da EBG para o estado 0, se vê que g0 = 0.
Juntando-se com a equacao que diz que
gk+1 = gk, tem-se que:
gk = 0
k 0
Solução de um PNM em
equilíbrio

Além disso, num PNM:

-1
0
E0

0
de onde g-1  0
1
E1
1
2
Solução de um PNM em
equilíbrio

Além disso, num PNM:

-1
0
E0

0
de onde g-1  0
1
E1
1

2

k
 k   k +1 k +1
Equação de balanço local

A equação anterior corresponde a uma equação de
balanço local (EBL), isto é:
 k-1
Ek-1
k
k
Ek+1
Ek
k
 k+1
 
k
k
 k+1
= 
k+1
Ek+2
k+1
Equação de balanço local

Cabe comentar que a EBL não é verdadeira
para qualquer cadeia de Markov, por exemplo:
 01
E0

30
03
E3
E1
 10
 20
 32
E2
Equação de balanço local

Cabe comentar que a EBL não é verdadeira
para qualquer cadeia de Markov, por exemplo:
 01
E0

30
03
E3
E1
 10
 20
 32
E2
Equação de balanço local

Cabe comentar que a EBL não é verdadeira
para qualquer cadeia de Markov, por exemplo:
 01
E0

30
03
E3

32 32
= 
23 23
E1
 10
 20
 32
E2
Equação de balanço local

Logo, segundo a EBL:
 k-1
Ek-1
k
k
Ek+1
Ek
k
 k+1
k

k
Ek+2
 k+1
= 
k+1 k+1
A EBL estabelece que, em estado estacionário,
o FLUXO entre dois estados adjacentes é IGUAL
Solução de um PNM em
equilíbrio

É mais fácil resolver a EBL do que a EBG.
Tem-se que:


Para:
k = 0:
k
 k   k +1 k +1
1 
0 0
1
, k = 1:
2 
 1 1
2
Solução de um PNM em
equilíbrio

É mais fácil resolver a EBL do que a EBG.
Tem-se que:


Para:
k = 0:

Por indução:
k
 k   k +1 k +1
1 
0 0
1
, k = 1:
k 1
k  0 
i0
i
 i 1
2 
 1 1
2
Solução de um PNM em
equilíbrio

Além disso:


k
1
k0
Logo:
0 
1

k 1
1 
k 1 i  0
i
 i 1