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

Thumbnail Image
drcn2015.pdf(604.22 KB)
Accepted Version
Arbelaez, Alejandro
Mehta, Deepak
O'Sullivan, Barry
Quesada, Luis
Journal Title
Journal ISSN
Volume Title
Institute of Electrical and Electronics Engineers (IEEE)
Research Projects
Organizational Units
Journal Issue
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.
Search problems , Manganese , Passive optical networks , Algorithm design and analysis , Time complexity , Joining processes
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
Link to publisher’s version
© 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.