We consider the problem of constructing logical topologies over a wavelength-routed optical network with no wavelength changers. We present a general linear formulation which considers routing traffic demands, and routing and assigning wavelengths to lightpaths, as a combined optimization problem. The formulation also takes into account the maximum number of hops a lightpath is permitted to take, multiple logical links in the logical topology, multiple physical links in the physical topology, and symmetry/asymmetry restrictions in designing logical topologies. The objective is to minimize congestion. We show by examples how equality and inequality logical degree constraints have a bearing on congestion. We prove that, under certain conditions, having equality degree constraints with multiple edges allowed in the design of logical topologies does not affect congestion. This helps in reducing the dimensionality of the search space and hence speeds up the search for an optimal solution of the linear formulation. We solve the linear formulation for small examples and show the tradeoff between congestion, number of wavelengths available and the maximum number of hops a lightpath is allowed to take. For large networks, we solve the linear formulation by relaxing the integer constraints. We develop topology design algorithms for large networks based on rounding the solutions obtained by solving the relaxed problem. Since the whole problem is linearizable, the solution obtained by relaxation of the integer constraints yields a lower bound on congestion. This is useful in comparing the efficiency of our heuristic algorithms. Following Bienstock and Gunluk (1995), we introduce a cutting plane which helps in obtaining better lower bounds on congestion and also enables us to reduce the previously obtained upper bounds on congestion.

In this paper we present a exact linear formulation (mixed integer linear program) for designing a logical topology with no wavelength changers. Since the objective of our linear formulation is minimizing the maximum offered load on any link, which is called congestion, the resulting logical topology reflects the traffic intensities between the nodes. Our linear formulation yields a logical topology and routing and wavelength assignment for the logical links. Previously (see IEEE Journal on Selected Areas in Communications, vol.40, no.1, p.840-51, 1996) the problem of logical topology design is considered but the number of wavelengths the fiber can support is not a constraint. In this paper we take into consideration the number of wavelengths the fiber supports, the hop length of a logical link, and show the trade-offs involved in minimizing congestion. Since the whole problem is linearizable the solution obtained by relaxation of the integer constraints yields a lower bound on the congestion. This can be used to compare the efficiency of heuristic algorithms. We solve the problem exactly for a small size network and for large size networks we develop some heuristic algorithms to obtain a feasible solution using the solution obtained by relaxing the integer constraints. We introduce a cutting plane which enables us to reduce the previously obtained upper bounds on congestion. Numerical results for a six node wide area network and the National Science Foundation Network (NSFNET) are presented for various cases.