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 SizeFormat
Disjoint path pair calculation considering bandwidths.pdf5.32 MBAdobe PDFView/Open
Show full item record

Page view(s) 5

1,068
checked on Mar 26, 2024

Download(s) 50

660
checked on Mar 26, 2024

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.