A constraint-based local search for designing tree networks with distance and disjoint constraints

Loading...
Thumbnail Image
Files
drcn2015.pdf(604.22 KB)
Accepted Version
Date
2015-11-12
Authors
Arbelaez, Alejandro
Mehta, Deepak
O'Sullivan, Barry
Quesada, Luis
Journal Title
Journal ISSN
Volume Title
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Research Projects
Organizational Units
Journal Issue
Abstract
In many network design problems clients are required to be connected to a facility under path-length constraints and budget limits. Each facility is associated with a tree network where the root is the facility itself and the remaining nodes of the tree are its clients. An inherent feature of these networks is that they are vulnerable to a failure. Therefore, it is often important to provide some resiliency in the network. We focus on a problem where we want to ensure that all clients are connected to two facilities so that if one facility fails then all clients can still be served by another facility. Optionally, one might require that each client is resilient to a single link or node failure by enforcing that the paths used to connect a client to its two facilities are either edge-disjoint or node-disjoint respectively. In this paper we use local search to evaluate the trade-off between cost versus resiliency and coverage versus resiliency for a real-world problem in the field of optical networks.
Description
Keywords
Search problems , Manganese , Passive optical networks , Algorithm design and analysis , Time complexity , Joining processes
Citation
Arbelaez, A., Mehta, D., O'Sullivan, B. and Quesada, L. (2015) 'A constraint-based local search for designing tree networks with distance and disjoint constraints', 2015 7th International Workshop on Reliable Networks Design and Modeling (RNDM), Munich, Germany, 5-7 October, pp. 128-134. doi: https://doi.org/10.1109/RNDM.2015.7325219
Copyright
© 2015, IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.