JPH07162415A - Distribution control type bypass route retrieval system - Google Patents

Abstract

PURPOSE:To retrieve a bypass route by not sending an arrival disable message to a CHOOSER node within an allowable remaining hop number so as to reduce occurrence of invalid messages and number of invalid processing nodes. CONSTITUTION:Upon the receipt of a bypass route retrieval message, a message transmission discrimination means 110 references a minimum hop number table 100 to discriminate whether or not the bypass route retrieval message arrives from a concerned node N to a CHOOSER node in a recognized remaining hop number based on information described in the bypass route retrieval message. In this case, when it is discriminated that the message is arrived in the CHOOSER node, a succeeding message is discriminated, and when the arrival to the CHOOSER node is disable, the message is not sent but the processing is finished.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a distributed control type detour route search system for searching a detour route which replaces all or a part of a fault path when a fault occurs in a communication network.

[0002]

2. Description of the Related Art Reference 1: "Examination of Fault Recovery Algorithm by Distributed Control", IEICE Tech.
Nakajo, Miyazaki, Ogura, Soejima; Fujitsu Laboratories, Ltd. Reference 2: "Examination of switching VP presetting type ATM network self-healing method", Technical Report CS91-90 Kawamura, Sato; NTT Transmission Systems Laboratories "Communication As the speed and capacity of networks increase, it is important to promptly deal with failures such as transmission line disconnection and transmission equipment failure. Since it takes time to directly physically repair the faulty part, as described in the above documents 1 and 2, the detour route is secured by using the free capacity of the transmission line of the communication network.
A method of recovering by switching the faulty path to a detour route is considered. As one method of this detour route search, a distributed control type detour route search method is considered.

Before describing the distributed control type alternative route search method, a communication network (here, a transmission network is handled) will be defined.

(A) Physical configuration of transmission network A plurality of transmission devices called nodes (or cross-connects) are distributed in the transmission network, and a transmission path called a link is provided between any two nodes. It is connected. The physical configuration of the transmission network is as described above.

(B) Logical structure of transmission network Within the transmission network, in order to transmit a call (channel) from one area (node) to another area (node), a logical grouping of calls (channels) A path that exists is set. This path is transmitted to the destination via some nodes. Each node constituting the path inputs the path from the connection link and outputs the path to the link to be output according to the path route information in the node. As described above, the connection is made in path units at each node,
A logical path is set up between two regions (nodes), and a call (channel) for which a connection request is made can be connected between regions through the path. The logical configuration of the transmission network is as described above.

(C) Outline of distributed control type detour route search method The distributed control type detour route search method means that when a failure such as a transmission line disconnection or a node failure occurs in such a transmission network, the entire transmission network is It is a method of obtaining a bypass route of a failure path by autonomously decentralized operation of each node in the network without going through a centralized management station that manages it. As the section of the detour route, both between the failed links and between the path end points can be considered.

An example of operation according to the conventional distributed control type detour route search method when setting a detour route between path termination points will be described below.

For example, when a transmission path failure occurs, either one of the nodes at both ends (termination points) of the failure path is SE.
The NDER node and the other CHOOSER node.
Here, the SENDER node is a node that is a transmission source of a message for determining a detour route (hereinafter, referred to as a detour route search message).
The node is a node that recognizes and confirms the detour route.

The SENDER node sends a detour route search message to all connection links satisfying a predetermined condition. Each node that has received the detour route search message similarly sends out the detour route search message to all the connection links that satisfy the predetermined condition. By repeating the propagation of the detour route search message between the nodes, the detour route search message output by the SENDER node finally arrives at the CHOOSER node. In the distributed control type detour route search method, by providing a condition that the free capacity of the output link is equal to or more than the failure path capacity as a message transmission condition of each node, one or more arriving detour route search messages of the CHOOSER node are set. It is possible to recognize the existence of a detour route (path) utilizing the free space in the transmission line from the route, and to determine the optimum detour route.

(D) Model for explaining the operation of the conventional distributed control type alternative route search method FIG. 2 is a diagram showing a transmission network model for explaining the conventional distributed control type alternative route search method. In FIG.
White circles indicate nodes, the numbers inside the white circles indicate node numbers, the thick solid lines connecting the nodes indicate links (transmission lines), and the arrows attached to each link indicate the message. Shows the transmission of.

The transmission network model shown in FIG. 2 is a model in which 16 nodes 1 to 16 are connected by links in a grid pattern, and a path A is connected between a node 5 and a node 7. It is assumed that the transmission route is node 5 → node 6 → node 7. In addition, in FIG. 2, in order to facilitate understanding, it is assumed that each link has a free capacity equal to or larger than the capacity of the path A between the node 5 and the node 7. In other words, regarding the free space condition of any link,
It can be used as a via link of the detour route of the path A.

(E) Operation by the conventional distributed control type detour route searching method The detour route searching operation when a failure occurs in the path A will be described below.

When the link between the node 6 and the node 7 is broken, a link failure (failure of the path A) is detected by the failure detection mechanism of the network, and both end point nodes of the path A that have used the failed link. 5 and node 7 are notified that the path A has failed. Then, when the termination point node 5 and the node 7 receive the fault occurrence notification from the fault detection mechanism, the termination point node 5 and the node 7 start the search operation of the detour route of the path A.

The operation thereafter is the operation of the distributed control type detour route search system. First, node 5 is SENDER
Node and node 7 become CHOOSER node, SE
The node 5 that has become the NDER node sends a detour route search message to all the connection links that have free capacity equivalent to the capacity of the fault path A, while the node 7 that has become the CHOOSER node is sent from the SENDER node 5. Wait for arrival of the sent out route search message.

FIG. 3 shows an example of the structure of a conventional detour route search message. The detour route search message is composed of the following six types of contents.

(1) Fault path identifier that identifies the fault path (2)) SENDER node / CHOOSER node number that identifies the SENDER node and CHOOSER node (3) Fault path capacity (4) History of the node through which the message concerned Node number via message for clarifying (5) Number of hops that is the number of links through which the message has passed (value updated each time the node passes) (6) Upper limit of the number of links through which messages can be passed (detour Hop limit value, which is the upper limit value of the number of rings that make up the route) Here, the message contents (1) to (3) and (6) are constants that are uniquely determined by the failure path and pass through the node. However, the contents do not change. In the case of the example in FIG. 2, the identifier of the path A is described in the message content (1), and the identification numbers of the node 5 and the node 7 are SEN respectively.
The DER node number and the CHOOSER node number are described in the message content (2), the capacity of the fault path A is described in the message content (3), and the predetermined hop limit value (eg, 6) is described in the message content (6). It

However, the message contents (4) and (5) are
It is added / updated every time it goes through a node. For example, in the message content (4) in the message sent by the SENDER node 5, the transit node number SE
The NDER node number 5 is described, and 0 is described as the initial value of the hop number in the message content (5). The number of hops described in the message content (5) is
It is compared with the hop limit value described in the message contents (6).

Next, the operation until the detour route is obtained by the detour route search message sent by the SENDER node 5 will be described.

In the node 1, node 6, and node 9 that have received the message from the SENDER node 5, first, the number of hops of the message content (5) is increased by 1 to 1.
Then, in these node 1, node 6, and node 9,
It is considered that the message can be sent only if the following message sending conditions are satisfied or only for the link, and the own node number is additionally described in the section of the transit node of the message content (4) and the message is sent to the corresponding connection link.

~ Message sending condition ~ (i) The number of hops described in the message content (5) (the value after adding 1 at the own node) is less than the hop limit value. (Ii) The destination to send the message. Node is not the node that passed through before (the connection destination node is not described in the message content (4)) (iii) The free capacity of the link from which the local node sends the message is the failure path A (Iv) Own node is not a CHOOSER node (C
In the case of a HOOSER node, no message is sent.) In the message processing of each node, there are multiple links to which the bypass route search message should be sent (that is, the links connected to the own node that meet the message sending conditions). If there is one, the detour route search message is copied and sent. Upon receiving the detour route search message, each node in the network performs similar message processing, and as a result, the detour route search message is propagated in all directions.

The detour route search message basically propagates in the network until the number of hops described in the message reaches the hop limit value. In this way, one or more detour route search messages finally arrive at the CHOOSER node 7. In CHOOSER node 7,
Message content of the arrived detour route search message
The detour route candidate can be known from the transit node information in (4).

FIG. 4 is a table showing all detour route candidates obtained when the conventional distributed control type detour route search method is executed with a hop limit value of 6 in the transmission network model shown in FIG.

The CHOOSER node 7 selects an optimum detour route from the all detour route candidates. There are various possible selection methods, but as an example, the route with the smallest number of hops can be selected. This Figure 4
Among the detour route candidates shown in (1), the minimum hop number is 4, and the detour route candidates 1), 4), 6), and 9) are applicable. One of these four detour route candidates will be selected as the final detour route.

[0024]

However, in the conventional distributed control type alternative route search method, the alternative route search message basically propagates in the transmission network until the number of hops reaches the hop limit value. , Many messages (invalid messages) other than the detour route search message involved in the finally obtained detour route are generated, and the nodes involved in message processing other than the nodes constituting the finally obtained detour route ( Invalid processing node)
Is occurring a lot. CHO in invalid message
If it arrives at the OSER node 7 and is discarded, it becomes a candidate for a detour route, so the propagation is significant.
It is a big problem that there are many invalid messages that do not reach the CHOOSER node 7. For example, node 5
→ node 1 → node 2 → node 6 → node 10 → node 14 → invalid message discarded via the route of node 15, node 5 → node 9 → node 10 → node 14 →
The invalid message discarded via the route of node 15 → node 16 → node 12 corresponds to the latter.

Therefore, in the conventional distributed control type detour route search method, the processing amount of invalid messages in each node is large, and the number of nodes to be subjected to invalidation processing is large.

By the way, the network is properly maintained and maintained at each node.
A central processing function (processor) for operation is installed, and this processor monitors network quality and establishes new paths.
Processes such as cancellation and route change are always performed. However, when the failure occurs, the detour route search process begins,
When the detour route search message is received, the processor is used for the detour route search process, so that the capacity of the maintenance / operation process, which is the original process of the processor, decreases. Therefore, the large amount of invalidation processing in each node and the large number of invalidation processing nodes as described above lead to a reduction in the maintenance / operation capability of the network.

In addition, when multiple failures occur, the message processing amount in the node further increases in the overlapping message coverage area of each failure, which may reduce the message propagation speed and the recovery time. To be

The present invention has been made in consideration of the above points, and searches for a detour route in the event of a communication network failure,
It can be executed with the minimum number of invalid messages and the number of invalid processing nodes.
This is an attempt to provide a distributed control type detour route search method.

[0029]

In order to solve such a problem, according to the present invention, when a failure occurs in a communication network, one of the normal nodes on the failure path becomes a SENDER node, and a predetermined condition for connection is established. Each node that sends the detour route search message to all the links that satisfy it and receives the detour route search message similarly sends the detour route search message to all the connection links that satisfy the predetermined condition. The alternate route search message is repeatedly propagated between the nodes to cause the alternate route search message to reach the CHOOSER node which is one of the normal nodes on the failure path, and the CHOOSER node has arrived the one or more alternate routes. The route of the search message recognizes the existence of a detour route that uses the free space in the transmission line, and It has been made to confirm the route,
The distributed control type detour route search method in which the limit value of the hop count of the detour route search message is specified is as follows.

That is, (1) each node is provided with a minimum hop count table that describes the minimum hop count at which the detour route search message sent by the own node can reach other nodes for all other nodes.

(2) CHOOSER that each node can recognize by the received detour route search message.
The number of remaining hops allowed up to the node and the CHOOSE described in the above minimum hop count table
Based on the minimum number of hops to the R node, when the own node sends out the detour route search message, it is determined whether or not the detour route search message can reach the CHOOSER node within the allowable remaining hop number, An affirmative result of this determination is set as one sending condition of the detour route search message.

[0032]

In the distributed control type detour route search method of the present invention, CHOOSE is used when the number of remaining hops is allowed.
The detour route search message that is found to be unreachable to the R node is discarded by the node that can be found to reduce the number of invalid messages and invalid processing nodes compared to the conventional case.

The number of remaining hops is set to CH.
In order to determine whether or not the OOSER node can be reached, the minimum hop number that describes the minimum hop count at which each node can reach the other node by the bypass route search message sent by the own node. There is a table.

[0034]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of a distributed control type detour route search system according to the present invention will be described in detail below with reference to the drawings.

(A) Functional configuration of each node FIG. 1 shows a functional configuration of each node in the communication network, which is necessary to realize the distributed control type detour route search method of this embodiment. is there. That is, by mounting such a function on each node, the distributed control type detour route search method of this embodiment is realized.

As shown in FIG. 1, each node N in the communication network
Is a minimum hop count table 100 and a message sending determination means 110 for searching a detour route in the event of a communication network failure.
And message sending means 120.

The minimum hop count table 100 is basically created at the time of network construction, and is updated according to the addition or deletion of nodes constituting the network. . Minimum hop count table 10
0 describes the minimum number of hops required for the detour route search message sent from the own node N to reach a node in the network for all other nodes in the network.

A failure (including both a physical failure and a logical failure that is not a physical failure such as a path failure) occurs in the communication network, and the node N sends a detour route search message that has occurred. When received, the message transmission determination means 110 inputs the CHOOSER node number of the message into the minimum hop count table 100, and the minimum hop count table 100 is the minimum required to propagate the message from the own node N to the CHOOSER node. Output the minimum number of hops. This minimum hop count table 100
Are actually formed as memories in the node N.

When the own node N receives the detour route search message generated by the occurrence of a failure in the communication network, the message sending determination means 110 receives the own node N.
It is to determine whether or not to send the detour route search message to each link connected to. There are several items (conditions) for message transmission determination.
However, as a necessary transmission determination condition, it is necessary to determine whether or not the detour route search message can arrive at the CHOOSER node within the remaining number of hops recognized from the information described in the detour route search message. The condition for making a determination by referring to the table 100 is provided.

The message sending means 120 carries out a predetermined message sending process for the connection link which is judged by the message sending judging means 110 that the message can be sent.

In this embodiment, the message sending determination means 110 and the message sending means 120 are, as a program or a dedicated hardware (not necessarily a processor) for realizing a predetermined operation by a processor mounted on each node. Equipped on each node.

(B) Outline of Message Processing in Each Node FIG. 5 shows the message processing executed in each node N when the detour route search message sent due to the occurrence of a failure is received. .

When the detour route search message is received (step 200), the message transmission determination means 110 makes the number of hops within the remaining hop number recognized from the information described in the detour route search message from the own node N to the CHOOSER node. Whether or not the detour route search message can arrive at the minimum hop count table 1
It is determined with reference to 00 (step 201). More specifically, the minimum number of hops fetched from the minimum number of hops table 100 by inputting the CHOOSER node number and the number of remaining hops recognized from the information described in the detour route search message arriving at the own node N The size is compared to determine.

At this time, if it is determined that the CHOOSER node can be reached, the process moves to the next message sending determination step. If the CHOOSER node cannot be reached, the process is terminated without sending the message.

When it is determined that the CHOOSER node can be reached, in the next determination step, the same message transmission as in the conventional method such as whether or not there is sufficient free space for forming a detour route for each connection link is sent. Is executed (step 202), and if it can be finally sent, a predetermined message sending process is executed (step 20).
3), the detour route search message is sent to the corresponding connection link, and the series of processing is terminated. If the message cannot be sent, the received detour route search message is discarded without being sent, and the process ends.

The contents (structure) of the detour route search message in this embodiment may be the same as the conventional one.

(C) Reason for providing a judgment item considering the number of remaining hops The number of hops within the remaining number of hops recognized based on the received detour route search message, and the CH from the own node N
The reason why the detour route search message can arrive at the OOSER node is provided as a judgment item for determining whether or not to send the detour route search message.

As one of the judgment items, consider a case where the judgment item is not provided. That is, it is assumed that the determination item (condition) is based on the conventional distributed control type alternative route search method.

In this case, it is assumed that the detour route search message arrives at a certain node and the number of hops becomes H, for example. The hop limit value of this message is HL
Further, it is possible to arrive from this node to the CHOOSER node in a minimum of α hops.

Here, if the number of remaining hops (HL-H) of the detour route search message is smaller than the minimum number of hops (α) from its own node to the CHOOSER node, even if all other message sending conditions are satisfied. , This bypass route search message reaches the hop limit value HL before reaching the CHOOSER node, and this message is discarded before reaching the CHOOSER node.

In other words, in the conventional distributed control type detour route search method, the node also sends a message (invalid message) which is apparently useless in terms of topology, and when the entire communication network is viewed, the invalid message becomes very large. It was getting many.

On the other hand, as described above, with the number of hops within the remaining number of hops directly or indirectly specified by the received detour route search message, the detour route from the own node N to the CHOOSER node. By determining whether the search message can arrive, it is possible to discard the unreachable detour route search message in the node and prevent the invalid message from being propagated in a wide range. For this reason, in this embodiment, the number of hops within the remaining number of hops specified in the received detour route search message is within the range from the own node N to C.
Whether or not the detour route search message can arrive at the HOOSER node is provided as one determination item for sending the message.

(D) Operation by the distributed control type detour route search method of the embodiment Next, the detour route searching operation by the distributed control type detour route search method of this embodiment will be described in detail using a specific example of a communication network. To do.

Also in the description of this embodiment, the communication network configuration (model) is assumed to have the configuration of FIG. 2 used in the operation by the conventional distributed control type detour route search method,
It is assumed that the capacity condition is satisfied for each ring.

For example, when the link between the node 6 and the node 7 is broken and a failure occurs in the path A, the failure detection mechanism of the network detects the link failure (that is, the failure of the path A) and uses the failed link. The termination point node 5 and node 7 of the path A that was being used are notified that a failure has occurred in that path. Then, upon receiving the failure occurrence notification from the failure detection mechanism, the node 5 and the node 7 at the termination point start the detour route search of the path A.

The subsequent operation is the operation of the distributed control type detour route search system. First, node 5 is SENDER
Node and node 7 become CHOOSER node, SE
The node 5 that has become the NDER node sends a detour route search message to all the connection links that have free capacity equivalent to the capacity of the fault path A, while the node 7 that has become the CHOOSER node is sent from the SENDER node 5. Wait for arrival of the sent out route search message.

Also in this embodiment, the content (structure) of the detour route search message is as shown in FIG. 3 described above. That is, (1) fault path identifier, (2) SENDE
R node / CHOOSER node number, (3) fault path capacity, (4) message passing node number, (5) number of hops,
(6) It is composed of hop limit values.

In the description below, the hop limit value is 6. That is, the detour route must be composed of 6 links or less.

The detour route search message sent by the SENDER node 5 is the node 1, node 6 and node 9.
To reach. In each of the node 1, the node 6 and the node 9, the message sending determination means 110 first increments the hop count of the message content (5) by 1 to set it to 1. Then, the message sending determination means 110 of each of the nodes 1, 6, and 9 considers that the message can be sent only to the links satisfying the following message sending conditions,
After the own node number is additionally described in the section of the transit node of the message content (4), the message sending means 120 is activated to send the detour route search message to the corresponding connection link.

-Message sending conditions- (i) The number of remaining hops (HL-H) is equal to or larger than the minimum required number of hops α for reaching the CHOOSER node (where HL is the message content of the received message).
The hop limit value described in (6), H is the value obtained by adding 1 to the number of hops described in the message content (5) of the received message, and α is the minimum hop number table 10
The minimum number of hops to reach the CHOOSER node 7 described in 0) (ii) The node to which the message is to be sent is not the node that has passed through previously (the connection destination node is described in the message content (4)). (Iii) The free capacity of the link from which the own node sends a message is equal to or larger than the capacity of the failure path A. (iv) The own node is not a CHOOSER node (C
In the case of the HOOSER node, message transmission is not performed.) Here, message transmission conditions (ii) to (iv) are the same as those in the conventional system. However, the message sending condition (i) is
The message sending condition (i) of the conventional method is replaced by the message sending condition adopted in this embodiment. This message sending condition (i) is provided for the reason described above, and is determined in preference to other message sending conditions (ii) to (iv) as shown in FIG. 5, for example.

In such message processing, the link (ie,
When there are a plurality of links connected to the own node that satisfy the message sending conditions), the bypass route search message is copied and sent. Upon receiving the detour route search message, each node in the network performs the same message processing, and as a result, the detour route search message is propagated in all directions while partially discarding it.

By the propagation in all directions, finally, one or more detour route search messages arrive at the CHOOSER node 7.

In the CHOOSER node 7, the detour route candidate can be known from the transit node information of the message content (4) of the arrived detour route search message, and among the detour route candidates with the minimum hop number of the message content (5). Select one from the above to determine the detour route.

When the hop limit value is set to 6, the detour route candidate shown in FIG. 4 is obtained as in the conventional method.

The detour route candidate similar to that of the conventional method is obtained by checking the hop limit value itself which has been conventionally performed in the message sending condition, and by checking the remaining hop number using the minimum hop number table 100 in this embodiment. This is because this operation only reduces invalid messages and does not discard the detour route search message that passes through the route that may be a detour route. In other words, only the redundant operation in the detour route search is suppressed, and the detour route search capability is not deteriorated.

Therefore, the process after the detour route candidate is obtained in the CHOOSER node 7 is exactly the same as the conventional method.

(E) Example of Reduction of Invalid Messages Next, when the method of this embodiment is applied to the transmission network shown in FIG. 2, the number of invalid messages is smaller than that of the conventional method. This will be described with an example.

Here, node 5 → node 1 → node 2 →
It is assumed that the detour route search message arrives at the node 14 via the node 6 → node 10. In the detour route search message immediately after the arrival, the number of hops: 4, the hop limit value: 6, the transit node: (5, 1, 2, 6, 10) is described.

In the node 14 according to the method of the above embodiment, the following message processing is executed.

(A) First, the hop count is increased by 1 to 5
And (b) Next, the updated number of hops (= 5) is subtracted from the described hop limit value (= 6) to calculate the number of remaining hops (= 1) that can be continuously propagated from the node 14. To do. (c) Minimum hop count table 100
The minimum hop count (= 3) required for the detour route search message output from the node 14 to reach the CHOOSER node 7 is obtained by referring to. (d) The remaining hop count (= 1) is compared with the minimum hop count (= 3) minimum required to reach the CHOOSER node 7, and the detour route search message is CHO with the remaining hop count.
It is determined whether or not the OSER node 7 can be reached. (e) In this case, since the determination result that it is unreachable is obtained, the bypass route search message is discarded without being transmitted.

On the other hand, in the conventional method, even if the number of hops is increased by 1, the value is 5, which is smaller than the hop limit value 6. Therefore, if the capacity condition is satisfied, the node 14 can be changed to another node. A detour route search message is sent to the links connected to 13 and the node 15. In each of these nodes 13 and 15, the value obtained by increasing the hop count by 1 becomes 6, which is equal to the hop limit value 6, and since the own node is not the CHOOSER node 7, the received detour route search message is invalidated. Discard.

As described above, according to the conventional method, the node 14
While the detour route search message that has reached the node is propagated to the nodes 13 and 15 and then discarded at these nodes, in the method of this embodiment, the node 14 and the node 14 are not propagated. Be discarded at. Therefore, in the conventional method, the node 13 and the node 1 are
The number of invalid messages propagated to 5 is smaller in this embodiment.

The same can be said for the other routes, and the method of this embodiment can reduce the number of invalid messages as compared with the conventional method.

(F) Reduction of the number of invalidation processing nodes If the number of invalidation messages can be reduced, it is naturally possible to reduce the number of invalidation processing nodes used for processing invalidation messages.

The fact that the number of invalidation processing nodes can be reduced will be described below from the viewpoint of the message spread range.

FIG. 6 shows the configuration of a fictitious communication network used for the above description. In this communication network, a plurality of nodes are arranged in a grid pattern over a wide area, and each node is connected to adjacent nodes in the same row and the same column by a link. Also, in order to facilitate understanding, both nodes of the faulty link are
The ER node S and the CHOOSER node C are assumed.
Further, the hop limit value is represented by HL (HL is 3 or more as is clear from FIG. 6) and will be described.

In the conventional system, the SENDER node S
The node to which the detour route search message sent from is given is a node that can receive a message in which the number of hops not passing through the faulty link is equal to or less than the value HL. Therefore, in the area AR0 where the detour route search message is spread in the conventional method, as shown in FIG.
It is a substantially rhombic region centered on the NDER node S. The number of nodes M in this area AR0 (SENDER nodes are not counted) can be expressed by the following equation (1) by using the summation formula of the odd columns (1, 3, ...).

M = 2HL ² + 2HL−2 (1) On the other hand, in the embodiment system, the node to which the detour route search message sent from the SENDER node S may be given is a hop limit value without going through the failed link. If the number of hops is within HL, the detour route search message is C
A node on a route that can reach the HOOSER node C and a node that is one hop farther from the SENDER node S than the node on the route that the detour route search message can reach the CHOOSER node C with the hop limit value HL without passing through the faulty link. Is. Therefore, the area AR to which the detour route search message is spread in the embodiment system
1 is the SENDER node S and C as shown in FIG.
The region is a substantially elliptical shape (also can be regarded as a rhombus shape) centered on the center between the HOOSER nodes C. The number N of nodes in this area AR1 (not counting the SENDER node) is an odd number column (3, 5, ... Or 1, 3, 3).
By using the summation formula of…)
It can be expressed by equation (2) or equation (3).

N = (HL ² + 6HL + 3) / 2 (when HL is an odd number) (2) N = (HL ² + 4HL-2) / 2-i (when HL is an even number) (i when HL is 4) = 1, i = 0 when HL is an even number of 6 or more) (3) From the above equation, the difference MN between the numbers of nodes in the message spread range of the conventional method and the example method is calculated to be MN = {HL (3HL-2) -7} / 2> 0 (when H is an odd number: HL ≧ 3) (4) MN = (3HL ² −2) / 2 + i> 0 (when HL is 4) When i = 1 and HL is an even number of 6 or more, i = 0) (5) can be obtained.

That is, considering that the hop limit value is 3 or more, it can be seen that the number N of nodes in the message spreading area in the embodiment system is always smaller and the message spreading range is suppressed. That is, the number of invalid processing nodes can be reduced. Moreover, the larger the hop limit value HL, the greater the effect.

FIG. 6 shows an example in which the hop limit value is 5, and the message spread range AR0 of the conventional system is 58 nodes, whereas the message spread range AR of the embodiment system is.
In the case of 1, the number has been reduced to 29 nodes, which is half.

(G) Effects of the Embodiments As described above, according to the above embodiments, the number of invalid messages and the number of invalid processing nodes can be significantly reduced as compared with the conventional method.

As a result, in each node, it is possible to prevent the capability of the maintenance / operation function of the network, which is the original function of the internal processor, from deteriorating due to message processing when a failure occurs.

Even if multiple failures occur, it is possible to reduce invalid messages in the overlapping message coverage areas of each failure, suppress a decrease in message propagation speed, and improve recovery time.

(H) Other Embodiments The present invention is not limited to the above-mentioned embodiments, but various modified embodiments are acceptable, and some examples are as follows.

As the contents of the detour route search message,
Instead of the hop count and the hop limit value, the remaining hop count may be described.

The minimum number of hops table 100 describes the minimum number of hops required for the detour route search message sent from the own node N to reach other nodes in the network for all adjacent nodes. It is a thing. For example, regarding the node 10 in FIG. 2, the minimum number of hops to the node 12 is 2 for the link to the node 11, 4 for the link to the node 6, and 6 for the link to the node 9. , May be described as 4 via a link to the node 14. In this way, it is possible to determine whether or not the CHOOSER node can be reached by the number of remaining hops for each link, and it is possible to further reduce the number of invalid messages and invalid processing nodes.

The message sending determination condition is not limited to that of the above embodiment. For example, when sending a message to the same link for the second time or later, the hop count of the subsequent message is the hop count of the previous message. The condition may be less. The present invention only needs to have at least a determination condition based on the number of remaining hops.

[0089]

As described above, according to the present invention, (1)
Each node is provided with a minimum hop count table that describes the minimum number of hops that the detour route search message sent by the own node can reach other nodes, and (2) each node receives the detour received by the node. Based on the number of remaining hops allowed to reach the CHOOSER node that can be recognized by the route search message and the minimum number of hops to the CHOOSER node described in the minimum hop number table, the own node detours the route search message. Is sent, the detour route search message is sent within CHOOS within the remaining number of hops allowed.
Since it is determined whether the ER node can be reached, and the positive result of this determination is used as one of the conditions for sending the detour route search message, the number of invalid messages and the number of invalid processing nodes are significantly reduced compared to the conventional method. be able to.

[Brief description of drawings]

FIG. 1 is a block diagram showing a functional configuration of each node according to an embodiment.

FIG. 2 is a diagram showing a communication network model for explaining operations of a conventional system and an example system.

FIG. 3 is a diagram showing a configuration (contents) of a detour route search message in a conventional system and an example system.

4 is a table showing detour route candidates in the communication network model of FIG.

FIG. 5 is a flowchart showing processing when a detour route search message of each node of the embodiment is received.

FIG. 6 is an explanatory diagram of the effect of reducing the number of invalidation processing nodes according to the embodiment.

[Explanation of symbols]

N ... Node, 100 ... Minimum hop count table, 110 ...
Message sending determination means, 120 ... Message sending means.

Claims (1)

[Claims] 1. When a failure occurs in a communication network, one of the normal nodes on the failure path becomes a SENDER node, and a detour route search message is sent to all the links that satisfy a predetermined condition to connect to the detour path. Each node receiving the route search message similarly sends out the detour route search message to all the connection links satisfying the predetermined condition, and repeatedly executes such detour route search message between the nodes, The detour route search message is sent to the CHOO which is one of the normal nodes on the failure path.
When the CHOOSER node arrives at the SER node, the CHOOSER node recognizes the existence of a detour route using the free capacity in the transmission line from the route of one or more detour route search messages that have arrived, and determines the optimum detour route. In the distributed control type detour route search method in which the limit value of the number of hops of the detour route search message is specified, (1) the minimum hop at which the detour route search message sent by the own node can reach other nodes. The minimum hop number table describing all the other nodes is provided, and (2) the number of remaining hops allowed by each node to reach the CHOOSER node that can be recognized by the received detour route search message, and the above Minimum hop count to the CHOOSER node described in the minimum hop count table Based on the above, when the self-node sends the detour route search message, it determines whether the detour route search message can reach the CHOOSER node within the allowable number of remaining hops, and the affirmative result of this determination is used as the detour route. A distributed control type detour route search method characterized in that one sending condition of a search message is set.