Teleprocessamento e Redes
Capítulo 3:
Camada de Enlace
Prof. Fábio M. Costa
INF / UFG
Introdução

Estudo de técnicas e algoritmos para se
obter comunicação confiável e eficiente entre
duas máquinas conectadas por um canal
direto
–
–
–

Propriedade essencial do canal:
–
2
através de um cabo (par trançado, coaxial, etc.)
através de uma linha telefônica
etc.
Bits são entregues na mesma ordem em que
foram enviados
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Introdução (2)

Problemas envolvidos
–
–
–

3
Erros introduzidos nos meios de transmissão
Taxa de transmissão limitada
Atrasos de propagação
Protocolos da camada de enlace devem
tratar tais problemas, fornecendo à camada
superior (camada de rede) a “ilusão” de um
canal “perfeito” (ou quase)
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Posicionamento da camada de enlace
4
Rede
Rede
Rede
Rede
Rede
Enlace
Enlace
Enlace
Enlace
Enlace
Enlace
Enlace
Física
Física
Física
Física
Física
Física
Física
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
5
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Unidades de transmissão de dados:
Nomenclatura utilizada




6
Camada de Transporte: Mensagens
Camada de Rede: Pacotes
Camada de Enlace: Quadros
Camada Física: Bits
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Aspectos de projeto




7
Tipo do serviço provido à camada de rede
Enquadramento (delimitação) dos dados
transmitidos
Controle de erros
Controle de fluxo
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Serviço provido à camada de rede
8
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Tipos de serviço



9
Serviço sem conexão e sem reconhecimento
Serviço sem conexão, com reconhecimento
Serviço orientado a conexões e com
reconhecimento
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Serviço sem conexão e sem
reconhecimento




Unidades de transmissão de dados (quadros)
independentes são enviados da máquina
origem para a máquina destino
Sem que a máquina destino envie de volta o
reconhecimento da recepção dos quadros
Perda de quadros (p. ex., devido a erros de
transmissão) não é tratada
Apropriado quando
–
–
10
Taxa de erros é muito baixa
Tráfego em tempo-real
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Serviço sem conexão, com
reconhecimento (Acknowledgement)


Quadros transmitidos independentemente
uns dos outros
Cada quadro é individualmente reconhecido
pela máquina destino da transmissão
–
–
11
Reconhecimento: quadro especial transmitido
de volta para a máquina origem da transmissão,
informando que um quadro foi recebido com
sucesso
Reconhecimento negativo: quadro não foi
recebido ou foi recebido com erros
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Serviço sem conexão, com
reconhecimento (2)

Caso um reconhecimento não chegue após um
certo tempo (a contar do instante em que o quadro
foi transmitido inicialmente):
–
–

Entretanto:
–

Se o quadro de reconhecimento em si for perdido, o quadro
de dados original será retransmitido, gerando uma
duplicação (que pode ser indesejável)
Serviço apropriado quando o meio de transmissão
(canal) é essencialmente não confiável
–
–
12
Timeout
Quadro é retransmitido
i.e., altas taxas de erros
Ex.: meios de transmissão sem-fio
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Considerações sobre
reconhecimentos

Acknowledgements (Acks) podem também ser
providos pelas camadas superiores
–

Ex.: camada de transporte (nível 4)
Entretanto, provê-los apenas nos níveis superiores
pode não ser eficiente. Exemplo:
–
Protocolo de transporte trabalha com mensagens longas

–
Implicações da perda de uma mensagem:


13
Fragmentadas em múltiplos quadros para transmissão através
do serviço da camada de enlace
Somente seria detectada após um tempo considerável
Uma grande quantidade de dados precisaria ser retransmitida
devido a, por exemplo, um erro apenas um quadro
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Considerações sobre
reconhecimentos (2)

Provê-los no nível da camada de enlace pode ser
mais eficiente
–
–

No exemplo anterior, apenas um quadro seria retransmitido
(não a mensagem completa)
Operação dirigida por hardware (implementação da
camada de enlace na placa de rede)
Acknowledgements podem ainda ser providos
(redundantemente) na camada de transporte
–
Para um nível de confiabilidade maior

–
14
Por exemplo, para lidar com falhas de roteamento de pacotes
na rede
Ex.: o protocolo TCP utilizado na Internet
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Serviço orientado a conexões, com
reconhecimento

Uma conexão deve ser estabelecida antes
que dados possam ser transmitidos
–

Quadros são transmitidos dentro do contexto
de uma conexão
–
–
15
Representa um contexto de comunicação bem
delimitado
As mesmas propriedados são aplicadas a todos
os quadros pertencentes a uma conexão
Quadros de uma conexão são numerados em
seqüência
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Serviço orientado a conexões, com
reconhecimento (2)

Garantias fornecidas pelo serviço
–
Cada quadro enviado será, de fato, recebido

–
Cada quadro será recebido apenas uma vez


–
16
Não ocorre a duplicação de quadros
Graças à numeração em seqüência dos quadros
Quadros são recebidos na mesma ordem em que
foram enviados


Quadros não são perdidos
Também conseqüência da numeração dos quadros
Permite à camada de redes assumir que o
meio de transmissão subjacente é
inteiramente confiável
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Serviço orientado a conexões: Fases
na comunicação (no nível de enlace)

Estabelecimento da conexão
–
Inicialização de variáveis e alocação de buffers
em ambos os lados da conexão




Transmissão de dados
Liberação da conexão
–
17
Para ter controle sobre os quadros transmitidos,
recebidos, retransmitidos, etc.
Pode envolver um acordo sobre os parâmetros de
transmissão (taxa de dados, atrasos máximos, etc.)
Recursos alocados à conexão (buffers, variáveis,
etc.) são liberados
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Procedimentos envolvidos na
comunicação: Exemplo de um roteador
18
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Procedimentos envolvidos na
comunicação
1.
2.
3.
Quadro é recebido em um roteador
Hardware verifica checksum (detecção de erros) e
repassa o quadro para o software da camada de
enlace
Camada de enlace verifica se o quadro recebido é
realmente o quadro esperado
–
4.
5.
19
Ex.: verifica se o quadro está na ordem correta
Caso afirmativo, camada de enlace extrai o pacote
de dentro do quadro e o entrega ao software da
camada de rede para roteamento
Software de roteamento escolhe a linha de saída
apropriada e repassa o pacote para o software de
camada de enlace responsável por aquela linha
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Unidades de dados transmitidas nas
várias camadas
Mensagens
Pacotes
Quadros
20
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Delimitação de quadros

Camada física: dados são transmitidos como
seqüências de bits não estruturadas
–

Camada de enlace: impor uma estrutura aos
dados a serem transmitidos
–

Facilitando o tratamento de tais erros
Abordagem básica:
–
–
21
Transmissão sujeita a erros
Agrupar os bits em quadros distintos
Calcular um checksum dos dados, o qual é
verificado no destino para detectar possíveis erros
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Delimitação de quadros: Abordagens

Separação dos quadros sucessivos através
de lacunas de “silêncio”
–
Não-confiável


Métodos mais confiáveis:
–
–
–
–
22
Atrasos de transmissão podem fazer com que as
lacunas desapareçam ou que lacunas indesejáveis
sejam inseridas, danificando a separação dos quadros
Contagem de caracteres
Caracteres de início e fim de quadro
Flags de início e fim de quadro
Uso de códigos inválidos
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Delimitação de quadros: Contagem de
caracteres



Cabeçalho do quadro contém um campo
especificando o número de caracteres nele
contidos
Receptor conta os caracteres recebidos para
determinar o fim de um quadro (e o início do
próximo)
Problema fundamental:
–
Erros de transmissão podem mudar o valor do
campo que contém o número de caracteres

23
Receptor incapaz de se re-sincronizar
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Delimitação de quadros: Contagem de
caracteres (2)
24
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Delimitação de quadros: Caracteres de
início e fim

Início e fim de quadro demarcado com
caracteres ASCII especiais
–
–
DLE + STX: início
DLE + ETX: fim




25
DLE = Data Link Escape
STX = Start of TeXt
ETX = End of TeXt
Na ocorrência de erros, o receptor pode se
re-sincronizar procurando pelo próximo par
DLE-STX ou DLE-ETX
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Delimitação de quadros: Caracteres de
início e fim (2)

Problema na transmissão de dados binários
ou numéricos
–
–

Ocorrência acidental de um padrão de bits idêntico
ao par de caracteres delimitadores
Interpretação errônea do fim (ou início) de quadro
Solução: character stuffing
–
Camada de enlace no transmissor insere um
caracter DLE antes do caracter DLE acidental

–
26
Resultado: DLEs “falsos” no meio dos dados sempre
aparecem em pares (ao contrário dos DLEs verdadeiros)
Receptor (camada de enlace) remove o caracter
DLE introduzido (antes de repassar os dados à
camada de rede)
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Delimitação de quadros: Caracteres de
início e fim (3)
27
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Delimitação de quadros: Caracteres de
início e fim (4)

Desvantagem fundamental:
–
–
O mecanismo de construção dos quadros (e sua
transmissão) é dependente do código de
caracteres utilizado (ASCII)
Impede o uso de códigos de caracteres mais
modernos


28
Tais como UNICODE, que é fundamental para a
internacionalização dos dados transmitidos
ASCII é voltado apenas para as necessidades das
línguas ocidentais (mais especificamente, do Inglês)
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Delimitação de quadros: Bits de início
e fim de quadro



Permite que quadros contenham um número
arbitrário de bits
O código de caracteres utilizado é irrelevante
Padrão de bits delimitador (flag): 01111110
–

Demarca início e fim de quadro
Princípio básico: Bit stuffing
–
Sempre que o transmissor encontrar cinco bits
“1” consecutivos no meio dos dados, um bit “0” é
automaticamente inserido

29
Impede que a seqüência delimitadora ocorra nos dados
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Delimitação de quadros: Bits de início
e fim de quadro (2)

Bit stuffing (cont.)
–
No receptor, sempre que se detectar cinco bits “1”
consecutivos seguidos de um bit “0”, este último é
automaticamente deletado


Exemplo:
–
–

Dados originais: 01111110
Dados transmitidos: 011111010
Transparente para a camada de rede
–
30
Pois foi inserido artificialmente
Stuffing bits são removidos antes de repassar os
dados para a camada de rede
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Delimitação de quadros: Bits de início
e fim de quadro (3)
31
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Delimitação de quadros: Uso de
códigos inválidos da camada física

Apenas aplicável quando o esquema de
codificação de bits para transmissão (na
camada física) contém redundância
–
–

Isto é, alguns dos possíveis códigos são inválidos
como dados
Utilizados para detectar condições excepcionais
Exemplo: Em redes locais
–
–
–
Bit “1”: high-low (nível alto seguido por nível baixo)
Bit “0”: low-high
High-high e low-low são inválidos como dados

32
Podem então ser usados como delimitadores
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Delimitação de quadros: Combinção
de técnicas


Contagem de caracteres empregada em
conjunto com bits (ou caracteres)
delimitadores
Maior segurança na delimitação dos quadros
–
O fim de um quadro só é confirmado (e o quadro
tido como válido) se:


–
Além disso, o conteúdo do quadro (i.e., um
pacote) só será entregue à camada de rede se:

33
Atingiu-se o número de caracteres esperado, e
Encontrou-se o caracter / flag delimitador
não houver erro no checksum ou na ordem do quadro
(ver a seguir)
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Controle de erros


Erros não-recuperáveis – i.e., que não podem ser
corrigidos no receptor
A camada de enlace deve tratar os seguintes
problemas:
–
Quadros perdidos

–
–
–
Quadros recebidos com erros de checksum que não
possam ser corrigidos
Quadros recebidos fora de ordem
Perda de quadros de reconhecimento


34
Ex.: devido a ruídos na transmissão
E, em conseqüência, a duplicação de quadros
Especialmente em serviços orientados a conexão
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Controle de erros (2)


Quadros de reconhecimentos
Transmissor
(acknowledgement)
Receptor informa ao transmissor
o estado do quadro recebido:
–
ACK: positivo – o quadro chegou
sem problemas

–
transmissor prossegue normalmente
NACK: negativo – o quadro chegou,
mas com erro

35
Receptor
o quadro deve ser re-transmitido
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Controle de erros (3)

Problema: Quadros perdidos devido a erros
de transmissão
–
O quadro não é recebido de forma alguma



Transmissor poderia ficar bloqueado para
sempre à espera do reconhecimento
Solução: Uso de temporizadores
–
36
portanto, NACK não será enviado pelo receptor
Permite que o transmissor atribua um limite
máximo (timeout) ao tempo que esperará por um
reconhecimento de um quadro pelo receptor
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Controle de erros (4)

Uso de temporizadores (cont.)
–
Ao enviar um quadro o transmissor dispara um
temporizador

Alarme “soará” (timeout) após um tempo considerado
suficiente para
–
o quadro se propagar e ser recebido do outro lado
– o receptor processar o quadro
– o reconhecimento propagar de volta até o remetente
–
Caso o reconhecimento não chegue antes do
timeout ocorrer

37
Transmissor re-envia o quadro, assumindo que o
mesmo não foi recebido do outro lado do enlace
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Controle de erros (5)
Transmissor
Receptor
timeout
38
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Controle de erros (6)

Mas e se um reconhecimento se perder?
–
–
Ocorrerá um timeout
Transmissor se comportará como se o quadro
original houvesse sido perdido

–
re-transmitirá uma duplicata o quadro!
O mesmo quadro será ser processado duas (ou
mais) vezes pelo receptor


cópias do mesmo pacote poderão ser passadas para a
camada de rede como se fossem pacotes diferentes
podendo gerar resultados indesejáveis
–
39
ex.: operações com o saldo de uma conta corrente)
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Controle de erros (7)
Transmissor
Receptor

Solução:
–
–
Associar números de
seqüência aos quadros
Receptor saberia se um
quadro já foi recebido


timeout
Esta solução é também
válida para o problema da
ordenação dos quadros:
–
40
Prof. Fábio M. Costa - INF / UFG
descarta duplicatas
um quadro somente é
repassado à camada de
rede se sua ordem estiver
de acordo com seu número
de seqüência
Capítulo 3: Camada de Enlace
Controle de fluxo

Problema fundamental:
–
Quando a taxa de transmissão é superior à taxa
em que o receptor pode processar os dados
recebidos

–
Processo transmissor reside em um computador mais
rápido ou menos carregado que o computador onde
reside o receptor
Receptor pode ficar “inundado” com quadros


buffer overflow
quadros começam a ser perdidos
–
41
mesmo que não haja erros de transmissão
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Controle de fluxo (2)

Solução genérica:
–
–
Regras para garantir o compasso entre o
transmissor e o receptor
Exige alguma forma de feedback do receptor
para o transmissor


Exemplo:
–
42
Protocolo que permite ao receptor informar quando (e o
quanto de) dados ele está preparado para receber
Receptor informa ao transmissor que pode
transmitir n quadros, após os quais deve parar
até que o receptor o autorize a enviar mais
quadros
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Detecção e Correção de Erros

Meios de transmissão comumente utilizados são
sujeitos a erros
–

Duas possibilidades:
–
–

43
Ex.: sistema telefônico (loops locais) e meios de
transmissão sem fio
Correção de erros: técnicas que permitem detectar e
corrigir bits errôneos em um quadro recebido
Detecção de erros: apenas detecta-se o erro, indicando a
necessidade de retransmissão
Obs.: Controle de erros (visto anteriormente)
envolve os tratamentos necessários uma vez que
um erro foi detectado (mas não corrigido)
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Natureza de erros de transmissão

Erros tendem a acontecer em rajadas
–

Exemplo:
–
–
–
–
–
44
Ex.: um surto de ruído no meio pode causar a inversão de
vários bits consecutivos
dados transmitidos em blocos de 1000 bits
taxa de erros de 0.001 erro por bit (1 a cada 1000 bits)
erros independentes (isolados): comprometeriam a maior
parte dos quadros
Vantagem de erros em rajada (ex.: 100 bits seguidos de
cada vez): apenas um ou dois blocos em cada 100 seriam
afetados (em média)
Por outro lado: erros em rajada são mais difíceis de se
detectar e corrigir do que erros isolados
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Códigos de correção de erros

Transmissor inclui informação redundante o
suficiente para permitir ao receptor deduzir
quais foram os dados corretos transmitidos
–

45
Bits de redundância permitem determinar a
posição do(s) bit(s) invertido(s)
Bits errôneos são corrigidos antes que os
dados sejam repassados para a camada de
rede
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Detecção e correção de erros:
Distância de Hamming



m bits de dados – mensagem
r bits de redundância – bits de checagem
palavra-código (codeword): mensagem +
bits de checagem
–

comprimento: n = m + r
Distância de Hamming entre duas palavrascódigo:
–
–
número de posições de bits nas quais as duas
palavras diferem entre si
Ex.: 10001001 e 10110001: dist. Hamming = 3

46
são necessários 3 erros de bit para transformar uma
palavra na outra
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Detecção e correção de erros:
Distância de Hamming (2)


2m mensagens válidas
Nem todas as 2n palavras-código são válidas
–

conjunto de todas as palavras-código: código
Dado o algoritmo para computar os bits de
checagem, é possível:
–
–
enumerar todas as palavras código válidas
encontrar as duas palavras-código cuja distância
de Hamming é mínima (dentro do código)

47
Distância de Hamming do código em si
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Detecção e correção de erros:
Distância de Hamming (3)


As propriedades de detecção e correção de erros de
um código dependem da sua distância de Hamming
Para detectar d erros: código com distância d + 1
–

não há como d erros converterem uma palavra-código
válida em outra palavra-código também válida
Para corrigir d erros: código com distância 2d + 1
–
mesmo com d bits errôneos, a palavra-código original ainda
estará mais próxima da palavra recebida do que qualquer
outra

48
palavra correta pode ser deduzida unicamente
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Exemplo: Detecção de erros com
bit de paridade


Um bit adicional é adicionado ao bloco de
bits a ser transmitido de forma que a soma
total dos bits “1” seja par (ou ímpar)
Exemplo: dados originais = 10110101
–
–

Distância de Hamming do código = 2
–
–
49
paridade par: 101101011
paridade ímpar: 101101010
Apenas um erro de bit: gera uma palavra-código
ilegal (com a paridade incorreta)
Permite detectar erros de um único bit
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Correção de erros: Exemplo

Código com as seguintes palavras-código
válidas:
–

Distância de Hamming do código = 5
–

0000000000, 0000011111, 1111100000, 1111111111
Capaz de corrigir erros duplos (dois bits)
Ex.: palavra recebida: 0000000111
–
–
Receptor deduz que a palavra correta é 0000011111
Mas se o erro for de três bits, convertendo a palavra
0000000000 em 0000000111, o erro não será
corrigido corretamente!

50
Não há como ter certeza disto (pode-se apenas fazer
suposições, com base em observações, sobre os tipos de
erros característicos em um determinado sistema)
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Código de correção de erros: Aspectos
gerais de projeto (exemplo)


Correção de erros simples (de 1 único bit)
Tamanho da mensagem: m bits
–

Número de bits de checagem: r
–
–

Total de bits em uma palavra-código: n = m + r
2n palavras-código (i.e., padrões de bits possíveis)
Para cada palavra-código válida:
–
–
–
51
2m mensagens válidas
n palavras ilegais (a uma distância 1 da palavra válida)
Portanto: Cada palavra válida requer n+1 padrões de bits
dedicados a ela
Logo, o número mínimo de check bits necessários é dado
por: (n + 1)2m ≤ 2n ou: (m + r + 1) ≤ 2r
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Código de correção de erros: Código
de Hamming

Numera-se os bits seqüencialmente
–



Bits numerados como potências de 2 (ex.: 1,
2, 4, 8, 16, etc.) representam os r check bits
Demais bits (3, 5, 6, 7, 9, etc.) representam
os m bits de dados
Cada check bit determina a paridade de um
sub-conjunto dos bits da palavra-código
–
52
Começando com o bit 1 como o bit mais à
esquerda
O mesmo check bit pode estar envolvido na
paridade de vários sub-conjuntos de bits
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Código de correção de erros: Código
de Hamming (2)

Para determinar os check bits que fazem a
verificação de um determinado bit de dados
na posição k:
–

Re-escrever k como uma soma de potências de 2
Exemplos:
–
k = 11 = 1 + 2 + 8

–
k = 29 = 1 + 4 + 8 + 16


53
bit 11 é checado pelos bits 1, 2 e 8
bit 29 é checado pelos bits 1, 4, 8 e 16
Transmissor calcula cada check bit e os
insere na palavra-código a ser transmitida
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Código de correção de erros: Código
de Hamming (3)

Ao receber uma palavra-código, o receptor
–
–
–
Inicializa um acumulador (em zero)
Examina cada check bit k (k = 1, 2, 4, 8, ...) para
determinar se o mesmo tem a paridade correta
Se paridade do check bit k está incorreta:

–
Se, ao final, o valor do acumulador for zero

–
Adiciona k ao acumulador
Não houve erro na palavra recebida
Se o valor do acumulador for diferente de zero:

Acumulador contém o número do bit errôneo
–
54
Ex.: check bits 1, 2 e 8 estão com paridade incorreta: bit
11 foi invertido (é o único bit checado pelos bits 1, 2 e 8)
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Código de correção de erros:
Código de Hamming - exemplo



Blocos de dados transmistidos: 7 bits
4 check bits: 1, 2, 4, 8
Bits de dados: 3, 5, 6, 7, 9, 10 ,11
1
55
2
3
4
Bit
3
Checado por
1, 2
5
6
7
1, 4
2, 4
1, 2, 4
Prof. Fábio M. Costa - INF / UFG
5
6
7
8
9
10
11
Bit
9
Checado por
1, 8
10
11
2, 8
1, 2, 8
Capítulo 3: Camada de Enlace
Código de correção de erros: Código
de Hamming – exemplo
56
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Código de Hamming: Correção de
surtos de erros

Grupo de k palavras-código a serem
transmitidas
–




57
Arranjadas como uma matriz k x n
Transmitir os dados coluna por coluna
Uma rajada de erros de até k bits afetaria, no
máximo um bit em cada palavra-código
Código de Hamming em cada palavra-código
seria usado para corrigir cada erro individual
Resultado: múltiplos (≤ k) erros consecutivos
corrigidos com kr check bits
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Códigos de Detecção de Erros

Correção de erros é aplicável (prática) quando
–
O canal de transmissão é simplex

–
Os atrasos de transmissão são muito grandes


Ex.: conexões de satélite ou enlaces interplanetários
Na maioria das situações comuns, contudo,
detecção seguida de retransmissão é mais
eficiente
–
Em geral, detecção de erros e retransmissões geram
menos bits de overhead do que códigos de correção de
erros

58
Retransmissões não são possíveis
Assumindo que erros ocorrem esporadicamente
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Códigos de detecção de erros: Modelo
fundamental
59
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Detecção de erros: Bits de paridade

Confiabilidade 100% apenas nos casos de erros
isolados
–

Para erros em rajada (vários bits no mesmo bloco):
–

1 bit para cada bloco protegido por um bit de paridade
Probabilidade de acerto de apenas 50%
Melhoria:
–
–
Organizar os dados a serem transmitidos como uma matriz
(k linhas x n colunas)
Última linha: bits de paridade


–
–
60
Paridade coluna-por-coluna
Cada bit de paridade checa uma posição de bit em cada linha
Capaz de corrigir rajadas de erros de até n bits
Ver exemplo a seguir
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Detecção de erros: Bits de paridade (2)
Ordem de transmissão
(uma linha de cada vez)
• k = 7 linhas
• n = 8 colunas
• Capaz de
detectar
surtos de
erros de até
8 bits
61
Bits de
Paridade
1
0
1
0
1
0
1
0
0
1
1
0
1
0
1
0
Prof. Fábio M. Costa - INF / UFG
0
0
0
1
1
1
0
1
1
0
0
1
0
1
0
1
1
0
0
0
0
0
1
0
1
1
0
1
0
1
0
0
0
1
1
1
1
0
1
1
0
1
1
0
1
1
1
1
Capítulo 3: Camada de Enlace
Detecção de erros: Códigos
polinomiais


Checagem de Redundância Cíclica (CRC)
Um quadro (seqüência de bits) a ser
transmitido é visto como um polinômio M(x)
binário (i.e., com coeficientes 0 e 1 apenas)
–

Polinômio gerador: G(x)
–
–
62
Ex.: 110001  x5 + x4 + x0 ou: x5 + x4 + 1
Utilizado para a geração de um checksum (CRC) a
ser concatenado ao final de cada quadro original
Polinômio resultante, M(x) + checksum, deve ser
divisível por G(x)
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Detecção de erros: Códigos
polinomiais – Algoritmo de geração

Concatenar um número de bits “0” (equivalente ao
grau r do polinômio gerador) ao final do quadro a ser
transmitido
–



63
resultando no polinômio xrM(x)
Dividir (módulo 2) o polinômio resultante por G(x)
Subtrair (módulo 2) o resto da divisão acima da
seqüência de bits correspondente ao polinômio
xrM(x)
O resultado é o quadro com checksum a ser
transmitido
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Detecção de erros: Códigos
polinomiais – Exemplo



Quadro original: 1 1 0 1 0 1 1 0 1 1
Gerador: 1 0 0 1 1 (x4 + x + 1 => grau 4)
Quadro após adicionar 4 bits:
–

Resto da divisão: 1 1 1 0
–

64
11010110110000
(1 1 0 1 0 1 1 0 1 1 0 0 0 0 dividido por 1 0 0 1 1)
Quadro transmitido: 1 1 0 1 0 1 1 0 1 1 1 1 1 0
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Detecção de erros: Códigos
polinomiais – Eficiência

Tipos de erros detectados:
–
–
–
–
–

Implementação simples e eficiente por hardware
–
65
Erros de um único bit (100%)
Erros duplos (desde que G(x) tenha pelo menos três bits
“1”)
Qualquer número ímpar de erros (desde que G(x) contenha
um fator x + 1)
Qualquer surto de erros cujo comprimento (entre o primeiro
e o último bits invertidos) seja menor que o comprimento do
polinômio gerador
A maior parte dos erros de rajada (probabilidade de não
detectar: 1/2r)
Registradores de deslocamento e portas XOR
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Detecção de erros: Códigos
polinomiais padronizados

CRC-12: X12 + x11 + x3 + x2 + x1 + 1
–
–

CRC-16: X16 + X15 + X2 + 1
–
–

Idem (Europa)
CRC-16 e CRC-CCITT: eficiência
–
–
–
–
–
66
Transmissão de seqüências de caracteres de 8 bits
Gera CRCs de 16 bits
CRC-CCITT: X16 + X12 + X5 + 1
–

Transmissão de seqüências de caracteres de 6 bits
Gera CRCs de 12 bits
Todos os erros de 1 ou 2 bits
Todos os erros de um número ímpar de bits
Todos os surtos de erros de até 16 bits
99,997% dos surtos de erros de 17 bits
99,998% dos surtos de erros de 18 bits ou mais
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolos de Enlace Elementares

Três protocolos em ordem crescente de
complexidade
–
Um protocolo simplex irestrito

–
Um protocolo simplex do tipo stop-and-wait

–
controle de fluxo básico
Um protocolo simplex com controle de erros

67
uma série de suposições (não-realistas) que simplificam
o projeto do protocolo
mais realista, reconhece que o canal de comunicação é
sujeito a erros
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolos de Enlace Elementares: O
modelo de comunicação

Camadas física, enlace e redes
–
implementadas através de processos
independentes, por exemplo:


–
camadas física e enlace: hardware da placa de rede
camada de rede: processo executando na CPU
comunicam-se entre si através de mensagens
(comunicação inter-processo)
CPU
Camada
Física
68
Camada
de Enlace
Camada
de Rede
NIC – Network Interface Card
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolos de Enlace Elementares: O
modelo de comunicação (2)

Transmissão simplex
–
–

Camada de rede (em A) sempre tem dados a
transmitir
–
–

69
do computador A para o computador B apenas
(em protocolos mais sofisticados: duplex)
suprimento de dados infinito
esta suposição será removida à medida em que
protocolos mais sofisticados são apresentados
Pacotes da camada de rede são tratados
puramente como dados pela camada de
enlace (inclusive o cabeçalho do pacote)
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolos de Enlace Elementares: O
modelo de comunicação (3)
Camada de Rede
H
Data
from_network_layer()
No transmissor:
•Encapsula
Camada de Enlace
H
H
Data T
to_physical_layer()
Camada Física
70
pacotes em
quadros
•Adiciona
cabeçalho e trailer
Prof. Fábio M. Costa - INF / UFG
•Calcula checksum
antes de transmitir
o quadro
Capítulo 3: Camada de Enlace
Protocolos de Enlace Elementares: O
modelo de comunicação (4)
Camada de Rede
No Receptor:
to_network_layer()
Data
H
•Checa cabeçalho
Camada de Enlace
para detectar
qualquer problema
•Extrai o pacote e o
repassa à camada
de rede
•Verifica checksum
•Sinaliza chegada
71
from_physical_layer()
H
H
Data T
Camada Física
do quadro (evento)
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolos de Enlace Elementares: O
modelo de comunicação (5)

Camada de enlace no receptor:
–
–
Loop infinito aguardando por eventos
Procedure wait_for_event( &event )

–
Vários tipos de eventos


–
dependente de protocolo
Exemplos: chegada de quadro, erro de checksum, timeout,
etc.
Ao receber um evento (ex.: chegada de um quadro),
a camada de enlace deve processá-lo

72
retorna quando algo acontece (ex.: chegada de um quadro)
Ex.: chama from_physical_layer() para obter o
quadro
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolos de Enlace Elementares:
Definições básicas
73
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolos de Enlace Elementares:
Definições básicas (2)
74
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolos de Enlace Elementares:
Estruturas de dados




75
#define MAX_PKT 1024
– tamanho máximo de um quadro
typedef enum {false, true} boolean;
typedef unsigned int seq_nr;
– número de seqüência atribuído aos quadros
– 0 a MAX_SEQ (dependente de protocolo)
– contagem circular (0, 1, 2,... MAX_SEQ, 0, 1, ...)
typedef struct{unsigned char
data[MAX_PKT];}packet;
– unidade de dados trocada entre a camada de
rede e a camada de enlace
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolos de Enlace Elementares:
Estruturas de dados (2)


76
typedef enum{data, ack, nak}frame_kind;
– tipo do quadro (dados ou controle)
typedef struct {
frame_kind kind;
seq_nr seq;
seq_nr ack;
packet info;
} frame;
– quadro propriamente dito
– seq: número de seqüência do quadro
– ack: acknowledgement
– info: pacote encapsulado (vazio se quadro de
controle)
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolos de Enlace Elementares:
Rotinas comuns




77
wait_for_event(event_type &event);
from_network_layer(packet *p);
– chamada pela camada de enlace para aceitar
pacotes (da camada de rede) a serem
transmitidos
to_network_layer(packet *p);
– chamada pela camada de enlace para passar
pacotes recebidos para a camada de rede
to_physical_layer(frame *s); e
from_physical_layer(frame *s);
– interface com a camada física
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolos de Enlace Elementares:
Rotinas comuns (2)

start_timer(seq_nr k);

dispara um temporizador para detectar a
ocorrência de timeouts (ex.: p/ ack de um quadro)
– um temporizador para cada quadro pendente
stop_timer(seq_nr k);
–
–

start_ack_timer(void); e
stop_ack_timer(void);
–
78
interrompe a contagem do temporizador quando
o evento esperado ocorreu (ex.: quadro chegou
antes do timeout)
uso semelhante em situações especiais
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolos de Enlace Elementares:
Rotinas comuns (3)

enable_network_layer(void);
–
–
utilizada em protocolos mais sofisticados (com controle de
fluxo e que não assumem a constância do fluxo de dados)
quando habilitada, a camada de rede pode interromper a
camada de enlace para avisar que há pacotes a serem
transmitidos

–

a camada de enlace então invoca from_network_layer
para obter o pacote
disable_network_layer(void);
–
–
79
evento network_layer_ready
desabilita a camada de rede (não permitindo novas
interrupções
para evitar que a camada de rede tente transmitir pacotes
além da capacidade da camada de enlace
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolos de Enlace Elementares:
Rotinas comuns (4)
#define inc(k) if (k < MAX_SEQ) k = k + 1; else k = 0

–
–

Todas as definições básicas são contidas no
arquivo protocol.h
–
80
macro utilizada para incrementar números de
seqüência circularmente
MAX_SEQ é definido por cada protocolo
incluído (#include) pela implementação de cada
protocolo
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Um protocolo simplex irrestrito

Suposições básicas:
–
–
dados são transmitidos apenas de A para B
camada de rede no transmissor sempre tem
dados a transmitir

–
camada de rede no receptor sempre está pronta
para receber dados

–
81
ao ser invocada pela camada de enlace (através de
from_network_layer)
ao ser invocada pela camada de enlace (através de
to_network_layer)
tempos de processamento (nas camadas) é
ignorado
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Um protocolo simplex irrestrito (2)

Suposições básicas (cont.):
–
–
Buffers com capacidade infinita nas camadas
Canal de comunicação 100% confiável


Suposições não-realistas, mas que
simplificam a implementação deste primeiro
protocolo estudado
–
–
82
nunca corrompe ou perde quadros
–
números de seqüência ou reconhecimentos
(acks) não são necessários
único evento possível: chegada de quadro (sem
erros)
apenas um tipo de pacote: de dados
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Um protocolo simplex irrestrito:
Transmissor
typedef enum{frame_arrival} event_type;
#include “protocol.h”
void sender1(void){
frame s;
packet buffer;
83
while(true){
from_network_layer(&buffer);
s.info = buffer;
to_physical_layer(&s);
}}
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Um protocolo simplex irrestrito:
Receptor
void receiver1(void){
frame r;
event_type event;
while(true){
wait_for_event(&event);
from_physical_layer(&r);
to_network_layer(&r.info);
}
}
84
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Um protocolo simplex Stop-and-Wait

Removendo a seguinte restrição:
–


Ainda assumindo um canal livre de erros e
tráfego de dados em uma só direção
Problema a ser resolvido:
–

85
receptor com capacidade infinita de
processamento/ armazenamento de quadros
prevenir que o transmissor inunde o receptor com
uma taxa dados maior do que ele é capaz de
consumir
Solução: feedback do receptor para o
transmissor indicando quando se pode
transmitir mais quadros
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolo simplex Stop-and-Wait:
Transmissor
typedef enum{frame_arrival} event_type;
#include “protocol.h”
void sender2(void){
frame s;
packet buffer;
event_type event;
while(true){
from_network_layer(&buffer);
s.info = buffer;
to_physical_layer(&s);
wait_for_event(&event);
}}
86
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolo simplex Stop-and-Wait:
Receptor
void receiver2(void){
frame r, s;
event_type event;
while(true){
wait_for_event(&event);
from_physical_layer(&r);
to_network_layer(&r.info);
to_physical_layer(&s);
}
}
87
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Um protocolo simplex para um canal
sujeito a erros

Quadros podem ser danificados ou perdidos
–
–

Quadros danificados: detectados pelo hardware ao
calcular o checksum
Quadros perdidos: excede-se o prazo para receber o
Acknowledgement
Solução simplista:
–
–
Uso de timeout no protocolo anterior
Não funciona:
timeout
timeout
Sender
Dados
Receiver
88
Ack
p/ camada
de rede
Duplicata!
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Um protocolo simplex para um canal
sujeito a erros (2)

Solução mais elaborada:
–
Uso de números de seqüência no cabeçalho de cada
quadro de dados enviado




Detalhe: Tamanho dos números de seqüência
–
–
89
Stop-and-wait com timeout e números de seqüencia
Receptor pode distingüir quadros novos de retransmissões
Acknowledgements: quadros vazios (ver posteriormente)
–
Influencia na quantidade de overhead carregada em
cada quadro de dados
É necessário ao receptor distinguir apenas entre um
quadro e o próximo (stop-and-wait significa que há
apenas um quadro em trânsito em um dado instante)
Portanto: 1 bit apenas neste caso: 0, 1, 0, 1, ...
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Um protocolo simplex para um canal
sujeito a erros (3)
timeout
timeout
Sender
Dados
0
1
1
1
Receiver

Protocolos deste tipo são conhecidos como:
–
–
90
Ack
p/ camada
de rede
ARQ – Automatic Repeat Request, ou
PAR – Positive Aknowledgement with
Retransmission
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Um protocolo simplex para um canal
sujeito a erros (4)

Outro detalhe: duração do intervalo de timeout
deve ser corretamente ajustada
–
Suficiente para:



–
Propagação do quadro até o receptor
Processamento do quadro e geração do Ack no receptor
Propagação do Ack (quadro de controle) até o transmissor
Problema se este intervalo for subestimado:
timeout
Sender
1
0
91
Receiver
Prof. Fábio M. Costa - INF / UFG
0
Falha do protocolo:
transmissor pensa
que este quadro foi
recebido ok.
Dados
Ack
p/ camada
de rede
Capítulo 3: Camada de Enlace
Protocolo ARQ simplex: Definições
/* Protocol 3 */
#define MAX_SEQ 1
typedef enum {frame_arrival,
cksum_error,
timeout} event_type;
#include “protocol.h”
92
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
void sender3(void){
seq_nr next_frame_to_send;
frame s;
packet buffer;
event_type event;
next_frame_to_send = 0;
from_network_layer(&buffer);
while(true){
s.info = buffer;
s.seq = next_frame_to_send;
to_physical_layer(&s);
start_timer(s.seq);
wait_for_event(&event);
if (event == frame_arrival) { /* chegou ACK */
from_network_layer(&buffer);
inc(next_frame_to_send);
}
}
}
93
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
void receiver3(void){
seq_nr frame_expected;
frame r,s;
event_type event;
frame_expected = 0;
while(true){
wait_for_event(&event);
if(event == frame_arrival){
from_physical_layer(&r);
if (r.seq == frame_expected){
to_network_layer(&r.info);
inc(frame_expected);
}
to_physical_layer(&s); /* envia ACK */
}
}
}
94
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
void sender3(void){
seq_nr next_frame_to_send;
frame s;
packet buffer;
event_type event;
95
O mesmo protocolo,
agora com números
de seqüência no
Acknowledgement
(transmissor)
next_frame_to_send = 0;
from_network_layer(&buffer);
while(true){
Ack com número
s.info = buffer;
de seqüência!
s.seq = next_frame_to_send;
to_physical_layer(&s);
start_timer(s.seq);
wait_for_event(&event);
if (event == frame_arrival) {
from_physical_layer(&s);
if (s.ack == next_frame_to_send){
from_network_layer(&buffer);
inc(next_frame_to_send);
}
}
}
}
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
void receiver3(void){
seq_nr frame_expected;
frame r,s;
event_type event;
}
96
O mesmo protocolo,
agora com números
de seqüência no
Acknowledgement
(receptor)
frame_expected = 0;
while(true){
wait_for_event(&event);
if(event == frame_arrival){
from_physical_layer(&r);
if (r.seq == frame_expected){
to_network_layer(&r.info);
inc(frame_expected);
}
s.ack = 1 – frame_expected;
to_physical_layer(&s);
}
}
Ack com número
de seqüência!
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolos de “Janela Deslizante”
(Sliding Window)

Conceitos básicos
Protocolo de janela deslizante de 1 bit
Protocolo “Go Back n”
Protocolo com repetição seletiva

Removendo mais uma das suposições:



–
Protocolos full-duplex


97
Um circuito físico full-duplex ou dois circuitos simplex
Mantém-se a suposição de que a camada de
rede sempre tem pacotes a transmitir
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Piggybacking

Problema: Reconhecimentos (Acks)
consomem recursos da rede
–

Solução: Enviar reconhecimentos de
“carona” em quadros de dados transmitidos
no sentido oposto ao do quadro reconhecido
–
–
98
um quadro transmitido para cada Ack
Aguarda-se até que haja um quadro de dados a
ser transmitido para então enviar o Ack
Caso demore muito, enviar o Ack em quadro
separado – para evitar timeout do transmissor
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
O conceito de “janela deslizante”


Cada quadro (e cada reconhecimento)
contém um número de seqüência
Janela de transmissão
–
Números de seqüência dos quadros que podem
ser transmitidos

–

Quadros transmitidos mas com Ack pendente
Janela de recepção
–
Números de seqüência dos quadros que o
receptor pode aceitar

99
Ex.: 0 1 2 3 4 5 6 7 9 10 11
Ex.: 0 1 2 3 4 5 6 7 8 9 10 11
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
O conceito de “janela deslizante” (2)


As duas janelas são atualizadas (deslizadas) a cada
quadro transmitido / recebido
Janela de transmissão
–
–
quadro transmitido: incrementa limite superior
Ack recebido: incrementa limite inferior


quadros são mantidos em buffer até receber Ack
Janela de recepção
–
quadro recebido com número de seq. dentro da janela:

quadro é aceito, Ack é enviado, janela é deslizada
–
–
quadro recebido com número de seq. fora da janela:

100
quadro só é passado para a camada de rede quando seu
número for igual ao primeiro número de seq. na janela
quadro é simplesmente descartado
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
O conceito de “janela deslizante”:
Janela de tamanho 1
101
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolo 4: Janela Deslizante de 1 bit
Cenário ideal
Notação:
(seq, ack, packet number)
102
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolo 4: Janela Deslizante de 1 bit
Cenário anômalo
•A e B iniciam o
envio de quadros
simultaneamente
•Protocolo não
comete erros
•Entretanto, metade
dos quadros
transmitidos são
duplicatas
103
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolo 4: Janela deslizante de 1 bit
#define MAX_SEQ 1 /* must be 1 for protocol 4 */
typedef enum {frame_arrival, cksum_err, timeout} event_type;
#include "protocol.h“
void protocol4 (void)
{
seq_nr next_frame_to_send;
seq_nr frame_expected;
frame r, s;
packet buffer;
event_type event;
next_frame_to_send = 0;
frame_expected = 0;
from_network_layer(&buffer);
s.info = buffer;
s.seq = next
frame_to_send;
s.ack = 1 – frame_expected;
to_physical_layer(&s);
start_timer(s.seq);
104
Prof. Fábio M. Costa - INF / UFG
/* 0 or 1 only */
/* 0 or 1 only */
/* scratch variables */
/* current packet being sent */
/* next frame on the outbound stream */
/* number of frame arriving frame expected */
/* fetch a packet from the network layer */
/* prepare to send the initial frame */
/* insert sequence number into frame */
/* piggybacked ack */
/* transmit the frame */
/* start the timer running */
Capítulo 3: Camada de Enlace
Protocolo 4: Janela deslizante de 1 bit
(2)
while (true) {
wait_for_event(&event);
/* frame_arrival, cksum_err, or timeout */
if (event == frame_arrival) {
/* a frame has arrived undamaged. */
from_physical_layer(&r);
/* go get it */
if (r.seq == frame_expected) {
/* Handle inbound frame stream. */
to_network_layer(&r.info);
/* pass packet to network layer */
inc(frame_expected);
/* invert sequence number expected next */
}
if (r.ack == next_frame_to_send) {
/* handle outbound frame stream. */
from_network_layer(&buffer);
/* fetch new pkt from network layer */
inc(next_frame_to_send);
/* invert sender’s sequence number */
}
}
s.info = buffer;
/* construct outbound frame */
s.seq = next_frame_to_send;
/* insert sequence number into it */
s.ack = 1 – frame_expected;
/* seq number of last received frame */
to_physical_layer(&s);
/* transmit a frame */
start_timer(s.seq);
/* start the timer running */
}
} /* End protocol4 */
105
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Eficiência de utilização


Stop-and-wait apresenta sérios problemas de
eficiência de utilização da capacidade do enlace
Exemplo: link de satélite usando o protocolo 4
–
–
–
–
–

Stop-and-wait é inapropriado quando temos:
–
–
–
106
Taxa de dados: 50Kbps; RTT = 500ms
Tempo de transmissão: 20ms
Recepção do quadro (receptor): 270ms
Recepção do reconhecimento (transmissor): 520ms
Transmissor ficou bloqueado durante 500/520 = 96% do
seu tempo -> 4% de utilização da capacidade disponível
RTT muito alto
Alta largura de banda
Quadros de tamanho pequeno
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Solução: Múltiplos quadros enviados
antes de bloquear o transmissor

Permite-se ao transmissor enviar até w
quadros antes que o primeiro
reconhecimento seja recebido
–
–

No exemplo anterior:
–
–
107
w calculado em função do RTT
Preenchendo o máximo da capacidade do enlace
(lembrança: produto delayXbandwidth)
w = 26 (RTT=520 dividido pelo tempo de
transmissão = 20)
Após enviar o 26o. quadro, Acks chegarão a cada
20ms, dando permissão para transmitir mais um
quadro
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolo de janela deslizante de 3 bits
108
©Stallings
2000
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolo usando “Go Back n”


O que fazer quando um dos quadros
transmitidos é perdido?
Solução 1: Go Back n
–
Retransmitir todos os quadros posteriores ao
quadro perdido, inclusive

–
Receptor com janela de tamanho 1

–
109
Após timeout do quadro perdido
Isto é, sem espaço de buffer para guardar quadros
Lembre-se de que o receptor não pode passar
quadros fora de ordem para a camada de rede
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolo usando “Go Back n”:
Exemplo
110
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolo usando “Go Back n”:
Detalhes de projeto

Buffers de transmissão: quadros com Ack pendente
devem ser armazenados temporariamente no
transmissor (um buffer para cada quadro)
–
–

A camada de rede não possui um suprimento
contínuo de pacotes
–
–
–
111
Buffers são liberados à medida em que Acks são recebidos
Um Ack pode liberar um ou mais buffers
Ela interrompe a camada de enlace quando há pacotes
Camada de rede pode ser desabilitada quando a janela de
transmissão está cheia
A cada Ack recebido, um ou mais buffers podem ser
liberados e novos pacotes podem ser aceitos da camada
de rede
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolo usando “Go Back n”:
Detalhes de projeto (2)

Números de seqüência dos quadros
–
–
–
De 0 a MAX_SEQ
Implicam que, no máximo, MAX_SEQ quadros
podem estar com Ack pendente em um dado
instante
MAX_SEQ+1 números de seqüência para
impedir que Acks sejam mal interpretados:




–
112
Transmissor envia quadros 0 a 7
Transmissor recebe Ack do quadro 7
Transmissor envia os próximos 8 quadros (0 a 7)
Outro Ack para o quadro 7 é recebido
O que aconteceria se o segundo grupo de 8
quadros fosse perdido?
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolo usando “Go Back n”:
Detalhes de projeto (3)

Temporizadores independentes devem ser
associados a cada quadro transmitido
–
–
Cada quadro tem um período de timeout próprio
Temporizadores lógicos são usados

113
Com um único relógio físico
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolo 5 – Go Back n
#define MAX_SEQ 7 /* should be 2ˆn - 1 */
typedef enum {frame_arrival, cksum_err, timeout, network_layer_ready}
event_type;
#include "protocol.h"
static boolean between(seq_nr a, seq_nr b, seq_nr c)
{
/* Return true if (a <=b < c circularly; false otherwise. */
if (((a <= b) && (b < c)) || ((c < a) && (a <= b)) || ((b < c) && (c < a)))
return(true);
else
return(false);
}
114
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
static void send_data(seq_nr frame_nr, seq_nr frame_expected,
packet buffer[])
{
/* Construct and send a data frame. */
frame s;
/* scratch variable */
s.info = buffer[frame_nr];
/* insert packet into frame */
s.seq = frame_nr;
/* insert sequence number into frame */
/* piggyback ack */
s.ack = (frame_expected + MAX_SEQ) % (MAX_SEQ + 1);
to_physical_layer(&s);
start_timer(frame_nr);
/* transmit the frame */
/* start the timer running */
}
115
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
void protocol5(void)
{
seq_nr next_frame_to_send;
seq_nr ack_expected;
/* oldest frame as yet unacknowledged */
seq_nr frame_expected; /* next frame expected (inbound stream) */
frame r;
/* scratch variable */
packet buffer[MAX_SEQ + 1];
/* buffers for the outbound stream */
seq_nr nbuffered;
/* # output buffers currently in use */
seq_nr i;
/* used to index into the buffer array */
event_type event;
enable_network_layer();
ack_expected = 0;
next_frame_to_send = 0;
frame_expected = 0;
nbuffered = 0;
116
Prof. Fábio M. Costa - INF / UFG
/* allow network_layer_ready events */
/* next ack expected inbound */
/* next frame going out */
/* number of frame expected inbound */
/* initially no packets are buffered */
Capítulo 3: Camada de Enlace
while (true) {
wait_for_event(&event); /* four possibilities: see event_type above */
switch(event) {
case network_layer_ready: /* network layer has a packet to send */
/* Accept, save, and transmit a new frame. */
/* fetch new packet */
from_network_layer(&buffer[next_frame_to_send]);
/* expand the sender’s window */
nbuffered = nbuffered + 1;
/* transmit frame */
send_data(next_frame_to_send, frame_expected, buffer);
/* advance sender’s upper window edge */
inc(next_frame_to_send);
break;
117
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
case frame_arrival: /* a data or control frame has arrived */
from_physical_layer(&r);
/* get frame from physical layer */
if (r.seq == frame_expected) {
/* Frames are accepted only in order. */
to_network_layer(&r.info); /* pass packet to network layer */
inc(frame_expected);
/* advance lower edge of
receiver’s window */
}
/* Ack n implies n - 1, n - 2, etc. Check for this. */
while (between(ack_expected, r.ack, next_frame_to_send)) {
/* Handle piggybacked ack. */
nbuffered = nbuffered - 1;
/* one frame fewer buffered */
stop_timer(ack_expected); /* frame arrived ok; stop timer */
inc(ack_expected);
/* contract sender’s window */
}
break;
118
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
case cksum_err: break; /* just ignore bad frames */
case timeout:
/* trouble; retransmit all outstanding frames */
next_frame_to_send = ack_expected; /* start retransm. here */
for (i = 1; i <= nbuffered; i++) {
/* resend 1 frame */
send_data(next_frame_to_send, frame_expected, buffer);
inc(next_frame_to_send); /* prepare to send the next one */
}
} /* end switch statement */
if (nbuffered < MAX_SEQ)
enable_network_layer();
else
disable_network_layer();
} /* end while */
} /* end protocol5() */
119
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolo de janela deslizante usando
Repetição Seletiva

Alternativa para o protocolo 5 quando
–
–

Receptor aceita quadros recebidos fora de
ordem, armazenando-os temporariamente
–
–

Até que possa entregá-los (em ordem) à camada
de rede
Não descarta os quadros subseqüentes quando
um quadro anterior for perdido ou danificado
Isto é: receptor com janela maior que 1
–
120
erros são freqüentes
receptor possui espaço de buffer suficiente
Um buffer para cada quadro que pode aceitar
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolo de janela deslizante usando
Repetição Seletiva
121
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolo com repetição seletiva:
Detalhes de projeto

A faixa de números de seqüência deve ser
grande o suficiente
–
–
O dobro do tamanho da janela
Evitar que duas janelas sucessivas se
sobreponham


Número de buffers necessários: equivale ao
tamanho da janela
–
–
–
122
O que poderia causar erros no protocolo
Um buffer para cada número de seqüência
Bit para marcar se o buffer está cheio ou vazio
Um temporizador para cada buffer
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolo com repetição seletiva:
Detalhes de projeto (2)

Quadros de reconhecimento Vs.
Piggybacking
–
–
–
123
Caso não haja um quadro de dados a ser
transmitido, o Ack pode ser enviado em um
quadro de controle independente
Receptor só espera por um pacote da camada de
rede por um certo tempo (ack_timeout)
Ack_timeout deve ser menor que o timeout para
quadros de dados
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolo com repetição seletiva:
Detalhes de projeto (3)

Reconhecimentos negativos (NAK)
–
–
Requisição para retransmissão de um quadro
Quando o receptor suspeita de um erro


–
124
Quadro perdido
Quadro recebido com erro de CRC
Melhoram o desempenho global quando o tempo
necessário para um quadro ser reconhecido não
pode ser determinado com precisão
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Protocolo com repetição seletiva:
Detalhes de projeto (4)

Determinando qual quadro causou um
timeout
–
–
Evento de timeout não diz explicitamente a que
quadro ele se refere
Quadros são transmitidos em seqüência, um
após o outro

–
–
125
Ao se transmitir cada quadro, um temporizador é
disparado
Quadros mais “antigos” expiram (timeout) mais
cedo
Logo, um evento de timeout refere-se ao quadro
mais “antigo”
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
“Leitura” Complementar


Protocolo 6 (Figura 3-18, Tanenbaum)
Applet animado ilustrando o protocolo de janelas
deslizantes:
–
126
http://www.kom.e-technik.tudarmstadt.de/projects/iteach/itbeankit/Applets/Sliding_
Window/sliding_window.html
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
Camada de Enlace na Internet

Enlaces ponto-a-ponto de longa distância
–

Enlaces entre usuários e provedores
–
127
Isto é, os protocolos de enlace utilizados na sub-rede de
comunicações
Linha dedicada, linha discada
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
SLIP – Serial Line IP (RFC 1055)

Quadro: pacote IP + flag de fim de quadro
–
–
–

Compressão de cabeçalho TCP e IP
–
128
Byte marcador de fim de quadro (flag): 0xC0
Uso de caracteres de enchimento (0xDB, 0xDC)
caso o flag apareça no meio do pacote a ser
tranmitido
Se 0xDB aparecer no meio do pacote, insere-se
outro 0xDB
RFC 1144
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
SLIP: Limitações





129
Não faz detecção ou correção de erros
Suporta apenas o protocolo IP
Não permite a atribuição dinâmica de
endereços IP
Não provê autenticação
Múltiplas versões existem (não é um padrão
aprovado pelo IETF)
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
PPP – Point-to-Point Protocol
(RFC 1661)

Vantagens sobre o SLIP:
–
–
–
–

Deteção de erros
Encapsulamento de múltiplos protocolos de
camada de rede
Negociação de endereços IP durante o
estabelecimento da conexão
Autenticação
Aplicações:
–
–
Conexões de linha discada (usuário-provedor)
Conexões de linha dedicada (roteador-roteador)

130
Ex.: sobre uma linha física SONET/SDH
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
PPP: Serviços providos


Formatação e delimitação de quadros
Protocolo de controle de enlace
–
–
–
–
–

LCP (Link Control Protocol)
Ativação do circuito físico
Teste do circuito
Negociação de opções
Desativação do circuito
NCP (Network Control Protocol)
–
–
Negociação de opções da camada de rede
Independente do protocolo de rede utilizado

131
Um NCP para cada protocolo de rede diferente
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
PPP: Exemplo de uso

132
Conectando um PC à Internet através de um
provedor de acesso
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
PPP: Exemplo de uso
1.
Estabelecimento da conexão física
–
–
2.
PC envia uma seqüência de pacotes LCP
–
–
3.
Encapsulados em um ou mais quadros PPP
Negociação dos parâmetros do protocolo PPP
PC e roteador trocam uma série pacotes
NCP
–
–
133
Entre o PC e o roteador do provedor de acesso
Através de um modem em cada lado
Também encapsulados em quadros PPP
Associação de um endereço IP ao PC
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
PPP: Exemplo de uso (2)
4.
PC funciona como um host na Internet
–
–
5.
Ao final da sessão:
–
–
6.
134
Pode enviar e receber pacotes IP
Encapsulados em quadros PPP
Protocolo NCP é usado para desfazer a
conexão (no nível de rede), liberando o
endereço IP
Protocolo LCP é usado para fechar a conexão
de enlace
PC instrui o modem para liberar o circuito
físico
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
PPP: Formato dos quadros


Protocolo orientado a caracteres
Delimitação de quadros:
–
–

Campo de endereço: 11111111 (todas as estações)
–
135
Caracter (byte) especial 01111110 usado para delimitar o início
e fim de cada quadro
Character stuffing: caso o caracter delimitador apareça no
meio do quadro
Endereço padrão (evita ter que associar endereços de enlace)
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
PPP: Formato dos quadros (2)

Campo de controle
–
–
–
Valor default: 00000011 – quadro não numerado
Por default, PPP não provê transmissão confiável, com
números de seqüência e reconhecimentos
RFC 1663: Especifica o uso de números de seqüência


136
Para ambientes susceptíveis a ruídos
Campos de endereço e de controle, se default, podem
ser omitidos – opção negociada via protocolo LCP
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
PPP: Formato dos quadros (3)

Campo de Protocolo
–
–
–
Especifica o tipo do pacote encapsulado no campo Payload
do quadro PPP
Códigos padrão definidos para os protocolos LCP, NCP, IP,
IPX, AppleTalk, entre outros
Primeiro bit:


–
137
0 – protocolo da camada de rede
1 – protocolo de negociação (LCP ou um dos vários NCPs)
Tamanho do campo: 1 ou 2 (default) bytes, negociável c/ LCP
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
PPP: Formato dos quadros (4)

Campo de Payload
–
–
Tamanho variável
Tamanho máximo: negociado através do protocolo LCP


Campo de Checksum
–
138
Default: 1500 bytes
2 ou 4 bytes de CRC, negociável usando LCP
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
PPP: Diagrama de estados
139
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace
PPP: Protocolo utilizado na fase de
negociação (LCP) – tipos de pacotes
140
Prof. Fábio M. Costa - INF / UFG
Capítulo 3: Camada de Enlace