Unidade I Camada de Enlace

Prévia do material em texto

Padrões de Redes Locais
Unidade I –Camada de Enlace
Prof Sérgio Cardoso
ssilva@unicarioca.edu.br
2
Contexto do Estudo
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1
Roteamento
Ethernet
Camada de Enlace
Open Systems Interconnection Transmission Control Protocol/Internet 
Protocol
2
3
Camada de Enlace
� Terminologia:
� Hospedeiros e 
Roteadores são NÓS.
� Canais de comunicação 
que se conectam a nós 
adjacentes pelo 
caminho de 
comunicação são 
ENLACES.
� Enlaces com fio;
� Enlaces sem fio.
� Pacote na camada-2 é 
um QUADRO, 
encapsula datagrama.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1
A Camada de Enlace de Dados tem a 
responsabilidade de transferir um datagrama 
de um nó ao nó adjacente por um enlace.
3 4
Camada de Enlace
� Conceitos:
� Um PROTOCOLO DE CAMADA DE ENLACE é usado para 
TRANSPORTAR um DATAGRAMA por um ENLACE 
INDIVIDUAL. 
� Cada QUADRO de camada de enlace ENCAPSULA um 
DATAGRAMA de camada de rede.
� O protocolo define o FORMATO DOS QUADROS trocados 
ENTRE OS NÓS nas extremidades do ENLACE, bem como as 
AÇÕES REALIZADAS por esses nós ao ENVIAR E 
RECEBER OS QUADROS.
� Entre as AÇÕES REALIZADAS estão:
� DETECÇÃO DE ERROS, RETRANSMISSÃO,
� CONTROLE DE FLUXO e ACESSO ALEATÓRIO.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 4
5
Camada de Enlace
� Conceitos:
� Uma CARACTERÍSTICA IMPORTANTE da camada de enlace 
é que um datagrama pode ser transportado por DIFERENTES 
PROTOCOLOS DE ENLACE nos DIFERENTES ENLACES do 
caminho.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1
ETHERNET
PPP
TOKEN RING
5 6
Serviços Oferecidos pela Camada de 
Enlace
� ENQUADRAMENTO DE DADOS: encapsulamento de 
DATAGRAMAS em QUADROS acrescentando CABEÇALHO
e TRAILER.
� Estruturas básicas:
o Cabeçalho: comunicação horizontal – endereço de origem e 
destino, etc.
o Dados: encapsula o PDU de rede – parte útil do quadro, onde 
os dados são transportados;
o Trailer: informações adicionais para tratamento de erro.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1
PDU
Dados TrailerCabeçalho
Camada de Rede
Camada de Enlace
Datagrama
Quadro
6
7
Serviços Oferecidos pela Camada 
de Enlace
� ACESSO AO ENLACE: um Protocolo de Controle de 
Acesso ao Meio (Medium Access Control protocol - MAC) 
especifica as REGRAS para transmissão dos quadros pelo 
enlace.
� Para enlaces PONTO A PONTO o remetente pode enviar 
um quadro sempre que o ENLACE ESTIVER OCIOSO.
� Para enlaces COMPARTILHADOS por vários NÓS o 
protocolo de controle de acesso ao meio irá COORDENAR 
AS TRANSMISSÕES.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 7 8
Serviços Oferecidos pela Camada 
de Enlace
� ENTREGA CONFIÁVEL: serviço confiável de entrega na 
camada de enlace com RECONHECIMENTOS e 
RETRANSMISSÕES (a exemplo do TCP – c.transporte).
� Muito usado por enlaces que costumam ter ALTAS TAXAS 
DE ERROS, a exemplo de enlaces sem fio.
o CORRIGE O ERRO NO ENLACE ao invés de forçar 
uma retransmissão fim a fim dos dados pela camada de 
transporte ou aplicação.
� Em enlaces com BAIXAS TAXAS DE ERROS (ex.: enlaces 
de fibra) o serviço pode ser considerado uma 
SOBRECARGA DESNECESSÁRIA.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 8
9
Serviços Oferecidos pela 
Camada de Enlace
� CONTROLE DE FLUXO: fornece controle de fluxo para 
EVITAR que um NÓ REMETENTE de um lado do enlace 
CONGESTIONE o NÓ RECEPTOR o outro lado.
� Os nós de cada lado de um enlace têm uma CAPACIDADE 
LIMITADA de armazenar quadros.
� O nó receptor pode RECEBER QUADROS a uma 
VELOCIDADE MAIOR do que sua CAPACIDADE DE 
PROCESSÁ-LOS.
� SEM o CONTROLE DE FLUXO, o buffer do receptor pode 
TRANSBORDAR e quadros podem ser PERDIDOS.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 9 10
Serviços Oferecidos pela Camada 
de Enlace
� DETECÇÃO DE ERROS: é feito quando um NÓ 
TRANSMISSOR ENVIA BITS DE DETECÇÃO DE ERROS no 
quadro e o NÓ RECEPTOR REALIZA A VERIFICAÇÃO DE 
ERROS.
� Um nó receptor pode decidir INCORRETAMENTE que um 
bit de uma quadro é 0 quando foi transmitido como 1 e vice-
versa.
� Erros de bits são introduzidos por ATENUAÇÃO DO SINAL
e RUÍDO ELETROMAGNÉTICO.
� A detecção de erros na camada de enlace geralmente é 
MAIS SOFISTICADA e é IMPLEMENTADA EM 
HARDWARE.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 10
11
Camada de Enlace
� Serviços Oferecidos pela Camada de Enlace:
� CORREÇÃO DE ERROS: complementar a DETECÇÃO DE 
ERROS (que detecta o erro) mas também DETERMINA EM 
QUE LUGAR DO QUADRO OS ERROS OCORRERAM e, 
então, OS CORRIGE.
� Alguns protocolos fornecem correção de erros na camada 
de enlace APENAS PARA O CABEÇALHO DO QUADRO 
e não para o quadro inteiro.
� TRANSMISSÃO HALF-DUPLEX e FULL DUPLEX:
� Half-duplex: os nós em ambas as extremidades do enlace 
podem transmitir, MAS NÃO AO MESMO TEMPO.
� Full-duplex: podem transmitir AO MESMO TEMPO.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 11 12
Camada de Enlace
� Onde é implementada 
a CAMADA DE 
ENLACE?
� É implementada no 
“adaptador” (ou placa 
de interface de rede, 
NIC)
� placa Ethernet, placa 
PCMCI, placa 802.11.
� implementa camada de 
enlace e física.
� É um combinação de 
hardware, software, 
firmware.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1
contro-
lador
física
transmissão
cpu memória
barramento
hospedeiro
(p. e., PCI)
placa adaptadora
de rede
esquema do hospedeiro
aplicação
transporte
rede
enlace
enlace
física
12
13
Enquadramento de dados
� É a delimitação dos quadros, necessária para sua a correta 
recepção, definindo seu INÍCIO e FIM.
� Algumas técnicas utilizadas:
� Contagem de Bytes;
� Orientado a Bit;
� Orientado a Caractere.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 13 14
Enquadramento de dados
� Técnica de Contagem de Bytes:
� Um campo do cabeçalho é utilizado para definir o 
TAMANHO DO QUADRO.
� Sabendo a QUANTIDADE DE BYTES a serem 
transmitidos a camada física saberá ONDE O QUADRO 
TERMINA.
� Normalmente utilizado quando o CAMPO DE DADOS 
POSSUI TAMANHO VARIÁVEL.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 14
15
Enquadramento de Dados
� ENQUADRAMENTO DE DADOS:
� Técnica de Contagem de Bytes:
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 15
Existe a possibilidade 
de ocorrer algum 
PROBLEMA ao se 
utilizar essa 
técnica???
SIM! O campo de 
contagem pode ser 
alterado e a camada de 
enlace do receptor não 
saberá onde o quadro 
termina corretamente.
16
Enquadramento de dados
� flags para identificar os limites de cada quadro
� Protocolos orientado a caractere
� Protocolos orientado a bit
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 16
Flag
01111110
Flag
01111110
Flag
01111110
Flag
01111110Dados ChecksumProtocoloControleEndereço
Quadro
17
Enquadramento de Dados
� Técnica de Orientado a Caractere:
� Para que o receptor identifique o INÍCIO e FIM de um 
quadro um CARACTERE ESPECIAL é utilizado para 
MARCAÇÃO.
� O caractere especial utilizado para marcação é 
denominado de FLAG.
� PROBLEMA?!??
� Se houver a OCORRÊNCIA de um CARACTERE 
ESPECIAL igual ao FLAG dentro dos Dados!!!
� SOLUÇÃO: Utilizar byte de enchimento (byte stuffing), 
isto é, OUTRO CARACTERE ESPECIAL denominado de 
ESCAPE (ESC).
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 17 18Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 18
Enquadramento de Dados
� Byte stuffing
� Existe um caractere especial para identificar o 
delimitador no quadro
� Transmissor:
� acrescenta (“stuffs”) um byte extra como padrão <01111101> 
(escape) antes de cada byte com o padrão de flag <01111110> 
nos dados 
� Receptor: 
� Um byte 01111101 seguido de 01111110 em seguida: descarta 
o primeiro e continua a recepção de dados
� Único byte 01111110: então é um flag
19
Camada de Enlace
� Técnica de Orientado a Caractere:
� Mas e se houver a OCORRÊNCIA do ESCAPE dentro 
dos Dados???
� SOLUÇÃO: utilizar O MESMO byte stuffing. Quando o 
receptor encontrar dois caracteres ESCAPE sucessivos 
um deles será removido.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1
FLAG FLAG FLAG
Quadro
FLAG FLAG FLAG
Quadro
ESC
FLAG ESC FLAG FLAG ESC FLAGESC
FLAG ESC FLAG FLAGESC FLAGESCFLAG FLAG ESC
FLAG ESC ESC ESCESC FLAGESCFLAG FLAG ESC
19 20
ENQUADRAMENTO DE DADOS:
� Técnica de Orientado a Bit:
� Para que o receptor identifique o INÍCIO e FIM de um 
quadro uma SEQUENCIA DE BITS é utilizada para 
MARCAÇÃO.
� A sequencia de bits utilizada para marcação é 
denominada de FLAG.
� PROBLEMA???
o Se houver a OCORRÊNCIA de uma SEQUENCIA DE 
BITS igual ao FLAG dentro dos Dados!!!
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1
Dados TrailerCabeçalho FLAGFLAG
20
21
ENQUADRAMENTO DE DADOS
� Técnica de Orientado a Bit:
� SOLUÇÃO: usar bit de enchimento 0 (bit stuffing).
� A cada 5 bits de dados sucessivos iguais a 1 acrescentar 
um bit stuffing igual a 0 em seguida.
� EXEMPLO:
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1
������ Msg a ser transmitida
���� Msg com bits 0 inseridos
� c/ FLAG
�� Msg recebida c/enchimento (0)
���� Msg recebido com sucesso
FLAG: 01111110
0110111111111011111011111001
0110111110111101111100111110001
01111110011011111011110111110011111000101111110
0110111110111101111100111110001
0110111111111011111011111001
21 22Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 22
Endereçamento
� Associado à interface de comunicação
� Endereço único para cada interface
� Formato definido pelo protocolo de enlace e seguido pelos 
fabricantes
� Ex: quadro Ethernet (6 bytes para endereços, 248 endereços)
End. destino End. origem Tam Dados Checksum
6 6 2 0 - 1500 4
23Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 23
Códigos de Detecção/Correção de Erros
� Existem duas estratégias básicas para o tratamento dos 
erros:
� Incluir informação redundante suficiente para permitir que o receptor 
detecte e corrija erros (códigos de correção de erros)
� Incluir informação redundante apenas para permitir que o receptor 
apenas detecte erros na mensagem, mas sem identificar qual (códigos 
de detecção de erros)
� Códigos de correção de erros - CCE:
� Não há necessidade de retransmissão
� Receptor é capaz de recuperar a informação
� Frequentemente chamada de correção antecipada de erros - Forward
Error Correction – FEC
� Códigos de detecção de erros -CDE (Feedback):
� Receptor detecta erro e solicita retransmissão
� Implementação através dos protocolos ARQ – Automatic Repeat reQuest.
24Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 24
Detecção de Erros
� A detecção de erros é feita através de informação de 
controle enviada no quadro
� Utiliza uma função (ex.: hash) para gerar um código e 
detecção de erro (CDE)
� Envia o CDE junto com a mensagem
Mensagem
Mensagem
CDEFunção(hash)
CDE
Transmissor
25Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 25
Detecção de Erros
� Receptor executa operação inversa
Mensagem CDE
Função CDE’
Iguais
Sim
Não
OK
Erro
Receptor
26Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 26
Detecção de Erros
� Funções de Controle de Erro
� Bit de paridade
� Cyclic Redundancy Check (CRC)
� Exemplos de código de CRC
Nome Polinômio
CRC-12 x12 + x11 + x3 + x2 + 1
CRC-CCITT x16 + x12 + x5 + 1
CRC-16 x16 + x15 + x2 + 1
CRC-32 x36 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1
27
Verificação de Paridade
� Existem 2 esquemas � Paridade PAR e ÍMPAR.
� Seja D uma sequencia de d bits em um quadro.
� Essa técnica ADICIONA UM BIT DE PARIDADE e escolhe 
o valor desse bit de modo que o NÚMERO TOTAL DE 
BITS ‘1’, nos d + 1 bits, seja PAR ou ÍMPAR.
� Ao receptor basta contar quantos ‘1’ há nos d + 1 bits 
recebidos. No exemplo acima, se for encontrado um 
número ímpar de bits com valor 1, o receptor saberá que 
ocorreu PELO MENOS um erro de bit.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 27
1
Exemplo com esquema 
de paridade PAR.
28
Verificação de paridade
� Mas o que acontecerá se ocorrer um 
número par de erros de bit???
� Resultaria em um ERRO NÃO 
DETECTADO!!!
� Usando um esquema da PARIDADE 
BIDIMENSIONAL, tanto a paridade 
da coluna quanto a da linha que 
contiver o bit modificado estarão 
com ERRO, possibilitando sua 
CORREÇÃO!
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 28
Exemplo com esquema de 
paridade PAR.
29Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 29
Detecção e Correção de Erros
� Quando um QUADRO chega ao destino COM ERRO??
� Uso de protocolo ARQ – Automatic Repeat reQuest.
� Receptor descartar o QUADRO e esperar 
RETRANSMISSÃO POR TIMEOUT.
o Esquema de BIT ALTERNADO.
� Receptor envia um RECONHECIMENTO NEGATIVO 
com retransmissão (NAK).
o Esquema de RETRANSMISSÃO INTEGRAL ou de 
RETRANSMISSÃO SELETIVA.
� Verifica se há possibilidade de CORREÇÃO no destino 
com uso do Forward Error Correction – FEC.
30Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 30
Protocolos ARQ
� Automatic Repeat reQuest – (ARQ)
� Utilizam o reconhecimento e retransmissão de quadros para 
correção de erros
� Bit Alternado (Stop and Wait)
� Retransmissão Integral
� Retransmissão Seletiva
31Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 31
Correção de Erros
� Esquema de BIT ALTERNADO (Stop-and-Wait ARQ):
32
Correção de erros
� Esquema de RETRANSMISSÃO INTEGRAL (Go-Back-N ARQ):
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 32
33
Correção de erros
� Esquema de RETRANSMISSÃO SELETIVA (Selective-Repeat
ARQ):
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 33
4
5
6
34
Camada de Enlace
� DETECÇÃO E CORREÇÃO DE ERROS:
� Esquema de Forward Error Correction – FEC:
� Utiliza a operação XOR (OU exclusivo) para corrigir o erro na 
transmissão de uma porção (p) do quadro enviado.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1
QUADRO ORIGINAL
p1 p2 p3
Representação em bits
p1 0 1 1 0
p2 1 1 1 0
p3 1 0 1 0
XOR’ 1 0 0 0
p3 1 0 1 0
FEC
XOR’’ 0 0 1 0
QUADRO 
TRANSMITIDO
p1 p2 p3 FEC
Transmissor
34
35
Camada de Enlace
� DETECÇÃO E CORREÇÃO DE ERROS:
� Esquema de Forward Error Correction – FEC:
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1
QUADRO ORIGINAL
p1 p2 p3
Representação em bits
p1 0 1 1 0
p3 1 0 1 0
FEC 0 0 1 0
XOR’ 1 1 0 0
FEC 0 0 1 0
p2 (porção perdida)
XOR’’ 1 1 1 0
QUADRO RECEBIDO 
COM ERRO
p1 p2 p3 FEC
Receptor
ERRO
CORRIGIDO!!!
35 36Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 36
Controle de Fluxo
� Para EVITAR que um NÓ REMETENTE de um lado do enlace 
CONGESTIONE o NÓ RECEPTOR o outro lado.
� REGULA o volume de dados enviados para não gerar uma sobrecarga 
(overflow) no receptor.
� Duas soluções:
� Stop-and-Wait (similar ao BIT ALTERNADO): envia um quadro e 
aguarda a confirmação. Se houver timeout, retransmite o quadro.
� Receptor envia EXPLICITAMENTE mensagens informando 
congestionamento. Assim o Transmissor REDUZ A TAXA DE 
ENVIO de quadros.
37
CONTROLE DE FLUXO
� Protocolo Stop-and-Wait considerando canal sem ruído.
Prof Sergio Cardoso - Padrõesde Redes Locais - Unidade 1 37 38
CONTROLE DE FLUXO
� Protocolo Stop-and-Wait ARQ considerando um canal 
com ruído.
� São implementados NÚMEROS DE SEQUENCIA para 
NUMERAR OS QUADROS antes do envio pelo EMISSOR.
� São implementados NÚMEROS DE CONFIRMAÇÃO pelo 
RECEPTOR para informar ao EMISSOR o NÚMERO DE 
SEQUENCIA do próximo QUADRO ESPERADO.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 38
39
CONTROLE DE FLUXO
� Protocolo Stop-and-Wait ARQ (canal com ruído).
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 39 40
Controle de Fluxo
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 40
41
Controle de Fluxo
� CONTROLE DE FLUXO:
� Análise de Eficiência:
� Métrica: Produto Largura de Banda-Atraso = número 
máximo de bits que um enlace pode comportar.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 41 42
Controle de Fluxo
� CONTROLE DE FLUXO:
� Análise de Eficiência - Protocolo Stop-and-Wait ARQ.
Analogia:
� Suponha que, em um sistema Stop-and-Wait ARQ, a 
Largura de Banda do enlace é 1 Mbps e 1 bit leva 20 ms
para fazer a viagem de ida e volta (Atraso).
� Produto Largura de Banda-Atraso é:
1 Mbps * 20 ms = (1 x 106) bits/s * (20 x 10-3) s = 20.000 bits
� O sistema é capaz de enviar 20.000 bits durante o tempo 
que leva para os dados irem e voltarem (Atraso).
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 42
43
Controle de Fluxo
� CONTROLE DE FLUXO:
� Análise de Eficiência - Protocolo Stop-and-Wait ARQ.
� Supondo que o tamanho do quadro seja 1.000 bits, qual é 
a porcentagem de utilização do enlace?
� O sistema é capaz de enviar 20.000 bits durante o tempo 
que leva para os dados irem e voltarem (Atraso), mas o 
emissor enviou apenas 1.000 bits (1 quadro). Logo: 
1.000 bits / 20.000 bits = 0,05 ou 5% de utilização
� Por essa razão, o uso do Stop-and-Wait ARQ
DESPERDIÇA a capacidade de um enlace com uma 
Largura de Banda elevada ou Atraso longo.
� Qual é a porcentagem de utilização do enlace se for possível 
enviar 15 quadros durante o tempo de ida e volta?
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 43 44
Controle de Fluxo
� CONTROLE DE FLUXO:
� Protocolo Go-Back-N ARQ (canal com ruído).
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1
Janelas
Deslizantes
44
45
Controle de Fluxo
� CONTROLE DE FLUXO:
� Conceito de JANELAS DESLIZANTES:
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 45 46
Controle de Fluxo
� CONTROLE DE FLUXO:
� Protocolo Go-Back-N ARQ (canal com ruído).
� Números de Sequencia são módulo 2m, onde m é o 
tamanho, em bits, do campo número de sequencia.
� Por exemplo: se m = 4, os números de sequencia vão de 0 a 
15, podendo a sequencia ser repetida (cíclica).
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, ...
� O Tamanho da janela de transmissão (EMISSOR) tem de ser 
menor que 2m e o Tamanho da janela de recepção é sempre 
1 (RECEPTOR).
� Por quê o Tamanho da janela de transmissão (EMISSOR) 
tem de ser menor que 2m???
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 46
47
Controle de Fluxo
� CONTROLE DE FLUXO:
� Tamanho da janela de transmissão < 2m .
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 47 48
Controle de Fluxo
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 48
49
Camada de Enlace
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 49 50
Controle de Fluxo
� CONTROLE DE FLUXO:
� Protocolo Selective Repeat ARQ (canal com ruído).
Janelas
Deslizantes
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 50
51
Controle de Fluxo
� CONTROLE DE FLUXO:
� Protocolo Selective Repeat ARQ (canal com ruído).
� O Tamanho máximo da janela de transmissão (EMISSOR) é 
de 2m-1.
� Por exemplo, se m = 4, os números de sequencia vão de 0 a 
15, no entanto o tamanho da janela é de apenas 8.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 51 52
Controle de Fluxo
� CONTROLE DE FLUXO:
� Protocolo Selective Repeat ARQ (canal com ruído).
� O Tamanho máximo da janela de recepção (RECEPTOR) é 
igual ao tamanho da janela de transmissão de 2m-1.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 52
53
Controle de Fluxo
� CONTROLE DE FLUXO:
� Por quê o Tamanho da janela de transmissão (EMISSOR) 
tem de ser igual a 2m-1???
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 53 54
Controle de Fluxo
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 54
55Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 55
Enlaces e protocolos de acesso 
múltiplo
� Dois tipos de “enlaces”:
� Dois tipos de ENLACES:
� Enlaces ponto a ponto: um único remetente em uma 
extremidade do enlace e um único receptor na outra.
� Enlaces broadcast: vários nós remetentes e receptores, todos 
conectados ao mesmo canal de transmissão único e 
compartilhado.
56
Protocolos de acesso múltiplo
� QUESTÃO: Como coordenar o acesso de vários nós 
remetentes e receptores a um canal broadcast 
compartilhado?
� RESPOSTA: Usando Protocolos de Acesso ao Meio ou 
Protocolos de Acesso Múltiplo.
� Problemática:
� Como todos os nós têm a capacidade de transmitir 
quadros, mais do que dois nós podem transmitir ao 
mesmo tempo ocasionando uma COLISÃO!!!
� Quando há COLISÃO nenhum dos nós receptores 
consegue INTERPRETAR OS DADOS e há um 
DESPERDÍCIO do TEMPO DE USO DO CANAL.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 56
57Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 57
� Os Protocolos de Acesso Múltiplo podem ser 
classificados nas seguintes CATEGORIAS:
� Protocolos de Divisão de Canal:
� Divide o canal em “pedaços menores” (intervalos de 
tempo, frequência ou código).
� Aloca um pedaço ao nó para uso exclusivo.
� Protocolos de Acesso Aleatório:
� Canal não dividido, permite colisões.
� Protocolos de Revezamento:
� Os nós se revezam, mas os nós com mais a enviar
podem receber mais tempo.
Protocolos de acesso múltiplo
58
Protocolos de Divisão de Canal
TDMA: Time Division Multiple Access 
� Acesso ao canal em “rodadas”.
� Cada estação recebe um intervalo de tamanho fixo
(tamanho = tempo transmissão do pacote) a cada rodada.
� Intervalos não usados ficam ociosos.
� Exemplo: LAN de 6 estações, 1, 3, 4 têm pacote, 
intervalos 2, 5, 6 ociosos
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 58
1 3 4
quadro de
6 intervalos
2 5 6 1 3 42 5 6
59
Protocolos de Divisão de Canal
FDMA: Frequency Division Multiple Access 
� Espectro do canal dividido em bandas de frequência.
� Cada estação recebe um banda de frequência fixa.
� Tempo de transmissão não usado nas bandas de frequência 
fica ocioso.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 59
b
a
n
d
a
s
 
d
e
 
f
r
e
q
.
cabo FDM
60
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1
Camada de Enlace
� ACESSO AO ENLACE:
� Protocolos de Divisão de Canal:
CDMA: Code Division Multiple Access 
� Utiliza um “código” exclusivo atribuído a cada nó (particionamento de 
conjunto de código).
� Todos os nós compartilham mesma frequência, mas cada usuário 
tem a própria sequência de “chipping” para codificar os dados.
� Permite que múltiplos usuários “coexistam” e transmitam 
simultaneamente com o mínimo de interferência (se os códigos 
forem “ortogonais”).
60
61Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 61
Protocolos de acesso aleatório
� Quando o nó tem um pacote a enviar:
� Transmite na velocidade de dados R total do canal.
� Sem coordenação a priori entre os nós.
� Se dois ou mais nós transmitindo � gera “colisão”.
� Protocolo MAC de acesso aleatório especifica: 
� Como detectarcolisões.
� Como recuperar-se de colisões.
� Exemplos de protocolos MAC de acesso aleatório:
� slotted ALOHA
� ALOHA
�CSMA, CSMA/CD e CSMA/CA.
62Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 62
CSMA (Carrier SenseMultiple Access)
� “Acesso Múltiplo por Detecção de Portadora”
� Utiliza o princípio do “ouça antes de falar”:
� Se o nó transmissor perceber que o canal está ocioso, 
transmite o quadro inteiro � detecção de portadora.
� Se perceber que o canal está ocupado, adia transmissão 
por um tempo aleatório � “backoff”.
63
CSMA (Carrier SenseMultiple Access)
� Mesmo “escutando o 
meio” antes de transmitir, 
COLISÕES ainda podem 
ocorrer???
� SIM, de acordo com o 
atraso de propagação
dois nós podem NÃO ouvir 
a transmissão um do outro.
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 63 64Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 64
� “Acesso Múltiplo por Detecção de Portadora/Detecção de 
Colisão”
� Similar ao CSMA, porém, o nó que está transmitindo ouve o canal 
enquanto transmite.
� Se esse nó detectar que outro nó está transmitindo ele para de 
transmitir � detecção de colisão; e usa algum protocolo para 
determinar quando deve tentar transmitir novamente.
� Quando há uma colisão os nós que estão transmitindo param e 
aguardam um tempo aleatório para tentar transmitir novamente 
conforme protocolo CSMA.
� Detecção de colisão:
� fácil em LANs com fio: mede intensidades de sinal, compara sinais 
transmitidos, recebidos
� difícil nas LANs sem fio: intensidade do sinal recebido abafada pela 
intensidade da transmissão local
CSMA/CD (Collision Detection)
65Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 65
Operação do CSMA/CD
� Colisão ocupa o canal durante a 
transmissão
� Estações escutam enquanto transmitem
1. Se o canal está livre → transmite, senão vai 
para o passo 2
2. Se o canal está ocupado, escuta até estar 
livre e então transmite
3. Se for detectada uma colisão, gera jam e 
cessando transmissão
4. Após o jam espera um tempo aleatório e 
inicia o processo novamente (passo 1)
66Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 66
� Protocolo de acesso ao meio (CSMA/CD)
CSMA/CD
Monta
quadro
Verifica
meio
Espera
backoff
Calcula
backoff
Aguarda
gap
Transmite
quadro
Envia
jam
Meio
livre?
Colisão?
Muitas
colisões?
Terminou?
Não
Não
Não
Sim
Sim
Quadro
enviado
Quadro
descartado
Sim
67
Acesso Ordenado
� Características:
� não existe colisão
� cada estação sabe quando deve 
transmitir
� o retardo de acesso é limitado
� Polling:
� Nó mestre “convida” nós escravos 
a alternarem a transmissão.
� Normalmente usado com 
dispositivos escravos “burros”.
� Preocupações:
� Sobrecarga da seleção.
� Latência.
� Único ponto de falha (mestre).
Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 67
mestre
escravos
poll
dados
dados
68Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 68
T
dados
(nada a
enviar)
T
Passagem de Permissão
� Passagem de permissão:
� Permissão de controle passada 
de um nó para o próximo 
sequencialmente.
� Preocupações:
� Sobrecarga da permissão 
� Latência
� Único ponto de falha 
(permissão).
69Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 69
� Endereço IP de 32 bits: 
� endereço da camada de rede
� usado para obter datagrama até sub-rede IP de destino 
(atravessando vários enlaces).
� Endereço MAC (ou LAN ou físico ou Ethernet) :
� função: levar quadro de uma interface para outra interface 
conectada fisicamente (na mesma rede)
� Endereço MAC de 48 bits (para maioria das LANs)
� Gravado diretamente na ROM dos adaptadores de rede, NIC, às 
vezes também configurável por software.
Endereçamento MAC e ARP
70Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 70
Cada adaptador na LAN tem endereço de LAN exclusivo
Endereço de broadcast =
FF-FF-FF-FF-FF-FF
= adaptador
1A-2F-BB-76-09-AD
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
71-65-F7-2B-08-53
LAN
(com ou
sem fio)
Endereços de LAN e ARP
71Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 71
� Alocação de endereço MAC administrada pelo IEEE.
� Fabricante compra parte do espaço de endereços MAC 
(para garantir exclusividade)
� Analogia:
� Endereço MAC: como o CPF.
� Endereço IP: como o endereço postal.
� Endereço MAC plano � portabilidade.
� Pode mover uma placa de uma LAN para outra.
� Endereço IP hierárquico NÃO portável.
� Endereço depende da sub-rede IP à qual o nó está 
conectado.
Endereços de LAN (mais)
72Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 72
ARP: Address Resolution Protocol
� Cada nó IP (hosp., roteador) 
na LAN tem tabela ARP
� Tabela ARP: mapeamentos de 
endereço IP/MAC para alguns 
nós da LAN
<endereço IP; endereço MAC; TTL>
� TTL (Time To Live): 
tempo após o qual o 
mapeamento de endereço 
será esquecido 
(normalmente, 20 min)
Pergunta: Como determinar
endereço MAC de B sabendo
o endereço IP de B?
1A-2F-BB-76-09-AD
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
71-65-F7-2B-08-53
LAN
137.196.7.23
137.196.7.78
137.196.7.14
137.196.7.88
73Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 73
Protocolo ARP: mesma LAN (rede)
� A quer enviar datagrama a B, e 
endereço MAC de B não está na 
tabela ARP de A.
� A envia por broadcast pacote de 
consulta ARP, contendo endereço IP 
de B
� endereço MAC de destino = 
FF-FF-FF-FF-FF-FF
� todas as máquinas na LAN 
recebem consulta ARP
� B recebe pacote ARP, responde para 
A com seu endereço MAC (de B)
� quadro enviado ao endereço 
MAC de A (unicast)
� A salva em cache par de endereços 
IP-para-MAC em sua tabela ARP até 
a informação expirar
� estado soft: informação que 
expira (desaparece) se não 
for renovada
� ARP é “plug-and-play”:
� nós criam suas tabelas ARP 
sem intervenção do 
administrador de rede
74Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 74
Endereçamento: roteando para outra LAN
acompanhamento: enviar datagrama de A para B via R
suponha que A saiba o endereço IP de B
� duas tabelas ARP no roteador R, uma para cada rede IP (LAN)
R
1A-23-F9-CD-06-9B
222.222.222.220
111.111.111.110
E6-E9-00-17-BB-4B
CC-49-DE-D0-AB-7D
111.111.111.112
111.111.111.111
A
74-29-9C-E8-FF-55
222.222.222.221
88-B2-2F-54-1A-0F
B
222.222.222.222
49-BD-D2-C7-56-2A
75Prof Sergio Cardoso - Padrões de Redes Locais - Unidade 1 75
Endereçamento: roteando para outra LAN
1. A cria datagrama IP com origem A, destino B 
2. A usa ARP para obter endereço MAC de R para 111.111.111.110
3. A cria quadro da camada de enlace com endereço MAC de R como destino, quadro contém datagrama 
IP A-para-B
4. NIC de A envia quadro
5. NIC de R recebe quadro 
6. R remove datagrama IP do quadro Ethernet, vê o seu destinado a B
7. R usa ARP para obter endereço MAC de B
8. R cria quadro contendo datagrama IP A-para-B e envia para B
R
1A-23-F9-CD-06-9B
222.222.222.220
111.111.111.110
E6-E9-00-17-BB-4B
CC-49-DE-D0-AB-7D
111.111.111.112
111.111.111.111
A
74-29-9C-E8-FF-55
222.222.222.221
88-B2-2F-54-1A-0F
B
222.222.222.222
49-BD-D2-C7-56-2A
Este é um exemplo realmente
importante – procure entender bem!