Repositório Institucional da Universidade de Aveiro > Departamento de Electrónica, Telecomunicações e Informática > DETI - Capítulo de livro >
 Optimal survivable routing with a small number of hops
Please use this identifier to cite or link to this item http://hdl.handle.net/10773/5165

title: Optimal survivable routing with a small number of hops
authors: Gouveia, Luís
Patrício, Pedro
Sousa, Amaro de
keywords: Routing optimization
Hop constraints
issue date: 17-Jan-2012
publisher: Springer
abstract: Consider a given network defined by an undirected graph with a capacity value associated with each edge and a set of traffic commodities that must be routed through the network. Assume that the network contains at least D hop-constrained node disjoint routing paths between the origin and the destination nodes of each commodity. This paper addresses the minimum hop survivability routing problem, i.e., the determination of the routing paths optimizing hop related objective functions applied to the delta minimum hop routing paths of each commodity, where 1 <= delta <= D. We propose ILP formulations addressing two objective functions: the minimization of the average number of hops and the minimization of the maximum number of hops. In both cases, the proposed models let us address two common survivability mechanisms: the case with delta = D corresponds to the Path Diversity mechanism and the case with delta = D - 1 corresponds to the Path Protection mechanism. We present computational results using pre-dimensioned networks based on the NSF network for given estimated commodity demands. We study two traffic engineering issues: i) the relationship between the total commodity demand and the optimal values of the objective functions and ii) the impact of demand estimation errors on the feasibility of pre-dimensioned network design solutions. Concerning the efficiency of the proposed formulations, the results show that when delta = D the proposed models are very efficient in all cases; the results also show that when delta = D - 1 the proposed models are efficient when the total commodity demand is as much as 97.5% of the network capacity and become harder to solve when total demand reaches the limit of the network capacity.
URI: http://hdl.handle.net/10773/5165
ISBN: 978-0-387-77779-5
appears in collectionsDETI - Capítulo de livro

files in this item

file description sizeformat
fulltext.pdfCapítulo publicado761.54 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