Aula_5_Roteamento_IP

Prévia do material em texto

4: Camada de Rede 4b-1 
Capítulo 4: Camada de Rede 
4.5 Algoritmos de 
roteamento 
Estado de enlace 
Vetor de distâncias 
Roteamento hierárquico 
4.6 Roteamento na 
Internet 
RIP 
OSPF 
BGP 
4.7 Roteamento 
broadcast e multicast 
4. 1 Introdução 
4.2 Redes de circuitos 
virtuais e de 
datagramas 
4.3 O que há dentro de 
um roteador 
4.4 O protocolo da 
Internet (IP) 
Formato do datagrama 
Endereçamento IPv4 
ICMP 
IPv6 
IPSec 
4: Camada de Rede 4b-2 
1 
2 3 
0111 
valor no cabeçalho 
do pacote que está 
chegando 
Algoritmo de 
roteamento 
tabela de repasse local 
valor cabeçalho link saída 
0100 
0101 
0111 
1001 
3 
2 
2 
1 
Relacionamento entre roteamento e 
repasse 
4: Camada de Rede 4b-3 
u 
y x 
w v 
z 
2 
2 
1 
3 
1 
1 
2 
5 
3 
5 
Grafo: G = (N,E) 
 
N = conj. de roteadores = { u, v, w, x, y, z } 
 
E = conj. de enlaces ={ (u,v), (u,x), (u,w), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) } 
Abstração com grafos 
Comentário: a abstração com grafos é útil em outros contextos da rede 
 
Exemplo: P2P, onde N é o conj. dos pares e E é o conj. das conexões TCP 
4: Camada de Rede 4b-4 
Abstração com grafos: custos 
u 
y x 
w v 
z 
2 
2 
1 
3 
1 
1 
2 
5 
3 
5 • c(x,x’) = custo do enlace (x,x’) 
 
 - p.e., c(w,z) = 5 
 
• custo poderia também ser 1, ou 
inversamente relacionado à banda, 
ou inversamente relacionado ao 
congestionamento 
Custo do caminho (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp) 
P: Qual o caminho de menor custo entre u e z? 
Algoritmo de roteamento: algoritmo que encontra o 
caminho de menor custo 
4: Camada de Rede 4b-5 
Classificação de Algoritmos de 
Roteamento 
Informação global ou 
descentralizada/local? 
Global: 
todos roteadores têm 
conhecimento completo da 
topologia e custos dos enlaces 
algoritmos de “estado de 
enlace” 
Descentralizada/local: 
roteador conhece vizinhos 
diretos e custos até eles 
processo iterativo de cálculo, 
troca de infos com vizinhos 
Algoritmo de “vetor de 
distâncias” 
Estáticos ou dinâmicos? 
Estáticos: 
rotas mudam lentamente com 
o tempo 
Dinâmicos: 
rotas mudam mais 
rapidamente 
atualização periódica 
em resposta a mudanças 
nos custos dos enlaces 
4: Camada de Rede 4b-6 
Capítulo 4: Camada de Rede 
4.5 Algoritmos de 
roteamento 
Estado de enlace 
Vetor de distâncias 
Roteamento hierárquico 
4.6 Roteamento na 
Internet 
RIP 
OSPF 
BGP 
4.7 Roteamento 
broadcast e multicast 
4. 1 Introdução 
4.2 Redes de circuitos 
virtuais e de 
datagramas 
4.3 O que há dentro de 
um roteador 
4.4 O protocolo da 
Internet (IP) 
Formato do datagrama 
Endereçamento IPv4 
ICMP 
IPv6 
IPSec 
4: Camada de Rede 4b-7 
O algoritmo de roteamento de 
“estado de enlace” (LS – Link 
State) 
Algoritmo de Dijkstra 
topologia da rede, custos dos 
enlaces conhecidos por todos os 
nós 
realizado através de “difusão 
do estado dos enlaces” 
todos os nós têm mesma info. 
calcula caminhos de menor custo 
de um nó (“origem”) para todos os 
demais 
gera tabela de rotas para 
aquele nó 
iterativo: depois de k iterações, 
sabemos menor custo p/ k 
destinos 
Notação: 
c(x,y): custo do enlace do 
nó x ao nó y. custo é 
infinito se não forem 
vizinhos diretos 
D(v): valor corrente do 
custo do caminho da origem 
ao destino v 
p(v): nó antecessor no 
caminho da origem ao nó v, 
imediatamente antes de v 
N’: conjunto de nós cujo 
caminho de menor custo já 
foi determinado 
 
4: Camada de Rede 4b-8 
O algoritmo de Dijkstra 
1 Inicialização: 
2 N’ = {u} 
3 para todos os nós v 
4 se v for um vizinho do nó u 
5 então D(v) = c(u,v) 
6 senão D(v) = ∞ 
7 
8 Loop 
9 encontre w não contido em N’ tal que D(w) é um mínimo 
10 adicione w ao conjunto N’ 
11 atualize D(v) para cada vizinho v de w e ainda não em N’: 
12 D(v) = min( D(v), D(w) + c(w,v) ) 
13 /* o novo custo para v é o velho custo para v ou o custo do 
14 menor caminho conhecido para w, mais o custo de w a v */ 
15 até que todos os nós estejam em N’ 
4: Camada de Rede 4b-9 
Algoritmo de Dijkstra: exemplo 
Etapa 
0 
1 
2 
3 
4 
5 
N' 
u 
ux 
uxy 
uxyv 
uxyvw 
uxyvwz 
D(v),p(v) 
2,u 
2,u 
2,u 
D(w),p(w) 
5,u 
4,x 
3,y 
3,y 
D(x),p(x) 
1,u 
D(y),p(y) 
∞ 
2,x 
D(z),p(z) 
∞ 
∞ 
4,y 
4,y 
4,y 
u 
y x 
w v 
z 
2 
2 
1 
3 
1 
1 
2 
5 
3 
5 
4: Camada de Rede 4b-10 
Algoritmo de Dijkstra: exemplo 
u 
y x 
w v 
z 
Árvore de caminhos mínimos resultante originada em u: 
v 
x 
y 
w 
z 
(u,v) 
(u,x) 
(u,x) 
(u,x) 
(u,x) 
destino enlace 
Tabela de repasse resultante em u: 
4: Camada de Rede 4b-11 
Algoritmo de Dijkstra, discussão 
Complexidade algoritmica: n nós 
a cada iteração: precisa checar todos nós, w, não em N’ 
n*(n+1)/2 comparações => O(n2) 
implementações mais eficientes possíveis: O(nlogn) 
Oscilações possíveis: 
p.ex., custo do enlace = carga do tráfego carregado 
A 
D 
C 
B 
1 1+e 
e 0 
e 
1 1 
0 0 
A 
D 
C 
B 
2+e 0 
0 0 
1+e 1 
A 
D 
C 
B 
0 2+e 
1+e 1 
0 0 
A 
D 
C 
B 
2+e 0 
e 0 
1+e 1 
inicialmente 
… recalcula 
rotas 
… recalcula … recalcula 
4: Camada de Rede 4b-12 
Capítulo 4: Camada de Rede 
4.5 Algoritmos de 
roteamento 
Estado de enlace 
Vetor de distâncias 
Roteamento hierárquico 
4.6 Roteamento na 
Internet 
RIP 
OSPF 
BGP 
4.7 Roteamento 
broadcast e multicast 
4. 1 Introdução 
4.2 Redes de circuitos 
virtuais e de 
datagramas 
4.3 O que há dentro de 
um roteador 
4.4 O protocolo da 
Internet (IP) 
Formato do datagrama 
Endereçamento IPv4 
ICMP 
IPv6 
IPSec 
4: Camada de Rede 4b-13 
O algoritmo de Vetor de Distâncias 
(DV) 
Equação de Bellman-Ford (programação 
dinâmica) 
Define 
dx(y) := custo do caminho de menor custo entre x 
e y 
 
Então 
 
dx(y) = min {c(x,v) + dv(y) } 
 
onde min é tomado entre todos os vizinhos v de x 
v 
4: Camada de Rede 4b-14 
Exemplo com Bellman-Ford 
u 
y x 
w v 
z 
2 
2 
1 
3 
1 
1 
2 
5 
3 
5 Claramente, dv(z) = 5, dx(z) = 3, dw(z) = 3 
du(z) = min { c(u,v) + dv(z), 
 c(u,x) + dx(z), 
 c(u,w) + dw(z) } 
 = min {2 + 5, 
 1 + 3, 
 5 + 3} = 4 
O nó que leva ao custo mínimo é o próximo passo 
ao longo do caminho mais curto➜ tabela de repasse 
A equação B-F diz: 
4: Camada de Rede 4b-15 
Algoritmo de Vetor de Distâncias 
Dx(y) = estimativa do menor custo entre x e y 
Nó x sabe o custo para cada vizinho v: c(x,v) 
Nó x mantém o vetor de distâncias Dx = 
[Dx(y): y є N ] 
Nó x mantém ainda os vetores de distâncias 
dos seus vizinhos 
Para cada vizinho v, x mantém 
 Dv = [Dv(y): y є N ] 
 
 
4: Camada de Rede 4b-16 
Algoritmo de Vetor de Distâncias 
Idéia básica: 
Cada nó envia periodicamente o seu próprio vetor 
de distâncias estimadas para os vizinhos 
Quando um nó x recebe um novo DV com as 
estimativas de um vizinho, ele atualiza o seu DV 
usando a equação B-F: 
Dx(y) ← minv{c(x,v) + Dv(y)} p/ cada nó y ∊ N 
Sob condições mínimas, naturais, a estimativa Dx(y) 
converge para o menor custo real dx(y) 
4: Camada de Rede 4b-17 
Algoritmo de Vetor de Distâncias 
Iterativo, assíncrono: cada 
iteração local causada por: 
mudança do custo do enlace 
localmensagem do vizinho: mudança 
de caminho de menor custo 
para algum destino 
Distribuído: 
cada nó avisa a seus vizinhos 
apenas quando muda seu 
caminho de menor custo para 
qualquer destino 
os vizinhos então avisam a seus 
vizinhos, se for necessário 
 
espera (mudança no custo 
de mensagem do vizinho) 
 
recalcula tabela de 
distâncias 
 
se mudou o caminho de 
menor custo para qq. 
destino, avisa vizinhos 
 
Cada nó: 
Network Layer 4-18 
x y z 
x 
y 
z 
0 2 7 
∞ ∞ ∞ 
∞ ∞ ∞ o
ri
ge
m
 
custo para 
or
ig
e
m
 
or
ig
e
m
 
x y z 
x 
y 
z 
0 
or
ig
e
m
 
custo para 
x y z 
x 
y 
z 
∞ ∞ 
∞ ∞ ∞ 
custo para 
x y z 
x 
y 
z 
∞ ∞ ∞ 
7 1 0 
custo para 
∞ 
2 0 1 
∞ ∞ ∞ 
2 0 1 
7 1 0 
tempo 
x z 
1 2 
7 
y 
Tabela nó x 
Tabela nó y 
Tabela nó z 
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} 
 = min{2+0 , 7+1} = 2 
Dx(z) = min{c(x,y) + 
 Dy(z), c(x,z) + Dz(z)} 
= min{2+1 , 7+0} = 3 
3 2 
Network Layer 4-19 
x y z 
x 
y 
z 
0 2 7 
∞ ∞ ∞ 
∞ ∞ ∞ o
ri
ge
m
 
custo para 
or
ig
e
m
 
or
ig
e
m
 
x y z 
x 
y 
z 
0 2 3 
or
ig
e
m
 
custo para 
x y z 
x 
y 
z 
0 2 3 
or
ig
e
m
 
custo para 
x y z 
x 
y 
z 
∞ ∞ 
∞ ∞ ∞ 
custo para 
x y z 
x 
y 
z 
0 2 7 
or
ig
e
m
 
custo para 
x y z 
x 
y 
z 
0 2 3 
or
ig
e
m
 
custo para 
x y z 
x 
y 
z 
0 2 3 
or
ig
e
m
 
custo para 
x y z 
x 
y 
z 
0 2 7 
or
ig
e
m
 
custo para 
x y z 
x 
y 
z 
∞ ∞ ∞ 
7 1 0 
custo para 
∞ 
2 0 1 
∞ ∞ ∞ 
2 0 1 
7 1 0 
2 0 1 
7 1 0 
2 0 1 
3 1 0 
2 0 1 
3 1 0 
2 0 1 
3 1 0 
2 0 1 
3 1 0 
tempo 
x z 
1 2 
7 
y 
Tabela nó x 
Tabela nó y 
Tabela nó z 
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} 
 = min{2+0 , 7+1} = 2 
Dx(z) = min{c(x,y) + 
 Dy(z), c(x,z) + Dz(z)} 
= min{2+1 , 7+0} = 3 
4: Camada de Rede 4b-20 
Vetor de Distâncias: mudanças no custo 
dos enlaces 
Mudanças no custo dos enlaces: 
nó detecta mudança no custo do enlace 
local 
atualiza tabela de distâncias 
se mudou o VD, avisa aos vizinhos 
X Z 
1 4 
50 
Y 
1 
“boas 
notícias 
chegam 
logo” 
No tempo t0, y detecta a mudança no custo do enlace, atualiza o 
seu VD e informa os vizinhos. 
 
No tempo t1, z recebe a atualização de y e atualiza a sua tabela. 
Computa o novo menor custo p/ x e envia o seu VD p/ os vizinhos. 
 
No tempo t2, y recebe a atualização de z e atualiza a sua tabela. 
Os custos mínimos de y não mudam e portanto y não envia 
nenhuma mensagem para z. 
 
4: Camada de Rede 4b-21 
Vetor de Distâncias: mudança no custo 
dos enlaces 
Mudança no custo dos enlaces: 
boas notícias chegam logo 
más notícias demoram para chegar - 
problema da “contagem até o 
infinito”! 
44 iterações antes do algoritmo 
estabilizar: veja texto 
Reversão envenenada: 
Se z roteia via y p/ chegar a x: 
z informa p/ y que sua distância p/ x 
é infinita (p/ que y não roteie p/ x via 
z) 
será que isto resolve completamente 
o problema da contagem até o 
infinito? 
x z 
1 4 
50 
y 
60 
4: Camada de Rede 4b-22 
Comparação dos algoritmos LS e DV 
Complexidade das mensagens 
LS: com n nós, E enlaces, O(nE) 
mensagens enviadas 
DV: trocar mensagens apenas 
entre vizinhos 
varia o tempo de 
convergência 
Velocidade de Convergência 
LS: algoritmo O(n2) requer 
O(nE) mensagens 
podem ocorrer oscilações 
DV: varia tempo para convergir 
podem ocorrer rotas cíclicas 
problema de contagem ao 
infinito 
Robustez: o que acontece se 
houver falha do roteador? 
LS: 
nó pode anunciar valores 
incorretos de custo de 
enlace 
cada nó calcula sua própria 
tabela 
DV: 
um nó VD pode anunciar um 
custo de caminho incorreto 
a tabela de cada nó é usada 
pelos outros nós 
• um erro propaga pela rede 
4: Camada de Rede 4b-23 
Capítulo 4: Camada de Rede 
4.5 Algoritmos de 
roteamento 
Estado de enlace 
Vetor de distâncias 
Roteamento hierárquico 
4.6 Roteamento na 
Internet 
RIP 
OSPF 
BGP 
4.7 Roteamento 
broadcast e multicast 
4. 1 Introdução 
4.2 Redes de circuitos 
virtuais e de 
datagramas 
4.3 O que há dentro de 
um roteador 
4.4 O protocolo da 
Internet (IP) 
Formato do datagrama 
Endereçamento IPv4 
ICMP 
IPv6 
IPSec 
4: Camada de Rede 4b-24 
Roteamento Hierárquico 
escala: com 200 milhões 
de destinos: 
impossível guardar todos 
destinos na tabela de rotas! 
troca de tabelas de rotas 
afogaria os enlaces! 
 
 
autonomia administrativa 
internet = rede de redes 
cada admin de rede pode 
querer controlar roteamento 
em sua própria rede 
Neste estudo de roteamento fizemos uma 
idealização: 
todos os roteadores idênticos 
rede “não hierarquizada” (“flat”) 
… não é verdade, na prática 
4: Camada de Rede 4b-25 
Roteamento Hierárquico 
agregar roteadores em 
regiões, “sistemas 
autônomos” (ASs) 
roteadores no mesmo 
AS usam o mesmo 
protocolo de 
roteamento 
protocolo de roteamento 
“intra-AS” 
roteadores em ASs 
diferentes podem usar 
diferentes protocolos de 
roteamento intra-AS 
Roteadores de borda 
Enlace direto para 
roteador em outro AS 
4: Camada de Rede 4b-26 
ASs interconectados 
3b 
1d 
3a 
1c 
2a AS3 
AS1 
AS2 
1a 
2c 
2b 
1b 
Algoritmo de 
roteamento 
intra-AS 
Algoritmo de 
roteamento 
inter-AS 
 
Tabela de 
repasse 
3c 
Tab. de encaminhamento 
é configurada pelos 
algoritmos intra-AS e 
inter-AS 
Intra-AS define entradas 
p/ dest. internos 
Inter-AS e Intra-AS 
definem entradas p/ dest. 
externos 
4: Camada de Rede 4b-27 
3b 
1d 
3a 
1c 
2a AS3 
AS1 
AS2 
1a 
2c 
2b 
1b 
3c 
Tarefas do roteamento inter-AS 
Suponha que um 
roteador no AS1 
recebe um datagrama 
cujo destino está fora 
do AS1 
Roteador deveria 
repassar o pacote p/ um 
dos roteadores de 
borda, mas qual? 
AS1 precisa: 
1. aprender quais destinos 
são alcançáveis via o 
AS2 e quais são 
alcançáveis via o AS3 
2. propagar estas info. de 
alcançabilidade para 
todos os roteadores no 
AS1 
Tarefas do rot. inter-AS! 
4: Camada de Rede 4b-28 
Exemplo: definindo a tabela de 
repasse no roteador 1d 
Suponha que o AS1 aprende (através do protocolo 
inter-AS) que a sub-rede x é alcançável via o AS3 (rot. 
de borda 1c) mas não via o AS2. 
Protocolo Inter-AS propaga info. de alcançabilidade 
para todos os roteadores internos. 
Roteador 1d determina através de info. de roteamento 
intra-AS que sua interface I está no caminho mínimo 
para 1c. 
Coloca par (x,I) na tab. de repasse. 
3b 
1d 
3a 
1c 
2a AS3 
AS1 
AS2 
1a 
2c 
2b 
1b 
3c 
x 
4: Camada de Rede 4b-29 
Exemplo: Escolhendo entre múltiplos ASes 
Suponha que o AS1 aprenda através do protocolo 
inter-AS que a subrede x seja alcançável de AS3 e 
de AS2. 
Para configurar a tabela de repasse, o roteador 1d 
deve determinar para qual gateway ele deve 
encaminhar pacotes para o destino x. 
Isto também é uma tarefa do protocolo de 
roteamento inter-AS! 
 
3b 
1d 
3a 
1c 
2a AS3 
AS1 
AS2 
1a 
2c 
2b 
1b 
3c 
x 
4: Camada de Rede 4b-30 
Aprende através do 
protocolo inter-AS 
que a sub-rede x é 
alcançável via 
múltiplos roteadores 
de borda 
Usa info. de 
roteamentodo 
protocolo intra-AS 
p/ determinar os 
caminhos mínimos 
p/ cada rot. de borda 
Roteamento da 
batata quente: 
escolhe o roteador 
de borda que tem o 
caminho de menor 
custo 
Determina da tab. de 
repasse a 
interface I que leva ao 
rot. de borda de menor 
custo. Insere (x,I) na 
tab. de repasse 
Exemplo: escolhendo entre múltiplos 
ASs 
Suponha agora que o AS1 aprende através do protocolo inter-
AS que a sub-rede x é alcançável via AS3 e via AS2. 
Para configurar a tabela de encaminhamento, o roteador 1d 
deve determinar para qual roteador de borda ele deve enviar 
pacotes com destino x . 
Isto também é tarefa do protocolo de roteamento inter-AS! 
Roteamento da batata quente (hot potato): envia pacote para o 
roteador de borda mais próximo. 
 
4: Camada de Rede 4b-31 
Capítulo 4: Camada de Rede 
4.5 Algoritmos de 
roteamento 
Estado de enlace 
Vetor de distâncias 
Roteamento hierárquico 
4.6 Roteamento na 
Internet 
RIP 
OSPF 
BGP 
4.7 Roteamento 
broadcast e multicast 
4. 1 Introdução 
4.2 Redes de circuitos 
virtuais e de 
datagramas 
4.3 O que há dentro de 
um roteador 
4.4 O protocolo da 
Internet (IP) 
Formato do datagrama 
Endereçamento IPv4 
ICMP 
IPv6 
IPSec 
4: Camada de Rede 4b-32 
Roteamento Intra-AS 
Também conhecidos como protocolos de 
roteadores internos (IGP - Interior Gateway 
Protocols ) 
Os protocolos de roteamento Intra-SA mais 
comuns são: 
 
RIP: Routing Information Protocol 
 
OSPF: Open Shortest Path First 
 
IGRP: Interior Gateway Routing Protocol 
(proprietário da Cisco) 
4: Camada de Rede 4b-33 
Capítulo 4: Camada de Rede 
4.5 Algoritmos de 
roteamento 
Estado de enlace 
Vetor de distâncias 
Roteamento hierárquico 
4.6 Roteamento na 
Internet 
RIP 
OSPF 
BGP 
4.7 Roteamento 
broadcast e multicast 
4. 1 Introdução 
4.2 Redes de circuitos 
virtuais e de 
datagramas 
4.3 O que há dentro de 
um roteador 
4.4 O protocolo da 
Internet (IP) 
Formato do datagrama 
Endereçamento IPv4 
ICMP 
IPv6 
IPSec 
4: Camada de Rede 4b-34 
RIP (Routing Information Protocol) 
Algoritmo vetor de distâncias 
Incluído na distribuição do BSD-UNIX em 1982 
Métrica de distância: nº de saltos (enlaces) (máx = 15 
enlaces) 
D C 
B A 
u v 
w 
x 
y 
z 
destino saltos 
 u 1 
 v 2 
 w 2 
 x 3 
 y 3 
 z 2 
 
Do roteador A p/ sub-redes: 
4: Camada de Rede 4b-35 
Anúncios RIP 
Vetores de distâncias: trocados a cada 30 
seg via Mensagem de Resposta (também 
chamada de anúncio) 
Cada anúncio: rotas para até 25 redes 
destino dentro do AS 
 
4: Camada de Rede 4b-36 
Exemplo RIP 
Sub-Rede Próximo Roteador No. de saltos até o 
 destino destino 
 w A 2 
 y B 2 
 z B 7 
 x -- 1 
 …. …. .... 
w x y 
z 
A 
C 
D B 
Tabela de rotas/repasse em D 
... 
4: Camada de Rede 4b-37 
Exemplo RIP 
Sub-Rede destino Próximo Roteador No. de saltos 
 w A 2 
 y B 2 
 z B A 7 5 
 x -- 1 
 …. …. .... 
w x y 
z 
A 
C 
D B 
Tabela de rotas/repasse em D 
... 
 Dest Prox Saltos 
 w - 1 
 x - 1 
 z C 4 
 …. … ... 
Anúncios de 
A para D 
4: Camada de Rede 4b-38 
RIP: Falha e Recuperação de Enlaces 
Se não for recebido anúncio novo durante 180 seg --> 
vizinho/enlace declarados mortos 
rotas via vizinho invalidadas 
novos anúncios enviados aos vizinhos 
na sua vez, os vizinhos publicam novos anúncios (se 
foram alteradas as suas tabelas) 
informação sobre falha do enlace rapidamente 
propaga para a rede inteira 
reversão envenenada usada para impedir rotas 
cíclicas (ping-pong) (distância infinita = 16 enlaces) 
4: Camada de Rede 4b-39 
RIP: Processamento de tabelas 
Tabelas de repasse RIP gerenciadas por processo de nível de 
aplicação chamado route-d (routing daemon) 
anúncios enviados periodicamente em pacotes UDP 
 
4: Camada de Rede 4b-40 
Capítulo 4: Camada de Rede 
4.5 Algoritmos de 
roteamento 
Estado de enlace 
Vetor de distâncias 
Roteamento hierárquico 
4.6 Roteamento na 
Internet 
RIP 
OSPF 
BGP 
4.7 Roteamento 
broadcast e multicast 
4. 1 Introdução 
4.2 Redes de circuitos 
virtuais e de 
datagramas 
4.3 O que há dentro de 
um roteador 
4.4 O protocolo da 
Internet (IP) 
Formato do datagrama 
Endereçamento IPv4 
ICMP 
IPv6 
IPSec 
4: Camada de Rede 4b-41 
OSPF (Open Shortest Path First) 
“open” (aberto): publicamente disponível 
Usa algoritmo do Estado de Enlaces (LS) 
disseminação de pacotes LS 
mapa da topologia em cada nó 
cálculo de rotas usando o algoritmo de Dijkstra 
Anúncio de OSPF inclui uma entrada por roteador 
vizinho 
Anúncios disseminados para AS inteiro (via inundação) 
Carregados em mensagens OSPF diretamente sobre IP (ao 
invés de TCP ou UDP) 
4: Camada de Rede 4b-42 
OSPF: características “avançadas” 
(não existentes no RIP) 
Segurança: todas mensagens OSPF 
autenticadas (para impedir intrusão maliciosa) 
Caminhos múltiplos de igual custo (o RIP 
permite e usa apenas uma rota) 
Suporte integrado para roteamento unicast e 
multicast: 
OSPF multicast (MOSPF) usa mesma base 
de dados de topologia usado pelo OSPF 
OSPF hierárquico em domínios grandes. 
4: Camada de Rede 4b-43 
OSPF Hierárquico 
4: Camada de Rede 4b-44 
OSPF Hierárquico 
Hierarquia de dois níveis: área local, backbone. 
Anúncios de LS disseminados apenas na mesma área 
cada nó possui topologia detalhada da área; apenas 
sabe a direção (caminho mais curto) para redes em 
outras áreas. 
Roteador de borda de área: “sumariza” distâncias às 
redes na sua própria área, anuncia a outros 
roteadores de fronteira de área. 
Roteadores de backbone: realizam roteamento OSPF 
limitado ao backbone. 
Roteadores de borda: ligam a outros ASs. 
 
4: Camada de Rede 4b-45 
Capítulo 4: Camada de Rede 
4.5 Algoritmos de 
roteamento 
Estado de enlace 
Vetor de distâncias 
Roteamento hierárquico 
4.6 Roteamento na 
Internet 
RIP 
OSPF 
BGP 
4.7 Roteamento 
broadcast e multicast 
4. 1 Introdução 
4.2 Redes de circuitos 
virtuais e de 
datagramas 
4.3 O que há dentro de 
um roteador 
4.4 O protocolo da 
Internet (IP) 
Formato do datagrama 
Endereçamento IPv4 
ICMP 
IPv6 
IPSec 
4: Camada de Rede 4b-46 
Roteamento externo a sistemas 
autônomos: BGP 
BGP (Border Gateway Protocol): o padrão de fato 
BGP provê para cada AS meios de: 
1. Obter informação de alcançabilidade (atingibilidade!!!) de 
sub-redes a partir de ASs vizinhos. 
2. Propagar informação de alcançabilidade para todos os 
roteadores internos ao AS. 
3. Determinar “boas” rotas para sub-redes a partir de 
informação de alcançabilidade e políticas. 
Permite que uma sub-rede anuncie a sua existência 
para o resto da Internet: “Eu existo e estou aqui!” 
 
4: Camada de Rede 4b-47 
O básico do BGP 
Par de roteadores (pares BGP) trocam infos de roteamento 
através de conexões TCP semipermanentes TCP: sessões BGP 
Note que sessões BGP não correspondem a enlaces físicos. 
Quando o AS2 anuncia um prefixo para o AS1, ele está 
prometendo que vai enviar àquele prefixo quaisquer 
datagramas destinados ao mesmo. 
AS2 pode agregar prefixos nos seus anúncios 
 
3b 
1d 
3a 
1c 
2a AS3 
AS1 
AS2 
1a 
2c 
2b 
1b 
3c 
sessão eBGP 
sessão iBGP 
4b-48 
Distribuindo informação de 
alcançabilidadeCom a sessão eBGP 3a-para-1c, AS3 envia informação de 
alcançabilidade de prefixos para AS1. 
1c pode usar iBGP para distribuir esta nova informação de 
alcance de prefixo para todos os roteadores em AS1. 
1b pode então re-anunciar a nova informação de alcance para 
AS2 através da sessão eBGP 1b-para-2a. 
Quando um roteador aprende sobre um novo prefixo, ele cria 
uma entrada para o prefixo na sua tabela de repasse. 
3b 
1d 
3a 
1c 
2a AS3 
AS1 
AS2 
1a 
2c 
2b 
1b 
3c 
sessão eBGP 
sessão iBGP 
4: Camada de Rede 4b-49 
Atributos de caminho e rotas BGP 
Quando um prefixo é anunciado, o anúncio inclui 
atributos BGP. 
prefixo + atributos = “rota” 
Dois atributos importantes: 
AS-PATH: contém os ASs pelos quais o anúncio para o 
prefixo passou: AS 67 AS 17 
NEXT-HOP: indica o roteador específico, interno ao AS, 
que leva ao AS do próximo salto. (Podem haver múltiplos 
enlaces do AS atual para o AS do próximo salto) 
Quando um roteador de borda recebe um anúncio 
de rota, usa a política de importação para 
aceitar/declinar. 
 
4: Camada de Rede 4b-50 
Seleção de rota do BGP 
Roteador pode aprender sobre mais de 
uma rota para algum prefixo. Ele deve 
selecionar a rota. 
Regras de eliminação: 
1. Valor do atributo preferência local associado à 
rota: decisão política 
2. Menor AS-PATH 
3. Roteador NEXT-HOP mais próximo: 
roteamento batata quente 
4. Critérios adicionais 
4: Camada de Rede 4b-51 
Mensagens BGP 
Mensagens BGP trocadas usando TCP. 
Mensagens BGP: 
OPEN: abre conexão TCP ao roteador par e 
autentica remetente 
UPDATE: anuncia caminho novo (ou retira velho) 
KEEPALIVE mantém conexão viva na ausência de 
UPDATES; também reconhece pedido OPEN 
NOTIFICATION: reporta erros na mensagem 
anterior; também usada para fechar conexão 
4: Camada de Rede 4b-52 
Políticas de roteamento BGP 
A,B,C são redes de provedores 
X,W,Y são clientes (das redes de provedores) 
X com duas interfaces: conectadas a duas redes 
X não quer rotear de B para C 
.. então X não vai anunciar para B a rota para C 
A 
B 
C 
W 
X 
Y 
legenda: 
rede 
cliente 
rede 
provedor 
 
4: Camada de Rede 4b-53 
Políticas de roteamento BGP (2) 
A anuncia para B o caminho AW 
B anuncia para X o caminho BAW 
Deveria B anunciar para C o caminho BAW? 
Nem pensar! B não obtém “rendimento” pelo roteamento 
CBAW, já que nem W ou C são clientes de B 
B quer forçar C a rotear para W via A 
B quer rotear apenas para/dos seus clientes! 
 
A 
B 
C 
W 
X 
Y 
legenda: 
rede 
cliente 
rede 
provedor 
 
4: Camada de Rede 4b-54 
Por que há diferenças entre 
roteamento Intra-AS e Inter-AS? 
Políticas: 
Inter-AS: administração quer controle sobre como o 
tráfego é roteado, quem transita através da sua rede. 
Intra-AS: administração única, logo são 
desnecessárias decisões políticas 
Escalabilidade: 
roteamento hierárquico economiza tamanho de tabela 
de rotas, reduz tráfego de atualização 
Desempenho: 
Intra-AS: pode focar em desempenho 
Inter-AS: políticas podem ser mais importantes do 
que desempenho 
4: Camada de Rede 4b-55 
Capítulo 4: Camada de Rede 
4.5 Algoritmos de 
roteamento 
Estado de enlace 
Vetor de distâncias 
Roteamento hierárquico 
4.6 Roteamento na 
Internet 
RIP 
OSPF 
BGP 
4.7 Roteamento 
broadcast e multicast 
4. 1 Introdução 
4.2 Redes de circuitos 
virtuais e de 
datagramas 
4.3 O que há dentro de 
um roteador 
4.4 O protocolo da 
Internet (IP) 
Formato do datagrama 
Endereçamento IPv4 
ICMP 
IPv6 
IPSec 
4: Camada de Rede 4b-56 
R1 
R2 
R3 R4 
duplicação 
na fonte 
R1 
R2 
R3 R4 
duplicação 
dentro da rede 
criação/transmissão 
duplicada 
duplicação 
Roteamento Broadcast 
Envia pacotes de um nó para todos os outros nós 
Duplicação na fonte é ineficiente: 
Duplicação na fonte: como a fonte determina 
os endereços dos receptores? 
duplicação 
4: Camada de Rede 4b-57 
Duplicação dentro da rede 
Inundação: quando nó recebe pacotes de 
broadcast, envia cópia para todos os vizinhos 
Problemas: ciclos e tempestades de broadcast 
Inundação controlada: nó somente faz broadcast 
do pacote se já não tiver feito antes com o mesmo 
pacote 
Nó mantém registro sobre ids dos pacotes para os quais 
já fez broadcast 
Ou adota o repasse pelo caminho inverso (Reverse Path 
Forwarding - RPF): só repassa pacote se chegou pelo 
caminho unicast mais curto até o remetente 
Árvores geradoras (spanning trees) 
Nenhum pacote redundante recebido por nenhum nó 
4: Camada de Rede 4b-58 
A 
B 
G 
D 
E 
c 
F 
A 
B 
G 
D 
E 
c 
F 
(a) Broadcast iniciado em A (b) Broadcast iniciado em D 
Árvore Geradora 
Primeiro construa uma árvore geradora 
Nós encaminham cópias somente ao longo 
da árvore geradora 
4: Camada de Rede 4b-59 
A 
B 
G 
D 
E 
c 
F 
1 
2 
3 
4 
5 
(a) Construção passo-a-
passo da árvore geradora 
A 
B 
G 
D 
E 
c 
F 
(b) Árvore geradora 
construída 
Árvore Geradora: criação 
Nó central 
Cada nó envia mensagem de adesão ponto-a-ponto 
(unicast) endereçadas ao nó central 
Mensagem é repassada até que chegue em um nó já 
pertencente à árvore geradora ou ao nó central! 
Problema de Roteamento Multicast 
Meta: achar uma árvore (ou árvores) conectando todos 
os roteadores com membros locais do grupo mcast 
árvore: nem todos os caminhos entre roteadores são usados 
baseada na fonte: árvore distinta de cada fonte para 
receptores 
compartilhada: mesma árvore usada por todos os membros do 
grupo 
Árvore compartilhada Árvores baseadas na fonte 
Abordagens para a construção de 
árvores mcast 
Abordagens: 
baseada na fonte: uma árvore por fonte 
árvores de caminhos mínimos 
envio pelo caminho reverso 
compartilhada: grupo usa uma árvore única 
árvore de custo mínimo (Steiner) 
árvore baseada em um centro 
…primeiro olharemos as abordagens básicas, e depois 
protocolos específicos que adotam estas abordagens 
 
Árvore de Caminhos Mínimos 
 
Árvore de encaminhamento mcast: árvore composta 
pelos caminhos mínimos da fonte para todos os 
receptores 
Algoritmo de Dijkstra 
R1 
R2 
R3 
R4 
R5 
R6 R7 
2 
1 
6 
3 4 
5 
i 
roteador com membro do 
grupo atrelado 
roteador sem membro do 
grupo atrelado 
enlace usado p/ envio, 
i indica a ordem de adição 
do enlace pelo algoritmo 
LEGENDA S: fonte 
Repasse pelo Caminho Inverso 
se (datagrama mcast recebido por um enlace de 
entrada no caminho mínimo de volta para a fonte) 
então inunda o datagrama por todos os enlaces de 
saída 
senão ignora o datagrama 
 Baseia-se no conhecimento do roteador 
sobre caminhos mínimos unicast dele para a 
fonte 
 cada roteador tem um comportamento de 
envio simples: 
Repasse pelo Caminho Inverso: 
exemplo 
• resultado é uma árvore de caminho mínimo inverso 
específica para a fonte 
- pode ser uma escolha ruim para enlaces 
assimétricos 
R1 
R2 
R3 
R4 
R5 
R6 R7 
datagrama vai ser 
encaminhado 
LEGENDA S: fonte 
datagrama não vai ser 
encaminhado 
roteador com membro do 
grupo atrelado 
roteador sem membro do 
grupo atrelado 
Envio pelo Caminho Reverso: poda 
Árvore de repasse contém sub-árvores sem nenhum 
membro do grupo multicast 
não há necessidade de enviar datagramas pelas 
sub-árvores 
mensagens de “poda” enviadas para trás pelo 
roteador sem nenhum membro do grupo pra frente 
R1 
R2 
R3 
R4 
R5 
R6 R7 
mensagem de poda 
LEGENDAS: fonte 
enlace com envio mcast 
P 
P 
P 
roteador com membro do 
grupo atrelado 
roteador sem membro do 
grupo atrelado 
Árvore de Steiner 
Árvore de Steiner: árvore de custo mínimo 
conectando todos os roteadores com 
membros locais do grupo mcast 
problema NP-completo 
existem excelentes heurísticas 
não é usada na prática: 
complexidade computacional 
necessita informações sobre a rede inteira 
monolítica: recalculada sempre que um roteador 
precisa ser acrescentado/retirado 
Árvores baseadas em centros 
árvore de envio única compartilhada por todos 
um roteador eleito como “centro” da árvore 
para juntar-se: 
roteador de fora envia msg-adesão unicast 
endereçada ao roteador central 
msg-adesão é “processada” pelos roteadores 
intermediários e repassada para o centro 
msg-adesão ou chega a um ramo da árvore já 
existente para este centro, ou chega ao centro 
caminho seguido por msg-adesão se torna novo 
ramo da árvore para este roteador 
Árvores baseadas em centros: 
exemplo 
Suponha que R6 foi escolhido como centro: 
R1 
R2 
R3 
R4 
R5 
R6 R7 
ordem em que as 
mensagens de junção são 
geradas 
LEGENDA 
2 
1 
3 
1 
roteador com membro do 
grupo atrelado 
roteador sem membro do 
grupo atrelado 
Roteamento Multicast na Internet: 
DVMRP 
DVMRP: distance vector multicast routing 
protocol, RFC1075 
inundação e poda: envio pelo caminho inverso 
(RPF), árvore baseada na fonte 
árvore RPF baseada em tabelas de roteamento 
próprias do DVMRP, construídas por meio da 
comunicação entre roteadores DVMRP 
nada assume sobre o roteamento unicast subjacente 
datagrama inicial para o grupo mcast é inundado por 
todo lugar via RPF 
roteadores sem membros: mensagens de poda para 
cima 
DVMRP: continuando… 
estado soft : roteador DVMRP “esquece” 
periodicamente (1 min.) que ramos estão podados: 
dados mcast novamente fluem pelos ramos não podados 
roteador de baixo: refaz a poda ou continua a receber 
dados 
roteadores podem rapidamente se enxertar na 
árvore 
seguindo junção IGMP na folha 
considerações finais 
comumente implementado em roteadores comerciais 
roteamento Mbone feito através do DVMRP 
Tunelamento 
Q: Como conectar “ilhas” de roteadores multicast em 
um “oceano” de roteadores unicast? 
 datagrama mcast encapsulado dentro de um datagrama 
“normal” (sem endereço multicast) 
 datagrama IP normal enviado através de um “túnel” via IP 
unicast regular para o roteador mcast receptor 
 roteador mcast receptor desencapsula para obter datagrama 
mcast 
Topologia física Topologia lógica 
PIM: Protocol Independent Multicast 
não depende de nenhum algoritmo de roteamento 
unicast subjacente (trabalha com todos) 
Dois cenários de distribuição multicast diferentes: 
Denso: 
 Localização dos 
membros do grupo de 
alta densidade 
 maior disponibilidade 
de banda 
Esparso: 
 nº de roteadores com 
membros do grupo é 
pequeno em relação ao nº 
total de roteadores 
 membros do grupo 
“amplamente dispersos” 
 menor disponibilidade de 
banda 
Conseqüências da Dicotomia Esparso-Denso: 
Denso 
participação dos 
roteadores nos grupos 
assumida até que os 
roteadores se podem 
explicitamente 
construção da árvore 
mcast ditada pelos dados 
(e.x., RPF) 
uso da banda e 
processamento no 
roteador não participante 
do grupo perdulários 
Esparso: 
sem participação até que 
os roteadores se juntem 
explicitamente 
construção da árvore 
mcast ditada pelos 
receptores (e.x., baseada 
em centro) 
uso da banda e 
processamento no 
roteador não participante 
do grupo criteriosos 
PIM- Modo Denso 
inundação com RPF e poda, similar ao 
DVMRP mas 
 Protocolo de roteamento unicast subjacente 
provê as informações referentes ao datagrama 
chegando, necessárias ao RPF 
 inundação menos complicada (menos eficiente) 
que a do DVMRP reduz a dependência em 
relação ao algoritmo de roteamento subjacente 
 possui mecanismo no protocolo para que o 
roteador detecte que é um nó folha 
PIM – Modo Esparso 
abordagem baseada em 
centro 
Roteador envia msg. de 
junção para o ponto de 
encontro (rendezvous point - 
RP) 
Roteadores intermediários 
atualizam estado e 
encaminham msg. de junção 
após se juntar via RP, 
roteador pode mudar p/ 
árvore baseada na fonte 
performance melhorada: 
menos concentração, 
caminhos menores 
R1 
R2 
R3 
R4 
R5 
R6 
R7 
junção 
junção 
junção 
multicast dos dados 
a partir do ponto 
de encontro (RP) 
ponto de 
encontro 
PIM – Modo Esparso 
fonte(s): 
dados via rot. unicast 
para o RP, que os 
distribui ao longo da 
árvore com raiz no RP 
RP pode estender 
árvore mcast para 
cima até a fonte 
RP pode enviar msg. 
pare p/ fonte se não 
houver receptores 
atrelados 
“ninguém está ouvindo!” 
R1 
R2 
R3 
R4 
R5 
R6 
R7 
junção 
junção 
junção 
multicast dos dados 
a partir do ponto 
de encontro (RP) 
ponto de 
encontro 
4: Camada de Rede 4b-77 
Camada de Rede: resumo 
Próxima parada: 
A camada de 
Enlace de 
Dados! 
O que nós cobrimos: 
Serviços da camada de rede 
O que há dentro de um 
roteador? 
O Protocolo da Internet: IP 
Algoritmos de roteamento: 
estado dos enlaces e vetor de 
distâncias 
roteamento hierárquico 
protocolos de roteamento 
Internet RIP, OSPF, BGP 
Roteamento broadcast e 
multicast