Optimizing restoration capacity

Details Optimizing restoration capacity Optimizing restoration capacity

1998-12-17

2002-12-24

Hsu, Alpus H. (Department: 2665)

Multiplex communications

Fault recovery

C370S238000, C709S239000, C709S241000

Reexamination Certificate

active

06498778

ABSTRACT:

TECHNICAL FIELD
The invention relates generally to optimizing network restoration and, more particularly, to optimizing restoration capacity and/or restoration paths for a network to resolve a restoration scenario or problem through the use of linear programming.
BACKGROUND
Interruptions in network operations are typically caused by failures in the network, such as an inoperable communication path (e.g., a link) or switching office. These failures may result from a variety of events, such as street works, thunder storms, equipment failures, floods, and so forth. A failure in the network can create a severe service loss to customers and revenue loss to the telecommunication service provider. Accordingly, the problem of network restoration and reliability is a major concern to the telecommunication industry.
The network restoration problem may be separated into two parts, i.e., spare capacity design and online restoration. First, spare capacity design is a special network design problem in which minimal spare capacity must be installed in a network to restore disrupted services in the event of any failure. The objective of such a network restoration design problem, also known as the spare capacity assignment problem, is to determine where and how much spare capacity to install in a network while minimizing facility cost. Second, online restoration is implemented at the time of failure to establish an alternate route around an inoperable link or switching office. Restoration paths for affected demands can be computed in real time by an online restoration algorithm. Two restoration schemes have been considered: line restoration and path restoration. In line restoration, when a link fails, an affected demand on the link is redirected to an alternative route that connects the two ends of the failed link. In path restoration, an affected path is restored from the source to the destination.
Accordingly, there is a need to improve overall reliability of networks. There is also a need for a method and system to improve the planning of restoration capacity in a network or, in other words, to find a better way to design and utilize restoration capacity in the network.
SUMMARY OF THE INVENTION
The above-identified problems are solved and a technical advance is achieved in the art by providing a method and system for computing an optimal restoration capacity and/or optimal restoration path for a network to resolve a restoration scenario or problem (“hereinafter restoration scenario”) by solving a linear program (LP) model, wherein the linear program model includes decision variables corresponding to restoration capacity and restoration paths and constraints requiring restoration of traffic and conservation of capacity in the network. The method and system of the invention is able to solve restoration scenarios, including line restoration problems and path restoration problems, in a manner which optimizes the use and integration of capacity in the network for restoring network traffic. As compared to other optimization methods, such as the node-arc formulation in linear programming, the path-based formulation of the invention requires fewer constraints and, thus, provides a simpler approach to solving restoration scenarios.
In one embodiment, the method and system of the invention determines a set of network paths (e.g., demands, links, etc.) that need to be restored preferably to meet direct measures of quality (DMOQ) for a restoration scenario, preprocesses network data corresponding to the network to be optimized to reduce LP processing workload and time (e.g., by aggregating network data); generates all possible restoration paths for the given restoration scenario; solves the LP model to obtain the optimal restoration capacity and/or the optimal restoration paths for the restoration scenario; changes the LP solution into integer form (as necessary), and changes the integer LP solution to the original format of the network data or an equivalent thereof.
In another embodiment, the method and system of the invention employs column generation methods in combination with linear programming to determine the optimal restoration capacity and/or the optimal restoration paths to resolve a restoration scenario. Initially, a set of network paths (e.g., demands, links, etc.) that need to be restored to meet DMOQ are determined for the restoration scenario, and the network data corresponding to the network to be optimized is preferably preprocessed to reduce LP processing workload and time (e.g., by aggregating network data). In accordance with column generation methods, one possible restoration path is generated for each affected network path initially. The LP model is then solved with all of the restoration capacity variables and the restoration path variables generated so far. After solving the LP model with the initial generated possible restoration paths, the dual LP solution is used to find a shortest restoration path for each demand. If the total length of a shortest restoration path of a network path is less than the length of dual variable corresponding to the restoration path variable of the network path, the restoration path is a feasible restoration path and is added to the set of restoration paths for the demand. The revised set of possible restoration paths are then used to solve the LP model. These steps are repeated until no feasible restoration paths can be found for any network path or, in other words, the optimal LP solution is reached. Thereafter, the LP solution is changed into integer form (as necessary) and then changed back to the original format of the network data or equivalent thereof. With column generation, restoration paths are only generated as needed to find the optimal solution to the LP model. Such an arrangement substantially reduces the number of possible restoration paths that need to be generated to solve the LP model and, thus, reduces the overall LP processing workload and time.
For column generation, the invention further provides a dynamic path control policy to increase the convergence speed of the LP solution. The dynamic path control policy regulates the number of restoration paths retained for use in each LP iteration by defining the maximum number or range of restoration paths to be retained in solving the LP model.
Other and further aspects of the present invention will become apparent during the course of the following description and by reference to the attached drawings.


REFERENCES:
patent: 5058105 (1991-10-01), Mansour et al.
patent: 5059105 (1991-10-01), Mansour et al.
patent: 5182744 (1993-01-01), Askew et al.
patent: 5850505 (1998-12-01), Grover et al.
patent: 6141318 (2000-11-01), Miyan
patent: 6141319 (2000-11-01), Dighe et al.
patent: 6304349 (2001-11-01), Alanyali et al.
H. Sakauchi, Y. Nishimura & S. Hasegawa,A Self-Healing Network With An Economical Spare-Channel Assignment, IEEE Globecom '90, CH2827-4/90/000, pp. 438-443 (1990).
W.D. Grover, T.D. Bilodeau & B.D. Venables,Near Optimal Spare Capacity Planning In A Mesh Restorable Network, IEEE Globecom '91, CH2980-1/91/0000, pp. 2007-2012 (1991).
M. Herzberg,A Decomposition Approach to Assign Spare Channels in Self-Healing Networks, IEEE Globecom '93, 0-7803-0917-0/93, pp. 1601-1605 (1993).
C. Wynants, M. Gendreau, M. Labbe & R. Seguin,Optimizing Reserve Capacities of Partially Equipped SDH Networks(Sep. 1996).
T. Magnanti & Y. Wang,Polyhedral Properties of the Network Restoration Problem—with the Convex Hull of a Special Case, Working paper OR 323-97, Operations Research Center, MIT (Nov. 1997).

Affiliated with

Also associated with

Rating

Optimizing restoration capacity does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Optimizing restoration capacity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimizing restoration capacity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2921464