Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/22442
Title: Lexicographical minimization of routing hops in hop-constrained node survivable networks
Author: Gouveia, Luis
Patrício, Pedro
Sousa, Amaro de
Keywords: Telecommunication networks
Traffic engineering
Integer linear programming
Lexicographical minimization
Hop-indexed models
Path protection
Issue Date: Jun-2016
Publisher: Springer Verlag
Abstract: In this paper, we address a hop-constrained node survivable traffic engineering problem in the context of packet switched networks with source based routing. Consider a telecommunications network with given link capacities that was dimensioned for a set of commodities, with estimated demand values, such that each commodity demand is routed through a set of node disjoint service and backup paths, all with at most H hops. When the network is put in operation, the real demand values might be different from the initial estimated ones. So, we aim to determine a set of hop-constrained service and backup paths for each commodity, with known demand values, such that the whole set of paths does not violate the link capacities. The traffic engineering goal is related with the hop minimization of only the service paths. We aim to minimize the number of routing hops in a lexicographical sense, i.e., minimize the number of service paths with the worst number of hops; then, among all such solutions, minimize the number of service paths with the second worst number of hops; and so on. We address two traffic engineering variants: in the first variant, all service paths of each commodity are accounted for in the objective function while in the second variant only the worst service path of each commodity is accounted for in the objective function. We first present and discuss three classes of Integer Linear Programming hop-indexed models- disaggregated, mixed and aggregated — for both variants. Then, we prove that, although the three classes are not equivalent, they provide the same Linear Programming relaxation bounds for each variant. Finally, we present computational results showing that, as a consequence, the more compact aggregated models are more efficient in obtaining the optimal integer solutions.
Peer review: yes
URI: http://hdl.handle.net/10773/22442
DOI: 10.1007/s11235-015-0083-9
ISSN: 1018-4864
Appears in Collections:DETI - Artigos

Files in This Item:
There are no files associated with this item.


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

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