O princípio de otimização

É possível criar uma descrição geral das rotas ótimas sem levar em conta a topologia ou o tráfego de rede. Essa descrição é conhecida como princípio de otimização. Esse princípio estabelece que, se o roteador J estiver no caminho ótimo entre o roteador I e o roteador K, o caminho ótimo de J até K também estará na mesma rota. Para validar isso, chamaremos a parte da rota entre I e J de r1 e o restante de r2 . Se existisse uma rota melhor que rentre J e K, ela poderia ser concatenada com r1 para melhorar a rota entre I e K, contradizendo a afirmação de que r1r2 seria a melhor rota.

Como conseqüência direta do princípio de otimização, é possível observar que o conjunto de rotas ótimas de todas as origens para um determinado destino forma uma árvore com raiz no destino. Uma árvore como é mostrada na figura é conhecida como árvore de escoamento, onde a unidade métrica de distância é o número de hops.

O objetivo de todos os algoritmos de roteamento é descobrir e utilizar as árvores de escoamento em todos os roteadores. Como uma árvore de escoamento é de fato uma árvore, ela não contém loops; portanto, cada pacote será entregue dentro de um número finito e limitado de hops.

 

Deixe uma resposta