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, 22nd Irish Conference on Artificial Intelligence and Cognitive Science. AICS 2011., Derry, 31-08-2011 / 02-09-2, 2011Download Item:
A Combinatorial Optimisation Approach to Designing Dual-Parented Long-Reach Passive Optical Networks.pdf (Published (publisher's copy) - Peer Reviewed) 519.1Kb
Abstract:
We present an application focused on the design of resilient long-reach passive optical networks. We specifically consider dual-parented networks whereby each customer must be connected to two metro sites via 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 fibre length is minimized. We prove that this problem is NP-Complete. We present two alternative combinatorial optimisation approaches to finding an optimal metro node placement using: a mixed integer linear programming (MIP) formulation of the problem; and, a hybrid approach that uses clustering as a preprocessing step. We consider a detailed case-study based on a network for Ireland. The hybrid approach scales well and finds solutions that are close to optimal, with a runtime that is two orders-of-magnitude better than the MIP model.
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:
PUBLISHEDDerry
Other Titles:
22nd Irish Conference on Artificial Intelligence and Cognitive Science. AICS 2011.Type of material:
Conference PaperAvailability:
Full text availableKeywords:
Artificial Intelligence, passive optical networksSubject (TCD):
Smart & Sustainable PlanetLicences: