Soluções Analíticas para
Distribuições Discretas na GSPN
César Augusto L. Oliveira
[email protected]
Introdução
• Solução Analítica X Simulação
• Distribuições discretas na GSPN
– Número de tokens em lugares
• Distribuições contínuas na GSPN
– Tempo e throughput (transições)
Objetivo
• Identificar distribuições discretas que surgem
na GSPN em determinadas condições
– GSPN  distribuição
• Identificar modelos em GSPN que
representam distribuições conhecidas
– Distribuição  GSPN
• Identificar as distribuições no contexto de
redes mais complexas
– Regras de composição/separação
Distribuições Discretas
•
•
•
•
•
•
Bernoulli
Categórica
Binomial
Binomial negativa
Multinomial
Multinomial negativa
• Geométrica
• Geométrica limitada
• Geométrica
multivariada
• Poisson
• Poisson multivariada
Bernoulli
• Experimentos em que há dois resultados
possíveis
– Ex.: jogar uma moeda
• P.M.F (probability mass function)
Bernoulli na GSPN
a1
A
[dA]
a2
P( A  1) 
B
[dB]
P( B  1) 
a1d A
a1d A  a 2 d B
a 2d B
a1d A  a 2 d B
Bernoulli na GSPN
A
[dA]
P( A  1) 
[dB]
B
dA
d A  dB
dB
P( B  1) 
d A  dB
Bernoulli na GSPN
• Todos os lugares limitados a 1 token
correspondem à distribuição Bernoulli
• Probabilidade é proporcional ao tempo que o
token passa neste lugar
Categórica
• Experimento em que há N resultados
(mutuamente exclusivos) possíveis, com
probabilidades p = [p1, ..., pN]
– Ex.: Jogada de dados
• P.M.F
f ( xi ; p)  pi
N
Tal que
p
i 1
i
1
Distr. Categórica na GSPN
A1
[d4]
A4
P( Ai  1) 
[d1]
[d3]
A2
[d2]
A4

di
N
j 1
dj
Distr. Categórica na GSPN
• Conjunto de lugares cobertos por uma
invariante limitada a 1 token
• Probabilidade é proporcional ao tempo que o
token passa em cada lugar
Binomial
• Representa um conjunto de N experimentos
do tipo sucesso/falha, onde cada resultado
tem probabilidade p de ter resultado sucesso
e (1-p) de ter resultado falha
• Distribuição do número de sucessos
– Ex.: jogada de N moedas
• P.M.F
N k
f (k ; N , p)    p (1  p) N k
k
Binomial na GSPN
N
-server
A
-server
[dA]
[dB]
B
N k
P( A  k )    p (1  p ) N  k
k
dA
p
d A  dB
Binomial na GSPN
• Dois lugares cobertos por uma invariante
limitada a N tokens
• Transições infinite-server
• Distribuição é proporcional aos tempos que os
tokens passam em cada lugar
Multinomial
• Representa a distribuição conjunta do número
de resultados de cada valor possível, em N
experimentos independentes, onde cada
experimento tem distribuição categórica
• P.M.F
 N!
x1
xk
p

p

k
f ( x1 ,, xk ; N , p1 ,, pk )   x1! xk ! 1

0

k
,  xi  N
i 1
, caso contrário.
Multinomial na GSPN
[dk]
A1
Ak
N
P( A1  x1 ,, Ak  xk ) 
-server
Mn( N , p1 ,, pk )
-server
[d1]
-server
[d3]
pi 
di
k
d
j 1
-server
A2
[d2]
A3
j
Multinomial na GSPN
• Um conjunto de lugares cobertos por uma
invariante limitada a N tokens
• Transições são infinite-server
• Distribuição é proporcional ao tempo que os
tokens passam em cada lugar
Geométrica
• Em uma sequencia de experimentos do tipo
sucesso/falha, representa o número de
sucessos obtidos antes da primeira falha, onde
o sucesso tem probabilidade p
• P.M.F
f (k; p)  p (1  p)
k
Geométrica na GSPN
[d1]
A
Onde d2 < d1, caso contrário,
o sistema tenderá a infinito.
[d2]
P( A  k )  Geom(k ; p)
d
p 2
d1
Geométrica na GSPN
• Lugar em que tokens chegam seguindo um
processo de Poisson e são removidos
sequencialmente entre intervalos de tempo
exponenciais (fila M/M/1)
• Transições são single-server
Geométrica Limitada
• Versão da distribuição geométrica em que o
número máximo de experimentos é limitado a
N
• P.M.F
f (k ; N , p)  p
k
1
1  i 1 p
N
i
Geométrica Limitada na GSPN
N
1-server
A
P( A  k )  p k
1-server
[dA]
p
[dB]
1
1  i 1 p i
N
dB
dA
B
[d1]
A
N
[d2]
Geométrica Limitada na GSPN
• Lugar em que chegam tokens seguindo um
processo de Poisson apenas enquanto sua
marcação for menor que N. Os tokens são
removidos sequencialmente a intervalos
exponenciais
• Transições são single-server
Geométrica Multivariada
• Em uma sequencia de experimentos com
resultados categóricos (valores a0,...,am),
representa o número de resultados de cada
tipo (x1, ..., xm) antes da primeira ocorrência
de um resultado específico (a0)
• P.M.F
m
m
f ( x1 ,, xm ; p1 ,, pm ) 
(i 1 xi )!

m
p

x!
i 1 i
p0  1  i 1 pi
m
i
i 1
xi
p0
Geométrica Multivariada na GSPN
[d1]
[d0]
A1
P( A1  x1 ,..., Am  xm ) 
A0
[d2]
[d0]
A2
... [dm]
MGeom(d 0 / d1 ,...,d 0 / d m )
Am
[d0]
Geométrica Multivariada na GSPN
• Recurso único compartilhado entre m filas,
onde as chegadas são processos de Poisson e
o serviço tem tempo exponencial
• Transições são single-server
• Distribuição conjunta das marcações dos
lugares A1,...,Am
Binomial Negativa
• Representa o número de sucessos que
ocorrem em uma sequencia de experimentos
de Bernoulli antes da R-ésima falha
• Equivale à soma de R variáveis geométricas
idênticas
• P.M.F
 k  R  1
 p k (1  p) R
f (k ; R, p)  
 R 1 
Binomial Negativa na GSPN
[d2]
P1
[d1]
A
[d2]
P2
...
P( A  k )  NB( R,
d2
)
d1
...
PR
[d2]
...
Binomial Negativa na GSPN
• Lugar que possui uma quantidade de tokens
igual à soma dos tokens de R lugares P1,...,PR,
onde cada lugar Pi possui distribuição
geométrica idêntica
• Transições são single-server
Multinomial Negativa
• Em uma sequencia de experimentos com
resultados categóricos (valores a0,...,am),
representa o número de resultados de cada
tipo (x1, ..., xm) antes que o valor a0 seja
obtido k vezes
• P.M.F
f ( x1 ,..., xm ; k , p0 ,..., pm ) 
k
m
xi
i
p0
p
(k  i 1 xi )

(k ) i 1 xi !
m
Multinomial Negativa na GSPN
[d1]
A1
[d0]
A0
[d2]
A2
[d0]
P( A1  x1 ,..., Am  xm ) 
NM (k , p0 , p1 ,..., pm )
d
pi  0 , i  1,...,m
di
[d1]
[d2]
[d0]
A0
[d0]
p0  1  i 1 pi
m
Ex.: k=2
Multinomial Negativa na GSPN
• Lugares somam os tokens acumulados em k
cópias de filas, cada cópia participando de um
sistema de filas com um recurso
compartilhado
• Cada sistema é uma cópia do modelo de
distribuição Geométrica Multivariada
• Transições são single-server
Poisson
• Número de eventos que ocorrem em um
intervalo fixo de tempo, tal que esses eventos
ocorrem a uma taxa conhecida e cada evento
ocorre independentemente do último evento
ocorrido
• P.M.F
k  T
( T ) e
f ( k ; T ) 
k!
Poisson na GSPN
[d1]
A
[d2]
P( A  k )  Poisson(k; d 2 / d1 )
-server
Onde d2 < d1, caso contrário,
o sistema tenderá a infinito.
Poisson na GSPN
• Modelo equivalente à uma fila M/M/∞
• Transição que representa o serviço é infiniteserver
Poisson Multivariada e Chegadas
Correlacionadas
• Versão da distribuição de Poisson onde há
diversas classes de clientes e existe um
relacionamento entre as chegadas
• Sistema cresce em complexidade dependendo
do número de classes
Poisson Tri-variada com Chegadas
Correlacionadas
• Caso em que há 3 classes (trivariate)
• Sejam q1, q2, q3 as taxas de chegadas das classes 1,
2 e 3, respectivamente
• Sejam q12, q13, q23 a covariância entre as chegadas
das classes 1 e 2, 1 e 3, 2 e 3, respectivamente
• P.M.F
f ( x1 , x2 , x3 ;q1 ,q 2 ,q 3 ,q12 ,q13 ,q 23 ) 


q1x1  y12  y13q 2x2  y12  y23q 3x3  y13  y23q12y12 q13y13q 23y23
e
. 


( y12 , y13 , y 23 )Y  ( x1  y12  y13 )!( x2  y12  y 23 )!( x3  y13  y 23 )! y12 ! y13 ! y 23 !
Y  {( y12 , y13 , y23 )  N 3 : { y12  y13  x1}  { y12  y23  x2 }  { y13  y23  x3}  }
q1 q 2 q 3 q12 q13 q 23
Poisson Tri-variada na GSPN
[d12]
A1
[d0]
[d1]
[d13]
-server
A2
[d0]
[d2]
-server
[d23]
A3
[d0]
[d3]
-server
q1=d0/d1
q2=d0/d2
q3=d0/d3
q12=d0/d12
q13=d0/d13
q23=d0/d23
Poisson Tri-variada na GSPN
• Modelo de 3 filas Poisson, onde as chegadas
são relacionadas por transições que disparam
tokens simultaneamente para mais de uma
fila
Conclusão
• 11 distribuições modeladas
• Bernoulli, categórica, binomial e multinomial
podem se aplicar quando:
– Lugares cobertos por uma invariante
– Probabilidade de chegar em cada lugar pode ser
calculada
– Tempo médio em cada lugar pode ser calculado
Conclusão
• Poisson, Geométrica e suas variações são
conhecidas da teoria das filas
• Outras distribuições são mais específicas
– Aplicação ainda não é clara
• Regras para redução, separação, composição e
equivalência ainda precisam ser desenvolvidas
Dúvidas?