Estudo da Camada de Rede - Roteamento

Prévia do material em texto

1
Estudo da Camada de
Rede - Roteamento
Prof. Fernando Dias
2
Roteamento
n Trata do encaminhamento da comunicação da origem até o 
destino desejado
n 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)
n 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
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
2
3
Roteamento em Redes comutadas 
por Circuitos
n O roteamento em redes baseadas em comutação 
por circuitos é basicamente estático, rotas 
predefinidas são armazenadas nos dispositivos da 
rede
n Existe uma rota principal, caso ela esteja fora de 
serviço, é tentada outra das rotas definidas numa 
certa ordem de prioridades
n Esquema basicamente estático, onde as rotas são 
definidas manualmente, inclusive as rotas de 
“backup”
4
Roteamento em Redes de Pacotes
n Em redes baseadas em pacotes, existe diferenças 
no tipo de roteamento
q Distribuído
q Centralizado
q Source routing
n Em redes baseadas em circuitos virtuais, a escolha 
da rota é feita no momento de inicialização do 
circuito virtual
n Em redes baseadas em datagramas, uma rota é 
determinada para cada pacote
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
3
Algoritmos de Roteamento
n Estabelecem os caminhos para cada pacotes de
acordo com certas regras
n Simplicidade, Robustez, Estabilidade, Otimizado,
distribuição igual
n Algoritmos Não-adaptativos (estáticos) – rotas 
pré-definidas, a informação de roteamento não é
atualizada
n Algoritmos Adaptativos (dinâmicos) – a
informação de roteamento é atualizada 
periodicamente
Princípio da Melhor Rota
n 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
n Dado um determinado destino, todas as rotas 
ótimas para este destino irão criar uma árvore (sink 
tree)
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
4
Algoritmos de Baixo Custo (Least-Cost)
n 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
n O algoritmo deve encontrar a rota de menor custo 
entre cada dois nós da rede
n Dois algoritmos básicos: Dijkstra e Bellman-Ford
Shortest Path Routing (Dijkstra)
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
5
Bellman-Ford
Estratégias de Roteamento Estático
n Flooding (inundação)
q Uso de contadores de saltos
q Útil para mensagens de emergência
(aplicações militares)
q Pode ser usada para se inicializar a rota de um
circuito virtual, já que todas as rotas possíveis 
são tentadas
q Pode ser usada para disseminar informação 
importante para todos os nós da rede
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
6
Estratégias de Roteamento Estático
n Roteamento randômico
q Escolhe uma das possíveis saídas 
randomicamente
q A distribuição da carga é maior que a ótima da
rede, mas não tão grande como a obtida com 
flooding
q Assim como em flooding, não há distribuição
da informação da rede para o roteamento
Estratégias de Roteamento Estático
n Roteamento Fixo
q Baseado num dos algoritmos de baixo custo
q Estes algoritmos não podem se basear em 
variáveis dinâmicas como o tráfego
q Não há diferença nos roteamentos de
datagramas e de circuitos virtuais
q As tabelas de roteamento somente necessitam 
armazenar o próximo nó da rede que compõe
a rota
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
7
Exemplo de Roteamento Fixo
14
Roteadores
n Roteadores são equipamentos que operam na 
camada de rede, comutando pacotes 
n Os roteadores dividem a rede em regiões, cada 
qual com o seu número de rede único
n Os cabeçalhos MAC mudarão constantemente 
durante a travessia do pacote pelas redes
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
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
8
15
Roteadores
n Os pacotes seguem para o seu destino com base 
nos endereços de rede
n O roteamento é feito baseado no protocolo e no 
endereço de rede apresentado no cabeçalho do 
pacote
n As tabelas dos roteadores contém basicamente 
entradas para os hosts locais e as redes remotas
n O último roteador no caminho para o destino 
encaminhará o pacote diretamente para o seu 
destino
16
Roteadores Multiprotocolos
n LAN´s de hoje podem trabalhar com vários 
protocolos (Apple Talk, TCP/IP, IPX)
n Ter um roteador para cada tipo de protocolo é 
ineficiente
n Ao receber um pacote, o roteador o analisa e 
passa para o processador de protocolo 
correspondente
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
9
Tabelas de Roteamento IP
n Roteadores mantém tabelas nas quais as entradas 
são endereços IP
n Cada entrada indica o próximo nó a ser seguido e
não toda a rota definida
n Visando reduzir estas tabelas, suas entradas são da 
forma:
q Endereços de redes remotas (Rede, 0)
q Endereços de hosts locais (esta rede, host)
q Endereços de subredes remotas (esta-rede, subrede, 0)
q Endereços de hosts locais na subrede local (esta-rede,
esta-subrede, host)
Algoritmos de Roteamento Dinâmico
n Nas redes de pacotes, normalmente se usa algum tipo de
técnica de roteamento dinâmico
n Isto quer dizer que as decisões de roteamento variarão com 
as mudanças em parâmetros da rede
n Estes parâmetros usualmente são falhas na rede e
condições de congestionamento
n Para ser dinâmico e distribuído, o roteamento depende de
troca de mensagens feita pelos nós a rede
n Aspectos devem ser levados em conta (processamento 
adicional, overhead e velocidade de resposta)
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
10
Algoritmo de Distance Vector
n Também chamado Bellman-Ford distribuído
n Cada roteador mantém uma tabela indexada 
para cada outro roteador da rede
n Cada entrada na tabela possui um destino, uma 
métrica e a linha de saída correspondente
n 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
n A informação de roteamento é atualizada por 
trocas das tabelas com os vizinhos
Algoritmo de Distance Vector
n Problema da contagem até infinito (reação lenta
a falhas na rede)
n Converge lentamente depois de uma mudança 
na topologia (sempre os roteadores devem 
recalcular suas tabelas para encaminhar a
informação de roteamento)
n Originalmente usado na Arpanet (e na internet -
RIP)
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
11
Algoritmo de Link State
n Identifica cada roteador individualmente
n Determina o custo para cada roteador vizinho
n Monta um pacote com os custos para cada 
vizinho (enlace) – LSP – Link State Packet
n Um LSP contém:
q Identidade do remetente
q Número de sequência e idade (age)
q Lista de vizinhos e custos
n Um número de sequência e uma idade em cada 
pacote previne pacotes velhos de serem aceitos
Algoritmo de Link State
n 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)
n LSP’s são enviados periodicamente ou em reflexo à
variações na rede comoq surgimento de um novo vizinho
q queda de um enlace
q mudança no custo de um enlace
n Substituiu algoritmos de DV na Arpanet (não levavam as
taxas de bits em conta e demoravam para convergir)
n Alguns protocolos que o utilizam: OSPF (internet), IS-IS 
(ISO)
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
12
Comparação dos Algoritmos 
Dinâmicos
n Link State converge mais rapidamente que
Distance Vector (não necessita recalcular
as tabelas a serem encaminhadas,
simplesmente encaminham os LSP’s 
recebidos)
n Um roteador com problemas desestabiliza 
os dois algoritmos na mesma escala
Protocolos de Roteamento
n 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 alteradas
n Um roteador recém inicializado pede informação da 
rede aos outros roteadores
n Os outros roteadores respondem enviando suas 
tabelas de roteamento
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
13
Autonomous System - AS (Sistema 
Autônomo)
n IGP – Interior Gateway Protocol
n EGP – Exterior gateway Protocol
AS
AS
Protocolos de Roteamento
n Um AS é um conjunto de redes e roteadores que são vistas
como um unidade do ponto de vista do roteamento
n É uma porção lógica de redes IP maiores
n O roteamento realizado dentro de um AS (interno) se difere
do realizado fora
n Foram desenvolvidos protocolos de “borda” para lidarem
com o roteamento entre AS’s (EGP’s)
n Os EGP’s oferecem o suporte a políticas de roteamento
(opções configuradas em cada rotedor – não fazem parte do
protocolo)
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
14
27
Routing Information Protocol (RIP)
n É um IGP padrão IAB (RFC 1058) adequado a redes 
pequenas
n São transmitidos em datagramas UDP para a porta 520
n Tem tamanho máximo de 512 octetos, acima disso a 
informação de roteamento deve ser dividida em vários 
datagramas
n Identifica participantes ativos (roteadores) e passivos 
(hosts)
n Baseado no algoritmo de distance vector
q O vetor é o número da rede
q A distância é o número de saltos para a rede
q Um salto é considerado uma travessia por um roteador
28
Routing Information Protocol (RIP)
n O protocolo possui dois tipos básicos de mensagens: request
(1) e reply (2)
n Um request enviado pede aos vizinhos que enviem parte ou 
toda a sua tabela de roteamento por um reply
n 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
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
15
29
Routing Information Protocol (RIP)
n Redes diretamente conectadas tem métrica de 1 e a 
métrica máxima tem valor 16
n Cada rota na tabela possui um temporizador
n RIP não prevê máscaras de subrede
n Impossibilidade de uso em redes que adotem máscaras de 
subrede de comprimento variável
n Projetado para redes medianas (centenas de nós) 
razoavelmente estáveis
n O número máximo de saltos numa rota é 15, um número de 
16 é considerado infinito (redes limitadas!)
n Existem versões incompatíveis de RIP para TCP/IP, 
NetWare e AppleTalk
30
RIP-2
n Descrito na RFC 1723
n É uma ampliação do RIP versão 1
n Utiliza os campos nulos que não são usados por 
RIP-1
n Assim, implementações de RIP-1 devem ignorar 
estes campos para que ambos possam operar 
juntos corretamente
n Seu objetivo: poder ser usado em redes 
medianas, onde se utilizam subredes variáveis e 
ainda apresentar interoperabilidade com RIP 1
n Oferece autenticação simples e suporte a 
multicasting
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
16
OSPF (Open Shortest Path First)
n É um protocolo baseado 
no algoritmo de Link State
(RFC 2328)
n Um custo é associado a 
cada interface de saída de 
cada roteador
n OSPF utiliza o IP 
diretamente (e não sobre 
UDP ou TCP)
OSPF
n Suporta diferentes métricas
n OSPF pode calcular um conjunto de rotas específicas para 
cada tipo de serviço IP (type-of-service)
n Permite balanceamento de carga entre rotas de mesmo 
custo
n Suporta máscaras de subrede de tamanho variável
n OSPF suporta 3 tipos de conexões:
q Enlaces ponto-a-ponto entre roteadores
q Redes multiacesso com broadcasting (LAN’s)
q Redes multiacesso sem broadcasting (WAN’s)
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
17
OSPF
n 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
n Áreas são identificadas por um número de 32 bits e 
roteadores também
n Sempre existirá uma área backbone de número identificador 0
n O cabeçalho de qualquer pacote OSPF tem 24 bytes:
2
Mensagens OSPF
n O protocolo funciona com a troca de mensagens entre 
roteadores adjacentes apenas (economia de banda) 
n Utiliza multicast para não sobrecarregar a rede (endereço 
224.0.0.5 - AllSPFRouters)
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
18
OSPF - Mensagem Hello
n São enviadas periodicamente em cada enlace do roteador 
para verificar a vizinhança
n Nunca são repassados
n Numa rede multiacesso, dentre todos os roteadores, um deles 
é escolhido como roteador designado (o de maior prioridade)
n Este será o responsável pelo envio de anúncios da rede em 
questão
OSPF - Mensagem Database Description
n Inicializam a idéia de topologia do roteador por que enviam 
a base de dados de topologia de cada um
n Comunicação mestre-escravo onde as mensagens são 
confirmadas pelo escravo
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
19
OSPF – Mensagem
Link Status Update
n As informações de estado do enlace são trocadas pelos 
roteadores OSPF para que os bancos de dados de topologia 
sejam mantidos
n 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)
BGP (Border Gateway Protocol)
n É um EGP desenvolvido para internets TCP/IP e substitui o 
velho protocolo EGP (Arpanet)
n A versão atual é a BGP-4 (RFC 1771)
n BGP é baseado em 3 procedimentos básicos:
1. Neighbor acquisition (aquisição de um vizinho)
2. Neighbor reachability (alcance do vizinho)
3. Network reachability (alcance da rede)
n 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
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
20
Tipos de mensagens BGP
n O protocolo é baseado em conexões TCP
n O procedimento de aquisição de um vizinho é feito pelo 
envio de uma mensagem “open”
n Se o outro roteador responder com um “keepalive” é sinal de 
que ele aceita a criação de um relacionamento
BGP (Border Gateway Protocol)
n Hold timer: parâmetro incluído na mensagem 
de open para indicar o intervalo máximo entre 
duas mensagens de keepalive
n A mensagem open carrega a identificação do 
roteador e do AS que ele está
n Para o relacionamento entre os dois 
roteadores permanecer (alcance do vizinho), 
devem ser enviadas mensagens keepalive
periodicamente 
n A mensagem de keepalive é composta 
somente do cabeçalho sombreado na figura
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com
21
BGP (Border Gateway Protocol)
n É um protocolo com algumas características 
de distance vector
n O procedimento de alcance de umarede é 
realizado pelo broadcast de mensagens 
Update
n Ela disponibiliza para os vizinhos informações 
de rotas válidas na internet (Path Attributes) e 
de rotas a serem desconsideradas (withdrawn
routes)
n Normalmente em cada AS poucos ou somente 
um roteador implementará BGP
n Uma mensagem de notificação somente é 
enviada em caso de detecção de erros na 
operação do protocolo
BGP (Border Gateway Protocol)
n Cada informação de rota informa
q A origem da informação (IGP ou EGP)
q Os AS’s que estão no caminho da rota 
(políticas de roteamento)
q O próximo roteador de borda no caminho 
(lembre-se que o caminho pode conter 
roteadores que não implementam BGP)
q Outras informações: múltiplas entradas no AS, 
preferências locais (interesse de roteadores 
internos somente) e rotas agregadas
n Normalmente as mensagens de update são 
criadas de forma que os atributos do caminho 
sejam válidos para todos os destinos 
informados na mensagem
PDF created with FinePrint pdfFactory Pro trial version www.pdffactory.com