Multiplex communications – Fault recovery
Reexamination Certificate
1998-08-19
2001-09-25
Hsu, Alpus H. (Department: 2662)
Multiplex communications
Fault recovery
C370S220000, C370S238000, C340S870030, C714S004110, C709S238000
Reexamination Certificate
active
06295275
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to telecommunications systems and more particularly to dynamic route generation for real time network restoration using a pre-plan generation methodology.
BACKGROUND OF THE INVENTION
Telecommunications networks are subject to failure and must be restored after failure. Two competing methodologies have evolved to devise plans to restore telecommunications networks after failure: pre-plan and dynamic route generation. In the pre-plan methodology, restoral routes are generated for every traffic route within the network prior to network failure. Plans are then created to implement the restoral routes. These plans are known as “pre-plans,” and each pre-plan contains a set of commands for issuance to restoration network devices to activate the restoral routes. “Restoration network devices” are devices, such as digital cross connects (DXCs), that are used to restore traffic on the network in the event of network failure.
The pre-plan methodology has the benefit of generating optimal restoral routes. In general, all possible restoral routes (“pre-plans”) within a given a cost limit are generated for each traffic trunk, and the best (i.e., lowest cost) restoral route among those generated is selected for use in restoring the network. A major disadvantage of the pre-plan methodology is that it takes a long time to generate a batch of pre-plans for an entire telecommunications network. Moreover, given that network topology is generally very dynamic, there is a great likelihood that the pre-plans are quickly outdated after generation.
In the dynamic route generation methodology, a restoral route is generated for an impacted traffic route in real time in response to the network failure. Dynamic route generation is also referred to as “real time restoration.” Dynamic route generation generally places a cost limit on possible restoral routes and only generates the routes that fall within the cost limit. Typically, the cost limits used in pre-plan route generation are substantially higher than those used in dynamic route generation. The low cost limits employed in dynamic route generation ensure that very few routes are generated and considered; hence, increasing the speed with which a restoral route is generated.
One advantage of the dynamic route generation methodology is that it is very fast and uses current topology data. There is no need to generate a massive set of pre-plans as in the pre-plan methodology. A disadvantage suffered by the dynamic route generation methodology is that it often selects sub-optimal restoral routes for the sake of speed.
SUMMARY OF THE INVENTION
The present invention addresses the limitations of the prior art by providing a hybrid approach that combines the benefits of the pre-plan methodology with the benefits of the dynamic route generation methodology. In one embodiment of the present invention, pre-plan sub-routes are generated, where each sub-route is a portion of the network that may be used in formulating a restoral route. Lowest cost sub-routes are combined to quickly produce a low cost restoral route. The restoral route is dynamically generated using the pre-plan generated sub-routes.
In accordance with a first aspect of the present invention, a method is practiced in a telecommunications network that has nodes which are interconnected by connections. The telecommunications network also includes a computing resource for directing restoration of the network from a failure. The computing resource generates restoral sub-routes where each restoral sub-route is a portion of the network that has nodes and connections that connect the nodes. These nodes include end nodes that correspond to respective ends of the sub-routes. Each restoral sub-route has an associated cost less than a threshold cost amount. A failure is identified in the network and a traffic route that is impacted by the failure is also identified. The traffic route includes nodes that are logically divisible into nodes positioned on the left side of the failure and nodes on the right side of the failure. Selected ones of the sub-routes that have a selected end node that is one of the nodes of the traffic route impacted by the failure are identified. The end node is positioned on the left side of the failure are identified. Given ones of the sub-routes are identified where the given sub-routes have an end node that is one of the nodes of the traffic route that is impacted by the failure and the given end node is positioned on the right side of the failure. One of the selected left side sub-routes and one of the given right side sub-routes are employed to create a restoral route for restoring the telecommunications network from failure.
In accordance with a further aspect of the present invention, a data structure is provided for storing information about a sub-route. The sub-route constitutes a route formed by the subset of the nodes and the connections that may be used in formulating restoral routes to recover from a failure in a telecommunications system. Information regarding a first end node and a second end node of the sub-route is stored in the data structure. Information stored in the data structure is used in formulating a restoral route.
In accordance with another aspect of the present invention, a method of generating restoral routes for failure in a network that affects nodes along a given traffic route is practiced in the telecommunications network. Sub-routes are identified that include as an end node one of the nodes on a given traffic route. A first subset of the sub-routes that share common end nodes that are not on the given traffic routes are identified. If there are sub-routes in the first subset, sub-routes are selected that when combined produce the restoral route based upon their associated costs.
In accordance with yet another aspect of the present invention, a telecommunications network has a restoration system and nodes that are interconnected by connections. The restoration system includes a sub-route generator for generating sub-routes. The sub-routes have costs that do not exceed a cost limit. Each sub-route is a path network that interconnects selected nodes. The restoration system also includes a restoral route generator for dynamically generating restoral routes for restoring the network in response to the failure of the network. The restoral route is created from a first and a second sub-route that is generated by the sub-route generator.
The present invention may also be practiced with a pre-plan methodology. In particular, failure spans are identified in the network and restoral routes are generated for each failure span. The restoral routes are generated from sub-routes as described above.
REFERENCES:
patent: 5459716 (1995-10-01), Fahim et al.
patent: 5646936 (1997-07-01), Shah et al.
patent: 5832196 (1998-11-01), Croslin
patent: 5881048 (1999-03-01), Croslin
patent: 5991264 (1999-11-01), Croslin
patent: 5995485 (1999-11-01), Croslin
patent: 5999103 (1999-12-01), Croslin
Hsu Alpus H.
MCI Communications Corporation
Qureshi Afsar M.
LandOfFree
Dynamic route generation for real-time network restoration... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic route generation for real-time network restoration..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic route generation for real-time network restoration... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2445568