Rede de computadores Aula 09

Prévia do material em texto

Redes de Computadores 1
9a Aula:9a Aula:
Camada de Enlace: funções e métodos de 
detecção e correção de erros
- Prover serviços para a camada de rede – no modelo TCP/IP, camada
Internet ou Inter-redes;
- Os enlaces ou links podem ser um canal:
- Broadcast: quando há muitos nós conectados ao mesmo canal de
Camada de Enlace: Funções
comunicação (por exemplo: redes locais). Neste cenário é necessário um
protocolo de controle de acesso ao meio;
- Ponto-a-ponto: há apenas dois nós envolvidos.
- Um protocolo camada de enlace define o formato dos quadros
trocados entre as extremidades do link, além de prover detecção e/ou
correção de erros, retransmissão, controle de fluxo e acesso aleatório;
- Um protocolo de camada de enlace é encarregado de movimentar
datagramas de nó a nó por um único enlace.
- Cada enlace (link) entre a origem e o destino da comunicação pode utilizar
um protocolo de camada de enlace diferente;
Camada de Enlace: Funções
- Os serviços proporcionados pelos protocolos de camada de enlace
podem ser diferentes. Por exemplo, um protocolo dessa camada pode
prover um serviço confiável enquanto o outro um serviço não-
confiável;
Nó A Nó B Nó C
- Exemplo do livro do Kurose – Relacionamento entre camada de
enlace e camada internet:
Camada de Enlace: Funções
- Serviços que podem ser oferecidos por um protocolo de enlace:
• Enquadramento de dados: processo de inserir o datagrama da camada de
internet num quadro antes de encaminhá-lo no link. A estrutura do quadro –
campos que compõem o cabeçalho – depende do protocolo utilizado;
Camada de Enlace: Funções
- Serviços que podem ser oferecidos por um protocolo de enlace:
• Acesso ao meio: define as regras para a transmissão do quadro no link;
• Entrega confiável: garantia de que a entrega dos quadros será realizada sem
erros, através de reconhecimentos e reenvios. Normalmente utilizados em
links que costumam ter altas taxas de erros;
Camada de Enlace: Funções
links que costumam ter altas taxas de erros;
• Controle de fluxo: controle de taxa de dados enviados para não sobrecarregar
buffer de recepção no destino;
- Serviços que podem ser oferecidos por um protocolo de enlace:
• Detecção de erros: atenuações de sinal podem provocar a erros na recepção
de sinais transmitidos no link. Como quadros com erros não devem ser
processados, obriga-se a origem a enviar bits de detecção de erros e o destino
a executar uma verificação de erros. Esta função normalmente é
Camada de Enlace: Funções
a executar uma verificação de erros. Esta função normalmente é
implementada em hardware;
• Correção de erros: muito semelhante à detecção de erros, porém o destino
além de verificar a ocorrência de erros no quadro, identifica onde os erros
ocorreram e os corrige;
• Modo de transmissão: define o modo como a comunicação ocorre no link em
questão – Half-duplex e Full-duplex;
- Os serviços normalmente ofertados pela camada de enlace são:
- Serviço sem conexão e sem confirmação: Não há nenhuma conexão lógica
entre os nós envolvidos e sem confirmação de recebimento dos quadros. É
mais apropriada quando a taxa de erros do link é muito baixa e a recuperação
fica sob responsabilidade das camadas superiores e para tráfego em tempo
Camada de Enlace: Tipos de Serviços
fica sob responsabilidade das camadas superiores e para tráfego em tempo
real;
- Serviço sem conexão e com confirmação: Continua não existindo uma
conexão lógica entre os nós, porém cada quadro transmitido é confirmado
individualmente. Caso não ocorra uma confirmação, é possível reenviar o
quadro em questão. Útil em canais não confiáveis, como redes sem fio;
- Os serviços normalmente ofertados pela camada de enlace são:
- Serviço orientado à conexão e com confirmação: os dispositivos envolvidos
estabelecem uma conexão lógica antes da transmissão efetiva dos dados.
Aqui, a camada de enlace garante que todos quadros serão recebidos e em
ordem, semelhante a um fluxo de bits confiável.
Camada de Enlace: Tipos de Serviços
ordem, semelhante a um fluxo de bits confiável.
- A idéia de separar os bits em quadros serve para facilitar a
identificação de erros na transmissão e a recuperação da informação
sempre que necessário;
- O uso de quadros parecer ser simples, mas ela oferece desafios:
Camada de Enlace: Enquadramento
como identificar os linites do quadro?
- Inicialmente, pensou-se em inserir períodos de tempo entre os
quadros, de maneira semelhante a um texto onde as palavras são
separadas por espaços, porém não há garantias de que esses períodos
de tempo serão respeitados na transmissão;
- Em função disso, foram definidas novos métodos de marcação de quadro:
- Contagem de caracteres: Neste método, o primeiro caractere informa o
número de caracteres que compõe o quadro. Caso ocorra um erro que altere a
correta interpretação do caractere, haverá perda de sincronismo:
Camada de Enlace: Enquadramento
- Em função disso, foram definidas novos métodos de marcação de quadro:
- Bytes de flags, com inserção de bytes:
- Este método contorna a perda de sincronismo devido a ocorrência de erros
utilizando bytes especiais para iniciar e terminar o quadro.
- Antigamente esses dois conjuntos de bytes eram diferentes, mas atualmente
Camada de Enlace: Enquadramento
- Antigamente esses dois conjuntos de bytes eram diferentes, mas atualmente
utiliza-se o byte de flag para o início e fim do quadro. Em caso de perda de
sincronismo, basta buscar o próximo byte de flag.;
- Problemas ocorrem quando os dados recebidos das camadas superiores
contenham o padrão do byte de flag. Para contornar isso, uma solução é inserir
um caractere de escape especial antes do byte de flag “acidental”. Essa técnica é
chamada de inserção de bytes ou inserçao de caracteres;
- Desvantagem: depende da utilização de caracteres de 8 bits;
- Em função disso, foram definidas novos métodos de marcação de quadro:
- Flags iniciais e finais, com inserção de bits: Esta técnica permite um número
arbitrário de bits e possibilita a utilização de códigos de caracteres com um
número arbitrário de bits por caractere.
- Violações de codificação da camada física: Só se aplica a redes nas quais a
Camada de Enlace: Enquadramento
- Violações de codificação da camada física: Só se aplica a redes nas quais a
decodificação no meio físico contém algum tipo de redundância. As
combinações alto-alto e baixo-baixo não são usados para dados, mas são
empregadas na delimitação de quadros de alguns protocolos;
- O controle de erros envolve a detecção de bits errados e, em um
segundo processo, a correção;
- Controlar erros significa garantir que a informação que chegou ao
destino é confiável. Isso pode implicar em descarte das informações
Camada de Enlace: Detecção e 
Correção de Erros
erradas;
- Para situações onde a retransmissão de dados custa mais caro que a
recuperação da informação, utilizam-se códigos de detecção e
correção de erros na camada de enlace;
-Principais opções: Bits de Paridade, Código de Hamming, CRC
- O mecanismo para verificação de ocorrência de erro chamada de
verificação de paridade faz com que o remete compute um bit
adicional , chamado de bit de paridade, e anexe-o a cada caractere
antes do envio;
Camada de Enlace: Bits de Paridade
- Após o recebimento de todos os bits do caractere, o destinatário
remove o bit de paridade, executa a mesma computação que o
remetente e verifica se o resultado está de acordo com o bit de
paridade;
- Existem 2 formas de paridade: par e ímpar. Remetente e destinatário
devem combinar qual destas será utilizada;
- A computação de paridade, tanto na par quanto na ímpar, é direta: o
bit de paridade assume valor0 ou 1 de acordo com o número de bits 1
no caractere.
- Ou seja, se a paridade é par, o número de bits 1 deve ser par. Se a paridade é
impar, o número de bits 1 deve ser ímpar.
Camada de Enlace: Bits de Paridade
impar, o número de bits 1 deve ser ímpar.
- Se todos os bits do caractere chegarem intactos, a computação do
destinatário concordará com o remetente. Se ocorrer interferência em
um bit, a computação do destinatário não concordará com o do
receptor e esse reportará um erro de paridade.
- Exercício de Fixação – Bits de Paridade:
1. Defina o valor do bit de paridade ímpar considerando que o caractere desse
sistema trabalha com 7 bits.
a) 0010011
Camada de Enlace: Bits de Paridade
b) 0101000
c) 1110001
2. Considerando que os bits a seguir representam recepções com verificação
de paridade par, identifique se ocorreu erro ou não na transmissão:
a) 00111001
b) 11001110
- É um código de detecção, isto é, permite não apenas detectar a
presença de erro de um bit, mas também definir a localização do bit
errado;
- Considere uma palavra de 8 bits. Numere os bits da esquerda para a
Camada de Enlace: Código de Hamming
direita como: m1m2m3m4m5m6m7m8
- A esse dado de 8 bits vamos acrescentar 4 bits adicionais, formando
o código de Hamming de 12 bits.
- Para isso, numere os bits do código de Hamming como sendo:
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12
- Os bits do Código de Hamming são assim calculados:
Camada de Enlace: Código de Hamming
-x3 = m1
-x5 = m2
-x6 = m3
-x7 = m4
-x1 = x3 x5 x7 x9 x11
-x2 = x3 x6 x7 x10 x11
-x4 = x5 x6 x7 x12
-x8 = x9 x10 x11 x12-x7 = m4
-x9 = m5
-x10 = m6
-x11 = m7
-x12 = m8
-x8 = x9 x10 x11 x12
onde o símbolo representa a operação “Ou Exclusivo”, ou seja,
entradas iguais resultam saída 0; entradas diferentes, saída 1.
- Observe que, dados bits A e B, a operação “Ou Exclusivo” C = A B
calcula o bit paridade (par) dos bits dados;
- Agora suponha que esses 12 bits são lidos como sendo:
y1y2y3y4y5y6y7y8y9y10y11y12
Camada de Enlace: Código de Hamming
- Se não houver erro, então cada yi é igual a seu respectivo xi. Se
houver erro em um bit apenas, é possível detectar esse erro e corrigi-
lo.
- Para isso fazemos o seguinte cálculo de 4 bits, denominados k1, k2,
k3 e k4:
• k1 = y1 y3 y5 y7 y9 y11
• k2 = y2 y3 y6 y7 y10 y11
• k3 = y4 y5 y6 y7 y12
• k4 = y8 y9 y10 y11 y12
Camada de Enlace: Código de Hamming
• k4 = y8 y9 y10 y11 y12
- Se k1 = k2 = k3 = k4 = 0, então não há erro;
- Senão o número binário codificado pelos 4 bits, k4k3k2k1,
determina a posição do bit errado, isto é, se k4k3k2k1 = 0111 então o
bit y7 está errado.
- Exercício de Fixação – Código de Hamming:
1. Calcule o código de Hamming de 12 bits que deve ser transmitido caso a
informação original seja:
a) Caractere ESC em ASCII – 00011011
b) Caractere 7 em ASCII – 00110111
Camada de Enlace: Código de Hamming
b) Caractere 7 em ASCII – 00110111
2. Identifique a mensagem enviada e verifique se ocorreram erros na recepção
dos caracteres considerando que foi utilizado o código de Hamming de 12
bits:
a) 001010111000
b) 001110111011
- Para diminuir o overhead de dados transmitidos pelos códigos de
detecção e correção de erros, além de também oferecer a detecção de
erros mesmo na ocorrência de mais de um erro por quadro, utiliza-se o
método do código polinomial;
Camada de Enlace: Código CRC
-Este método também é conhecido como “código de redundância
cíclica” ou CRC (Cyclic Redundancy Check);
-Os códigos polinomiais se baseiam no tratamento de strings de bits
como representações de polinômios com coeficientes 0 e 1 apenas, ou
seja, para um quadro de k bits considera-se a lista de coeficientes para
um polinômio de k termos, onde os graus variam de k-1 até 0;
- Tanto a adição quanto a subtração são idênticas à operação Ou
Exclusivo ou XOR:
- Entradas iguais resultam em zero;
- Entradas diferentes resultam em um;
Camada de Enlace: Código CRC
-Neste método, antes da transmissão dos quadros, a origem e o destino
concordam quanto ao uso de um polinômio gerador.
- Os bits de mais alta ordem e de mais baixa ordem devem ter
coeficiente igual a 1;
- A mensagem a ser transmitida possua mais bits que o polinômio
gerador;
-A ideia é transmitir a mensagem adicionada a um valor de verificação
ao final do quadro (resto da divisão M/G), de forma a permitir que o
Camada de Enlace: Código CRC
ao final do quadro (resto da divisão M/G), de forma a permitir que o
polinômio resultante seja divisível pelo polinômio gerador acordado;
-Exemplo: 110001 = x5 + x4 + 1
-A aritmética polinomial é feita em módulo 2 sem transportes para a
adição nem empréstimos para a subtração;
- Considerando-se a Mensagem M(x) e o polinômio gerador G(x)
abaixo, o polinômio resultante a ser transmitido T(x) é:
- M(x) = x5+ x4+ x3+ x + 1 = 111011
- G(x) = x4 + x + 1 = 10011
Camada de Enlace: Código CRC
- M(x) /G(x) = quoeficiente = 100001
resto (CRC) = 1001
- T(x) = M(x) + CRC = 1110111001
- Ao receber o quadro com o total de verificação, o receptor divide
este por G, ou seja, ele calcula (R+E)/G, onde E representa os erros
que podem ter ocorrido durante a transmissão;
- Se houver ocorrido um erro de um único bit, E = xi, onde i
Camada de Enlace: Código CRC
- Se houver ocorrido um erro de um único bit, E = xi, onde i
determina o bit incorreto. Se contiver dois ou mais termos, G nunca
dividirá (R+E); portanto, todos os erros de um único bit serão
detectados;
- No exemplo anterior, encontraríamos R = 0 , informando que não houve erro
na transmissão.
- Certos polinômios se tornaram padrões internacionais:
- CRC-8 = x8 + x7 + x6 + x4 + x2 + 1
- CRC-16 = x16 + x12+ x5 + 1
- CRC-32 = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5+
Camada de Enlace: Código CRC
x4 + x2 + x + 1
- O protocolo PPP utiliza o CRC-16 enquanto o protocolo HDLC e o
padrão IEEE 802 (incluindo as redes Ethernet e WiFi) utilizam CRC-
16 ou CRC-32;
- Exercício de Fixação – Código CRC:
1. Encontre o total verificador que deve ser unido a mensagem M usando-se o
polinômio gerador G:
M = 101101 e G = 10011
Camada de Enlace: Código CRC
2. Aplique o polinômio gerador G na mensagem recebida R para verificar se
ocorreu algum erro de transmissão:
R = 1100111001 e G = 11101