Repositório Institucional da Universidade de Aveiro > Departamento de Electrónica, Telecomunicações e Informática > DETI - Comunicações >
 Lexicographical minimization of routing hops in telecommunication networks
Please use this identifier to cite or link to this item http://hdl.handle.net/10773/5122

title: Lexicographical minimization of routing hops in telecommunication networks
authors: Gouveia, Luís
Patrício, Pedro
Sousa, Amaro Fernandes de
issue date: Jun-2011
publisher: Springer Verlag
abstract: Consider a telecommunications network with given link capacities and a set of commodities with known demands that must be routed over the network. We aim to determine a single routing path for each commodity such that the whole set of paths does not violate the link capacities and the number of routing hops is minimized in a lexicographical sense, i.e., minimizing the number of paths with the worst number of hops; then, among all such solutions, minimizing the number of paths with the second worst number of hops; and so on. We present two approaches for solving this problem. The first approach is iterative where a sequence of hop constrained problems is solved and the optimal solution value of each iteration defines a new constraint added to the problems of subsequent iterations. The second approach is based on defining a single integer programming model for the whole problem. In this approach, we consider appropriate cost parameters associated with the number of hops of each routing path such that the cost of a path with h hops is higher than the cost of all paths with h-1 hops. In both cases, we propose multi-commodity flow and hop-indexed models and compare them both in terms of linear programming relaxation values and in terms of efficiency.
URI: http://hdl.handle.net/10773/5122
ISSN: 0302-9743
source: International Network Optimization Conference
appears in collectionsDETI - Comunicações

files in this item

file description sizeformat
Publisher_proof_final.pdfVersão publicada126.93 kBAdobe PDFview/open
Restrict Access. You can Request a copy!

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


Valid XHTML 1.0! RCAAP OpenAIRE DeGóis
ria-repositorio@ua.pt - Copyright ©   Universidade de Aveiro - RIA Statistics - Powered by MIT's DSpace software, Version 1.6.2