OPTIMIZATION METHODS APPLIED TO NETWORK PLANNING PROBLEMS

Abstract

.

This thesis focuses on the feasibility of solving network planning prob- lems that include non-linear aspects by means of integer linear pro- gramming (ILP).In the specialized literature, most network planning problems solved by applying ILP models do not include non-linear expressions in a direct way. However, non-linear expressions are very common when including constraints related to key network performance metrics as the blocking rate or the availability. To circumvent the difficulties of solving such problems, researchers have usually resorted to not includ- ing non-linear aspects or using meta-heuristics and heuristics, which do not guarantee an optimal solution. Such sub-optimal solutions lead to higher budget requirements or under performing networks and thus, as long as the optimal solution can be found in acceptable running times, it is preferred to other alternatives. The use of logarithm func- tions (to linearize some expressions) and mixed zero-one models have also be used, but not for the problems addressed in this thesis.In this thesis 3 network planning problems including non-linear ex- pressions were solved by means of ILP. The first problem was the dimensioning of network nodes and links in a dynamic wavelength- division multiplexed (WDM) network equipped with reconfigurable optical add-drop multiplexers (ROADM) as switching nodes. The network had to be dimensioned in such a way that the maximum blocking probability experienced by point-to-point connections would not exceed a maximum threshold. To date, no ILP works have ad- dressed the problem of dimensioning for a specific blocking value. The second problem consisted on dimensioning and configuring the backup resources of a static WDM network using shared-path protection as survivability mechanism. The network had to be dimensioned guar- anteeing that the availability of every connection would not decrease under a given target value. A new way of dealing with the non-linear expression for the availability target, the inclusion of an availability- based priority scheme for the access to the shared resources and the equations to consider the wavelength continuity constraint are the main contributions of this work. Finally, the dimensioning of work- ing and backup wavelengths of the dynamic WDM network operat- ing as the physical substrate of a network virtualization system was solved. In this system, virtual networks must be guaranteed a maxi- mum blocking and minimum availability. No previous work has dealt with these constraints.The strategies used in this thesis to solve non-linear network plan- ning problems could be used as a starting point to solve problems in different network contexts that include important non-linear aspects.Keywords: network planning, integer linear programming, mixed zero-one models, WDM networks, blocking, availability, ROADM-based networks, shared path protection, network virtualization.