Comunicação de Dados e
Teleprocessamento
Nível de Enlace
Fontes: Stallings, W. Data and Computer Commmunications Transparências
Stallings
Redes de Computadores - das LANs, MANs e WANs às Redes ATM. Luiz
Fernando G. Soares, Guido Lemos, Sérgio Colcher. Editora Campus.
Protocolos de comunicação
O que os protocolos fazem ?











controle de erros: canais mais confiáveis - retransmissão
reseqüenciamento: reordenar mensagens fora de ordem
controle de fluxo: evita “inundar” receptor mais lento
controle de congestionamento: evita “inundar” rede mais lenta
fragmentação: dividir mensagens em pedaços menores para adaptar a
camada de protocolo inferior
multiplexação: combinar várias sessões de comunicação
em um “canal”
compressão de dados
translação de formatos entre fonte e destino
resolução de endereços
roteamento de pacotes
...
Modelo OSI
Organização em camadas
Comparação das Arquiteturas OSI e Internet
Nível de Enlace
Principais Características
Delimitação de Quadros
Controle de Fluxo
Controle de Erros
Serviços oferecidos
Controle de Acesso
Nível de Enlace
 Delimitação de Quadro
 Contagem de caracteres
cabeçalho contém tamanho dos dados
 Caracteres delimitadores
caracter especial para início / fim de quadro
Transparência ? - caracter especial “dentro dos dados” ?
Usa outro caracter especial precedendo o delimitador para indicar que
é caracter de dado
• >>> técnica de “stuffing”
 Seqüência de bits delimitadores
ex.: 01111110 (HDLC)
mesmo problema de transparência
inserção de 0’s (“bit-stuffing”)
• no envio: a cada 5 bits 1: insere 0
• na recepção: contrário
 Violação de código
uso de sinal no nível físico diferente de sinais usados para codificar bit’s
Nível de Enlace
Serviços oferecidos
sem conexão, sem reconhecimento
redes com baixa taxa de erros no nível físico
demora na transmissão pior do que perda (ex.: voz, vídeo)
sem conexão, com reconhecimento
pouco volume - de maneira confiável
tempo para abrir/fechar conexão não vale a pena
problema: nível de rede pode receber várias cópias
(descarte)
com conexão, e reconhecimento:
volumes maiores de maneira confiável, cópia única
Nível de Enlace
Controle de Acesso
duas máquinas ligadas ao meio de transmissão: caso
simples
várias máquinas ligadas ao meio de transmissão:
disciplina ?
Centralizado: “polling”
Distribuído: estações logicamente iguais
todas controlam acesso ao meio físico
Diferentes meios: diferentes formas de controle de acesso
Uso da arquitetura IEEE 802:
• camada LLC: serviço uniforme de enlace independente do
meio
• camada MAC: características dependentes do meio
Nível de Enlace
 Controle de fluxo
stop and wait
originador espera confirmação de um quadro para mandar outro
mecanismo de janelas deslizantes
Quadro 0
ACK 0
Quadro 1
ACK 1
Quadro 0
ACK 0
Stop and Wait
Fonte transmite frame
destino recebe e replica com acknowledgement
(confirmação - ack)
Fonte espera ACK antes de mandar próximo
frame
Destino pode parar fluxo não mandando ACK
Stop and Wait - utilização do
link
Janelas deslizantes
Permite vários frames em transito
Receptor tem um buffer de tamanho W (janela)
Transmissor pode mandar até W frames sem
Ack
Cada frame é numerado
Ack inclui número do próximo frame esperado
Números de sequencia limitados a tamanho do
campo
tamanho em “x” bits -> Frames numerados até 2x
Janelas Deslizantes
Janelas Deslizantes - exemplo
Janelas deslizantes - melhorias
Receptor pode confirmar frames (ack) sem
permitir transmissão (Receive not Ready)
Enviador fica suspenso
Receptor tem que mandar uma confirmação
normal para continuar o tráfego
Em caso de fluxo duplex, utilizar confirmação
junto com dados
técnica chamada “piggybacking”
se nao mandar dados - usar frame com ack
se tem dados mas não tem ack para mandar
manda último número de ack novamente
ou tem um flag indicando se ack é válido ou não (ex.: TCP)
Controle de fluxo - exercícios
Canal transmite a 4kbps e tem tempo de
propagação de 30 ms. Que tamanho de frame
de dados dá uma eficiência de no mínimo 50%
da utilização do canal utilizando stop-and-wait ?
Considere o uso de frames de 1000 bits em um
canal de satélite de 1Mbps e atraso de 270 ms.
Qual a taxa de utilização do canal para controle
de fluxo
stop and wait
janela deslizante de tamanhos 7, 127 e 255
Transmissão de Frames - com e
sem erros
Controle de erros
Detecção de bits errados em frames
Frames perdidos
Pedido de repetição
ack positivo - ok
ack negativo - retransmissão
repetição automática
retransmissão automática depois de um tempo sem
confirmação de frame - timeout
Coletivamente: ARQ -Automatic Repeat Request
Detecção de erros
Bits adicionais adicionados pelo transmissor para
detectar erro
Paridade
indica número par ou ímpar de bits 1 em um caracter
número par de bits errados - não detecta
CRC- Cyclic Redundancy Check
Para um bloco de k bits o transmissor gera uma
sequencia de n bits
Transmite k+n bits - que deve ser divisível sem
resto por um número escolhido (n gerado para
que divisão de k+n por este número seja
inteira)
Receptor divide o frame pelo número
Sem resto - assume-se inexistência de erro
com resto - erro
Controle de erros
ARQ -Automatic Repeat Request
stop and wait
go back N
selective reject
Stop and Wait
Fonte transmite frame único
espera ack
se recebe frame com erro, descarta
transmissor tem mecanismo de timeout
se não recebe confirmação dentro do timeout retransmite
Se o ACK está corrompido, transmissor não o
reconhece
retransmite
receptor recebe duas cópias do frame
usa ACK0 e ACK1
Diagrama
Stop and Wait
simplicidade
ineficiencia
Go Back N (1)
Baseado em janela deslizante
se não tem erro: manda confirmação do frame,
que indica próximo frame esperado
em caso de erro, responde com rejeição
descarta o frame e
todos os frames futuros até que o frame com erro
seja recebido corretamente
tramissor deve voltar (go back) e retransmitir o
frame errado e todos os subsequentes
Go Back N - caso de frame
errado
Receptor detecta erro no frame i
receptor manda rejeição de i
transmissor recebe rejeição
transmissor retransmite frame i e todos
subsequentes
Go Back N - Frame perdido (1)
Frame i perdido
Transmissor manda i+1
receptor recebe frame i+1 for a de sequencia
receptor manda reject i
transmissor volta ao frame I e retransmite
Go Back N - Frame Perdido(2)
Frame i perdido e não foi mandado frame
adicional
receptor nao recebe nada e nao retorna nada
transmissor tem timeout e manda ack com bit P
setado para 1 - pedido de confirmação
receptor interpreta como um comando que deve
ser confirmado com o número do próximo frame
esperado
receptor manda confirmação de i
transmissor transmite frame I
Go Back N - Ack corrompido
Receptor recebe frame I e manda ack I+1 que é
perdido
acks são cumulativos, então ack I+n deve
chegar antes do transmissor ter timeout do
frame i
se chegar ack I+n - considera frames
confirmados
se transmissor tem timeout, manda ack com bit
P ligado, pedindo confirmação
isto pode ser repetido um número de vezes
antes de resetar o enlace
Go Back N Diagrama
Reject seletivo
Também chamado retransmissão seletiva
somente frames rejeitados sao retransmitidos
frames subsequentes sao aceitos pelo receptor
e bufferizados
minimiza retransmissão
receptor deve manter buffer suficiente
Selective Reject Diagram