Efficient topology design methods for next generation access networks

Optical networks provide a future proof platform for a wide range of services at the expense of replacing the cable plant. Such an enormous investmenthas to be justified by long term sustainability. Deployment costs have to be minimized,therefore planning optimal network topology plays crucial role regarding profitability. Our novel algorithmic solutionsaim to achieve a "strategic topology design", providing the location of the network elements, layout of the optical cable plant, and a complete system design, using available digital maps and cost databases as inputs. Our network planning methods were used in the industry with success, and the cost estimation methodology based on the achieved strategic design has outperformed traditional cost estimation solutions. Instead of time consuming human guesswork, the problem is now solved algorithmically by computers, and the algorithms scale for problem sizes of practical interest (over 10.000s of subscribers).Complexity and approximability studies, heuristics and exact algorithms are presented for minimizing cost of the network deployment, with respect to administrative requirementsand physical limitations of optical access networks.