Lexicographical minimization of routing hops in hop-constrained node survivable networks

Luis Gouveia (), Pedro Patrício () and Amaro Sousa ()
Additional contact information
Luis Gouveia: Centro de Matemática, Aplicações Fundamentais e Investigação Operacional
Pedro Patrício: Centro de Matemática, Aplicações Fundamentais e Investigação Operacional
Amaro Sousa: Instituto de Telecomunicações

Telecommunication Systems: Modelling, Analysis, Design and Management, 2016, vol. 62, issue 2, No 13, 417-434

Abstract: 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.

Keywords: Telecommunication networks; Traffic engineering; Integer linear programming; Lexicographical minimization; Hop-indexed models; Path protection (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s11235-015-0083-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:telsys:v:62:y:2016:i:2:d:10.1007_s11235-015-0083-9

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11235

DOI: 10.1007/s11235-015-0083-9

Access Statistics for this article

Telecommunication Systems: Modelling, Analysis, Design and Management is currently edited by Muhammad Khan

More articles in Telecommunication Systems: Modelling, Analysis, Design and Management from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().