Heuristics for Fiber Installation in Optical Network Optimization

Consider the following optimization problem that arises from optical network design. We are given a network topology representing the fiber connectivity and a demand matrix to be carried over the network. A demand can either be unprotected, for which a single routing path is required, or protected, for which two disjoint paths are needed. Moreover, a demand may request a large bandwidth in multiples of a wavelength or a small bandwidth in the order of a fraction of a wavelength. Our objective is to route all demands while minimizing the cost of optical components necessary to carry the traffic. This paper has two aspects: modeling and effective heuristics. First, we define edge cost using subadditive functions and reason why they closely model the optical component cost. Second, we present shortest-path based heuristics to choose demand routes, where the choice of edge weights drives the optimization. One natural candidate for edge weight is the marginal cost incurred when carrying an additional demand. We observe good performance of this approach in combination with iterative re-routing and random orderings of demands. For heavy traffic, we note further improvement if we gradually approximate the original cost function with a set of more sophisticated piecewise strongly concave functions. Our heuristics are simple, scalable and find close-to-optimal solutions in many real instances.