JP4182872B2 - Fault recovery path search method and fault recovery path search program in communication network - Google Patents

Description

  The present invention relates to a failure recovery route search method and a failure recovery route search program in a communication network, and in particular, a section [m, m between an active path passing through nodes 1 to k (k: positive number) and a node of the active path. +1] (1 ≦ m <k, m: integer) spare resources for each section are prepared for each section, and the failure recovery path in the communication network that performs the failure recovery operation according to the failure location when a failure occurs The present invention relates to a failure recovery route search method and a failure recovery route search program in a communication network.

  Conventional failure recovery methods can be roughly divided into the following two types. One is called “path end switching” and the other is called “failure end switching”.

  In the path edge switching method, when a failure occurs in a route that has been used, the route is switched to a new route that does not overlap with the route that has been used so far, from the start node to the end node of the route ( For example, see non-patent documents 1 and 2). Here, a new route to be used after a failure is determined in advance as a backup route before the occurrence of the failure.

  On the other hand, the failure end switching is a method in which only a failed part is restored by a substitute route, and the other part is used as it is. One way to achieve this is IP rerouting. As a protocol for realizing IP rerouting, RIP Version2, OSPF and the like have been devised (for example, see Non-Patent Documents 3 and 4). However, IP rerouting determines a new route after a failure occurs and the network topology changes, and pre-reservation type restoration cannot be realized, and there is no method for calculating a backup path route adapted to it.

  As described above, there is no technique in the prior art that can reserve a preliminary route in advance and that can cope with restoration restoration at the failure end.

  Here, a method is assumed in which a path is assumed on a certain network and a route that can substitute a part of the path is determined.

  The conditions assumed for the network and the path on the network are shown below.

  (1) The network topology is represented by a directed label graph G using nodes having IDs, edges (links) between them, and weights attached to the links.

  (2) The weight value given to the link is always a positive value.

  (3) If there is a link from one node to another node, there is always a link in the opposite direction. In addition, it is assumed that the weight values given to two links in which opposite nodes are opposite and have the same node at both ends are equal.

  (4) On the graph G, a path P composed of N nodes and N−1 links is given (where N ≧ 2).

  (5) P is an unbranched route having a start point (Ingress node) and an end point (Egress node).

  (6) A node constituting P knows addresses of all nodes constituting P other than itself and all adjacencies.

  (7) P is not necessarily the optimum route.

  (8) When P is traced from the Ingress node to the Egress node, the kth component node of P appears as NODE [k], and the kth link appears as LINK [k].

  (9) The cost of passing is given to the link weight, and the cost of LINK [k] is LINK_WEIGHT [k].

  (10) The optimum route between NODE [a] and NODE [b] is h [a, b], and the cost is represented by COST [a, b].

  (11) NODE [i] has the following information.

      The number of nodes adjacent to NODE [i] DEG [i].

      Cost from NODE [i] to adjacent node ADJ [i, j].

        ADJ_WEIGHT_OUT [i, j] (j = 1 to DEG [i]).

      The cost ADJ_WEIGHT_IN [j, i] (j = 1 to DEG [i]) from the adjacent node ADJ [i, j] to NODE [i].

  An example of a network and a path having such conditions is shown in FIG. 16, and a path expression method is shown in FIG. Here, it is desired to determine substitute routes s [1] to s [N-1] for N-1 links from LINK [1] to LINK [N-1]. The relationship between LINK [k] and s [k] is shown in FIG.

  However, the above conventional method has the following problems to be solved.

  In path end switching, the selection of a backup path is subject to the restriction that the backup path must not overlap with the original path, and the backup path and the original path must have the same end point and start point. For this reason, at the time of failure recovery, it is necessary to control a portion that is not related to the failure, and the portion that does not have a failure is affected by the failure recovery.

  In addition, IP rerouting, which is failure edge switching, has a problem that it takes a long time from failure to recovery because a substitute route is calculated after the failure is detected.

  These problems can be solved by a method of switching to a substitute route at the failure end and pre-reserving the substitute route, but such a method has not been realized so far. One reason for this is that there was no efficient method for calculating a substitute route.

  The present invention has been made in view of the above points, and when switching to a substitute route at the failure end, a failure in a communication network using a substitute route calculation method that minimizes the range for performing failure recovery control. An object of the present invention is to provide a recovery route search method and a failure recovery route search program.

  FIG. 1 is a diagram for explaining the principle of the present invention.

The present invention is for a failure in a section [m, m + 1] (1 ≦ m <k, m: integer) between a working path passing through nodes 1 to k (k: positive number) and a node of the working path. Prepared for each section, and a failure recovery path in a communication network performed by a node device on a communication network that performs a failure recovery operation according to a failure location when a failure occurs or a device that controls the communication network In the search method,
The node device calculation means
When calculating the backup path for failure recovery, the sum of the weights of all links existing in the communication network excluding the link of the calculation target current section for calculation of the calculation target current section [m, m + 1]. A detour route calculation process (step 1) for calculating a detour route by giving a larger value;
If the calculation result of the detour route shares the other path with the working path (step 2), the section including the calculation target section [m, m + 1] by removing the overlapping part of the working path and the other section And a backup route determination process (step 3).

  Further, according to the present invention, in the backup route determination process, the detour route calculation process and the backup route determination process are performed again for the section including the calculation target section obtained by removing the overlapping portion.

  Further, in the detour route calculation process of the present invention, a method for obtaining the shortest route of the weighted directed graph is used.

  The Dijkstra method is used as a method for obtaining the shortest path of the weighted directed graph of the present invention.

The present invention is for a failure in a section [m, m + 1] (1 ≦ m <k, m: integer) between a working path passing through nodes 1 to k (k: positive number) and a node of the working path. Prepared for each section, and a failure recovery route search program to be executed by a node device on a communication network that performs a failure recovery operation according to a failure location when a failure occurs or a device that controls the communication network Because
An input step for inputting a value larger than the sum of the weights of all links existing in the communication network excluding the link of the calculation target working section for calculation of the calculation target working section [m, m + 1];
A calculation step for calculating a detour route using the input value as a backup route calculation for failure recovery,
When the calculation result of the detour route in the calculation step shares the active path and other sections, the overlapping part of the active path and other sections is removed and the section including the calculation target section [m, m + 1] And causing the computer to execute a backup route determination step of outputting the backup route.

  Further, according to the present invention, in the backup route determination step, the detour route calculation step and the backup route determination step are performed again for the section including the calculation target section obtained by removing the overlapping portion.

  Further, in the detour route calculation step of the present invention, a method for obtaining the shortest route of the weighted directed graph is used.

  In the detour route calculation step of the present invention, the Dijkstra method is used as a method for obtaining the shortest route of the weighted directed graph.

  As described above, according to the present invention, the range for performing the failure recovery control can be reduced by obtaining the shortest detour route by excluding the active line based on the calculation result of the backup route.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings.

  First, the necessary condition in the nature of the Dijkstra method used in the present invention is to find an optimum route between two nodes so that the weight (in this case, cost) given to the link is minimized. In order to obtain the optimum route, a directed label graph representing all nodes or links linked to them and their weights (positive values) is required.

  In the following description, A ← B indicates that the value of B is substituted for the value of A. Further, “DOWN” of MIN_DOWN means from downstream, and “UP” of MIN_UP means from upstream.

  The following operations are performed on a node device (computer) connected to the communication network or a device (computer) on a system that manages (or monitors) the communication network.

[First Embodiment]
In this embodiment, when LINK [k] between NODE [k] and NODE [K + 1] is not used, a route s [k] that can be used as a substitute for the link is determined. The procedure for finding such a route is shown below.

  The following procedures (1) to (3) are repeated from k = 1 to N-1.

  Procedure (1) Set the cost of LINK [k] to ∞.

  Procedure (2) The shortest path h [k, k + 1] is obtained by using the Dijkstra method between nodes at both ends of LINK [k] and NODE [k], NODE [k + 1].

  Procedure (3) If there is a shortest path, set s [k] ← h [k, k + 1], otherwise skip determination of s [k].

  Hereinafter, the above procedure will be described with reference to a flowchart.

  FIG. 2 is a flowchart of the operation in the first embodiment of the present invention.

  Step 101) As an initial value, 1 is substituted for k.

  Step 102) The cost of LINK [k] is set to ∞.

  Step 103) The shortest path h [k, k + 1] is obtained by using the Dijkstra method between the both end nodes of LINK [k], NODE [k], NODE [k + 1].

  Step 104) If the shortest path exists, the process proceeds to step 105, and if not, the process proceeds to step 106.

  Step 105) Substitute h [k, k + 1] for s [k] and proceed to Step 106.

  Step 106) If k becomes N-1, the process is terminated. If not, the process proceeds to Step 107.

  Step 107) Increment k and go to Step 102.

  As described above, when there is a route that does not pass LINK [k] between the nodes at both ends, a substitute route can be obtained.

[Second Embodiment]
This embodiment is a further improvement of the first embodiment described above. For example, consider the example shown in FIG. Here, for simplicity, bidirectional links and weights are represented by one line and one weight. In this network, when a substitute route of LINK [k] from NODE [k] to NODE [k + 1] is obtained by the method of the first embodiment, as shown by a dotted line in FIG. 3, NODE [k -1] is found. If the LINK [k] part of the path P is substituted with h ′ [k] obtained here, a redundant part is created in the new path P ′ obtained by substitution. The part of NODE [k] → NODE [k−1] is not necessary for the path P ′ and can be removed. In the first embodiment, it is inevitable that this redundant portion is generated, but in this embodiment, the path s [k] can be selected so that such a redundant portion is not generated.

  The conditions of the route s [k] obtained by this method are shown below.

  (Condition 1) Do not use LINK [k].

  (Condition 2) The start point and end point of the route are both nodes on P. The start point of s [k] is NODE [k] or a node on P that is ingress from NODE [k], and the end point is Node on P on the Egress side from NODE [k + 1] or NODE [k + 1].

  (Condition 3) Do not pass any node on P other than the start and end points.

  (Condition 4) The shortest path from NODE [k] to NODE [k + 1] or a part thereof.

  That is, the route s [k] to be obtained here is obtained from NODE [k] to obtain the shortest route h [k, k + 1] from NODE [k + 1], and h [k, k + 1] is set to P. It eliminates the redundant path that is created when it is inserted. FIG. 4 shows an example of h ′ [k] obtained in the first embodiment, and FIG. 5 shows an example of s [k] obtained by this method in the same network.

  In FIG. 5, the portion of NODE [k] → Node-a → NODE [k + 1] is removed from the path shown in FIG. 4 selected in the first embodiment.

  The procedure for obtaining the substitute path s [k] of LINK [k] for k = 1, 2... N−1 is shown below.

  S [1], s [2],..., S [N-1] can be obtained by performing the following steps (1) to (6) for k = 1 to N-1.

Procedure (1) As the route removal operation for the corresponding section (LINK [k]), the cost of LINK [k] is set to LINK_WEIGHT [k] ← ∞.

Procedure (2) After removing the corresponding section (LINK [k]) in the above procedure (1), the shortest path h [k] from NODE [k] to NODE [k + 1] to NODE [ N ] , M] (m = k + 1 to N) and the cost COST [k, m] (m = k + 1 to N) of h [k, m] are calculated by the Dijkstra method.

    i. If COST [k, k + 1] = ∞, the determination of s [k] is skipped.

    ii. If COST [k, k + 1] ≠ ∞, the process proceeds to step (3).

Procedure (3) Obtain m that gives the minimum values MIN_DOWN [k] and MIN_DOWN [k] in COST [k, m] for m = k + 1 to N. In addition, m at that time is set to m _{MIN — DOWN} [k].

Step (4) Shortest path h [m _{MIN_DOWN} [k], m] (m = 1 to k) from NODE [m _{MIN_DOWN} [k]] to NODE [1] to NODE [k-1] and its shortest path Cost COST [m _{MIN — DOWN} , [k], m] (m = 1 to k) is calculated by the Dijkstra method.

Procedure (5) _Obtain m giving COST [m, _{MIN_DOWN} [k]] for m = 1 to k. In addition, m at that time is set to m _{MIN_UP} [k].

Procedure (6) NODE [m _{MIN_UP} [k]] is obtained and s [k] ← h [m _{MIN_UP} [k], m _{MIN_DOWN} [k]].

  The above procedure will be described below using a flowchart.

  6 and 7 are flowcharts of operations in the second embodiment of the present invention.

  Step 201) Substitute 1 for k as an initial value.

  Step 202) Let LINK [k] cost LINK_WEIGHT [k] ← ∞.

Step 203) MIN_UP ← ∞, m _{MIN_UP} ← k + 1, MIN_DOWN ← ∞, m _{MIN_DOWN} ← k.

  Step 204) m ← N.

  Step 205) Calculate the shortest path h [k, m] (m = k + 1 to N) and the cost COST [k, m] (m = k + 1 to N) of h [k, m] by the Dijkstra method. .

  Step 206) It is determined whether or not the MIN_UP symbol COST [k, m]. If so, the process proceeds to Step 207. If not, the process proceeds to Step 208.

Step 207) MIN_UP ← COST [k, m], m _{MIN_DOWN} ← m.

  Step 208) Set m ← m-1.

  Step 209) If m = k, go to Step 210, otherwise go back to Step 205.

Step 210) h [m _{MIN_DOWN} , m] and COST [m _{MIN_DOWN} , m] are obtained by the Dijkstra method.

Step 211) It is determined whether MIN_DOWN ≧ COST [m _{MIN_DOWN} , m]. If so, the _{process proceeds to} Step 212, and otherwise, the _{process proceeds} to Step 213.

Step 212) MIN_DOWN ← COST [m _{MIN_DOWN} , m], m _{MIN_UP} ← m.

  Step 213) If m = 1, go to Step 215; otherwise, go to Step 214.

  Step 214) Set m ← m-1, and proceed to Step 210.

  Step 215) If COST [k, k + 1] ≠ ∞, go to Step 216, otherwise go to Step 219.

Step 216) h [m _{MIN_UP} , m _{MIN_DOWN} ] is _obtained by Dijkstra method.

Step 217) s [k] ← h [m _{MIN_UP} , m _{MIN_DOWN} ].

  Step 218) It is determined whether or not k = N−1. If yes, the process ends. If not, the process proceeds to Step 219.

  Step 219) Increment k and go to Step 202.

  The above procedures (1) to (6) will be described in detail.

  Procedure (1) The Dijkstra method LINK_WEIGHT [k] ← ∞ is intended not to use LINK [k] when selecting h [k, m]. If there is at least one finite cost path that starts with NODE [k] and ends with NODE [k + 1] other than LINK [k], h [k, m including LINK [k] in Dijkstra's method ] Is never determined.

  Step (2) If COST [k, k + 1] = ∞, it means that there is only one LINK [k] path from NODE [k] to NODE [k + 1]. That is, there is no h [k, m] that does not pass LINK [k]. An example of a network in such a case is shown in FIG. In such a case, since there is no route that can be s [k], the determination of s [k] is skipped. Here, since the cost of the link is equal in both directions, if COST [k, k + 1] ≠ ∞, COST [k + 1, k] ≠ ∞ is guaranteed.

Step (3) When h [k, k + 1] passes through NODE [p] (i + 1 ≦ p ≦ N) on the egress side from NODE [k], COST [k, k + 1] ≧ COST [ k, p]. Therefore, when tracing h [k, k + 1] from NODE [k] to NODE [k + 1], the node that reaches the first among the nodes on P on the Egress side from NODE [k] NODE [m _{MIN_DOWN} [k]]. Therefore, if m _{MIN — DOWN} [k]> k + 1, there may be a duplicate node with P between _NO [[ _{MIN_DOWN} [k]] and NODE [k + 1] of h [k, k + 1]. Recognize. By _selecting NODE [m _{MIN_DOWN} [k]] as the end point of the substitute route, it is excluded that the route as shown in FIG. 4 is selected.

Procedure (4) Similar to the description in (3) above, when h [m _{MIN_DOWN} [k], k] is traced from NODE [m _{MIN_DOWN} [k]] to NODE [k], the first NODE to be reached The node on P on the Ingress side from [k + 1] is NODE [m _{MIN_UP} [k]], so from NODE [k] of h [k, k + 1], NODE [m _{MIN_UP} [k]] It can be seen that there is a node that overlaps with P.

  Procedure (5) Determine s [k].

  In the method according to the present embodiment, if P is not set as the shortest path, the following part of P can be reset as the shortest path as necessary.

・ From NODE [m _{MIN_UP} [k]] to NODE [k].

・ From NODE [k + 1] to NODE [m _{MIN_DOWN} [k]].

  An example in which P of the network in FIG. 5 is reset by such a method is shown in FIG. Path Q is a path obtained by resetting P.

[Third Embodiment]
This embodiment is different from the above-described second embodiment in that the range through which the substitute route passes can be limited.

  For example, the start point of the substitute route is designated as NODE [a] on P, the end point of the substitute route is designated as NODE [b] on P, and the substitute route is a node on P except for the two nodes. Suppose that the restriction of not passing is imposed when selecting an alternative route. At this time, in the first embodiment and the second embodiment, the shortest path from NODE [a] to NODE [b] obtained using the Dijkstra method in each process satisfies such a restriction. Unless it happens to be included in the set of routes, no route that satisfies this constraint is found. FIG. 3 shows a specific example in the case where the first embodiment and the second embodiment do not work as described above. The route satisfying the request is NODE [k] → NODE-a → NODE [k + 1], but this route cannot be obtained by a method using the Dijkstra method. This is because, in the method using the Dijkstra method, only one route with the lowest cost is found, but information on routes other than the shortest route does not even know whether the route exists.

  In this embodiment, in this case, NODE [k] → Node-a → NODE [k + 1] can be selected as a substitute route. FIG. 4 shows an example of a network in which the same problem as in FIG. 3 occurs on the egress side.

  The condition of s [k] obtained in the present embodiment is as follows.

  (Condition 1) When the start point of the route is NODE [i] and the end point is NODE [j], among the routes satisfying the conditions (1) to (3) of s [k] of the second embodiment, The route with the smallest j-i.

  (Condition 2) Let NODE [i] be the starting point and NODE [j] be the end point of the path that satisfies all the conditions (1) to (4) of s [k] of the second embodiment. A part of NODE [i] to NODE [j] on the path P is replaced with a path that satisfies all the conditions (1) to (4) of s [k] of the second embodiment, and a new path P ′ is created. And At this time, the route that minimizes the cost of the route P ′ selected by the Dijkstra method from the routes satisfying the conditions (1) to (4) of s [k] of the second embodiment.

  The procedure for determining the substitute route s [k] for k = 1, 2,... N−1 of LINK [k] is shown below.

  S [1], s [2],... S [N-1] are obtained by performing the following steps (1) to (6) for k = 1 to N-1.

  Procedure (1) LINK [k] cost LINK_WEIGHT [k] ← ∞.

  Procedure (2) The shortest path h [k, k + 1] from NODE [k] to NODE [k + 1] and the cost COST [k, k + 1] of h [k, k + 1] are calculated by the Dijkstra method. calculate.

      i. If COST [k, k + 1] = ∞ and h [k, k + 1] does not exist, the determination of s [k] is skipped and the process proceeds to step (10).

    ii. If COST [k, k + 1] ≠ ∞, proceed to step (3).

  Step (3) From NODE [k] or NODE [k] From the node NODE [kp] (0≤p≤k-1) on the Ingress side and NODE [k + 1] or NODE [k + 1] Considering the node NODE [k + 1 + q] (0 ≦ q ≦ Nk−1) on the Egress side, a variable Δ of Δ≡1 + p + q (Δ = 1 to N−1) is defined.

  Procedure (4) Starting from Δ = 1, from Δ = 1 to N−1, the following procedures (5) to (8) are performed in ascending order of Δ.

  Procedure (5) In the graph G, consider a graph G ′ in which all the weights of links going to the nodes NODE [1] to NODE [N] on P are infinite. (Links from NODE [1] to NODE [N] in the opposite direction to those adjacent nodes do not change the weight).

  Procedure (6) The weight of the link toward NODE [k-p] and NODE [k + 1 + q] is returned from ∞ to the same value as the first graph G.

Procedure (7) All p satisfying Δ = 1 + p + q (0 ≦ p ≦ k−1, 0 ≦ q ≦ N−k−1) on the network which has been performed up to the procedure (6). About q
COST [k + 1-Δ, kp] + COST [kp, k + 1 + q] + COST [k + 1 + q, Δ + 1]
And set it as P'_COST [p, q].

Procedure (8) For p and q satisfying Δ = 1 + p + q (0 ≦ p ≦ k−1, 0 ≦ q ≦ N−k−1), the minimum value MIN [Δ] of P′_COST [p, q], p give it the value of q, p_ _MIN [Δ], seek q_MIN [Δ].

      i. If MIN [Δ] = ∞, Δ ← Δ + 1 is returned to step (4).

    ii. If MIN [Δ] ≠ ∞, proceed to step (9).

  Procedure (9) As s [k] ← h [p, min [Δ], q_min [Δ]], the procedure proceeds to procedure (10).

  Procedure (10) The calculation for the current k is terminated.

  A flowchart showing the above procedure is shown in FIGS.

  Step 301) Substitute 1 for k as an initial value.

  Step 302) Set LINK_COST [k] ← ∞.

  Step 303) h [k, m] and COST [k, m] are obtained by the Dijkstra method.

  Step 304) If COST [k, k + 1] ≠ ∞, go to Step 305, otherwise go to Step 327.

  Step 305) i ← 1.

  Step 306) Δ ← 1.

  Step 307) p ← 0 and q ← Δ−p−1.

  Step 308) For j = 1, 2... DEG [j], ADJ_WEIGHT_IN [j, i] ← ∞.

  Step 309) If i = N, go to Step 311; otherwise, go to Step 310.

  Step 310) Increment i and go to Step 308.

  Step 311) For j = 1, 2,... DEG [k + p], ADJ_WEIGHT_IN [j, k + p] ← ADJ_WEIGHT_OUT [k + p, j].

Step 312) For j = 1, 2,... DEG [k + 1 + q], ADJ_WEIGHT_IN [j, k + 1 + q
] ← ADJ_WEIGHT_OUT [k + 1 + q, j]

  Step 313) Set MIN [Δ] ← ∞.

  Step 314) Find h [k-p, k + 1 + q] and COST [k-p, k + 1 + q].

  Step 315) COST [k + 1- [Delta], kp] + COST [kp, k + 1 + q] + COST [k + 1 + q, [Delta] +1] is obtained and this is calculated as P'_COST [p, q] And

  Step 316) If MIN_ [Δ] ≧ P′_COST [p, q], go to Step 317, otherwise go to Step 318.

  Step 317) MIN [Δ] ≧ P′_COST [p, q], p_min [Δ] ← p, and q_min [Δ] ← q.

  Step 318) If p = k-1, then go to Step 320, otherwise go to Step 319.

  Step 319) Set q ← p + 1 and q ← q−1, and proceed to Step 308.

  Step 320) If MIN [Δ] ≠ ∞, go to Step 322, otherwise go to Step 321.

  Step 321) Δ ← Δ + 1, and the process proceeds to Step 307.

  Step 322) s [k] ← h [p_min [Δ], q_min [Δ]].

  Step 323) i ← 1.

  Step 324) For j = 1, 2,... DEG [i], ADJ_WEIGHT_IN [j, i] ← ADJ_WEIGHT [i, j].

  Step 325) If i = N, go to Step 327, otherwise go to Step 326.

  Step 326) Set i ← i + 1 and proceed to Step 324.

  Step 327) If k = N−1, the process is terminated; otherwise, the process proceeds to Step 328.

  Step 328) Set k ← k + 1, and proceed to Step 302.

  Each procedure as described above will be described in detail.

  Procedure (1) Similar to the second embodiment described above, LINK_WEIGHT [k] ← ∞ is intended not to use LINK [k] when selecting h [k, m]. ing. If there is at least one finite cost path that starts with NODE [k] and ends with NODE [k + 1] other than LINK [k], h [k, m including LINK [k] in Dijkstra's method ] Is never determined.

  Procedure (2) If COST [k, k + 1] = − ∞, it means that there is only one LINK [k] path from NODE [k] to NODE [k + 1]. That is, there is no h [k, m] that does not pass LINK [k]. As in the case of the second embodiment described above, the example shown in FIG. 8 is applicable to this case.

  Procedure (3) Define Δ so that j−i = Δ, where NODE [i] is the start point of the route and NODE [j] is the end point.

  Procedure (4) The one with a small Δ is preferentially obtained.

  Procedure (5) I want to prevent nodes on P from passing through nodes other than those with the start and end points of s [k]. For this purpose, first, the weights of links directed to the nodes on all P are set to ∞. In step (6) above, the weight of the link toward the start point and end point of s [k] is restored from ∞.

  Procedure (6) The cost from the adjacent node to the start point and end point of s [k] is changed from an infinite value to the original value so that it can be used.

Specifically, the weight from the start node NODE [k + p] and the end node NODE [k + 1 + q] to the adjacent node
ADJ_WEIGHT_OUT [k + p, j] (j = 1 to DEG [i]), ADJ_WEIGHT_OUT [k + 1 + q, j]
, The weights from adjacent nodes to NODE [k + p], NODE [k + 1 + q]
ADJ_WEIGHT_IN [j, k + p], ADJ_WEITHT_IN [j, k + 1 + q]
Assign to. Since weights are equal in both directions,
ADJ_WEITHT_OUT [k + p, j] (j = 1 ~ DEG [i]), ADJ_WEIGHT_OUT [k + 1 + q, j]
The original weight can be obtained from the value of.

  Step (7) When h [kp, k + 1 + q] is inserted into the path P from NODE [kp] to NODE [k + 1 + q] to create a new path P ′, Try to minimize costs. As described above, the cost is evaluated by adding COST [k + 1−Δ, kp] and COST [k + 1 + q, Δ + 1] because a substitute path having the same Δ as shown in FIG. This is to cope with the existing network topology. In the case of FIG. 12, there are a and b, both of which are Δ = 2, as substitute paths for LINK [k]. If only the substitute route is compared, a has a smaller cost than b. However, if the route from NODE [k-1] to NODE [k + 2] is compared, the route through b has a lower cost. Have. In such a case, the optimal substitute route is b.

  Procedure (8) If the desired route is not found in the current Δ, Δ is increased by one.

  Procedure (9) Determine s [k].

  Similarly to the second embodiment, even in the third embodiment, when P is not set as the shortest path, the following part of P may be reset as the shortest path as necessary. it can.

・ From NODE [k + 1−Δ] to NODE [kp];
・ From NODE [k + 1 + q] to NODE [Δ + 1];
In the network of FIG.
・ NODE [k-1] to NODE [k];
・ NODE [kp1] to NODE [k + 2];
This is the case.

[Fourth Embodiment]
In the present embodiment, a route created by inserting s [k] into P as a substitute for LINK [k] has no redundant portion, and a route with the smallest number of hops is selected when selecting a substitute route. (The third embodiment selects the route with the lowest cost). The selection of the route with the minimum number of hops is realized by using the Dijkstra method with the cost of all links as 1.

  The conditions in the present embodiment are shown below.

(Condition 1) Among those satisfying the conditions (1) to (4) of the second embodiment described above, when NODE [i] is the start point of the route and NODE [j] is the end point, NODE [i] Route with minimum number of hops in route h [i, j] to NODE [j]:
Next, the procedure for determining the substitute route s [k] for k = 1, 2... N−1 of LINK [k] is shown below.

  S [1], s [2],... S [N-1] are obtained by performing the following procedures (1) to (6) for k = 1 to N-1.

  Procedure (1) The weight of all links in the graph G is set to 1, and the graph in which G is changed in this way is set to G ′.

  Step (2) LINK [k] cost LINK_WEIGHT [k] ← ∞.

  Step (3) The cost COST [k, k + 1] of the shortest path h [k, k + 1] and h [k, k + 1] from NODE [k] to NODE [k + 1] is calculated by the Dijkstra method. calculate.

      i. If COSt [k, k + 1] = ∞ and h [k, k + 1] does not exist, the determination of s [k] is skipped and the process proceeds to step (12).

    ii. If COST [k, k + 1] ≠ ∞, the process proceeds to step (4).

  Step (4) Node NODE [kp] (0 ≦ p ≦ k−1) on the ingress side from NODE [k] or NODE [k] and Egress from NODE [k + 1] or NODE [k + 1] Considering the side node NODE [k + 1 + q] (0 ≦ q ≦ N−k−1), a variable Δ of Δ≡1 + p + q (Δ = 1 to N−1) is defined.

  Procedure (5) Starting from Δ = 1, from Δ = 1 to N−1, the following procedures (6) to (9) are performed in ascending order of Δ.

  Procedure (6) Consider a graph G ′ in which the weights of links to nodes NODE [1] to NODE [N] on P are all infinite in the graph G (NODE [1] to NODE [ N] to their neighbors will not change the weight).

  Procedure (7) The weight of the link toward NODE [k-p] and NODE [k + 1 + q] is returned from ∞ to the same value as the first graph G.

Procedure (8) On all the p and q satisfying Δ = 1 + p + q (0 ≦ p ≦ k−1, 0 ≦ q ≦ N−k−1) on the network formed as in the procedure (7),
COST [k + 1-Δ, kp] + COST [kp, k + 1 + q] + COST [k + 1 + q, Δ + 1]
And set it as P'_COST [p, q].

Procedure (9) For p and q satisfying Δ = 1 + p + q (0 ≦ p ≦ k−1, 0 ≦ q ≦ N−k−1), the minimum value MIN [Δ] of P′_COST [p, q], p give it the value of q, p_ _{MIN [Δ],} seek q_ _MIN [Δ].

  Procedure (10) For Δ = 1 to Δ = N−1, a minimum value MIN ′ of MIN [Δ] and a set of Δ, p_MIN [Δ], q_MIN [Δ] giving the same, Δ ′, p ′, q ′ Ask for.

  Step (11) Return to step (10) as s [k] ← h [p ′, q ′].

  Procedure (12) The calculation is terminated for the current k.

  Flowcharts representing such a procedure are shown in FIGS.

  Step 401) As an initial value, k ← 1.

  Step 402) As an initial value, i ← 1.

  Step 403) For j = 1, 2... DEG [j], ADJ_WEIGHT_IN [j, i] ← 1.

  Step 404) If i = N, go to Step 406, otherwise go to Step 405.

  Step 405) Increment i and return to Step 403.

  Step 406) Set LINK_COST [k] ← ∞.

  Step 407) Obtain h [k, m] and COST [k, m] by Dijkstra method.

  Step 408) If COST [k, k + 1] ≠ ∞, the process proceeds to Step 409, and if not, the process ends.

  Step 409) i ← 1.

  Step 410) Let Δ ← 1.

  Step 411) MIN '← ∞.

  Step 412) p ← 0 and q ← Δ−p−1.

  Step 413) For j = 1, 2... DEG [i], ADJ_WEIGHT_IN [j, i] ← ∞ is set.

  Step 414) If i = N, go to Step 416, otherwise go to Step 415.

  Step 415) Increment i and return to Step 413.

  Step 416) For j = 1, 2... DEG [k + p], ADJ_WEIGHT_IN [j, k + p] ← ADJ_WEIGHT_OUT [k + p, j].

  Step 417) For j = 1, 2... DEG [k + 1 + q], let ADJ_WEIGHT_IN [j, k + 1 + q] ← ADJ_WEIGHT_OUT [k + 1 + q, j].

  Step 418) Set MIN [Δ] ← ∞.

  Step 419) Find h [k-p, k + 1 + q] and COST [k-p, k + 1 + q].

  Step 420) COST [k + 1−Δ, kp] + COST [kp, k + 1 + q] + COST [k + 1 + q, Δ + 1] is obtained and this is calculated as P′_COST [p, q] And

  Step 421) It is determined whether MIN [Δ] ≧ P′_COST [p, q]. If yes, the procedure goes to Step 422, and if not, the procedure goes to Step 423.

  Step 422) MIN [Δ] ← P′_COST [p, q], p_min [Δ] ← p, q_min [Δ] ← q.

  Step 423) It is determined whether p = k−1. If so, the process proceeds to Step 425. Otherwise, the process proceeds to Step 424.

  Step 424) p ← p + 1, q ← q−1, and return to Step 413.

  Step 425) If MIN ′ ≧ MIN [Δ], the process proceeds to step 426, and if not, the process proceeds to step 427.

  Step 426) MIN '← MIN [Δ], p' ← p_min [Δ], q '← q_min [Δ].

  Step 427) If Δ = N−1, the process proceeds to Step 429; otherwise, the process proceeds to Step 428.

  Step 428) Δ ← Δ + 1 and return to Step 411.

  Step 429) s [k] ← h [p ′, q ′].

  Step 430) i ← 1.

  Step 431) For j = 1, 2... DEG [i], ADJ_WEIGHT_IN [j, i] ← 1.

  Step 432) If i = N, go to Step 434, otherwise go to Step 433.

  Step 433) Increment i and return to Step 431.

  Step 434) If k = N−1, the process is terminated; otherwise, the process proceeds to Step 435.

  Step 435) Increment k and return to Step 402.

  The above procedure will be described in detail.

  Procedure (1) The number of hops is calculated by giving 1 to the weight of all links and calculating the cost.

  Procedure (2) Similar to the second and third embodiments described above, if COST [k, k + 1] = − ∞, the path from NODE [k] to NODE [k + 1] is LINK [k] Indicates that there is only one. That is, there is no h [k, m] that does not pass LINK [k]. As in the case of the second embodiment described above, the example shown in FIG. 8 is applicable to this case.

  Step (3) If COST [k, k + 1] = ∞, this means that there is only one LINK [k] route from NODE [k] to NODE [k + 1]. That is, there is no h [k, m] that does not pass LINK [k]. Similar to the second embodiment, the example shown in FIG. 8 is applicable to this case.

  Procedure (4) Define Δ so that j−i = Δ, where NODE [i] is the start point of the route and NODE [j] is the end point.

  Procedure (5) For all Δs, find a substitute route that minimizes the number of hops.

  Procedures (6) to (9) are the same as those described in (6) to (9) of the third embodiment.

  Step (10) From the alternative routes having the same Δ, the route having the smallest number of hops is obtained for all Δs from those determined to minimize the number of hops.

  In the above description, the path given first is not necessarily the optimum path. However, even when the optimum path is given, the same path can be determined by the same procedure.

  Further, it is assumed that the optimum route obtained by the Dijkstra method used above does not pass the same road more than once and does not have a loop.

  In each of the above embodiments, the Dijkstra method is used as a method for calculating the detour route. However, the present invention is not limited to this example, and any other method can be used as long as it can obtain the shortest route of the weighted directed graph. It may be a method.

  Further, the operations of the flowcharts shown in FIG. 2, FIG. 6 to FIG. 7, FIG. 10 to FIG. 11, and FIG. It can be installed in a computer used as an apparatus for managing the communication network, executed by a control unit such as a CPU, or distributed via the network.

  Further, the constructed program is stored in a portable storage medium such as a hard disk, a flexible disk, or a CD-ROM connected to a node device on the communication network or a computer used as a device for managing the communication network. It can also be stored and installed on a computer when implementing the present invention.

  The present invention is not limited to the above-described embodiment, and various modifications and applications can be made within the scope of the claims.

  The present invention can be applied to a system that prepares a backup resource for a failure in a section between a working path passing through a node on the network and a node of the working path, and performs a failure recovery process according to the failure location.

It is a figure for demonstrating the principle of this invention. It is a flowchart of the operation | movement in the 1st Embodiment of this invention. This route is selected when it overlaps with P in the Ingress side node in the first embodiment of the present invention. This route is selected when it overlaps with P at the node on the egress side in the first embodiment of this invention. It is an example of path | route s [k] calculated | required in the 2nd Embodiment of this invention. It is a flowchart (the 1) of the operation | movement in the 2nd Embodiment of this invention. It is a flowchart (the 2) of the operation | movement in the 2nd Embodiment of this invention. It is an example of the network where the path | route which satisfy | fills the conditions in the 2nd Embodiment of this invention does not exist. This is a path Q obtained by resetting the path P in the second embodiment of the present invention. It is a flowchart (the 1) of the operation | movement in the 3rd Embodiment of this invention. It is a flowchart (the 2) of the operation | movement in the 3rd Embodiment of this invention. This is a network having a plurality of substitute routes having the same Δ in the third embodiment of the invention. It is a flowchart (the 1) of the operation | movement in the 4th Embodiment of this invention. It is a flowchart (the 2) of the operation | movement in the 4th Embodiment of this invention. It is a flowchart (the 3) of the operation | movement in the 4th Embodiment of this invention. It is an example of a network and a path. This is a path expression. This is the relationship between LINK [k] and route s [k].

Claims (8)

A spare resource for a failure in a section [m, m + 1] (1 ≦ m <k, m: integer) between the working path passing through the nodes 1 to k (k: positive number) and the node of the working path In the failure recovery path search method in a communication network performed by a node device on a communication network prepared for each section, and performing a failure recovery operation according to a failure location when a failure occurs, or a device controlling the communication network,
The node device calculation means comprises:
When calculating the backup path for failure recovery, the sum of the weights of all links existing in the communication network excluding the link of the calculation target current section for calculation of the calculation target current section [m, m + 1]. A detour route calculation process for calculating a detour route by giving a larger value;
If the calculation result of the detour route shares the other section with the working path, the spare path of the section including the calculation target section [m, m + 1] by removing the overlapping portion of the working path and the other section A preliminary route determination process and
A fault recovery route search method characterized by comprising:   The failure recovery route search method according to claim 1, wherein, in the backup route determination process, the detour route calculation process and the backup route determination process are performed again for a section including a calculation target section obtained by removing overlapping portions. In the detour route calculation process,
The failure recovery route search method in the communication network according to claim 1, wherein a method for obtaining the shortest route of the weighted directed graph is used.   The failure recovery route search method in a communication network according to claim 3, wherein a Dijkstra method is used as a method for obtaining the shortest route of the weighted directed graph. A spare resource for a failure in a section [m, m + 1] (1 ≦ m <k, m: integer) between the working path passing through the nodes 1 to k (k: positive number) and the node of the working path Prepared for each section, a node device on a communication network that performs a failure recovery operation according to a failure location when a failure occurs, or a failure recovery route search program that is executed by a device that controls the communication network,
An input step for inputting a value larger than the sum of the weights of all links existing in the communication network excluding the link of the calculation target working section for calculation of the calculation target working section [m, m + 1];
A calculation step for calculating a detour route using the input value as a backup route calculation for failure recovery,
When the calculation result of the detour route in the calculation step shares the other section with the working path, the section including the calculation target section [m, m + 1] by removing the overlapping portion of the working path and the other section A failure recovery route search program for causing a computer to execute a backup route determination step for outputting as a backup route.   6. The fault recovery route search program according to claim 5, wherein, in the backup route determination step, the detour route calculation step and the backup route determination step are performed again for a section including a calculation target section obtained by removing overlapping portions. In the detour route calculation step,
6. The failure recovery route search program according to claim 5, wherein a method for obtaining the shortest route of the weighted directed graph is used. In the detour route calculation step,
The failure recovery route search program according to claim 7, wherein the Dijkstra method is used as a method for obtaining the shortest route of the weighted directed graph.

Images