Roteamento em Backbones IP
A.S., RIP, OSPF, IS-IS e BGP
Edgard Jamhour
Estrutura da Internet
- Como as
informações são
roteadas na
Internet?
- Quem configura
os roteadores da
Internet?
INTERNET
Coleção de Roteadores
Estrutura da Internet
• A internet é estruturada na forma de sistemas autônomos:
A
B
C
F
E
G
I
D
SISTEMA AUTÔNOMO 1
H
J
SISTEMA AUTÔNOMO 2
X
Y
Z
SISTEMA AUTÔNOMO 3
Sistema Autônomo
(Autonomous System - AS)
• Um AS é uma rede que divulga seus endereços para outras redes da
Internet.
• Propriedades do AS
– Possui os seus próprios IP’s.
– Seus endereços independem do provedor de acesso.
– Pode conectar-se a vários provedores simultaneamente.
Redes
pertencentes
ao AS
Conexão com outro AS
F
G
I
Conexão com outro AS
H
J
Exemplo de AS
• Bloco de Endereços do AS:
– 200.17.0.0/16 (255.255.0.0)
– 200.17.0.0 ao 200.17.255.255
G: 200.17.1.1
H: 200.17.2.1
J: 200.17.3.1
200.17.1.0/24
AS: 200.17.0.0/16
Conexão com
outro AS
F
Conexão com
outro AS
200.17.2.0/24
G
I
H
J
200.17.3.0/24
Tipos de AS
• Sistemas autônomos podem ser:
– Redes Privadas:
• Transportam apenas o seu próprio tráfego.
– Provedores:
• Transportam o tráfego de outras redes.
privado
público
público
público
privado
Quem usa os endereços do Provedor não é um AS
Gateway Default da
Rede Corporativa
A
B
C
F
E
G
I
D
H
J
SISTEMA AUTÔNOMO 2
SISTEMA AUTÔNOMO 1
X
Y
Z
SISTEMA AUTÔNOMO 3
Roteadores na Internet
• Os roteadores da Internet são de dois tipos:
• Exterior Gateways
– Troca informações com roteadores pertencentes a outros AS.
– Equipamento muito caro, com alta capacidade de memória.
• Interior Gateways
– Troca informações apenas no interior do seu AS.
– Roteador comum.
Gateway Interno
F
G
I
H
J
Gateway
Externo
Sistema Autônomo
• As rotas na Internet são atualizadas
automaticamente.
• A estratégia de roteamento no interior do sistema
autônomo rede é escolhida pelo administrador do
sistema.
– IGP: Internal Gateway Protocol
• A estratégia de roteamento entre sistemas
autônomos é definida por um protocolo de
roteamente padrão:
– BGP: Border Gateway Protocol
EGP e IGP
Conhece todas
as rotas da
Internet
Conhece apenas
as rotas no
interior do AS
216.1.2.0/24
AS: 216.1.2.0/16
IGP
A
IGP
B
IGP
IGP
F
E
D
G
IGP
IGP
IGP
SISTEMA
AUTÔNOMO 1
H
I
IGP
J
IGP
IGP
E
I
AS: 220.2.0.0/16
IGP
IGP
IGP
C
IGP
EGP
SISTEMA
AUTÔNOMO 2
220.2.1.0/24
IGP e EGP
• IGP: Interior Gateway Protocols
• Informações de Roteamento no Interior do AS
– RIP: Routing Information Protocol
– OSPF: Open Shortest Path First
– IS-IS: Intermediate System to Intermediate System
• EGP: Exterior Gateway Protocols
• Informações de Roteamento entre ASs
– BGP: Border Gateway Protocol
Conceitos Básicos de Roteamento
• RIB (Router Information Base)
– conjunto de rotas configuradas no roteador
• origem estática
• protocolos de roteamento
• icmp (redirecionamento)
– pode conter mais de uma rota para o mesmo destino
• FIB (Forwarding Information Base)
– conjunto de rotas ativas (não ambiguas)
• pode conter o endereço MAC do próximo salto
– contém apenas as melhores rotas
Algoritmos de Roteamento
• Algoritmo de Roteamento Global
– tem conhecimento de toda estrutura da rede
• algoritmo de estado de enlace: LS (link-state)
• Algoritmo de Roteamento Decentralizado
– nenhum nó tem informação completa da rede
• algoritmo de vetor de distâncias: DV (distance vector)
3
5
2
2
3
2
1
1
Vetores de Distância
• A) Os roteadores divulgam as redes a que estão diretamente
conectados por seus enlaces
• B) Apenas as melhores ofertas são aceitas para cada rede.
• C) A rotas são propagadas com custo acrescido
rede A por B.1-A.1
acesso a rede
A com custo 1
1
B
acesso a rede
A com custo 2
2
rede A por D.1-C.3
1
rede A
2
A
C
2
acesso a rede
A com custo 1
X
1
D
3
rede A por C.1-A.2
1
acesso a rede
A com custo 2
Atualizações de Rota
• Por re-anuncio e temporização
– As rotas tem um tempo de vida (TTL)
– Os roteadores re-anunciam periodicamente suas rotas
– Rotas cujo re-anuncio não é recebido dentro do prazo de vida são
desativadas.
– Rotas de maior custo previamente ignoradas passam a ser
aceitas.
– O tempo de atualização das rotas é aproximadamente: nsaltos *
TTL
• Por atualizações (triggered updates)
– Quando um roteador detecta uma alteração em sua tabela ele reanuncia todas as suas rotas.
– Essa técnica reduz o tempo de atualização mas gera grande
carga de mensagens de atualização na rede.
Estado de Enlace
• Roteadores trocam informações sobre a topologia da
rede (roteadores, enlaces e redes).
– Cada roteador mantém um banco de dados completo com a
descrição de toda topologia da rede (link state database)
– Os roteadores só repassam informações para roteadores
parceiros (protocolo Hello - também usado como keep alive)
– Os roteadores parceiros sincronizam sua base de estado de
enlace através de mensagens LSA (Link State Advertisement)
hello
hello
Link State
Database
B
A
lsa
lsa
Link State
Database
Atualizações de Estado (Inundação)
• Quando um roteador recebe um LSA que não existe em sua base, ele
propaga a informação para todas as suas interfaces (menos a
interface por onde a LSA foi recebida)
– O mesmo ocorre quando o roteador detecta que um enlace deixou de
funcionar (através das camadas física ou enlace ou do protocolo Hello).
B
novo LSA
novo LSA
C
X
novo LSA
A
D
novo LSA
novo LSA
E
TTL e Número de Seqüência das LSA
• Um limite de idade (TTL) é atribuído às informações
anunciadas pelo LSA.
– As LSAs precisam ser renovadas periodicamente. As LSAs são
removidas quando o TTL é esgotado.
– Cada LSAs tem um TTL controlado por temporizadores individuais.
– As LSAs possuem também um número de seqüência que permite
distinguir anúncios novos de antigos.
3
4
5
2
6
1
-6
-5
-4
-3
-2
-1
7
0
8
13
9
12
11
10
contador
em pirulito
Divisão em Áreas
• Num protocolo LS os requisitos de memória crescem linearmente
com o número de enlaces (n) e o processamento cresce entre n*
log(n) e n2.
• Para prover escalabilidade em redes de grade porte, é utilizado a
estratégia de divisão por áreas.
área B
estado
completo
da própria
área
ABR: Roteador de
Borda de Àrea
ABR
ABR
resumo
resumo
das outras
áreas
área A
área C
Vetores de Caminho e políticas
• O roteamento por vetor de caminho (path vector) utiliza com estratégia
anunciar caminhos completos nos anúncios de rota.
– Essa estratégia permite anunciar rotas de acordo com políticas préestabelecidas.
– Utilizado nos anúncios de rota entre os S.A.s
Y
Z
200.17.1.0/24
X
200.17.1.0/24 via SA3
W
EGP
SA3
200.17.1.0/24 via SA3, SA2
200.17.1.0/24 via SA3, SA2, SA1
B
E
F
C
D
G
EGP
I
SA2
SA1
J
Conjunto de Caminhos
• Em alguns casos, os anúncios de caminho podem ser
agrupados em conjuntos.
SA3
Y
Z
200.17.0.0/25
X
B
200.17.0.0/24
seqüência {SA1},
conjunto {SA2, SA3}
W
E
200.17.128.0/25
F
C
D
G
EGP
I
SA2
SA1
J
RIP: Routing Information Protocol
• Originário do conjunto XNS da Xerox
• Duas Versões
– Versão 1: RFC 1058
• mensagens em broadcast
• não suporta CIDR (Classless InterDomain Routing)
– Versão 2: RFC 1723
• mensagens em multicast
• suporta CIDR
RIP
• Baseado em vetor de distâncias
• Transportado em mensagens UDP (Porta 520)
– Cada mensagem pode informar até 25 rotas
– Dois tipos de mensagem:
• Requisição (tipo 1): solicita informações de roteamento
• Resposta (tipo 2): envia informações de roteamento
• Indicado para redes de pequeno a médio porte.
– É muito simples de usar, mas torna-se ineficiente para redes
muito grandes.
– Custo baseado em saltos (hop count)
– Valor máximo 15 (acima deste valor, a rede é considerada
inalcançável)
Elementos de uma rede RIP
• Ativos: envia e escuta mensagens RIP
• Passivos: apenas escuta mensagens RIP
Rede 200.192.0.0/24
PASSIVO
Usualmente host
ATIVO
Usualmente roteador
Rede 200.134.51.0/24
Exemplo de Operação RIP
G,R,D
…
G: Gateway
R: Rede
D: Distância
REDE 1
G1
(G1,R5,3)
(G1,R5,3)
REDE 2
2
(G2,R5,4)
G2
G3
(G3,R5,2)
1
REDE 3
(G4,R5,5)
REDE 4
G4
REDE 6
(G5,R5,1)
G5
G6
(G6,R5,1)
REDE 5
…
Tabela de Roteamento
• Roteador G3
Destino
Next Hop
Metrica
Direto/
Remoto
Local/
RIP
Interface
REDE 1
REDE 2
REDE 3
REDE 4
REDE 5
REDE 6
G1
0
G2
0
G5
G2
2
1
2
1
2
3
R
D
R
D
R
R
R
L
R
L
R
R
2
2
2
1
1
2
Timers para Rotas
• As mensagens de rotas (responses in RIP) são enviadas
a cada 30 segundos.
• Time-out timer
– Inicializado todas as vezes que uma rota é criada ou atualizada.
– Se a rota não for atualizada em 180 segundos, ela é considerada
obsoleta.
• Garbage collection Timer
– As rotas que estiverem expiradas por mais de 120 segundos são
removidas.
RIP Request e Response
• Um gateway pode enviar uma mensagem para outro
solicitando a atualização de uma rota específica.
RIP REQUEST
RIP RESPONSE
RIP Versão 1: RFC 1058
• PROBLEMAS:
– Não propaga máscaras (só permite definir rotas segundo as
classes A, B e C).
– Envia mensagens em Broadcast.
– Não possui mecanismos de autenticação.
RIP Versão 2: RFC 1723
• RIP Versão dois suporta:
– Propaga as rotas utilizando mensagens de broadcast, ao invés de
multicast.
– Suporta a definição de rotas com uso de máscaras.
– Autenticação por:
• Message Digest (16 bytes MD5 da mensagem)
• Password Simples (senha de 6 bytes)
• Message Digest Key e Sequence Number (HMAC com chave
secreta)
– Em todos esses casos, a autenticação é colocada no início da
mensagem.
Formato das Mensagens RIP v2
Byte 2
Byte 1
Byte 3
Command
Version
(1: request, 2:
(2)
response)
Address Family
(0xffff para Autenticação)
Byte 4
Reserved
Cabeçalho
Tipo de Autenticação
Autenticação
Informação de Autenticação X 4
Address Family
(2 para IPv4)
Tag de Rota
Entradas de
Rota
....
IP Address
Subnet mask
Next Hop IP Address
Metric
Address Family
(0xffff para Autenticação)
Tipo de Autenticação
Informação de Autenticação X 4
Autenticação
Exemplo
• Inicialmente os roteadores tem apenas as rotas das redes
conectadas fisicamente a eles.
10.26.128.0
255.255.128.0
3
2
192.168.0.0
255.255.255.0
1
INTERNET
0.0.0.0
0.0.0.0
192.168.1.0
255.255.255.0
Propagação da Rota 0
• Inicialmente os roteadores tem apenas as rotas das redes
conectadas fisicamente a eles.
10.26.128.0
255.255.128.0
0.0.0.0 por 3
(custo 3)
3
2
0.0.0.0 por 1
(custo 1)
1
INTERNET
0.0.0.0
0.0.0.0
0.0.0.0 por 2
(custo 2)
192.168.0.0
255.255.255.0
192.168.1.0
255.255.255.0
Propagação da Rota 0
• Inicialmente os roteadores tem apenas as rotas das redes
conectadas fisicamente a eles.
192.168.0.0 por 3
(custo 1)
10.26.128.0
255.255.128.0
3
2
192.168.0.0 por 2
(custo 1)
1
INTERNET
0.0.0.0
0.0.0.0
192.168.0.0 por
2 (custo 1)
192.168.0.0
255.255.255.0
192.168.1.0
255.255.255.0
OSPF: Open Shortest Path First
• Versão Atual:v2
– RFC 2328 e RFC 1246
– Protocolo IGP por estado de enlace
– Único protocolo de roteamento dinâmico obrigatório para
roteadores.
• Protocolo de roteamento completo, mais flexível que o
RIP.
– RIPv2 permite apenas trabalhar com custo por número de saltos.
– OSPF permite utilizar técnicas mais genéricas para cálculo das
métricas das rotas.
Dijkstra Shortest Path First (SPF)
•
Princípio:
– Encontrar o menor caminho entre um dos nós da rede e todos os demais
• Se D pertence ao melhor caminho entre AF, então o melhor caminho é o
melhor AD + melhor DF.
• Custo: L*log(N) (L:enlaces e N:nós)
•
Estratégia:
– Escolher sempre o melhor nó adjacente
– Atribuir custos acumulativos a cada nó da rede
6
4
B
5
10
E
2
0
A
1
3
F
1
C
1
D
5
5
4
9
Constrained Shortest Path First (CSPF)
• Permite impor restrições adicionais ao invés de escolher
simplesmente o caminho mais curto
• As restrições podem ser de várias naturezas:
– restringir o uso de enlaces indisponíveis, pouco confiáveis ou
muito lentos (menos banda)
• Duas técnicas são utilizadas:
– Aparar enlaces indesejáveis (eliminá-los do grafo - prunning)
– Criar uma nova métrica que incorpora outras restrições em seu
cálculo
• Problema:
– Todos os roteadores precisam usar a mesma métrica, ou poderão
ser criadas rotas em loop.
Equal Cost Mutipath (ECMP)
• Geralmente, quando dois caminhos de custo idêntico são
encontrados, o primeiro a ser descoberto é mantido.
• Isso pode levar a uma sub-utilização da capacidade da
rede.
• No ECMP os roteadores procurar efetuam
balanceamento de carga entre caminhos de custo
idêntico.
– Roteadores que suportam ECMP criam regras automáticas de
balanceamento utilizando parâmetros como:
• O endereço de origem ou destino dos pacotes encaminhados.
• A marcaçao diffserv
• O tipo de tráfego transportado
Conceitos do OSPF
• Um roteador OSPF deve ter um identificador único em
todo o sistema Autônomo
– identificador de roteador: endereço IP de uma das interfaces
(geralmente o menor)
– identificador de área: exclusivo em um sistema autônomo
• Os seguintes métodos de autenticação são suportados:
– tipo 0: sem autenticação + checksum
– tipo 1: proteção adicional contra erro de configuração
– tipo 3: autenticação criptográfica MD5
Funcionamento do OSPF
•
Protocolo de Estado de Enlace
–
–
•
Protocolo OSPF é diretamente encapsulado no IP (protocolo
tipo 89).
São transmitidos em multicast para o endereço padrão:
224.0.0.5 e 224.0.0.6.
Mensagens do OSPF:
1.
2.
3.
4.
5.
Hello
Descrição do Banco de Dados
Solicitação do Estado de Enlace
Atualização do Estado de Enlace
Reconhecimento do Estado de Enlace
Mensagens OSPF
• Hello:
– usada para descobrir vizinhos e manter o relacionamento entre
eles
• DataBase Description:
– lista um diretório de entradas de estado de enlace
• LinkState Request:
– requisita uma ou mais informações específicas de estado de
enlace
• LinkState Update:
– envia a informação de uma ou mais entradas de estado de enlace
(LSA - Link State Advertisement)
• LinkState Acknowledgement:
– confirma o recebimento seguro da informação de estado de
enlace
Mensagens OSPF
Byte 2
Byte 1
Version (2)
Byte 3
Tipo de Mensagem
Byte 4
Tamanho da Mensagem
Identificador de Roteador
Identificador de Área
Checksum da mensagem
Tipo de Autenticação
Dados de autenticação
...
Reservado
ID de Chave
Tamanho da Autentic.
Número de sequência
Cabeçalho OSPF
Byte 2
Byte 1
Byte 3
Byte 4
Máscara de rede
Opções
Intervalo de Hello
Intervalo de morte do roteador
Roteador designado
Roteador designado de backup
Primeiro Vizinho
Outros Vizinhos
Mensagem Hello
Prioridade Roteador
Descoberta de Vizinhos
• Mensagem Hello
– Permite detectar novos vizinhos e verificar se estão ativos
– As mensagens são enviadas em intervalos de 10 segundos
– O intervalo de morte é geralmente 40 segundos
• Prioridade do Roteador
– Utilizado para eleger o roteador designado (designated router)
• o desempate entre prioridades é feito para o roteador com ID
mais alto
• Lista de Vizinhos
– Os vizinhos são identificados pelo seu ID (IP)
Mensagens OSPF
Byte 2
Byte 1
Byte 3
MTU da Interface
Byte 4
Opções
Reservado
I
M
Número de sequência da descrição do banco de dados
Identificador de Área
Idade do Estado de Enlace
Opções
Tipo do Est. Enlace
Identificador de Estado de Enlace
Roteador Anunciante
Número de sequência do Estado de Enlace
Checksum
Tamanho
Outros Cabeçalhos de Anúncio de Estado de Enlace
....
Database Description
S
Sincronismo com Banco de Dados
• O método OSPF exige que cada roteador possua uma
cópia idêntica dos estados de enlace da rede.
• Para evitar que informações em excesso sejam trocadas
pela rede, a seguinte estratégia é adotada:
– O roteador anuncia uma lista de enlaces que ele conhece
(DataBase Description)
• lista os identificadores de entrada da base, mas não envia os
dados propriamente dito
– O roteador que recebe o anúncio solicita apenas as entradas que
estão faltando (Link State Request)
– O roteador que fez o anúncio envia mensagens contendo os LSA
solicitados (Link State Update)
Mensagens OSPF
Byte 1
Byte 2
Byte 3
Byte 4
Tipo de Estado de Enlace
Identificador do Estado de Enlace
Roteador Anunciante
Outros Anúncios de Estado de Enlace Requisitados....
Link State Request (LSR)
Contador de Anúncios (número de LSAs)
Idade do Estado de Enlace (LS)
Opções
Tipo de LS
Identificador de estado do enlace
Roteador Anunciado
Número de Sequência de Estado do Enlace
Checksum do Estado de Enlace (LS)
Flags
Reservado
Tamanho
Número de Enlaces
Identificador de Enlace (IP ou Subrede)
Dado do Enlace (Máscara de Subrede)
Tipo de Enlace
Contador de TOS
Métrica Padrão
TOS
Reservado
Métrica do TOS
Link State Update (LSU = N X LSA)
Redes de Acesso Múltiplo
• Redes de acesso múltiplo são redes nas quais vários roteadores são
interconectados a um enlace compartilhado com suporte a broadcast
(multicast)
– Mensagens de Hello são enviadas em multicast (224.0.0.5)
– Anúncios de LSA são feitos ao roteador designado e ao roteador designado
de backup usando um endereço de multicast (224.0.0.6)
– O roteador designado distribui os anúncios usando o endereço de multicast
224.0.0.5.
Roteador Designado
Roteador
Designado de
Backup
meio de múltiplo acesso
Áreas OSPF
• No OSPF, áreas são organizadas em uma
hierarquia de dois níveis:
– área zero: backbone do AS
– demais áreas: conectadas ao backbone
• Os roteadores que conectam uma área ao
backbone são denominados: ABR
• Os ABR transmitem informações sumarizadas
para os demais roteadores da sua área.
• Se uma única área for utilizada, a quantidade de
roteadores é limitada (menos que 200 para
roteadores legados).
Terminologia OSPF
BACKBONE
OSPF
Area 0.0.0.0
Area 0
N1
Area 3
Roteador de
Fronteira de Área
(ABR)
R0
N2
R1
Fronteira
de AS
R3
Area 1
R2
R4
R8
R6
R5
Roteador de
Fronteira de AS
(ASBR)
R7
LSA NSA
N1
Area 2 (Stub)
Rx
Rede RIP
Terminologia OSPF
• Roteadores Intra-Area:
– Conhecem apenas a topologia de rede do interior de sua própria
área.
• Roteadores de Fronteira de Área (ABR)
– Conhecem duas ou mais áreas aos quais estão diretamente
conectados.
– Efetuam agregação de rotas utilizando CIDR (a agregação pode
ser ativada ou não)
• a agregação interfere no funcionamento do LDP (MPLS)
• Roteadores de Fronteira de AS (ASBR)
– Trocam informações com outros AS e podem pertencer a
qualquer área.
Tipos de Anúncio de Estado de Enlace
• No OSPF são utilizados 4 tipos de LSA:
– Tipo 1: Router-Link Entry
• Anúncios de Enlaces de Roteador
• Produzidos por todos os roteadores e são espalhados dentro de uma
única área.
– Tipo 2: Network-Link Entry
• Anúncios de Enlaces de Rede:
• Produzidos pelo roteador designado e são espalhados em uma única
área.
– Tipo 3 e 4: Summary-Link Entry
• Anúncio de Enlaces de Resumo:
• Produzidos pelos roteadores de fronteira de área ABR. Descrevem
rotas para destinos em outras áreas e para os roteadores de fronteira
de AS.
– Tipo 5: Autonomous System External Link Entry
• Anúncio de Enlaces de AS Externo
• São produzidos pelos roteadores de fronteira AS e são espalhados
por todos as áreas.
Tipos de Áreas
• Áreas Stub
– Utilizadas para proteger roteadores com pouca capacidade de CPU ou
memória
– Esse tipo de área é configurada no ABR, que propaga apenas uma rota
padrão para os demais roteadores da área
• Not So Stubby Area (NSSA)
– Uma LSA especial denominada LSA-NSSA é utilizada para propagar
rotas de uma área Stub para outras áreas que não suporte OSPF (por
exemplo RIP)
• Essa mensagem tem um campo adicional que permite apontar uma
gateway diferente do roteador anunciante.
• Enlaces Virtuais
– Permitem criar enlaces virtuais (não físicos) usados para aumentar a
conectividade da malha OSPF.
• Exemplo: interconectar duas áreas adjacentes utilizando um roteador
que não tem interface direta com a Área 0.
BGP: Border Gateway Protocol
• Função
– Troca de informação entre sistemas autônomos
• Criado em 1989
– RFC 1267
– Substitudo do EGP
• Utiliza mensagens de “update” para informar aos
roteadores sobre alterações nas tabelas de
roteamento.
EGP
SA3
IGP
Y
Z
•
ROTAS
•
•
200.17.0.0/16 por Z
200.18.0.0/16 por Z
IGP
X
IGP
W
IGP
EGP
200.17.0.0/16
200.18.0.0./16
•
ROTAS
•
•
•
210.7.0.0/16 por E
200.17.0.0/16 por E
200.18.0.0/16 por E
IGP
B
IGP
E
IGP
C
D
F
IGP
EGP
IGP
IGP
IGP
G
I
IGP
J
IGP
SA2
210.7.0.0/16
SA1
BGP
Mensagem de UPDATE
A
BGP
B
C
SISTEMA
AUTÔNOMO 4
E
F
G
H
D
SISTEMA
AUTÔNOMO 1
I
SISTEMA
AUTÔNOMO 2
BGP Speaker
SISTEMA
AUTÔNOMO 3
PROPAGAÇÃO DAS ALTERAÇÕES