Mestrado em Telecomunicações
COMUNICAÇÃO DE DADOS
TE – 723
REDES DE COMPUTADORES
Aluno: Vicente Mazzolla Morais
Prof: Eduardo Parente Ribeiro
Outubro de 2002
Mestrado em Telecomunicações
TEMA DA APRESENTAÇÃO
•
•
Questões de Projeto da Camada de Enlace de Dados:
–
Serviços Fornecidos à Camada de Rede;
–
Enquadramento (Framing);
–
Controle de Erros;
–
Controle de Fluxos.
Detecção e Correção de Erros:
–
Códigos de Correção de Erros;
–
Códigos de Detecção de Erros.
Redes de Computadores
(parte 01)
Mestrado em Telecomunicações
CAMADA DE ENLACE
Função: transferir dados da camada de rede da máquina de
origem para a camada de rede da máquina de destino.
•
Alguns Serviços da Camada de Enlace:
–
Montagem de quadros para transmissão;
–
Controle de acesso ao meio físico;
–
Transmissão seqüencial dos quadros;
–
Recebimento dos quadros;
–
Detecção / Correção de Erros;
–
Retransmissão de quadros
–
Controle de fluxos.
Redes de Computadores
Mestrado em Telecomunicações
CAMADA DE ENLACE
•
Serviços Fornecidos à Camada de Rede:
1.
Serviço sem conexão e sem confirmação
–
Apropriado às redes onde a taxa de erros no nível físico é muito baixa;
–
Recuperação dos dados é realizada pelas camadas superiores;
–
Utilizado para transmissão de voz em tempo real.
2.
Serviço sem conexão com confirmação
–
Adequado quando um pequeno volume de dados deve ser transferido de
forma confiável;
–
Cada quadro enviado é individualmente confirmado;
–
Este serviço é apropriado em canais não confiáveis (sistema sem fio).
3.
Serviço orientado à conexão
–
Máquina de origem e destino estabelece conexão antes dos dados
serem transferidos;
–
Nível de Enlace garante que os quadros transmitidos sejam entregues
ao receptor sem erros e na ordem que foram enviados (quadros são
numerados).
Redes de Computadores
Mestrado em Telecomunicações
CAMADA DE ENLACE
•
Serviço orientado à conexão:
1.
Primeira fase
Utilização de variáveis e contadores para controle de quadros
enviados x não-recebidos.
2.
Segunda fase
Um ou mais quadros são realmente transmitidos.
3.
Terceira fase
Desconexão, são liberados as variáveis, buffers e os demais
recursos .
Redes de Computadores
Mestrado em Telecomunicações
ENLACE PONTO A PONTO
Exemplo:
HOST 01
HOST 02
(01)
(1) Mensagem ENQ
Mensagem ACK (2) ou
Mensagem NACK (2)
Questionamento enquiry para saber se o Host 2
está preparado para receber os dados.
Estabelecimento da
Conexão
(02)
Reconhecimento
positivo
acknowledgement
para indicar que o Host 2 está preparado.
ERP – Procedimento de Recuperação de Erro
ERP
(03)
(3) FRAME
Host 1 envia alguns dados (Frames) e realiza
uma pausa para esperar resultados.
Mensagem ACK (4) ou
Transferência de Dados
(04)
Mensagem NACK (4)
Reconhecimento
positivo
acknowledgement
para indicar recebimento bem sucedido.
ERP – Procedimento de Recuperação de Erro
ERP
(5) Mensagem EOT
Desconexão
(05)
Mensagem de fim de transmissão.
Redes de Computadores
Mestrado em Telecomunicações
ENLACE PONTO A PONTO
Roteador
Processo da
camada de
enlace de dados
2
Quadros
Processo de
roteamento
3
Protocolo de
enlace de
dados
2
Pacotes
2
2
3
Responsável pela confiabilidade
da linha de comunicação
Linha de Transmissão
para um roteador
1.
Hardware do roteador checa a soma de verificação (checksum) do quadro de entrada
e envia o quadro para o software da camada de enlace de dados;
2.
Software da camada de enlace verifica se esse é o quadro esperado, então, passa o
pacote contido no campo de carga útil (playload) para o software de roteamento;
3.
Software de roteamento seleciona a linha apropriada e envia o pacote para o
software da camada de enlace de dados.
Redes de Computadores
Mestrado em Telecomunicações
ENQUADRAMENTO
Estratégia: dividir o fluxo de bits em quadros e calcular o checksum em
relação a cada quadro .
•
Métodos para marcar o Início e o fim dos quadros:
1.
Contagem de Caracteres
Utiliza um campo do cabeçalho para especificar o número de caracteres do quadro.
Contagem de Caracteres
5
1
2
3
4
5
Quadro 1
5 caracteres
5
Erro de
Transmissão
1
2
3
Quadro 1
6
7
8
9
8
0
1
Quadro 2
5 caracteres
4
7
6
7
8
2
3
4
5
6
4
5
6
Quadro 3
8 caracteres
9
8
Quadro 2
(Incorreto)
0
1
2
3
Contagem de
caracteres (Agora)
• Checksum não dispõe de informação para identificar onde começa o quadro seguinte (perda da sincronização);
• Não resolve solicitar retransmissão, destinatário não reconhece quantos quadros deverão ser ignorados.
Redes de Computadores
Mestrado em Telecomunicações
ENQUADRAMENTO
2.
Caracteres iniciais e finais com inserção de caracteres(character stuffing)
Este método contorna o problema de sincronização após um erro .
Cada quadro começa com a seqüência de caracteres ASCII DLE STX (Data Link
Escape Start of Text) e termina com DLE EXT (Data Link Escape End of Text).
Dados enviados pela camada de rede
DLE
STX
A
DLE
B
DLE
ETX
Dados depois que a camada de enlace de dados inclui caracteres (stuffing)
DLE
STX
A
DLE
DLE
B
DLE
ETX
DLE inserido (stuffing)
Dados passados para camada de rede do receptor
DLE
STX
A
DLE
B
DLE
ETX
• Distinguir um enquadramento DLE STX ou DLE ETX de uma seqüência de caracteres contidas nos dados
com base na presença ou na ausência de uma única seqüência DLE;
• As seqüências DLE dos dados são sempre duplicadas;
• Desvantagem da utilização do método => Utiliza caracteres de 8 bits em geral caracteres ASCII.
Redes de Computadores
Mestrado em Telecomunicações
ENQUADRAMENTO
3.
Flags iniciais e finais com inserção de bits (bit stuffing)
Cada quadro começa e termina com um padrão de bits, 0111110, chamado Byte Flag.
Dados Originais
011011111111111111110010
Transmissor da camada de enlace de dados insere um bit 0 a cada 5 bits 1 enviados.
011011111011111011111010010
bits inserido
Receptor remove (destuffing) o bit 0 e armazena na memória.
011011111111111111110010
• A inserção de bits, assim como, a inserção de caracteres, é completamente transparente para a camada de rede;
Redes de Computadores
Mestrado em Telecomunicações
ENQUADRAMENTO
4.
Violações de codificação da camada física
Este método se aplica a redes nas quais a decodificação do meio físico contém
algum tipo de redundância. Ex: codificação de 1 bit de dados utilizando 2 bits
físicos.
Fluxo de bits
1
0
0
0
0
1
0
1
1
1
1
Cod. binária
Cod. Manchester
Cod. Manchester
diferencial
• Codificação Manchester IEEE 802.3 Ethernet: bit 1= nível alto no primeiro intervalo e baixo no segundo e o bit 0= nível
baixo no primeiro intervalo e alto no segundo;
•
Codificação Manchester diferencial IEEE 802.3 Ethernet: bit 1= indicado pela ausência de uma transição e bit 0= indicado
pela presença de uma transição (no início do bit).
Redes de Computadores
Mestrado em Telecomunicações
CONTROLE DE ERROS
Definição: mecanismo para detectar e corrigir erros na
transmissão de quadros.
Questão?
Como é possível certificar de que todos os quadros serão entregues na
camada de rede de destino, e na ordem correta?
•
Tipos de Erros:
1.
Quadro Perdido: o quadro não chega no receptor (ruído).
2.
Quadro Danificado: quadro é recebido mas um erro é detectado
(paridade, CRC).
Redes de Computadores
Mestrado em Telecomunicações
CONTROLE DE ERROS
•
•
Técnicas de Controle de Erro baseiam-se em:
1.
ACK positivo: receptor reconhece quadro(s) sem erros.
2.
Detecção de Erro - CRC
3.
ACK negativo e retransmissão: receptor envia NACK,
especificando número de seqüência do quadro sem erro.
4.
Retransmissão após “timeout”: a estação fonte retransmite um
quadro que não foi reconhecido após um determinado tempo.
Estes mecanismos são chamados de:
Pedido Automático de Retransmissão
(ARQ – Automatic Repeat Request)
•
Tipos:
1.
Envia e Espera (Stop-and-Wait);
2.
Retorna – n (Go-Back-n);
3.
Retransmissão Seletiva (Selective-reject).
Redes de Computadores
Mestrado em Telecomunicações
CONTROLE DE FLUXO
Definição: técnica para assegurar que a estação transmissora não
envie dados numa taxa maior do que a estação receptora
possa processar.
•
Técnicas de Controle de Fluxo baseiam-se em:
1.
Alocação de um “buffer”: o receptor irá alocar um buffer de
dados com algum comprimento máximo.
2.
Limpeza do “buffer”: o receptor irá realizar uma certa quantidade
de procedimento até que possa limpar o buffer e estar preparado
para receber mais dados.
Obs:na ausência de Controle de Fluxo poderá ocorrer sobrecarga
(overflow) do buffer enquanto processa dados antigos.
•
Métodos:
1.
Envia e Espera (Stop-and-Wait): mais simples
2.
Janela Deslizante (Sliding Window): mais eficiente
Redes de Computadores
Mestrado em Telecomunicações
DETECÇÃO E CORREÇÃO DE ERROS
•
Detecção de Erro: o quadro possui informações redundantes suficientes
para permitir que o receptor deduza que houve um erro, mas sem
identificar qual, e solicite retransmissão.
•
Correção de Erro: o quadro possui informações redundantes de forma a
permitir a identificação de qual bit contém erro. Não necessita reenvio.
Quadro:
Consiste em m bits de dados (mensagem) e de r bits redundantes ou
de verificação.
Palavra-código: n = m + r
A propriedade de detecção e correção depende da distância de Hamming
Distância de Hamming:
Número de posições de bits em que duas palavras de código diferem.
Exemplo:
palavra código de 7 bits
1101000 + 0110100 = 1011100 .: dHmín= 4
Redes de Computadores
Mestrado em Telecomunicações
CORREÇÃO DE ERROS
•
Código de Hamming:
–
Se duas palavras-código estiverem a uma distância de Hamming
d, será necessário corrigir d erros de bits para converter uma
palavra na outra;
–
Toda as 2m mensagens são válidas;
–
Nem todas as 2n possíveis palavras-código são usadas;
–
Para detectar d erros: dH = d + 1;
Capacidade de detecção do código: Cd = dHmín - 1
–
Para corrigir d erros: dH = 2.d + 1.
Capacidade de correção do código: Cc = (dHmín – 1) / 2
Exemplo: 0000000000, 0000011111, 1111100000 e 1111111111.
dHmín = 5
Cd = dHmín – 1 = 4
Redes de Computadores
(10 bits)
Cc = (dHmín – 1) / 2 = 2
Mestrado em Telecomunicações
CORREÇÃO DE ERROS
•
Código de Hamming: Erros Simples
–
Os bits da palavra-código são numerados, começando no bit 1
da extremidade esquerda;
–
Os bits que são potências de 2 (1, 2, 4,etc) são de verificação;
–
Os demais (3,5,6,etc) são preenchido com m bits de dados;
–
Cada bit de verificação força a um conjunto de bits (incluindo
ele) a ser par ou ímpar.
Exemplo: Caractere
Mensagem
H
ASCII
1001000
Cálculo dos bits de verificação de Paridade (PAR)
V1= b3 + b5 + b7 + b9 + b11 = 0 .: PAR
V2= b3 + b6 + b7 + b10 + b11 = 0 .: PAR
V4= b5 + b6 + b7 = 1 .: ÍMPAR
V8= b9 + b10 + b11 = 0 .: PAR
Redes de Computadores
palavra-código
7 btis
00110010000
11 btis
Mestrado em Telecomunicações
CORREÇÃO DE ERROS
•
Código de Hamming: Erros em Rajada
–
Seqüência de k
palavras-código é organizada como uma
matriz. Uma palavra por linha;
–
Os dados são transmitidos uma coluna por vez, começando
pela coluna mais à esquerda;
–
No receptor a matriz é reconstruída, uma coluna de cada vez;
–
Se ocorrer um erro em rajada de extensão k, no máximo 1 bit
de cada uma das k palavras-código será afetado;
–
O código de Hamming poderá corrigir um erro por palavracódigo, possibilitando a recuperação do bloco inteiro.
• Este método utiliza kr bits de verificação para tornar blocos de km dados
imunes a um único erro em rajada que tenha uma extensão menor ou igual a k.
Redes de Computadores
Mestrado em Telecomunicações
DETECÇÃO DE ERROS
•
bit de Paridade: é a forma mais simples de detecção de erros.
Inserção de 1 bit extra ao final de cada caractere de modo a deixar todos os
caracteres com um número par ou ímpar de bits 1.
Técnica de Paridade Par
Bit de paridade = 0, se o total de bit "1” for par
Bit de paridade = 1, se o total de bit "1” for ímpar
Ex: Caractere
1000010
1000011
+
Paridade
0
1
BYTE DE TRANSMISSÃO
o número total de Bits 1 é par
o número total de Bits 1 é ímpar
Técnica de Paridade Ímpar
Bit de paridade = 1, se o total de bit "1” for par
Bit de paridade = 0, se o total de bit "1” for ímpar
Ex: Caractere
1000010
1000011
+
Paridade
1
0
BYTE DE TRANSMISSÃO
o número total de Bits 1 é par
o número total de Bits 1 é ímpar
• Caso um número par de bits tenha sido invertido não é possível detectar o erro.
Redes de Computadores
Mestrado em Telecomunicações
DETECÇÃO DE ERROS
•
CRC – Cyclic Redundancy Check: forma mais eficiente de detecção de
erros.
–
Cadeia de bits tratados como representações de polinômios;
–
K bits = polinômio Xk-1 + Xk-2 + Xk-3 + ... + X0 ;
Ex: 110001 possui 6 bits .: X5 + X4 + X0
–
Aritmética polinomial em módulo 2 (soma e subtração = XOR);
–
Transmissor e Receptor devem concordar em relação ao
polinômio gerador G(x) ;
–
Tanto o bit de mais alta ordem quanto o de mais baixa ordem
de G(x), devem ser = 1.
Redes de Computadores
Mestrado em Telecomunicações
DETECÇÃO DE ERROS
•
CRC - Algoritmo para calcular o checksum:
Idéia: acrescentar um checksum no final do quadro, de forma que o
polinômio
representado pelo quadro modificado seja divisível por G(x).
1.
Definir r como o grau de G(x). Acrescentar r bits zero à
extremidade de baixa ordem do quadro, de modo que ele passe
a conter m + r bits e corresponda ao polinômio xr M(x);
2.
Dividir (módulo 2 ) G(x) por xr M(x);
3.
Subtraia (módulo 2) o resto da divisão e acrescente no
polinômio original, formando T(x) polinômio a ser transmitido.
Exemplo:
Quadro M(x): 1101011011
(10 bits)
Gerador: 10011 .: G(x) = X4 + X + 1
Mensagem xr M(x): 11010110110000
Quadro transmitido T(x) : 11010110111110 resto
Redes de Computadores
Mestrado em Telecomunicações
DETECÇÃO DE ERROS
•
CRC - Algoritmo para calcular o checksum:continuação
a.
No receptor T(x) é dividido por G(x). Caso haja erro T(x)
passa a ser T(x) + E(x);
•
b.
O resultado da divisão será E(x) / G(x);
c.
Para que os erros possam se detectados E(x) / G(x) deve ser
diferente de Zero;
Padrões de Polinômios:
para caracteres de 6 bits
1.
CRC-12 = X12 + X11 + X3 + X2 + X1 + 1 (checksum 12 bits)
para caracteres de 8 bits
1.
CRC-16 = X16 + X15 + X2 + 1 (checksum 16 bits)
2.
CRC- CCITT = X16 + X12 + X5 + 1 (checksum 16 bits)
Redes de Computadores