Redes de Computadores I

Aula 4
Camada de enlace de dados e subcamada
de acesso ao meio
Prof. José Martins Junior
 Pacotes
• Muitas redes dividem os dados em pequenos blocos,
denominados pacotes para a transmissão
– Cada pacote é enviado individualmente
– Tais redes são chamadas de redes de pacotes ou redes de comutação
de pacotes
• Motivação
– Coordenação
• Permite transmissor e receptor determinarem qual dado foi ou não
recebido corretamente
– Compartilhamento de recursos
• Diversos computadores podem compartilhar a infraestrutura da rede
– Redes forçam o uso justo
• Cada computador pode enviar somente uma mensagem por vez
 A camada de enlace
• A camada de enlace de dados provê uma interface bem definida para a
camada de redes

• Dentre suas principais funções, encontram-se

– Tratamento de erros de transmissão
– Controle de fluxo de dados
– Outra questão importante tratada por esta camada é o enquadramento
(delimitação) dos dados
 Serviços prestados
• A camada de rede encaminha um conjunto de dados para a
camada de enlace (um pacote, ou seu PDU)
• Tal pacote é então encapsulado em um quadro (frame)
– O frame é transmitido para a outra entidade de enlace na máquina de
destino
– O destino extrai de seu conteúdo o pacote transmitido e o entrega
para a camada de redes
 Enlace e o laço local
• A camada de enlace está associada a cada interface distinta
de um host ou roteador
• O protocolo de enlace tem significado local, comum a duas
interfaces em um mesmo laço, ou rede local
 Pacotes e Quadros
• Pacote é um termo genérico que se refere a um PDU da
camada de rede
– Cada tecnologia de rede define um formato específico de pacote
• Quadro (hardware frame) denota um PDU de um formato
específico em uma tecnologia específica de rede local
– É necessária a definição de um formato padrão para os dados, para
indicar o começo e o fim do quadro
– O cabeçalho e o fim de quadro são normalmente utilizados para
enquadrar os dados
 Enquadramento
• A camada física limita-se à transmissão de sinais que
representam os bits, através de um meio físico
– Erros podem ocorrer, e a camada de enlace necessita detectá-los para
prover/solicitar a retransmissão
– O principal problema: como reconhecer os limites de uma sequência
de bits antes mesmo de verificar se foi corretamente transmitida
• Uma das formas de enquadramento pouco utilizadas é a
quebra do protocolo físico
– Um sinal diferente é transmitido pela camada física para delimitar os
quadros
 Contagem de caracteres
• Uma das formas é transmitir um valor que representa a
contagem de octetos (caracteres) que seguirão na transmissão
– Problema: um erro ocorrido no caractere que representa a contagem
causará a interpretação errada de todos os restantes
– No exemplo, a alteração de apenas um bit pode mudar o valor de 5
para 7
 Uso de delimitadores
• Pode-se escolher dois valores de dados não utilizados para o
enquadramento
– Ex., se os dados limitam-se a valores ASCII, pode-se usar:
• Começo do cabeçalho (soh - start of header)
• Fim do texto (eot - end of text)
– O computador transmissor envia primeiramente um soh, e depois os
dados, e finalmente o eot
– O receptor interpreta e descarta o soh, armazena os dados no buffer e
interpreta e descarta o eot
Formato do quadro
 Problemas com delimitadores
• Implica em overhead extra - soh e eot consomem tempo de
transmissão e não carregam dados
• Problemas de transmissão
– Falta do eot – computador transmissor travou
– Falta de soh – receptor perdeu o começo da mensagem
– Quadros defeituosos são descartados
• Delimitador entre os dados
– Quando se transmitem dados binários arbitrários, o caracter
delimitador pode aparecer no payload
• soh e eot serão mal interpretados como limites de quadro
– Transmissor e receptor devem codificar caracteres especiais extras
para resolverem as ambiguidades
 Byte (character) Stuffing
• Esta técnica envolve a escolha de um caractere (flag byte)
para indicar o início e fim de quadro
– Problema: em transmissões com conteúdo binário, a sequência de bits
que resulta no flag byte pode ocorrer sem controle, ocasionando erro
de enquadramento
– Solução: adicionar um caractere pouco utilizado (ESC, por exemplo)
antes do flag byte acidental, que ocorrer no conteúdo
– Um caractere ESC também deve ser inserido antes de todos os
caracteres ESC verdadeiros que ocorrerem no conteúdo
Byte (character) Stuffing
 Bit Stuffing
• Técnica muito parecida com o byte stuffing
– Utiliza-se também de um caractere (flag) para delimitação, 01111110
– Para evitar sua ocorrência no conteúdo (payload), o emissor insere um
bit 0 a cada seqüência de 5 bits 1
 Controle de erros
• Um canal físico de comunicação pode incorrer em erros de
transmissão, e alterar valores binários no fluxo transmitido
– A distância de Hamming entre dois quadros a e b é o número de bits
na mesma posição que foram alterados
• Exemplo: com distância 3
– a: 10001001 (XOR)
– b: 10110001
– ------------
– 00111000
– Dados adicionais são inseridos aos originais para serem operados os
algoritmos de detecção ou correção de erros
• Para se detectar um conjunto de k (ou menos) erros, é necessário que a
distância Hamming entre quaisquer dois quadros seja, de no mínimo, k+1
• Já para a correção, tal distância deve ser de, no mínimo, 2k+1
– A correção de erros exige, portanto, um maior número de dados
adicionais e, na prática, não é utilizada na maioria das redes
 Bit de paridade
• Paridade está relacionada ao número de bits de valor 1 em
um conjunto
– Paridade par: espera-se um número total par de bits com valor 1
– Paridade ímpar: " " um número total ímpar de bits com valor 1
• Um bit de paridade é um bit extra transmitido com o conjunto
– Seu valor é definido para que se obtenha a paridade resultante, par
ou ímpar
– Exemplos:
Conjunto de bits: 10010001 10010101 10010111
Número de bits 1: 3 4 5
Bit de paridade par: 1 0 1
Bit de paridade ímpar: 0 1 0
 Bit de paridade
• Se o ruído ou outra interferência induzir um erro, um dos bits
nos dados pode ser alterado de 1 para 0, ou de 0 para 1
– A paridade resultante dos bits estará errada
– Exemplo (com paridade par):
Dados enviados (8 bits + paridade): 100100011
Dados recebidos (inversão de um bit): 101100011 ERRO DETECTADO

• Limitação
– Esta estratégia aplica-se à detecção de apenas erros de um bit
– Se dois (ou um número par) de bits forem alterados, a detecção
falhará
 Checksum
• Tal técnica envolve a soma do conjunto de bits em blocos que
representam valores inteiros de 8, 16, ou 32 bits
– Todo o valor excedente à esquerda (carry) é adicionado novamente à
parte menos significativa (de tamanho compatível com o inteiro
utilizado)
– O valor resultante é transmitido junto com o conjunto de bits
– Exemplo: Checksum com aritmética de 16 bits e adição de carries

• A sentença é interpretada como uma sequência de inteiros (hexa) de 16

bits. Os valores inteiros são somados, resultando em 271FA
• O valor 2 é o carry (parte que excede o campo de 16 bits) e é somado à
parte menos significativa: 2 + 71FA
• O resultado 71FC, de 16 bits, é a soma do checksum
 Checksum
• O checksum não é indicado para a conferência de erros
cíclicos
– Exemplo:
 CRC (Cyclic Redundancy Check)
• Também conhecido como Polinomial Code
– Um polinômio de grau r (onde r=k-1) pode ser representado através
de um conjunto de k bits
– Posição relativa de cada bit indica cada coeficiente no polinômio
• Exemplo: 110001

1 1 0 0 0 1 → x5 + x4 + x0 = x 5 + x4 + 1
5 4 3 2 1 0

Número de bits: k=6

Grau do polinômio: r = k-1 = 5
– Padrões internacionais
• CRC-12 = x12 + x11 + x3 + x2 + x1 + 1
• CRC-16 = x16 + x15 + x2 + 1
• CRC-CCITT = x16 + x12 + x5 + 1
 CRC (Cyclic Redundancy Check)
• Transmissor e receptor devem concordar por um polinômio
gerador G(x) de grau r (k-1)
• O algoritmo para cálculo do checksum polinomial
– Concatena-se r bits 0 ao final (parte menos significativa) do quadro
M(x), que tem m bits
• O resultante terá m+r bits, e corresponderá ao polinômio xrM(x)
– Divide-se o conjunto de bits de xrM(x) pelo conjunto de bits de G(x),
utilizando-se divisão com módulo 2
– Subtrai-se o resto (r ou menos bits) de xrM(x) usando subtração de
módulo 2
• O resultado será o frame T(x), a ser transmitido
 CRC (Cyclic Redundancy Check)
• Exemplo AND
– Frame original M(x)
1101011011 XOR

– Polinômio gerador G(x)

10011 → x4 + x1 + x0 → x4 + x + 1
– Pede-se T(x)

r=4
xrM(x) = 11010110110000

– Combinando-se (XOR) o resto e xrM(x)

xrM(x)= 11010110110000
Resto = 1110 (XOR)
--------------
T(x) = 11010110111110 Resto
M(x) CRC
 Detecção de erros e quadros
• A detecção de erros geralmente é feita para cada quadro

• Erros no quadro geralmente implicam no descarte do quadro

pelo receptor
– Ex.: CRC enviado depois do fim do quadro computado em dados no
quadro
 Controle de fluxo
• Uma das funções da camada de enlace é o controle do fluxo
da comunicação entre as entidades dessa camada, em
máquinas distintas
• Tal problema deve considerar diversos fatores, como
– Capacidade de processamento do fluxo pelo destino
– Ocorrência de erros no canal de transmissão
– Ocorrência de perda de quadros
• Mensagens de propósito geral são trocadas entre as duas
entidades, e devem conter informações de controle
 Exemplo:
Controle codificado em caracteres
SYN utilizado para obter e manter a sincronização de caracteres entre transmissor e receptor
SOH (Start of Header) utilizado para indicar o início de um cabeçalho
STX (Start of Text) utilizado para indicar o início de um texto ou de um bloco de dados
ETB (End of Transmission Block) para informar o final de um bloco de dados iniciado com STX
ITB para dividir uma mensagem, sem requerer uma resposta imediata da estação receptora
ETX (End of Text) indica o fim de um texto de dados iniciado por STX e requer uma resposta
EOT (End of Transmission) indica o fim da transmissão de uma estação
ENQ (Enquiry) solicita resposta da receptora ou retransmissão da resposta de mensagem enviada
ACK (Affirmative Acknowledgment) indica recepção sem erros de um bloco e que a estação está apta a receber um novo bloco
WACK (Wait Before Transmit ACK) informa o recebimento positivo de um bloco, porém indica uma impossibilidade momentânea
de receber o próximo bloco. A estação transmissora, ao receber um WACK, envia um ou mais ENQ até que receba como
resposta um ACK. Só então, continua a transmissão de blocos de mensagem
NACK (Negative Acknowlegment) indica que o bloco anterior foi recebido com erro. A estação receptora aguarda a
retransmissão
DLE (Data Link Escape) indica o modo de transmissão transparente, onde caracteres de controle não são reconhecidos como
tal e sim como caracteres de texto
TTD (Temporary Text Delay) enviado pela estação transmissora para indicar a impossibilidade
momentânea de continuar a enviar dados, mas quer reter a linha para novas transmissões
RVI (Reverse Interrupt) transmitido no lugar do ACK, indicando a recepção do último bloco corretamente, mas solicita a
inversão do sentido de transmissão para o envio de uma mensagem de maior prioridade
BCC (Block Check Character) Seqüência binária que representa o resultado obtido pela operação de CRC para a verificação
da integridade dos dados. É transmitido após os caracteres de ETB e ETX
 Canal ponto-a-ponto
• A estação que deseja transmitir deve enviar uma seqüência
para “tomar” a linha
SYN SYN ENQ
• A estação receptora pode responder das seguintes maneiras
SYN SYN ACK - Estou pronta
SYN SYN NACK - Não estou pronta
SYN SYN WACK - Espere
Canal sem erros
Canal com erros
Inclusão de timeout
 Protocolos de enlace
• Tanenbaum apresenta 3 protocolos (algoritmos) elementares que tratam
progressivamente os problemas dessa camada
– Simplex
• Dados transmitidos em apenas uma direção
• Ambas as camadas de rede do transmissor e do receptor estão sempre prontas
• Tempo de processamento pode ser ignorado
• Existe um espaço infinito de buffer
• O meio físico não incorre em erros ou perdas de pacotes
– Simplex stop-and-wait
• Inclui a complexidade de aguardar por um evento a cada envio
– Simplex para um canal com ruído
• Passa a considerar a ocorrência de erros no canal
• Inclui mecanismos para confirmação de recebimento de quadros inalterados,
timeout para a recepção de confirmação de quadros, e tratamento de duplicatas
com números de seqüência
 Protocolo Sliding-Window (janela
deslizante)
• Permite o encaminhamento de um conjunto de quadros de uma vez
(chamado de janela de transmissão) que permanecerão aguardando a
confirmação do recebimento
– Um quadro é removido da janela se a confirmação for recebida
– O receptor mantém uma janela de recepção que indicará quantos quadros
poderá receber antes de confirmar o primeiro
– Se um quadro chegar corrompido, a posição na janela mantém-se pendente
– No caso das janelas operarem com tamanho 1, será um protocolo do tipo
stop-and-wait. Exemplo de janela (de tamanho 1, e sequência em 3 bits):
 Sliding-Window com Go back N

• a) Quando a janela do receptor (buffer) de tamanho 1 – Go back N

• b) Operação de retransmissão seletiva do segmento que faltou (janela do receptor é maior)
 Estudo de caso
HDLC (High-Level Data Link Control)
• Protocolo amplamente utilizado para conexões ponto-a-ponto
– É orientado a bit
– Formato

– O campo endereço, apesar de presente, não tem grande utilidade

– O campo de controle é utilizado para distinguir diferentes tipos de
quadros
• O HDLC usa um protocolo com sequenciamento em 3 bits
• Outras informações (sequência, acks, nacks, ...) são também carregadas
pelo campo de controle
 Estudo de caso
PPP (Point-to-Point Protocol)
• Protocolo de enlace para conexões ponto-a-ponto na Internet
• Define
– Delimitação clara de quadro
– Um protocolo separado para controle da linha (setup, negotiating,
options...), chamado LCP (Line Control Packet)
– Suporta outros protocolos de rede, além do IP
– Não necessita definição de endereços
– Formato do quadro
 Controle de acesso ao meio
• Em canais de difusão, várias estações compartilham o uso de
um mesmo meio físico
• Vários problemas novos surgem
– Como uma estação pode referenciar de forma não-ambígua uma outra?
– Como as estações se organizarão para compartilhar o uso do mesmo
canal?
• A maioria das redes locais não suporta a coexistência de vários
canais de diferentes frequências
– Portanto só resta, como opção, a divisão em relação ao tempo (TDM)
• Há, portanto, a necessidade de um controle de acesso ao meio
– Ou Media Access Control (MAC)
 Alocação de canais
• Algumas estratégias foram definidas para solução do
problema de alocação de canais
– Sistemas de contenção
• Nenhum controle central é criado
• As estações simplesmente tentam utilizar o canal, e algo deve ser feito
quando uma colisão ocorrer
– Sistemas baseados em tokens
• Uma técnica de rodízio é aplicada, utilizando-se um token, que é lançado
na rede
• Quando uma estação tiver posse do token, poderá realizar uma
transmissão
– Sistemas slotted
• Uma estação pode solicitar a reserva por um período de tempo
 Sistemas baseados em tokens
• Muitas tecnologias de LAN que usam a topologia anel utilizam
a passagem de token para o acesso sincronizado ao anel
• O anel é tratado como um único e compartilhado meio de
comunicação
• Os bits enviados pelo transmissor passam por outros
computadores e são copiados pelo destinatário
• O hardware deve ser designado a passar o token sempre que
um computador anexado é desligado
Token Ring
 Uso do Token
• Quando um computador quer transmitir, ele espera pelo token
– Depois da transmissão, o computador transmite o token no anel
– O próximo computador pronto para transmitir recebe o token e então
transmite
• Pelo motivo de haver apenas um token, apenas um computador
transmitirá a cada vez
– O token é um quadro curto e reservado que não contém dados
– O hardware (um master) deve recriar o token se for perdido
• O token dá permissão ao computador para enviar um quadro
– Se todos estão prontos para transmitir, um acesso “round-robin” é
forçado
– Se nenhum computador estiver pronto para transmitir, o token circulará
pelo anel
 Protocolo ALOHA
• O ALOHA é um tipo de sistema de contenção
– A estação que deseja transmitir um quadro simplesmente o faz
– Se uma colisão ocorrer, tenta novamente mais tarde

• A variação Slotted ALOHA

– Impõe slots de tempo (intervalos fixos) bem definidos onde se pode
começar uma transmissão
– Estatisticamente, isso colabora para a redução de incidências de
colisões
 CSMA (Carrier Sense Multiple Access)
• Introduziu uma melhoria ao ALOHA
– A estação transmissora deve monitorar o canal antes e/ou durante a
transmissão
• Existem três implementações
– 1-persistent
• Detecta quando o canal está livre antes de transmitir
• Se ocupado, aguarda sua liberação e inicia imediatamente a transmissão
– Nonpersistent
• Quando o canal está ocupado, espera um intervalo aleatório de tempo
antes de tentar novamente
– p-Persistente
• Utilizado em sistemas Slotted
• Se o canal estiver livre em um intervalo, a estação transmitirá com
probabilidade p, e adia até o próximo slot, com probabilidade 1-p
• p = 1 não é bom, p = 0 é mais polido
Comparação ALOHA e CSMA
 Bibliografia
• FOROUZAN, Behrouz A. Comunicação de dados e redes
de computadores. Porto Alegre: AMGH, 2010 –
Capítulos 10 e 11.

• TANENBAUM, Andrew S.; WETHERALL, David J. Redes

de Computadores. 5ª ed. São Paulo: Pearson Prentice
Hall, 2011 – Capítulo 3.