Classificação de Algoritmos de Roteamento

Os algoritmos de roteamento são adotados pelos protocolos de roteamento, que podem optar em possuir um ou vários algoritmos para roteamento.

Os algoritmos de roteamento podem ser classificados em duas categorias:

Algoritmos de roteamento globais

Algoritmos de roteamento descentralizados

Os algoritmos de roteamento globais trabalham com o objetivo de determinar o menor caminho entre os nós de origem e de destino. Para que possam trabalhar, os algoritmos de roteamento globais devem ter pleno conhecimento da topologia da rede e seu enlace. O envio e recebimento de numerosa quantidade de mensagens em broadcast informando o estado dos roteadores é uma das principais características de seu funcionamento, o que o torna inadequado para redes maiores.

Um exemplo de algoritmo de roteamento global é o algoritmo de Dijkstra, que tem como objetivo determinar o menor caminho entre dois nós. Seu funcionamento constitui em uma etapa de inicialização seguida por um looping, o qual possui quantidade de iterações equivalente ao tamanho de hosts na rede. Ao seu término, é retornado o menor caminho possível entre dois nós.
Com freqüência, o roteador dispara mensagens em broadcast para os demais roteadores, informando sobre seu estado e também recebe informações sobre o estado de outros roteadores, a fim de atualizar suas tabelas de roteamento. Isso torna o algoritmo de Dijkstra inadequado para redes maiores, sendo utilizado apenas em segmentos menores da rede, em casos específicos.

Os algoritmos de roteamento descentralizados são algoritmos iterativos e distribuídos. O algoritmo Distance-Vector é um algoritmo dinâmico, distribuído e iterativo, utilizado em protocolos de roteamento como IPX, Apple Talk e RIP. Nele, os roteadores conhecem seus vizinhos imediatos e trocam tabelas de retardos entre si.
O algoritmo de Bellman-Ford é utilizado para calcular a distância métrica de Distance Vector.