Camada de Enlace - LLC
Controle de Erros



Refere-se ao processo de garantir a entrega
confiável dos dados
Dados recebidos na camada de rede são
idênticos aos transmitidos
Duas estratégias:


Correção de erros por retransmissão
Correção autônoma de erros
Correção de Erros por
Retransmissão


Requer informação apenas suficiente no
fluxo de dados para que o nó receptor possa
detectar um erro durante a transmissão
Tendo detectado um erro o destino solicita a
origem retransmissão do quadro
Correção Autônoma de Erros




Requer informação redundante no fluxo de
dados para que o destino possa detectar e
corrigir os erros de forma autônoma
Não se baseia em retransmissão
O destino ao detectar um quadro com erro,
corrigi os erros por conta própria
Troca retransmissão por informação
redundante
Correção Autônoma de Erros





Custosa de implementar
Diversos bits extras são necessários para a
informação redundante e para localizar o bit
com erro
Implementada usualmente em canais simplex
Não se pode requisitar retransmissão
Na maioria das situações o método para
corrigir erros é a retransmissão
Correção de Erros


Redes locais Ethernet e 802.3 usam
retransmissão como correção de erros
Feito usando o CRC
Checagem de Soma




CRC - Checagem de Redundância Cíclica
Para checar uma série de bits o CRC constrói
um polinômio algébrico cujos coeficientes
dos termos são os valores dos bits
Um conjunto de dados com n bits
corresponde a um polinômio de grau n-1
O bit mais à esquerda é o coeficiente do
termo xn-1
Checagem de Soma

Exemplo:





10111101
1x7 + 0x6 + 1x5 + 1x4 + 1x3 + 1x2 + 0x1 + 1
x7 + x5 + x4 + x3 + x2 + 1
A seguir o polinômio é dividido por um
polinômio gerador pré-determinado
O conjunto de dados fica sendo o dividendo e
polinômio gerador o divisor
Checagem de Soma




O resto da divisão é a checagem de soma
(CRC) que é incluída no quadro
O destino executa um procedimento análogo
Se o CRC calculada pelo destino for igual à
do emissor, a divisão dá resto 0. Quadro
correto
Se CRC não casam, a origem é notificada e o
quadro retransmitido
Polinômios Geradores

CRC-16



Checagem de soma de 16 bits
X16 + x15 + x2 + 1
CRC-CCITT


Também de 16 bits
X16 + x12 + x5 + 1
Polinômios Geradores

CRC-32


Checagem de soma de 32 bits
Usada na maioria dos protocolos para redes locais
x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x

Ethernet, 802.3 e Token Ring
CRC - Eficiência


A eficiência do CRC é função do polinômio
gerador usado
CRC-16 e CRC-CCITT detectam:





100% dos erros únicos e duplos
Todos os erros em um número ímpar de bits
Falhas em 16 ou menos de 16 bits
99,997% das falhas em 17 bits
99,998% das falhas em 18 ou mais bits
CRC - Eficiência

CRC-32

A chance de termos dados ruins recebidos e não
detectados é aproximadamente 1 em 4.3 bilhões
CRC - Exemplo

Origem




Divide um quadro Tb por um divisor específico D
O resto R é incluído no campo de checagem de
soma do quadro
Ta representa o quadro completo, após cálculo de
CRC
Destino



Divide Ta por D
Se R = 0 --> não possui erros
Se R  0 --> erros, retransmissão do quadro
CRC - Exemplo

Polinômio gerador




X5 + x4 + x2 + x + 1
Ou seja D = 110111
Tb = 111000111000
Passo 1


Como polinômio gerador é de grau 5, acrescentase 5 zeros em Tb
11100011100000000
CRC - Exemplo

Passo 2
Dividimos a cadeia do passo 1 por D
 Lembre estamos usando binário, mod 2
 Não existe vai-um nem empresta-um
 Adição e subtração correspondem a XOR:
101101
-110011
011110

CRC - Exemplo
11100011’10’0’0’00’000 / 110111
110111
111111
110111
100010
110111
101010
110111
111010
110111
110100
110111
11000  Resto
CRC - Exemplo

Passo 3



Junte o Resto aos bits originais
Ta = 11100011100011000
Passo 4

Destino recebe Ta e efetua a divisão
CRC - Exemplo
11100011’10’0’0’11’000’ / 110111
110111
111111
110111
100010
110111
101010
110111
111010
110111
110111
110111
000000000 --> Resto
CRC - Exemplo


Como R = 0, não houve erros na transmissão do
quadro
Caso R  0, erro e retransmissão é necessária
CRC - Exercício

Polinômio gerador



X6 + x5 + x3 + 1
Tb = 111100001101
Calcule Ta e o Resto no destino