PROTOCOLO DE ROTEAMENTO

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Roteamento
Prof. Mauro Tapajós
Roteamento
	Trata do encaminhamento da informação da origem até o destino desejado
	A seleção de uma rota normalmente é baseada em algum critério de performance (número de saltos até o destino, atraso, velocidade do link)
	Esquemas de roteamento vão depender do tipo de rede (comutada por pacotes ou circuitos)
HA
HB
R
R
R
R
R
Rede 1
Rede 2
Rede 3
Rede 4
Rede 5
Roteamento em Redes comutadas por Circuitos
	O roteamento em redes baseadas em comutação por circuitos é basicamente estático, rotas predefinidas são armazenadas nos dispositivos da rede
	Existe uma rota principal, caso ela esteja fora de serviço, é tentada outra das rotas definidas numa certa ordem de prioridades
	Esquema basicamente estático, onde as rotas são definidas manualmente, inclusive as rotas de “backup”
	Um exemplo é o roteamento de chamadas através de redes telefônicas
Roteamento na Rede Telefônica
	Características neste tipo de roteamento
		Tráfego estável e previsível
	Nós (centrais telefônicas) extremamente confiáveis
	Uma única organização controla a maior parte deste tipo de rede (pouca subdivisão)
	Rede muito capilarizada
	As conexões exigem a mesma quantidade de recursos de rede
Roteamento em Redes de Pacotes
Como se define os melhores caminhos de uma rede para outra?
Como se encaminha um pacote de uma rede para outra?
A
B
C
D
W
X
Y
Z
?
Roteamento em Redes de Pacotes
Através da interconexão de vários equipamentos capazes de encaminhar tráfego - Roteadores
A
B
C
D
W
X
Y
Z
R
A
B
C
D
W
X
Y
Z
R
R
Network
Cloud
Roteamento em Redes de Pacotes
	Características
		Roteadores e links com confiabilidade apenas razoável
	Grande diversidade de perfis de tráfego
	Os trechos da rede possuem vários diferentes donos (grande subdivisão)
	Capilaridade irregular e esparsa
Roteamento em Redes de Pacotes
	Em redes baseadas em circuitos virtuais, a escolha da rota é feita no momento de inicialização do circuito virtual
	Em redes baseadas em datagramas, uma rota é determinada para cada pacote de forma independente
	Roteamento é a decisão de qual caminho seguir
	Encaminhamento (forwarding) é o envio depois da decisão feita
	Routing ≠ Bridging
Roteamento em Redes de Pacotes
	Se A manda pacotes para E, B deve tomar uma decisão de encaminhamento com base nos endereços de rede dos pacotes
	Este endereço apenas define um destino e não o caminho a ser tomado
A
E
B
C
D
packet
?
?
Flooding (inundação)
	Uso de contadores de saltos
	Útil para mensagens de emergência (aplicações militares)
	Pode ser usada para se inicializar a rota de um circuito virtual, já que todas as rotas possíveis são tentadas
	Pode ser usada para disseminar informação importante para todos os nós da rede
Tipos de Algoritmo de Roteamento
	Distribuídos / Centralizados
	Baseados em um único caminho (single path) / vários caminhos (multi path)
	Plano ou hierárquico
	Decisões de encaminhamento nos hosts (source-routing) ou nos roteadores
	Intra-domínio ou inter-domínio
	Baseado em estratégias Link State ou Distance Vector (Bellman-Ford) 
Métricas
Usadas para o cálculo da melhor rota. Exemplos:
	Comprimento do caminho (path length)
	Confiabilidade (em termos de erros de bits ou números de quedas de links)
	Atraso
	Largura de banda
	Carga
	Custo de comunicação ($)
	Combinações
Princípio da Melhor Rota
	Se um roteador está no meio da melhor rota r entre outros dois roteadores, então a melhor rota dele para qualquer dos dois passa por r
	Dado um determinado destino, todas as rotas ótimas para este destino irão criar uma árvore (sink tree)
Algoritmos de Roteamento
	Estabelecem os caminhos para cada pacotes de acordo com certas regras
	Simplicidade, Robustez, Flexibilidade, Estabilidade, Otimização (convergência rápida)
	Algoritmos Não-adaptativos (Estáticos) – rotas pré-definidas, a informação de roteamento não é atualizada
	Algoritmos Adaptativos (Dinâmicos) – a informação de roteamento é atualizada periodicamente
Roteamento Estático
	Define rotas permanentes e fixas entre cada par origem-destino
	Baseado num dos algoritmos de baixo custo
	Estes algoritmos não podem se basear no estado da rede (variáveis dinâmicas como o tráfego)
	Não há muita diferença nos roteamentos de datagramas e de circuitos virtuais
	As tabelas de roteamento somente necessitam armazenar o próximo nó da rede que compõe a rota
	Baseia-se em volumes de tráfego estimado ou capacidades de links
Exemplo de Roteamento Estático
Algoritmos de Baixo Custo (Least-Cost)
	Dada uma rede conectada por enlaces bidirecionais entre seus nós e cada enlace possui um custo associado, o custo de uma determinada rota será a soma dos custos de cada enlace que compõe a rota
	O algoritmo deve encontrar a rota de menor custo entre cada dois nós da rede
	Dois algoritmos básicos: Dijkstra e Bellman-Ford
Dijkstra
	Algoritmo desenvolvido em 1959
	Determina os menores caminhos entre um dado vértice A e todos os demais
	Inicia um conjunto S somente com o nó de origem A e parte para os outros
	A cada iteração: agrega o nó de um conjunto W de nós ligados diretamente a S, com menor custo para A
Algoritmo de Dijkstra - Exemplo
Algoritmos de Roteamento Rede de Exemplo
Algoritmo de Dijkstra Exemplo
Algoritmo de Bellman-Ford Exemplo
Algoritmos de Dijkstra e Bellman-Ford
Passos dos Algoritmos
Roteadores
	Roteadores são equipamentos que operam na camada de rede, comutando pacotes 
	Os roteadores dividem a rede em regiões, cada qual com o seu número de rede único
	Os cabeçalhos MAC mudarão constantemente durante a travessia do pacote pelas redes, logo as decisões de encaminhamento deverão se basear em endereços de rede
Rede A
Aplicação
Transporte
Rede
Interface
de Rede
Host B
Rede
Interface
de Rede
Roteador
Rede
Interface
de Rede
Roteador
Rede B
Rede C
Aplicação
Transporte
Rede
Interface
de Rede
Host A
Roteadores
	Em hosts – a informaçao de roteamento é parcial (normalmente 2 rotas: uma direta e uma default)
	Em roteadores – é exigida uma informação maior sobre a topologia
	As tabelas dos roteadores contém basicamente entradas para os hosts locais e as redes remotas
	O último roteador no caminho para o destino encaminhará o pacote diretamente para o seu destino
	O roteamento é feito com base no endereço de rede apresentado no cabeçalho do pacote
	Roteadores são essencialmente dispositivos de rede de camada 3
	Deve saber tratar itens como: esquemas de endereçamento, MTU’s e interfaces
Roteadores Multiprotocolos
	LAN´s de hoje podem trabalhar com vários protocolos (Apple Talk, TCP/IP, IPX)
	Ter um roteador para cada tipo de protocolo é ineficiente
	Ao receber um pacote, o roteador o analisa e passa para o processador de protocolo correspondente
Tabelas de Roteamento
	Uma requerida para cada roteador
	Entradas para cada rede alcançável e não para cada destino (inviável!)
	Cada entrada mostra o próximo nó na rota – não toda a rota
	Podem existir em hosts
	No caso normal, hosts apenas definem um roteador (default gateway) padrão para onde devem ser encaminhados os pacotes para uma rede externa a sua própria
	Se houverem vários roteadores
ligados na rede do host, ele então deve ter tabelas de roteamento para definir para qual deles enviar
Tabelas de Roteamento IP
	Roteadores mantém tabelas nas quais as entradas são endereços IP
	Cada entrada indica o próximo nó a ser seguido e não toda a rota definida
	Visando reduzir estas tabelas, suas entradas são da forma:
	Endereços de redes remotas (rede, 0)
	Endereços de hosts locais (esta rede, host)
	Endereços de subredes remotas (esta-rede, subrede, 0)
	Endereços de hosts locais na subrede local (esta-rede, esta-subrede, host)
Buscas em Tabelas de Roteamento IP
	Busca por um endereço de host idêntico – flag H
Tenta reconhecer um host dentre os que estão diretamente ligados no roteador
Se encontrar encapsula diretamente num quadro com endereço MAC do host e envia no segmento de rede
	Busca por um rede remota de mesmo endereço
Necessidade de conhecimento de máscaras de rede
Se encontrar encapsula diretamente num quadro com endereço MAC igual ao do próximo nó da rota
	Busca por uma entrada default
Permite que uma única entrada seja usada para uma lista de entradas com mesmo próximo nó
Tabela de Roteamento em R2
N2
N3
N4
N1
R1
R2
R3
N1
N2
N3
N4
R1
Entrega Direta
Entrega Direta
R3
Dest
Próximo Nó
Tabelas de roteamento reais contém endereços IP, flags indicando o tipo de entrada, máscaras de subrede, e outras informações
Tabelas de Roteamento IP - Exemplo
Agregação de rotas com CIDR
	Nas redes de pacotes, normalmente se usa algum tipo de técnica de roteamento dinâmico
	Isto quer dizer que as decisões de roteamento variarão com as mudanças em parâmetros da rede
	Estes parâmetros usualmente são falhas na rede e condições de congestionamento
	Para ser dinâmico e distribuído, o roteamento depende de troca de mensagens feita pelos nós a rede
	Aspectos devem ser levados em conta (processamento adicional, overhead e velocidade de resposta)
Algoritmos de Roteamento Dinâmico
	A determinação da rota pode se basear numa variedade de métricas (valores derivados de computações de uma determinada variável como, por exemplo, atraso) ou até combinações de métricas
	Assim, existirá a necessidade de um protocolo para fornecer e atualizar esta informação
	Roteadores podem então tomar suas decisões de encaminhamento com base na topologia e nas condições da rede
Algoritmos de Roteamento Dinâmico
Algoritmos de Roteamento Dinâmico
	Algoritmos de roteamento estático - Implementação fácil, mas e se um link cai ou determinada região fica inacessível em virtude de congestionamento?
	Algoritmos de roteamento dinâmicos – hosts e roteadores continuamente trocam informação e encontram os melhores caminhos entre dois pontos, reagindo a mudanças na rede
	Podem se ajustar a condições de queda de links ou congestionamento, mas:
	A informação a mais de roteamento cria tráfego extra – overhead (indesejável)
	Loops de pacotes podem ocorrer enquanto a informação de roteamento estiver sendo trocada
	“Fluttering” – enquanto os roteadores tentam “entender” o que está acontecendo, podem enviar pacotes para um mesmo destino por rotas diferentes tentando balancear rotas, ou mesmo tratando links bidirecionais de forma distinta dificultando e confundindo o gerenciamento da rede e as aplicações de rede em execução (as que usam TCP por exemplo)
Algoritmos de Roteamento Dinâmico
	Protocolos de roteamento não serão a solução para problemas de congestionamento ou quedas de links (apenas podem amenizar o problema) mas podem, depois da mudança, corrigir as rotas previamente usadas para que se ajustem à nova realidade
	Maior necessidade de processamento em função de decisões de roteamento mais complexas
	Melhoram performance do ponto de vista do usuário
Estratégias para Algoritmos de Roteamento Dinâmico
Com base nas fontes de informação, podemos ter:
		Estratégias locais:
	Roteamento através da saída com menor fila de pacotes no roteador
	Balanceamento de carga
	Podem ser estratégias equivocadas e raramente são usadas
	Informações trocadas entre todos os nós
	Algoritmos de Link-state
	Informações trocadas entre nós vizinhos
	Algoritmos de Distance vector
Algoritmo de Distance Vector
	Também chamado Bellman-Ford distribuído
	Cada roteador mantém uma tabela indexada para cada outro roteador da rede
	Cada entrada na tabela possui um destino, uma métrica e a linha de saída correspondente
	As métricas podem ser várias: o número de saltos, o tamanho das filas ou o atraso para um pacote chegar ao destino
	A informação de roteamento é atualizada por trocas das tabelas entre os nós da rede
Algoritmo de Distance Vector
(Exemplo)
Algoritmo de Distance Vector
Problema da Contagem ao Infinito
Problema da Contagem ao Infinito Soluções Alternativas
	Split Horizon: alternativa que evita enviar informações de determinado destino de volta à interface que informou sobre este mesmo destino.
	Poison Reverse: ao invés de não enviar as informações na interface como descrito acima, se envia a informação de que o destino é inalcançável (custo = infinito). Esta alternativa quebra imediatamente possíveis loops de rotas.
Algoritmo de Distance Vector
	Problema da contagem até infinito (reação lenta a falhas na rede)
	Converge lentamente depois de uma mudança na topologia (sempre os roteadores devem recalcular suas tabelas para encaminhar a informação de roteamento)
	Originalmente usado na Arpanet (e na internet - RIP)
	São fáceis de se implementar mas geram muito overhead, comparado com outras alternativas
Algoritmo de Link State
	Identifica cada roteador individualmente
	Determina o custo para cada roteador vizinho
	Monta um pacote com os custos para cada vizinho (enlace) – LSP – Link State Packet
	Um LSP contém:
	Identidade do remetente
	Número de sequência e idade (age)
	Lista de vizinhos e custos
	Um número de sequência e uma idade em cada pacote previne pacotes velhos de serem aceitos
Algoritmo de Link State
	A troca de mensagens LSP’s utiliza flooding (no caso de roteadores em LAN’s são usados endereços multicast para todos os roteadores)
	LSP’s são enviados periodicamente ou em reflexo à variações na rede como
	surgimento de um novo vizinho
	queda de um enlace
	mudança no custo de um enlace
	Substituiu algoritmos de DV na Arpanet (não levavam as taxas de bits em conta e demoravam para convergir) 
	Alguns protocolos que o utilizam: OSPF (internet), IS-IS (ISO)
Comparação dos Algoritmos Dinâmicos
	Link State converge mais rapidamente que Distance Vector (não necessita recalcular as tabelas a serem encaminhadas, simplesmente encaminham os LSP’s recebidos)
	Um roteador com problemas desestabiliza os dois algoritmos na mesma escala
Protocolos de Roteamento
	Apesar de roteamento ser uma tarefa da camada de rede, protocolos de roteamento se preocupam na troca de informações de roteamento entre os pontos da rede e assim são protocolos de aplicação
	Um protocolo de roteamento deve resumir a informação de roteamento e divulgá-la da maneira mais eficiente possível
	A maneira como um roteador analisa a tabela de roteamento não muda, o que muda é a forma como as entradas desta tabelas são geradas e alteradas
Protocolos de Roteamento
	Um roteador recém inicializado pede informação da rede aos outros roteadores (noção de topologia)
	Os outros roteadores respondem enviando informação de roteamento
	O roteador usa estas informações para gerar uma primeira tabela de roteamento e se insere no processo divulgando suas próprias informações para os demais de forma dinâmica
	A troca das informações é contínua e as novas tabelas
geradas podem refletir o que está acontecendo com a rede
Routing Information Protocol (RIP)
	É um IGP (RFC 1058) originalmente criado para a Xerox (XNS)
	Posteriormente associado com o UNIX e TCP/IP e normalmente implementado no routed dos sistemas UNIX BSD (aceitação pelo mercado)
	É uma versão distribuída do algoritmo de Bellman-Ford
	Adequado a redes pequenas
	Somente possui uma única métrica: saltos
Routing Information Protocol (RIP)
	Identifica participantes ativos (roteadores) e passivos (hosts)
	Baseado no algoritmo de distance vector
	O vetor é o número da rede
	A distância é o número de saltos para a rede
	Um salto é considerado uma travessia por um roteador
	O protocolo possui dois tipos básicos de mensagens: request (1) e reply (2)
	Um request enviado pede aos vizinhos que enviem parte (se indicados os destinos) ou toda a sua tabela de roteamento por um reply
	Uma mensagem de reply também é enviada a cada 30 segundos ou quando há alteração na tabela de roteamento (atualização) o que pode causar problemas como uma avalanche de broadcasts
Formato de Mensagem RIP
	São transmitidos em datagramas UDP para a porta 520
	Tem tamanho máximo de 512 octetos, acima disso a informação de roteamento deve ser dividida em vários datagramas (25 rotas em cada um)
Formato de Mensagem RIP
RIP
	Redes diretamente conectadas tem métrica de 1 e a métrica máxima tem valor 16 (infinito)
	Cada rota na tabela possui um temporizador
	2 tipos de participantes: ativos (somente roteadores) e passivos (só “ouvem” as mensagens)
	Aceita atualizações de qualquer dispositivo (pode ser confundido por qualquer um)
	RIP não prevê máscaras de subrede
	Projetado para redes medianas (centenas de nós) razoavelmente estáveis
	Existem versões incompatíveis de RIP para TCP/IP, NetWare e AppleTalk
RIP-2
	Descrito na RFC 1723
	É uma ampliação do RIP versão 1
	Seu objetivo: poder ser usado em redes medianas, onde se utilizam subredes variáveis e ainda apresentar interoperabilidade com RIP 1 e CIDR
	Oferece autenticação simples e suporte a multicasting
	Utiliza os campos nulos que não são usados por RIP-1
	Route tag: informação sobre a origem da rota
	Assim, implementações de RIP-1 devem ignorar estes campos para que ambos possam operar juntos corretamente
Formato da Mensagem RIP-2
OSPF (Open Shortest Path First)
	É um protocolo IGP baseado no algoritmo de Link State (RFC 2328)
	Derivado de uma versão preliminar do protocolo de roteamento OSI IS-IS
	Um nó pode ser um roteador ou uma rede
	Um custo é associado a cada interface de saída de cada roteador
	OSPF utiliza o IP diretamente (e não sobre UDP ou TCP) com campo protocol igual a 89
OSPF
	Suporta diferentes métricas
	OSPF pode calcular um conjunto de rotas específicas para cada tipo de serviço IP (type-of-service)
	Permite balanceamento de carga entre rotas de mesmo custo
	Suporta máscaras de subrede de tamanho variável
	OSPF suporta 3 tipos de conexões:
	Enlaces ponto-a-ponto entre roteadores
	Redes multiacesso com broadcasting (LAN’s)
	Redes multiacesso sem broadcasting (WAN’s)
OSPF - Exemplo de Rede e seu Grafo
Áreas OSPF
	OSPF pode dividir AS’s muito grandes em áreas (uma rede ou conjunto de redes contíguas) para diminuir o banco de dados da topologia (hierarquização)
	São identificadas por um número de 32 bits e os roteadores também
	Sempre existirá uma área backbone de identificador 0 que liga todas as áreas → topologia estrela
	Elas não se sobrepõem, mas um roteador pode não fazer parte de uma área
	Cada área roda uma instância do algoritmo de LS - a informação de topologia está limitada naquela área (mensagens do protocolo de roteamento estarão também confinadas naquela área - menor overhead)
OSPF
Mensagens OSPF
	Utiliza multicast para não sobrecarregar a rede (endereço 224.0.0.5 – AllSPFRouters)
	Usa Dijkstra para calcular as melhores rotas
Operação OSPF
	Ao inicializar, cada roteador:
1. Determina o custo de cada uma de suas interfaces
2. Descobre/alerta seus vizinhos através de uma mensagem de HELLO
3. Anuncia seus custos para os outros roteadores na topologia (mensagem LINK STATE UPDATE)
	quando ocorrer uma mudança nos links, os custos são recalculados e reanunciados para todos os roteadores → LINK STATE UPDATE
	Cada roteador deve confirmar as atualizações recebidas
	Cada roteador de posse destas informações é capaz de gerar os caminhos de menor custo para cada rede de destino - pode usar qualquer algoritmo de roteamento estático (como Dijkstra)
Roteador Designado
	Roteadores numa mesma LAN não precisam se falar todos entre si 
	→ um roteador designado fará o papel de nó central para os demais
	O protocolo funciona com a troca de mensagens entre roteadores adjacentes apenas (economia de banda)
Cabeçalho Comum de Mensagens OSPF
Cabeçalho de Mensagens OSPF
	Versão: atualmente igual a 2
	Tipo: um dos 5 tipos de mensagens OSPF
	Comprimento do pacote: em octetos incluindo o cabeçalho (+24 bytes)
	Router ID: 32 bits
	Área ID: 32 bits
	Tipo de autenticação: ausente, password ou encriptação
	Dados de autenticação: usados no procedimento de autenticação
OSPF - Mensagem Hello
	São enviadas periodicamente em cada enlace do roteador para verificar a vizinhança, mas nunca são repassados
	O roteador designado (o de maior prioridade) será o responsável pelo envio de anúncios da rede em questão
OSPF - Mensagem Database Description
	Inicializam a idéia de topologia do roteador por que enviam a base de dados de topologia de cada um
	Como a base de topologia pode ser muito grande, muitas mensagens podem ser usadas (campos I, M e seq. number)
OSPF – Mensagem
Link Status Update
	As informações de estado do enlace são trocadas (ou pedidas com link state request) pelos roteadores OSPF para que os bancos de dados de topologia sejam mantidos
	Tabelas da rede sob as métricas de atraso, velocidade e confiabilidade podem ser usadas independentemente de acordo com o type-of-service (roteamentos independentes)
Anúncio (enlace de roteador, rede, resumo ou AS externo)
IGRP
	Interior Gateway Routing Protocol
	É um protocolo proprietário de roteamento baseado no algoritmo de distance vector desenvolvido nos anos 80
	Adequado em redes IP mas também portado para outras como CLNP
	Utiliza uma combinação de métricas na decisão roteamento
EIGRP (Enhanced Interior Gateway Routing Protocol)
	Evolução do IGRP
	Baseado em relacionamentos entre roteadores vizinhos (mensagens hello)
	Hello de 5 seg (links alta velocidade) e 60 seg (links baixa velocidade) – ajustável
	Sempre lida com os endereços primários das interfaces
	Métricas: basicamente largura de banda e atraso total - é aplicada uma fórmula específica
	Quando for necessário a informação de uma rota específica, pode ser enviada somente parte da tabela pelo vizinho e não toda ela
EIGRP
	Pode armazenar várias rotas de mesmo custo ou não para fazer balanceamento de carga proporcionalmente
	Evita loops com “split horizon” e “poison reverse” 
	Pode ser configurado para utilizar parte do link e não todo em casos de links de baixa velocidade
VRRP – Virtual Router Redundancy Protocol
	Encapsulado diretamente no IP
	Como um end-host descobre o next-hop para um destino?
	R.: Prot rot dinâmico, ICMP router discovery, rota estática (default gateway)
	Rota padrão para o “roteador virtual”
	Um roteador master assume depois de eleição
	Incompatível com HSRP (Cisco)
	Escopo → LAN
	Usa multicast
	Só IPv4
	VR → VR ID + IP's associados
VRRP cenário simples
	Só 1 VRouter
	Anúncios VRRP periódicos
End origem IP primário
	End MAC origem → MAC virtual
	É possível load splitting
VRRP – Cenário 2 – 2 VRouters
VRRP
	O MAC do VR tem o seguinte formato:
	00-00-5E-00-01-{VRID} (hex - internet standard bit-order)
	Os 3 primeiros octetos são derivados da OUI IANA
	Os 2 seguintes (00-01) indicam que é um AC VRRP
	{VRID} é o indetificador do VR
	Até 255 roteadores VRRP na rede
Mobilidade IP
	Muitas das novas tecnologias pressupõem mobilidade dos equipamentos
	Esquema de endereçamento IP na Internet dificulta esta mobilidade – na Internet o endereçamento está relacionado com a topologia da rede
	Impossível manter tabelas de roteamento para cada host na Internet
	Um grupo de trabalho do IETF (atualmente na RFC 3344) estuda mecanismos para que seja possível a mobilidade em redes IP de forma automática
	Características desejadas: transparência, interoperabilidade com as versões atuais de IP (IPv4) e segurança
	Não prevê movimentação em alta velocidade como celular (geração de grande overhead)
Mobilidade IP - Endereços
	É independente de tecnologia de transmissão
	Um host terá 2 endereços (primário fixo e um secundário temporário)
	Duas possibilidades de se trabalhar com 
	os dois IP’s
		Co-located care-of address – aplicações usam o IP primário e a camada 2 usa o secundário
			Pode-se usar a infra-estrutura como ela é
	Exige software mais robusto no equipamento móvel
		Foreign agent care-of address - exige um participante ativo na rede estrangeira (foreign agent) como um roteador ou servidor específico
Mobilidade IP
Mobilidade IP - Registro
	Um agente estrangeiro envia mensagens de anúncio periodicamente (advertisements - uma mensagem ICMP Router Discovery alterada)
	Um host móvel deve se cadastrar com o agente estrangeiro na rede sendo visitada
	É usada porta UDP 434
	Ele deve encaminhar o pedido de encaminhamento de pacotes para o seu home agent via o foreign agent
	Ele deve então conseguir um IP care-of para esta rede
Mobilidade IP - Operação
	O endereço co-located care-of IP pode ser o do próprio agente estrangeiro que seria seu responsável nesta rede (economia de endereços) ou de um serviço como DHCP
	Quando o visitante for se comunicar o endereço de origem a ser usado é o seu primário (necessidade de acordo com o ISP)
	Assim, toda resposta para ele será encaminhada para a rede home, e o home agent deve encaminhar para o túnel
Mobilidade IP – 2X Problem
	O tunelamento tem o final no agente estrangeiro ou no próprio host móvel (se ele obteve um IP de um serviço externo como o DHCP)
	O uso de proxy ARP pelo foreign agent na rede remota permite a entrega direta de pacotes sem passar pelo túnel
	Visa também evitar o ponto de falha que seria o home agent
Mobilidade IP
	Broadcast na rede original do host pode ou não ser encaminhado para o host móvel
	Na volta à rede original o host deve corrigir sua tabela de roteamento antes de retirar seu registro
	Necessidade de padronização de mecanismos de segurança (RFC 2002 propõe MD5 chaveado para autenticação e sugere outros mecanismos para casos em que privacidade for necessária)
Roteamento Multicast
	Roteamento multicast tem encaminhamento diferente do roteamento unicast
	O roteamento multicast se altera com a inclusão/saída de um host do grupo multicast
	Para encaminhar pacotes multicast, os roteadores devem examinar mais do que simplesmente o endereço de destino
	Um datagrama multicasting pode ser gerado por um host que não faz parte do grupo e passar por redes que não possuam membros deste grupo
Roteamento Multicast
	Os caminhos que levam um datagrama multicast da sua origem até todos os membros do grupo formam uma “árvore de distribuição”
	Para cada origem possível existe uma árvore de distribuição
	A informação de grupos/membros deve ser conhecida pelos roteadores a todo momento mas existe a preocupação de não afogar a rede com estas atualizações
	Não há ainda um mecanismo de multicasting sendo largamente adotado na Internet
Transmissão e Roteamento Multicast
	Necessidade de criação de uma árvore multicast da origem para o destino, passando por todos os segmentos onde existam estações do grupo multicast (spanning tree)
	Os pacotes são transmitidos pela origem e seguem sendo replicados em todos os segmentos que compõem o caminho de forma que um pacote chegue para cada segmento, INDEPENDENTE DO NÚMERO DE ESTAÇÕES DO GRUPO NO SEGMENTO
	Com isso se reduz o tráfego necessário
	Para fazer parte de um grupo, cada novo participante deve sinalizar isso de forma dinâmica para os roteadores que o atendem (IGMP)
	Os roteadores devem trocar informação sobre que segmentos contém elementos do grupo
	Com isso montam as árvores com os caminhos multicast
	Para esta troca de informação eles necessitam de um protocolo de roteamento multicast
Tabelas de Roteamento Multicast
	As tabelas de roteamento multicasting terão entradas do tipo:
			(grupo multicast, origem), sendo a origem normalmente um endereço de rede
	Para reduzir estas tabelas, os protocolos de roteamento usam prefixos para as origens possíveis
Roteamento Multicast
Mecanismos de Roteamento Multicast
	RPF - Reverse Path Forwarding – o roteador que recebe o datagrama multicast analisa se ele foi recebido pela interface coerente baseado na sua tabela de roteamento comum gerada por algum algoritmo de roteamento unicast. Se positivo, ele é replicado nas demais interfaces
	TRPF - Truncated Reverse Path Forwarding – sofisticação do algoritmo acima que evita o broadcast nas interfaces registrando que grupos são acessados por quais interfaces
	DVMRP – Distance Vector Multicast Routing Protocol
	Semelhante ao RIP – não pegou
	RPM - Reverse Path Multicast
	Melhora o TRPF “podando” ou “enxertando” ramos na árvore (mais dinâmico) – grafts requests
	data-driven (só divulga a informação de grupos quando chegam datagramas para aquele grupo)
Roteamento Multicast
	Core-based Trees
	Cada região possui um core-router (raiz)
	Árvores spanning tree criadas com centro (core ou root) aproximadamente no centro do grupo
	Pacotes para o grupo são enviados para o core que os encaminha pela árvore.
	Demand driven – só depois de ativado o envio se recebem pacotes
	MOSPF – Multicast Extensions to OSPF
	Demand-driven
	Trata multicast dentro de uma área
	Usa ABR (area border router) para propagar informação para fora da área
Roteamento Multicast - PIM
	PIM – Protocol Independent Multicast
	Dense Mode (DM) → adequado a LAN's
	Abordagem broadcast and prune
	Depende de uma instância de roteamento unicast (ao contrário de DVMRP)
	Não é muito escalável (assim como DVMRP)
	Sparse Mode (SM) → adequado a WAN's
	Semelhante a CBT
	Root → rendez-vous point
	Também tem problemas de escalabilidade
Roteamento Multicast - MSDP
	MSDP – Multicast Source Distribution Protocol
	Idéia básica: túneis entre os vários RPs dos domínios
	MSDP é usado para divulgar informações de grupos multicast entre os RPs
Engenharia de Tráfego
	Baseada no conceito de encontrar rotas adequadas de acordo com exigências de serviço adequadas
	Exige um protocolo de troca de informações de rotas
	Protocolos de roteamento com extensões apropriadas para divulgação de rotas e recursos disponíveis na rede
	Constraint-based routing - CBR - capacidade de encontrar caminhos com base em mecanismos de otimização e critérios de restrição
	Suporta critérios relacionados com recursos disponíveis (por exemplo: banda disponível) e também relacionados com aspectos administrativos (por exemplo: clientes VIP)
	Suporte a rotas hot stand-by
	RSVP pode estabelecer caminhos sobre uma rede
MPLS com base em critérios CBR
	Pode-se ainda estabelecer rotas manualmente
Core Routing
	Sistema de roteamento baseado em várias redes onde existe uma região core para troca de tráfego entre estas redes
	Adequado para redes onde exista um backbone centralizado
	Toda a informação sobre destinos estaria armazenada nos core routers
	Não é adequado para a Internet
Roteamento Interno e Externo
Roteamento Hierárquico
	Em redes de tamanho maior, ter um entrada para cada destino-roteador possível torna-se uma realidade inviável
	Uma forma de reduzir tabelas de roteamento é hierarquizar a estrutura de forma que as tabelas sejam resumidas
Roteamento Hierárquico
Autonomous System - AS (Sistema Autônomo)
IGP – Interior Gateway Protocol
EGP – Exterior gateway Protocol
AS
AS
Roteamento de Borda
	Protocolos baseados puramente em distance vector ou link state não são efetivos para roteamento exterior
	Assumem que todos os roteadores compartilham as mesmas métricas
	Podem existir diferenças de prioridades e restrições entre AS’s (diferentes políticas implementadas)
	Uso de flooding de informação de link state pode se tornar intolerável
	Protocolos de roteamento exterior devem propagar:
	Informação de que redes são alcançadas e por cada roteador
	Informação de quais AS’s devem ser atravessados para se chegar até elas
	Este tipo de informação permite a implementação de políticas de roteamento
Roteamento de Borda
	AS's normalmente pertencem a uma organização mas o roteamento externo ultrapassa estes domínios
	Apesar dos roteadores trocarem informação de roteamento, é impraticável que todos os roteadores de um rede grande pertençam a um mesmo nível de roteamento externo
	É utilizado então um mecanismo que processe informações de roteamento dentro do AS (IGP) e um outro que processe entre AS’s (EGP)
	Esta estrutura oferece uma hierarquia de vários níveis para roteamento na Internet
	Dentro de um AS existe a liberdade de se escolher a arquitetura de roteamento interna
Roteamento de Borda
Roteamento de Borda
	AS's normalmente pertencem a uma organização mas o roteamento externo ultrapassa estes domínios
	Apesar dos roteadores trocarem informação de roteamento, é impraticável que todos os roteadores de um rede grande pertençam a um mesmo nível de roteamento externo
	É utilizado então um mecanismo que processe informações de roteamento dentro do AS (IGP) e um outro que processe entre AS’s (EGP)
	Esta estrutura oferece uma hierarquia de vários níveis para roteamento na Internet
	Dentro de um AS existe a liberdade de se escolher a arquitetura de roteamento interna
Autonomous System - AS (Sistema Autônomo)
AS
Roteamento nos AS’s
	Um AS é um conjunto de redes e roteadores que são vistas como um unidade do ponto de vista do roteamento: é uma porção lógica de redes IP maiores
	O roteamento realizado dentro de um AS (interno) se difere do realizado fora
	Foram desenvolvidos protocolos de “borda” para lidarem com o roteamento entre AS’s (EGP’s)
	Os EGP’s oferecem o suporte a políticas de roteamento (opções configuradas em cada rotedor – não fazem parte do protocolo)
Roteamento nos AS’s
BGP (Border Gateway Protocol)
	É um EGP desenvolvido para internets TCP/IP e substitui o velho protocolo EGP (Arpanet)
	A versão atual é a BGP-4 (RFC 1771)
	BGP é baseado em 3 procedimentos básicos:
		Neighbor acquisition (aquisição de um vizinho)
	Neighbor reachability (alcance do vizinho)
	Network reachability (alcance da rede)
	O protocolo não se preocupa em como um roteador saberá da existência de um outro roteador ou mesmo como ele decidirá que deve trocar informação com este roteador
BGP (Border Gateway Protocol)
	Exige confiabilidade rodando sobre TCP (porta 179)
	Não é um protocolo puramente baseado em Distance Vector nem Link State (alguns, como Tanenbaum, o consideram DV)
	Não realiza sempre trocas completas de informação: uma vez somente isto é feito e depois são trocadas informações incrementais
	Além das informações de destino e próximo salto (normalmente em termos de AS's), são trocados também informações dos AS’s que compõem os caminhos
BGP (Border Gateway Protocol)
	Suporta CIDR
	Permite implementação de políticas de roteamento
	Reduz uso de banda – agrega rotas
	Maior flexibilidade
	Foi projetado para evitar loops de topologia (usa informações de caminho completas – path attributes)
	Sujeito aos problemas de segurança comuns em aplicações sobre TCP
Sessões BGP
	Sessões eBGP – roteadores em AS's diferentes
	Sessões iBGP – roteadores no mesmo AS
	Estabelecidas através de conexões TCP entre pares BGP
	Trocam rotas (prefixo/destino + atributos BGP)
	Atributos importantes:
	AS-PATH: sequência de ASN's (AS number)
	NEXT_HOP: IP do roteador de borda (uso no caso de vários caminhos para o mesmo destino)
Tipos de mensagens BGP
	O procedimento de aquisição de um vizinho é feito pelo envio de uma mensagem “open”
	Se o outro roteador responder com um “keepalive” é sinal de que ele aceita a criação de um relacionamento
Relacionamento BGP
	Cada um dos roteadores envia um open sobre a conexão TCP (porta 179) e recebe como resposta uma mensagem keepalive
	Para o relacionamento entre os dois roteadores permanecer ativo (alcance do vizinho), devem ser enviadas mensagens keepalive periodicamente
	O campo Marker é acordado entre as partes e pode ser usado para sincronização ou até autenticação básica (o protocolo de transporte não define início e fim)
BGP – Mensagem Open
	A mensagem open carrega a identificação do roteador e do AS que ele está
	Hold timer: parâmetro incluído na mensagem de open para indicar o intervalo máximo entre duas mensagens de keepalive
	Version (= 4)
	BGP ID: identifica o roteador. Único para vários AS. Deve ser um de seus IP's.
	Parâmetros opcionais: somente 1 definido, tipo de autenticação (para evitar que os mecanismos de autenticação sejam parte do BGP)
BGP – Mensagem Update
	O procedimento de alcance de uma rede é realizado pelo broadcast de mensagens Update nas conexões 
	Ela disponibiliza para os vizinhos informações de rotas válidas na internet (Path Attributes) e de rotas/destinos a serem desconsiderados (withdrawn routes)
	Normalmente em cada AS poucos, ou somente um roteador, implementará BGP
	Uma mensagem de notificação somente é enviada em caso de detecção de erros na operação do protocolo
	Endereços IP são representados uma máscara numérica de 1 byte e por 1,2,3 ou 4 bytes do end. IP (dependendo da máscara))
BGP
	Normalmente as mensagens de update são criadas de forma que os Path Attributes sejam válidos para todos os destinos informados na mensagem (fatoração)
	Path Attributes:
		A origem da informação (IGP ou EGP)
	Os AS’s que estão no caminho da rota (políticas de roteamento)
	O próximo roteador de borda no caminho (lembre-se que o caminho pode conter roteadores que não implementam BGP)
	Outras informações: múltiplas entradas no AS, preferências locais (interesse de roteadores internos somente) e rotas agregadas
	Pode agregar rotas
Protocolos de Roteamento OSI
	ES-IS - End System to Intermediate System
	Usado com CLNP (Connectionless Network Protocol)
	Troca de informações de roteamento com os sistemas finais (hosts)
	IS-IS - Intermediate System to Intermediate System
	Roteamento intra-domínio
	Herança DECNet
	Redes Novell: NLSP (variante do IS-IS)
	IDRP - Inter-Domain Routing Protocol
	Roteamento inter-domínio
Click to edit the title text format
	Click to edit the outline text format
	Second Outline Level
	Third Outline Level
	Fourth Outline Level
	Fifth
Outline Level
	Sixth Outline Level
	Seventh Outline Level
	Eighth Outline Level
	Ninth Outline Level
	Redes Avançadas - Roteamento
	Prof. Mauro Tapajós