Encaminhamento com múltiplas árvores

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

Nas redes de computadores, o tráfego entre cada par de nós pode ser encaminhado sempre pelo mesmo caminho ou distribuído por vários. Neste trabalho, abordam-se duas facetas do encaminhamento multi-caminho. Por um lado apresenta-se um novo algoritmo que calcula o conjunto dos caminhos a usar para encaminhar o tráfego entre cada par de nós da rede. A dificuldade do problema advém do facto de que os critérios de seleção dos caminhos podem ser contraditórios. Para privilegiar a comunicação entre o par de nós, devem-se selecionar caminhos de menor custo. No entanto, para aumentar, quer a distribuição de carga entre o par de nós, quer a resistência às falhas, devem-se escolher caminhos disjuntos. O algoritmo proposto tenta conciliar os diferentes requisitos e é parametrizável, para se poder adaptar às diversas características das redes e de forma a controlar a qualidade dos caminhos. A segunda parte da tese trata o problema da complexidade espacial do encaminhamento multi-caminho dado que o número total de caminhos necessários é potencialmente muito elevado, da ordem de O(kn2) (sendo k o número de caminhos desejados entre cada par de nós e n o número de nós de entrada ou saída da rede). Reduzir o número de entradas das tabelas de encaminhamento é um objetivo importante, que pode alcançado pela agregação dos caminhos em árvores. Porém, determinar o número mínimo de árvores que cobrem um conjunto de caminhos é um problema NP-difícil. A tese apresenta um novo algoritmo de agregação de caminhos num número reduzido de árvores. A estratégia utilizada privilegia a agregação de caminhos com troços em comum. Nos testes experimentais efetuados, que envolvem redes sintéticas e reais, ambos os algoritmos produziram melhores resultados que outros previamente publicados.