Redes de Computadores I

Aula 19 – Camada de Rede

(Algoritmos de Roteamento)
Prof. Carlos Giovanni N. de Carvalho
[email protected]
 Agenda
• Algoritmos de Roteamento
• Roteamento na Internet
• Roteamento Multicast
Algoritmos de Roteamento
algoritmo de
roteamento

tabela de repasse local

valor cab. enlace saída
0100 3
0101 2
0111 2
1001 1

valor no cabeçalho
do pacote de chegada

0111 1

3 2
 Algoritmos de Roteamento
• Abstração

5
3
v w 5
2
u 2 1 z
3
1 2
Grafo: G = (N,E)
x 1
y

N = conjunto de roteadores = { u, v, w, x, y, z }

E = conjunto de enlaces = { (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
 Algoritmos de Roteamento
• Custo
5 • c(x,x’) = custo do enlace (x,x’)
3
v w 5 - p. e., c(w,z) = 5
2
u 2 1 z
3 • custo poderia ser sempre 1, ou
1 2 inversamente relacionado à largura
x 1
y ou inversamente relacionado ao
congestionamento

Custo do caminho (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)

algoritmo de roteamento: algoritmo que encontra o

caminho de menor custo
 Algoritmos de Roteamento
• Classificação
– Global:
• Todos os roteadores têm topologia completa,
informação de custo do enlace
• Algoritmos de “estado do enlace”
– Descentralizada:
• Roteador conhece vizinhos conectados fisicamente,
custos de enlace para vizinhos
• Processo de computação iterativo, troca de
informações com vizinhos
• Algoritmos de “vetor de distância”
 Algoritmos de Roteamento
• Classificação
– Estático:
• Rotas mudam lentamente com o tempo
– Dinâmico:
• Rotas mudam mais rapidamente
• Atualização periódica
• Em resposta a mudanças no custo do enlace
 Algoritmos de Roteamento
• Estado do Enlace
– Algoritmo de Dijkstra
• Nova topologia, custos de enlace conhecidos de todos
os nós
– Realizado por “broadcast de estado do enlace”
– Todos os nós têm a mesma informação
• Calcula caminhos de menor custo de um nó (“origem”)
para todos os outros nós
– Tabela de repasse para esse nó
• Iterativo: após k iterações, sabe caminho de menor
custo para k destinos
 Algoritmos de Roteamento
• Estado do Enlace
– Algoritmo de Dijkstra
• Notação
– c(x,y): custo do enlace do nó x até y; = ∞ se não forem
vizinhos diretos
– D(v): valor atual do custo do caminho da origem ao destino v
– p(v): nó predecessor ao longo do caminho da origem até v
– N': conjunto de nós cujo caminho de menor custo é
definitivamente conhecido
 Algoritmos de Roteamento
• Estado do Enlace – Algoritmo de Dijkstra
1 Inicialização:
2 N' = {u}
3 para todos os nós v
4 se v adjacente a u
5 então D(v) = c(u,v)
6 senão D(v) = ∞
7
8 Loop
9 acha w não em N' tal que D(w) é mínimo
10 acrescenta w a N'
11 atualiza D(v) para todo v adjacente a w e não em N' :
12 D(v) = min( D(v), D(w) + c(w,v) )
13 /* novo custo para v é custo antigo para v ou custo conhecido
14 do caminho mais curto para w + custo de w para v */
15 até todos os nós em N'
 Algoritmos de Roteamento
• Estado do Enlace – Algoritmo de Dijkstra
– Complexidade do algoritmo: n nós
• Cada iteração: precisa verificar todos os 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. e., custo do enlace = quantidade de tráfego
transportado
 Algoritmos de Roteamento
• Vetor de Distância
– Equação de Bellman-Ford (programação dinâmica)
• Defina
dx(y) : = custo do caminho de menor custo de x para y
• Depois
dx(y) = min {c(x,v) + dv(y) }
• Onde min assume todos os vizinhos v de x
 Algoritmos de Roteamento
• Vetor de Distância
– Dx(y) = estimativa do menor custo de x para y
– Nó x sabe custo de cada vizinho v: c(x,v)
– Nó x mantém vetor de distância Dx = [Dx(y): y є N ]
– Nó x também mantém vetor de distância de seus
vizinhos
• Para cada vizinho v, x mantém
Dv = [Dv(y): y є N ]
 Algoritmos de Roteamento
• Vetor de Distância
– Ideia básica:
• De tempos em tempos, cada nó envia sua própria estimativa
de vetor de distância aos vizinhos
• Assíncrono
• Quando um nó x recebe nova estimativa DV do vizinho, ele
atualiza seu próprio DV usando a equação de B-F:

Dx(y) ← minv{c(x,v) + Dv(y)} para cada nó y ∊ N

• Sob condições modestas, naturais, a estimativa Dx(y)

converge para o menor custo real dx(y)
 Algoritmos de Roteamento
• Vetor de Distância
– Iterativo, assíncrono: cada iteração local causada
por:
• Mudança de custo do enlace local
• Mensagem de atualização do DV do vizinho
– Distribuído:
• Cada nó notifica os vizinhos apenas quando seu DV
muda
• Vizinhos, então, notificam seus vizinhos, se necessário
 Algoritmos de Roteamento
• Vetor de Distância
– mudanças de custo do enlace:
– nó detecta mudança de custo no enlace local
– atualiza informação de roteamento, recalcula vetor de
distância
– se DV mudar, notifica vizinhos
• No tempo t0, y detecta a mudança do custo do enlace, atualiza
seu DV e informa aos seus vizinhos
• No tempo t1, z recebe a atualização de y e atualiza sua tabela
• Calcula um novo custo mínimo para x e envia seu DV aos vizinhos
• No tempo t2, y recebe a atualização de z e atualiza sua tabela de
distância. Menores custos de y não mudam, e daí y não
envia qualquer mensagem a z
 Algoritmos de Roteamento
• Comparação entre LS e DV
– Complexidade da mensagem
• LS: com n nós, E enlaces, O(nE) mensagens enviadas
• DV: troca apenas entre vizinhos
– Tempo de convergência varia
– Velocidade de convergência
• LS: algoritmo O(n2) requer O(nE) mensagens
– Pode ter oscilações
• DV: tempo de convergência varia
– Podem ser loops de roteamento
– Problema da contagem até o infinito
 Algoritmos de Roteamento
• Comparação entre LS e DV
– Robustez: o que acontece se roteador der defeito?
– LS:
• Nó pode anunciar custo do enlace incorreto
• Cada nó calcula apenas sua própria tabela
– DV:
• Nó DV pode anunciar custo do caminho incorreto
• Tabela de cada nó usada por outros
– Erro se propaga pela rede
 Algoritmos de Roteamento
• Roteamento Hierárquico
– Escala: com 200 milhões de destinos:
• Não pode armazenar todos os destinos nas tabelas de
roteamento!
• Troca de tabela de roteamento atolaria os enlaces!
– Autonomia administrativa
• Internet = rede de redes
• Cada administrador de rede pode querer controlar o
roteamento em sua própria rede
 Algoritmos de Roteamento
• Roteamento Hierárquico
– Roteadores agregados em regiões, “sistemas
autônomos” (AS)
– Roteadores no mesmo AS rodam o mesmo
protocolo de roteamento
• Protocolo de roteamento “intra-AS”
• Roteadores em ASes diferentes podem executar
protocolo de roteamento intra-AS diferente
– Roteador de borda
• Enlace direto com roteador em outro AS
 Algoritmos de Roteamento
• Roteamento Hierárquico

3c
3a 2c
3b 2a
AS3 2b
1c AS2
1a 1b AS1
1d

algoritmo algoritmo
de roteamento de roteamento
intra-AS inter-AS

tabela de
repasse
 Roteamento na Internet
• Roteamento Intra-AS
– Também conhecido como Interior Gateway
Protocols (IGP)
– Protocolos de roteamento intra-AS mais comuns:
• RIP: Routing Information Protocol
• OSPF: Open Shortest Path First
• IGRP: Interior Gateway roteamento Protocol
(proprietário da Cisco)
 Roteamento na Internet
• RIP
– Algoritmo de vetor de distância
– Incluído na distribuição BSD-UNIX em 1982
– Métrica de distância: # de saltos (máx. = 15 saltos)

u destino
v
saltos
A B w u 1
v 2
w 2
x x 3
z C D y 3
y z 2
 Roteamento na Internet
• Anúncios RIP
– Vetores de distância: trocados entre vizinhos a
cada 30s por meio de mensagem de resposta
(também conhecida como anúncio)
– Cada anúncio: lista de até 25 sub-redes de destino
dentro do AS
Destino
Roteamento na Internet
Próx. saltos
w - 1
anúncio de A para
x - 1 D
z C 4
…. … ...
z
w x y
A D B

C
Rede de destino Roteador seguinte Núm. saltos até
dest.
w A 2
y B 2
z BA 75
x -- 1
…. …. ....
tabela de roteamento/repasse em
D
 Roteamento na Internet
• RIP: Falha e Recuperação do Enlace
– Se nenhum anúncio for ouvido após 180 s -->
vizinho/enlace declarado morto
• Rotas via vizinho invalidadas
• Novos anúncios enviados aos vizinhos
• Vizinhos por sua vez enviam novos anúncios (se não
houver tabelas alteradas)
• Informação de falha do enlace rapidamente (?) se
propaga para rede inteira
• Reversão envenenada usada para impedir loops de
pingue-pongue (distância infinita = 16 saltos)
 Roteamento na Internet
• OSPF
– “open”: publicamente disponível
– Usa algoritmo Link State
• Disseminação de pacote LS
• Mapa de topologia em cada nó
• Cálculo de rota usando algoritmo de Dijkstra
– Anúncio OSPF transporta uma entrada por
roteador vizinho
– Anúncios disseminados ao AS inteiro (com
inundação)
• Transportados nas mensagens OSPF diretamente por IP
(em vez de TCP ou UDP)
 Roteamento na Internet
• OSPF: Outros Recursos
– Segurança: todas as mensagens OSPF autenticadas
(para impedir intrusão maliciosa)
– Múltiplos caminhos de mesmo custo permitidos
(apenas um caminho no RIP)
– Para cada enlace, múltiplas métricas de custo para
diferentes TOS (p. e., custo de enlace de satélite
definido “baixo” para melhor esforço; alto para tempo
real)
– Suporte integrado para uni e multicast:
• Multicast OSPF (MOSPF) usa mesma base de dados de
topologia que o OSPF
– OSPF hierárquico em grandes domínios
 Roteamento na Internet
• OSPF: Outros Recursos
– Hierarquia em dois níveis: área local, backbone.
• Anúncios de estado do enlace somente na área
• Cada nó tem topologia de área detalhada; somente direção
conhecida (caminho mais curto) para redes em outras áreas.
– Roteadores de borda: “resumem” distâncias às redes
na própria área, anunciam para outros roteadores de
borda.
– Roteadores de backbone: executam roteamento OSPF
limitado ao backbone.
– Roteadores de fronteira: conectam-se a outros AS’s
 Roteamento na Internet
• Roteamento inter-AS da Internet: BGP
– BGP (Border Gateway Protocol): o padrão de fato
– BGP oferece a cada AS um meio de:
• Obter informação de acessibilidade da sub-rede a partir
de ASs vizinhos.
• Propagar informação de acessibilidade a todos os
roteadores internos ao AS.
• Determinar rotas “boas” para sub-redes com base na
informação e política de acessibilidade.
– Permite que a sub-rede anuncie sua existência ao
resto da Internet: “Estou aqui”
 Roteamento na Internet
• BGP
– Pares de roteadores (pares BGP) trocam
informações de roteamento nas conexões TCP
semipermanentes: sessões BGP
• Sessões BGP não precisam corresponder a enlaces
físicos
– Quando AS2 anuncia um prefixo para AS1:
• AS2 promete que repassará datagramas para esse
prefixo
• AS2 pode agregar prefixos em seu anúncio
 Roteamento na Internet
• BGP

sessão eBGP
3c sessão iBGP
3a 2c
3b 2a
AS3 2b
1c AS2
1a 1b
AS1 1d
 Roteamento na Internet
• BGP
– Distribuindo informações de atingibilidade
• Usando sessão eBGP entre 3a e 1c, AS3 envia
informação de atingibilidade do prefixo a AS1
– 1c pode então usar iBGP para distribuir nova informação de
prefixo a todos os roteadores em AS1
– 1b pode então reanunciar nova informação de atingibilidade
para AS2 por sessão 3BGP 1b-para-2a
• Quando roteador descobre novo prefixo, ele cria
entrada para prefixo em sua tabela de repasse.
 Roteamento na Internet
• Diferenças entre roteamento intra-AS e inter-AS
– Política:
• Inter-AS: admin deseja controle sobre como seu tráfego é
roteado, quem roteia através de sua rede
• Intra-AS: único admin, de modo que nenhuma decisão
política é necessária
– Escala:
• Roteamento hierárquico salva tamanho de tabela, tráfego
de atualização reduzido
– Desempenho:
• Intra-AS: pode focalizar no desempenho
• Inter-AS: política pode dominar sobre desempenho
 Roteamento Multicast
• Roteamento Broadcast
– Entrega pacotes da fonte para todos os outros nós
– Duplicação de fonte é ineficaz

criação/transmiss
duplicata
R1 ão R1
de duplicata
duplicata
R2 R2

R3 R4 R3 R4

duplicação duplicação
de fonte na rede
 Roteamento Multicast
• Duplicação Dentro da Rede
– Inundação: quando o nó recebe pacote de
broadcast, envia cópia para todos os vizinhos
• Problemas: ciclos & tempestade de broadcast
– Inundação controlada: nó só transmite pacote se
não tiver transmitido algum pacote antes
• Nó registra ids de pacote já transmitidos por broadcast
• Ou repasse pelo caminho inverso (RPF): só repassa
pacote se chegasse no caminho mais curto entre nó e
fonte
– Spanning tree
• Nenhum pacote redundante recebido por qualquer nó
 Roteamento Multicast
• Spanning Tree
– Primeiro construa uma spanning tree
– Nós repassam cópias apenas ao longo da spanning
tree
A A

B B
c c

D D
F E F E

G G
(a) broadcast iniciado em A (b) broadcast iniciado em D
 Roteamento Multicast
• Problema
– Achar uma árvore (ou árvores) conectando
roteadores que têm membros do grupo mcast
local
• Árvore: nem todos os caminhos entre roteadores são
usados
• Baseado em fonte: árvore diferente de cada emissor
aos receptores
• Árvore compartilhada: mesma árvore usada por todos
os membros do grupo
 Roteamento Multicast
• Problema

árvore compartilhada árvores baseadas na

fonte
 Roteamento Multicast
• Técnicas para criação de árvores mcast
– Árvore baseada na fonte: uma árvore por fonte
• Árvores de caminho mais curto
• Repasse pelo caminho inverso
– Árvore compartilhada pelo grupo: grupo usa uma
árvore
• Spanning mínimo (Steiner)
• Árvores baseadas no centro
 Roteamento Multicast
• Roteamento multicasting da Internet
– DVMRP: Distance Vector Multicast Routing Protocol,
RFC1075
– Inundação e poda: repasse de caminho inverso,
árvore baseada na fonte
• Árvore RPF baseada nas próprias tabelas de roteamento do
DVMRP construídas pela comunicação de roteadores
DVMRP
• Sem suposições sobre unicast subjacente
• Datagrama inicial para grupo multicast inundado para toda
parte por meio de RPF
• Roteadores não querendo agrupar: enviam mensagens de
poda para roteadores antes dele
 Roteamento Multicast
• Tunelamento
– Datagrama multicast encapsulado dentro do
datagrama “normal” (não endereçado por
multicast)
– Datagrama IP normal enviado por “túnel” via
unicast IP regular ao roteador multicast receptor
– Roteador multicast receptor encapsula para
receber datagrama multicast
 Roteamento Multicast
• Tunelamento

P: Como conectar “ilhas” de roteadores

multicast em um “mar” de roteadores unicast?

topologia física topologia lógica

 Roteamento Multicast
• PIM: Protocol Independent Multicast
– Não depende de qualquer algoritmo de
roteamento unicast específico (funciona com
todos)
– Dois cenários de distribuição multicast diferentes:
• Denso:
– Membros do grupo densamente compactados, muito
próximos
– Largura de banda mais farta
 Roteamento Multicast
• PIM: Protocol Independent Multicast
– Dois cenários de distribuição multicast diferentes:
• Esparso:
– # redes com membros do grupo pequeno em relação ao #
total de redes
– Membros do grupo “bastante dispersos”
– Largura de banda não farta
 Bibliografia
• KUROSE, James F. ROSS, Keith W. Redes de
Computadores e a Internet. 3ª Edição,
Pearson, 2007.
• STALLINGS, William. Redes e Sistemas de
Comunicação de Dados. 5ª ed., Editora
Campus, Rio de Janeiro – RJ, 2005.
• TANENBAUM, Andrew. Redes de
Computadores. 4ª ed., Editora Campus, Rio de
Janeiro – RJ, 2003.