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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.