JPH11163878A - Spare route setting method - Google Patents

Abstract

(57) [Summary] [Problem] To set a plurality of backup routes for one working route and realize a high recovery rate against a failure due to a failure. SOLUTION: A first spare route is set, a spare capacity capable of recovering from a failure in all one link failures is determined in that situation, and a spare route after the second spare route is determined in consideration of the spare capacity. Make settings.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to an ATM (Asynchronou).
s Transfer Mode). The present invention relates to a technique for setting a plurality of backup routes for one working route.

[0002]

2. Description of the Related Art In an ATM communication network, when a failure occurs in a working route, a backup route is widely set in advance to recover the working route.

[0003] A conventional backup route setting method will be described with reference to FIG. FIG. 6 is a diagram for explaining a conventional backup route setting method. As shown in FIG. 6, the working route and the backup route are configured by a plurality of nodes and links. In the conventional backup route setting method, only one backup route is set for the working route so as to be independent of the route, ie, not to share the same link or node with each other (R. Kawamura et.al.) Self-healing Virt
ual Path Architecture in ATM Networks ", IEEE Commun
ication Magazine, vol. 33, No. 9, 1995).

[0004]

Therefore, when setting a plurality of backup routes for one working route, there is no specific study on how to set those backup routes.

[0005] Therefore, when a plurality of backup routes are conventionally set for one working route,
Without setting the spare route after the second spare route among the plurality of spare routes in consideration of the spare capacity,
In addition, there is no need to consider whether to set a spare route after the second spare route independently of the previously set spare route among the plurality of spare routes.

SUMMARY OF THE INVENTION The present invention has been made in such a background. In an ATM communication network in which a plurality of protection routes are set for one working route, a protection method is used to improve a path recovery rate as much as possible. An object of the present invention is to provide a preliminary route setting method capable of setting a route.

[0007]

SUMMARY OF THE INVENTION The present invention is based on the assumption that each link included in an ATM communication network has a failure, and efficiently uses a spare capacity reserved to recover from the failure. The most main feature is to set a plurality of spare routes for a route.

That is, a failure is assumed for each link included in the ATM communication network, and a spare capacity for restoring this is set for each link. This is used as the initial spare capacity. This initial reserve capacity is not constant for each link. The present invention is characterized in that a spare route is set in order from a link in which the spare capacity is set as large as possible, and the spare capacity is used efficiently.

First, assuming a failure in one link in the ATM communication network, a path having a working route passing through this link is extracted as a path group. It is assumed that a first backup route is set for each of these paths.

Next, it is assumed that a failure of a path included in the path group has been recovered by the first backup route. The spare capacity of each link secured at this time is defined as a reserved spare capacity. A spare capacity obtained by subtracting the reserved spare capacity from the initial spare capacity is defined as a remaining spare capacity.

Here, a second spare route is set,
At this time, a plurality of second preliminary route candidates are extracted. Then, a route including a link having a large remaining spare capacity among the candidates is set as a second spare route. This procedure is repeated up to the n-th backup route. At this time,
When there are a plurality of links included in the spare route, a route including a larger number of links having a large remaining spare capacity is selected.

[0012] Thus, a spare route can be set from a link having a larger remaining spare capacity. At this time, a certain spare route may not share a link and a node with another spare route at all, or may allow some sharing. When no link is shared at all, the reliability at the time of failure recovery can be increased. However, by sharing a part of the link, the number of backup routes for one working route can be easily increased. Therefore, even when sharing a part, the number of backup routes for one working route is increased. Thereby, the reliability at the time of failure recovery can be improved.

That is, the present invention is a backup route setting method for an ATM communication network in which one route is composed of a plurality of nodes and links, and a plurality of backup routes are set for one working route.

Here, a feature of the present invention is that a first spare route for each working route is set, and an initial spare capacity that can recover from a failure in all one link is set for each link. Assuming the failure of one link, the reserved spare capacity of the link included in the first spare route to be secured to recover the failure of the working route including this link is checked, and the reserved spare capacity is subtracted from the initial spare capacity. To calculate the remaining spare capacity, set a second spare route candidate, refer to the remaining spare capacity of the links included in this candidate, and select the link having the relatively large remaining spare capacity among the candidates. A second preliminary route candidate including a large number is set as a second preliminary route.

The reserved spare capacity of the first to n-th spare routes is subtracted from the initial spare capacity to calculate the remaining spare capacity, and the (n + 1) th spare route candidate is set, and the links included in this candidate are set. , The (n + 1) th spare route candidate including the largest number of links having a relatively large remaining spare capacity among the candidates is referred to as the (n +
It is desirable to set as a backup route of 1). However, it is an integer of n ≧ 2. Further, it is desirable to assume one link failure for each link.

[0016] The backup route to be set may not share a link with the backup route already set, or the backup route to be set may be a link between the backup route already set and some links. May be allowed.

[0017]

Embodiments of the present invention will be described with reference to FIG. FIG. 1 is a diagram showing a configuration of an ATM communication network according to an embodiment of the present invention.

In the present invention, one route includes a plurality of nodes A
This is a backup route setting method for an ATM communication network in which a plurality of backup routes are set for one working route. In the example of FIG. 1, a plurality of backup routes (link 4 ← → link 5) and (link 3 ← → link 8 ← → link 9 ← → link 7 ← → link 2) are set for the path P1 which is the working route. Is done.

Here, a feature of the present invention is that a first spare route is set for each working route, and an initial spare capacity that can recover from a failure in all one link is set for each link. Assuming the failure of one link, the reserved spare capacity of the link included in the first spare route to be secured to recover the failure of the working route including this link is checked, and the reserved spare capacity is subtracted from the initial spare capacity. To calculate the remaining spare capacity, set a second spare route candidate, refer to the remaining spare capacity of the links included in this candidate, and select the link having the relatively large remaining spare capacity among the candidates. A second preliminary route candidate including a large number is set as a second preliminary route.

The reserved spare capacity of the first to n-th spare routes is subtracted from the initial spare capacity to calculate the remaining spare capacity, and the (n + 1) th spare route candidate is set, and the link included in this candidate is set. , The (n + 1) th spare route candidate including the largest number of links having a relatively large remaining spare capacity among the candidates is referred to as the (n +
Set as a backup route of 1). However, it is an integer of n ≧ 2. It is also assumed that one link fails for all links.

In the first embodiment of the present invention, the backup route to be set does not share a link with the backup route already set.

In the second embodiment of the present invention, the spare route to be set is allowed to share some links with the already set spare route.

[0023]

DESCRIPTION OF THE PREFERRED EMBODIMENTS (First Embodiment) A first embodiment of the present invention will be described with reference to FIGS. FIG. 1 is as described above. FIG. 2 is a diagram for explaining a method of obtaining the spare capacity. FIG. 3 is a diagram for explaining the setting of the backup route. FIG. 4 is a flowchart showing the operation of the first embodiment of the present invention.

In FIG. 1, the number of route-independent routes between nodes is "3". 1 path between all nodes A to I
The message processing time in the nodes A to I is the same for all the nodes A to I, and the message propagation delay is also the same for all the links 1 to 16. The bandwidths of the paths are all the same. Here, it is set to "1". The working route of each path is set to the shortest route connecting the nodes, and the first protection route is the shortest route independent of the working route. Is set to root. For example, the working route of the path between the node A and the node B passes only through the link 1, and the first backup route passes through the links 4 and 5.

Then, the spare capacity is determined as a capacity that is 100% recoverable from all one-link failures. A method of obtaining the spare capacity will be described with reference to FIG. FIG. 2 is a diagram for explaining how to find the spare capacity. The node is P,
Q and R are three, and links are 51, 52, and 53. One path is set between all nodes,
All the bands are set to “1”. That is, the working route of the path P51 between the nodes P and Q passes through the link 51, the working route of the path P52 between the nodes Q and R passes through the link 52, and the working route of the path P53 between the nodes R and P is , Via the link 53.

It is assumed that the backup route is set independently of the working route. That is, the backup route of the path P51 passes through the links 52 and 53, the backup route of the path P52 passes through the links 51 and 53, and the backup route of the path P53 passes through the links 51 and 52.

Now, if the link 51 is disconnected due to a failure, the backup route of the path P51 becomes a new working route. Therefore, in order to be able to recover from a failure in the event of a link 51 failure, the links 52 and 53 need a spare capacity of “1”. Similarly, in order to be able to recover from a failure in the event of a link 52 failure, the links 51 and 53 each require a spare capacity of “1”. Similarly, in order to be able to recover from a failure in the event of a link 53 failure, the links 51 and 52 each require a spare capacity of “1”.

Therefore, for all 1-link failures, the spare capacity that can recover from the failure is as follows: {link 51, link 52, link 53} = {1, 1,
1｝. When the principle shown in FIG. 2 is applied to the ATM communication network shown in FIG. 1, ｛link 1, link 2, link 3, link 4, link 5, link 6, link 7, link 8, link 9, link 10, Link 11, Link 12, Link 13, Link 1
4, link 15, link 16} = {3, 2, 2, 2,
2, 2, 3, 2, 2, 3, 2, 1, 1, 4, 4, 2}.

It is assumed that the link 1 has been disconnected for the spare capacity thus determined. The path via the link 1 is a path P1 via only the link 1 between the nodes A and B, a path P2 via the links 1 and 2 between the nodes A and C, and links 1 and 3 between the nodes B and D.
Are the three paths P3 passing through.

The first spare route of the path P1 goes through the links 4 and 5, the first spare route of the path P2 goes through the links 4 and 6, and the first spare route of the path P3 goes through the link 5. And 8.

Therefore, the reserved spare capacity required for the paths P1 to P3 to be able to recover from a failure is "2" for the links 4 and 5, "1" for the links 6 and 8, and "0" for the other links. It is. Then, the capacity “1” of the link 2 used by the working route of the path P2 and the capacity “1” of the link 3 used by the working route of the path P3 are released. Therefore, the reserved spare capacity is as follows: ｛link 1, link 2, link 3, link 4, link 5, link 6, link 7, link 8, link 9, link 10, link 11, link 12, link 13, link 1.
4, link 15, link 16} = {0, -1, -1,
2, 2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0,
0｝. As a result, the residual spare capacity (RSC: Residual
Spare Capacity) is ｛3,2,2,2,2,2,3,2,2,3,2,1,
1, 4, 4, 2}-{0, -1, -1, 2, 2, 1,
0, 1, 0, 0, 0, 0, 0, 0, 0, 0} = {x,
3, 3, 0, 0, 1, 3, 1, 2, 3, 2, 1, 1,
4, 4, 2}. A feature of the present invention resides in that backup routes subsequent to the second backup route are set in consideration of the remaining backup capacity.

In the first embodiment of the present invention, it is assumed that the same link is not shared between the backup routes.
In the example of FIG. 1, the second backup route of the path P1 is the only link 3 ← → link 10 ← → link 15 ← → link 16 ←
→ Link 14 ← → Link 7 ← → Set as a route via Link 2. The reserved spare capacity in this case is $ 0,
1,1,0,0,0,1,0,0,1,0,0,0,
1, 1, 1}. The remaining spare capacity at this time is Δx, 2, 2, 0, 0, 1, 2, 1, 2, 2, 2,.
1, 1, 3, 3, 1}.

In the example of FIG. 1, the second spare route is uniquely determined. However, when there are a plurality of candidates, the reserved spare capacity is referred to, and among the candidates, the remaining spare capacity is relatively large. A second backup route candidate including the largest number of links is set as a second backup route.

The operation of the first embodiment of the present invention will be described with reference to FIG. FIG. 4 shows the operation of the first embodiment of the present invention extended to the setting of the j-th backup route. However,
j is an integer of 2 or more. I is a natural number.

First, an initial spare capacity is set as an initial setting using the principle shown in FIG. 2 (S1). Where i = 1
Assume that the link 1 is disconnected. Here, "2" is substituted for j (S2). A path having a working route via link 1 is set as a path group (S3). The remaining spare capacity R after the paths included in the path group are restored
SC is obtained (S4). The path for which the second backup route has already been set is deleted from the path group, and the capacity secured by the backup route for that path is subtracted from the remaining backup capacity RSC (S5). At this point, if there are still paths remaining in the path group (S6), an arbitrary path is selected from the path group (S7), and as many as possible and independent of the previously set backup route of the selected path. A route whose remaining spare capacity RSC of the link is equal to or larger than the band of the path is set as a second spare route of the selected path (S8). The capacity secured by the set spare route is subtracted from the remaining spare capacity RSC, and the selected path is deleted from the path group (S
9). This procedure (S6 to S9) is repeated until no paths are left from the path group.

Further, if necessary (S10), "1" is added to j (S12), and the procedure (S3 to S9) is repeated. If necessary (S11), "1" is added to i (S13), and the procedure (S2 to S10) is repeated.

(Second Embodiment) A second embodiment of the present invention will be described with reference to FIG. FIG. 5 is a flowchart showing the operation of the second embodiment of the present invention. The second embodiment of the present invention is characterized in that a part of a link is allowed to be shared between backup routes when setting a backup route. Thus, when compared with the first embodiment of the present invention, at first glance, there is an impression that the reliability of the failure recovery is somewhat inferior, but since the degree of freedom in setting the backup route is improved, it is possible to set one backup route for one working route. Since a larger number of backup routes can be set more easily than in the first embodiment of the present invention, the reliability of failure recovery is not inferior to that of the first embodiment of the present invention.

First, an initial spare capacity is set as the initial setting by using the principle shown in FIG. 2 (S21). Where i =
As 1, assume that link 1 is disconnected. Where j
Is substituted for "2" (S22). A path having a working route via link 1 is set as a path group (S2
3). The remaining spare capacity RSC after the paths included in the path group have been restored is obtained (S24). Delete the path for which the second backup route has already been set from the path group,
The capacity reserved by the backup route for the path is the remaining spare capacity R
Subtract from SC (S25). At this point, if there is still a path in the path group (S26), an arbitrary path is selected from the path group (S27), and a part of the route overlaps with the previously set backup route of the selected path. Better, and the remaining spare capacity RSC of as many links as possible
Route that is greater than or equal to the bandwidth of the path
(S28). The capacity secured by the set spare route is subtracted from the remaining spare capacity RSC, and the selected path is deleted from the path group (S29). This procedure (S26 to S29) is repeated until no paths are left from the path group.

Further, if necessary (S30), "1" is added to j (S32), and the procedure (S23 to S29) is repeated. If necessary (S31), "1" is added to i (S33), and the procedure (S22 to S30) is repeated.

[0040]

As described above, according to the present invention,
In an ATM communication network in which a plurality of backup routes are set for one working route, a backup route can be set so as to improve the path recovery rate as much as possible.

[Brief description of the drawings]

FIG. 1 is a diagram showing a connection configuration of nodes and links for explaining an embodiment of the present invention.

FIG. 2 is a diagram for explaining a method of obtaining a spare capacity.

FIG. 3 is a diagram illustrating the setting of a backup route.

FIG. 4 is a flowchart showing the operation of the first embodiment of the present invention.

FIG. 5 is a flowchart showing the operation of the second embodiment of the present invention.

FIG. 6 is a diagram for explaining a conventional backup route setting method.

[Explanation of symbols]

 1 to 16 links A to I, P to R nodes P1 to P3 path

Claims (5)

[Claims] 1. A backup route setting method for an ATM communication network in which one route is composed of a plurality of nodes and links, and a plurality of backup routes are set for one working route. In order to set one spare route, set an initial spare capacity that can recover from failure for all one link failures for each link, and recover from failure of the working route including this link assuming failure of one link The reserved spare capacity of the link included in the first spare route to be secured is checked, the reserved spare capacity is subtracted from the initial spare capacity to calculate a remaining spare capacity, and a second spare route candidate is set. Referring to the remaining spare capacity of the link included in the candidate, a second spare route candidate including the largest number of links having a relatively large remaining spare capacity among the candidates is referred to as a second spare route. Spare route setting method and setting the bets. 2. The remaining spare capacity is calculated by subtracting the reserved spare capacity of the first to n-th spare routes from the initial spare capacity, and sets an (n + 1) th spare route candidate, which is included in the candidate. The (n + 1) th spare route candidate including the largest number of links having a relatively large remaining spare capacity among the candidates is referred to as the (n +
2. The backup route setting method according to claim 1, wherein the backup route is set as the backup route of 1). Where n ≧ 2 3. The backup route setting method according to claim 1, wherein one link failure is assumed for all links. 4. The backup route to be set does not share a link with the backup route already set.
3. The method for setting a spare route according to any one of items 1 to 3. 5. The backup route setting method according to claim 1, wherein the backup route to be set allows some links to be shared with the already set backup route.