Optimisation of passive optical network design under demand uncertainty

Abstract

The Passive Optical Network (PON) is a point-to-multipoint, optical fibre telecommunication network used at the access level, in which a signal is distributed via a single fibre from the Central Office (CO) to a number of downstream Optical Network Units (ONUs) at customer premises. In addition to sharing a single fibre between a number of customers, these networks use passive components in the field, providing future-proof networks with no electricity requirements. All these benefits, together with high bandwidth potential, makes PONs and, in particular, the ITU-T G.984 Gigabit Passive Optical Network (GPON), the access network of choice for service providers. Traditionally planned by hand, advanced methods have been developed to design PON deployments, including heuristics, meta-heuristics and exact mathematical models. Unfortunately, heuristic methods provide sub-optimal solutions, which, due to high deployment costs in general, result in high and unnecessary overhead. Conversely, exact mathematical models of the Passive Optical Network Design Problem (PONDP) can give optimal, minimum cost solutions, but are very demanding in terms of computational effort, limiting the size of networks that can be solved in an acceptable time period. Furthermore, since PONs are mostly deployed in a greenfield setting, customer demand is uncertain, complicating the design of an accurate model even more. This thesis addresses two concerns in the exact mathematical modelling framework: model accuracy and computational tractability. To improve computational performance, a row- and column generation approach based on Benders decomposition is provided, strengthened by additional cut separation algorithms. This approach is found to be much more scalable and flexible than the classical arc flow approach when accounting for physical network constraints inherent in the PON specifications, due to the efficient handling of path length constraints. Furthermore, the framework presented contributes towards general hierarchical network connectivity problems with path length constraints, which have not been studied extensively in literature, and its flexibility is demonstrated by means of a number of model refinements, including the addition of different splitter types, edge-disjoint survivability between the CO and splitters, and homo- and heterogeneous multi-level networks. To address demand uncertainty, two distinct approaches are followed, resulting in a two-stage recourse and a robust formulation. These both serve to lower cost through optical fibre and splitter dimensioning while ensuring a minimum level of connectivity. A revenue-based model is formulated in conjunction with the stochastic formulations to illustrate the impact of directly maximising return on investment. Finally, the methods are verified and validated using cross-model verification, an external feasibility checker and face validation, before ensuring all network parameters conform to the G.984 specification, resulting in a practically feasible network design