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, acrescenta-

se 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