aula5-redes

Prévia do material em texto

Fundamentos de Redes de Computadores
Professor: Rodrigo da Rosa Righi
Contato: rrrighi@unisinos.br
Aula: 5
Dia/Horário: Quinta-Feira, 19:30 - 22:23
Você lembra da Aula 5?
Dado e sinal analógico e digital
Lembramos das 4 
transformações
PCM
Sincronização no Manchester
Modulação QAM
Agenda
Fundamentos da Camada Data Link
Serviços da Camada Data Link
Framming
Controle de Fluxo
Controle de Erros
Subcamada de Acesso ao Meio
Aloha Puro, Aloha Slotted
CSMA/CD
Protocolos Livres de Colisão
Revisando...
Camada Data Link
Modelo de 
Referência TCP/IP 
possui 4 camadas
Aplicação
Estamos nos 
baseando no modelo 
híbrido proposto por 
Tanenbaum
Transporte
Rede
Data Link
Física
Principais funções da 
camada Data Link
Controle de Fluxo
Controle de Erros
Ou Camada 
de Enlace
Camada Data Link
Fornecer uma interface 
bem definida para a 
interface de rede
Lidar com 
erros na 
transmissão
Regular 
o fluxo
Gerenciar frames
Pega os dados da 
camada de Rede e os 
encapsula em quadros
Ações
Camada Data Link
Frame 
Data 
Link
Cabeçalho
Região de Dados 
(Payload)
Rabeira
Pacote
Payload RabeiraCabeçalho
Pacote
Payload RabeiraCabeçalho
Máquina Transmissora Máquina Receptora
Frame
Tipos de Serviço da Camada Data Link
O principal serviço da camada Data Link é transferir 
dados da camada de rede de uma máquina fonte para a 
camada de rede de uma máquina destino.
Tipos de 
Serviço
Sem Conexão e sem 
ACK
Sem Conexão e com 
ACK
Com Conexão e 
com ACK
Tipos de Serviço da Camada Data Link
Sem Conexão e sem ACK
Frames 
independentes para 
a máquina destino
Máquina destino não 
faz reconhecimento 
(ACK)
Não há o 
estabelecimento da 
conexão
Se um frame é perdido 
devido a ruído, por 
exemplo, não há tentativas 
de retransmissão
Uso
Tráfego em tempo real
Streamming
Perda de dados é melhor 
que lentidão na 
transmissão
Tipos de Serviço da Camada Data Link
Não há conexões 
lógicas 
estabelecidas
Mas há ACKs 
individuais para 
cada um dos 
frames enviados
Como ocorre a 
retransmissão?
Caso o ACK não chega 
num determinado tempo 
(timeout), retransmite-se os 
frames que não chegaram
Uso Sistemas Wireless
Problema?
Num ambiente com 
muito ruído, podemos 
ter um tráfego 
desnecessário na rede
Frame pode não chegar
ACK pode se perder
Sem Conexão e com ACK
Tipos de Serviço da Camada Data Link
Conexão lógica antes 
dos dados serem 
transmitidos
Existem sempre três fases
Estabelecimento 
da conexão
Transmissão 
dos dados
Encerramento 
da conexão
Uso
Necessidade de confia-
bilidade na transmissão
Perda de frames não é 
tolerada
Frames 
chegam em 
ordem
Com Conexão e com ACK
Framming
Camada Data Link deve ter 
noção de um Frame Por que?
Para fazer o checksum 
(verificação de 
somatórios) do frame
Métodos para 
demarcar um frame
Contagem de 
Caracteres
Flags no início e no fim
Framming
Contagem de Caracteres
Presença de 
cabeçalho que 
informa o número de 
caracteres
3 1 2 3 1 4 5 5 6 7 8 9 2 0 1 2 2 3
Frame 1 Frame 2 Frame 3 Frame 4 Frame 5
Caractere de contagem
Problema?
O próprio campo que informa a quantidade de 
caracteres do frame pode estar crrompido
Framming
Há flags que 
delimitam o início e o 
fim de um dado frame
Problema?
Pode acontecer que os bits da Própria flag 
estejam no frame
Alternativa? Colocar bits especiais (bit stuffing)
Flag Cabeçalho Payload Rabeira Flag
Uso de Falgs no Início e no Fim
Controle de Erros
Quando o transmissor envia um frame, ele geralmente lança 
um temporizador. Caso esse temporizador expire depois de 
um intervalo, podemos ter a sua retransmissão dependendo 
do tipo de serviço usado na camada.
Caso um frame ou um ACK for perdido, o transmissor posui 
um problema em potencial. Uma solução óbvia é transmitir o 
frame novamente. Entretanto, múltiplos frames podem ser 
retransmitidos e podemos correr o risco do receptor aceitar o 
frame duas ou mais vezes.
Colocar um número de 
sequência em cada frameIdeia
Controle de Erros
Principais Estratégias
Bit de paridade Checksum Código de HammingCRC
Detecta erros de transmissão
Corrige erro em 1 
posição (bit)
Controle de Erros
Paridade
Um bit de paridade é incuído no conteúdo 
transmitido para detecção simples de erros
Paridade Par
Número par de 
uns
Número ímpar de 
uns
Transmitindo 
01010100
Saída: 
010101001 Saída: 010101000
Problema: Erro em vários bits
Transmitindo 
com paridade 
par 01010100
Saída: 
110101101
Tipos
Paridade Ímpar
Controle de Fluxo
Dois grandes grupos 
Stop-and-Wait Janela Deslizante
Protocolo envia um frame e 
então espera o ACK antes de 
transmitir o próximo
Go Back n Repetição Seletiva
Transmissão e/ou recepção de vários 
frames sem enviar ACK para cada 
um deles
Controle de Fluxo
Janela Deslizante
Ter frames de dados 
e de controle na 
mesma transmissão
Uso de informações de piggybacking
Colocar nos frames de saída 
informações uteis ao outro ponto
Ideia: economizar o uso 
de largura de banda
Todos os frames 
possuem 
números de 
sequência
Frames 
de 
controle
RR (Receive Ready)
RNR (Receive Not 
Ready)
REJ (Reject)
SREJ (Selective Reject)
Controle de Erros
Algoritmo de 
controle de Fluxo
Automatic 
Repeat Request
ARQ
Controle de 
fluxo e de erros
Controle de Fluxo
Stop and Wait ARQ
frame
 0
ACK1
frame
 1
ACK0
frame
 1
ACK 0
frame
 0
ACK1
frame
 1
Frame trans-
mission time
ACK trans-
mission time
Propagation time
Time-out interval
Frame 0 lost;
A retransmits
Time-out interval
ACK0 lost;
A retransmits
B discards
duplicate frame
Figure 7.8 Stop-and-Wait ARQ
frame
 0
ACK 0
Ti
m
e
A B
Controle de Fluxo
Go back n ARQ
Ideia de 
Pipeline
Funcionamento
Receptor 
simplesmente 
descarta todos os 
frames subse-
quentes ao erro
Não há ACK 
para os 
frames 
descartados
Camada Datalink se 
recusa a receber 
qualquer frame senão 
aquele que é o próximo 
da sequência
Eventualmente, o ACK 
irá expirar e ele o 
transmissor deve 
retransmitir os frames 
que não possuem ACK
Problema?
Perda de largura de 
banda quando a taxa 
de erros for alta
Controle de Fluxo
Protocolo de Repetição Seletiva ARQ
Frame ruim que não é recebido é 
descartado, mas frames bons são 
recebidos e bufferizados
Funcionamento
Quando o transmissor lança 
o timeout, simplesmente o 
frame que ão recebeu o 
ACK é retransmitido. 
Se o receptor tem todos os 
frames corretos e na 
sequência, ele pode os 
entregar para a camada de rede
Controle de Fluxo
Questões de projeto
Largura de 
banda x 
Espaço em 
Buffer
Repetição Seletiva trabalha 
melhor a largura de banda, 
enquanto precisa de um espaço em 
buffer maior
Controle 
de Fluxo
Protocolo de 
Repetição 
Seletiva ARQ
Protocolo de Go 
Back n ARQ
RR
 (P
 bit
 =
 1)
RR 2
RR 4
REJ 4
RR 5
RR 1
frame
 0
frame
 1
frame
 2
frame
 3
frame
 5
frame
 6
frame
 4
frame
 5
frame
 6
frame
 7
frame
 0
frame
 1
frame
 2
frame
 4
RR 7
(a) Go-back-N ARQ
4, 5, and 6
retransmitted
discarded by
receiver
Timeout
RR
 (P
 bit
 =
 1)
RR 2
RR 4
SREJ
 
4
RR 7
RR 3
frame
 0
frame
 1
frame
 2
frame
 3
frame
 5
frame
 6
frame
 4
frame
 7
frame
 0
frame
 1
frame
 2
frame
 3
frame
 4
frame
 4
RR 1
(b) Selective-reject ARQ
4 retransmittedbuffered by
receiver
Timeout
Figure 7.9 Sliding-Window ARQ Protocols
A B A B
Em redes do tipo 
Broadcast, a camada 
Data Link deve tratar o 
acesso ao meio 
compartilhado.
Para isso, existe a 
submacada MAC - 
Medium Access Control
Subcamada de Acesso ao Meio
Cada de Enlance 
dividida em duas
Camda de Enlace em si
Subcamada de acesso ao meio
Acesso 
múltiplo 
ao meio
Aloha
CSMA
Sem Colisão
Principais 
Represen-
tantes
Bus (Ethernet, 
802.3)
Ring (Token Ring, 
802.5)
Wireless (802.11)
Subcamada de Acesso ao Meio
Subcamada de Acesso ao Meio
Aloha
1970
Tentativa de resolução do 
problema de alocação do 
canal de comunicação
Ideia
Estações não sentem o uso 
de redes pelos demais
Subcamada de Acesso ao Meio
Aloha Puro
Não requer sincronização 
global de tempo
Usuários transmitem tão logo 
tenham dados para transmitir
Sistemas nos quais vários usuários 
compartilham o mesmo meio são 
chamados de sistemas de contenção
Usuários
A
B
C
D
Tempo
Subcamada de Acesso ao Meio
Aloha Puro
Ideia proveniente do 
aprendizado com o Aloha 
Puro
Estações de tempo devem 
respeitar um tempo para 
começar a sua transmissão
Sincronização
Subcamada de Acesso ao Meio
Slotted Aloha
Divide o tempo em 
intervalos discretos
Exige que os usuários 
definem um limite para o 
tempo de um slot
Estações devem esperar 
o começo de um slot 
para transmitir
Usuários
A
B
C
D
Tempo
Slot
Subcamada de Acesso ao Meio
Vazão da rede com Aloha
Subcamada de Acesso ao Meio
Protocolos 
que sentem 
o meio
1 Persistente
Não 
Persistente
p Persistente
CSMA
Carrier Sense 
Multiple Access
Subcamada de Acesso ao Meio
1 
Persis-
tente
Quando uma estação possui dados para enviar, ela 
primeiro escuta o canal para ver se alguém está 
transmitindo.
Se uma colisão existir, a estação espera por um tempo 
aleatório e começa novamente. 
Estação transmite com probabilidade 1 quando o canal está 
ocioso
Se o canal estiver ocupado, a estação espera até que ele se 
torne vago. Quando vago, tenta-se a transmissão 
novamente. 
CSMA 1 
persistence
CD 
(Collision 
Detection)
Ethernet
Subcamada de Acesso ao Meio
Não 
Persis-
tente
Antes de enviar a estação sente o canal. Caso ninguém 
estiver transmitindo, ela começa a transmitir.
Caso o canal já estiver em uso, a estação não continua 
sentindo o canal até terminar a transmissão do outro 
usuário. Ao invés disso, ela espera por um tempo 
aleatório e repete o algoritmo
Subcamada de Acesso ao Meio
p 
Persis-
tente
Antes de enviar a estação sente o canal. Caso 
ninguém estiver transmitindo, ela transmite com 
uma probabilidade p.
O processo é repetido até que todos os frames sejam 
transferidos. No meio tempo em que não transmite, 
outra estação pode transmitir. 
Caso a estacão sentir o canal ocupado, espera-se por 
um tempo aleatóro para entar novamente.
CSMA p 
persistence
CA 
(Collision 
Avoindance)
Wifi e Sistemas 
baseados em radio
Subcamada de Acesso ao Meio
CSMA 
com 
Detecção 
de 
colisão
Estações abortam tão logo detectam uma colisão. 
Se duas estações sentem o canal ocioso e ambas 
começam a transmitir, ambas irão detectar uma colisão
Depois de detectar a colisão, a estação aborta e espera 
por um tempo aleatório para tentar a retransmissão
CSMA/CD alterna períodos de contenção com períodos 
de transmissão
Subcamada de Acesso ao Meio
Até o momento, estudamos alguns 
protocolos de acesso ao meio 
compartilhado com suporte a 
colisões.
Existem aqueles que são sem 
colisões. Será que eles são melhores? 
Eles são usados na prática?
Subcamada de Acesso ao Meio
Protocolo Bit-Map
Contagem Binária
Protocolos 
Livres de colisão
Subcamada de Acesso ao Meio
Protocolo Bit-Map
Contenção com n 
slots, onde n é o 
número de 
máquinas
Slots informam quem 
vai transmitir e a 
ordem dos frames
Protocolo 
de reserva
Problemas? Largura de banda e escalabilidade
1 1 1 1 1 1
Slots de Contenção Frames
0 1 2 3 4 5
1 3 4 0 1 5
0 1 2 3 4 5 0 1 2 3 4 5
Slots de Contenção Slots de ContençãoFrames Frame
Subcamada de Acesso ao Meio
Contagem Binária
Estação que quer usar o canal, faz um broadcast de seu endereço 
em forma de um string de bits para as demais estações
É feita uma operação de OR nos endereços 
e assim delimitada a ordem de transmissão 0 0 1 0
0 1 0 0
1 0 0 1
1 0 1 0 
0 1 2 3
0 - - -
0 - - -
1 0 1 -
1 0 1 0
Estações 0010
e 0100 olham o 
bit 1 e abortam
Estação 1001 
olha o 1 e aborta
Problema?
Justiça