Please enable JavaScript.
Coggle requires JavaScript to display documents.
16 - Algoritmos de Roteamento.pdf - Coggle Diagram
16 - Algoritmos de Roteamento.pdf
Seções relevantes para estudo:
5.2
Algoritmos de roteamento em uma única rede✅
5.2.9
Roteamento por anycast
5.2.8
Roteamento por multicast
5.2.7
Roteamento por broadcast
5.2.6
Roteamento hierárquico dentro de uma rede ✅
5.2.5
Roteamento de estado de enlace ✅
5.2.4
Roteamento por vetor de distância ✅
5.2.2
Roteamento pelo caminho mais curto ✅
A principal função da camada de rede é rotear pacotes da máquina de origem para a máquina destino.
Fragmentos de origem e destino devem estar no mesmo segmento de rede.
Processos
Roteamento(Routing)
Função global que se baseia na criação e manutenção de uma tabela de roteamento. O objetivo é garantir que a tabela de roteamento contenha os melhores caminhos para alcançar qualquer destino possível.
Determina o melhor caminho para os pacotes seguirem através da rede.
Quando um roteador se conecta a uma nova rede ou detecta mudanças, como uma rota indisponível, ele ajusta sua tabela com base nas informações recebidas de outros roteadores, garantindo que sempre tenha uma rota eficiente para todos os destinos.
Encaminhamento(Forwarding)
Decisão sobre quais rotas utilizar de acordo com a tabela de encaminhamento
Função local que se baseia em informações já disponíveis. Quando um pacote chega a um roteador, este consulta a tabela de encaminhamento para descobrir para onde o pacote deve ser enviado, encaminhando-o para a próxima etapa de sua jornada, em direção ao destino final.
Exemplo: Se um pacote chega a um roteador, o roteador verifica o endereço de destino no cabeçalho do pacote, consulta sua tabela de encaminhamento para encontrar a melhor interface de saída e encaminha o pacote para o próximo salto.
Princípio da otimização
Imagine que você está resolvendo um problema de encontrar o caminho mais curto entre dois pontos em um grafo. O princípio de Bellman afirma que, se você conhece o caminho mais curto de um ponto intermediário até o destino, pode usar essa informação para determinar o caminho mais curto desde o ponto inicial até o destino. Não é necessário recalcular tudo do zero; apenas reutilizar as soluções ótimas dos subproblemas já resolvidos.
Algoritmos
Um fato relevante a se comentar é que todos os algoritmos de roteamento contam com o processamento de todos os roteadores para calcular as rotas.
Problemas com hardware ou software, até mesmo com um número pequeno de roteadores, podem causar grandes complicações na rede.
Responsáveis pela decisão sobre a linha de saída a ser usada na transição do pacote de entrada
Rede internamente utiliza circuítos virtuais ?
Uma rota específica é estabelecida antes da transmissão dos dados. Isso cria uma conexão lógica, embora não haja um circuito físico dedicado como nas redes telefônicas.
Rede internamente utiliza datagramas?
Nesse tipo de rede, cada pacote é tratado de forma independente, sem garantir uma rota pré-estabelecida.
Tipos
Adaptativos( Roteamento dinâmico)
Distinguem-se com base
onde encontram essas informações.
Roteadores adjacentes ou todos os roteadores?
do momento em que alternam as rotas
Do momento em que a topologia muda ou a cada x tempo.
Métrica utilizada na otimização.
Distância, número de saltos, tempo estimado de tráfego.
Exemplos: Algoritmo de vetor distância e roteamento de estado de enlace.
Alteram deciões as decisões de roteamento para refletir nas mudanças de topologia.
Não adaptativos (Roteamento estático)
Não baseiam suas decisões de roteamento no tráfego e topologias atuais.
Escolha de rota é previamente calculada offline, sendo transferida para os roteadores apenas quando iniciada.
Não responde bem a falhas. Escolhas de rota devem ser óbvias.
Exemplo: algoritmo de Flooding
Flooding
Desvantagem: Gera uma grande quantidade de pacotes duplicados.
Solução: Contador de hops no cabeçalho de cada pacote.
O contador é iniciado com a distância de caminho origem até o destino, caso este sendo desconhecido é possível que gere o pior caso, a dimensão total da rede. Esse contador é decrementado em cada salto, com o pacote sendo descartado quando o contador atingir zero.
Controlar pacotes que já foram transmitivos a fim de evitar que sejam transmitidos uma segunda vez.
Inserir um número de sequência em cada pacote recebido pelos seus hosts.
Cada roteador possui uma lista informando quais números de sequência já foram vistos.
Se for uma cópia , este será descartado.
Se o número de pacote recebido for mais baixo que o maior número de sequência incluso na tabela de roteamento, ele será rejeitado e se tornará obsoleto.
Se for um número de sequência novo será enviado para todas as linhas , exceto aquela que chegou.
Vantagem: Garente que um pacote seja entregue a cada nó na rede.
Técnica local simples na qual cada pacote de entrada é enviado para cada linha de saída, execto para aquela que chegou.
Propriedades
Equidade
Eficiência
Estabilidade
Robustez
Uma rede grande quando é instalada deve funcionar por anos e nesse meio tempo haverão muitas fahas de hardware e software, fazendo com que a topologia e o tráfego mudem várias vezes, o que não pode interromper o funcionamento dos hosts.
Simplicidade
Exatidão
Algoritmo de estado de enlace
Routing information protocol(RIP)
O problema da contagem ao infinito
Apesar de convergir para a resposta certa o roteamento por vetor distância pode reagir de maneira lenta para casos ruins.
Ele basicamente demora muito para recalcular as topologias. Como uma queda de luz, um corte de fio, entre outras mudanças de topologia.
Cada roteador mantém uma tabela que fornece a melhor distância conhecida até cada destino e determina qual enlace deve ser utilizado para chegar até lá.
Essa tabela possui uma entrada dividida em duas partes.
Estimativa de distância até esse destino.
Linha de saída
Atualizando seus valores com base nos seus vizinhos
Presume-se que cada roteador conheça a distância entre cada um dos seus vizinhos
Se a métrica for em saltos, a distância será apenas de um salto.
Se for o atraso de propagação, o roteador poderá medir diretamente com pacotes Echo especiais, que o receptor identifica com um registro de tempo e transmite de volta o mais rápido possível.
Roteamento hierárquico
Inter AS
Rip
DV
OSPF
Intra AS
Agrupa roteadores em sistemas autonomos denominados regiões ou áreas
Grupo de roteadores sobre a mesma administração
Cada área conhecerá todos os detalhes sobre como rotear pacotes para destinos dentro de sua própria região, mas não saberá nada sobre a estrutura interna de outras regiões.
Em suma, isso permite com que os roteadores de uma rede especifica não precisem conhecer a estrutura topológica das demais.
Todo o roteamento para outra área passa por um único caminho.
Isso faz com que á medida que cresce a relação entre o número de regiões e o número de roteadores por região, a economia de espaço na tabela só aumente.
Em consequência disso, ocorre o aumento no comprimento do caminho.
Para redes maiores
Quantos níveis ela deve ter ?
O número ideal de níveis para uma rede com N roteadores é ln N, exigindo um total de e(euler) ln N entradas por roteador.