Optical-ring integer linear program formulation

Details Optical-ring integer linear program formulation Optical-ring integer linear program formulation

2001-01-12

2003-12-16

Gordon, Paul P. (Department: 2121)

Data processing: generic control systems or specific application

Generic control system, apparatus or process

Optimization or adaptive control

C700S103000, C359S341200, C370S252000, C370S403000, C385S024000, C398S025000

Reexamination Certificate

active

06665567

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to the field of optical networks, and more particularly, to a system for minimizing the cost of an optical network.
BACKGROUND OF THE INVENTION
An important consideration in the design of optical networks is the overall cost. The cost of an optical network includes, but is not limited to, the cost optimal placement of amplifiers, the cost optimal grouping of wavelengths into bands, and the cost optimal placement of regenerators.
One technique to minimize the cost of an optical network is referred to as a “brute force” technique, where all possible permutations of a network configuration are evaluated and the cheapest one is selected. While this technique may work for very small networks having few elements, it is not really practical or scalable for the types of large optical networks currently required.
Therefore, given the ever increasing size and capacity requirements of optical networks, it would be desirable to have an accurate, efficient and scalable way to minimize the overall cost of the designed network.
SUMMARY OF THE INVENTION
The present invention includes a method and apparatus to minimize the total cost (i.e., determining the cost optimal placement of amplifiers, the cost optimal grouping of wavelengths into bands, and the cost optimal placement of regenerators) of an optical network. One embodiment of the present invention provides an Integer Linear Program (ILP) formulation that uses a ‘ring packing’ technique to optimally route demands through one or more defined rings on the network.
The ILP formulation includes a flow-based constraints approach to determine the minimum cost, wherein eligible working and protection routes are identified, and thereafter, the most cost efficient routing is determined. Some of the benefits provided by the disclosed ILP formulation are:
the formulation minimizes the cost, rather than the capacity, of a network.
the formulation is specific to an optical network, rather than a SONET or ATM network.
the formulation optimally routes demands through one or more defined rings, instead of placing one or more rings on a set of predefined paths.
the formulation is based on an ILP formulation, instead of using heuristics or simulated annealing techniques.
In one embodiment of the present invention a method is provided for designing an optical network to have minimized costs. The optical network has a plurality of nodes connected by interconnecting optical fibers. The method comprises inputting channel parameters associated with the optical network, inputting cost parameters associated with the optical network, calculating band parameters associated with the optical network, restricting at least one parameter associated with the optical network to having only integer values, and using an integer linear program to solve a minimization objective function that allows the cost of the optical network to be minimized, wherein the minimization objective function includes selected channel, cost and band parameters.
In another embodiment, a method for minimizing the cost of an optical network, the optical network having a plurality of nodes connected by interconnecting optical fibers, and wherein a plurality of parameters are associated with the nodes and the fibers. The method comprising steps of determining values for a first portion of the plurality of parameters, restricting values for a second portion of the plurality of parameters to have integer values, and solving a minimization objective function that includes at least some of the first and second portions of the plurality of parameters, to determine values for a third portion of the plurality of parameters, wherein a solution to the minimization objective function allows the cost of the optical network to be minimized.
The various features, advantages and other uses of the present invention will become more apparent by referring to the following detailed description and accompanying drawings.


REFERENCES:
patent: 6304347 (2001-10-01), Beine et al.
patent: 6339663 (2002-01-01), Leng et al.
patent: 6421349 (2002-07-01), Grover
patent: 6438286 (2002-08-01), Duerksen et al.
Ramaswami et al., “Optical Networks: A Practical Perspective”, p. 399-421, 1998.
Stern et al., “Multiwavelength Optical Networks, A Layered Approach”, p. 543-707, 1999.
Wu, “Fiber Network Service Survivability”, p. 255-329, 1992.

Affiliated with

Also associated with

Rating

Optical-ring integer linear program formulation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Optical-ring integer linear program formulation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optical-ring integer linear program formulation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3177641