Publicação
Encaminhamento com múltiplas árvores
| dc.contributor.advisor | Martins, José Legatheaux | |
| dc.contributor.advisor | Mamede, Margarida | |
| dc.contributor.author | Horta, João Pedro Amaro da Silva | |
| dc.date.accessioned | 2014-04-28T10:54:56Z | |
| dc.date.available | 2014-04-28T10:54:56Z | |
| dc.date.issued | 2013 | |
| dc.description | Dissertação para obtenção do Grau de Mestre em Engenharia Informática | por |
| dc.description.abstract | 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. | por |
| dc.identifier.uri | http://hdl.handle.net/10362/11978 | |
| dc.language.iso | por | por |
| dc.publisher | Faculdade de Ciências e Tecnologia | por |
| dc.subject | Encaminhamento multi-caminho | por |
| dc.subject | Seleção de caminhos | por |
| dc.subject | Problemas de grafos | por |
| dc.subject | Agregação de caminhos | por |
| dc.subject | Problemas difíceis | por |
| dc.title | Encaminhamento com múltiplas árvores | por |
| dc.type | master thesis | |
| dspace.entity.type | Publication | |
| rcaap.rights | openAccess | por |
| rcaap.type | masterThesis | por |