Módulo 2: Algorítmos de Roteamento

Algorítmos Usados

Os protocolos dinâmicos podem implementar diversos algoritmos de roteamento. Alguns destes algoritmos utilizados são apresentados abaixo:

a) Vetor distância: Também definido como algoritmo de Bellman-Ford, este algoritmo trabalha baseado na idéia que cada roteador propaga periodicamente uma tabela com todas as redes conhecidas e a distância para alcançá-las. Geralmente, a distância é calculada pelo número de next hops necessários para alcançar uma determinada rede. O termo HOP caracteriza-se pela passagem entre um roteador e outro. Esse termo poderia ser equivalente a palavra “salto”. Sendo assim, cada roteador, ao receber os anúncios de todos os demais, calcula o caminho ótimo baseado no menor número de HOPs para chegar a determinada rede. Vale lembrar também, que cada roteador ao receber as informações de outras redes incrementa o número de HOPs e anuncia as rotas divulgadas para os demais roteadores.

b) Estado de enlace: Também definido como algoritmo Link State, este algoritmo trabalha baseado na idéia de que cada roteador possui informações sobre as redes que estão conectadas a ele e, periodicamente, testa para determinar se cada enlace está ativo. Com estas informações cada roteador divulga uma lista sobre o status de cada conexão, dizendo se estas estão ativas ou inativas. Baseado nessas informações, quando um roteador recebe um conjunto de mensagens sobre o estado dos enlaces das redes próximas a ele, é aplicado o algoritmo SPF de Dijskstra. Este algoritmo é aplicado baseado nas informações de cada roteador e é feito localmente a cada um destes, para o cálculo das melhores rotas para todos os destinos a partir de uma mesma origem. Em termos de expansão, este algoritmo tem vantagem sobre o Vetor Distância, pois o cálculo do melhor caminho é feito localmente e não depende do cálculo de roteadores intermediários. Outra vantagem é que devido a suas características, este algoritmo converge mais rapidamente devido a utilização de flooding para divulgação do estado de seus enlaces, ou seja, divulga de forma mais eficaz os melhores caminhos para suas redes a todos os roteadores conectados.

Baseados nesses algoritmos são implementados os protocolos dinâmicos apresentados nas próximas seções.