Redes de Comunicação

2025/26

Camada de Ligação de Dados

* Slides traduzidos e adaptados dos originais em Inglês fornecidos com o livro adoptado
Camada de Ligação de Dados 5-1
Camada de Ligação de Dados
 5.1 Introdução e Serviços
 5.2 Detecção e correcção de erros
 5.3 Protocolos de acesso múltiplo
 5.4 Endereçamento
 5.5 Ethernet
 5.6 Comutadores
 5.7 Redes sem fios

Camada de Ligação de Dados 5-2

Camada de Ligação de Dados
Terminologia:
 terminais e routers designam-
se nós
 canais de comunicação que
interligam nós adjacentes
designam-se ligações
 ligações com fios
 ligações sem fios
 LANs
 a unidade de dados é a trama
 tramas encapsulam datagramas

a camada de ligação de dados

é responsável pela transferência
de tramas entre nós adjacentes
Camada de Ligação de Dados 5-3
Camada de Ligação de Dados
 datagrama transferido analogia
em tramas de diferentes  viagem em múltiplos meios
protocolos nas de transporte (metro,
diferentes ligações: avião, autocarro)
 e.g., Ethernet na primeira  viajante = datagrama
ligação, frame relay nas
intermédias e 802.11 na  troço da viagem = ligação
última ligação  meio de transporte = pro-
 diferentes protocolos tocolo de ligação de dados
fornecem diferentes  agência de viagens = algo-
conjuntos de serviços ritmo de encaminhamento
 e.g., pode haver ou não
fiabilidade na ligação

Camada de Ligação de Dados 5-4

Serviços da Camada de Ligação de Dados

 encapsulamento
 como noutras camadas, mas para além do cabeçalho pode
adicionar um trailer
 delineação de tramas (framing)
 descobrir em que ponto de uma sequência de bits ou
bytes começa uma trama
 normalmente é usado um padrão para sincronização, e
pode ser necessário fazer escape se ocorrer nos dados
 controlo de fluxo
 entre nós adjacentes

Camada de Ligação de Dados 5-5

Serviços da Camada de Ligação de Dados

 detecção de erros
 provocados pela atenuação, ruído e interferêncas
 usando CRC em vez de checksum

 correcção de erros
 receptor detecta e corrige erros de bit sem necessidade
de retransmissões
 fiabilidade
 recuperação de erros por confirmações e retransmissões
(Automatic Repeat Request – ARQ)
 raramente usada em tecnologias com baixa taxa de erros
(e.g., fibra óptica, algumas de par entrançado)
 muito usada em ligações sem fios, que têm taxas de erros
elevadas
Camada de Ligação de Dados 5-6
Serviços da Camada de Ligação de Dados

 controlo de acesso ao meio

 determinar que nó pode transmitir em cada instante
 necessário em tecnologias que usam um canal partilhado
 algumas tecnologias permitem transmissão simultânea nos
dois sentidos (full duplex), outras só num sentido de cada
vez (half duplex)
 endereçamento
 em ligações de acesso múltiplo, indicar a qual dos nós
vizinhos se destina a trama
 uso de endereços MAC (endereços físicos)
• endereços diferentes em cada ligação ao longo do percurso

Camada de Ligação de Dados 5-7

Que nós implementam a camada de LD?
 todos!
 implementada no contro-
lador (placa) de rede* esquema do nó

 placa de rede ethernet, aplicação

transporte
placa de rede 802.11 rede cpu memória
lig. dados
 implementa camadas de
ligação de dados e física barramento
contro- (e.g., PCI)
 ligada ao barramento do lig. dados
lador

sistema física
física

 combinação de hardware,
firmware e software placa de rede

Camada de Ligação de Dados 5-8

Comunicação entre controladores

datagrama datagrama

contro- contro-
lador lador

nó emissor nó receptor
datagrama

trama

 lado do emissor:  lado do receptor:

 encapsula datagrama numa  trata erros, fiabilidade,
trama controlo de fluxo, etc.
 adiciona bits para controlo  extrai datagrama e passa-o
de erros, fiabilidade, con- à camada de rede
trolo de fluxo, etc.
Camada de Ligação de Dados 5-9
Camada de Ligação de Dados
 5.1 Introdução e Serviços
 5.2 Detecção e correcção de erros
 5.3 Protocolos de acesso múltiplo
 5.4 Endereçamento
 5.5 Ethernet
 5.6 Comutadores
 5.7 Redes sem fios

Camada de Ligação de Dados 5-10

Detecção de Erros
EDC= Error Detection and Correction bits (redundância)
D = Dados protegidos (podem incluir campos do cabeçalho)

• A detecção de erros nunca é 100% fiável!

• o protocolo pode não detectar determinados erros (mas é raro)
• campos EDC maiores ➔ melhor detecção e correcção de erros

datagrama datagrama
S
EDC'
corresponde a N
D'? Erro detectado!

D EDC D' EDC'

Ligação sujeita a erros

Camada de Ligação de Dados 5-11
Verificação de paridade
Um bit de paridade: Paridade bidimensional:
Detecta erros de apenas um bit Detecta e corrige erros de apenas um bit
paridade
das linhas
bit de
d bits de dados paridade

paridade
das colunas

Paridade par: número de uns é par

(incluindo bit de paridade)
sem erros erro num bit (corrigível)
0 1 1 1 1 0 1 1 1 1
Paridade ímpar: número de uns é ímpar 0 0 0 1 1 0 1 0 1 1 erro de paridade
(incluindo bit de paridade) 1 0 1 0 0 1 0 1 0 0 o bit errado no está no
1 0 1 1 1 1 0 1 1 1 cruzamento entre a
0 1 1 1 1 0 1 1 1 1 linha e a coluna que
erro de paridade falham o teste de pa-
ridade – basta inverter
esse bit para corrigir o
erro
Camada de Ligação de Dados 5-12
Verificação de Redundância Cíclica (CRC)
 considerar os bits de dados, D, como coeficientes de um
polinómio em GF(2)
 escolher um padrão de r+1 bits (gerador), G
 objectivo: escolher r bits de CRC, R, tais que
 <D,R> seja divisível por G (módulo 2)
 o receptor conhece G, e divide <D,R> por G; se o resto não for
zero, foi detectado um erro
 detecta todos os erros que afectem até r bits seguidos (incl.)
 simples de implementar em hardware
 muito utilizado na prática (Ethernet, 802.11 WiFi, ATM)
d bits r bits
D: bits de dados a enviar R: bits de CRC padrão
de bits
fórmula
D * 2r  R matemática
Camada de Ligação de Dados 5-13
 Exemplo de CRC G D R
3 bits de CRC (menos 1 bit que o gerador)
Pretendemos que: '
1 0 1 1 1 0 0 0 0 1 0 0 1
D.2r  R = nG - 1 0 0 1 1 0 1 0 1 1
ou seja‡: 0 0 1 0 1

D.2r = nG  R - 0 0 0 0
0 1 0 1 0
portanto:
- 1 0 0 1
R é o resto da divisão 0 0 1 1 0
de D.2r por G (mod 2) - 0 0 0 0

R = resto[ D.2r ] 0 1 1 0 0
G - 1 0 0 1
0 1 0 1 0
São enviados os bits: - 1 0 0 1
101110011 0 0 1 1
dados crc
Camada de Ligação de Dados 5-14
‡ Em GF(2), subtracção = adição = xor
CRC: Implementação em Hardware

 O CRC é muito usado na camada de ligação de dados por ser

fácil de implementar em hardware
 Baseado em shift registers
 Enviado como trailer porque é calculado à medida que se
transmite a trama
 Exemplo para o polinómio (CRC de 8 bits)
bits de
entrada

C7 C6 C5 + C4 + C3 C2 C1 C0 +

 Um XOR para cada termo não nulo do polinómio excepto o de

grau mais elevado
Camada de Ligação de Dados 5-15
CRC em Hardware: Cálculo
entrada

C2 C1 C0 +

Passo C2 C1 C0 C2 + entrada entrada

Início 0 0 0 1 1
1 0 0 1 0 0
2 0 1 0 1 1 Bits de
3 1 0 1 0 1 dados
4 0 1 0 1 1
5 1 0 1 1 0
6 0 1 1 0 0 3 zeros
7 1 1 0 1 0 (tamanho
8 1 0 1 1 0 do CRC)
9 0 1 1 —
Bits de CRC
Demo: [Link] Camada de Ligação de Dados 5-17
CRC em Hardware: Verificação
entrada

C2 C1 C0 +

Passo C2 C1 C0 C2 + entrada entrada

Início 0 0 0 1 1
1 0 0 1 0 0
2 0 1 0 1 1 Bits de
3 1 0 1 0 1 dados
4 0 1 0 1 1
5 1 0 1 1 0
6 0 1 1 0 0
Bits de
7 1 1 0 0 1
CRC
8 1 0 0 0 1
9 0 0 0 —
Tudo zeros ➔ não houve erro
Camada de Ligação de Dados 5-18
Camada de Ligação de Dados
 5.1 Introdução e Serviços
 5.2 Detecção e correcção de erros
 5.3 Protocolos de acesso múltiplo
 5.4 Endereçamento
 5.5 Ethernet
 5.6 Comutadores
 5.7 Redes sem fios

Camada de Ligação de Dados 5-19

Ligações e Protocolos de Acesso Múltiplo
Dois tipos de “ligações”:
 ponto-a-ponto
 Linha dedicada
 Ethernet comutada

 difusão (cabo ou outro meio partilhado)

 Ethernet original
 Redes wireless 802.11

pessoas numa festa

cabo partilhado ondas rádio no ar ondas rádio (meio partilhado: ar;
(e.g., Ethernet) (e.g., 802.11 WiFi) (satellite) comunicação acústica)
Camada de Ligação de Dados 5-20
Protocolos de Acesso Múltiplo
 canal único de difusão partilhado
 duas ou mais transmissões em simultâneo: interferência
 colisão se um nó recebe dois ou mais sinais ao mesmo tempo

protocolo de acesso múltiplo

 algoritmo distribuído que determina como é feita a
partilha do canal entre os nós (i.e., quem transmite)
 dificuldade: a comunicação para coordenar a partilha do
canal usa o próprio canal!
 não existe outro canal fora de banda para coordenação

Camada de Ligação de Dados 5-21

Protocolo de Acesso Múltiplo Ideal
Canal de difusão com taxa de transmissão R (bps)
1. Quando apenas um nó pretende transmitir,
transmite à taxa R
 Eficiente com apenas um emissor
2. Quando M nós pretendem transmitir, cada um
transmite à taxa média R/M
 Eficiente com muitos emissores
 Distribuição equitativa da capacidade
3. Completamente descentralizado:
 Sem nenhum nó especial para coordenar as transmissões
 Sem necessidade de sincronização de relógios ou slots
4. Simples
Camada de Ligação de Dados 5-22
Protocolos MAC: taxonomia
Três classes principais:
 Partição do canal
 dividir o canal em “pedaços” (time slots, frequências,
códigos)
 afectar um “pedaço” a cada nó para seu uso exclusivo
 Acesso aleatório
 canal não dividido ➜ colisões possíveis
 “recuperação” de colisões

 Por turnos
 os nós transmitem por turnos, mas aqueles que têm mais
para transmitir podem ter turnos mais longos

Camada de Ligação de Dados 5-23

Partição do canal: TDMA*
TDMA: time division multiple access
 acesso ao canal em rondas
 cada estação tem uma slot de comprimento fixo
para transmitir em cada ronda
 slots não utilizadas ➜ capacidade desperdiçada
 exige sincronização de relógios
 exemplo: LAN com 6 estações; 1, 3 e 4 têm
pacotes para transmitir; 2, 5 e 6 não têm
trama com
6 slots
1 3 4 1 3 4

*Multiple Access ➔ múltiplos nós a transmitir. Não confundir com TDM, em que há múltiplos fluxos
que na ligação em causa são transmitidos por um único nó. Camada de Ligação de Dados 5-24
Partição do canal: FDMA*
FDMA: frequency division multiple access
 espectro do canal dividido em bandas de frequências
 a cada estação é atribuída uma banda de freq. fixa
 tempo não utilizado numa banda ➜ desperdício
 exemplo: LAN com 6 estações; 1, 3 e 4 têm pacotes
para transmitir; bandas 2, 5 e 6 não utilizadas
bandas defrequência

*Não confundir com FDM. Camada de Ligação de Dados 5-25

Protocolos de Acesso Aleatório
 Quando um nó quer transmitir
 transmite à capacidade total do canal, R
 ausência de coordenação a priori entre os nós

 Dois ou mais nós a transmitir ➜ colisão

 Protocolo MAC de acesso aleatório especifica:
 como detectar colisões
 como recuperar de colisões (e.g., através de retransmis-
sões retardadas)
 Exemplos de protocolos MAC de acesso aleatório:
 slotted ALOHA
 ALOHA
 CSMA, CSMA/CD, CSMA/CA

Camada de Ligação de Dados 5-26

 Slotted Aloha
Pressupostos: Operação:
 tramas de tamanho igual  quando um nó tem uma
 tempo dividido em slots nova trama para transmi-
de tamanho fixo (tempo tir, fá-lo na próxima slot
de transmissão de uma  se não houver colisão:
trama) pode enviar uma nova
 nós iniciam transmissão trama na slot seguinte
apenas no início da slot  se houver colisão: com
 nós sincronizados probabilidade p, o nó
 se 2 ou mais nós trans-
retransmite a trama em
mitem numa slot, todos cada slot subsequente
detectam a colisão até não haver colisão

Camada de Ligação de Dados 5-27

Slotted Aloha

Prós Contras
 um único nó activo pode  colisões ➔ desperdício
transmitir continuamen- de slots
te à taxa total do canal  slots não utilizadas
 descentralizado: apenas  nós poderiam detectar
as slots têm que estar colisão num tempo
menor que o de trans-
sincronizadas missão duma trama
 simples  exige sincronização de
relógios Camada de Ligação de Dados 5-28
Eficiência do Slotted Aloha
Eficiência: fracção média a  prob. de um dado nó
longo prazo de slots com conseguir transmitir
transmissões bem sucedidas numa dada slot:
= p(1-p)N-1
considerando que existem muitos
nós, e que todos têm tramas para  prob. de qualquer nó
transmitir (backlog permanente) conseguir transmitir:
E(p) = Np(1-p)N-1
 N nós com muitas  Eficiência máxima com
tramas para transmitir p* que maximiza E(p)
 cada nó transmite numa  Ponto com derivada nula

dada slot com probabi- E’(p) = N(1 - p)N-1 - Np(N - 1)(1 - p)N-2
lidade p = N(1 - p)N-2((1 - p) - p(N - 1))
= N(1 - p)N-2(1 - Np)
E’(p) = 0 com p = p* = 1/N
Camada de Ligação de Dados 5-29
Eficiência do Slotted Aloha (cont.)

 A eficiência máxima do  Para N grande,

Slotted Aloha é, então:  lim(N->∞)(1-1/N) = 1
E(p*) = N·1/N(1-1/N)N-1  lim(N->∞)(1-1/N)N = 1/e
= (1-1/N)N-1
 lim(N->∞)E(p*) = 1/e ≈ 0.37
= (1-1/N)N/(1-1/N)

!
Quando há muitos nós a querer
transmitir, a eficiência do Slotted
Aloha é, na melhor das hipóteses, de
apenas 37%

Camada de Ligação de Dados 5-30

Aloha Puro (unslotted)
 mais simples ― dispensa sincronização de relógios
 quando chega uma nova trama
 transmite-a imediatamente

 aumenta a probabilidade de colisão:

 trama enviada em t0 colide com outras tramas enviadas no
intervalo [t0-1,t0+1]
vai colidir com o vai colidir com
início da trama o fim da trama
do nó i do nó i

trama do nó i

Camada de Ligação de Dados 5-31

Eficiência do Aloha Puro
P(sucesso para um dado nó) =
= P(nó transmite) .
P(nenhum outro começa a transmitir em [t0-1,t0]) .
P(nenhum outro começa a transmitir em [t0,t0+1])
= p . (1-p)N-1 . (1-p)N-1
= p . (1-p)2(N-1)

E(p) = Np(1 - p)2(N-1)

E’(p) = N(1 - p)2N-2 – Np·2(N-1)(1 - p)2N-3
= N(1-p)2N-3((1 - p)-2p(N - 1)) = N(1-p)2N-3(1 - p(2N - 1))
E’(p) = 0 com p = p* = 1/(2N-1)
lim(N->∞)E(p*) = ½ * 1/e = 1/(2e) ≈ 0.18

18% ➔ Ainda pior que o Slotted Aloha!!!

Camada de Ligação de Dados 5-32
 Eficiência: Aloha e Slotted Aloha
Aloha Puro
Slotted Aloha
Eficiência (taxa de sucesso)

Carga oferecida G = Np
Camada de Ligação de Dados 5-33
CSMA (Carrier Sense Multiple Access)

CSMA: escutar antes de transmitir

 Se o canal estiver livre, transmitir a trama inteira

 Se o canal estiver ocupado, protelar a transmissão

“Quando um burro fala, os outros baixam as orelhas.”

Camada de Ligação de Dados 5-34

 CSMA: colisões distribuição espacial dos nós
espaço
ainda assim podem ocor-
rer colisões:
o atraso de propagação implica
que dois nós podem não conse-

tempo
guir ouvir a transmissão um do
outro
colisão:
todo o tempo de transmissão
é desperdiçado
nota:
a distância entre os nós e a
velocidade de propagação têm
influência na probabilidade de
colisão
Camada de Ligação de Dados 5-35
CSMA/CD (Collision Detection)
CSMA/CD: CSMA acrescido de
 colisões detectadas num curto espaço de tempo
 transmissões que colidem são abortadas, reduzindo
o desperdício de capacidade
 detecção de colisões:
 fácil em LAN cabladas: medição da intensidade do
sinal, comparação dos sinais transmitido e recebido
 difícil em LAN sem fios: intensidade do sinal
recebido muitíssimo inferior à da transmissão local

“Uma conversa educada”

Camada de Ligação de Dados 5-36
CSMA/CD detecção de colisões
espaço
tempo

tempo de
detecção de
colisão e
abortamento
da transmissão

Camada de Ligação de Dados 5-37

Acesso ao meio (MAC) por turnos
Protocolos MAC com partição do canal:
 partilha eficiente e equitativa do canal com
carga elevada
 ineficientes com carga baixa: atraso no acesso
ao canal, um nó utiliza 1/N da capacidade mesmo
que seja o único activo
Protocolos MAC de acesso aleatório:
 eficientes com carga baixa: um único nó pode
utilizar toda a capacidade do canal
 overhead de colisões com carga elevada
Protocolos MAC por turnos
 pretendem obter o melhor dos dois mundos...
Camada de Ligação de Dados 5-38
Protocolos MAC por turnos
Polling:
 nó “mestre” pede al-
ternadamente a ca- dados
da “escravo” para poll

transmitir mestre
 usado tipicamente dados
com dispositivos
escravos “estúpidos”
 problemas: escravos
 overhead do polling
 latência
 ponto singular de
falha (mestre)
Camada de Ligação de Dados 5-39
Protocolos MAC por turnos
Passagem de testemunho:
T
 testemunho (token) de
controlo pasado se-
quencialmente ao pró-
ximo nó (nada a
 mensagem de teste- enviar)
munho (token) T

 problemas:
 overhead do testemunho
 latência
 ponto singular de falha
(testemunho)
dados
Camada de Ligação de Dados 5-40
Resumo dos protocolos MAC
 partição do canal, por tempo, frequência ou código
 TDMA, FDMA, CDMA

 acesso aleatório (dinâmicos),

 ALOHA, S-ALOHA, CSMA, CSMA/CD
 collision detection: fácil nalgumas tecnologias (cabladas),
muito difícil/impossível noutras (wireless)
 CSMA/CD usado na Ethernet
 CSMA/CA usado no 802.11 (Wi-Fi)

 por turnos
 polling a partir dum nó central, passagem de testemunho
 Bluetooth, FDDI, IBM Token Ring

Camada de Ligação de Dados 5-41

Camada de Ligação de Dados
 5.1 Introdução e Serviços
 5.2 Detecção e correcção de erros
 5.3 Protocolos de acesso múltiplo
 5.4 Endereçamento
 5.5 Ethernet
 5.6 Comutadores
 5.7 Redes sem fios

Camada de Ligação de Dados 5-42

Endereços MAC e protocolo ARP

 Endereços IP de 32 bits:
 endereços da camada de rede
 usados para transportar o datagrama até à sub-rede
de destino
 Endereço MAC (endereço físico):
 função: passar a trama duma interface dum nó a
outra interface doutro nó à qual está fisicamente
ligada (i.e., na mesma sub-rede)
 endereço MAC de 48 bits (na maioria das LANs)
• gravada na ROM da interface de rede (normalmente pode
alterar-se por software)
Camada de Ligação de Dados 5-43
 Endereços MAC e protocolo ARP
Cada interface de rede na LAN tem um endereço MAC único

1A-2F-BB-76-09-AD

Endereço de difusão:
FF-FF-FF-FF-FF-FF

LAN
(cablada ou
wireless)
71-65-F7-2B-08-53
58-23-D7-FA-20-B0

0C-C4-11-6F-E3-98
= interface de rede

Camada de Ligação de Dados 5-44

Endereços MAC
 Atribuição de endereços MAC coordenada pelo IEEE
 Cada fabricante compra uma parte do espaço de
enredeçamento MAC (para garantir unicidade)
 Analogia:
(a) Endereço MAC: número do Cartão de Cidadão
(b) Endereço IP: endereço postal (morada)
 Os endereços MAC são planos ➜ portabilidade
 é possível mover uma interface de rede duma LAN para outra
 Os endereços IP, hierárquicos, não são portáveis
 dependem da sub-rede IP à qual o nó está ligado

Camada de Ligação de Dados 5-45

 ARP: Address Resolution Protocol

Questão: como se determina  Cada nó IP (terminal,

o endereço MAC conhecendo router) na LAN tem uma
o endereço IP? tabela de ARP
 Tabela de ARP: mapea-
[Link]
mento entre endereços
1A-2F-BB-76-09-AD
IP e MAC para alguns nós
[Link]
[Link] <endereço IP; endereço MAC; TTL>
 TTL (Time To Live): tempo
LAN ao fim do qual a entrada
71-65-F7-2B-08-53 vai ser esquecida
58-23-D7-FA-20-B0

0C-C4-11-6F-E3-98
[Link]

Camada de Ligação de Dados 5-46

 Protocolo ARP: na mesma LAN
 A quer enviar um datagrama a  ARP é “plug-and-play”
B, e o endereço MAC de B não  Tradução obtida automatica-
está na tabela de ARP de A mente
 A difunde pedido de ARP
contendo o endereço IP de B A

 endereço MAC de destino:

FF-FF-FF-FF-FF-FF ARP
Request
 todos os nós na LAN
recebem o pedido de ARP B
 B responde a A com o seu
endereço MAC
 trama enviada em unicast para A
o endereço MAC de A
 A guarda em cache a tradução
ARP
IP➔MAC de B Reply
 estado volátil: a tradução
expira (desaparece) se não B
for refrescada
Camada de Ligação de Dados 5-47
Encaminhamento entre LANs
envio dum datagrama de A para B através de R
assumindo que A conhece o endereço IP de B
74-29-9C-E8-FF-55 88-B2-2F-54-1A-0F

A E6-E9-00-17-BB-4B
[Link]
1A-23-F9-CD-06-9B
[Link]

[Link] [Link]
[Link]
B
[Link]
R 49-BD-D2-C7-56-2A
CC-49-DE-D0-AB-7D

 O router R tem duas tabelas de ARP, uma por cada

sub-rede IP a que está ligado

Camada de Ligação de Dados 5-48

Encaminhamento entre LANs (cont.)
 A gera um datagrama com srcIP = [Link] e dstIP =
[Link]
 Através da tabela de encaminhamento, A descobre que para
[Link] o próximo salto é [Link] (gateway)
 Usando o ARP, A descobre que o endereço MAC da interface
[Link] de R é o E6-E9-00-17-BB-4B
 A encapsula o datagrama numa trama com srcMAC = 74-29-
9C-E8-FF-55 e dstMAC = E6-E9-00-17-BB-4B
 A envia a trama para R através da sua interface; R recebe-a
74-29-9C-E8-FF-55 88-B2-2F-54-1A-0F

A
E6-E9-00-17-BB-4B
[Link]
1A-23-F9-CD-06-9B
[Link]

[Link] [Link]
[Link] B
[Link]
R 49-BD-D2-C7-56-2A

CC-49-DE-D0-AB-7D
Camada de Ligação de Dados 5-49
Encaminhamento entre LANs (cont.)
 R desencapsula o datagrama IP da trama e verifica que este
se destina a B
 Através da tabela de encaminhamento, R vê que tem ligação
directa a B (gateway é [Link])
 Usando o ARP, R descobre que o endereço MAC de B é
49-BD-D2-C7-56-2A
 R encapsula o datagrama numa trama com srcMAC = 1A-23-
F9-CD-06-9B e dstMAC = 49-BD-D2-C7-56-2A
 R envia a trama para B através da placa de rede; B recebe-a
74-29-9C-E8-FF-55 88-B2-2F-54-1A-0F

A
E6-E9-00-17-BB-4B
[Link]
1A-23-F9-CD-06-9B
[Link]

[Link] [Link]
[Link] B
[Link]
R 49-BD-D2-C7-56-2A

CC-49-DE-D0-AB-7D
Camada de Ligação de Dados 5-50
Encaminhamento entre LANs

IMPORTANTE

Ao longo do percurso do datagrama entre o

nó de origem e o de destino os endereços IP
mantêm-se iguais, mas os endereços MAC são
diferentes em cada salto

 Os endereços IP pertencem à camada de rede, responsável pela

entrega de pacotes ao destino final, por isso têm de se manter
 Os endereços MAC pertencem à camada de ligação de dados,
responsável pela entrega de pacotes entre máquinas adjacentes,
pelo que só são válidos numa dada ligação

Camada de Ligação de Dados 5-51

Camada de Ligação de Dados
 5.1 Introdução e Serviços
 5.2 Detecção e correcção de erros
 5.3 Protocolos de acesso múltiplo
 5.4 Endereçamento
 5.5 Ethernet
 5.6 Comutadores
 5.7 Redes sem fios

Camada de Ligação de Dados 5-52

Ethernet
Tecnologia dominante em LANs cabladas:
 primeira tecnologia LAN usada em larga escala
 mais simples e barata que Token Ring ou ATM
 a sua evolução permitiu manter débitos
competitivos: 10 Mbps – 10 Gbps

Esboço original da
ethernet de Robert
Metcalfe

Camada de Ligação de Dados 5-53

Ethernet
*
Cabo coaxial
grosso
Conector AUI

* Cabo coaxial
fino
Conectores BNC

RJ-45 AUI*
BNC*

Pares entrançados
Conectores 8P8C (RJ45)
* Já não se usam Camada de Ligação de Dados 5-54
Topologia em estrela
 topologia em barramento comum até meados dos ’90
 todos os nós num único domínio de colisão

 actualmente usa-se a topologia em estrela

 comutador (switch) no centro
 a ligação entre cada terminal e o comutador corre uma
instância separada do protocolo Ethernet (um só domínio de
difusão, mas múltiplos domínios de colisão)
 com concentradores (hubs) existia uma estrela a nível
físico mas um barramento a nível lógico

comutador

barramento: cabo coaxial estrela Camada de Ligação de Dados 5-55

Estrutura da trama ethernet
A interface de rede da estação transmissora
encapsula o datagrama IP numa trama ethernet

Preâmbulo:
 usado para sincronizar o relógio do receptor com o
do emissor
 7 bytes com o padrão de bits 10101010 seguidos de
um byte com o padrão 10101011
 o último bit, a 1, quebra o padrão, indicando que a trama
vai começar

Camada de Ligação de Dados 5-56

Estrutura da trama ethernet (cont.)
 Endereços: 6 bytes (48 bits) cada um
 se a interface de rede recebe uma trama com o seu MAC
ou com o MAC de difusão, passa-a à camada de rede
 caso contrário, ignora-a

 Tipo: indica o protocolo da camada acima (normal-

mente IP)
 CRC: verificado no receptor (se houver erro a trama
é ignorada)
 Como “trailer”, pois é calculado em hardware à medida que
a trama vai sendo transmitida

Camada de Ligação de Dados 5-57

Ethernet: não-fiável e sem conexões

 sem conexões: ausência de handshaking entre a

interface de rede transmissora e a receptora
 não-fiável: a interface receptora não envia confirma-
ções (nem positivas nem negativas) à transmissora
 fluxo de datagramas passado à camada de rede pode ter
“buracos” (perdas)
 informação nos “buracos” pode ser recuperada se se usar TCP
 caso contrário, a aplicação recebe dados com “buracos”
 Protocolo MAC da ethernet: CSMA/CD

Camada de Ligação de Dados 5-58

Ethernet: algoritmo CSMA/CD
m-ésima colisão
Novo datagrama
para esta trama
para transmitir
(máx. 10)
CSMA
Encapsula datagrama

Espera 512×k tempos

Canal livre? de bit

exponencial
Não

Backoff
Sim Escolhe aleatoriamente
Transmite trama k inteiro entre 0 e 2m-1

CD
Detectada Aborta transmissão e envia
colisão? Sim sinal de empastelamento
Não

Fim de transmissão
Camada de Ligação de Dados 5-59
CSMA/CD na Ethernet
Sinal de empastelamento: Backoff exponencial:
serve para o nó assegurar  Objectivo: adaptar as tenta-
que os outros nós a transmi- tivas de retransmissão à carga
tir se apercebem da colisão; estimada da rede
duração de 48 bits  com cargas elevadas, o
Tempo de bit: 0.1 μs na ether- tempo de espera é maior
net a 10 Mbps; para K=1023,  1ª colisão: escolher aleatori-
o tempo de espera é de amente K de {0,1}; o atraso é
cerca de 50 ms K·512 tempos de transmissão
de bit (K tempos de slot)
 2ª colisão: escolher aleatoria-
mente K de {0,1,2,3}; …
 10ª colisão e seguintes: esco-
lher K de {0,1,2,3,4,…,1023}; …

Camada de Ligação de Dados 5-60

Eficiência do CSMA/CD
 tprop = tempo máximo de propagação na LAN (entre os nós mais distantes)
 ttrans = tempo de transmissão de uma trama (de comprimento máximo)
1
eficiência =
1 + 5t prop /ttrans
 a eficiência tende para 1
 quando tprop tende para 0 (distâncias curtas)
 quando ttrans tende para ∞ (tramas longas)
ttrans

2·tprop CSMA torna impossível haver colisão

Pode haver colisão

 desempenho melhor que o do ALOHA, simples, barato e descentralizado!

 Por alguma razão a ethernet se tornou tão popular...
Camada de Ligação de Dados 5-61
Normas Ethernet 802.3: Camadas de Ligação de
Dados e Física
 Muitas normas Ethernet diferentes
 em comum: protocolo MAC e formato da trama
 velocidades diferentes: 2 Mbps, 10 Mbps, 100 Mbps,
1Gbps, 10Gbps (40Gbps e 100Gbps ainda raras)
 diferentes meios de propagação: coaxial, par
entrançado, fibra óptica

protocolo MAC e
aplicação formato das tramas
transporte
rede 100BASE-TX 100BASE-T2 100BASE-FX
lig. dados 100BASE-T4 100BASE-SX 100BASE-BX
física

camada física em camada física em

cobre (par entrançado) fibra óptica
Camada de Ligação de Dados 5-63
Camada de Ligação de Dados
 5.1 Introdução e Serviços
 5.2 Detecção e correcção de erros
 5.3 Protocolos de acesso múltiplo
 5.4 Endereçamento
 5.5 Ethernet
 5.6 Comutadores
 5.7 Redes sem fios

Camada de Ligação de Dados 5-64

Concentradores (Hubs)
… repetidores “estúpidos” que operam na camada física:
 os bits que entram por uma ligação são enviados para
todas as outras e ao mesmo débito
 todos os nós ligados ao hub podem colidir uns com os
outros (domínio de colisão): barramento a nível lógico
 sem bufferização de tramas
 o hub não implementa o CSMA/CD, são as interfaces
de rede dos nós que detectam as colisões

par entrançado

hub

Camada de Ligação de Dados 5-65

Comutadores (Switches)
 operam na camada de ligação de dados
 mais “inteligentes” que os concentradores, têm um
papel activo
 armazenam e reenviam tramas Ethernet
 examinam os endereços MAC das tramas e reenviam-nas
selectivamente para uma ou mais ligações de saída
 usam o CSMA/CD para aceder a cada segmento (ligação)*
 apenas um domínio de difusão (uma trama de difusão é
enviada para todos os segmentos)
 múltiplos domínios de colisão (um por porta física)
 transparente
 os nós não se apercebem da presença de comutadores

 plug-and-play, auto-aprendizagem
 os comutadores não necessitam de ser configurados
Camada de Ligação de Dados 5-66
Comutadores permitem múltiplas
transmissões em simultâneo
A

 nós têm ligações dedicadas C’ B

ao comutador
 comutadores bufferizam 1 2
tramas 6 3
4
 protocolo Ethernet usado 5
em cada ligação, sem C
colisões e full duplex
 cada ligação é um domínio de B’
colisão independente A’

 é possível o envio simultâ- comutador com 6 portas

neo A➔A’ e B➔B’ sem (1,2,3,4,5,6)
colisões
 impossível com concentrador
Camada de Ligação de Dados 5-67
 Tabela de comutação
A
 Q: como é que o comutador
sabe que chega a A’ pela por- C’ B
ta 4 e a B’ pela porta 5?
 R: o comutador mantém uma 1 2
6 3
tabela de comutação, onde 5 4
cada entrada contém:
 (endereço MAC do nó, porta, C
timestamp)
B’
 Semelhante a uma tabela de A’
encaminhamento… comutador com 6 portas
 Q: como se criam e mantêm as (1,2,3,4,5,6)
entradas nesta tabela?
Camada de Ligação de Dados 5-68
Auto-aprendizagem Origem: A
Destino: A’

A A A’
 o comutador aprende que
nós estão acessíveis por C’ B
cada interface (porta
física) 1 2
6 3
 quando recebe uma trama,
o comutador “aprende” a 5 4
localização do emissor:
segmento de entrada C
 armazena (emissor, porta)
B’
na tabela de comutação A’

End. MAC interface TTL

A 1 60 Tabela de comutação
(inicialmente vazia)

Camada de Ligação de Dados 5-69

Filtragem e reenvio de tramas
Quando é recebida uma trama:

1. regista a porta usada pelo nó emissor

2. indexa a tabela de comutação com o MAC de destino
3. se encontrar entrada para o destino
então {
se destino no segmento onde a trama foi recebida
então ignora a trama
senão reenvia a trama na porta indicada
}
senão inunda
reenvia a trama em todas as portas
excepto naquela por onde a recebeu
Camada de Ligação de Dados 5-70
Auto-aprendizagem e re- Origem: A
Destino: A’
envio de tramas: exemplo A A A’

C’ B

 destino da trama (A') 1 2

desconhecido:inundação A6A’ 3
5 4
 destino da trama (A)
conhecido: C
A’ A
reenvio selectivo
B’ A’

End. MAC interface TTL

A 1 60 Tabela de comutação
A’ 4 60 (inicialmente vazia)

Camada de Ligação de Dados 5-71

Interligação de comutadores
 é possível interligar vários comutadores

S4

S1
S3
A S2
F
D I
B C
G H
E

 Q: envio de A para G — como é que S1 sabe que uma

trama destinada a G deve ser enviada pela porta de S4?
 R: auto-aprendizagem, exactamente como no caso dum
comutador isolado!
 A tabela pode conter múltiplas entradas para a mesma in-
terface de saída
Camada de Ligação de Dados 5-72
Rede institucional simples

servidor de email
para a rede
externa
router servidor web

Sub-rede IP

Camada de Ligação de Dados 5-73

Comutadores vs. Routers
 ambos são dispositivos store-and-forward
 routers: operam na camada de rede (examinam cabeçalhos
da camada de rede)
 comutadores: operam na camada de ligação de dados

 os routers mantêm tabelas de encaminhamento e

implementam algoritmos de encaminhamento
 os comutadores mantêm tabelas de comutação e im-
plementam filtragem e algoritmos de aprendizagem

Terminal Bridge ou Router Terminal

Camada de Ligação de Dados 5-74
comutador
Camada de Ligação de Dados
 5.1 Introdução e Serviços
 5.2 Detecção e correcção de erros
 5.3 Protocolos de acesso múltiplo
 5.4 Endereçamento
 5.5 Ethernet
 5.6 Comutadores
 5.7 Redes sem fios

Camada de Ligação de Dados 5-75

Componentes duma rede sem fios

terminais
 PC portátil, PDA, tele-
fone VoIP, etc.
 correm aplicações
 podem ser fixos ou
móveis
infra-estrutura
de rede  sem fios ≠ mobilidade

Camada de Ligação de Dados 3-76

Componentes duma rede sem fios
estações-base
 tipicamente ligadas à
rede cablada
 responsáveis pelo
envio de pacotes
entre a rede cablada
e os nós sem fios na
infra-estrutura sua “área”
de rede
 torres da rede de
telemóvel, pontos
de acesso 802.11

Camada de Ligação de Dados 3-77

Componentes duma rede sem fios
ligação sem fios
 tipicamente usada para
ligar nós sem fios à
estação-base
 também pode ser
usada como backbone
infra-estrutura  acesso ao meio contro-
de rede lado por um protocolo
 várias taxas de trans-
missão, dependendo da
distância e do ruído

Camada de Ligação de Dados 3-78

 Características de algumas normas de
redes sem fios
1300 802.11ac
Taxa de transmissão (Mbps)

450 802.11n

54 802.11a,g 802.11a,g ponto-a-ponto

5-11 802.11b 4G: LTWE WIMAX

4 3G: UMTS/WCDMA-HSPDA, CDMA2000-1xEVDO

1 802.15

.384 2.5G: UMTS/WCDMA, CDMA2000

.056 2G: IS-95, CDMA, GSM

Interior Exterior Média Longa

10-30m 50-200m distância distância
Alcance 200m – 4 Km 5Km – 20 Km

Camada de Ligação de Dados 3-79

Características das ligações sem fios
Diferenças em relação a redes cabladas:

 menor intensidade de sinal: os sinais rádio ate-

nuam-se com o quadrado da distância
 interferência de outras fontes: frequências
utilizadas por outros dispositivos (e.g., telefo-
nes sem fios); interferência de outros
dispositivos (e.g., motores, fornos micro-ondas)
 propagação multi-caminho: reflexões do sinal em
objectos ou no solo chegam ao destino com
atrasos ligeiramente diferentes

Estas diferenças tornam a comunicação sem fios

(mesmo ponto-a-ponto) muito mais “difícil”
Camada de Ligação de Dados 3-80
Características das redes sem fios
A existência de múltiplos emissores cria problemas
adicionais (além do acesso múltiplo):

A B C
C

Intensidade Intensidade
B do sinal de A do sinal de C
A

space
Terminal escondido
 B e A ouvem-se mutuamente Atenuação do sinal
 B e C ouvem-se mutuamente  B e A ouvem-se mutuamente
 A e C não se ouvem ➔ não  B e C ouvem-se mutuamente
podem detectar interferência  A e C não conseguem detectar
em B interferência em B

Camada de Ligação de Dados 3-81

Redes sem fios IEEE 802.11 (WiFi)

 Modo infra-estruturado: os
Internet terminais sem fios comuni-
cam através do ponto de
acesso (estação-base)
 Modo ad-hoc: os terminais
comunicam directamente
entre si
AP  Basic Service Set (BSS)
(“célula”) contém:
BSS 1
 terminais sem fios
AP
 ponto de acesso (no
modo infra-estruturado)

BSS 2
Camada de Ligação de Dados 3-82
IEEE 802.11: acesso múltiplo
 CSMA – escutar o canal antes de transmitir
 Evitar colisão com trasmissão de outro nó em curso

 Sem detecção de colisões

 Muito difícil receber (para detectar colisões) enquanto se
transmite dada a enorme diferença de intensidade de sinal
 Nalguns casos, seria impossível de todo (terminal escondido,
sinal insuficiente para recepção)
 CSMA/CA(Collision Avoidance): evitar colisões

A B C
C

Intensidade Intensidade
B do sinal de A do sinal de C
A

Camada de Ligação de Dados 3-83

Protocolo MAC 802.11 — CSMA/CA
Emissor 802.11
1 se ouvir o canal desocupado por um período sender receiver
de tempo DIFS, transmite a trama inteira
2 se ouvir o canal ocupado, DIFS

inicia um tempo de espera aleatório

o temporizador conta apenas o tempo em data
que o canal está desocupado
quando acaba tempo de espera, transmite
se não receber ACK, aumenta exponenci- SIFS

almente o intervalo de escolha do ACK

tempo aleatório e volta ao passo 2
Receptor 802.11
- se receber correctamente a trama
envia ACK após tempo SIFS
Camada de Ligação de Dados 3-84
CSMA/CA: refinamento
ideia: permitir ao emissor “reservar” o canal antes de transmitir
uma trama longa
 emissor começa por transmitir uma pequena trama RTS (request
to send) à estação-base (BS) usando CSMA
 RTSs podem colidir, mas são pequenas
 a estação-base difunde CTS (clear to send) em resposta ao RTS
 CTS é ouvida por todos os nós, informando-os da reserva do
canal pela duração da transmissão da trama de dados
 o emissor transmite trama de dados
 os outros nós diferem as transmissões tal como se ouvissem
o canal ocupado

evitam-se colisões com a trama de dados

usando pequenas tramas de reserva!
Camada de Ligação de Dados 3-85
 Collision Avoidance: RTS e CTS
A B
AP

colisão na reserva

DADOS (A)
difere

tempo

Camada de Ligação de Dados 3-86

Canais no 802.11
Frequência central
Canal

Europa: canais 1 a 13
EUA: canais 1 a 11
Japão: canais 1 a 14

Camada de Ligação de Dados 5-87

Canais não sobrepostos (802.11)

Camada de Ligação de Dados 5-88

Capítulo 5: Resumo
 Princípios subjacentes aos serviços da camada de
ligação de dados:
 detecção e correcção de erros
 partilha dum canal de difusão — acesso múltiplo
 endereçamento na camada de ligação de dados
 Instanciação e implementação de algumas tecnolo-
gias da camada de ligação de dados
 Ethernet
 LANs comutadas
 Aspectos específicos das redes sem fios

Camada de Ligação de Dados 5-89