We present algorithms for the design of optimal virtual topologies embedded on wide-area wavelength-routed optical networks. The physical network architecture employs wavelength-conversion-enabled wavelength-routing switches (WRS) at the routing nodes, which allow the establishment of circuit-switched all-optical wavelength-division multiplexed (WDM) channels, called lightpaths. We assume packet-based traffic in the network, such that a packet travelling from its source to its destination may have to multihop through one or more such lightpaths. We present an exact integer linear programming (ILP) formulation for the complete virtual topology design, including choice of the constituent lightpaths, routes for these lightpaths, and intensity of packet flows through these lightpaths. By minimizing the average packet hop distance in our objective function and by relaxing the wavelength-continuity constraints, we demonstrate that the entire optical network design problem can be considerably simplified and made computationally tractable. Although an ILP may take an exponential amount of time to obtain an exact optimal solution, we demonstrate that terminating the optimization within the first few iterations of the branch-and-bound method provides high-quality solutions. We ran experiments using the CPLEX optimization package on the NSFNET topology, a subset of the PACBELL network topology, as well as a third random topology to substantiate this conjecture. Minimizing the average packet hop distance is equivalent to maximizing the total network throughput under balanced flows through the lightpaths. The problem formulation can be used to design a balanced network, such that the utilizations of both transceivers and wavelengths in the network are maximized, thus reducing the cost of the network equipment. We analyze the trade-offs in budgeting of resources (transceivers and switch sizes) in the optical network, and demonstrate how an improperly designed network may have low utilization of any one of these resources. We also use the problem formulation to provide a reconfiguration methodology in order to adapt the virtual topology to changing traffic conditions.

We explore an optical network architecture which employs dense wavelength division multiplexing (WDM) technology and passive waveguide grating routers (WGRs) to establish a virtual topology based on lightpath communication. We examine the motivation and the technical challenges involved in this approach, propose and examine the characteristics of a network design algorithm, and provide some illustrative performance results.

We consider a wavelength-routed optical network operated as a lightpath-based virtual topology. We present an exact linear programming formulation for the complete virtual topology design, including choice of constituent lightpaths, routes for these lightpaths, and intensity of packet flows through these lightpaths. By making a shift in the objective function to minimal hop distance and by relaxing the wavelength-continuity constraints (i.e., assuming wavelength converters at all nodes), we demonstrate that the entire optical network design problem can be linearized and hence solved optimally. The linear formulation can be used to design a balanced network, such that the utilizations of both transceivers and wavelengths are high, i.e., neither of these expensive resources are under-utilized. We also use the linear formulation to provide a reconfiguration methodology in order to adapt the virtual topology to changing traffic conditions.

We consider large optical networks in which nodes employ wavelength-routing switches which enable the establishment of wavelength-division-multiplexed (WDM) channels, called lightpaths, between node pairs. We propose a practical approach to solve routing and wavelength assignment (RWA) of lightpaths in such networks. A large RWA problem is partitioned into several smaller subproblems, each of which may be solved independently and efficiently using well-known approximation techniques. A multicommodity flow formulation combined with randomized rounding is employed to calculate the routes for lightpaths. Wavelength assignments for lightpaths are performed based on graph-coloring techniques. Representative numerical examples indicate the accuracy of our algorithms.

We explore design principles for next-generation optical wide-area networks, employing wavelength-division multiplexing (WDM) and targeted to nationwide coverage. This optical network exploits wavelength multiplexers and optical switches in routing nodes, so that an arbitrary virtual topology may be embedded on a given physical fiber network. The virtual topology, which is used as a packet-switched network and which consists of a set of all-optical "lightpaths", is set up to exploit the relative strengths of both optics and electronics-viz. packets of information are carried by the virtual topology "as far as possible" in the optical domain, but packet forwarding from lightpath to lightpath is performed via electronic switching, whenever required. We formulate the virtual topology design problem as an optimization problem with one of two possible objective functions: (1) for a given traffic matrix, minimize the network-wide average packet delay (corresponding to a solution for present traffic demands), or (2) maximize the scale factor by which the traffic matrix can be scaled up (to provide the maximum capacity upgrade for future traffic demands). Since simpler versions of this problem have been shown to be NP-hard, we resort to heuristic approaches. Specifically, we employ an iterative approach which combines "simulated annealing" (to search for a good virtual topology) and "flow deviation" (to optimally route the traffic-and possibly bifurcate its components-on the virtual topology). We do not consider the number of available wavelengths to be a constraint, i.e., we ignore the routing of lightpaths and wavelength assignment for these lightpaths. We illustrate our approaches by employing experimental traffic statistics collected from NSFNET.

Explores design principles for next generation optical wide-area networks, employing wavelength-division multiplexing (WDM), and targeted to nationwide coverage. This almost-all-optical network will exploit wavelength multiplexers and optical switches in routing nodes, so that arbitrary virtual topologies may be imbedded on a given physical network. The virtual topology, which is packet switched and which consists of a set of all-optical lightpaths, is set up to exploit the relative strengths of both optics and electronics viz. packets of information are carried by the virtual topology "as far as possible" in the optical domain, but packet forwarding from lightpath to lightpath is performed via electronic switching, whenever required. Algorithms are developed so that the WDM-based network architecture will (a) provide a high aggregate system capacity due to spatial reuse of wavelengths, and (b) support a large and scalable number of users, given a limited number of wavelengths. The authors illustrate their approaches by employing experimental traffic statistics collected from NSFNET.>