Camada de Enlace de Dados - Departamento de Informáticaelvio/redes/3-Enlace.pdfCamada de Enlace de...

Camada de Enlace de Dados

Redes de Computadores3. Camada de Enlace de Dados

Elvio Leonardo

DIN/CTC/UEM

2008

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Funcoes Principais

I Lidar com erros de transmissao

I Regular o fluxo de dados

I Enquadramento:

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Funcoes Principais

I Divide informacao em quadros:I Verifica se quadros chegaram corretamenteI Caso contrario:

I Descarta quadro eI Solicita retransmissao somente do quadro e nao de toda a

informacao

I Servicos oferecidos a Camada de Rede:I Servico sem conexao e sem confirmacaoI Servico sem conexao com confirmacaoI Servico orientado a conexoes com confirmacao

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Enquadramento com Contador

(a) recepcao sem erros (b) recepcao com erros

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Enquadramento com Byte Stuffing

(a) quadro delimitado por flag bytes (b) exemplos de sequencias de bytes antes e depois do stuffing

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Enquadramento com Bit Stuffing

I Permite caracteres com qualquer numero de bitsI Cada quadro comeca e termina com uma sequencia padrao

I Exemplo: 01111110

I Caso o padrao aconteca no campo de dados, bits sao incluıdospara quebrar a sequencia

(a) sequencia original (b) sequencia apos bit stuffing (c) sequencia apos de-stuffing

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Deteccao e Correcao de ErrosI Existem codigos detectores de erros e codigos detectores e

corretores de errosI Codigo adicionam redundancia

I Seja k o numero de bits de informacaoI Seja r o numero de bits adicionados para protecaoI Seja n = k + r o numero total de bitsI Portanto, das 2n palavras possıveis utilizam-se apenas 2k

I Hamming Distance (Distancia Hamming) = DH(w1, w2)I Numero de bits diferentes entre as palavras w1 e w2

I A Distancia Hamming de um codigo e a menor distancia dentre quaisquer duas palavras do codigo

I Deteccao de n bits erradosI Distancia Hamming do codigo = n + 1

I Correcao de n bits erradosI Distancia Hamming do codigo = 2n + 1

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Paridade

I Acrescenta 1 bit a palavra de informacao de maneira que onumero de bits com valor 1 na palavra transmitida fique par(ou impar)

I Exemplo: 10101 + 1 = 101011 (para paridade par)I Exemplo: 10101 + 0 = 101010 (para paridade ımpar)

I No receptor, a informacao recebida esta errada quando onumero de bits com valor 1 na palavra recebida naocorresponde ao esperado

I A Distancia Hamming deste codigo e d = 2 e portanto capazde detectar erro em 1 bit, mas incapaz de corrigir qualquererro

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Repeticao

I Repete cada bit n vezesI Exemplo (com n = 3): 1 + 11 = 111

I No receptor, se os bits nao aparecem em trincas significa erro

I A Distancia Hamming do codigo e d = 3 e portanto ele ecapaz de detectar erros em ate 2 bits e corrigir erro em 1 bit

I Exemplos para transmissao de 111:I Erro em 1 bit: Recepcao de 110 e corrigido para 111 e e

corretamente decodificado como bit de informacao 1I Erro em 2 bits: Recepcao de 100 e corrigido para 000 e e

incorretamente decodificado como bit de informacao 0

I Codigo ineficiente (neste caso, reduzindo a vazao em 3 vezesou redundancia de 67% para apenas d = 3)

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Codigos de HammingI Codigos de bloco criados por Richard Hamming, com

distancia d = 3 (portanto corrige erros em 1 bit e detectaerros em ate 2 bits)

I Bits de redundancia = r (r ≥ 2)I Bits de informacao = k = 2r − r − 1I Comprimento total = n = k + r = 2r − 1

I Exemplos:I r = 2, n = 3 e k = 1 (redundancia de 2/3 ≈ 67%)I r = 3, n = 7 e k = 4 (redundancia de 3/7 ≈ 43%)I r = 4, n = 15 e k = 11 (redundancia de 4/15 ≈ 27%)I r = 10, n = 1023 e k = 1013 (redundancia de 10/1023 ≈ 1%)I Eficiencia do codigo aumenta com o comprimento

I Posicao dos bits:I Bits de redundancia = multiplos de 2 = 1, 2, 4, 8, . . .I Bits de informacao = demais posicoes

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Codigos de HammingI Exemplo:

I Codigo de Hamming com n = 15, k = 11 e r = 4

posicao → 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15bits → p1 p2 d1 p3 d2 d3 d4 p4 d5 d6 d7 d8 d9 d10 d11

informacao di → 1 0 0 1 0 0 0 1 1 0 0paridade p1 → X X X X X X X Xparidade p2 → X X X X X X X Xparidade p3 → X X X X X X X Xparidade p4 → X X X X X X X Xtransmitido → 1 0 1 1 0 0 1 0 0 0 0 1 1 0 0

recebido → 1 0 1 1 0 0 1 0 0 0 1 1 1 0 0paridade p1 → E X X X X X X Xparidade p2 → E X X X X X X Xparidade p3 → X X X X X X X Xparidade p4 → E X X X X X X Xcorrigido → 1 0 1 1 0 0 1 0 0 0 0 1 1 0 0

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Cyclic Redundancy Check (CRC)

I O que e melhor: corrigir ou apenas detectar?

I Exemplo:

I Enlace com taxa de erro de bit de 10−6 (1 bit errado a cada106 = 1.000.000)

I Comunicacao em blocos de 1000 bits

I Correcao de erros simples:I Utilizando Codigo de Hamming, r = 10, n = 1023 e k = 1013I Custo da correcao de aproximadamente 1%

I Deteccao de erros simples:I Utilizando 1 bit de paridade por bloco, custo de 0,1%I Retransmissao de blocos errados (1 a cada 1000 blocos),

custo de 0,1%I Custo total de 0,2%

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

CRC

I Codigos cıclicos utilizados na deteccao de erros

I Produz um checksum que e enviado com a informacao

I Consegue detectar:I qualquer polinomio de erro E (x) que nao e divisıvel por G (x)I qualquer erro simples desde que o polinomio gerador G (x)

tenha 2 ou mais termosI qualquer erro duplo cuja distancia seja menor que a ordem de

G (x)I qualquer erro de um numero ımpar de bits desde que G (x) seja

multiplo de (x + 1)I erros em rajadas com comprimento ate a ordem de G (x) desde

que G (x) tenha o termo x0

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

CRC

I RepresentacaoI Codigo descrito pelo polinomio gerador G (x) de ordem rI Informacao descrita pelo polinomio M(x)I Operacoes em modulo 2, sem emprestimo na subtracao ou

carregamento na adicao

I OperacaoI Acrescentar r bits 0 ao polinomio M(x), isto e, x rM(x)I Realizar a divisao x rM(x)/G (x) e transmitir o resto desta

operacao junto com a informacao

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

CRC

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

CRC

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Specification and Description Language (SDL)

I Recomendacao ITU Z.100

I Linguagem de especificacao para sistemas reativosdistribuıdos, inicialmente para sistemas de telecomunicacoes,mas que hoje tem aplicacao mais ampla

I Possui representacao grafica e textual

I Possui linguagem formal para especificacao clara, precisa esem ambiguidades

I Pode ser utilizada em ferramentas de geracao automatica decodigo

I Pode ser utilizada em ferramentas de simulacao de sistemas

I Define padrao publico (nao proprietario)

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

SDL: SistemaI Sistema e composto de blocos conectados por canaisI Canais carregam sinais entre blocos e com o exterior

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

SDL: BlocoI Bloco e composto de processos conectados por canaisI Canais carregam sinais entre processos e com o exterior

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

SDL: ProcessoI Processo contem a maquina de estados

I Processo consome e produz sinais (consome estımulos eproduz respostas)

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

SDL: Processo

I Processo contem tarefas, decisoes e procedimentos

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

SDL: ProcedimentoI Procedimento e equivalente a subrotinas

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Message Sequence Chart (MSC)I Utilizado para mostrar o comportamento dinamico do sistema

atraves de sequencias de mensagens

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Protocolo Simplex Sem Erros e Sem Restricoes

pacote

único

quadro

-

quadro

único

pacote

-

Transmissor Receptor

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Protocolo Simplex Stop-and-Go Sem Erros

pacote

vazio

quadro

espera

Receptor

ack

-

pacote

espera

espera

ack

vazio

trata erro confirma

quadro

vazio

ack

-

pacote

Transmissor

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Protocolo Simplex Stop-and-Go Com Ruıdo

pacote

vazio

quadro(seq)

espera

*

-

pacote

espera

espera

ack

vazio

trata erro

confirma

Transmissor

iniciatempor.

timeout

falha

cnt_tx = 1

cancelatempor. cnt_tx <

max?quadro(seq)

-

iniciatempor.

cnt_tx =cnt_tx + 1vazio

cancelatransm.

SN

seq = -1

incr(seq)

Receptor nao mostrado; receptor deve detectar recepcao duplicada do mesmo quadro

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Melhorias

I Transmissao bi-direcional

I Piggybacking: espera um pacote de dados para embutir eenviar o ACK

I Quanto tempo esperar por esse pacote de dados?

I Fazer pacote de ACK curto (sem campo de dados)

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Janelas Deslizantes

I Janela de comprimento n

I Transmissor precisa de buffer com n posicoes para quadrospendentes (sem recebimento de ACK)

I Transmissor envia ate que, no maximo, n pacotes fiquempendentes

I Envia ate pacote numero (acked + n)I Numeracao dos pacotes em formato circular

I Numeracao de 0 ate n

I Recebimento de ACK para pacote m implica emacknowledgement de todos os pacotes anteriores

I Veja exemplo de codigo no livro texto

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Janelas DeslizantesI Exemplo para n = 7

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Janelas Deslizantes

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Go-Back-N e Retransmissao Seletiva

(a) Go-back-n (b) Retransmissao seletiva

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

High-level Data Link Control (HDLC)I Desenvolvido pela ISO, base para o LAPB (Link Access

Protocol, Balanced) da ITUI Desbalanceado: configuracao onde existe uma estacao

principal que controla o enlaceI Balanceado: inexistencia da relacao mestre-escravo, isto e,

qualquer estacao pode iniciar a comunicacaoI Orientado a bit, com utilizacao de bit stuffingI Modos

I Normal Response Mode (NRM): modo desbalanceado ondeestacoes secundarias somente transmitem se autorizadas pelaestacao principal; pode ser ponto-a-ponto ou multiponto

I Asynchronous Response Mode (ARM): modo desbalanceadoque permite a estacao secundaria iniciar a comunicacao

I Asynchronous Balanced Mode (ABM): enlaces full-duplexponto-a-ponto; utilizado no X.25

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

High-level Data Link Control (HDLC)

I Estrutura do quadroI Flag: delimita o quadroI Address (Endereco): desnecessario em linhas ponto-a-ponto

(utilizado para distincao entre comandos e respostas)I Control (Controle): identifica tipo de quadro, inclui numero

de sequencia e outros controlesI Data (Dado): quando presente, contem informacao de usuarioI Checksum: contem redundancia do tipo CRC

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

High-level Data Link Control (HDLC)

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

High-level Data Link Control (HDLC)I Quadros de supervisao

I Receive Ready (RR): usado para o confirmacao positivaI Reject (REJ): confirmacao negativaI Receive Not Ready (RNR): controle de fluxoI Selective Reject (SREJ): solicita retransmissao do quadro

especificado

I Quadros nao numeradosI Disconnect (DISC): desconectar o enlaceI Set Asynchronous Balanced Mode (SABM): solicitacao para

estabelecimento de enlace balanceadoI Set Normal Response Mode (SNRM): estabelecer enlace

desbalanceadoI Unnumbered Acknowledgement (UA): confirmacao generica de

recebimentoI Unnumbered Information (UI): informacao generica de camada

2

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

High-level Data Link Control (HDLC)

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

High-level Data Link Control (HDLC)

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

High-level Data Link Control (HDLC)

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Point-to-Point Protocol (PPP)I Descrito pela RFC 1661I Utilizado na transmissao de pacotes sobre cabo serial, linha

telefonica, telefone celular, enlace de radio ou fibra oticaI Composto por 3 partes:

I Encapsulamento de datagramasI Link Control Protocol (LCP)I Network Control Protocol (NCP)

I Encapsulamento:I Baseado no HLDC (exceto que orientado a bytes)I Protocolo: especifica o protocolo (LCP, NCP, IP, etc.)I Checksum: para detectar quadros com erros (similar ao CRC,

com 16 ou 32 bits)

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Link Control Protocol (LCP)

I Estabelecer, configurar, manter, terminar e testar o enlace dedados

I Usado para:I Iniciar e terminar a conexaoI Formato de encapsulamentoI Limites de tamanho dos pacotesI Detectar erros de configuracaoI Detectar loops infinitos

I Opcionalmente:I Autenticacao de identificacao

I Password Authentication Protocol (PAP)I Challenge Handshake Authentication Protocol (CHAP)

I Verificacao da qualidade do enlace

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Network Control Protocol (NCP)

I Composto por uma famılia de protocolos que se ajustam aoprotocolo de rede utilizado

I Exemplos:I Internet Protocol Control Protocol (IPCP): utilizado para IPI Internetworking Packet Exchange Control Protocol (IPXCP):

utilizado para IPXI NetBIOS Frames Control Protocol (NBFCP): utilizado para

NBFI IP Version 6 Control Protocol (IPv6CP): utilizado para IP

versao 6

Elvio Leonardo Redes de Computadores

Camada de Enlace de Dados

IntroducaoEnquadramentoControle de ErrosEstudos de Caso

Estados do PPP

Elvio Leonardo Redes de Computadores