Algoritmos de Roteamento em Redes

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

PROTOCOLOS DE ROTEAMENTO
Aula 08: Algoritimos de roteamento
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Temas/objetivos desta Aula
Tipos de Algoritmos 
de Roteamento;
1
PRÓXIMOS 
PASSOS
Métricas de Algoritmos
 de Roteamento;
2
Distância 
Administrativa.
3
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Algoritmo de Roteamento
É responsável por determinar para qual porta de saída um pacote ou pedido de conexão deve ser endereçado.
Atributos desejáveis:
Correção: não cometer erros;
Simplicidade: pouca complexidade;
Robustez: recuperação rápida após erros e mudanças;
Equidade: todos têm direito de usar a rede;
Otimalidade: determinação da melhor rota.
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Algoritmo de Roteamento
Determina a rota (melhor) para um dado destino;
Rede é representada por um grafo:
nós do grafo: nós da rede (roteadores);
arestas do grafo: enlaces da rede (normalmente associados a um custo/peso).
Classificação:
centralizado ou distribuído;
estático ou dinâmico;
load-sensitive ou load-insensitive.
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Centralizado X Distribuído
Centralizado:
usa informação global da rede para determinar as rotas (mapa da rede);
computação centralizada em um site ou replicada nos demais nós;
exemplo: link state algorithm.
Distribuído:
determinação da rota é iterativa e distribuída;
informação apenas dos vizinhos (partial information);
nós não sabem o caminho completo, apenas o próximo passo até o destino;
exemplo: distance vector algoritm.
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Estáticos X Dinâmicos
Estáticos (não adaptativo):
Não utilizam de medidas ou estimativa do tráfego corrente;
Não utilizam de informações sobre a topologia atual da rede;
O cálculo de rotas é realizado em off-line e carregado nos nós;
Mudanças de rota requerem intervenção humana;
Exemplos: Shortest path e Flooding
Dinâmicos (adaptativos):
O cálculo de rotas é baseado em informações atualizadas;
As decisões sobre o cálculo das rotas são alteradas de acordo com mudanças na topologia e no tráfego;
Normalmente empregam algum tipo de métrica associada às rotas;
Exemplos: Distance vector e Link state
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Load Insensitive X Load Sensitive
Load insensitive:
não alteram as rotas em função da carga na rede;
custos dos enlaces não dependem do congestionamento observado.
Load sensitive:
custo dos enlaces varia com o estado da rede;
rotas dependem do congestionamanto;
novas rotas evitam os hot-spots;
otimização, porém podem causar grandes oscilações.
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Algoritmos Dinâmicos de Roteamento
Distance Vector:
Foi o algoritmo de roteamento original da Internet;
Baseia-se na manutenção de uma tabela atualizada com os custos dos melhores caminhos para cada destino na rede e qual o enlace a ser utilizado;
Esses custos são medidos em hops (saltos);
As tabelas são trocadas entre nós vizinhos a certa frequência;
A capacidade e o tráfego do enlace não são levados em conta.
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Protocolos de roteamento dinâmico
Funções dos protocolos de roteamento dinâmico:
 Compartilhar dinamicamente informações entre roteadores;
 Atualizar automaticamente a tabela de roteamento quando há mudanças 
na topologia;
 Determinar o melhor caminho para um destino.
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Protocolos de roteamento dinâmico
A finalidade de um protocolo de roteamento dinâmico é:
 Descobrir redes remotas;
 Manter atualizadas as informações de roteamento
 Escolher o melhor caminho para redes de destino;
 Habilidade para encontrar um “melhor caminho” novo se o atual não estiver disponível
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Protocolos de roteamento dinâmico
Vantagens do roteamento estático:
Processamento mínimo da CPU;
Mais fácil para o administrador entender;
Fácil de configurar;
Mais seguro.
Desvantagens de roteamento estático:
Mudanças na rede requerem reconfiguração manual;
Não ajusta bem em grandes topologias;
Requer conhecimento completo da rede inteira para implementação adequada.
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Protocolos de roteamento dinâmico
Os componentes principais de protocolos de roteamento dinâmico incluem:
Estruturas de dados — os protocolos de roteamento geralmente usam tabelas ou bancos de dados para suas operações. Essas informações são mantidas na RAM; 
Mensagens do protocolo de roteamento — os protocolos de roteamento usam vários tipos de mensagens para descobrir roteadores vizinhos, trocar informações de roteamento e outras tarefas para aprender e manter informações precisas sobre a rede. 
Algoritmo — os protocolos de roteamento usam algoritmos para facilitar as informações de roteamento para a determinação do melhor caminho. 
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Protocolos de roteamento dinâmico
Vantagens do roteamento dinâmico:
Compartilhar automaticamente informações sobre redes remotas;
Determinar o melhor caminho para cada rede e adicionar essas informações às suas tabelas de roteamento;
Em comparação com o roteamento estático, os protocolos de roteamento dinâmico exigem menos sobrecarga administrativa;
Ajude o administrador de rede a gerenciar o processo demorado de configurar e manter rotas estáticas.
Desvantagens do roteamento dinâmico:
Dedique a parte dos recursos de roteadores para a operação do protocolo, incluindo o tempo de CPU e a largura de banda do link de rede.
Momentos em que o roteamento estático é mais apropriado.
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Roteamento dinâmico v. estático
As redes normalmente utilizam uma combinação de roteamento estático e dinâmico.
O roteamento estático tem vários usos principais: 
Fornecer facilidade de manutenção da tabela de roteamento em redes menores que não devem crescer significativamente;
Roteamento para uma rede stub:
uma rede com apenas uma rota padrão de saída e nenhum conhecimento sobre redes remotas.
Acessando um único roteador padrão: 
usado para representar um caminho para qualquer rede que não tenha uma correspondência na tabela de roteamento. 
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Roteamento dinâmico v. estático
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Roteamento dinâmico v. estático
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Rotas aprendidas estaticamente - Exemplo de rotas estáticas
AULA 08 : ALGORITIMOS
DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Roteamento Dinâmico
Geralmente, as operações de um protocolo de roteamento dinâmico podem ser descritas da seguinte forma: 
O roteador envia e recebe mensagens de roteamento em suas interfaces; 
O roteador compartilha mensagens e informações de roteamento com outros roteadores que estão usando o mesmo protocolo de roteamento; 
Os roteadores trocam informações de roteamento para aprender sobre as redes remotas; 
Quando um roteador detecta uma alteração de topologia, o protocolo de roteamento pode anunciar essa alteração para outros roteadores. 
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Roteamento Dinâmico - Funcionamento
R1 adiciona a rede 10.1.0.0 disponível por meio da interface FastEthernet 0/0 
e 10.2.0.0 está disponível pela interface serial 0/0/0;
R2 adiciona a rede 10.2.0.0 disponível por meio da interface serial 0/0/0 e 10.3.0.0 está disponível por meio da interface serial 0/0/1;
R3 adiciona a rede 10.3.0.0 disponível por meio da interface serial 0/0/1 e 10.4.0.0 está disponível por meio da interface FastEthernet 0/0.
Roteadores que executam RIPv2
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Fundamentos de operação do protocolo de roteamento - Descoberta de rede
R1: 
Envia uma atualização sobre a rede 10.1.0.0 da interface Serial0/0/0;
Envia uma atualização sobre a rede 10.2.0.0 da interface FastEthernet0/0;
Recebe a atualização de R2 sobre a rede 10.3.0.0 com métrica 1;
Armazena a rede 10.3.0.0 na tabela de roteamento com métrica 1.
Roteadores que executam RIPv2
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Fundamentos de operação do protocolo de roteamento - Descoberta de rede
R2: 
Envia uma atualização sobre a rede 10.3.0.0 da interface Serial 0/0/0;
Envia uma atualização sobre a rede 10.2.0.0 da interface Serial 0/0/1;
Recebe uma atualização de R1 sobre a rede 10.1.0.0 com métrica 1;
Armazena a rede 10.1.0.0 na tabela de roteamento com métrica 1;
Recebe uma atualização de R3 sobre a rede 10.4.0.0 com métrica 1;
Armazena a rede 10.4.0.0 na tabela de roteamento com métrica 1.
Roteadores que executam RIPv2
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Fundamentos de operação do protocolo de roteamento - Descoberta de rede
R3: 
Envia uma atualização sobre a rede 10.4.0.0 da interface Serial 0/0/1;
Envia uma atualização sobre a rede 10.3.0.0 de FastEthernet0/0;
Recebe uma atualização de R2 sobre a rede 10.2.0.0 com métrica 1;
Armazena a rede 10.2.0.0 na tabela de roteamento com métrica 1.
Roteadores que executam RIPv2
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Fundamentos de operação do protocolo de roteamento
Trocar as informações de roteamento
R1: 
Envia uma atualização sobre a rede 10. 1. 0. 0 da interface 
serial 0/0/0;
Envia uma atualização sobre as redes 10. 2. 0. 0 e 10. 3. 0. 0 da interface FastEthernet0/0;
Recebe uma atualização de R2 sobre a rede 10. 4. 0. 0 com 
uma métrica 2;
Armazena a rede 10. 4. 0. 0 na tabela de roteamento com métrica 2;
A mesma atualização do R2 contém informações sobre a rede 10. 3. 0. 0 com a métrica 1. Não há alterações; portanto, as informações de roteamento continuam as mesmas.
Roteadores que executam RIPv2
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Fundamentos de operação do protocolo de roteamento
Trocar as informações de roteamento
R2: 
Envia uma atualização sobre as redes 10. 3. 0. 0 e 10. 4. 0. 0 da interface serial 0/0/0;
Envia uma atualização sobre as redes 10. 1. 0. 0 e 10. 2. 0. 0 da interface serial 0/0/1;
Recebe uma atualização de R1 sobre a rede 10. 1. 0. 0. Não há alterações; portanto, as informações de roteamento continuam 
as mesmas;
Recebe uma atualização de R3 sobre a rede 10. 4. 0. 0. Não há alterações; portanto, as informações de roteamento continuam 
as mesmas.
Roteadores que executam RIPv2
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Fundamentos de operação do protocolo de roteamento
Trocar as informações de roteamento
R3: 
Envia uma atualização sobre a rede 10. 4. 0. 0 da interface 
serial 0/0/1;
Envia uma atualização sobre as redes 10. 2. 0. 0 e 10. 3. 0. 0 da interface FastEthernet0/0;
Recebe uma atualização de R2 sobre a rede 10. 1. 0. 0 com 
uma métrica 2;
Armazena a rede 10. 1. 0. 0 na tabela de roteamento com métrica 2;
A mesma atualização do R2 contém informações sobre a rede 10. 2. 0. 0 com a métrica 1. Não há alterações; portanto, as informações de roteamento continuam as mesmas.
Roteadores que executam RIPv2
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Fundamentos de operação do protocolo de roteamento - Obtendo a convergência
Convergência da rede quando todos os roteadores têm informações completas e precisas sobre a rede;
O tempo de convergência é o tempo que o roteador leva para compartilhar informações, calcular os melhores caminhos e atualizar suas tabelas de roteamento;
Uma rede não estará totalmente operacional até que tenha realizado a convergência; 
As propriedades de convergência incluem a velocidade da propagação de informações de roteamento e o cálculo de caminhos melhores. A velocidade da propagação se refere à quantidade de tempo levado para roteadores dentro da rede encaminharem informações de roteamento; 
Geralmente, protocolos mais antigos, como o RIP, demoram a convergir, ao passo que os protocolos modernos, como OSPF, convergem mais rapidamente. 
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Tipos de protocolos de roteamento - Classificando protocolos de roteamento
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Tipos de protocolos de roteamento - Protocolos de roteamento IGP e EGP
Protocolos Internos de Gateway (IGP) 
Usados para roteamento dentro 
de um AS;
Incluem RIP, EIGRP, OSPF e IS-IS;
Protocolos Externos de Gateway (EGPs)  
Usados para roteamento entre AS;
Protocolo de roteamento oficial usado pela internet.
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Tipos de protocolos de roteamento
Tipos de protocolos de roteamento de vetor distância
IGPs IPv4 de vetor distância:
RIPv1 — Protocolo legado de primeira geração;
RIPv2 — Protocolo de roteamento de vetor distância simples.
Para R1, 172.16.3.0/24 está a um salto (de distância) e pode ser acessado por meio de R2 (vetor).
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Tipos de protocolos de roteamento - Protocolos de roteamento classful
Os protocolos de roteamento classful não enviam informações de máscara de sub-rede nas atualizações
de roteamento: 
Somente RIPv1 e IGRP são classful;
Criados quando os endereços de rede são alocados com base em classes (classe A, B ou C);
Não podem fornecer mascaramento de sub-rede de tamanho variável (VLSM) e roteamento entre domínios classless (CIDR);
Criam problemas em redes não contíguas.
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos
de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Tipos de protocolos de roteamento - Protocolos de roteamento classful
Os protocolos de roteamento classless incluem informações de máscara de sub-rede nas atualizações de roteamento:
RIPv2, EIGRP, OSPF e IS_IS;
Suporte para VLSM e CIDR;
Protocolos de roteamento IPv6.
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Tipos de protocolos de roteamento
Características de protocolo de roteamento
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Tipos de protocolos de roteamento - Métricas de protocolo de roteamento
Uma métrica é um valor mensurável atribuído pelo protocolo de roteamento a rotas diferentes com base na utilidade da rota:
Usada para determinar o “custo” geral de um caminho da origem para o destino;
Os protocolos de roteamento determinam o melhor caminho com base na rota com o menor custo.
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Tipos de protocolos de roteamento - Métricas de protocolo de roteamento
Métricas usadas por protocolos de roteamento IP:
 Largura de Banda;
 Custo;
 Atraso;
 Contagem de saltos;
 Carga;
 Confiabilidade.
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Métricas de protocolos de roteamento 
O campo de métrica na tabela de roteamento;
Métricas usadas pelos protocolos 
de roteamento:
 RIP – contagem de saltos
 OSPF – custo, largura de banda 
		(implementação da Cisco)
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Métricas de protocolos de roteamento 
Balanceamento de carga
 Esta é a capacidade de um roteador para distribuir os pacotes entre múltiplos caminhos de mesmocusto.
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Distâncias administrativas de um roteador
Propósito de uma métrica
É um valor calculado, utilizado para determinar o melhor caminho para um destino.
Propósito da Distância Administrativa
É um valor numérico que especifica a preferência de uma determinada rota.
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Distâncias administrativas de um roteador
Identificando a Distancia Administrativa (AD) na tabela de roteamento
 É o primeiro número entre parênteses na tabela de roteamento.
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Distâncias administrativas de um roteador
Protocolos de roteamento dinâmico
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Distâncias administrativas de um roteador
Redes diretamente conetadas
 Têm o padrão de AD de 0
Rotas estáticas
 A distância administrativa de rotas estáticas tem valor padrão de 1
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Distâncias administrativas de um roteador
Rotas diretamente conectadas
 Imediatamente aparecem na tabela de encaminhamento, logo que a interface é configurada:
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental
Assuntos da próxima aula:
AVANCE PARA FINALIZAR A APRESENTAÇÃO.
Vetor de distâncias.
AULA 08 : ALGORITIMOS DE ROTEAMENTO
Protocolos de roteamento
AULA 3: TERAPIA COGNITIVA DE AARON BECK
Terapia Cognitiva Comportamental