Please use this identifier to cite or link to this item:
https://hdl.handle.net/10316/40425
Title: | Disjoint path pair calculation considering bandwidths | Authors: | Cruz, Fernando Pedro Ferreira da | Orientador: | Gomes, Teresa Martinez dos Santos | Keywords: | caminhos disjuntos; caminho mais largo; proteção; otimização lexicográfica; max-sum; encaminhamento com restrições; disjoint paths; widest path; protection; lexicographic optimization; max-sum; constrained routing | Issue Date: | 12-Sep-2014 | Place of publication or event: | Coimbra | Abstract: | A dependência da sociedade moderna dos serviços de telecomunicações tem vindo a crescer
nos últimos anos, assim como a responsabilidade de providenciar serviços com elevada qualidade. A garantia de fornecimento de um serviço de comunicações sem perda de conetividade é
extremamente importante, pois qualquer interrupção nas comunicações é fortemente sentida pelos
utilizadores. A proteção global de um caminho é uma forma simples de aumentar a resiliência
de uma ligação ponto-a-ponto. A sua implementação requer o cálculo de pelo menos um par de
caminhos disjuntos.
O cálculo de pares de caminhos disjuntos, com ou sem restrições, tem sido objeto de estudo
por numerosos autores. Existem algoritmos exactos para a resolução de alguns destes problemas,
contudo outros são de mais difícil resolução. A determinação de um par de caminhos disjuntos de
custo aditivo mínimo pode ser resolvido de forma eficiente utilizando o algoritmo de Suurballe.
Contudo, o problema da determinação de um par de caminhos de largura de banda total máxima é
NP-Completo.
Com isto em mente, este trabalho foca-se em três problemas de encaminhamento disjunto. O
primeiro é um problema de otimização lexicográfica para obter caminhos disjuntos de largura de
banda máxima e, depois, maximizar a largura de banda do caminho mais largo do par. O segundo
é o cálculo de um par de caminhos tal que a soma das larguras de banda é máxima para um dado
par de nós. Finalmente, o terceiro é um problema que tem como objetivo encontrar um par de
caminhos disjuntos que satisfaçam duas restrições de largura de banda diferentes.
Estes problemas de encaminhamento disjunto são formalizados como problemas de programação linear inteira (PLI) e é proposta uma heurística para cada um deles. O desempenho das
heurísticas é analisado tendo em conta o tempo de CPU das heurísticas e o requerido pelo CPLEX;
é também analisada a qualidade das soluções obtidas, utilizando como referência a solução ótima
devolvida pelo CPLEX ao resolver a formulação PLI do problema correspondente. Modern society’s dependency on telecommunications services has been increasing throughout the years and so has the responsibility to provide high quality services. The guarantee that a communications service is provided without loss of connectivity is extremely important, because any interruption in communications is strongly felt by the users. Global path protection is a simple way to increase resilience in an end-to-end connection. Its implementation requires the calculation of at least a pair of disjoint paths. The calculation of disjoint path pairs, with or without restrictions, has been the subject of study by many authors. There are exact algorithms that solve these problems, however others are harder to solve. The determination of a pair of disjoint paths of additive minimum cost can be solved efficiently using Suurballe’s algorithm. However, the problem of determining a pair of paths with maximum total bandwidth is NP-Complete. With this in mind, this work addresses three disjoint routing problems. The first is a lexicographic optimization problem for obtaining maximum bandwidth disjoint paths and, then, maximizing the widest path in the pair. The second is the calculation of a path pair such that the sum of the bandwidths is maximum for the given pair of nodes. Finally, the third is a problem that aims to find a pair of disjoint paths that satisfy two different bandwidth constraints. These disjoint routing problems are formalized as integer linear programming (ILP) and an heuristic is presented for each one. The performance of these heuristics is analyzed taking into account the heuristic’s and CPLEX’s CPU time; it is also analyzed the quality of the obtained solutions using as reference the optimal solutions obtained by CPLEX when it solves the ILP formulation of the corresponding problem. |
Description: | Dissertação de Mestrado Integrado em Engenharia Electrotécnica e de Computadores apresentada à Faculdade de Ciências e Tecnologia da Universidade de Coimbra | URI: | https://hdl.handle.net/10316/40425 | Rights: | openAccess |
Appears in Collections: | UC - Dissertações de Mestrado FCTUC Eng.Electrotécnica - Teses de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Disjoint path pair calculation considering bandwidths.pdf | 5.32 MB | Adobe PDF | View/Open |
Page view(s) 5
1,100
checked on Oct 8, 2024
Download(s) 50
694
checked on Oct 8, 2024
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.