Protocolo Aloha
Protocolo Aloha
 Arquitetura
física:
N = Número de estações
Est. 1
Est. 2
Est. N
canal comum

Uma estação transmite quando precisa, sem se
preocupar em escutar o canal.
Protocolo Aloha

Técnica mais simples que utiliza a estratégia de
acesso a um meio comum, que pode ser acessado
por todos os usuários.

Existem dois tipos de protocolo Aloha:
Aloha Puro
 Aloha Segmentado

Protocolo Aloha puro
Duas ou mais estações podem transmitir ao mesmo
tempo. Esta situação dá origem a colisões, que
devem ser detectadas e logo resolvidas.

Est. 1
Est. 2
Est. 3
Tempo
Modelo Aloha puro

Modelo do canal:
Est. 1
+
.
.
CANAL
.
Est. N
+
Modelo Aloha puro
Hipóteses:
 Comprimento fixo dos pacotes = T
 Canal livre de ruído (perda de pacotes somente
por colisões)
 Estações têm comportamento homogêneo
 Uma estação transmite pacotes com sucesso
antes da chegada do seguinte
 Chegada de pacotes em cada estação obedece a
um proceso de Poisson  taxa de chegadas ao
meio comum tem distribuição de Poisson
Taxa efetiva de transmissão
Est. 1

.
+

CANAL
.
.
Est. N


+

= taxa média de transmissão de novos pacotes
ao canal, em cada estação (pac/seg)

’ = taxa média de transmissão ao canal de
pacotes novos mais os retransmitidos (devido a
colisões), em cada estação (pac/seg)
Taxa efetiva de transmissão
Est. 1

.
+

.
.
Est. N
CANAL


S
G
+

 = tamanho fixo de um pacote (seg)

S = N  T = utilização proporcional do canal
por pacotes efetivamente transmitidos (novos)

G = N ’ T = utilização proporcional do canal
pelo total de pacotes transmitidos (novos mais
colisões)
Taxa efetiva de transmissão

Logo, tem-se que:
S
P0 
G
(1)
P0 = probabilidade de transmissão com sucesso de
pacotes pelo canal (sem colisões)
Taxa total de transmissão de pacotes tem
distribuição de Poisson com parâmetro N’:
i   N  t 
N   t  e

Pi  t 
 2
i!

Taxa efetiva de transmissão

Colisão entre duas mensagens:
Canal
0
2T
Tempo
Tempo de vulnerabilidade
 A probabilidade
de que não ocorram colisões
nesse intervalo [0,2T] é a probabilidade de que não
sejam transmitidos pacotes neste intervalo. Logo,
de (2) obtem-se:
P0  P0 2T  P nenhuma transmissao em  0,2T
P0  e 2N t  e 2G
3
Taxa efetiva de transmissão
Das equações (1) e (3) obtém-se a capacidade do
canal (S) em função da taxa de transmissão total de
pacotes (G):

S  G  P0  G  e
2G
Rendimento máximo ocorre para G=0.5, com
S=0.184:

Max (S) = 18%
Taxa efetiva de transmissão

Gráfico de S(G):
0,184

S  G  e 2G
Observações:
Para cargas baixas de pacotes acontecem poucas
colisões, portanto S = G

À medida em que G aumenta e, portanto, S aproximase de 0.18, o número de colisões aumenta.

Taxa efetiva de transmissão

Gráfico de S(G):
S  G  e 2G
0,184

Observações:
 Ao
aumentar o número de colisões, aumenta o
número de retransmissões e, por conseguinte, aumenta
a probabilidade de que ocorra uma colisão.
Então, S decai e o sistema torna-se instável para altos
valores de G.

Protocolo Aloha segmentado

A estação espera que comece um intervalo de
tempo para transmitir um pacote

O sistema passa de contínuo a discreto
Est. 1
Est. 2
Est. 3
Tempo

Neste caso, ocorre colisão total ou não ocorre.

É necessário haver sincronismo geral.
Taxa efetiva de transmissão

Tempo de vulnerabilidade cai à metade:
T
 Após
a mesma análise que foi feita com Aloha
puro, obtém-se o seguinte resultado para Aloha
segmentado:
S  G  P0 = G  e
G
Taxa efetiva de transmissão

Gráfico de S(G):
0,368
S  G  e G
Rendimento máximo ocorre para G=1, com
S=0.368:

Max (S) = 37%
Comparação
 Aloha
puro
Est. 1
Est. 2
Est. 3
Tempo
 Aloha
segmentado
Est. 1
Est. 2
Est. 3
Tempo
Comparação

Resumo de resultados:
Taxa efetiva
S(G)
Puro
Segmentado
S  G e
2G
S  Ge
G
Máximo
rend. S
18%
37%
(G = 0,5)
(G = 1)
Comparação

Comparação de gráficos:
Distribuições contínuas
Variáveis aleatórias contínuas


Variáveis aleatórias contínuas: a v.a. assume
valores em um contínuo de valores possíveis,
seu domínio não é um conjunto enumerável.
X é uma variável aleatória contínua se existe
uma função f: (-,)   tal que B  
P{XB} = f ( x ) dx


B
f(.) é a função de densidade de probabilidade
da v.a. X
Variáveis aleatórias contínuas


P{X(-,+)} =
b

P{X[a,b]} =
a
 f ( x)dx  1

 f ( x)dx
a
 f ( x)dx  0

P{X = a} =

a
Probabilidade de uma v.a. contínua assumir
determinado valor é nula
Variáveis aleatórias contínuas

Função de distribuição acumulada:
F(a) = P{X  a} =
a
 f ( x)dx

d
F (a)  f (a)
da
Variáveis aleatórias contínuas

Seja X uma v.a. contínua. Então, seu valor
esperado é dado por:
E[ X ] 

 x. f ( x)dx

Distribuição uniforme

Uniforme u(0,1)
X  0,1
0  x 1
1

f ( x)  0 caso contrário

Distribuição uniforme
 Uniforme u(,)
X   ,  
 1
   
f ( x)  
 0

 x
caso contrário
Distribuição uniforme
 Função de distribuição:
 0
a 
 a 
F (a)  
 a
 
a
 1
Distribuição uniforme

Valor esperado:

E[X] =
x
    dx

=
Portanto, E[X] =   
2
2   2
2(   )
Distribuição uniforme
Parâmetros
E[X]
(b+a)/2
Var[X]
(b-a)2/12
Distribuição uniforme

Discos de um dispositivo de memória rodam
uma vez a cada 25 ms. Quando a cabeça de
leitura/escrita está posicionada sobre uma
trilha para ler algum registro em particular
dessa trilha, este pode estar em qualquer lugar.
Então, o retardo rotacional T até que o registro
fique na posição para ser lido é uniformemente
distribuído no intervalo 0 a 25 ms.
(a) E[T] = ?
(b) Var[T] = ?
(c) probabilidade do retardo rotacional ficar
entre 5 e 15 ms?
Distribuição uniforme
(a)
(b)
(c)
0  25
ET  
 12 .5
2
Var[T ] 
25  02
12
ms
 52.0833
10
P5  T  15   04
.
25
Distribuição exponencial

X Exp ()

X 
 e
f x  
0
  x
 1  e  x
F  x  
0
,
,
x  0
x  0
, x0
, x0
Distribuição exponencial
9
8
7
6
5
4
3
2
1
0
=8
f x    e
- x
x
2x = 0.25
0.125
E[x]
0.2
0.4
0.6
0.8
1.0
Distribuição exponencial
f x    e
f (x)
- x
6
5
 = 6
4
 =2
3
 =4
2
1
x
0
0.5
1.0
1.5
2.0
Distribuição exponencial
1.0
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
F  x 1 e
 x
= 8
2x = 0.25
0
0.2
0.125
E[x]
0.4
0.6
0.8
1.0
x
Distribuição exponencial
1
0.9
0.8
0.7

F(x)
0.6
0.5

0.4
0.3

0.2
0.1
0
0
5
10
15
x
20
25
30
Distribuição exponencial

Valor esperado: 
x
E[X]=
xe dx

0
Para integrar por partes, define-se:
u = x ; du = dx
x
x
v =  e ; dv = e dx
Logo:


E[X] =  xex   e x dx =
0 0
1
Portanto, E[X]= 
e  x 
0
 0
Distruibuição exponencial
1
E [X]

X
1
Var [X]
f X( q)
n
E [X ]

1

2

 q
n!

n
Exemplo 1
X
 X:
v.a. tamanho de um pacote
 X ~ Exp (1/L)
 L: Valor médio do tamanho do pacote
 L: bits/pacote
Exemplo 2
X
Canal de transmissão : C (bps)
 X:
tamanho do pacote
 Y: v.a. tempo de transmissão de cada pacote
 Y ~ Exp (C/X)
 X/C: valor médio do tempo de transmissão de
um pacote (seg/pacote)
Exemplo 3
Tempo entre chegadas
chegada de
pacotes
Nó
t


t0
t1
t2
tn
 i = t i -t i-1: tempo entre chegadas
 i ~ Exp ()
 i são independentes
 1/: valor médio do tempo entre pacotes
(seg/pacote)
Falta de memória
PX  s  t X  t  PX  s
s,t  0
f (x)

=8


P X s

P X  st X  t

x [ut]
0
s
t
s+t
ut  unidades de tempo
Falta de memória
X
: ~ Exp (): probabilidade de falha de uma rede
 P{X > s}:probabilidade de que a rede não falhe
durante s unidades de tempo
 P{X > s + t | X > t}: probabilidade de que a rede não
falhe durante s+t unidades de tempo, dado que
funcionou durante t unidades de tempo
 Como o sistema não tem memória:
P{X > s + t | X > t}= P{X > s}
Ordem entre eventos exponenciais

X1 ~ Exp (1)

X2 ~ Exp (2)

Problema:

Solução:
P
X
 X
1
2

?
1
PX1  X 2 
2  1
Generalização
 Xi ~ Exp(i),
 Problema:
 Solução:
i=1,…,n

P X1  X 2 
X3 Xn

P X1  X 2 
X3 Xn


?
1
n
 i
i 1
Exemplo
 Sistema
de servidor de impressão formado por
duas partes principais: servidor e impressora
 Sejam:
Xs ~ Exp(s):
vida útil servidor
Xi ~ Exp(i):
vida útil impressora
E[Xs]:
10.000 hrs
E[Xi]:
3.000 hrs
 Problema: Qual é a probabilidade do sistema
falhar devido a uma falha no servidor?
Exemplo


Problema :
Qual é a probabilidade do sistema falhar devido
a uma falha no servidor?

Solução: P X  X 
s





s
i





 s  i
1
10000

1  1
10000 3000
 3
13
Distribuição de Erlang
X Erl (k,)
 X 
 Função de densidade de probabilidade
k 1
 (x)
-x
f x 
e
, x  0,   0, k = 1,2,...

 

(k  1)!
(1)
Função de distribuição:
( x )
F x  1  
n!
n 0
k 1
n
e
-x
,
x  0,   0, k = 1,2,...
(2)
Distribuição de Erlang
f x 
0.8
 (x)
k 1
(k  1)!
e
-x
,
x0
0.7
0.6
k=2
=2
0.5
0.4
0.3
0.2
2 x  2
0.1
0
0
E[x]=1
2
3
4
5
x
Distribuição de Erlang
( x )
F x  1  
n!
n 0
1
k 1
n
e
-x
,
x0
0.9
0.8
0.7
0.6
k=2
=2
0.5
0.4
0.3
0.2
0.1
2 x  2
0
0
2
E[x]=1
3
4
5
x
Distribuição de Erlang (k,)
Parâmetros
E [X]
X
Var (X)
fX (q)
E [Xn]
1

1
 k
1
2 k
  k 


  k q 
k
k  k  1...  k  n  1
 k  n
Relação entre Exponencial e Erlang

servidor

Servidor com somente uma entrada e uma saída

Todos os pacotes devem ser atendidos

Servidor atende somente um pacote de cada vez

Existe retardo somente no servidor

X: v.a. tempo de serviço

X ~ Exp(): f(x) = ·e-x, x 0

E[x] = 1/
x2 = 1/2
Relação entre Exponencial e Erlang


Etapa 1 Etapa 2







Servidor com duas etapas em série
Cada pacote deve passar por ambas etapas
Servidor atende um pacote de cada vez (ambas
etapas não podem estar ativas simultaneamente)
não há retardo entre etapas
Xi: v.a. tempo de serviço da etapa i
Xi ~ Exp(2): f(xi ) = 2·e -2, x 0
E[Xi] = 1/(2
xi2 = 1/(22
Relação entre Exponencial e Erlang


Problema: qual é a distribuição do tempo total de
serviço (retardo total)?
Solução: soma de duas variáveis aleatórias
independentes e idênticamente distribuídas com
distribuição exponencial
X: v.a. tempo de serviço total
Seja £[f(x)] a transformada de Laplace de f(x)
Então: £[f(x)] = £[f(x1)] · £[f(x2)]
f(x) = xe-x, x 
E[X] = E[X1] + E[X2] = 1/
x2 = x 2 +x 2 = 1/(22)
Relação entre Exponencial e Erlang







k
k
k
k
Etapa 1
Etapa 2
Etapa i
Etapa k
Servidor de k etapas em série
Cada pacote deve passar pelas k etapas
Um novo pacote pode entrar na etapa i apenas
quando o pacote em serviço acabar a etapa k
não há retardo entre etapas
Xi: v.a. tempo de serviço da etapa i
Xi ~ Exp(k): f(xi ) = k  e -kx, x 0
E[xi] = 1/(k
x 2 = 1/(k2
Relação entre Exponencial e Erlang


Problema: qual é a distribuição do tempo total
de serviço (retardo total)?
Solução: é a soma de k variáveis aleatórias
independentes e idênticamente distribuídas.
X: v.a. tempo de serviço total
E[X] = E[Xi] = k (1/(k)) = 1/
X2 =  Xi2 = k (1/(k))2 = 1/(k2)
£[f(x)] = £[f(xi)]
k ( kx )k  1  kx
f ( x) 
e
: X ~Erl(k,  )
( k  1)!
Relação entre Exponencial e Erlang
 x:
atraso total (em unidades de tempo) de um
pacote ao atravessar k etapas, cada uma das
quais introduz um retardo y
 Y~ Exp()
 X ~ Erl(k,), /k
 E[X] = k E[Y]
 x2k·y2
 x·
k y
Relação entre Exponencial e Erlang
 = 1/2 , k = 4
2.00E+00
 = 2/3 , k = 3
=1 , k=2
=2 , k=1
1.50E+00
f(x)
1.00E+00
5.00E-01
0.00E+00
0.00
2.00
29.00
30.00
31.00
4.00
32.00 6.00
1.86E-03 9.67E-06
1.29E-03 5.50E-06 8.42E-11 1.75E-26
8.92E-04 3.11E-06 3.31E-11 2.37E-27
8.00 6.15E-04
10.00 12.00
14.00 1.30E-11
16.00 18.00
20.00
1.76E-06
3.21E-28
-5.00E-01
Função de densidade para  . k = 2 = 
x ~ Erl (k , )
y ~ Exp ()
Função de densidade para = 1
1.4
1.2
k = 10
k=1
k=2
k=
1
0.8
0.6
0.4
0.2
0
0
1
2
3
4
Fazendo : df(x)/dx = 0
obtém-se: x f
max
k 1 1


k 
5
x
Exemplo

Problema: obter o tempo médio E[T] que demora um
nó para transmitir n pacotes de um buffer, se o tempo
de transmissão de um pacote é Exp() com média 1/.
Nó
Buffer
Canal de transmissão
Exemplo
Solução:
S ~ Exp(): v.a. tempo de serviço por elemento
T: v.a. tempo de serviço de n elementos
Como o tempo de serviço por elemento distribui-se
exponencialmente, então o tempo de transmissão de n
elementos tem distribuição de Erlang.
Logo:
T ~ Erl(n,n)

n 1
F(t)  1 
k 0
E[T] = n/
( t ) k
k!
et ,
t0
Exemplo
n=1024 pacotes
=100 pacotes/seg
n
 E[T]   10.24

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
00
 
2
n

 0.32
n = 1024 pacotes
 = 100 pacotes/seg
5
10
15
E[T]=10.24 segs
20
T(segs)
Variáveis aleatórias
conjuntas e probabilidade
condicional
Variáveis aleatórias conjuntas

Cálculos de probabilidades envolvendo duas
ou mais variáveis simultaneamente

Função de distribuição de probabilidade
acumulada de X e Y:
F(a,b) = P{X  a,Y  b}
- < a,b < 
FX(a) = P{X  a} = P{X  a,Y  } = F(a,)
Variáveis aleatórias conjuntas

X e Y variáveis aleatórias discretas:
Função de massa de probabilidade conjunta
p(x,y) = P{X = x, Y = y}
pX(x) =
 p ( x, y )
y: p ( x , y )0
Variáveis aleatórias conjuntas

X e Y são variáveis aleatórias contínuas
conjuntas se existe uma função real f (x,y)
definida para qualquer reais x e y tal que para
quaisquer conjuntos A,B  
P{XA, YB} =

  f ( x, y )dxdy
BA
f(x,y) é a função de densidade de probabilidade
conjunta de X e Y
Variáveis aleatórias conjuntas

P{XA, YB} = P{XA, Y(-,)} =

=
  f ( x, y)dxdy
 A
onde
f X ( x) 

 f ( x, y)dy

Variáveis aleatórias independentes

X e Y são variáveis aleatórias independentes se
para qualquer a e b tem-se:
P{X  a,Y  b} = P{X  a}.P{Y  b}
F(a,b) = FX(a).FY(b)

X discreta: p(x,y) = pX(x).pY(y)
X contínua: f(x,y) = fX(x).fY(y)
Funções geradoras de momentos

X variável aleatória discreta:
f (t )  E[etX ]   etx p( x)
x

X variável aleatória contínua:

f (t )  E[etX ]   etx f ( x)dx

Funções geradoras de momentos
d
d tX
tX
tX
f (t )  E[e ]  E[ e ]  E[ Xe ]
dt
dt
'
f ' (0)  E[ X ]
d '
2 tX
f (t )  f (t )  E[ X e ]
dt
''
f (0)  E[ X ]
''
2
f
( n)
(0)  E[ X ]
n
Probabilidade condicional

Cálculo de probabilidades quando há
informações parciais
Probabilidade condicional
P
(
E

F
)
 P[E|F] =
P( F )

Caso discreto: função de massa de
probabilidade condicional
p ( x, y )
P
{
X

x
,
Y

y
}
pX|Y(x|y) = P{X=x|Y=y} =
=
pY ( y )
P{Y  y}

Se X é independente de Y, então:
px|y(x|y) = px(x)
Probabilidade condicional

Função de distribuição de probabilidade
condicional de X dado que Y = y:
FX |Y ( x | y )  P{ X  x | Y  y} 

 p X |Y (a | y)
a x
Valor esperado condicional de X dado que Y=y
E[ X | Y  y ]   x.P{ X  x | Y  y}   x. p X |Y ( x | y )
x
x
Probabilidade condicional

X e Y v.a.s independentes:
P{ X  x, Y  y}
p X |Y ( x | y )  P{ X  x | Y  y} 

P{Y  y}
P{ X  x}{Y  y}

 P{ X  x}
P{Y  y}
E[ X | Y  y ]  E[ X ]
Exemplo 1

X e Y v.a.s independentes com distribuição de
Poisson de parâmetros 1 e 2 respectivamente.
Calcular:
P{X=k |X + Y = n} = ?
E[X |X + Y = n] = ?
P{ X  k , X  Y  n}
P{X = k | X + Y = n} =
P{ X  Y  n}
P{X  k }P{Y  n  k }
P{X  k ,Y  n  k }
=
=
P{X  Y  n}
P{X  Y  n}
Exemplo 1
Como X+Y tem distribuição de Poisson de
parâmetro 1+2
1 k 2 n k
P{X = k | X + Y = n} =
k1n2 k
n!
k !(n  k )!( 1   2 ) n
=
e 1 e 2
k! (n  k )!
n
( 1 2 ) (1  2 )
e
n! nk
k
 n   1    2 
 

 
 k  1   2   1   2 
Exemplo 1
Interpretação:
P{X= k | X +Y = n} é uma v.a. Bi(n,
logo:
1
E[X | X +Y = n]= n
1   2
 1 ),
1   2
Exemplo 2
Sejam n + m experimentos independentes,
cada um sendo do tipo Be(p). Avaliar o número
esperado de sucessos nos n primeiros
experimentos, dado que nocorreram k sucessos
no total.
Sejam as seguintes v.a.’s:
1 se houve sucesso no i-ésimo exp.
Xi  
0 caso contrário
Y = número de sucessos nos (n+m) experimentos.

Exemplo 2
n
Problema: E[ X i | Y  k ]  ?
i 1
n
n
k
E[ X i | Y  k ]   E[ X i | Y  k ]  n
nm
i 1
i 1
k
pois E[ X i | Y  k ]  P{ X i  1 | Y  k} 
nm
Probabilidade condicional


Caso contínuo: se X e Y têm uma função de
densidade de probabilidade conjunta f(x,y),
então a função de densidade de probabilidade
condicional de X dado que Y = y é dada por
f ( x, y )
f X |Y ( x | y ) 
fY ( y )
Valor esperado condicional de X dado que Y=y
E[ X | Y  y ] 

 x. f X |Y ( x | y)dx

Exemplo

Sejam X e Y v.a.s tais que:
1  xy
f X |Y ( x | y)  y.e , 0  x  , 0  y  2
2
Problema:
E[e
X /2
| Y  1]  ?
1 x
e
f ( x,1)
x
2
f X |Y ( x | 1) 

e
fY (1)  1 e  x dx
0 2
E[e
X /2
 x/2
e
f
(
x
|
1
)
dx
X
|
Y
0
| Y  1]  
 x / 2 x
e
e
dx
0

2
Probabilidade condicional



Caso discreto:
E[X] = y E[X | Y = y] P{Y = y}
Caso contínuo:
E[X] =   E[X | Y = y] fY(y)dy

Em geral:
E[X] = E[E[X|Y]]
Probabilidade condicional

Prova do caso discreto
E[ X ]   x.P{ X  x}   x. P{ X  x, Y  y} 
x
x
y
  x.P{ X  x | Y  y} 
y x
P{ X  x | Y  y}
 
P{Y  y} 
P{Y  y}
y x
  x.P{ X  x | Y  y}P{Y  y} 
y x
  E[ X | Y  y ]P{Y  y} E[E[ X | Y ]]
y
Exemplo

Sejam N uma v.a. Ge(p) e Y a seguinte v.a.:
1 , primeiro é cara (probabilidade p)
Y
0 , primeiro é coroa (probabilidade 1-p)
E[N] = número médio de experimentos
realizados até obter-se a primeira cara = ?
Solução condicionando no resultado do primeiro
experimento:
E[N]=E[N|Y=1].P{Y=1} + E[N|Y=0].P{Y=0}
= p.E[N|Y=1]. + (1-p).E[N|Y=0]
E[N] = 1p.1 + (1-p).(1+ E[N])
E[N] = p1/p
