Redes de Computação Industrial
PROTOCOLOS MAC
DETERMINÍSTICOS
Í
Gerson Barboza, [Link].
CX3C
gersonbarboZa@[Link]
Este material foi elaborado pelo professor Gerson Barboza e Pedro Vieira para o curso de redes de computação
ind strial nas instituições
industrial instit ições em que
q e lecionam.
lecionam O uso
so do presente material só é autorizado
a tori ado dentro da finalidade
específica do presente curso. Sua utilização, portanto, fora dessa finalidade específica constitui violação de
propriedade intelectual.
Revisão: 10/03/2011
2
Desligue a luz ao sair da sala.
3
4
Pensamento...
“Só as pessoas
inteligentes
procuram,
para auxiliá-
las pessoas
las,
mais
inteligentes
do que elas.”
(Baltasar Gracian
y Morales)
5
Pensamento...
Sua família produz,
produz em
um ano, um elefante de
lixo.
lixo
6
7
PROLEGÔMENOS
8
O Modelo de Referência OSI
CPU 1 Ligações
g ç lógicas
g CPU 2
7. Aplicação 7. Aplicação
6 Apresentação
6. 6 Apresentação
6.
5. Sessão 5. Sessão
4 Transporte
4. 4 Transporte
4.
3. Rede 3. Rede
2 Enlace
2. E l 2 Enlace
2. E l
1. Física 1. Física
Transmissão Física (Bit)
Camadas
C d orientadas
i t d a conexão ã
Camadas orientadas a aplicação
9
O RM-OSI e a Camada MAC
RM OSI
RM-OSI IEEE
802.1
LLC 802 2
802.2
ENLACE
MAC
FÍSICO 802.3 802.4 802.5 802.6
A camada
d MAC (IEEE) é a parte
t iinferior
f i d da
camada de enlace (RM-OSI)
10
Classificação
ç dos Protocolos MAC
Classificação dos Protocolos MAC
Alocação fixa:
• alocam o meio às estações por determinados intervalos de
tempo, independentemente de haver ou não necessidade de
acesso (ex.: TDMA = Time Division Multiple Access);
Alocação aleatória:
• permitem
it acesso aleatório
l tó i das
d estações
t õ ao meio i (ex.:
( CSMA =
Carrier Sense Multiple Access). Em caso de envio simultâneo por
mais de uma estação, ocorre uma colisão e as estações
envolvidas tem que transmitir suas mensagens após a resolução
do conflito resultante (protocolos de contenção);
11
Classificação
ç dos Protocolos MAC
Classificação dos Protocolos MAC
Alocação controlada:
• cada estação tem direito de acesso apenas quando de posse de
uma permissão, que é entregue às estações segundo alguma
seqüência predefinida (ex.: Token-Passing, Master-Slaves);
Alocação por reserva:
• para poder usar o meio, as estações tem que reservar banda com
antecedência enviando pedidos a uma estação controladora
antecedência,
durante um intervalo de tempo pré-destinado e este fim (ex.:
CRMA = Cyclic Reservation Multiple Access);
Híbridos:
• consistem de 2 ou mais das categorias anteriores.
12
Classificação
ç dos Protocolos MAC
Classificação dos Protocolos MAC
Classificação com relação ao comportamento
temporal:
• protocolos
p determinísticos: caracterizados p pela
possibilidade de definir um tempo limite para a entrega
de uma dada mensagem g ((mesmo q
que somente em
pior caso);
• protocolos não determinísticos: tempo de entrega
não determinável (aleatório ou probabilístico).
13
O PROTOCOLO CSMA
14
CSMA Persistente e Não
Persistente
CSMA 1-persistente
1 persistente, p-persistente
p persistente e não persistente
CSMA = Carrier Sense Multiple Access (Acesso Múltiplo por
Detecção
ç de p portadora))
baseia-se no conceito de escuta do meio de transmissão
para a seleção
p ç do direito de acesso a este.
CSMA p-persistente: estação que quer enviar dados escuta
meio. Se canal livre, envia quadro com probabilidade “p”.
Senão, aguarda na escuta até que o meio esteja livre.
Caso particular: p=1.
CSMA não persistente: idem anterior, mas se canal
ocupado, estação espera um período de tempo aleatório e
esc ta o canal no
escuta novamente.
amente
15
CSMA Persistente e Não
Persistente
CSMA 1-persistente:
p faz melhor uso da banda,, mas tem
grande chance de gerar colisões
CSMA não persistente: faz pior uso da banda, mas tem
menor probabilidade de gerar colisões
CSMA p-persistente (0<p<1): compromisso entre as
soluções anteriores.
np
P-p
1-p
tempo
16
Rendimento do CSMA
Rendimento do CSMA:
Probabilidade de colisão cresce
exponencialmente com tráfego
Tráfego é influenciado por dois fatores: tráfego
individual de cada estação (bits por segundo) e
número de estações na rede
17
Rendimento do CSMA
Probabilidade
de colisão
Tráfego x número estações
18
O Protocolo CSMA
Exemplo de transmissão com CSMA
A estação 2 inicia a transmissão com
o canal livre
A estação 4 escuta o canal ocupado e evita transmitir,
já que o canal está sendo utilizado pela estação 2
Quando o canal é liberado, a estação 4 inicia a
transmissão
O mesmo ocorre depois
d i com a estação
t ã 2 querendo d
transmitir novo quadro
19
CSMA/CD
20
CSMA/CD
/
CSMA/CD: Carrier Sense Multiple Access with Collision
Detection
A primeira estação que detectar a colisão interrompe transmissão,
reiniciando a após um tempo aleatório
reiniciando-a
Resultados:
Colisões detectadas num tempo
p mais curto
Redução do desperdício do canal – maior disponibilidade
Retransmissões persistentes ou não-persistentes
Detecção de colisão:
Redes cabeadas: medição da potência do sinal, comparação dos
sinais transmitidos e recebidos
Redes sem fio: receptor desligado enquanto transmitindo –
solução: CSMA/CA (with Collision Avoidance)
21
CSMA/CD
/
Exemplo de transmissão com CSMA/CD: colisão
As estações 2 e 5 começam a transmissão quase
simultaneamente colisão
A colisão é detectada por ambas as estações, que
interrompem a transmissão
Cada estação inicia um contador randômico
A estação 2 retransmite e o protocolo CSMA continua
agindo
i d normalmente
l t
22
CSMA/CD
/
Quanto tempo é necessário para detectar uma colisão?
No pior caso: o dobro do tempo máximo de propagação
• Chamado tempo para dominação do canal (seize time)
A inicia a transmissão
B inicia a transmissão
B detecta a colisão
A detecta a colisão
Restrições de tamanho mínimo de quadro (tempo de
dominação) e tamanho máximo de cabo (para o cálculo
anterior)
23
CSMA/CD
/
emissor receptor
emissor emissor
24
CSMA/CD
/
início
Quando
começar a
retransmitir não
Estação
depois de uma Pronta?
colisão?
li ã ?
Algoritmo de sim
Novo
escolha: nc = 0 Quadro?
exponential
não
backoff
Não aumenta o Sîlêncio
Sî ê i nc++
tempo depois de na Rede?
não
limite = 2nc-1
10 tentativas sim
Wait=random
Desiste depois transmitir [0,limite]
de 16 tentativas
não sim
Colisão?
25
Característica Temporal do
CSMA/CD
Métodos de acesso CSMA convencionais: tempo de
reação não pode ser exatamente determinado (não
determinístico).
)
Não se sabe de antemão:
se haverão colisões;;
quantas colisões seguidas podem ocorrer;
o tempo
p ((aleatório)) de espera
p em caso de colisão.
Tempo de espera é randomizado segundo
algoritmo
g BEB ((Binary
y Exponential
p Backoff))
Portanto o CSMA/CD,
CSMA/CD por si só,
só não
garante determinismo.
26
PROTOCOLOS MAC
DETERMINÍSTICOS
27
Protocolos MAC Determinísticos
Métodos de acesso determinísticos
têm tempo de resposta limitado e determinável
( menos no pior
(ao i caso).
)
Podem ser classificados em:
métodos com comando centralizado (ex.: Mestre-
Escravos árbitro de barramento)
Escravos,
métodos com comando distribuído (ex.: Token-
Passing variantes deterministas do CSMA)
Passing, CSMA).
28
COMANDO CENTRALIZADO
29
Comando Centralizado: Mestre-
Escravo
MESTRE
escravo
escravo escravo
escravo escravo
escravo escravo
escravo
30
COMANDO DISTRIBUÍDO
31
Comando Distribuído: Token-Bus
receptor
f h
ficha emissor
32
Comando Distribuído: Token-Ring
g
33
COMANDO DISTRIBUÍDO
CSMA/NBA
34
Comando Distribuído: Forcing
Headers (CSMA/NBA)
Variante determinística do CSMA ((CSMA/NBA = CSMA with
Nondestructive Bitwise Arbitration).
Estações enviam bit a bit um identificador da mensagem,
que define prioridade da mesma
mesma.
Cada mensagem tem que ter prioridade diferente das
demais.
Se todos os bits do identificador são 0, prioridade máxima.
Camada física executa AND sobre cada bit enviado ao
barramento (CD ativada ao enviar um 1 e desativado ao
enviar um 0).
Transmissão interrompida quando um 1 é enviado e ocorrer
colisão (0 é lido)
lido).
Se identificador transmitido até o fim sem colisão, resto da
mensagem
g é enviado.
35
Comando Distribuído: Forcing
Headers (CSMA/NBA)
100 dados
Header do frame
Frame a enviar
Nó 4
Nó 0 Nó 1 Nó 2 Nó 3
000 dados 001 dados 010 dados 011 dados
36
Comando Distribuído: Forcing
Headers (CSMA/NBA)
Estação possuidora da mensagem de alta
prioridade terá que esperar ao menos o envio
de uma mensagem de prioridade menor para
tomar o barramento para si novamente
A estação
t ã que envioui a mensagem,
mesmo que tenha havido uma colisão, a
quall não
ã foi
f i por ela
l percebida,
bid não
ã
precisou reiniciar a mensagem, uma vez
que a mensagem de d prioridade
i id d maior
i nãoã
é corrompida.
37
COMANDO DISTRIBUÍDO
COMPRIMENTO DE PREÂMBULO
38
Comando Distribuído:
Comprimento de Preâmbulo
Variante determinista de CSMA/CD
A cada mensagem é associado um preâmbulo com
comprimento diferente
diferente, que é transmitido com CD
desativada.
A messagem com o maior preâmbulo tem a
prioridade mais alta
Após término de envio do preâmbulo, CD reativada
Se detectou colisão, existe outra mensagem mais
prioritária sendo enviada e estação fica a espera de
meio livre.
39
Comando Distribuído:
Comprimento de Preâmbulo
Preambulo do frame
Frame a enviar
Nó 4
Nó 0 Nó 1 Nó 2 Nó 3
40
Comando Distribuído:
Comprimento de Preâmbulo
41
COMANDO DISTRIBUÍDO
CSMA/DCR
42
Comando Distribuído: CSMA/DCR
/
CSMA with Deterministic Collision Resolution
determinismo garantido através de busca em árvore binária
balanceada
prioridades são atribuídas a cada estação => “Índices”
cada estação deve conhecer:
status do barramento:
• livre
• ocupado
p com transmissão
• ocupado com colisão
seu próprio índice
número total de índices consecutivos alocados às fontes (Q)
tamanho da árvore binária q = menor potência de 2 maior ou
igual
g a Q ((ex.: Q = 12, q = 16))
43
Comando Distribuído: CSMA/DCR
/
operação como CSMA/CD até colisão
em caso de colisão, iniciado período de resolução
por busca em árvore binária => “época”
estações envolvidas se auto-classificam em dois grupos:
Winners (W) ou Losers (L):
• W = índices entre [0,q/2[
• L = índices entre [q/2,
[q/2 q]
estações do grupo W tentam nova transmissão
se nova colisão
colisão, nova divisão em grupos:
• W = [0,q/4[
• L = [q/4, q/2]
44
Comando Distribuído: CSMA/DCR
/
se não ocorrer nova colisão ((só sobrou uma estação
ç no grupo
g p W), )
estação transmite seu frame de dados
estações do grupo L desistem e aguardam término de transmissão
bem sucedida de outro nó seguida
g de meio livre
se grupo W vazio, busca revertida => nova subdivisão de nós a partir
do último grupo L:
• W = [q/2,
[q/2 3q/4[
• L = [3q/4, q]
Época encerrada quando todas as estações envolvidas na
colisão original conseguiram transmitir seus dados
tempo de duração de uma época pode ser calculado =>
determinismo !
seqüência de concessão de direito de acesso ao meio =
q
seqüência de índices crescentes => nós mais p
prioritários
transmitem primeiro !
45
Comando Distribuído: CSMA/DCR
Exemplo
Índice 2 Índice 3 Índice 5
Í di 12
Índice Í di 14
Índice Í di 15
Índice
6 estações
t õ d de uma rede
d com 16 ffontes
t enviam
i fframes
simultaneamente
Índices de cada estação conforme figura acima
Q = 16
q = 16 (24)
altura da árvore binária = log2 16 = 4
46
Comando Distribuído: CSMA/DCR
Exemplo
[0,15]
[0 15]
1
[0,7] [8 15]
[8,15]
2 9
[0,3] [4,7] [8,11] [12,15]
3 6 10 13
4 5 7 8 11 12 14 15
[2,3] [4,5] [6,7] [8,9] [10,11] [12,13]
Árvore binária balanceada completa para Q = 16
47
Comando Distribuído: CSMA/DCR
Exemplo
0C
2,3,5,12,14,15
W= 2,3,5
L=12,14,15
1C 8C
2,3,5 12 14 15
12,14,15
W= 2,3 W=
L=5 L=12,14,15
2C 7T 9V 10 C
2,3 5 12,14,15
W= W= 12
L=2,3 L=14,15
3V 4C 12 C
2,3 11 T
12 14,15
W=2 W= 14
L=3 L=15
5T 6T
2 3 13 T 14 T
14 15
Evolução
ç do algoritmo
g
48
Comando Distribuído: CSMA/DCR
Exemplo
O tempo
p até o inicio da transmissão da fonte com índice 5
será:
4 colisões + 1 vazio = 5. slot-time
2 transmissões = 2.(tamanho
2 (tamanho quadro em slot-times)
slot times)
Assumindo que cada quadro tem um tamanho fixo de 6 slot-
times e considerando 1 slot-time como 40 microssegundos,
o tempo para início da transmissão da mensagem da fonte
com índice 5 seria:
Tinicio 5 = 5.40 + 2.6.40 = 680 microssegundos (não é ainda pior
caso)
O tempo de duração total da época será:
7 colisões = [Link]-time
2 vazios = 2. slot-time
6 transmissões = 6 .(tamanho do quadro em slot-times)
Assumindo 1 slot-time
slot time = 40 microssegundos:
T época = 7.40 + 2.40 + 6.6.40 = 1800 microssegundos = 1.8
49
Comando Distribuído: CSMA/DCR
/
Cálculo do tempo de pior caso pode ser formalizado
como segue...
Seja:
F(v) = número de ramos da árvore binária percorridos
por uma mensagem g proveniente de um nó com índice v
q = menor potência de 2 maior ou igual ao maior índice
disponível
S(v)
S( ) = número de potências de 2 contidas em v
s = 1 slot-time (2 vezes o tempo de propagação do sinal
na rede)
M= tempo máximo de transmissão da uma mensagem no
meio físico ((depende
p do comprimento
p da mensagem
g em
bits e da taxa de transmissão)
50
Comando Distribuído: CSMA/DCR
/
Para uma mensagem participando de uma dada época,
temos que:
F (v) = log2 q + v - S(v)
Tespera
T (v)
( ) = F(v).s
F( ) + v.M M
Para o exemplo anterior, tomando uma mensagem da
estação com índice 5, temos:
q =16
v =5
S(5) = 2 (5 = 2**2+2**0)
F (5) = log2 16 + 5 - 2 = 7
Tespera (5) = 7.s + 5.M
Assumindo s = 40 microssegundos e M = 6.s = 240
microssegundos, obteremos para o pior caso de tempo de
espera da
d mensagem d da ffonte
t com índice
í di 5 o valor
l dde 1480
microssegundos
51
Comando Distribuído: CSMA/DCR
/
O tempo de duração da época
época, no pior caso
caso, é dado por:
• Tépoca = F(q
F(q-1)
1).s
s+Q
Q.M
M
Para uma mensagem que chega a fila de emissão de uma
fonte com índice v em um instante qualquer, o pior caso de
tempo
p de espera
p é maior, p
pois a nova mensagem
g p
pode
chegar na fila imediatamente após o inicio de uma época, da
qual ela ainda não faz parte.
Neste caso, o pior caso do tempo de espera será dado por:
• T max espera (v) = Tépoca + F(v).s + v.M
52
"Aquele
Aquele que não duvida de
nada, não sabe nada."
(Ditado Grego)
53
Mate sua dúvida...
54