Method and system for pre-patching a communications network

A method and system for pre-patching spare capacity into a communications network. The pre-patching system analyzes an original network configuration along with restoration plans that define restoral routes to bypass a network failure. The pre-patching system identifies existing spare connections in the original network configuration that can advantageously be destroyed from the original configuration so that their destroying can be avoided when implementing the restoration plans. The pre-patching system also identifies connections that do not exist in the original configuration and that can advantageously be created in the original network configuration to avoid the overhead of their creation when implementing the restoration plans.

CROSS-REFERENCE TO RELATED APPLICATIONS 
This application is related to the U.S. patent applications entitled 
"Method and System for Assigning Spare Transmission Links To Restoral 
Routes" and "Method and System for Augmenting a Communications Network 
with Spare Capacity," which are being filed concurrently and are hereby 
incorporated by reference. 
TECHNICAL FIELD 
The present invention relates to communications networks and, in 
particular, to the restoration of communications networks following 
failures of a network component. 
BACKGROUND OF THE INVENTION 
Telecommunications carriers (e.g., long distance providers) continually 
strive to increase the reliability of their communications networks. They 
do this, in part, by increasing the speed by which they can restore 
network operation following failure in one or more components of the 
network. A communications network consists of a collection of transmission 
links, also known as segments, that are interconnected at network nodes. 
The segments include transmission lines, fiber optic cables, microwave 
links, and other such transmission medium. Traffic is transmitted on the 
network from one endpoint to another endpoint through a current route or 
"trunk," which is a network path of segments that interconnect the 
endpoints. The network nodes may serve a variety of functions such as 
amplifying the network traffic for transmission down the next segment in 
the route or establishing an interconnection between two segments 
connected to the node (i.e., a switch). Segments are interconnected by 
switching nodes to form "spans." The switching nodes can be controlled 
locally or from a remote computer system to connect or to disconnect 
segments that are connected to the node. 
Unfortunately, the components (e.g., nodes and segments) of the 
communications network may occasionally fail. For example, a segment that 
is a buried fiber optic cable may fail as a result of being inadvertently 
severed by someone digging near the buried cable. If one or more of the 
cables fail, massive disruption of services to a large number of network 
customers could result. Therefore, telecommunications carriers strive to 
quickly and economically route the network traffic around such failed 
components by establishing a "restoral" route. A restoral route is a path 
between the endpoints that does not include the failed component. The 
establishing of a restoral route generally involves: (1) detecting that a 
component on the current route has failed, (2) identifying the location of 
the component, (3) selecting a restoral route to bypass the failed 
component, and (4) implementing the selected restoral route. The 
reliability of telecommunication networks depends in large part on the 
ability to detect such failures and implement the restoral route with 
minimal impact on network customers. A plan that identifies which 
switching nodes, also referred to as restoration nodes, are to be switched 
to bypass one or more specific failed components is called a "restoration 
plan." 
Communications networks typically have excess capacity that can be used to 
bypass a failed component. The segments of a network that are currently 
being used to bear traffic are referred to as active segments, and the 
segments that are not being currently used to bear traffic (i.e., excess 
capacity) are referred to as spare segments. Spare segments that are 
currently connected to another to form a span are referred to as a spare 
span. Restoral routes are implemented by identifying spare segments and 
incorporating certain of those spare segments into the network. 
Telecommunications carriers desire to use restoral routes that minimize 
costs and that can be implemented rapidly when a network failure is 
detected. Telecommunications carriers typically consider the quality, 
capacity, and length of a restoral route as an indication of the cost of 
the restoral route. However, other costs, such as switching costs, are 
typically not considered. Switching costs are the costs associated with 
switching a restoration node to disconnect the failed segment and to 
connect spare segments to the non-failed active segments. In general, it 
is desirable to reduce the number of connections and disconnections (i.e., 
actions) when bypassing a failure. The number of connects and disconnects 
increases the time needed to implement a restoral route. Also, since an 
attempted connect or disconnect can fail, it is also desirable to reduce 
the number of connects and disconnects to reduce the chance of the 
implementation of the restoral route failing. 
SUMMARY OF THE INVENTION 
The present invention provides a method and system for determining an 
initial configuration for a communications network. The pre-patching 
system of the present invention retrieves various restoration plans for 
the network. Each restoration plan specifies restoral routes to bypass 
network failures. The pre-patching system then analyzes the retrieved 
restoration plans to identify an initial configuration of the network that 
reduces the cost of implementing some of the retrieved restoration plans. 
The pre-patching system then implements the identified initial 
configuration so that the cost of implementing a restoration plan is 
reduced. 
More specifically, the pre-patching system determines a modification to an 
initial configuration of a communications network. The communications 
network has components that include active segments, spare segments, 
active connections that connect an active segment with another active 
segment, and spare connections that connect a spare segment with another 
segment. The pre-patching system then identifies three types of 
connections: to-be-created, to-be-used, and to-be-destroyed. The 
to-be-created connections need to be created to bypass a failed active 
segment. The to-be-used connections are existing spare connections that 
are used to bypass a failed active segment. The to-be-destroyed 
connections are existing spare connections that are destroyed to bypass a 
failed active segment. Based on the initial configuration of the 
communications network and on the identified to-be-created, to-be-used, 
and to-be-destroyed connections, the pre-patching system determines 
existing spare connections that should be destroyed and new connections 
that should be created to modify the initial configuration of the 
communications network to improve the performance of bypassing network 
failures.

DETAILED DESCRIPTION OF THE INVENTION 
The present invention provides a method and system for pre-patching a 
communications network in order to reduce the time required to implement a 
restoral route when a network component fails. The pre-patching system 
identifies new spare connections that if created and existing spare 
connections that if destroyed in the initial network configuration would 
improve the overall performance of building restoral routes. The 
pre-patching system then pre-patches the identified connections by 
creating or destroying those identified connections in the initial network 
configuration. When restoration plans are then implemented to bypass a 
failure, it is likely that the total number of connections that need to be 
created or destroyed is reduced because of the pre-patching. Thus, the 
overall performance of implementing the restoration plans would improve. 
The pre-patching system determines which connections to create or destroy 
by analyzing the restoration plans that have been developed to bypass 
various failures that could occur in the communications network. The 
pre-patching system counts the total number of times each connection would 
be created, destroyed, or used "as is" if each restoration plan was 
implemented to bypass a failure in the initial network configuration. If a 
certain connection is used "as is" or created in a large number of 
restoration plans, but only destroyed in a few restoration plans, then the 
pre-patching system would ensure that this connection is left "as is" or 
created. If a certain connection is destroyed in a large number of 
restoration plans, but only used "as is" or created in a small number of 
restoration plans, then the pre-patching system would ensure that the 
connection is destroyed in the initial network configuration. More 
generally, the pre-patching system of the present invention counts the 
number of times that each connection is needed by the restoration plans 
and counts the number of times that each connection would conflict with a 
restoration plan. A connection conflicts with a restoration plan if it 
would need to be destroyed to implement the restoration plan. The 
pre-patching system then selects a set of connections to create or destroy 
which would reduce the overall number of actions needed to implement the 
restoration plans. The pre-patching system may also use factors other than 
the counts to determine the set of connections to create or destroy. For 
example, certain network failures may occur more frequently than others. 
Thus, the restoration plan to bypass these failures would be implemented 
more frequently than other restoration plans. The pre-patching system may 
assign a weighting factor to each restoration plan to account for its 
expected frequency of implementation. Thus, even though a connection may 
be used by only one restoration plan, if that restoration plan is expected 
to be implemented frequently, then it may be advantageous for the 
pre-patching system to create that connection initially. Also, certain 
restoration plans may be used to restore failures in high priority trunks. 
These restoration plans may also be assigned a weighting factor that is 
based on the priority in this way, high priority trunks could be restored 
more quickly because the needed connections have already been created or 
destroyed. 
FIG. 1 is a block diagram of a generalized computer system for executing 
the pre-patching system. The computer system 101 includes a central 
processing unit 102, a memory 103, and a storage device 104 (e.g., a hard 
disk drive). The pre-patching system, implemented as a pre-patching 
program 105, is stored on the storage device within the computer system. 
The pre-patching program, or portions thereof, are transferred to an 
in-memory copy of the pre-patching program 106 that comprises instructions 
that direct the CPU to perform the pre-patching analysis based on the 
original network configuration and on restoration plans. Intermediate data 
generated during pre-patching analysis is stored in a triplet table 107 in 
the memory of the computer. The triplet table contains the total count of 
the number of times a connection is used "as is," created, or destroyed by 
the restoration plans. 
FIGS. 2-13 are diagrams illustrating an example pre-patching analysis. FIG. 
2 illustrates the original configuration of a communications network. The 
communications network includes restoration nodes A-E. Node A represents 
one endpoint of the communications network and node E represents the other 
end of the communications network. The communications network includes 
three active segments 1, 4, and 7. These three active segments are 
connected together through restoration nodes B and D to form the trunk for 
the communications network. In other words, as originally configured, all 
network traffic is transmitted through segments 1, 4, and 7. The example 
communications network further includes eight spare segments 2, 3, 5, 6, 
and 8-13. Restoration node B contains three connections 21-23. Connection 
21 connects segment 1 to segment 4. Because segment 1 and segment 4 are 
active segments, connection 21 is an active connection. Connections 22 and 
23 connect spare segments 2 and 5, and spare segments 3 and 10, 
respectively, and are therefore spare connections. Each connection is 
identified by a "triplet" that specifies segments and the interconnecting 
node. For example, the triplet "1B4" identifies connection 21, and triplet 
"3B10" identifies connection 23. Restoration node C contains a single 
spare connection 24, which connects spare segment 10 to spare segment 12. 
Restoration node D contains three connections 25-27. Connection 25 
connects active segment 4 with active segment 7 and is therefore an active 
connection. Connections 26 and 27 connect spare segments 5 and 8 and spare 
segments 13 and 9, respectively, and are therefore spare connections. The 
spare segments 2, 3, 5, 6, and 8-13 and the spare connections 22-24 and 
26-27 represent the spare capacity of the example communications network. 
FIG. 3 illustrates a triplet table that contains intermediate results of 
the pre-patching system. Each row in the triplet table represents a spare 
connection that exists in the original configuration of the network or a 
new connection that is created by a restoration plan. The pre-patching 
system uses the triplet table to track the count of the number of times 
each connection is created, destroyed, or used "as is" in the restoration 
plans. The triplet column 301 contains the triplets that identify the 
various connections. The connection numbers are shown in parenthesis 
(e.g., "2B5 (22)"). The "already exists" column 302 contains a Boolean 
value, "T" or "F," indicating whether the connection represented by the 
triplet existed in the original configuration of the communications 
network. The "number of times created" column 303 contains a count of the 
number of times the connection was created in the restoration plans. The 
"number of times destroyed" column 304 contains a count of the number of 
times the connection was destroyed in the restoration plans. The "number 
of times used `as is`" column 305 contains a count of the number of times 
the existing spare connection is used "as is" in the restoration plans. 
The pre-patching system initially identifies all existing spare connections 
within the original configuration of the communications network and adds a 
row for each identified spare connection to the triplet table. The triplet 
table corresponding to the example communications network thus initially 
contains five rows, one for each spare connection. Since each spare 
connection exists in the original network communications, the "already 
exists" column has the value "T" for each row. 
The pre-patching system then analyzes the restoration plans that have been 
developed to reconfigure the network using spare segments to bypass 
network failure. The restoration plans may also indicate restoral routes 
that would likely be implemented if the restoral routes are identified 
dynamically at the time of failure by a dynamic restoration system. In 
this analysis of restoration plans, the pre-patching system identifies 
each existing spare connections that is used "as is," each existing spare 
connection that is destroyed, and each new connection that is created. A 
row for each identified connection is added to the triplet table (if one 
does not already exist). For each identified connection, the pre-patching 
system increments the counts appearing in the appropriate columns of the 
row of the triplet table corresponding to the identified connection. For 
example, if a restoration plan indicates that a new connection is to be 
created, then the "number of times created" column for the row 
corresponding to the new connection is incremented. 
FIG. 4 illustrates an example restoration plan that bypasses segment 4. 
This restoration plan represents the restoral route comprising active 
segment 1, spare segment 5, and active segment 7. The restoration plan 
creates two new connections 28 and 29, in order to incorporate spare 
segment 5 into the restoral route and destroys two connections 22 and 26 
that existed in the original configuration. FIG. 5 illustrates the updates 
to the triplet table as a result of processing this restoration plan. The 
two new connections 28 and 29 are identified by triplets "1B5" and "5D7," 
respectively. The pre-patching system adds new rows for these connections 
to the triplet table. The pre-patching system sets the "number of times 
created" column for these new rows to 1 since this is the first 
restoration plan that has been processed in which these connections are 
created. Existing connections 22 and 26 are identified by the triplets 
"2B5" and "5D8," respectively. The triplet table already contains rows for 
these connections. The pre-patching system sets "number of times 
destroyed" column to 1 since this is the first restoration plan in which 
the connections are destroyed. 
FIG. 6 illustrates a second restoration plan that bypasses active segments 
1 and 4. This restoration plan represents the restoral route comprising 
spare segments 2 and 5, and active segment 7. The restoration plan uses 
existing connection 22 "as is," creates new connection 29, and destroys 
existing spare connection 26. Although the restoration plan would also 
destroy connection 25, since it is an active connection, it must be 
included in the initial configuration and thus is not considered as a 
connection that can be destroyed. FIG. 7 illustrates the updates to the 
triplet table as a result of processing this restoration plan. The 
pre-patching system increments the "number of times used `as is`" column 
for the row corresponding to triplet "2B5" to 1. The pre-patching system 
increments the "number of times created" column for the row corresponding 
to triplet "5D7" to 2. The pre-patching system increments the "number of 
times destroyed" column for the row corresponding to triplet "5D8" to 2. 
FIG. 8 illustrates a third restoration plan that bypasses segments 1, 2, 
and 4-7. This restoration plan represents the restoral route comprising 
spare segments 3, 10, 12, and 9. The restoration plan uses the existing 
connections 23 and 24 "as is," destroys the existing connection 27, and 
creates the new connection 30. FIG. 9 illustrates the updates to the 
triplet table as a result of this restoration plan. The new connection 30 
is identified by triplet "12D9." The pre-patching system adds a new row 
for the new connection 30 to the triplet table. The pre-patching system 
sets the "number of times created" column for the new row to 1. The 
pre-patching system also increments the "number of times used `as is`" 
column for connections 23 and 24 and the "number of times destroyed" 
column for connection 27 to 1. 
FIG. 10 illustrates a fourth restoration plan that bypasses segments 1 and 
4. The restoration plan represents a restoral route comprising spare 
segments 2 and 5, and active segment 7. The restoration plan uses the 
existing connection 22 "as is," creates new connection 29, and destroys 
connection 26. FIG. 11 illustrates updates to the triplet table as a 
result of processing this restoration plan. The pre-patching system 
increments the "number of times used `as is`" column for connection 22 to 
2, increments the "number of times created" column for connection 29 to 3, 
and increments the "number of times destroyed" column for connection 26 to 
3. 
FIG. 12 illustrates a final restoration plan that bypasses segments 1, 2, 
and 4-6. The restoration plan represents a restoral route comprising spare 
segments 3, 10, and 12, and active segment 7. The restoration plan uses 
the spare connections 25 and 26 "as is" and creates a new connection 31. 
FIG. 13 illustrates the updates to the triplet table as a result of 
processing this restoration plan. The pre-patching system adds a row for 
the new connection 31 and sets the "number of times created" column to 1 
for that row. The pre-patching system also increments the "number of times 
used `as is`" column for connections 23 and 24 to 2. 
The final triplet table indicates that connection 26 was destroyed three 
times in the five restoration plans and that connection 26 was never used 
"as is." Therefore, connection 26 would be a prime candidate to be 
destroyed in the initial configuration. In this way, the time-consuming 
task of destroying this connection is avoided when the restoration plans 
that destroy the connection are implemented in response to network 
failures. Since connection 25 is never used in a restoration plan, there 
is no reason for it to be included in the original configuration of the 
network. Conversely, connection 29 is created in three of the five 
restoration plans. 
FIG. 14 displays a control flow diagram for an implementation of the 
"pre-patching" program. This program generates the triplet table and 
determines which connections should be created or destroyed in the initial 
configuration. In step 1401, the program identifies the spare connections 
that exist in the original network configuration and records the 
identified connections in the triplet table. In step 1402, the program 
analyzes the restoration plans provided as input to the program in the 
manner illustrated in the example above with cumulative results of the 
analyses stored in the triplet table. In step 1403, the program analyzes 
the cumulative results stored in the triplet table and proposes 
modifications to the original network configuration, including creating 
new connections and destroying existing spare connections. In the optional 
step 1404, the program implements these proposed modifications by sending 
appropriate configuration signals to the affected restoration nodes. 
FIG. 15 is a flow control diagram for a routine that identifies spare 
triplets. This routine identifies and records in the triplet table 
existing spare connections in the original network configuration. In step 
1501, the routine identifies the next spare segment in the original 
network configuration starting with the first spare segment. In step 1502, 
if all the spare segments have already been identified, then the routine 
returns, else the routine continues at step 1503. In step 1503, the 
routine records any spare triplets related to the identified spare segment 
in the triplet table if they have not already been previously added to the 
triplet table and loops to step 1501 to identify the next spare segment in 
the original network configuration. 
FIG. 16 is a control flow diagram of an implementation of a routine that 
analyzes the restoration plans. The routine analyzes the restoration plans 
provided as input and suggests connections that should be created or 
destroyed in the initial configuration. In steps 1601-1609, the routine 
loops selecting and processing each restoration plan. In step 1601, the 
routine retrieves the next restoration plan starting with the first. In 
step 1601a, if all the restoration plans have already been retrieved, then 
the routine returns, else the routine continues at step 1602. In step 
1602, the routine identifies the next triplet in the restoral route 
represented by the retrieved restoration plan, starting with the first 
triplet. In step 1603, if all the triplets have already been identified, 
then the routine loops to step 1601 to retrieve the next restoration plan, 
else the routine continues at step 1604. In steps 1604, 1606, and 1608, 
the routine determines whether the identified triplet is used "as is," 
destroyed, or created by the retrieved restoration plan. In step 1604, if 
the identified triplet represents a spare connection used "as is," then in 
step 1605, the routine increments the "number of times used `as is`" 
column for that triplet. In step 1606, if the identified triplet is an 
existing spare connection that has been destroyed, then in step 1607, the 
routine increments the "number of times destroyed" column for that 
triplet. In step 1608, if the identified triplet is a newly created 
connection, then in step 1609, the routine adds a row for the identified 
triplet to the triplet table if a row for that triplet has not already 
been added. The routine then increments the "number of times created" 
column for the row corresponding to that triplet. 
FIG. 17 is a flow control diagram of an implementation of a routine that 
determines which connections to create and destroy. This routine 
determines which connections to create and destroy based on the cumulative 
results of the analysis of the restoration plan stored in the triplet 
table. In step 1701, the routine retrieves the next triplet from the 
triplet table, starting with the first triplet in the table. In step 1702, 
if all the triplets have already been retrieved, then the routine returns, 
else the routine continues at step 1703. In step 1703, if the connection 
represented by the retrieved triplet is an existing spare connection, then 
the routine continues at step 1704, else the routine continues at step 
1705. In step 1704, the routine analyzes the counts stored in the triplet 
table for the retrieved triplet to determine whether that spare connection 
should be destroyed in the original network configuration or whether that 
spare connection should remain "as is" in the original network 
configuration. In step 1705, the routine analyzes the counts stored in the 
triplet table for the retrieved connection to determine whether the 
connection should be created in the original network configuration. 
The determination as to whether an existing spare connection should be 
destroyed or left "as is" can be made in many different ways. For example, 
the pre-patching system can divide the counts of the number of times an 
existing spare triplet is destroyed and used "as is" by the total number 
of restoration plans analyzed. This gives a percentage of times that that 
connection was destroyed and was used "as is." These percentages can then 
be matched against threshold percentages to make the determination of 
whether to destroy or retain the connection. Thresholds can be established 
by any number of factors, including the cost of destroying connections. 
The priorities of traffic restored by a restoration plan can also be 
factored into the analysis. For instance, if a given existing spare 
connection is destroyed 60% of the time, but always for low priority 
traffic, and is used "as is" 20% of the time, but always for high priority 
traffic, then the thresholds and the method of comparing computed 
percentages to thresholds may indicate that it is better to retain that 
existing spare connection than to destroy it, despite that it is destroyed 
far more often than it is used "as is" on a purely percentage basis. The 
determination as to whether to create a spare connection can also be made 
in various ways. For example, if the percentage of the restoration plans 
that create the spare connection exceeds a pre-determined threshold, the 
connection should be created in the initial configuration. Also, as 
described previously, the counts in the triplet table can be weighted 
based on the anticipated frequency in which a restoration plan is used and 
based on priority of the trunk that has failed. 
Although the present invention has been described in terms of one 
embodiment, it is not intended that the invention be limited to this 
embodiment. Modifications within the spirit of the invention would be 
apparent to those skilled in the art. For example, the present invention 
can be used to propose an original configuration for any type of 
communications network (e.g., Internet or other computer-based network). 
The scope of the present invention is defined by the claim is that follow.