Capítulo 6 – A camada de enlace e as LANs

Redes de computadores e a Internet

Uma abordagem Top-Down

8a edição. Jim Kurose, Keith Ross. Pearson, 2020.

Esse material de aula foi desenvolvido a

partir dos slides disponibilizados, em
inglês, pelos autores do livro.

2024.2 – Redes de Computadores 1 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Camada enlace e as LANs: roteiro
●
introdução
●
detecção de erros, correção
●
múltiplos protocolos de acesso
●
LANs
➢
endereçamento, ARP
➢
Ethernet
➢
comuta
➢
VLANs
●
virtualização de links: MPLS
●
rede de data center
●
um dia na vida de uma solicitação da web
2024.2 – Redes de Computadores 2 Profa. Morganna Diniz - BSI/EIA/UNIRIO
 Introdução

2024.2 – Redes de Computadores 3 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Camada de enlace: introdução
Terminologia: mobile network
●
hosts, roteadores: nós national or global ISP

●
canais de comunicação que conectam nós
adjacentes ao longo do caminho de comunicação:
links
➢
com fio, sem fio
➢
LANs
●
pacote da camada 2: quadro, encapsula datagrama datacenter
network

Camada de enlace tem a responsabilidade

de transferir datagrama de um nó para um
enterprise
outro nó fisicamente adjacente através de network
um link

2024.2 – Redes de Computadores 4 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Camada de enlace: contexto

●
datagrama transferido por diferentes
protocolos de enlace em diferentes
enlaces:
➢
por exemplo, WiFi no primeiro link,
Ethernet no próximo link
●
cada protocolo de link fornece serviços
diferentes
➢
por exemplo, pode ou não fornecer
transferência confiável de dados
através de link

2024.2 – Redes de Computadores 5 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Analogia de transporte
Analogia do transporte:
●
viagem de Princeton a Lausana
➢
limusine: Princeton para JFK
Princeton
JFK
➢
avião: JFK para Genebra
➢
trem: Genebra para Lausanne
●
turista = datagrama
●
segmento de transporte = link de
comunicação
●
modo de transporte = protocolo da
camada de enlace
●
agente de viagens = algoritmo de
roteamento
Genebra Lausanne

2024.2 – Redes de Computadores 6 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Camada de enlace: serviços
●
enquadramento, acesso ao link:
➢
encapsular datagrama em quadro, adicionando …
cabeçalho, trailer …
➢
acesso ao canal se for mídia compartilhada Cable access
➢
Os endereços “MAC” nos cabeçalhos dos quadros
identificam a origem e o destino (diferente do
endereço IP!)
●
entrega confiável entre nós adjacentes
➢
já sabemos como fazer isso! cellular
➢
raramente usado em links com baixo erro de bit
Ethernet LANs
➢
links sem fio: altas taxas de erro
WiFi
P: por que a confiabilidade no nível do link e no final?
2024.2 – Redes de Computadores 7 Profa. Morganna Diniz - BSI/EIA/UNIRIO
Camada de enlace: serviços (mais)
●
controle de fluxo:
➢
ritmo entre nós adjacentes de envio e recebimento …
●
detecção de erro: …
Cable access
➢
erros causados ​pela atenuação do sinal, ruído.
➢
receptor detecta erros, retransmite sinais ou descarta
quadro
●
correção de erros:
➢
receptor identifica e corrige erro(s) de bit sem cellular
retransmissão
●
half-duplex e full-duplex: Ethernet LANs
➢
com half duplex, os nós em ambas as extremidades
do link podem transmitir, mas não ao mesmo tempo WiFi

2024.2 – Redes de Computadores 8 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Implementação da camada de enlace do
host
●
em cada host
●
camada de link implementada no chip ou
na placa de interface de rede (NIC)
aplicação
➢
implementa link, camada física transporte
rede
cpu memória
enlace
●
anexa-se aos barramentos do sistema do
host host bus
(e.g., PCI)
controladora
●
combinação de hardware, software, enlace
física
física
firmware

Interface de rede

NIC = Network Interface Card

2024.2 – Redes de Computadores 9 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Comunicação de interfaces
aplicação aplicação
transporte transporte
cpu memory memory CPU rede
datagrama rede
enlace enlace

controladora controladora
linkh datagrama enlace enlace
física física
física physical

lado de envio: lado receptor:

●
encapsula datagrama em quadro ●
procura erros, transferência
confiável de dados, controle de
●
adiciona bits de verificação de erros, fluxo, etc.
transferência confiável de dados,
controle de fluxo, etc. ●
extrai o datagrama, passa para a
camada superior no lado receptor
2024.2 – Redes de Computadores 10 Profa. Morganna Diniz - BSI/EIA/UNIRIO
 Detecção de erros,
correção

2024.2 – Redes de Computadores 11 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Detecção de erros
EDC: error detection and correction bits (redundância)
D: dados protegidos por verificação de erros, podem incluir campos de cabeçalho

A detecção de erros não é

datagram datagrama 100% confiável!
de outra forma ●
protocolo pode perder
todos
bits em D N alguns erros, mas é raro
OK? erro
d bits de dados
detectado ●
campo EDC maior
produz melhor detecção
D EDC D’ EDC’
e correção
link sujeito a erros de bit

2024.2 – Redes de Computadores 12 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Verificação de paridade
Pode detectar e corrigir erros (sem
paridade de bit único: retransmissão!)
 detect single bit errors
●
paridade bidimensional: detecta e
corrige erros de bit único
0111000110101011 1 paridade da linha
d bits de d1,1 ... d1,j d1,j+1
dados d2,1 ... d2,j d2,j+1
bit de paridade
... ... ... ...
Paridade par/ímpar: defina o bit de paridade di,1 ... di,j di,j+1
para que haja um número par/ímpar de 1’s paridade
da coluna
di+1,1 ... di+1,j di+1,j+1
No receptor: calcula paridade de d bits
recebidos e compara com o bit de sem erros: 1 0 1 0 1 1 Um único 10101 1
erro de bit erro de
paridade recebido – se for diferente, 11110 0 10110 0 paridade
detectado e
erro detectado 01110 1 corrigido: 01110 1
00101 0 00101 0
erro de
paridade

2024.2 – Redes de Computadores 13 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Verificação de paridade: exemplo

Suponha que a carga útil de um pacote consista em 10 valores de oito bits. Assuma
paridade par. Calcule os bits de paridade bidimensionais para as 16 colunas. Combine
os bits em uma string.

2024.2 – Redes de Computadores 14 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Verificação de paridade: exemplo

Suponha que a carga útil de um pacote consista em 10 valores de oito bits. Assuma
paridade par. Indique a linha e a coluna com o bit invertido. É possível detectar e
corrigir as inversões de bits neste caso?

2024.2 – Redes de Computadores 15 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Verificação de paridade

Confira os exercícios interativos online para mais exemplos:

http://gaia.cs.umass.edu/kurose_ross/interactive
“Error Detection and Correction: Two Dimensional Parity”

2024.2 – Redes de Computadores 16 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Soma de verificação (checksum) da Internet
Objetivo: detectar erros (ou seja, bits invertidos) no segmento transmitido
Remetente: Receptor:
●
tratar o conteúdo do segmento UDP ●
calcular soma de verificação do segmento
(incluindo campos de cabeçalho UDP recebido
e endereços IP) como uma sequência
de números inteiros de 16 bits
●
verifique se a soma de verificação
calculada é igual ao valor do campo de
●
soma de verificação: adição (soma do soma de verificação:
complemento de um) do conteúdo do
segmento
➢
diferente - erro detectado
●
valor da soma de verificação
➢
igual - nenhum erro detectado. Mas
colocado no campo de soma de talvez erros mesmo assim?
verificação UDP
2024.2 – Redes de Computadores 17 Profa. Morganna Diniz - BSI/EIA/UNIRIO
Cyclic Redundancy Check (CRC)
 codificação de detecção de erros mais poderosa
 D: bits de dados
 G: padrão de bits (gerador), de r+1 bits (dados, especificados no padrão CRC)

r CRC bits
d data bits
D R bits para enviar

remetente: calcula r bits CRC, R, tais que <D,R> exatamente divisível por G (mod 2)
●
receptor conhece G, divide <D,R> por G. Se resto diferente de zero: erro detectado!
●
pode detectar todos os erros de rajada menores que r+1 bits
●
amplamente utilizado na prática (Ethernet, 802.11 WiFi)

2024.2 – Redes de Computadores 18 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Cyclic Redundancy Check (CRC): exemplo
Suponha que o gerador de 4 bits (G) seja 1001, que a carga útil de dados (D) seja 10011110 e
que r = 3.
Transmissor
1) D . 23 2) D . 23 / G 3) Transmite

10011110 111
D R

Receptor
1) Valor recebido / G
Sem erro!!!

2024.2 – Redes de Computadores 19 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Cyclic Redundancy Check (CRC): exemplo
Considere o algoritmo Cyclic Redundancy Check (CRC) discutido na Seção 6.2.3
do texto. Suponha que o gerador de 4 bits (G) seja 1001, que a carga útil de dados
(D) seja 10011100 e que r = 3. Quais são os bits CRC (R) associados à carga útil
de dados D, dado que r = 3?

Transmissor 10011100101

Receptor

Fonte: http://www.ee.unb.ca/cgi-bin/tervo/calc.pl?num=10011100000&den=1001&f=d&e=1&m=1

2024.2 – Redes de Computadores 20 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Cyclic Redundancy Check (CRC)

Confira os exercícios interativos online para mais exemplos:

http://gaia.cs.umass.edu/kurose_ross/interactive
“Error Detection and Correction: Cyclic Redundancy Check”

Operações com números binários:

http://www.ee.unb.ca/cgi-bin/tervo/calc.pl

2024.2 – Redes de Computadores 21 Profa. Morganna Diniz - BSI/EIA/UNIRIO

 Protocolos de
acesso múltiplo

2024.2 – Redes de Computadores 22 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Enlaces e protocolos de acesso múltiplo
Dois tipos de “links”:
●
ponto a ponto
➢
link ponto a ponto entre switch Ethernet, host
➢
PPP para acesso discado
●
transmissão (wire ou meio compartilhado)
➢
Ethernet da velha escola
➢
LAN sem fio 802.11, 4G/4G. satélite

fio compartilhado (e.g., rádio compartilhado: rádio compartilhado: humanos em uma festa
Ethernet cabeada) rádio compartilhado:
4G/5G WiFi (compartilham ar, acústica, etc)
satélite
2024.2 – Redes de Computadores 23 Profa. Morganna Diniz - BSI/EIA/UNIRIO
Protocolos de acesso múltiplo
●
único canal de transmissão compartilhado
●
duas ou mais transmissões simultâneas por nós: interferência
➢
colisão se o nó receber dois ou mais sinais ao mesmo tempo

Protocolo de acesso múltiplo

 algoritmo distribuído que determina como os nós compartilham o canal, ou
seja, determina quando o nó pode transmitir
 a comunicação sobre compartilhamento de canal deve usar o próprio canal!

2024.2 – Redes de Computadores 24 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Um protocolo ideal de acesso múltiplo
dado: canal de acesso múltiplo (MAC) de taxa R bps
desejos:
1. quando um nó deseja transmitir, ele pode enviar à taxa R.
2. quando M nós desejam transmitir, cada um pode enviar a uma taxa média R/M
3. totalmente descentralizado:
●
nenhum nó especial para coordenar as transmissões
●
sem sincronização de relógios, slots
4. simples

2024.2 – Redes de Computadores 25 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Protocolos MAC: taxonomia
Três classes amplas:
●
particionamento de canal
➢
dividir o canal em “pedaços” menores (intervalos de tempo, frequência,
código)
➢
alocar peça ao nó para uso exclusivo
●
acesso aleatório
➢
canal não dividido, permite colisões
➢
“recuperar-se” de colisões
●
“revezando”
➢
os nós se revezam, mas os nós com mais para enviar podem demorar mais

2024.2 – Redes de Computadores 26 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Protocolos MAC de particionamento de
canal: TDMA
TDMA: acesso múltiplo por divisão de tempo
●
acesso ao canal em “rodadas”
●
cada estação recebe um slot de comprimento fixo (comprimento = tempo de transmissão
do pacote) em cada rodada
●
slots não utilizados ficam ociosos
●
exemplo: LAN de 6 estações, 1, 3, 4 têm pacotes para enviar, slots 2 ,5 , 6 ociosos

6-slot 6-slot
frame frame
1 3 4 1 3 4

2024.2 – Redes de Computadores 27 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Protocolos MAC de particionamento de
canal: FDMA
FDMA: acesso múltiplo por divisão de frequência
●
espectro de canal dividido em bandas de frequência
●
cada estação atribuída banda de frequência fixa
●
o tempo de transmissão não utilizado nas bandas de frequência fica ocioso
●
exemplo: LAN de 6 estações, 1, 3, 4 tem pacote para enviar, bandas de frequência 2,
5, 6 inativas
tempo

Bandas de frequência
Cabo FDM

2024.2 – Redes de Computadores 28 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Protocolos de acesso aleatório
●
quando o nó tem pacote para enviar
➢
transmitir na taxa de dados de canal total R
➢
sem coordenação a priori entre nós
●
dois ou mais nós transmissores: “colisão”
●
protocolo de acesso aleatório especifica:
➢
como detectar colisões
➢
como se recuperar de colisões (por exemplo, por meio de retransmissões atrasadas)
●
exemplos de protocolos MAC de acesso aleatório:
➢
ALOHA, slotted ALOHA
➢
CSMA, CSMA/CD, CSMA/CA

2024.2 – Redes de Computadores 29 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Slotted ALOHA
t0 t0+1

Premissas: Operação:
●
todos os quadros do mesmo tamanho ●
quando o nó obtém um novo
●
tempo dividido em slots de tamanhos quadro, transmite no próximo slot
iguais (tempo para transmitir 1 quadro) ➢
se não houver colisão: o nó pode
●
nós começam a transmitir apenas o enviar um novo quadro no
início do slot próximo slot
●
nós são sincronizados
➢
se colisão: o nó retransmite o
quadro em cada slot subsequente
●
se 2 ou mais nós transmitem no slot, com probabilidade p até sucesso
todos os nós detectam colisão

2024.2 – Redes de Computadores 30 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Slotted ALOHA
node 1 1 1 1 1

node 2 2 2 2 C: collision
S: success
node 3 3 3 3
E: empty
C E C S E C E S S

Prós: Contras:
●
único nó ativo pode transmitir ●
colisões, desperdiçando slots
continuamente na taxa total do canal ●
slots ociosos
●
altamente descentralizado: apenas slots ●
nós podem ser capazes de detectar colisão
em nós precisam estar sincronizados
em menos de tempo para transmitir
●
simples pacotes
●
sincronização de relógio
2024.2 – Redes de Computadores 31 Profa. Morganna Diniz - BSI/EIA/UNIRIO
Slotted ALOHA: eficiência

eficiência: fração de longo prazo de slots bem-sucedidos (muitos nós, todos com
muitos quadros para enviar)
●
suponha: N nós com muitos quadros para enviar, cada um transmitindo no slot com
probabilidade p
➢
problema de que determinado nó tenha sucesso em um slot = p(1-p)N-1
➢
probabilidade de que qualquer nó tenha sucesso = Np(1-p)N-1
●
na melhor das hipóteses: transmissões úteis do canal correspondem a 37% do tempo!

2024.2 – Redes de Computadores 32 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Slotted ALOHA: exemplo
Suponha que existam 4 nós ativos, cada um com um suprimento infinito de quadros que
desejam transmitir, e esses quadros tenham um tamanho constante de L bits. Se dois ou
mais quadros colidirem, todos os nós detectarão a colisão.

1. Dada uma probabilidade de transmissão p = 0,2, qual é a eficiência máxima?

N * p * (1 - p)(N - 1) = 4 * 0.2 * (1 - 0.2)(4 - 1) = 0.41 = 41%

2. Dada uma probabilidade de transmissão p = 0,55, qual é a eficiência máxima?

N * p * (1 - p)(N - 1) = 4 * 0.55 * (1 - 0.55)(4 - 1) = 0.2 = 20%

2024.2 – Redes de Computadores 33 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Slotted ALOHA: exemplo
Considere a chegada de 7 mensagens para transmissão em diferentes nós sem fio de
acesso múltiplo em horários t = <0.5, 1.8, 2.6, 3.1, 4.4, 4.5, 4.8> e cada transmissão
requer exatamente uma unidade de tempo.

1. Suponha que todos os nós usem o protocolo Slotted Aloha. Para cada mensagem,
indique a hora em que cada transmissão começa.

1, 2, 3, 4, 5, 5, 5

2. Quais mensagens são transmitidas com sucesso?

1, 2, 3, 4
2024.2 – Redes de Computadores 34 Profa. Morganna Diniz - BSI/EIA/UNIRIO
Pure ALOHA
●
Aloha sem slots: mais simples, sem sincronização
➢
quando o primeiro quadro chegar: transmita imediatamente
●
a probabilidade de colisão aumenta sem sincronização:
➢
quadro enviado em t0 colide com outros quadros enviados em [t0-1, t0+1]

irá se sobrepor irá se sobrepor

com início do com fim do
i-ésimo quadro i-ésimo quadro

t0 - 1 t0 t0 + 1

2024.2 – Redes de Computadores 35 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Pure ALOHA
●
Suponha que existem N nós com muitos quadros para enviar e que o nó X começa a
transmissão em um determinado momento.
➢
A probabilidade de que os outros nós não estejam transmitindo quando o nó X começa
a sua transmissão é (1-p)N-1 → tempo anterior
➢
A probabilidade de que os outros nós não iniciem a transmissão durante a transmissão
do nó X é (1-p)N-1 → tempo atual
➢
A probabilidade do nó X conseguir terminar a transmissão com sucesso é p(1-p)2(N-1)
➢
A probabilidade de um nó qualquer conseguir terminar a transmissão com sucesso é
N *(1-p)N-1 * (1-p)N-1 = N * p * (1-p)2(N-1)

Eficiência do pure Aloha: 18%!

2024.2 – Redes de Computadores 36 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Pure ALOHA: exemplo
Suponha que existam 2 nós ativos, cada um com um suprimento infinito de quadros que
desejam transmitir, e esses quadros tenham um tamanho constante de L bits. Se dois ou
mais quadros colidirem, todos os nós detectarão a colisão.

1. Dada uma probabilidade de transmissão p = 0,4, qual é a eficiência máxima?

N * p * (1 - p)2(N - 1) = 2 * 0.4 * (1 - 0.4)2(2 - 1) = 0.29 = 29%

2. Dada uma probabilidade de transmissão p = 0,68, qual é a eficiência máxima?

N * p * (1 - p)2(N - 1) = 2 * 0.68 * (1 - 0.68)2(2 - 1) = 0.14 = 14%

2024.2 – Redes de Computadores 37 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Pure ALOHA: exemplo
Considere a chegada de 11 mensagens para transmissão em diferentes nós sem fio de
acesso múltiplo em horários t = <0.1, 0.2, 0.3, 1.3, 1.6, 2.3, 2.9, 3.3, 3.4, 3.7, 4.3> e
cada transmissão requer exatamente uma unidade de tempo.

1. Suponha que todos os nós estejam implementando o protocolo Aloha. Para cada
mensagem, indique a hora em que cada transmissão começa.

0.1, 0.2, 0.3, 1.3, 1.6, 2.3, 2.9, 3.3, 3.4, 3.7, 4.3

2. Quais mensagens são transmitidas com sucesso?

Nenhuma

2024.2 – Redes de Computadores 38 Profa. Morganna Diniz - BSI/EIA/UNIRIO

CSMA (carrier sense multiple access)
CSMA simples: ouça antes de transmitir:
●
se o canal for detectado como inativo: transmite o quadro inteiro
●
se o canal for detectado como ocupado: adiar a transmissão
Analogia humana: não interrompa os outros!

CSMA/CD: CSMA com detecção de colisão

●
colisões detectadas em pouco tempo
●
colisões de transmissões abortadas, reduzindo o desperdício de canal
●
detecção de colisão fácil com fio, difícil com sem fio
Analogia humana: o conversador educado

2024.2 – Redes de Computadores 39 Profa. Morganna Diniz - BSI/EIA/UNIRIO

CSMA: exemplo
Considere a chegada de 8 mensagens para transmissão em diferentes nós sem fio de
acesso múltiplo em horários t = <0.1, 1.2, 2.1, 2.8, 3.1, 3.5, 3.9, 4.4> e cada transmissão
requer exatamente uma unidade de tempo.

1. Suponha que todos os nós usem CSMA sem detecção de colisão. Suponha que o tempo
desde o início da transmissão de uma mensagem até que ela comece a ser recebida em
outros nós seja de 0.4 unidades de tempo. Para cada mensagem, indique o tempo em que
cada transmissão de mensagem começa, ou indicar que a transmissão da mensagem não
começa devido a um canal que é detectado como ocupado quando essa mensagem chega.
0.1, ocupado, 2.1, ocupado, ocupado, 3.5, ocupado, ocupado
2. Quais mensagens foram transmitidas com sucesso? Escreva sua resposta como uma lista
separada por vírgulas sem espaços usando os números das mensagens
1, 3, 6
2024.2 – Redes de Computadores 40 Profa. Morganna Diniz - BSI/EIA/UNIRIO
CSMA/CD: exemplo
Considere a chegada de 10 mensagens para transmissão em diferentes nós sem fio de acesso
múltiplo em horários t = <0.3, 0.7, 0.8, 1.2, 2.2, 2.7, 3.5, 3.7, 4.4, 4.6> e cada transmissão
requer exatamente uma unidade de tempo.

1. Suponha que todos os nós usem CSMA/CD. Suponha que o tempo desde o início da
transmissão de uma mensagem até que ela comece a ser recebida em outros nós seja de 0,4
unidades de tempo e suponha que um nó possa interromper a transmissão instantaneamente
quando uma colisão de mensagem for detectada. Para cada mensagem, indique o tempo em
que cada transmissão de mensagem começa ou indique que a transmissão da mensagem não
começa.
0.3, ocupado, ocupado, ocupado, 2.2, ocupado, ocupado, 3.7, ocupado, ocupado
2. Quais mensagens foram transmitidas com sucesso?
1, 5, 8
2024.2 – Redes de Computadores 41 Profa. Morganna Diniz - BSI/EIA/UNIRIO
Ethernet CSMA/CD
1) Adaptador recebe datagrama da camada de rede e cria um quadro
2) Se o adaptador percebe que o canal está ocioso, começa a transmitir o quadro.
Se percebe que o canal está ocupado, espera que o canal fique livre e transmite
3) Se o adaptador transmitir todo o quadro sem detectar outra transmissão, o
adaptador concluiu a operação com o quadro
- Não houve colisão
4) Se o adaptador detectar outra transmissão enquanto estiver transmitindo, aborta
e envia sinal de reforço de colisão
5) Após interromper a transmissão, o adaptador retransmite o quadro após um
tempo aleatório

2024.2 – Redes de Computadores 42 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Protocolos MAC “revezados”
Protocolos MAC de particionamento de canal
●
compartilhe o canal de forma eficiente e justa em alta carga
●
ineficiente em carga baixa: atraso no acesso ao canal, largura de banda
1/N alocada mesmo que apenas 1 nó ativo!

Protocolos MAC de acesso aleatório

●
eficiente em baixa carga: um único nó pode utilizar totalmente o canal
●
carga alta: sobrecarga de colisão

Protocolos de “revezamento”
●
procure o melhor dos dois mundos!

2024.2 – Redes de Computadores 43 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Protocolos MAC “revezados”
polling:
●
controlador centralizado “convida” outros
nós a transmitirem por sua vez
data
●
normalmente usado com dispositivos poll

“burros”
controlador
●
preocupações: data centralizado
➢
sobrecarga de votação
➢
latência
➢
ponto único de falha (mestre) dispositivos cliente

●
Bluetooth usa pesquisa

2024.2 – Redes de Computadores 44 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Protocolos MAC “revezados”
T
Passagem de token:
●
mensagem de token de controle passada
explicitamente de um nó para o próximo,
sequencialmente (nada para
●
transmitir enquanto segura o token enviar)
T
●
preocupações:
➢
sobrecarga de token
➢
latência
➢
ponto único de falha (token)

data

2024.2 – Redes de Computadores 45 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Resumo dos protocolos MAC
●
particionamento de canal, por tempo, frequência ou código
➢
Divisão de Tempo, Divisão de Frequência
●
acesso aleatório (dinâmico)
➢
ALOHA, S-ALOHA, CSMA, CSMA/CD
➢
detecção de portadora: fácil em algumas tecnologias (com fio),
difícil em outras (sem fio)
➢
CSMA/CD usado em Ethernet
➢
CSMA/CA usado em 802.11
●
revezando
➢
votação do site central, passagem de token
➢
Bluetooth, token ring

2024.2 – Redes de Computadores 46 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Acesso Aleatório

Confira os exercícios interativos online para mais exemplos:

http://gaia.cs.umass.edu/kurose_ross/interactive
“Random Access Protocols: Aloha”
“Random Access Protocols: Collisions”

2024.2 – Redes de Computadores 47 Profa. Morganna Diniz - BSI/EIA/UNIRIO

 LANs
●
endereçamento, ARP

2024.2 – Redes de Computadores 48 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Endereços MAC
●
Endereço IP de 32 bits:
➢
endereço da camada de rede para interface
➢
usado para encaminhamento da camada 3 (camada de rede)
➢
por exemplo: 128.119.40.136
●
Endereço MAC (ou LAN ou físico ou Ethernet):
➢
função: usada “localmente” para obter quadros de uma interface para outra interface
conectada fisicamente (mesma sub-rede, no sentido de endereçamento IP)
➢
Endereço MAC de 48 bits (para a maioria das LANs) gravado na ROM da NIC, às
vezes também configurável por software
●
Por exemplo: 1A-2F-BB-76-09-AD
notação hexadecimal (base 16)
(cada “numeral” representa 4 bits)

2024.2 – Redes de Computadores 49 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Endereços MAC
Cada interface na LAN
●
tem endereço MAC exclusivo de 48 bits
●
tem um endereço IP localmente exclusivo de 32 bits (como vimos)

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

LAN
(cabeada ou
sem fio)
71-65-F7-2B-08-53 137.196.7/24 58-23-D7-FA-20-B0
137.196.7.23 137.196.7.14

0C-C4-11-6F-E3-98
137.196.7.88

2024.2 – Redes de Computadores 50 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Endereços MAC
●
Alocação de endereço MAC administrada pelo IEEE
●
fabricante compra parte do espaço de endereço MAC (para garantir exclusividade)
●
analogia:
➢
Endereço MAC: como número de CPF
➢
Endereço IP: como endereço postal
●
Endereço MAC plano: portabilidade
➢
pode mover a interface de uma LAN para outra
➢
recuperar endereço IP não portátil: depende da sub-rede IP à qual o nó está
conectado

2024.2 – Redes de Computadores 51 Profa. Morganna Diniz - BSI/EIA/UNIRIO

ARP: address resolution protocol
Pergunta: como determinar o endereço MAC da interface,
conhecendo o seu endereço IP?
Tabela ARP: cada nó IP (host, roteador) na
ARP LAN possui tabela
137.196.7.78
●
Mapeamentos de endereços IP/MAC para
ARP
1A-2F-BB-76-09-AD alguns nós da LAN:
ARP
<endereço IP; Endereço MAC; TTL>
LAN
71-65-F7-2B-08-53 58-23-D7-FA-20-B0
●
TTL (Time To Live): tempo após o qual o
137.196.7.23 137.196.7.14 mapeamento de endereço será esquecido
ARP 0C-C4-11-6F-E3-98 (normalmente 20 minutos)
137.196.7.88

2024.2 – Redes de Computadores 52 Profa. Morganna Diniz - BSI/EIA/UNIRIO

ARP em ação
Exemplo: A deseja enviar datagrama para B
• O endereço MAC de B não está na tabela ARP table de A, assim A usa ARP
para descobrir o endereço MAC de B

A transmite consulta ARP, contendo o endereço IP de B

Ethernet frame (envia para FF-FF-FF-FF-FF-FF)
1 • endereço MAC de destino = FF-FF-FF-FF-FF-FF
• todos os nós na LAN recebem consulta ARP C Source MAC: 71-65-F7-2B-08-53
Source IP: 137.196.7.23
Tabela ARP em A Target IP address: 137.196.7.14
…
IP addr MAC addr TTL
TTL
A B
1
71-65-F7-2B-08-53 58-23-D7-FA-20-B0
137.196.7.23 137.196.7.14

D
2024.2 – Redes de Computadores 53 Profa. Morganna Diniz - BSI/EIA/UNIRIO
ARP em ação
Exemplo: A deseja enviar datagrama para B
• O endereço MAC de B não está na tabela ARP table de A, assim A usa ARP
para descobrir o endereço MAC de B
Mensagem ARP no quadro Ethernet
(envia para 71-65-F7-2B-08-53)
C Target IP address: 137.196.7.14
Target MAC address:
Tabela ARP em A 58-23-D7-FA-20-B0
…
IP addr MAC addr TTL
TTL
A B
2
71-65-F7-2B-08-53 58-23-D7-FA-20-B0
137.196.7.23 137.196.7.14

2 B responde a A com resposta

ARP, fornecendo seu endereço
D MAC
2024.2 – Redes de Computadores 54 Profa. Morganna Diniz - BSI/EIA/UNIRIO
ARP em ação
Exemplo: A deseja enviar datagrama para B
• O endereço MAC de B não está na tabela ARP table de A, assim A usa ARP
para descobrir o endereço MAC de B

C
Tabela ARP em A
IP addr MAC addr TTL
TTL
137.196. 58-23-D7-FA-20-B0 500
A B
7.14

71-65-F7-2B-08-53 58-23-D7-FA-20-B0
137.196.7.23 137.196.7.14

3 A recebe a resposta de B,
adiciona a entrada B em sua
tabela ARP local D
2024.2 – Redes de Computadores 55 Profa. Morganna Diniz - BSI/EIA/UNIRIO
Roteamento para outra sub-rede:
endereçamento
Passo a passo: enviando um datagrama de A para B via R
●
foco no endereçamento – nos níveis IP (datagrama) e camada MAC (quadro)
●
Assuma que:
➢
A conhece o endereço IP de B
➢
A conhece o endereço IP do roteador de primeiro salto, R (como?)
➢
A conhece o endereço MAC de R (como?)
A B
R
111.111.111.111
74-29-9C-E8-FF-55 222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112 111.111.111.110
CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 222.222.222.221
88-B2-2F-54-1A-0F

2024.2 – Redes de Computadores 56 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Roteamento para outra sub-rede:
endereçamento
●
A cria datagrama IP com IP origem A, destino B MAC src: 74-29-9C-E8-FF-55
MAC dest: E6-E9-00-17-BB-4B
IP src: 111.111.111.111
●
A cria um quadro de camada de enlace contendo IP dest: 222.222.222.222

datagrama IP A para B IP
Eth
➢
O endereço MAC de R é o destino do quadro Física

A B
R
111.111.111.111
74-29-9C-E8-FF-55 222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112 111.111.111.110
CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 222.222.222.221
88-B2-2F-54-1A-0F

2024.2 – Redes de Computadores 57 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Roteamento para outra sub-rede:
endereçamento
●
quadro enviado de A para R MAC src: 74-29-9C-E8-FF-55
MAC dest: E6-E9-00-17-BB-4B
IP src: 111.111.111.111 IP src: 111.111.111.111
●
quadro recebido em R, datagrama IP dest: 222.222.222.222 IP dest: 222.222.222.222

removido, passado para IP IP

Eth IP
Física Eth
Física

A B
R
111.111.111.111
74-29-9C-E8-FF-55 222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112 111.111.111.110
CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 222.222.222.221
88-B2-2F-54-1A-0F

2024.2 – Redes de Computadores 58 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Roteamento para outra sub-rede:
endereçamento
●
R determina a interface de saída, passa o datagrama com o IP origem A e destino B para a
camada de enlace
●
R cria um quadro de camada de enlace contendo datagrama IP A para B. Endereço de destino
do quadro: endereço MAC de B MAC src: 1A-23-F9-CD-06-9B
MAC dest: 49-BD-D2-C7-56-2A
IP src: 111.111.111.111
IP dest: 222.222.222.222

IP
Eth
Física
A B
R
111.111.111.111
74-29-9C-E8-FF-55 222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112 111.111.111.110
CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 222.222.222.221
88-B2-2F-54-1A-0F

2024.2 – Redes de Computadores 59 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Roteamento para outra sub-rede:
endereçamento
●
R determina a interface de saída, passa o datagrama com o IP origem A e destino B para a
camada de enlace
●
R cria um quadro de camada de enlace contendo datagrama IP A para B. Endereço de destino
do quadro: endereço MAC de B MAC src: 1A-23-F9-CD-06-9B
MAC dest: 49-BD-D2-C7-56-2A
●
transmite quadro da camada de enlace IP src: 111.111.111.111
IP dest: 222.222.222.222
IP
IP Eth
Eth Física
Física
A B
R
111.111.111.111
74-29-9C-E8-FF-55 222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112 111.111.111.110
CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 222.222.222.221
88-B2-2F-54-1A-0F

2024.2 – Redes de Computadores 60 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Roteamento para outra sub-rede:
endereçamento
●
B recebe o quadro, extrai o destino do datagrama IP B
●
B passa o datagrama pela pilha de protocolos para IP
IP src: 111.111.111.111
IP dest: 222.222.222.222

IP
IP Eth
Eth Phy
Física
A B
R
111.111.111.111
74-29-9C-E8-FF-55 222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.220
1A-23-F9-CD-06-9B
111.111.111.112 111.111.111.110
CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B 222.222.222.221
88-B2-2F-54-1A-0F

2024.2 – Redes de Computadores 61 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Endereçamento e encaminhamento

2024.2 – Redes de Computadores 62 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Endereçamento e encaminhamento
Considere um datagrama IP sendo enviado do nó D para o nó A.

1. Qual é o endereço MAC de origem no ponto 5?

78-DD-22-72-DB-F4

2. Qual é o endereço MAC de destino no ponto 5?

DA-CC-DE-DC-9F-8D
3. Qual é o endereço IP de origem no ponto 5?
128.119.75.21
4. Qual é o endereço IP de destino no ponto 5?
128.119.191.191
5. Os endereços MAC de origem e destino mudam no ponto 4?
Não, os datagramas podem ser enviados pela sub-rede através da camada de
enlace de uma só vez.
2024.2 – Redes de Computadores 63 Profa. Morganna Diniz - BSI/EIA/UNIRIO
Endereçamento e encaminhamento
6. Os endereços MAC de origem e destino mudam no ponto 2?
Sim, o datagrama está passando por um roteador, o que causa
uma mudança de sub-rede.

7. Qual é o endereço MAC de origem no ponto 2?

FF-5C-70-14-FA-B3

8. Qual é o endereço MAC de destino no ponto 2?

C3-84-50-C0-54-B2

9. Os endereços MAC de origem e destino mudam no ponto 1?

Não, os datagramas podem ser enviados pela sub-rede
através da camada de enlace de uma só vez.

2024.2 – Redes de Computadores 64 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Endereçamento e encaminhamento

Confira os exercícios interativos online para mais exemplos:

http://gaia.cs.umass.edu/kurose_ross/interactive
“Link Layer (and network layer) addressing, forwarding”

2024.2 – Redes de Computadores 65 Profa. Morganna Diniz - BSI/EIA/UNIRIO

 LANs
●
Ethernet

2024.2 – Redes de Computadores 66 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Ethernet
Tecnologia LAN com fio “dominante”:
●
primeira tecnologia LAN amplamente utilizada
●
mais simples, barato
●
acompanhou a corrida de velocidade: 10 Mbps – 400 Gbps
●
chip único, múltiplas velocidades (por exemplo, Broadcom BCM5761)

Esboço Ethernet de Metcalfe Bob Metcalfe: co-inventor da Ethernet,

Vencedor do Prêmio ACM Turing 2022

2024.2 – Redes de Computadores 67 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Ethernet: topologia física
bus: popular até meados dos anos 90
●
todos os nós no mesmo domínio de colisão (podem colidir entre si)
switched: prevalece hoje
●
switch ativo da camada de enlace 2 no centro
●
cada “spoke” executa (separado) um protocolo Ethernet (os nós não colidem entre si)

bus: cabo coaxial switched

2024.2 – Redes de Computadores 68 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Estrutura do quadro Ethernet
A interface de envio encapsula o datagrama IP (ou outro pacote de
protocolo da camada de rede) no quadro Ethernet

tipo
preamble dest. source data (payload) CRC
address address

tipo: indica protocolo de camada superior , principalmente IP, mas outros são
possíveis,

2024.2 – Redes de Computadores 69 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Ethernet: não confiável, sem conexão
●
sem conexão: sem handshake entre NICs de envio e recebimento
●
não confiável: o NIC receptor não envia ACKs ou NAKs para o NIC remetente
➢
dados em quadros descartados recuperados somente se o remetente inicial usar rdt de
camada superior (por exemplo, TCP), caso contrário, os dados descartados serão
perdidos
●
Protocolo MAC da Ethernet: CSMA/CD sem slot com backoff binário

O algoritmo de back-off é um mecanismo de

resolução de colisão usado em protocolos MAC
de acesso aleatório (CSMA/CD). Este
algoritmo é geralmente usado em Ethernet para
agendar retransmissões após colisões.

2024.2 – Redes de Computadores 70 Profa. Morganna Diniz - BSI/EIA/UNIRIO

 LANs
●
switches

2024.2 – Redes de Computadores 71 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Switch Ethernet
●
Switch é um dispositivo de camada de enlace: assume um papel ativo
➢
armazenar, encaminhar quadros Ethernet (ou outro tipo de)
➢
examinar o endereço MAC do quadro de entrada, encaminhar seletivamente o
quadro para um ou mais enlaces de saída quando o quadro for encaminhado no
segmento, usar CSMA/CD para acessar o segmento
●
transparente: hosts não sabem da presença de switches
●
plug-and-play, autoaprendizagem
➢
switches não precisam ser configurados

2024.2 – Redes de Computadores 72 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Switch: múltiplas transmissões simultâneas

●
hosts têm conexão direta e dedicada ao switch
●
comuta pacotes de buffer A
C’ B
●
Protocolo Ethernet usado em cada link de
entrada, então: 1 2
6
➢
sem colisões; duplex completo 3
5 4
➢
cada link é seu próprio domínio de colisão
B’ C
●
switching: A-para-A' e B-para-B' podem A’
transmitir simultaneamente, sem colisões
➢
mas A-para-A’ e C para A’ não podem acontecer switch com seis
simultaneamente interfaces (1,2,3,4,5,6)
➢

2024.2 –➢ Redes de Computadores 73 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Tabela de encaminhamento de switch

P: como o switch sabe que A’ pode ser

acessado pela interface 4, B’ pode ser acessado A
pela interface 5? C’ B
1 2
R: cada switch possui uma tabela de switches, 6
cada entrada: endereço MAC do host, interface 3
5 4
para acessar o host, carimbo de data/hora.
B’ C
P: como as entradas são criadas e mantidas na A’
tabela switch?
●
algo como um protocolo de roteamento?

2024.2 – Redes de Computadores 74 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Switch: autoaprendizagem
Source: A
Dest: A’

A A’
A
Switch aprende quais hosts podem ser C’
alcançados através de quais interfaces B
●
quando o quadro é recebido, o switch 1 2
6
“aprende” a localização do remetente: 3
segmento LAN de entrada 5 4
●
registra o par remetente/local na tabela B’ C
de switch A’
Tabela Switch
MAC addr interface TTL (inicialmente
A 1 60 vazia)

2024.2 – Redes de Computadores 75 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Autoaprendizagem, encaminhamento:
exemplo Source: A
Dest: A’

A A’
●
destino do quadro, A’, local A
desconhecido: C’ B
➢
broadcast 1 2
●
destino um local conhecido: 6A A’
3
5 4
➢
enviar seletivamente, para
apenas um link B’ C
A’ A A’

MAC addr interface TTL

A 1 60 Tabela Switch
A’ 4 60 (inicialmente
vazia)

2024.2 – Redes de Computadores 76 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Interconectando switches
Interruptores de autoaprendizagem podem ser conectados entre si:

S4

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

P: enviando de A para G - como S1 sabe encaminhar o quadro destinado a G via S4 e S3?

R: autoaprendizagem! (funciona exatamente da mesma forma que no caso de switch único!)

2024.2 – Redes de Computadores 77 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Switches X roteadores
aplicação
transporte
ambos são store-and-forward: datagrama rede
quadro enlace
●
roteadores: dispositivos da camada de rede
física quadro
(examine os cabeçalhos da camada de rede) enlace
●
switches: dispositivos da camada de enlace física
(examine os cabeçalhos da camada de enlace) switch

ambos têm tabelas de encaminhamento: rede datagrama

●
roteadores: tabelas de computação usando enlace quadro
algoritmos de roteamento, endereços IP física
●
switches: aprenda a tabela de encaminhamento aplicação
usando broadcast, aprendizagem, endereços transporte
MAC rede
enlace
física

2024.2 – Redes de Computadores 78 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Switches: exemplo
Considere uma LAN composta por 10 computadores conectados por dois switches
Ethernet de autoaprendizagem. Em t = 0, as entradas da tabela de switches para ambos os
switches estão vazias. Em t = 1, 2, 3 e 4, um nó de origem envia para um nó de destino
conforme mostrado abaixo, e o destino responde imediatamente (bem antes do próximo
intervalo de tempo).

Suponha que ocorram as seguintes

transmissões (as transmissões em
resposta ocorrem, mas não são
mostradas na lista abaixo):
t=1: E→ B
t=2: K→I Tabela 2 Tabela 1
t=3: J → I
t=4: A → L

2024.2 – Redes de Computadores 79 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Switches: exemplo
1. Em t=1, qual é a entrada de origem para a switch 1?
No tempo t=1, (E,5) é adicionado como uma entrada na tabela 1.

2. Em t=1, qual é a entrada de destino para a switch 1?

No tempo t=1, (B,2) é adicionado como uma entrada na tabela 1.

3. Em t=1, qual é a entrada de origem para a switch 2?

No tempo t=1, (E,8) é adicionado como uma entrada na tabela 2.

4. Em t=1, qual é a entrada de destino para a switch 2?

No tempo t=1, a tabela 2 não recebe informação.

5. Em t=2, qual é a entrada de origem para a switch 1?

No tempo t=2, (K,7) é adicionado como uma entrada na tabela 1.

6. Em t=2, qual é a entrada de destino para a switch 1?

No tempo t=2, a tabela 1 não recebe informação.
2024.2 – Redes de Computadores 80 Profa. Morganna Diniz - BSI/EIA/UNIRIO
Switches: exemplo
7. Em t=2, qual é a entrada de origem para a switch 2?
No tempo t=2, (K,14) é adicionado como uma entrada na tabela 2.

8. Em t=2, qual é a entrada de destino para a switch 2?

No tempo t=2, (I,12) é adicionado como uma entrada na tabela 2.

9. Em t=3, qual é a entrada de origem para a switch 1?

No tempo t=3, a tabela 1 não recebe informação.

10. Em t=3, qual é a entrada de destino para a switch 1?

No tempo t=3, a tabela 1 não recebe informação.

11. Em t=3, qual é a entrada de origem para a switch 2?

No tempo t=3, (J,13) é adicionado como uma entrada na tabela 2.

12. Em t=3, qual é a entrada de destino para a switch 2?

A entrada já existe na tabela 2
2024.2 – Redes de Computadores 81 Profa. Morganna Diniz - BSI/EIA/UNIRIO
Switches: exemplo
13. Em t=4, qual é a entrada de origem para a switch 1?
No tempo t=4, (A,1) é adicionado como uma entrada na tabela 1.

14. Em t=4, qual é a entrada de destino para a switch 1?

No tempo t=4, (L,7) é adicionado como uma entrada na tabela 1.

15. Em t=4, qual é a entrada de origem para a switch 2?

No tempo t=4, (A,8) é adicionado como uma entrada na tabela 2.

16. Em t=4, qual é a entrada de destino para a switch 2?

No tempo t=4, (L,15) é adicionado como uma entrada na tabela 2.

2024.2 – Redes de Computadores 82 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Switches: exemplo
Considere uma LAN composta por 10
computadores conectados por dois
switches Ethernet de
autoaprendizagem. Em t = 0, as
entradas da tabela de switches para
ambos os switches estão vazias. Em t
= 1, 2, 3, 4, 5, 6, 7, 8 e 9, uma fonte
envia para um destino conforme
mostrado abaixo, e o destino responde
imediatamente (bem antes do
próximo intervalo de tempo).

Tabela 2 Tabela 1

2024.2 – Redes de Computadores 83 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Switches: exemplo
É possível fazer algumas observações em cima da tabela.
1. O TTL inicial é igual a 10. O TTL de H é 1 após 9 unidades de tempo (u.t.). Além disso, H
começou a primeira comunicação, pois H está na primeira linha nas duas tabelas.
2. O TTL dos nós que estão nas tabelas é diminuído de 1 a cada unidade de tempo se ele o nó
não participar da nova comunicação.
3. Quando o caminho do nó (origem ou destino) participa de nova comunicação e ele já está nas
tabelas, o TTL recebe valor 9 ao final da unidade de tempo.
4. O valor do caminho de um nó, na tabela final, indica há quanto tempo o caminho foi
acessado pela última vez. Por exemplo, (I,8) na tabela 2, indica que o caminho foi acessado
na u.t. anterior (tinha TTL = 9) e, portanto, este caminho foi utilizado em t = 8. Assim,
sabemos que
t=1→H t = 5 → D, K
t=2→I t=6→K
t=3→B t = 7 → E, G
t=4→A t=8→I
t = 9 → G, L
2024.2 – Redes de Computadores 84 Profa. Morganna Diniz - BSI/EIA/UNIRIO
Switches: exemplo

O exemplo não forneceu a lista de mensagens, mas

podemos apenas fazer algumas deduções sobre as
mensagens transmitidas.

2024.2 – Redes de Computadores 85 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Switches: exemplo
Tabela 2 Tabela 1
End. MAC interface TTL End. MAC interface TTL
H 11 9 H 7 9
G 10 9

t=1
H→G

H envia um broadcast querendo saber o endereço de G; G responde direto para H. A switch 1

recebe apenas o broadcast de H. Como H e G estão conectados através da switch 1, a tabela 1
possui as duas entradas. A comunicação de H não poderia ser com I, porque o nó I está nas
duas tabelas.

2024.2 – Redes de Computadores 86 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Switches: exemplo
Tabela 2 Tabela 1
End. MAC interface TTL End. MAC interface TTL
H 11 8 H 7 8
G 10 8 I 7 9
I 12 9 A 1 9
t=2 A 8 9
I→A

I envia um broadcast querendo saber o endereço de A. A responde direto para I. Como os dois
nós estão conectados a switches diferentes, as duas tabelas registram o nó A.

2024.2 – Redes de Computadores 87 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Switches: exemplo
Tabela 2 Tabela 1
End. MAC interface TTL End. MAC interface TTL
H 11 7 H 7 7
G 10 7 I 7 8
I 12 8 A 1 8
t=3 A 8 8 B 2 9
B→D B 8 9 D 4 9

B envia um broadcast querendo saber o endereço de D. D responde direto para I. Apenas a

Tabela 1 registra a resposta de D, pois B e D estão conectados à mesma switch.

2024.2 – Redes de Computadores 88 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Switches: exemplo
Tabela 2 Tabela 1
End. MAC interface TTL End. MAC interface TTL
H 11 6 H 7 6
G 10 9 I 7 7
I 12 7 A 1 7
t=4 A 8 7 B 2 8
A→G B 8 8 D 4 8
G 7 9

Sabemos que A teve comunicação com outro nó em t=4. Os próximos nós das tabelas são K
(tabela 2) e G (na tabela 1). Não pode ser K, pois teria que aparecer também na tabela 1. Pode
ser o nó G, pois este nó já está na tabela 1. O G é incluído na tabela 1 e o valor de TTL de G é
atualizado na tabela 2. Não poderia ser de G → A, porque G já sabia o caminho para A e nada
mudaria nas tabelas.
2024.2 – Redes de Computadores 89 Profa. Morganna Diniz - BSI/EIA/UNIRIO
Switches: exemplo
Tabela 2 Tabela 1
End. MAC interface TTL End. MAC interface TTL
H 11 5 H 7 5
G 10 8 I 7 6
I 12 6 A 1 6
t=5 A 8 6 B 2 7
K→D B 8 7 D 4 9
K 14 9 G 7 8
D 8 9 K 7 9

Sabemos que D e K se comunicam em t = 5. Como K aparece antes de D na tabela 2, a

comunicação foi de K para D. Além de incluir K na tabela 2, o TTL de D é mudado.

2024.2 – Redes de Computadores 90 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Switches: exemplo
Tabela 2 Tabela 1
End. MAC interface TTL End. MAC interface TTL
H 11 4 H 7 4
G 10 9 I 7 5
I 12 5 A 1 5
t=6 A 8 5 B 2 6
K→G B 8 6 D 4 8
ou K 14 9 G 7 7
G→K D 8 8 K 7 8

Sabemos que K se comunica com algum nó em t = 6. Como os dois nós estão ligados a uma
mesma switche e já estão na tabela 2, basta atualizar os TTLS na tabela.

2024.2 – Redes de Computadores 91 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Switches

Confira os exercícios interativos online para mais exemplos:

http://gaia.cs.umass.edu/kurose_ross/interactive
“Learning Switches - Basic”
“Learning Switches - Advanced”

2024.2 – Redes de Computadores 92 Profa. Morganna Diniz - BSI/EIA/UNIRIO

 LANs
●
VLAN (Virtual Local
Area Network)

2024.2 – Redes de Computadores 93 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Virtual LANs (VLANs): motivação
P: o que acontece à medida que o tamanho da LAN aumenta
e os usuários mudam o ponto de conexão?

domínio único de broadcast:

●
escala: todo o tráfego de transmissão
da camada 2 (ARP, DHCP, MAC
desconhecido) deve cruzar toda a LAN
●
eficiência, segurança, questões de
Computer privacidade
Science EE

2024.2 – Redes de Computadores 94 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Virtual LANs (VLANs): motivação
P: o que acontece à medida que o tamanho da LAN aumenta
e os usuários mudam o ponto de conexão?
domínio de transmissão único:
●
escala: todo o tráfego de transmissão
da camada 2 (ARP, DHCP, MAC
desconhecido) deve cruzar toda a LAN
Computer
●
eficiência, segurança, privacidade,
Science EE questões de eficiência
Problemas administrativos:
●
O usuário CS muda o escritório para
EE - fisicamente conectado ao switch
EE, mas deseja permanecer
logicamente conectado ao switch CS
2024.2 – Redes de Computadores 95 Profa. Morganna Diniz - BSI/EIA/UNIRIO
VLANs baseadas em portas
VLAN baseadas em portas: portas de switch
agrupadas (por software de gerenciamento
de switch) para que um único switch físico
Virtual Local Area ……
Network (VLAN) 1 7 9 15

switch(es) que suportam

2 8 10 16

… …
recursos de VLAN podem
ser configurados para EE (VLAN ports 1-8) CS (VLAN ports 9-15)

definir múltiplas LANs … opere como vários switches virtuais

virtuais em uma única
infraestrutura de LAN
física. 1 7 9 15

2 8 10 16

… …
EE (VLAN ports 1-8) CS (VLAN ports 9-15)

2024.2 – Redes de Computadores 96 Profa. Morganna Diniz - BSI/EIA/UNIRIO

VLANs baseadas em portas
●
isolamento de tráfego: os quadros de/para as portas 1
a 8 só podem alcançar as portas 1 a 8
➢
também pode definir VLAN com base em
endereços MAC de endpoints, em vez de portas de
switch
●
associação dinâmica: as portas podem ser atribuídas
dinamicamente entre VLANs
1 7 9 15

●
encaminhamento entre VLANS: feito via roteamento 2 8 10 16

(assim como com switches separados) … …

➢
na prática, os fornecedores vendem switches e EE (VLAN ports 1-8) CS (VLAN ports 9-15)

roteadores combinados

2024.2 – Redes de Computadores 97 Profa. Morganna Diniz - BSI/EIA/UNIRIO

 virtualização de
enlaces: MPLS

2024.2 – Redes de Computadores 98 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Multiprotocol label switching (MPLS)
●
O MPLS é um mecanismo que direciona dados de um nó da rede para o próximo nó
baseado em rótulos de menor caminho em vez de endereços de rede. Os rótulos
identificam enlaces virtuais (caminhos) entre nós distantes em vez de pontos terminais.
O MPLS pode encapsular pacotes de vários protocolos de rede.
●
objetivo: encaminhamento IP de alta velocidade entre redes de roteadores compatíveis
com MPLS, usando rótulo de comprimento fixo (em vez de correspondência de
prefixo mais curto)
➢
pesquisa mais rápida usando identificador de comprimento fixo
➢
emprestando ideias da abordagem do Circuito Virtual (VC)
➢
mas o datagrama IP ainda mantém o endereço IP!

2024.2 – Redes de Computadores 99 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Roteadores compatíveis com MPLS
●
também conhecido como roteador comutado por etiqueta
●
encaminhar pacotes para a interface de saída com base apenas no valor do rótulo (não
inspecionar o endereço IP)
➢
Tabela de encaminhamento MPLS distinta das tabelas de encaminhamento IP
●
flexibilidade: as decisões de encaminhamento de MPLS podem diferir daquelas de IP
➢
usar endereços de destino e origem para rotear fluxos para o mesmo destino de
maneira diferente (engenharia de tráfego)
➢
redirecionar fluxos rapidamente se o link falhar: caminhos de backup pré-
computados

2024.2 – Redes de Computadores 100 Profa. Morganna Diniz - BSI/EIA/UNIRIO

MPLS versus caminhos IP
O roteador de entrada IP/MPLS (R4) pode usar diferentes rotas MPLS para A
com base, por exemplo, no endereço de origem IP ou em outros campos

R6
D
IP router
R4 R3
R5
IP/MPLS router
A
R2 R1

●
Roteamento IP: caminho para o destino determinado apenas pelo endereço de destino
●
Roteamento MPLS: o caminho para o destino pode ser baseado no endereço de origem
e destino

2024.2 – Redes de Computadores 101 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Tabelas de encaminhamento MPLS
in out out
label label dest interface
10 A 0 in out out
12 D 0 label label dest interface

8 A 1 10 6 A 1
12 9 D 0
IP router
R6
0 0
D
1 1 IP/MPLS router
R4 R3
R5
0 0
A
R2 R1
in out out in out out
label label dest interface label label dest interface
8 6 A 0 6 - A 0

2024.2 – Redes de Computadores 102 Profa. Morganna Diniz - BSI/EIA/UNIRIO

 Redes do
DataCenter

2024.2 – Redes de Computadores 103 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Redes do Datacenter
De 10 a 100 milhares de hosts, muitas vezes intimamente
acoplados, próximos:
●
e-business (por exemplo, Amazon)
●
servidores de conteúdo (por exemplo, YouTube, Akamai,
Apple, Microsoft)
●
mecanismos de pesquisa, mineração de dados (por
exemplo, Google)
desafios:
●
vários aplicativos, cada um atendendo a um grande
número de clientes
●
confiabilidade
●
gerenciamento/balanceamento de carga, evitando
processamento, rede e gargalos de dados Inside a 40-ft Microsoft container, Chicago data center

2024.2 – Redes de Computadores 104 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Redes do Datacenter: Elementos de rede
Roteadores de borda
 Conexões para fora do datacenter

Switches de camada 1 (T-1)

 Conectando ~16 T-2s abaixo

Switches de camada 2 (T-2)

 conectando ~16 TORs abaixo
… … … …
Switches TOR (Top of Rack)
 um por rack
… … … …
 100G-400G Ethernet
Estantes (racks) de servidores
 20- 40 servidores blade: hosts

Os servidores blade são concebidos para a montagem em prateleiras

2024.2 – Redes de Computadores 105 Profa. Morganna Diniz - BSI/EIA/UNIRIO
 Um dia na vida de uma
solicitação da web

2024.2 – Redes de Computadores 106 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Um dia na vida de uma solicitação web

Cenário
●
nossa jornada pela pilha de protocolos está concluída!
➢
aplicação, transporte, rede, enlace
●
juntando tudo: síntese!
➢
objetivo: identificar, revisar, compreender os protocolos (em todas as
camadas) envolvidos em um cenário aparentemente simples: solicitar a
página www
➢
cenário: aluno conecta laptop à rede do campus, solicita/recebe
www.google.com

2024.2 – Redes de Computadores 107 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Um dia na vida de uma solicitação web
Cenário:
browser DNS server ●
cliente móvel
Comcast network chegando se conecta à
68.80.0.0/13 rede...
●
solicita página da web:
school network
www.google.com
68.80.2.0/24

web page

Parece
web server Google’s network Simples!
64.233.169.105 64.233.160.0/19

2024.2 – Redes de Computadores 108 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Um dia na vida de uma solicitação web

Conectando-se à Internet
DHCP DHCP
DHCP
DHCP
UDP
IP
 Para conectar o laptop, é preciso obter seu
Eth mobile entra na rede: próprio endereço IP, endereço do roteador de
DHCP
cliente DHCP
Física
DHCP
primeiro salto,
 Solicitação DHCP encapsulada em UDP,
DHCP
DHCP
DHCP UDP
encapsulada em IP, encapsulada em Ethernet
DHCP IP
Eth
 Transmissão de quadro Ethernet (destino:
DHCP

Física
roteador tem
servidor DHCP FFFFFFFFFFFF) na LAN, recebida no
roteador executando o servidor DHCP

2024.2 – Redes de Computadores 109 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Um dia na vida de uma solicitação web
DHCP
Conectando-se à Internet
UDP
 O servidor DHCP formula DHCP ACK
DHCP
DHCP IP
DHCP Eth mobile entra na rede: contendo o endereço IP do cliente, endereço
Física cliente DHCP
DHCP
IP do roteador de primeiro salto para o
cliente, nome e ender
DHCP
DHCP  encapsulamento no servidor DHCP,
DHCP
DHCP
UDP
IP
encaminhamento de quadro (aprendizado de
DHCP
Eth switch) através de LAN, dem
DHCP Física
roteador tem  Cliente DHCP recebe resposta DHCP
servidor DHCP

O cliente agora tem endereço IP, sabe o nome e endereço do

Servidor DNS, endereço IP do seu roteador de primeiro salto
2024.2 – Redes de Computadores 110 Profa. Morganna Diniz - BSI/EIA/UNIRIO
Um dia na vida de uma solicitação web
ARP
 antes de enviar a solicitação HTTP, é
necessário o endereço IP www.google.com:
DNS DNS DNS
DNS UDP  Consulta DNS criada, encapsulada em UDP,
ARP IP
DNS
ARP query Eth mobile entra na rede: encapsulada em IP, encapsulada em Eth. Para
Física cliente DHCP enviar quadro ao roteador, é necessário o
endereço MAC da interface do roteador: ARP
 Transmissão de consulta ARP, recebida pelo
roteador, que responde com uma resposta ARP
ARP
fornecendo o endereço MAC da interface do
ARP reply Eth
Física roteador
roteador tem
servidor DHCP  o cliente agora conhece o endereço MAC do
roteador do primeiro salto, então agora pode
enviar um quadro contendo a consulta DNS
2024.2 – Redes de Computadores 111 Profa. Morganna Diniz - BSI/EIA/UNIRIO
Um dia na vida de uma solicitação web
DNS
DNS DNS
DNS UDP
DNS DNS
IP DNS UDP
DNS
Eth
DNS IP
DNS Eth DNS
DNS Física server
DNS Física

Comcast network
68.80.0.0/13

 Datagrama IP contendo  Datagrama IP encaminhado da rede

consulta DNS encaminhada do campus para a rede Comcast,
via switch LAN do cliente roteado (tabelas criadas pelos
para o roteador de primeiro protocolos de roteamento RIP, OSPF,
salto IS-IS e/ou BGP) para o servidor DNS

2024.2 – Redes de Computadores 112 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Um dia na vida de uma solicitação web

HTTP
 para enviar uma solicitação
HTTP
SYNACK
SYN TCP HTTP, o cliente primeiro abre o
SYNACK
SYN

SYNACK
SYN
IP
Eth
soquete TCP para o servidor web
Física Comcast network
68.80.0.0/13  Segmento TCP SYN (etapa 1 no
handshake de 3 vias TCP) entre
domínios roteado para o servidor
web
 o servidor web responde com
SYNACK
SYN TCP
SYNACK
SYN IP TCP SYNACK (etapa 2 no
SYNACK
SYN Eth handshake TCP de 3 vias)
Física
Google web server  Conexão TCP estabelecida!
64.233.169.105

2024.2 – Redes de Computadores 113 Profa. Morganna Diniz - BSI/EIA/UNIRIO

Um dia na vida… solicitação/resposta HTTP
 Solicitação HTTP enviada
para o soquete TCP
HTTP
HTTP HTTP Página web
HTTP
HTTP TCP finalmente(!!!)
IP
 Datagrama IP contendo
HTTP
HTTP
mostrada
HTTP
HTTP Eth
Física Comcast network solicitação HTTP roteada para
68.80.0.0/13
www.google.com
 servidor web responde com
resposta HTTP (contendo
HTTP
HTTP
HTTP página web)
TCP
HTTP
IP
HTTP
Eth
 Datagrama IP contendo
Física resposta HTTP roteada de
Google web server volta ao cliente
64.233.169.105

2024.2 – Redes de Computadores 114 Profa. Morganna Diniz - BSI/EIA/UNIRIO

2024.2 – Redes de Computadores 115 Profa. Morganna Diniz - BSI/EIA/UNIRIO