Redes de computadores:
Sub-camada de Access ao Meio(1)
Prof. Dr. Amine BERQIA
[email protected]
http://w3.ualg.pt/~bamine /
PROBLEMA DA DISTRIBUIÇÃO DE CANAIS:
DISTRIBUIÇÃO ESTÁTICA DE CANAIS EM LANs E MANS(1)
A forma tradicional (companhia
telefones ) de alocar um único
canal é de Multiplexagem por
Divisão de Frequência. FDM
funciona bem para número
limitado e fixo de utilizadores.
Ineficiente dividir em número fixo
de bocados. Podem não ser
todos usados, ou pode precisar
mais. Não controla “burstiness”.
T = tempo médio de atraso
C = capacidade (bps)
1
T = ---------mC - l
l = ritmo de chegada
1/ m = comprimento médio
PROBLEMA DA DISTRIBUIÇÃO DE CANAIS:
DISTRIBUIÇÃO ESTÁTICA DE CANAIS EM LANs E MANS(2)
Se dividir este canal em N sub-canais, cada um com
capacidade C/N. A taxa de entrada em cada um dos canais
N é A/N. Portanto
1
N
T(fdm) = ----------------- = ------------ = NT
m(C/N) - l /N
mC - l
PROBLEMA DA DISTRIBUIÇÃO DE CANAIS:
DISTRIBUIÇÃO DINÂMICA DE CANAIS (1)
Possíveis suposições subjacentes :
Modelo de Estação:
Assume que cada uma de N" estações" (geradora de pacotes) produzem quadros
independentemente. A probabilidade de produzir um pacote no intervalo dt é de l
dt onde l é a taxa de chegada constante. Esta estação não gera mais nenhum
quadro novo até que o anterior é transmitido.
Suposição de Canal Único :
Há apenas um canal; todas as estações são equivalentes e podem enviar e receber
naquele canal.
Suposição de colisão:
Se dois quadros se sobrepõem de alguma forma no tempo, então isso é uma
colisão. Qualquer colisão é um erro, e ambos os quadros devem ser
retransmitidos. A Colisão é o único erro possível.
PROBLEMA DA DISTRIBUIÇÃO DE CANAIS:
DISTRIBUIÇÃO DINÂMICA DE CANAIS (2)
Tempo Contínuo -
Não há nenhum" relógio grande no céu" para gerir a transmissão. O tempo não
existe em blocos discretos.
Slotted Time (Tempo em fatias):
A Transmissão de quadros começa sempre no inicio duma fatia de tempo.
Qualquer estação pode transmitir em qualquer abertura (com uma possível
colisão.)
Carrier Sense (Percepção da Portadora) :
Estações conseguem aperceber-se se um canal está ocupado antes de o tentarem
utilizar
NOTA - isto não evita colisões, (LANs têm isto, redes de satélite não têm).
Protocolos Acesso múltiplo (1)
As Colisões funcionam bem para utilização baixa (não é provável que elas
aconteçam.) A Arbitragem (falaremos depois), funciona melhor em situações
de alta utilização.
ALOHA:
Desenvolvido no Havaí nos anos setenta.
ALOHA PURO :
Todas as estações podem transmitir sempre que quiserem. Quadros que
colidem são destruídos. O remetente sabe se seu quadro foi destruído, e nesse
caso espera um tempo randomico e então retransmite.
1. QUALQUER sobreposição é uma colisão.
2. Melhor eficiência se quadros são do mesmo tamanho.
3. MAS, o qual é a eficiência?.
Aloha PURO (1)
• S =num. de quadros a
transmitir. Em unidade de
tempo de quadro a quadro de
forma que 0 < S < 1. (Qual é o
significado de tempo de
quadro usado aqui??)
• G = S + quadros
retransmitidos devido a
colisões anteriores.
• P0 = probabilidade dum
quadro não sofrer nenhuma
colisão.
• S = P0 X G
Utilize a Figura para determinar
vulnerabilidade de colisão.
PURO Aloha (2)
A Probabilidade de que são gerados k
quadros durante um determinado
tempo de quadro (Poison distribution):
G k e-G
Pr[k] = -------------k!
Probabilidade de nenhum tráfico ser
iniciado durante o período vulnerável:
P0 = e-2G
assim sendo
Desempenho por tempo de quadro é
:
S = G e -2G
SLOTTED Aloha
Duplica a eficiência dividindo tempo em "ticks“. O envio ocorre
apenas no inicio do tick. Período vulnerável é 1/2 do caso Aloha
puro, assim sendo
S = G e-G
Veja o desempenho na página anterior. O melhor processamento
está em G = 1 quando
S = 0.37; slots vazios = Pr[0] = 0.37;
colisões = G - S = 0.26
CARRIER SENSE MULTIPLE ACCESS
PROTOCOLS(1):
É quando o remetente escuta antes de lançar algo no cabo. Colisão acontece quando uma estação ouvir
algo diferente do aquilo que enviou.
CSMA PERSISTENTE E NÃO PERSISTENTE :
CSMA persistente
A estação escuta. Se o estiver canal inactivo, transmite. Se há colisão, espera um tempo randomico e
tenta novamente. Se o canal estiver ocupado, espera até estar inactivo.
Se uma estação quer enviar E canal == ocioso
então envia.
Sucesso neste caso depende do tempo de transmissão - quanto tempo depois que o canal seja sentido
como inactivo, é que este fica inactivo (pode na realidade estar a caminho o outro pedido.)
CSMA Não persistente (equivalente a 0-persistent CSMA)
Igual ao anterior EXCEPTO, quando canal é sentido como ocupado, não continua a monitorizar para
até ficar livre. Espera um tempo randomico e então verifica novamente. Isto leva a que
1) melhor utilização e
2) atrasos mais longos que 1 - persistente.
CARRIER SENSE MULTIPLE ACCESS
PROTOCOLS(2):
CSMA Não persistente (equivalente a
CSMA 0-persistente) Igual ao anterior
EXCEPTO, quando canal é sentido como
ocupado, não continua a monitorizar para até
ficar livre. Espera um tempo randomico e
então verifica novamente. Isto leva a que
1) melhor utilização e
2) atrasos mais longos que 1 - persistente.
CSMA p-persistente [Para canais tipo slotted.]
Se pronto a enviar E canal == ocioso
então envia com probabilidade p,
e
com a diferença de probabilidade q = 1 - p
para a próxima slot.
CARRIER SENSE MULTIPLE ACCESS
PROTOCOLS(3):
CSMA COM DETECÇÃO DE COLISÕES:
CSMA/CD - usado nas LANs.
Quando uma estação detecta uma colisão, deixa de enviar, até mesmo se no
meio dum quadro.
Espera um tempo randomico e então tenta novamente.
O que é o intervalo de contenção – quanto tempo depois duma estação ter
enviado tem de esperar até saber que adquiriu controlo do canal? É duas
vezes o tempo para viajar à estação mais longínqua..
PROTOCOLOS Livres de
Colisões
Qual o comprimento dum pacote (ou qual o comprimento dum cabo para conter um pacote)
de 1500 bytes comprimento numa rede ethernet de 100 Mbps?
À medida que os cabos ficam mais longos e mais rápidos, os métodos mencionados acima
ficam menos eficientes. Portanto, …
• Protocolo de mapa de bits
Uma " slot de contenção”, subdividida em bits, permite a cada estação anunciar que quer
enviar. Depois do anúncio, todas as estações podem enviar em ordem de prioridade, e não
haverá nenhum luta pelo canal. Chamado "Protocolo de reserva“.
• Contagem regressiva binária
Na slot de contenção, cada estação coloca o seu ID. E feita uma operação OR entre todas.
Uma determinada estação sabe que ganhou porque mais nenhuma estação com intenção de
enviar teve um número mais alto que ela na slot. (Por Exemplo, 101101 OU 110011: A
estação 101101 sabe que perdeu na altura que envia o seu segundo bit - vê um" 1" no cabo
quando acaba de enviar um " 0“..
LIMITED-CONTENTION PROTOCOLS
• Técnicas de colisão funcionam bem para utilização baixa (não é provável
que eles aconteçam.) Arbitragem funciona melhor em alta utilização.
Este método é a melhor destas técnicas.
• Divide as estações em grupos. Estipula que apenas os membros do grupo
0 podem arbitrar para a slot 0, membros do grupo 1 para a slot 1, etc.
Funciona bem porque reduz a contenção sentida por qualquer estação
particular.
• Se quisermos um método que terá muitos membros por grupo a baixa
contenção, e poucos (ou um) membro a contenção alta. Pode usar uma
pesquisa binária para fazer isto.