Dijkstra's algorithm

O método de caminho mais curto dos roteadores link-state: a distância do nó provisório mais próximo é definitiva e ele entra a seguir.

Edsger Dijkstra o projetou em 1956 para demonstrar o computador ARMAC e o publicou em 1959. O OSPF e o IS-IS o citam como base do cálculo de rotas, e por isso os roteadores o chamam de SPF, shortest path first.

A nota de 1959 na Numerische Mathematik tem três páginas e resolve dois problemas, primeiro a árvore geradora mínima e depois o caminho mais curto. Ela constrói os caminhos mais curtos a partir do nó de origem em ordem crescente de comprimento, de modo que a distância de cada nó fica resolvida antes de qualquer distância maior. Em 1993, Dijkstra escreveu que o projetou sem lápis e sem papel, tomando café num terraço em Amsterdã, só para uma demonstração.

A RFC 2328 descreve a versão do roteador: a cada iteração, o candidato mais próximo da raiz tem garantidamente o caminho mais curto, entra na árvore e seus vizinhos são examinados. Quando dois caminhos empatam, os dois próximos hops são mantidos, e a rigor o resultado deixa de ser uma árvore. A especificação não exige esse método exato, só que qualquer outro algoritmo produza uma árvore idêntica.

A garantia exige custos não negativos, e o OSPF vai além: todo custo de interface tem de ser maior que zero. A RFC 1195 dá o custo do cálculo como o quadrado do número de nós, menor em redes esparsas, e a documentação do FRRouting o chama de quase desprezível nas CPUs atuais. O que os roteadores limitam é a frequência: a RFC 8405 padroniza um back-off que adia o SPF quando os eventos chegam muito juntos.

Também conhecido como: shortest path first, spf algorithm, dijkstra, spf calculation, shortest-path tree

Fontes

← Todos os verbetes do glossário