Aulas 15 & 16
Redes Locais
Eytan Modiano
MIT
1
Acesso Múltiplo com Monitoração de Portadora
(Carrier Sense Multiple Access - CSMA)
• Em certas situações os nós podem ouvir uns aos outros escutando o
canal.
– Monitoração da portadora (“Carrier Sensing”).
• CSMA: Versão mais refinada do Aloha
– Os nós escutam o canal antes de transmitir:
• Canal não ocupado ⇒ Transmite;
• Canal ocupado ⇒ Espera.
– Quando os nós que estão aguardando o acesso voltam a tentar
novamente?
• Quando o canal volta a ser livre os nós que já tinham tentado
anteriormente tentam a transmissão com probabilidade qr = 1.
– Protocolo Persistente, qr = 1
– Protocolo não persistente, qr < 1
2
CSMA
• Seja τ = atraso de propagação máximo do canal
– Quando um nó inicia/para a transmissão todos os nós irão perceber
que o canal esta ocupado/livre após o atraso de propagação.
• Para iniciar o entendimento, veja o sistema como composto por “minifatias” de duração igual ao atraso máximo de propagação.
– Normalize a duração da mini-fatia para β = τ/Dtp e duração do
pacote = 1.
•
Sistemas reais não são fatiados, mas este sistema hipotético simplifica
a análise e o entendimento do CSMA.
3
Regras Para o CSMA Fatiado
•
•
•
Quando um novo pacote chega:
– Se a mini-fatia atual esta livre, inicie a transmissão na próxima mini-fatia;
– Se a mini-fatia atual esta ocupada, o nó se tenta retransmitir mais tarde;
– Se uma colisão ocorre, os nós envolvidos na transmissão tentam a
retransmissão mais tarde.
Os nós que aguardam a retransmissão, tentam a transmissão após uma minifatia vazia com probabilidade qr <1 (não-persistente).
– Tentativas de transmissão são feitas somente após uma mini-fatia livre
(ou vazia);
– Cada “período ocupado” (sucesso ou colisão) é seguido por uma fatia
vazia antes que uma nova transmissão possa se iniciar.
O tempo pode ser dividido em duas épocas:
– Um pacote bem sucedido seguido por uma mini-fatia vazia (duração =
β+1);
– Uma colisão seguida por uma mini-fatia vazia A (duração = β +1);
– Uma mini-fatia vazia (duração = β).
4
Análise do CSMA
• Seja o estado do sistema o número de nós que tentam retransmitir.
• Seja o instante em que há uma transição de estado o fim das faixas
vazias.
– Seja T(n) = tempo médio entre transição de estado quando o
sistema esta no estado n.
T(n) = β + (1 - e-λβ (1-qr)n)
Quando qr é pequeno (1 - qr)n ~ e-qrn ⇒T(n) = β + (1-e-λβ−nqr)
• No inicio de cada época, cada nó que deve retransmitir , transmite com
probabilidade qr.
• Novas chegadas durante a fatia vazia anterior são também transmitidas.
• Com n nós tentando a retransmissão, o número dos pacotes que tentam
a retransmissão no início da época é aproximadamente Poisson com
taxa.
g(n)=λβ+nqr
5
Análise do CSMA
• A probabilidade de sucesso (por época) é:
Os = g(n)e-g(n)
• A duração espera apara uma época é aproximadamente:
T(n)~β+(1-e-g(n))
• Portanto a taxa de sucesso por unidade de tempo é:
λ < taxa de saída =
g(n)e−g(n)
β +1−e−g(n)
6
Vazão Máxima do CSMA
• O valor ótimo de g(n) pode ainda ser obtido por:
g ( n) ≈ 2 β
λ<
1
1 + 2β
• Há um compromisso entre faixas vazias e tempo perdido nas colisões.
• Alta vazão quando β é pequeno.
• Problemas de estabilidade similares ao do Aloha (menos crítico).
7
CSMA Não Fatiado
• CSMA fatiado não é prático.
– Dificuldade em se manter sincronização;
– Mini-faixas são úteis para entender mas não são para o desempenho
do CSMA.
• CSMA não fatiado terá uma menor vazão devido ao aumento na
probabilidade de colisão.
• CSMA não fatiado tem um menor valor efetivo de β do que o CSMA
fatiado.
– Essencialmente β torna-se uma média em vez de atraso de
propagação máximo.
8
CSMA/ CD e Ethernet
WS – Estações
de trabalho
•
•
CSMA com a capacidade de detecção de colisão (CD)
– Os nós são hábeis em detectar colisões.
– Após a detecção de colisão o nó para a transmissão.
• Reduz a quantidade de tempo perdido com as colisões.
Protocolo:
– Todos os nós escutam o canal antes da transmissão.
– Quando um nó te pacote para transmitir:
• Canal vazio ⇒ transmite;
• Canal ocupado ⇒ espera por um tempo aleatório (binary exponential
backoff).
– Se um nó que estiver transmitindo detectar colisão para a transmissão:
• Tenta novamente após um atraso aleatório.
9
Tempo Para Detectar a Colisão
• Uma colisão pode ocorrer enquanto o sinal se propaga entre os dois
nós.
• Irá tomar um atraso de propagação adicional para ambos os usuários
detectar a colisão e parar de transmitir.
• Se τ é o máximo atraso de propagação no cabo então se uma colisão
ocorre, irá demorar 2τ segundos para que todos os nós envolvidos na
colisão detectem a colisão e parem a transmissão.
10
Modelo Aproximado Para o CSMA/CD
• Aproximação simplificada para melhor entendimento.
• Considere um sistema fatiado com mini-fatias de duração 2τ.
• Se um nó inicia a transmissão no início de uma mini-faixa, no final da
mini-faixa pode ocorrer:
– Não ocorreu colisão e o resto da transmissão não será interrompido.
– Uma colisão aconteceu, mas ao final da mini-faixa o canal esta
livre novamente.
• Portanto uma colisão afeta no máximo uma mini-faixa.
11
Análise do CSMA/CD
• Suponha N usuários e que cada um tente a transmissão durante uma
mini-faixa livre com probabilidade p.
– P inclui novas chegadas e retransmissões i.
()
P(I usuários tentam) = N P i (1 − P) N −i
i
P(exatamente 1 tentativa) = P(sucesso)= NP(1-P)N-1
Para maximizar P(sucesso),
d
[ NP(1 − P) N −1 ] = N (1 − P) N −1 − N ( N − 1) P(1 − P) N − 2 = 0
dp
1
N
⇒ Taxa media de tentativas uma por faixa.
⇒Observe a semelhança com o Aloha fatiado..
⇒ Popt =
12
Análise do CSMA/CD, continuação
1

N-1
1
−
P(sucesso) =NP (1-p) = 

N


N −1
1
Ps= limite (N→ ∞) P(sucesso) =
e
Seja X =Número médio de faixas por transmissão bem sucedida
P(X =i)= (1-Ps)i−1 Ps
⇒ E[ X ] =
1
=e
Ps
• Uma vez que uma mini-faixa tenha sido capturada, a transmissão
continua sem interrupção.
• Novas tentativas de transmissão irão começar na próxima mini-faixa
após o fim da transmissão do pacote corrente.
13
Análise do CSMA/CD, continuação
• Seja S = Tempo médio entre transmissões bem sucedidas
Mini-faixa livre/colisão
S = (e-1)2τ+DTp+τ
Tempo médio antes do
inicio da próxima mini-faixa
Tempo para transmitir um
pacote
• Eficiência = DTp / S = DTp / (DTp +τ + 2τ (e-1))
• Seja β = τ / DTp => Eficiência ≈1/(1+4,4β) = λ < 1 / (1 + 4,4β)
• Compare com o CSMA sem CD onde λ <
1
1 + 2β
14
Notas Sobre o CSMA / CD
• Pode ser visto como um sistema com reserva onde as mini-faixas são
usadas para fazer reserva para faixa de dados.
• Neste caso, Aloha é usado para fazer reserva durante as mini-faixas.
• Uma vez que o usuário captura uma mini-faixa continua a transmissão
sem interrupções.
• Na prática naturalmente não existem mini-faixas;
– Impacto mínimo no desempenho mas análise é mais complexa.
15
Exemplos: CSMA/CD
• Exemplo (Ethernet)
– Taxa de transmissão = 10Mbps
– Comprimento do pacote = 1000 bits, DTp = 10-4sec
– Distância = 1 milha, τ = 5x10-6sec
– Îβ = 5x10-2 e E = 80%
• Exemplo ( Satélite GEO)
– atraso de propagação 1/4 segundo
– β = 2,500 e E ~0%
• Conveniente somente para cenários com baixos valores de atraso de
propagação.
• Como a Ethernet é estendida para 100Mbps?
• Como a Ethernet é estendida para 1Gbps?
16
Rede em Anel (Token Rings)
•
•
•
•
Foi desenvolvida pela IBM no início dos 1980 ’s.
Uma seqüência de bits,
– Token circula ao longo do anel:
token ocupado: 01111111;
token livre: 01111110.
Quando um nó quer transmitir:
– Espera por um token livre;
– Remove o token do anel (o substitui por token ocupado);
– Transmite a mensagem;
– Uma vez feita a transmissão e coloca o token livre no anel;
– Os nós devem armazenar 1 bit de dados de modo que um token livre
possa ser alterado para token ocupado.
Token ring é basicamente um system polling;
Token faz o polling.
17
Entrega do Token
• Entrega após transmissão
– Nó entrega o token logo após ter completado a transmissão dos seus
pacotes.
– O próximo nó pode usar o token após um pequeno atraso de
propagação.
• Entrega após recepção
– Nó entrega o token somente após seu próprio pacote tenha voltado
para ele.
Serves como um simples mecanismo de confirmação de recebimento.
18
Transmissão do Pacote
(entrega após transmissão)
• Quando não transmitem seus próprios pacotes os nós retransmitem
tudo o que recebem.
• Após receber um token livre um nó pode iniciar a transmissão de um
novo pacote (descarta bits que estejam recebendo).
• Após um nó ter enviado um pacote e o token livre, envia tokens livres
até:
– Receber o pacote enviado, ou
– Receber um token ocupado.
intervalo
inativo
intervalo
inativo
19
Transmissão do Pacote
• Em muitas implementações (incluindo a IEEE-802.5, mas não a
FDDI), um nó espera para checar o retorno de seu pacote antes de
enviar o token livre.
– Isto aumenta o tempo de transmissão do pacote de um atraso de ida
e volta.
20
Análise do Atraso
• O sistema pode ser analisado utilizando os resultados da reserva multiusuário.
• Sistema exaustivo - nós esvaziam suas filas antes de passar o token
para o próximo o nó.
• Suponha m nós cada um com chegadas de Poisson com taxa λ/m.
• Seja v = o atraso médio de propagação e da transmissão do token.
• O sistema pode ser visto como um sistema de reservas com m usuários
e intervalo médio de reserva (veja os resultados do sistema com
reserva).
λE[ X 2 ] + v(m − ρ )
W=
2(1 − ρ )
ρ = m ( λ / m ) E[ X ] = λ E [ X ]
• Observe que 100% de vazão pode ser obtida no sistema exaustivo.
21
Análise da Vazão
(Não-Exaustivo)
• Sistemas comporta com serviço limitado – cada nó é limitado em
enviar um pacote por vez.
– Quando o sistema é muito carregado os nós são sempre ocupados e
tem pacotes para transmitir.
• Suponha que cada nó transmite um pacote e passa o token para o
próximo nó;
– Vi = tempo de propagação e de transmissão do token entre nós
(tempo de transmissão geralmente é desprezível)
• A quantidade de tempo para transmitir N pacotes é:
TN = N * E[X] + V1 + V2+…+VN = N * E[X] + N * E[V]
λ < N*E[X] / (N*E[X] +N*E[V]) = 1 / (1+E[V] / E[X])
• Compare com o CSMA/CD, mas observa que V é o atraso entre dois
nós e não o máximo atraso na fibra.
22
Análise da Vazão
(entrega do token após recepção)
• Os nós entregam o token somente após recebê-lo
• Suponha ainda que cada nó envie um pacote por vez.
• Tempo total para transmitir um pacote é de:
T = E[ X ] + V1 + V2 + ... + Vm + Vi
Tempo para transmitir o token
“m” nós no anel
T = E[ X ] + (m + 1) E[V ] ⇒ λ <
E[ X ]
1
=
T
(1 + (m + 1) E[V ] / E[ X ])
23
Análise do Atraso
• Entrega após transmissão
– Sistema Comporta Parcial com serviço ( sessão 3.5.2)
λE[ X 2 ] + v(m + λE[ X ])
W=
2(1 − λE[ X ] − λv)
• Entrega após recepção
– Problema 4.27
– Tempo de ida e volta adicional pode ser adicionado ao tempo de
transmissão.
λE[ X 2 ] + 2mv + m 2 v 2 + v(m + λE[ X ] + mv)
W=
2(1 − λ ( E[ X ] + (m + 1)v))
24
Problemas Com o Token Ring
• Igualdade: Pode um nó segurar um token por um longo período.
– Solução: tempo máximo de retenção do token.
• Falha no Token: Tokens podem ser criados ou destruídos pelo ruído.
– Solução distribuída:
• Nós são permitidos de reconhecer a perda de um token e criar
um novo token.
• Colisões podem ocorrer quando dois ou mais nós criam um
novo token ao mesmo tempo ⇒ são necessários algoritmos de
resolução de colisão.
• Falha do nó: Desde que cada nó deve enviar todos os dados que recebe,
a falha de um nó interrompe a operação do anel.
• Padrão Token Ring: IEEE 802.5.
25
FDDI
•
•
•
•
•
Fiber Distributed Data Interface - FDDI é um padrão de rede local em anel
em fibra óptica a 100Mbps.
FDDI utiliza dois anéis em sentido contrários.
– Uma falha pode ser isolada comutando de um
anel para outro.
O token é entregue após a transmissão.
• No tempo de retenção do token
Limite superior no tempo entre visitas do tokens em
um nó,
– Suporta atrasos garantidos,
– Impõe limites quanto ao tamanho do anel (distância entre nós, número de
nós);
FDDI foi projetado para ser uma tecnologia de rede metropolitana ou para
ser utilizada dentro de um campus.
26
Token em Barramento (Token Buses)
• Pacote de controle especial serve como token.
• Os nós devem ter o token para transmitir
• Token é passado de nó para nó em uma determinada ordem
– Conceitualmente, um token bus é o mesmo que um token ring.
– Quando um nó termina a transmissão, envia um token vazio (livre).
para o próximo nó (endereçando o pacote de controle de forma
apropriada).
– Semelhante ao sistema polling.
• Problemas
– Menos eficiente que o token ring devido a maiores atrasos de
transmissão de pacotes e maiores atrasos de propagação.
– Precisa de um protocolo para acessar e deixar o barramento.
27
Tokens Implícitos
• O token livre em um token bus pode ser substituído pelo silêncio.
• O próximo nó inicia a transmissão de um pacote após escutar que o
barramento se tornou silencioso.
• Se o próximo nó não tem pacote pata.
•
Transmitir, os sucessivos nós iniciam com atrasos sucessivos cada vez
maiores.
• Se o atraso de propagação no barramento é muito menor que o tempo
de transmissão de um token, isto pode reduzir o atraso.
• Este esquema é usado em redes locais sem fio (IEEE 802.11) e é
conhecido como CSMA/CA (collision avoidance).
28
Distributed Queue Dual Bus - DQDB
• Redes Metropolitanas usando dois barramentos unidirecionais em cada
sentido a 150Mbps.
• Todos os quadros são de mesmo comprimento (53 bytes); quadros
vazios são gerados nos pontos finais dos barramentos e são
preenchidos pelos nós “on the fly”.
• Um nó usa o barramento que move os pacotes para a direita para enviálos aos nós que estão à direita e vice-versa (no outro barramento) para
os nós que estão á sua esquerda.
• DQDB foi padronizado como IEEE 802.6 e foi projetado para ser
compatível com o ATM.
29
Reservas DQDB
• Algoritmo Greedy: Cada nó usa uma fatia livre quando tem algo para
transmitir,
– Portanto uma eficiência de 100% é possível.
• O problema com esta solução trivial é quanto á igualdade de uso - nós
no final do barramento podem ser “mortos”.
• DQDB usa um sistema de reserva onde nós enviam pedidos (no sentido
upstream – nó fim do barramento) de forma que fatias (slots) vazias
possam ser reservadas.
– Se um nó tem um quadro para enviar no barramento á direita, seta o
bit de pedido em um quadro no barramento à esquerda.
– Nós mantém uma fila “implícita” de pedidos que pode ser servida
na base de FCFS (primeiro a chegar primeiro a ser servido) por isso
o nome de fila distribuída.
30
Grandes Atrasos de Propagação
(redes via satélite)
RES - Reserva
• Sistema de reserva via satélite
– O acesso mini-fatia pode ser ineficiente (Aloha, TDMA, etc.).
• De forma bastante aproximada, o atraso é 3/ 2 vezes o atraso de
propagação mais o atraso ideal de enfileiramento.
31
Reserva Via Satélite
•
•
•
O comprimento do quadro deve exceder o atraso de ida e volta.
– As fatias de reserva durante o quadro j são usadas para reservar fatias de
dados no quadro j+1.
– Comprimento variável: Serve todos os pedidos a partir do quadro j no
quadro j+1.
• Difícil manter sincronização
• Difícil prover QoS ( por ex.: suportar tráfego de voz)
– Comprimento fixo: Mantém um fila virtual de pedidos
Mecanismo de reserva
– Escalonador a bordo do satélite.
– Escalonador em terra.
– Algoritmo de fila distribuída: Todos os nós cuidam dos pedidos e utilizam
o mesmo algoritmo para fazer a reserva.
Controle de acesso ao canal
– TDMA:Simples mas difícil de adicionar mais usuários.
– Aloha: Pode suportar mais usuários mais resolução de colisões é difícil e
adiciona um enorme atraso.
32
Reserva Via Aloha
• Usa Aloha para capturar a fatia.
• Após a captura o usuário ocupa a fatia até terminar a transmissão.
– Outros usuários percebem que a fatia esta ocupada e não tentam o
acesso.
• Após a liberação da fatia outros usuários podem tentar o acesso.
– Outros usuários observam a fatia livre e tentam a reserve usando
Aloha.
• Método útil para transferência de dados longa ou mistura de voz e de
dado.
33
Múltiplo Acesso a Pacote - Resumo
•
•
•
Latência : Razão entre atraso de propagação e tempo de transmissão do pacote
– Exemplo GEO : Dp = 0,5 seg, comprimento do pacote = 1000 bits, R = 1Mbps
Latência = 500 ⇒ muito alta
– Exemplo LEO : Dp = 0,1 seg
Latência = 100 ⇒ ainda muito alta
– Em canais via satélite a taxa de dados deve ser muito baixa para que se tenha uma
Latência baixa
Protocolos de baixa latência
– CSMA, Polling, Token Rings, etc.
– Vazão ~ 1/(1+aα), α = latência, a = constante
Protocolos de alta latência
– Aloha é insensível à latência, mas geralmente tem baixa vazão
Atrasos bastante pequenos
– Sistemas com reserve podem atingir alta vazão
Atrasos para fazer as reservas
– Protocolos podem ser projetados para serem um híbrido entre Aloha e reserva
Aloha para baixa carga, reserva para alta carga
34
Migração Para redes locais Comutadas
•
•
•
•
Ethernet tradicional
– Nós conectados a cabo coaxial.
• Longos lances de fio por toda parte.
– Protocolo CSMA/ CD
•“Hub ” Ethernet
– Nós conectados ao hub.
• O Hub age como um repetidor em todas as
direções .
• Curtos lances de cabo, útil para 100Mbps.
– Protocolo CSMA/CD fácil em adicionar/remover
usuários.
– Fácil em localizar falhas.
– Cabeação barata (par trançado, 10baseT).
Ethernet comutada
– Não CSMA/ CD
Fácil de incrementar taxa de dados (por ex.: Gbit Ethernet)
– Nós transmitem quando querem.
• O comutador armazena os pacotes e os transmite
para seus destinos.
– Capacidade típica de um comutador é de 20- 40 portas.
– Cada nó pode transmitir na taxa total de 10/ 100/Gbps.
– Modularidade: Comutadores podem estar conectados
uns aos outros através de portas de alta taxa de
transmissão.
35