A Combinatorial Optimisation Approach to the Design of Dual Parented Long-Reach Passive Optical Networks
File Type:
PDFItem Type:
Conference PaperDate:
2011Citation:
H. Cambazard, D. Mehta, B. O'Sullivan, L. Quesada, M. Ruffini, D. B. Payne, L. Doyle, A Combinatorial Optimisation Approach to the Design of Dual Parented Long-Reach Passive Optical Networks, 23rd IEEE International Conference on Tools with Artificial Intelligence (ICTAI), Boca Raton, Florida, USA, 7-9, November 2011, 2011, 785 - 792Download Item:
Abstract:
We present an application focused on the design of resilient long-reach passive optical networks. We speci?cally consider dual parented networks whereby each customer must be connected to two metro sites via a local exchange sites. An important property of such a placement is resilience to single metro node failure. The objective of the application is to determine the optimal position of a set of metro-nodes such that the total optical ?bre length is minimised. We prove that the decision variant of this problem is NP-Complete. We present three alternative combinatorial optimisation approaches to ?nding an optimal metro node placement using: a mixed integer linear programming formulation of the problem; a hybrid approach that uses clustering as a preprocessing step; and, ?nally, a local search approach. We consider a detailed case-study based on a network for Ireland. The hybrid approach scales well and ?nds solutions that are close to optimal, with a runtime that is two orders-of-magnitude better than the MIP model. The local search approach is consistently good on all benchmarks.
Sponsor
Grant Number
Science Foundation Ireland (SFI)
10/CE/I1853
Author's Homepage:
http://people.tcd.ie/ruffinmhttp://people.tcd.ie/ledoyle
http://people.tcd.ie/payned
Description:
PUBLISHEDBoca Raton, Florida, USA
Other Titles:
23rd IEEE International Conference on Tools with Artificial Intelligence (ICTAI)Type of material:
Conference PaperCollections
Availability:
Full text availableKeywords:
long-reach passive optical network, LR-PON, networksSubject (TCD):
Smart & Sustainable PlanetMetadata
Show full item recordLicences: