06 - Camada de Enlace de Dados
24 de novembro de 2014
Conteúdo
Camada de Enlace de dados segundo OSI
Subcamada de enlace lógico
Transmissão confiável
Subcamada de controle de acesso ao meio
Protocolos de controle de acesso ao meio
2/55
Camada de Enlace de dados
I
Serviços
I
I
Endereçamento
Transmissão confiável
I
I
I
Controle de Acesso ao Meio
I
I
Compartilhamento de canais broadcast
Na camada de enlace são transmitidos datagramas
I
I
Controle de fluxo
Detecção e correção de erros
Como é feito o enquadramento?
Duas subcamadas
I
I
Subcamada superior: Logical Link Control (LLC)
Subcamada inferior: Media Access Control sub-layer (MAC)
3/55
Camada de Enlace de dados segundo OSI
I
Detecta e corrige erros da Camada Fı́sica
I
Provê funções básicas para comunicação de entidades da
Camada de Rede
I
Permite a criação de circuitos de dados
4/55
Serviços para a Camada de Rede
I
Em modo de conexão
I
I
I
I
I
I
I
I
Endereço de camada de enlace
Conexão de enlace
Notificação de erros
Unidades de dados de serviços
Identificadores de pontos de conexão
Reset/Reinı́cio da comunicação
Parâmetros de qualidade de serviço
Em modo sem conexão
I
I
I
Endereço
Transmissão de unidades de dados
Especificação de parâmetros de qualidade de serviço
5/55
Endereços da camada de enlace de dados
I
Endereço
I
I
I
Entidades da Rede se identificam pelos endereços de Enlace
No OSI, um endereço é único na camada de Enlace
Conexão e PDU
I
I
I
I
Camada de enlace permite comunicação sem conexão
Tamanho da PDU pode ser limitado pelo meio fı́sico
Camada de enlace fornece identificadores para entidades da
camada de rede
Notificação de erros
I
Quando não é possı́vel corrigir erro, camada de enlance avisa
camada de rede
6/55
Parâmetros de qualidade de serviço
I
I
Opcional
A própria camada de Enlace pode determinar parâmetros de
qualidade
I
I
I
I
Tempo médio entre erros detectáveis mas não corrigı́veis
Disponibilidade de serviços
Demora de transmissão
Capacidade de transmissão
7/55
Comunicação entre NICs
I
Lado emissor
I
I
I
Encapsula datagrama no quadro
Inclui bits de verificação de erro e controle de fluxo
Lado receptor
I
I
I
Procura de erros
Verifica bits de controle de fluxo
Extrai dados do datagrama e envia para camada superior
8/55
Subcamada de enlace lógico: Datagramas
I
Ideal: todo datagrama é enviado apenas 1 vez
I
I
I
Na ordem certa
Com o conteúdo correto
Camada de enlace inclui um cabeçalho e um sufixo ao
conteúdo sendo transmitido
cabeçalho
I
pacote de dados
sufixo
Como saber se isso é um datagrama?
0101001011101110010101001000101011
9/55
Enquadramento
I
Como determinar o inı́cio e o fim de datagramas?
0101001011101110010101001000101011
I
I
Aonde estão os dados?
Abordagens:
I
I
Enquadramento orientado a caracteres
Contagem de tamanho
I
I
Opção: tamanho fixo
Protocolos orientados a bits (uso de flags)
10/55
Enquadramento orientado a caracteres
...
SYN
SYN
STX
header
dados
ETX
CRC
SYN
I
Mais usado de 1960 a 1975
I
Código de caracteres padrões (ASCII ou EBCDIC) tem
caracteres reservados para comunicação
Comunicação é baseada nesses caracteres especiais
I
I
SYN
...
SYN 0x16 - Synchronous Idle
I
I
I
STX
I
ETX
I
I
indica sincronia e ociosidade
00010110
indica inı́cio de texto
indica fim de texto
11/55
Tabela ASCII
12/55
Problemas com enquadramento baseado em caracteres
I
Dependência ao código de caracteres
I
I
Quadros deve ter um número inteiro de caracteres
I
I
Como enviar dados binários?
Número de bits deve ser múltiplo do número de bits de um
caracter
Erros em caracteres de controle são catastróficos
I
Erro em STX provoca perda do inı́cio do texto
13/55
Enquadramento baseado em campo de tamanho
I
Usar campo de cabeçalho para indicar o tamanho do quadro
I
I
I
I
Limita tamanho dos quadro
Problemas
I
I
I
Receptor conta até o fim do quadro para achar próximo quadro
Campo de tamanho precisa usar log2 TAMMAX + 1 bits
Difı́cil recuperar de erros
Ressincronização após erro na contagem de tamanho
Usado na DECnet (1975)
14/55
Quadros de tamanho fixo
I
Quadros têm tamanho sempre igual
I
Necessária sincronização na inicialização
Problemas:
I
I
I
I
I
I
Se tamanho dos dados não é múltiplo do tamanho do quadro
Último quadro deve ter conteúdo parcialmente vazio
Sincronia pode ser difı́cil
Fragmentação e remontagem dos quadros pode ser difı́cil em
taxas altas
Exemplo:
I
I
Padrões Asynchronous Transfer Mode (ATM)
Frames com 53 bytes
15/55
Enquadramento orientado a bits
I
Uso de bits indicadores: flags
I
I
Flag de inı́cio/fim não pode aparecer dentro do frame
I
I
I
I
Flag: sequência de bits para indicar inı́cio e fim de quadro
Comum usar como flag: 01111110
E usar para erro: 01111111...1110 < 16 bits
Repetição de flag ou somente 1 indica estado ocioso
Criado pela IBM (1970)
I
Synchronous Data Link Control (SDLC)
16/55
Justificação positiva ou Bit Stuffing (preenchimento de
bits)
I
Na transmissão com enquadramento orientado a bits é
comum perder sincronia após muitos bits 1s
I
Introdução de 0s para não perder sincronia (SDLC e USB)
I
SDLC usa flag com 6 bits 01111110
SDLC introduz um 0 a cada cinco bits 1s dos dados originais
I
I
I
I
I
garante que flag não aparece nos dados
Original:
1111110111111111111101111110
Após preenchimento:
1111101011111011111011101111100
Remoção
I
I
Remover todos 0 precedido de 011111
O zero precedido por 0111111, faz parte da flag
17/55
Erros de enquadramento
I
Todas as técnicas de enquadramento são sensı́veis a erros
I
I
I
I
Um erro em um campo de tamanho faz o quadro terminar no
lugar errado e o quadro seguinte pode ser perdido
Erro nos caracters STX, ETX causam o mesmo problema
Um erro em uma flag faz um quadro sumir ou um quadro
inexistente aparecer
Abordagem com flag é menos sensı́vel pois eventualmente
uma flag aparece
I
Possı́vel eliminar quadros errôneos com detecção de erros
18/55
Técnicas de detecção de erros
I
Usado pelo receptor para determinar se quadro tem erros
I
Se quadro tem erros, receptor pede seu reenvio
Técnicas de detecção de erros
I
I
Verificação de paridade
I
I
I
Paridade de bit único
Paridade múltipla (vertical ou horizontal)
Verificação de redundância cı́clica (CRC)
19/55
Efetividade de técnicas de detecção de erros
I
Número mı́nimo de erros d para evitar detecção
I
I
Habilidade de detecção de rajadas de erros (burst)
I
I
Se ocorrerem menos que d erros, a detecção é garantida
Tamanho máximo B da rajada de erros
Probabilidade de reconhecer um bit errôneo como correto
20/55
Verificação de paridade de bit único
I
Adicionar um bit para paridade
I
bit é 1, se quadro tiver número ı́mpar de 1s
bit é 0, caso contrário
I
Simplificação assumindo erros independentes
I
I
P
P(erro não detectado) = i par ki p i (1 − p)i
k é o tamanho do quadro
p é a probabilidade de erro de 1 bit
21/55
Paridade múltipla: horizontal e vertical
1
0
1
1
0
1
0
1
1
0
0
0
0
1
1
0
1
1
1
1
0
0
1
1
0
0
0
1
0
1
1
1
0
1
0
1
0
0
1
1
1
1
Verificação
vertical
I
I
I
1
0
0
0
1
0
Verificação
horizontal
1
0
1
1
0
1
0
1
1
0
0
0
1
1
1
0
1
1
1
1
0
0
1
1
0
0
0
1
0
1
1
1
0
1
0
1
0
0
1
1
1
1
1
0
0
0
1
0
Bit de paridade é obtido para cada linha e coluna
Se um número ı́mpar de erros estão em uma só coluna, cada
erro pode ser detectado pelos bits de paridade das linhas
Se ocorrem 4 erros em um quadrado, não é possı́vel detectar
erros
22/55
Verificação de Erro Cı́clico (CRC)
I
Temos bits de dados:
sK −1 , sK −2 , . . . , s0
I
Representamos bits como um polinômio:
s(x) = sK −1 x K −1 + sK −2 x K −2 + . . . s1 x 1 + s0
I
Representamos o CRC com L bits como
c(x) = cL−1 x L−1 + cL−2 x L−2 + . . . c1 x 1 + c0
I
O quadro inteiro pode ser representado como polinômio
f (x) = s(x)x L +c(x) = sK −1 x L+K −1 +. . .+s0 x L +cL−1 x L−1 +. . .+c0
I
Por quê representação polinomial?
I
Para obter coeficientes ci de c(x) pela divisão de s(x)x L por
um polinômio conhecido g (x)
23/55
Obtenção de c(x)
I
I
I
Temos si (dados) para i = 0, . . . , K − 1
Como computar ci (CRC) para i = 0, . . . , L − 1?
I
Seja g (x) = x L + gL−1 x L−1 + . . . + g 1x + 1 conhecido
(gL = g0 = 1).
então
s(x)x L
c(x) = Resto de divisão módulo 2
g (x)
I
Resulta em polinômio de grau L − 1 → L bits
Exemplo: s = 101 (K=3) e g (x) = x 3 + x 2 + 1(L = 3)
I
I
I
s(x) =?
s(x)x L =?
Dividir s(x)x L por g (x) e obter resto.
24/55
Exemplo CRC
I
L=3
I
s = 110101
I
g (x) = x 3 + 1
I
s(x) = x 5 + x 4 + x 2 + 1
I
s(x)x L = x 8 + x 7 + x 5 + x 3
x8 + x7 + x5 + x3
= x5 + x4 + x + 1
x3 + 1
I
c(x) = 0x 2 + 1x + 1(L = 3) → c = 011
110101
011
25/55
Como c(x) ajuda?
I
s(x)x L = g (x)z(x) + c(x)
I
s(x)x L + c(x) = g (x)z(x) + c(x) + c(x)
|
{z
}
0 em módulo 2
I
s(x)x L + c(x) = g (x)z(x)
I
f (x) = g (x)z(x)
I
I
I
Representação polinomial do quadro é múltipla de g (x)
Assumir que f (x) foi recebido como y (x)
Receptor recebe y (x) em Frame Check Sequence (FCS) e
computa
y (x)
Resto
g (x)
I
Se Resto 6= 0, então erro!
26/55
Implementação
I
A implementação é realizada com o operador XOR
I
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Polinômio: x 3 + x + 1 com coeficientes: 1011
11010011101100
1011
01100011101100
1011
00111011101100
1011
00010111101100
1011
00000001101100
1011
00000000110100
1011
00000000011000
1011
00000000001110
1011
00000000000101
101
00000000000000
000 <−−
<−−
000 <−−
<−−
000
d a d o s d e s l o c a d o s em 3 b i t s
d i v i s o r /XOR
resultado
divisor ...
000
000 <−−− move p a r a o p r i m e i r o b i t 1
000
000
000
000
1
100 <−−− r e s t o ( 3 b i t s ) .
27/55
Verificação de código CRC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
I
Processo similar ao da obtenção do CRC
I
Se resto for zero, não houveram erros.
11010011101100 100 <−−− d a d o s com CRC
1011
<−−− d i v i s o r
01100011101100 100 <−−− r e s u l t a d o
1011
<−−− d i v i s o r . . .
00111011101100 100
......
00000000001110 100
1011
00000000000101 100
101 1
−−−−−−−−−−−−−−−−−−
0 <−−− r e s t o
28/55
Erros não detectados
I
Assumir que erro é e(x) tal que y (x) = f (x) + e(x)
I
Então,
I
Teremos erros não detectados se e só se e(x) 6= 0 divisı́vel por
g (x)
Erros únicos (1 bit) são sempre detectados
I
I
I
y (x)
g (x)
=
f (x)
g (x)
+
e(x)
g (x)
por absurdo, assumir não detectado: e(x) = x i = g (x)z(x)
para algum i
uma vez que g (x) = x L + . . . + 1, multiplicando g (x) por
qualquer z(x) 6= 0 não produz x i (deve produzir pelo menos 2
termos)
29/55
Frame Ethernet: Frame Check Sequence (FCS)
Formato do Quadro Ethernet (IEEE 802.3-2012, seção 3.1.1):
I
Preâmbulo: 7 octetos 10101010... (codificação Manchester)
I
Start Frame Delimiter (SFD): 1 octeto 10101011
I
MAC destino: 6 octetos
I
MAC original: 6 octetos
I
EtherType (comprimento/tipo): 2 octetos
I
Dados (payload): 46 a 1500 octetos
I
Frame Check Sequence (FCS): 4 octetos
Polinômio CRC Ethernet:
g (x) =
x 32 +x 26 +x 23 +x 22 +x 16 +x 12 +x 11 +x 10 +x 8 +x 7 +x 5 +x 4 +x 2 +x+1
30/55
Caracterı́sticas de erros de meios fı́sicos
I
I
Muitos meios fı́sicos não são ideais
Erros não são independentes
I
I
são comuns erros consecutivos (burts)
CRC consegue detectar sequências de erros consecutivos cujo
número é menor que o grau do polinômio de detecção
31/55
Controle de erros por retransmissão
I
Reconhecimento positivo
I
I
Reconhecimento negativo
I
I
Aguardar confirmação de recebimento correto, senão
retransmite
Retransmite apenas se receber confirmação de recebimento
errôneo
Reconhecimento contı́nuo
I
Reconhecimento de até N quadros consecutivos
32/55
Subcamada de Controle de acesso ao meio: tipos de
conexões
I
Conexões ponto-a-ponto
I
I
I
I
Estrela
Em malha
Hierárquica
Conexões em meio compartilhado (broadcast)
I
I
I
Radio difusão via satélite
Hub – comunicação por barramento
Centralizado em anel (token ring IEEE 802.5)
33/55
Protocolo de comunicação em broadcast idealizado
I
Quando um host quer transmitir, ele pode enviar na taxa R
bit/s
I
Quando M hosts querem transmitir, cada um pode enviar na
taxa R/M bit/s
Totalmente descentralizado:
I
I
I
I
Nenhum host especial para coordenar transmissões
Nenhuma sincronização de relógios, intervalos
Simples
34/55
Protocolos de controle de acesso ao meio: Conexões
broadcast
I
Se todos tem direito ao acesso, quem vai acessar o meio?
I
I
Abordagem aleatória
Abordagem determinı́stica
I
I
I
Particionamento
Revezamento
Como tratar colisões?
I
O que acontece quando duas pessoas tentam falar ao mesmo
tempo?
35/55
Protocolos de acesso ao meio
I
Time Division Multiple Access
I
I
I
Frequency Division Multiple Access
I
I
I
Cada usuário pode transmitir em uma faixa de frequências
diferente
Faixa não usada é perdida
Code Division Multiple Acess (CDMA)
I
I
Cada usuário tem um momento determinado para acessar o
canal
Intervalos não usados são perdidos
Divisão por código (vetores ortogonais), um código por
transmissor
Acesso aleatório
36/55
Acesso aleatório
I
Quando host tem um pacote a enviar:
I
I
I
I
Dois ou mais transmitindo juntos = colisão
Um protocolo de Controle de Acesso ao Meio aleatório:
I
I
I
transmite na velocidade de dados R total do canal
sem coordenação a priori entre os hosts
como detectar colisões
como recuperar-se de colisões
Exemplos de protocolos de Controle de Acesso ao Meio
Aleatório:
I
I
ALOHA
CSMA/CD
37/55
Protocolos de acesso ao meio: ALOHA puro
1. Transmitir quadro
2. Aguardar ACK por no máximo um perı́odo T. Se receber
ACK, sucesso.
3. Se não recebe ACK, gerar novo perı́odo aleatório T
4. Esperar o perı́odo T e retransmitir quadro
38/55
Protocolo de acesso ao meio: ALOHA com slots
I
quadros sempre do mesmo
tamanho
I
tempo dividido em intervalos
de mesma duração,
chamado de slots (tempo
para enviar 1 quadro)
I
transmissão começa
somente no inı́cio dos slots
I
hosts são sincronizados
I
se 2 ou mais transmitem no
mesmo intervalo, todos
percebem a colisão
I
quando host tem quadro a
ser enviado, tenta
transmissão no slot seguinte
I
I
se não há colisão: host
tenta enviar novo quadro
no próximo slot
se há colisão: host tenta
probabilisticamente enviar
em um próximo slot
39/55
ALOHA com slots
I
Vantagens:
I
I
I
I
simplicidade
um host pode transmitir na velocidade máxima do meio
decentralização: sincronismo apenas nos slots
Desvantagens:
I
I
I
Colisões frequentes, perda de slots
Intervalos ociosos
Necessário sincronia de relógio
40/55
CSMA
I
Carrier Sense Multiple Access (CSMA)
I
“Ouça antes de falar”
I
Somente transmite se meio está ocioso
41/55
CSMA: colisões
I
Colisões em CSMA ocorrem pois existe tempo de atraso de
transmissão
I
I
Dois podem iniciar a transmissão quase simultaneamente
Se há colisão, o tempo de transmissão de um quadro inteiro é
perdido
42/55
CSMA/CD ou CA
I
Collision Detection (CD) - IEEE 802.3
I
I
I
I
Capaz de comparar sinais transmitidos com recebidos
Transmissões colididas são abortadas, reduzindo tempo perdido
Mais fácil em meios com fio do que meios sem fio
Collision Avoidance (CA) - IEEE 802.11
I
I
Evita colisão
Se canal está ocupado, espera um tempo aleatório para
próxima tentativa
43/55
Outros protocolos de acesso ao meio
I
Seleção (Polling)
I
I
Mestre escolhe quem pode enviar
Uso de permissões para envio (Token Ring)
I
I
Quem tem o token, pode enviar
Quando não usar mais o token, passa para o seguinte
44/55
Endereçamento: exemplo
I
OSI pede por identificador único na camada de enlace
I
Endereço MAC de NICs, IEEE 802
I
Cada MAC consiste de 6 bytes
MAC são únicos e atribuı́dos por fabricante
I
I
I
Armazenado em Hardware
Possı́vel mudar em software
45/55
1
2
6 bytes
3
4
5
6
mais signi cante
6º byte
5º byte
4º byte
3º byte
2º byte
1º byte
1º octeto
2º octeto
3º octeto
4º octeto
5º octeto
6º octeto
ou
3 bytes
3 bytes
Identicador Único
Organizacional
Especíco ao
Controlador da Interface
de Rede (NIC)
menos signi cante
posição:
8 bits
b8 b7 b6 b5 b4 b3 b2 b1
0: unicast
1: multicast
0: globalmente único
1: administrado localmente
46/55
Figura: Pacote do protocolo Address Resolution Protocol (ARP) sobre
um frame Ethernet II
47/55
Endereçamento MAC e tabela ARP
I
Tabela de Address Resolution Protocol (ARP)
I
I
I
Conversão de endereço de meio fı́sico e endereço de camada
superior
“MAC address é o CPF e IP é o CEP”
Se um host A quer falar com B, pergunta seu pelo seu MAC
indicando endereço da camada superior
48/55
Ethernet
I
I
I
I
I
I
Tecnologia LAN — IEEE 802.3 (1983)
Camada fı́sica e camada de enlace
Inı́cio com cabo coaxial de 10 Mbit/s
Compartilhamento do meio CSMA/CD
Praticamente todo ano, tecnologia teve atualizações
Gerações futuras: IEEE 802.3ba2-2010, cat8, 100 Gb/s
49/55
I
Até ≈1995,
meio
compartilhado
I
Hub –
broadcast, sem
buffering
I
Switch – isola
hosts, com
buffering
50/55
Quadro Ethernet
I
I
I
IEEE 802.3-2012
Packet Ethernet: camada fı́sica
Frame Ethernet: camada de enlace
bytes
I
Preâmb
Flag
7
1
MAC MAC 802.1q
Tipo
dest
src VLAN
6
6
4
2
Preâmbulo: repetições de
0x55 (menos significante
primeiro)
I
I
Flag - delimitador de ı́nicio
de frame - 0xD5
0xD5 = 11010101b
I
CRC
42-1500
4
Intervalo
Separador
12
Intervalo separador: estado
ocioso para marcar fim de
packet
I
0x55 = 01010101b
Payload
.96ns para 100Gb/s, 96ns
para 1Gb/s
Tipo indica o protocolo
encapsulado no payload
51/55
Ethernet
I
O cabeçalho do frame é conhecido como Ethernet II
I
Não oferece confiabilidade
I
Não oferece serviços de conexões
Originalmente não usava subcamada LLC (Logical Link
Control)
I
I
I
I
IEEE 802.2 Subnetwork Acess Protocol (SNAP) permite
transmitir informações em outras redes que não Ethernet
MacOS usa 802.2 para o AppleTalk
Protocolo de compartilhamento de meio: CSMA/CD sem slots
52/55
IEEE 802: Famı́lia de padrões para LAN e MAN
Distâncias
1m
10m
100m
1km
10km
100km
1000km
10.000km
Área
metro quadrado
sala
prédio
campus/bairro
cidade
paı́s
continente
planeta
Tipo
PAN
LAN
LAN
LAN
MAN
WAN
WAN
Exemplo
bluetooth IEEE 802.15.1
WiFi IEEE 802.11
IEEE 802.3
WiMAX IEEE 802.16
FDDI 802.6
WiMAX IEEE 802.16
Internet
Personal Area Network (PAN), Local Area Network (LAN), Metropolitan
Area Network (MAN), Wide Area Network (WAN), Body Area Network
(BAN) – IEEE 802.15.6, Controller Area Network (CAN) – ISO 11898.
IEEE 802 (http://www.ieee802.org/): padrões para LAN e MAN para
redes com pacotes de tamanho variável. Camadas OSI 1 e 2.
53/55
Formas e gerenciamento de enlaces
I
Enlace ponto-a-ponto vs. multiponto
I
I
I
Gerenciamento de enlace
I
I
I
I
I
Estabelecimento
Transferência de dados
Encerramento
Reinicialização
Controle de fluxo – interromper temporariamente transmissão
I
I
I
Estações primárias (controladoras)
Estações secundárias (recebem comandos)
Quadro RR (receiver ready)
Quadro RNR (receiver not ready)
Bridging (LLC)
I
Agregação de segmentos de enlace (802.3 + 802.5)
I
I
Shortest Path Bridging (IEEE 802.1aq)
Spanning Tree Protocols (exemplo IEEE 802.1D)
54/55
Referências
I
Computer Networks (Tanembaum)
I
Computer Networking (Kurose)
I
Material didático L. Faina (Facom/UFU)
I
IEEE Standard for Ethernet (802.3-2012)
I
IEEE Standard for WirelessMAN-Advanced Air Interface for
Broadband Wireless Access Systems (802.16.1)
55/55