A carregar...
Publicação
Encaminhamento com múltiplas árvores
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 2.73 MB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
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.
Descrição
Dissertação para obtenção do Grau de Mestre em
Engenharia Informática
Palavras-chave
Encaminhamento multi-caminho Seleção de caminhos Problemas de grafos Agregação de caminhos Problemas difíceis