Aula 2
6.263/16.37
A Camada de Enlace de Dados:
Delimitação de Quadro & Detecção de Erro
Eytan Modiano
MIT, LIDS
1
Camada de Enlace de Dados
(Data Link Layer- DLC)
• Responsável pela transmissão confiável dos pacotes ao longo de
um enlace:
– Delimitação (Framing): Determina o início e o fim dos
pacotes (2,5 segundos).
– Detecção de erro: Determina quando um pacote contém erro
(2,3 segundos).
– Recuperação do erro: Retransmissão dos pacotes contendo
erros (s2,4 segundos).
• DLC camada de recuperação,
• Pode ser feita em camadas mais altas.
2
Delimitação
010100111010100100101010100111000100
Onde estão os dados?
•
•
Existem três procedimentos para delimitar um quadro:
1. Orientado a caráter.
2. Contagem do comprimento.
- comprimento fixo.
4. Protocolo orientado a bit (bandeira).
3
Delimitação Orientada a Carácter
SYN carácter especial utilizado entre quadros.
STX carácter que indica início do quadro.
ETX carácter que indica fim do quadro
• Códigos de caracteres padrões tais como ASCII e EBCDIC contêm
caracteres especiais que não aparecem nos dados.
• Toda a transmissão é baseada neste código de carácteres.
4
Problemas Com a Delimitação Orientada à Caractéres
• Dependente do código de caractéres.
– Como você envia dados binários?
• Os quadros devem ser números inteiros de caractéres
• Erros nos caracteres de controle interferem muito na delimitação.
NOTA: Método primário de delimitação de 1960 a ~1975.
5
Procedimento Pelo Campo de Comprimento
(DECNET)
• Utiliza um campo do cabeçalho para fornecer o comprimento do
quadro (em bits ou bytes),
– O receptor procura no campo de comprimento do cabeçalho do
pacote para determinar o comprimento do pacote.
• O campo de comprimento deve ter seu comprimento em bit igual a log2
(Max_Size_Packet) + 1;
– Isto limita o comprimento do pacote a ser utilizado.
• Problemas com este procedimento
– Dificuldade em se recuperar de situações de erro;
– Uma re-sincronização é necessária após ocorrer erro no contador de
comprimento.
6
Pacotes de Comprimento Fixo
(Ex.: ATM)
• Todos os pacotes são de mesmo tamanho.
– Nas redes ATM todos os pacotes são de 53 bytes.
• Requerem sincronização após a inicialização.
• Problemas :
– Os comprimentos das mensagens não são múltiplos do tamanho do
pacote;
– o último pacote de uma mensagem pode conter bits de
preenchimento (ineficiente);
– Problemas com a sincronização;
– Segmentação e Recomposição são complicadas em altas taxas de
transmissão.
7
Delimitação Orientada a Bit
(Bandeira)
• Uma bandeira é uma seqüência fixa de bits para indicar o início e o fim
de um pacote.
– Uma única bandeira pode ser utilizada para indicar tanto o início
como o fim de um pacote.
• A princípio qualquer seqüência poderia ser usada, mas o aparecimento
da bandeira deve ser prevenido nos dados.
– Protocolos padrões usam uma seqüência de 8 -bits, 01111110,
como bandeira;
– Usam 01111111..1110 (<16 bits) como aborto sob condições de
erro;
– Bandeira com todos 1’s é considerada como estado não ativo.
• Portanto 0111111é a seqüência que não deve aparecer nos dados.
• INVENTADO ~ 1970 pela IBM para o SDLC (synchronous data link
protocol).
8
Preenchimento
(Transmissor)
• Utilizado para remover a bandeira a partir dos dados.
• Um 0 é inserido após cinco 1’s consecutivos no quadro.
• Porque é necessário inserir 0 em 0111110?
– Se não inserirmos, então:
0111110111 -> 0111110111
011111111 -> 0111110111
– Como é possível diferenciar no receptor?
9
Retirando o Preenchimento – Destuffing
(Receptor)
• Retirando o preenchimento. (DESTUFFING ) (Receptor)
• Se 0 é precedido por 011111 no fluxo de bits então é removido.
• Se 0 é precedido por 0111111, então é o bit final da bandeira.
Exemplo: Bits a serem removidos estão sublinhados abaixo.
10
Overhead
• Em geral com uma bandeira 01K0 o bit 0 de preenchimento é
necessário sempre que a seqüência 01k-1 aparece no fluxo de dados
• Para um pacote de comprimento L isto vai ocorrer cerca de L/2k vezes
ou seja o overhead médio é:
E {OH} = L/ 2k + (k+ 2) bits
• Para uma bandeira de 8 bits OH ~ 8 + L/64
– Para pacotes grandes a eficiência é ~ 1 -1/64 = 98,5 (ou 1,5%
overhead).
• Comprimento primo da bandeira
– Se os pacotes são longos mais longa é a bandeira (menos
preenchimento).
– Se os pacotes são curtos mais curta é a bandeira (reduz o overhead
devido à bandeira).
Kopt ~ log2 (L)
11
Erros no Delineamento
• Todas as técnicas de delineamento são sensíveis a erros.
– Um erro no campo que contém o comprimento causa a terminação
do quadro em um ponto errado (e torna difícil determinar o início
do próximo quadro).
– Um erro em DLE, STX, ou ETX causa o mesmo problema.
– Um erro na bandeira, ou uma bandeira criada por um erro causa o
desaparecimento de um quadro ou aparecimento de quadro extra.
• O procedimento que usa a bandeira é menos sensível a erros pois uma
bandeira irá eventualmente aparecer novamente para indicar o fim do
próximo quadro.
– A única coisa que ocorre é que um pacote errado foi criado.
– Este pacote errado pode ser removido através de uma detecção de
erro.
12
Técnicas de Detecção de Erro
• Utilizada pelo receptor para determinar se o pacote contém erros.
• Se houver detecção de erro o receptor pede ao transmissor para reenviar o pacote.
• Técnicas de detecção de erro:
– Cheque de paridade
• Únicos bits
• Cheque de redundância horizontal e vertical
– Cheque de redundância cíclico (CRC).
13
Eficiência da Técnica de Detecção de Erro
•
A eficiência de um código para detecção de erro é geralmente medida
por meio de três parâmetros:
1) mínima distância do código (d) (número mínimo de bits errados não
detectados).A distância mínima de um código é o menor número de
erros que podem mapear uma palavra código em uma outra. Se menos
que d erros ocorrerem eles serão sempre detectados.Mesmo mais que
d erros irão ser detectados com uma certa freqüência (mas não
sempre!);
2) Habilidade em detectar rajadas (B) (comprimento máximo da rajada
que é sempre detectada);
3) probabilidade de que um conjunto aleatório de bits faça com que um
pacote errado seja aceito como correto ou livre de erros (bom
estimador se o número de erros em um quadro é >> d ou B)
• Útil quando o delimitador é perdido.
• K bits de info. => 2k palavras código válidas.
• Com r bits de cheque a probabilidade de que uma seqüência
aleatória de bits de comprimento k+r mapeie uma das 2k
palavras código é 2k/2k+r = 2-r .
14
Códigos de Cheque de Paridade
k bits de dados
r bits de cheque
• Cada cheque de paridade é a soma em modulo 2 de alguns dos bits de
dados.
• Exemplo:
C1 = x1 + x2 + x3
C2 = x2 + x3 + x4
C3 = x1 + x2 + x4
15
Código de Cheque de Paridade Par
• O bit de cheque é 1 se o quadro contém um número impar de 1’s; caso
contrário é 0:
1011011 → 10110111
1100110 → 11001100
• Portanto o quadro codificado contém um numero par de 1’s.
• O receptor conta o número d 1’s no quadro.
– Um número par de 1’s é interpretado como ausência de erro.
– Um número impar de 1’s é interpretado como ocorrência de erro.
Um número impar de erros pode ser detectado.
Um número par de erros não pode ser detectado.
• Probabilidade de não detectar erro (erros independentes)
N i
P (un det ected ) = ∑   p (1 − p ) N −i
i⋅even i 
N = tamanho do pacote
P = probabilidade de erro
16
Paridade Horizontal e Vertical
• Os dados são vistos como um array retangular (ex.: uma seqüência de
palavras).
• Distância mínima = 4, quaisquer 4 erros em uma configuração
retangular são não detectáveis.
17
Cheque de Redundância Cíclica (CRC)
M = bits de informação
R = bits de cheque
T = palavra código
• Um CRC é implementado usando
um registrador de deslocamento.
18
Cheque de Redundância Cíclica
T = M 2r + R
• Como calcular R (os bits de cheque)?
– Escolha um gerador G como sendo uma string de bits com
comprimento de r+1 bits.
– Escolha R tal que T é um múltiplo de G (T = A*G, for some A).
– Agora quando T é dividido por G o resto será nulo => não há
erros.
– Tudo é feito usando aritmética mod 2.
T = M 2r + R = A*G => M 2r = A*G + R (aritmética mod 2)
Seja R = resto de M 2r/G e T será um múltiplo de G.
• A escolha de G é um parâmetro crítico para o desempenho do CRC.
19
Exemplo
r = 3, G = 1001
M = 110101 => M2r = 110101000
20
Verificando a Ocorrência de Erros
• Seja T’ a seqüência recebida
• Divide T’ por G
– Se o resto = 0 assume que não há erros
– Se o resto não é zero então erros foram encontrados
• Exemplo:
Envia T = 110101011
Não há forma de saber quantos erros
aconteceram ou quais bits estão em erro.
21
Divisão Mod 2 Como Divisão Polinomial
22
Implementando Um CRC
23
Desempenho do CRC
•
Para r bits de cheque por quadro e quadro de comprimento menor 2r-1,
pode-se detectar:
1) Todos os conjuntos de 1,2, ou 3 erros (d > 3).
2) Grande número aleatório de erros probabilidade 1-2-r.
•
Standard DLC' padrão usa um CRC com r=6 com opção de r=32.
– CRC-16, G = X16 + X15 + X2 +1 = 11000000000000101
24
Características de Erro da Camada Física
• A maioria das camadas físicas não é bem descrita por um simples
parâmetro de BER.
• A maioria dos processos de erros na camada física tende a criar uma
mistura de erros aleatórios & rajadas.
• Um canal com uma BER de 10-7 e um tamanco médio de rajada de
1000 bits é muito diferente daquele com erros aleatórios
independentes.
• Exemplo: Para um quadro de comprimento médio de 104 bits:
– Canal aleatório: E [taxa de quadros errados] ~ 10-3;
– Canal com rajada: E [taxa de quadros errados] ~ 10-6.
• É melhor caracterizar um canal pela taxa de quadros errados.
• Este é um problema difícil para nos sistemas reais.
25