JP5321908B2 - Communication network, network node, communication path control method, and communication path control program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide a communication network which suppresses computational complexity for computing an alternative path table to be held in preparation for upon failure, and a memory size for storage while being able to switch a communication path fast. <P>SOLUTION: Each of network nodes includes: a plurality of interfaces; a principal path table recording path information; a routing process part for transferring a packet based on the principal path table; an alternative path table storing part for storing the alternative path table recording alternative path information updating the path information of the principal path table upon failure of network resources; an alternative path table determining part for deciding whether or not the alternative path table corresponding to the network resource concerned is produced when the failure occurs in a specific network resource; an alternative path table computing part for computing the alternative path information; and a path table updating part for updating the principal path table by use of the alternative path table corresponding to the network resource in which the failure has occurred. <P>COPYRIGHT: (C)2011,JPO&amp;INPIT

Description

  The present invention relates to a technique for performing path switching at high speed in a communication network that dynamically performs path control.

  There is an urgent need to improve the stability of communication networks. As communication network technologies represented by the Internet become widespread, the impact of communication network failures on society is increasing.

  The communication network includes network nodes (hereinafter referred to as nodes) that transfer data and links that connect the nodes. Usually, a communication network is designed to improve the reliability of the network by providing a redundant configuration of nodes and links that are network resources constituting the communication network. In a communication network that dynamically performs path control, a path control protocol that controls optimal path information operates at each node. In a network that performs such dynamic route control, each node exchanges route information with other nodes constituting the communication network, and autonomously obtains optimum route information based on the obtained route information. Form. For example, when a failure occurs in a link connected to the own node or a node connected via the link, the node that detects the failure notifies the other nodes of the failure. The node notified of the failure performs route calculation in a state where the failed node or the link is removed, and determines new route information. In this way, a communication network that performs dynamic route control can continue communication even if a failure occurs in the communication network by autonomously forming a data transfer route using other nodes and links. It is possible.

  OSPF (Open Shortest Path First) is known as one of path control protocols for performing dynamic path control (Non-patent Document 1). OSPF is a typical link state algorithm standardized by the Internet Engineering Task Force (IETF). In a communication network in which OSPF operates, each node exchanges network topology information with each other. This topology information indicates a connection relationship between nodes and links in the communication network, and each node calculates route information based on the topology information. Each node can determine the optimum next transfer destination for the destination of the received packet based on the path information calculated based on the topology information.

  When a failure occurs in a node or link in the communication network, communication is restored in the following phase. First, a failure detection phase in which a failure node or a node adjacent to the link detects the failure. Next, a notification phase in which the detected failure is notified to other nodes in the communication network. Furthermore, a route calculation phase that recalculates transfer routes based on the topology after the failure. A route table update phase in which each node updates the route calculation result to the route table. The above four phases. In order to stabilize the communication network, it is preferable that the time from detection of a failure to the update of the routing table of each node is short. However, if the communication network becomes large, it takes a long time to restore the communication because the above-described route calculation phase takes time. Therefore, in order to shorten the time from failure occurrence to communication recovery, each node calculates the route table used in the event of a failure in advance and replaces it in case a link or node in the communication network fails. Techniques to keep as a route table are being studied as follows.

  Patent Document 1 discloses a high-speed path switching method that performs loop determination of an alternative path and uses only a path that does not become a loop. A router device that implements the high-speed route switching method of Patent Document 1 includes at least a network interface, a packet transfer unit, a main route calculation unit, an alternative route table calculation unit, and a switching unit, and further includes a loop route determination unit. Prepare. The network interface is connected to other routers. The packet transfer unit performs routing processing for packets received via the network interface based on route information stored in advance in the main route table. The main route calculation unit calculates route information stored in the main route table. The alternative route table calculation unit calculates an alternative route to be used when a failure of a link connected to the network interface or an adjacent router device is detected, and stores it in the alternative route table. When a failure of a link connected to the network interface or an adjacent router device is detected, a replacement process is performed for the route information stored in the alternative route table. The loop route determination unit determines whether the alternative route becomes a loop when the alternative route information is stored in the alternative route table by the alternative route table calculation unit, and substitutes the alternative route determined not to be a loop. Store in the routing table.

  According to the high-speed path switching method disclosed in Patent Document 1, a path that becomes a loop can be excluded from switching targets when performing high-speed path switching at the time of a link failure, and a loop of a transfer packet can be prevented from occurring. High-speed path switching can be realized while reducing the load.

  However, in such a fast switching method, each node will prepare in advance an alternative route table corresponding to all nodes and links where there is a possibility of failure, and the amount of calculation for calculating the alternative route table, And it was not realistic from the viewpoint of the capacity of the storage memory for holding the alternative path table.

JP 2006-279482 A

“OSPF Version2”, J.Moy, RFC2328, Internet Engineering Task Force, April 1998

   An object of the present invention is to provide a communication network capable of switching communication paths at high speed while suppressing the amount of calculation for calculating an alternative path table held in preparation for a failure and the memory size for storing. Is to provide.

  The communication network of the present invention is a communication network including a plurality of network nodes, each of the plurality of network nodes including a plurality of interfaces, a main route table in which route information in the communication network is recorded, and a main route table. A routing processing unit that forwards packets input from a plurality of interfaces based on the route information recorded in the main route table when the network resource is faulty and provided corresponding to the network resource that constitutes the communication network. An alternative route table storage unit that stores an alternative route table in which alternative route information of route information to be updated is recorded, the network resource includes a plurality of network nodes, and a link connecting the plurality of network nodes, and a network Selection to select from among resources An alternative route that determines whether or not to create an alternative route table corresponding to the selected network resource based on whether or not the route information in the main route table needs to be updated when a failure occurs in the network resource A table determination unit, an alternative route table calculation unit that calculates alternative route information to be recorded in the selected alternative route table corresponding to the selected network resource determined to create an alternative route table, and a failure occurred when a failure was detected A route table update unit that updates the route information of the main route table using the alternative route information recorded in the alternative route table corresponding to the network resource.

  The network node of the present invention constitutes the communication network described above.

  The communication route control method of the present invention includes a step of recording route information in a communication network in a communication network having a plurality of network nodes, and a step of transferring packets input from a plurality of interfaces based on a main route table. An alternative route table that is provided corresponding to the network resources constituting the communication network and records alternative route information of the route information to be updated among the route information recorded in the main route table when the network resource fails And the network resource includes a plurality of network nodes and links connecting the plurality of network nodes, and when a failure occurs in the selected network resource to select the network resource, the routing information of the main routing table Whether update is required And determining whether or not to create an alternative route table corresponding to the selected network resource, and an alternative route to be recorded in the selected alternative route table corresponding to the network resource determined to create the alternative route table A step of calculating information, and a step of updating the route information of the main route table using the alternative route information recorded in the alternative route table corresponding to the network resource in which the failure occurs when a failure is detected.

  The computer program of the present invention causes a computer to execute the communication path control method described above.

  According to the present invention, there is provided a communication network capable of switching communication paths at high speed while suppressing the amount of calculation for calculating an alternative path table held in preparation for a failure and the memory size for storage. Can be provided.

It is a figure which shows the structure of the node 1 in 1st Embodiment. It is a figure which shows an example of the main route table 122 in 1st Embodiment. It is a figure which shows an example of the alternative path | route tables 1311-131n in 1st Embodiment. The operation | movement flow which produces the alternative routing table in 1st Embodiment is shown. It is an operation | movement flow which extracts the link which should produce the alternative path | route tables 1311-131n in 1st Embodiment. It is a figure which shows an example of the shortest path tree which the main route calculation part 112 in 1st Embodiment produced | generated. It is a figure which shows the path | route 62 which the alternative path | route table determination part 113 in 1st Embodiment extracted from the shortest path tree. It is an operation | movement flow which determines whether the update of the route information of the main route table 122 is required at the time of the failure of the link ek in 1st Embodiment. It is a figure which shows the structure of the node 1 in 2nd Embodiment. It is a figure which shows the payload of the preparation instruction message in 2nd Embodiment. It is a figure which shows the structure of the payload of "Network LSA" in the conventional OSPF. It is an operation | movement flow which produces the alternative routing table in 2nd Embodiment. It is an operation | movement flow which specifies the calculation designation | designated node in 2nd Embodiment. The operation | movement flow at the time of receiving the creation instruction | indication message from the other node in 2nd Embodiment is shown.

  A communication network according to an embodiment of the present invention will be described below with reference to the accompanying drawings.

(First embodiment)
First, the communication network in the first embodiment of the present invention will be described.

  In the communication network of the present embodiment, each network node (hereinafter referred to as a node) constituting the communication network has a failure in each link in preparation for a failure of a link connecting each node existing in the communication network. An alternative route table to be used for each link is created in advance corresponding to each link. When a failure occurs, each node updates the main route table that is normally used by using an alternative route table corresponding to the link in which the failure has occurred. When creating an alternative route table, each node determines whether or not the route information recorded in the main route table needs to be updated when it is assumed that a failure has occurred in the link. Each node creates an alternative route table corresponding to the link only when it is determined in this determination that the main route table needs to be updated. Thus, since each node creates only the alternative route table determined to be necessary, it is possible to reduce the amount of calculation for calculating the alternative route table and the amount of memory for storing the alternative route table.

[Description of configuration]
First, the configuration of the nodes constituting the communication network in the present embodiment will be described. FIG. 1 is a diagram illustrating a configuration of the node 1 in the present embodiment. The node 1 of this embodiment includes a route control unit 11, a packet transfer unit 12, an alternative route table management unit 13, and network interfaces (hereinafter referred to as IF) 21 to 2n.

  The communication network of this embodiment includes a plurality of nodes 1 as shown in FIG. 1, and each node 1 is connected to other nodes by links 31 to 3n connected to IFs 21 to 2n to form a communication network. To do.

  First, the packet transfer unit 12 will be described. The packet transfer unit 12 includes a routing processing unit 121 and a main route table 122.

  First, the main route table 122 is a data table in which route information is recorded. FIG. 2A is a diagram illustrating an example of the main route table 122 in the present embodiment. Referring to FIG. 2A, the main route table 122 records a destination 41, a mask length 42, a next transfer destination 43, and an interface 44 in association with each other. The destination 41 is a network address to be associated with the destination IP (Internet Protocol) address recorded in the header of the packet received by the node 1. The mask length 42 is a subnet mask in the network address of the destination 41. The next transfer destination 43 is the IP address of the node 1 that is the transfer destination of the received packet corresponding to the network address of the destination 41. The interface 44 is the number of IFs 21 to 2n to which the next transfer destination 43 is connected via a link. 2A shows the case of IPv4, but this may be IPv6.

  Next, the routing processing unit 121 performs transfer processing of the received packet. The routing processing unit 121 refers to the destination IP address stored in the header of the packet received via the IFs 21 to 2n, the destination 41 and the mask length 42 of the main route table 122, and specifies the next transfer destination 43. . The routing processing unit 121 sends the packet to the interface 44 corresponding to the specified next transfer destination 43.

  Next, the route control unit 11 will be described. The route control unit 11 includes a topology information exchange unit 111, a main route calculation unit 112, an alternative route table determination unit 113, and an alternative route table calculation unit 114.

  First, the topology information exchange unit 111 exchanges topology information with adjacent nodes using a routing control protocol such as OSPF. Here, the topology information is information indicating a connection relationship between a node existing in the communication network and a link connecting the nodes. The adjacent node is a node connected through links 31 to 3n connected to IFs 21 to 2n. The topology information exchanging unit 111 outputs the acquired topology information to the main route calculating unit 112, the alternative route table determining unit 113, and the alternative route table calculating unit 114.

  The topology information exchange unit 111 transmits and receives a failure notification. The failure notification is transmitted by the topology information exchange unit 111 to the adjacent node via the packet transfer unit 12 when a failure occurs in the links 31 to 3n or when a failure occurs in the node 1. When the topology information exchange unit 111 receives the failure notification, the topology information exchange unit 111 detects a failure in the communication network, and detects that a change has occurred in the topology in the communication network. The topology information exchanging unit 111 extracts changes in the topology information of the communication network before and after the occurrence of the failure and notifies the adjacent nodes. The topology information exchange unit 111 also outputs a failure notification to the main route calculation unit 112, the alternative route table determination unit 113, the alternative route table calculation unit 114, and the route table update unit 132.

  The topology information exchange unit 111 exchanges topology information and failure notification with the adjacent node 1 via the packet transfer unit 12 and the IFs 31 to 3n.

  Next, the main route calculation unit 112 calculates route information to be recorded in the main route table 122. When the topology information is input from the topology information exchange unit 111, the main route calculation unit 112 calculates the route information based on the topology information and updates the route information in the main route table 122. The main route calculation unit 112 calculates route information using a general IGP (Interior Gateway Protocol). The IGP includes the OSPF described above.

  Next, the alternative route table determination unit 113 determines whether or not an alternative route table should be created. The alternative route table determination unit 113 determines whether or not an alternative route table corresponding to each link should be created when a failure occurs in each link for all links in the communication network. The alternative route table determination unit 113 determines whether or not an alternative route table corresponding to each link should be created when topology information is input from the topology information acquisition unit 111 or every predetermined time. The alternative route table determination unit 113 notifies the alternative route table calculation unit 114 of the determination result. The determination result includes a link determined to create an alternative route table.

  Next, the alternative route table calculation unit 114 calculates alternative route information. When the alternative route table calculation unit 114 receives the determination result from the alternative route table determination unit 113, the alternative route table calculation unit 114 calculates the alternative route information to be recorded in the alternative route table corresponding to the link included in the determination result. The alternative route table calculation unit 114 calculates alternative route information on the assumption that a failure has occurred in a link for which alternative route information is to be calculated. The alternative route table calculation unit 114 records the alternative route information calculated in the alternative route table corresponding to the link for which the alternative route information is calculated in the alternative route table recording unit 131 of the alternative route table management unit 13 described later.

  Next, the alternative route table management unit 13 will be described. The alternative route table management unit 13 includes an alternative route table storage unit 131 and a route table update unit 132.

  First, the alternative route table storage unit 131 records alternative route tables 1311 to 131n. The alternative route tables 1311 to 131n record alternative route information for updating the route information recorded in the main route table when a failure occurs in the communication network. The alternative route tables 1311 to 131n are provided corresponding to each link existing in the communication network. In the present embodiment, the alternative route table storage unit 131 does not store the alternative route tables 1311 to 131n corresponding to all links existing in the communication network. The alternative route table storage unit 131 stores only the alternative route tables 1311 to 131n corresponding to the links determined to generate the alternative route tables 1311 to 131n based on the determination result of the alternative route table determination unit 113. Yes.

  FIG. 2B is a diagram illustrating an example of the alternative route tables 1311 to 131n in the present embodiment. In the alternative route tables 1311 to 131n, the same items as the main route table 122 are recorded. That is, the alternative route tables 1311 to 131n include items of a destination 51, a mask length 52, a next transfer destination 53, and an interface 54. These are the same as the items of the destination 41, the mask length 42, the next transfer destination 43, and the interface 44 in the main route table 122, respectively, so that the repeated description is omitted.

  The route table update unit 132 updates the main route table 122 using the alternative route tables 1311 to 131n. The route table update unit 132 inputs a failure notification from the topology information exchange unit 111 of the route control unit 11. When the route table update unit 132 detects that a failure has occurred in a specific link in the communication network, the route table update unit 132 generates an alternative route table (hereinafter referred to as a selected alternative route table) corresponding to the failed link (hereinafter referred to as a failed link). The main route table 122 is updated using the selected alternative route table specified by the alternative route table storage unit 131. That is, the route information in the main route table 131 is updated with the alternative route information recorded in the selected alternative route table corresponding to the failed link.

  The route table updating unit 132 updates only the route information corresponding to the alternative route information recorded in the selected alternative route table among the route information recorded in the main route table 122. For example, when FIG. 2B is described as a selected alternative route table, it is assumed that only “192.168.1.0” and “192.168.12.0” are recorded as the destination 51 in FIG. 2B. In this case, only the information corresponding to “192.168.1.0” and “192.168.12.0” is updated in the main route table 122 of FIG. 2A. Therefore, the destination 41 “192.168.10.0” in the main route table 122 and other destinations 41 not shown are not updated. The destination 41 “192.168.10.0” remains in the main route table 122 as this information, and is used by the routing processing unit 121 as it is.

  The above is the description of the configuration of the communication network in the present embodiment. In the present embodiment, the alternative route table determination unit 113 of the route control unit 11 determines whether or not the alternative route tables 1311 to 131n should be created for each link in the communication network. The alternative route table calculation unit 114 creates only the alternative route tables 1311 to 131n corresponding to the links for which it is determined that the alternative route tables 1311 to 131n should be created, and the alternative route table storage unit of the alternative route table management unit 13 131 is stored. Thus, since only the alternative route tables 1311 to 131n determined to be necessary are created and stored, the calculation amount of the alternative route table calculation unit 114 can be suppressed, and the alternative route table storage unit 131 is also stored. It is possible to reduce the memory capacity.

[Description of operation method]
Next, the operation method of the communication network in this embodiment will be described. First, an operation method for creating an alternative route table in the present embodiment will be described with reference to FIG. FIG. 3 shows an operation flow for creating an alternative route table in the present embodiment.

(Step S10)
The alternative route table determination unit 113 extracts links for which the alternative route tables 1311 to 131n are to be created from all the links in the network. The alternative route table determination unit 113 sets the extracted set of links as Nu.

(Step S11)
The alternative route table calculation unit 114 calculates the alternative route information for each link included in the set Nu on the assumption that a failure has occurred in the link.

(Step S12)
The alternative route table calculation unit 114 records the calculated alternative route information in the corresponding alternative route tables 1311 to 131n of the alternative route storage unit 131 of the alternative route table management unit 13.

  The above is the description of the operation method for creating the alternative route table in the present embodiment. In this way, the alternative route tables 1311 to 131n are created and stored in the alternative route table storage unit 131.

  Next, an operation method for extracting a link for creating the alternative route tables 1311 to 131n in the present embodiment will be described. This operation method describes the detailed operation method of step S10 described above. FIG. 4 shows an operation flow for extracting links for creating the alternative route tables 1311 to 131n in the present embodiment.

(Step S20)
The alternative route table determination unit 113 generates empty sets Nu and Nn. The set Nu is a set to be registered of links determined to create an alternative route table. On the other hand, the set Nn is a set to be registered of links determined to have no need to create an alternative route table.

(Step S21)
The alternative route table determination unit 113 extracts, from the shortest path tree, a path to an arbitrary leaf node that has not been subjected to subsequent processing with the self node as a root node. The alternative route table determination unit 113 acquires the shortest path tree from the main route calculation unit 112. Here, the shortest path tree is an effective graph generated based on topology information, and the main route calculation unit 112 calculates route information to be recorded in the main route table 122 using the shortest path tree. The alternative route table determination unit 113 selects one arbitrary leaf node that has not been processed from this step onward from the shortest path tree. Here, the leaf node is a node 1 located at the end of the shortest path tree. The alternative route table determination unit 113 extracts a path from the own node to the selected leaf node in the shortest path tree.

  FIG. 5A is a diagram illustrating an example of the shortest path tree generated by the main route calculation unit 112 in the present embodiment. In FIG. 5A, reference numeral 60 denotes a local node that is a root node. Here, the root node is the highest node 1 in the shortest path tree. In FIG. 5A, reference numerals 61-1 to 6-5 are leaf nodes. It is assumed that the alternative route table determination unit 113 has selected the leaf node 61-1. In this case, the alternative route table determination unit 113 extracts the path 62 from the root node (own node) 60 to the leaf node 61-1.

(Step S22)
The alternative route table determination unit 113 sets links “e1, e2, e3... Em” in the order from the own node to the leaf node in the path extracted from the shortest path tree.

  FIG. 5B is a diagram illustrating the path 62 extracted from the shortest path tree by the alternative route table determination unit 113 according to the present embodiment. As shown in FIG. 5B, the links are set to “e1, e2, e3... Em” in order from the root node 60 toward the leaf node 61-1, from the root node (own node) 60 to the leaf node 61-1.

(Step S23)
The alternative route table determination unit 113 generates a variable i and substitutes “1” for i.

(Step S24)
The alternative route table determination unit 113 determines whether the link ei is an element of the set Nu. In other words, the alternative route table determination unit 113 determines whether or not the link ei is included in the link set Nu that is determined to create the alternative route table. If the link ei is an element of the set Nu, the process proceeds to step S25. On the other hand, if the link ei is not an element of the set Nu, the process proceeds to step S26.

(Step S25)
When the link ei is an element of the set Nu, the alternative route table determination unit 113 increments i as “i = i + 1”. Thereafter, the process returns to step S24.

  In steps S24 and S25, the alternative route table determination unit 113 determines whether or not the link ei close to the own node is an element of the set Nu. Referring to FIG. 5B, the alternative route table determination unit 113 determines whether or not the link ei is included in the set Nu of links determined to create the alternative route table in order from the link close to the root node (own node) 60. It will be determined. This is because the closer to the own node, the greater the influence on the own node when a failure occurs, and the higher the need to update the route information recorded in the main route table 122.

(Step S26)
If the link ei is not an element of the set Nu, the alternative route table determination unit 113 generates a variable j and substitutes “m” for j.

(Step S27)
The alternative route table determination unit 113 determines whether the link ej is an element of the set Nn. That is, the alternative route table determination unit 113 determines whether or not the link ej is included in the link set Nn that is determined not to generate the alternative route table. If the link ej is an element of the set Nn, the process proceeds to step S28. On the other hand, if the link ej is not an element of the set Nn, the process proceeds to step S29.

(Step S28)
When the link em is an element of the set Nn, the alternative route table determination unit 113 decrements j as “i = j−1”. Thereafter, the process returns to step S27.

  In steps S27 and S28, the alternative route table determination unit 113 determines whether or not the link ej that is far from the own node (close to the leaf node) is an element of the set Nn. Referring to FIG. 5B, the alternative route table determination unit 113 determines whether or not the link ei is included in the link set Nn determined that it is not necessary to create an alternative route table in order from the link closest to the leaf node 61-1. It will be determined. This is because the link farther from the own node (closer to the leaf node) has less influence on the own node when a failure occurs, and the necessity of updating the route information recorded in the main route table 122 becomes lower. .

(Step S29)
If the link ei is not an element of the set Nu, the alternative route table determination unit 113 generates a variable k, substitutes the maximum integer that does not exceed the value, taking the arithmetic average of the current i and j. That is, the alternative route table determination unit 113 calculates “k = [(i + j) / 2]”.

  Of the links included in the path extracted from the shortest path tree at the time of this step, it is not determined whether or not route update is necessary for “link ei to link ej”. As described above, it is necessary to update the route information in the main route table 122 at the time of the link failure as the link is closer to the own node. The link information from the main route table 122 at the time of failure of the link is closer to the link from the own node. Need to update. In the following steps, the alternative route table determination unit 113 determines whether or not the route information in the main route table 122 needs to be updated when a specific link failure occurs in the path to the specific leaf node, as shown in FIG. 5B. A process for searching for a link to be a point is performed.

(Step S30)
The alternative route table determination unit 113 determines whether or not the route information in the main route table 122 needs to be updated when the link ek fails. The detailed operation of this step will be described later. If the route information needs to be updated, the process proceeds to step S31. On the other hand, if it is not necessary to update the route information, the process proceeds to step S33.

(Step S31)
The alternative route table determination unit 113 adds the links ei to ek to the elements of the set Nu when the route information in the main route table 122 needs to be updated when the link ek fails. In other words, in the path to a specific leaf node, when it is determined that the route information in the main route table 122 needs to be updated when the link ek fails, all links on the own node side from the link ek have failed in each link. In this case, it is determined that the link needs to be updated in the route information of the main route table 122. As described above, this is because the closer the link is to the own node, the higher the need to update the route information in the main route table 122 at the time of failure. In the present embodiment, by performing the processing in this manner, the alternative route table determination unit 113 can reduce the amount of calculation for determination.

(Step S32)
The alternative route table determination unit 113 sets i to “i = k + 1”. Thereafter, the process proceeds to step S35.

(Step S33)
The alternative route table determination unit 113 adds the links ek to ej to the elements of the set Nn when it is not necessary to update the route information in the main route table 122 when the link ek fails. That is, in the path to a specific leaf node, when it is determined that updating of route information in the main route table 122 is not necessary when the link ek fails, all links on the leaf node side from the link ek have failed in each link. It is determined that the update of the route information in the main route table 122 is not necessary. As described above, this is because the farther the link is from the own node, the lower the need to update the route information in the main route table 122 at the time of failure. By performing the processing in this way, the alternative route table determination unit 113 can reduce the amount of calculation for determination.

(Step S34)
The alternative route table determination unit 113 sets j to “j = k−1”. Thereafter, the process proceeds to step S35.

(Step S35)
The alternative route table determination unit 113 determines “i> j” whether the value of i exceeds the value of j. If the value of i exceeds the value of j, the processing has been completed for all links included in the path. On the other hand, if the value of i does not exceed the value of j, the processing has not yet been completed for all the links included in the path. If the value of i exceeds the value of j, the process proceeds to step S36. On the other hand, if the value of i does not exceed the value of j, the process returns to step S29.

(Step S36)
When the value of i exceeds the value of j, the alternative route table determination unit 113 determines whether or not processing for paths to all leaf nodes included in the shortest path tree has been completed. If processing for paths to all leaf nodes included in the shortest path tree has not been completed, processing returns to step S21 in order to perform processing for paths to other leaf nodes. On the other hand, when the processing for the paths to all the leaf nodes included in the shortest path tree is completed, the operation method ends. At this time, the links included in the set Nu are the links for creating the alternative route tables 1311 to 131n.

  The above is the description of the operation method for extracting the links for creating the alternative route tables 1311 to 131n in the present embodiment. In this way, the links for which the alternative route tables 1311 to 131n are to be created are extracted.

  Next, an operation method for determining whether or not the route information in the main route table 122 needs to be updated when the link ek fails will be described. This operation method explains the detailed operation method of step S30 described above. FIG. 6 shows an operation flow for determining whether or not the route information in the main route table 122 needs to be updated when a failure occurs in the link ek in the present embodiment.

(Step S40)
The alternative route table determination unit 113 acquires the route information currently recorded in the main route table 122.

(Step S41)
The alternative route table calculation unit 114 calculates route information (hereinafter, failure time route information in this description) assuming that a failure has occurred in the link ek. The alternative route table calculation unit 114 calculates the failure route information by the same method as the main route calculation unit 112. The alternative route table calculation unit 114 outputs the calculated failure route information to the alternative route table determination unit 113.

(Step S42)
The alternative route table determination unit 113 obtains the current route information acquired from the main route calculation unit 112 in step S40 and the failure time route information at the time of failure of the link ek calculated by the alternative route table calculation unit 114 in step S41. Compare.

(Step S43)
The alternative route table determination unit 113 determines whether there is a destination network having a different next transfer destination before and after the failure of the link ek in the comparison in step S42. If there is even one destination network with a different next transfer destination before and after the failure of the link ek, the process proceeds to step S44. On the other hand, if there is no destination network with a different next transfer destination before and after the failure of the link ek, the process proceeds to step S45.

(Step S44)
The alternative route table determination unit 113 determines that route update for the link ek is necessary when there are destination networks with different next transfer destinations before and after the failure of the link ek. Therefore, as described above, the link ek belongs to the set Nu, and the alternative route tables 1311 to 131n corresponding to the link ek are created. In this case, this operation method ends.

(Step S45)
The alternative route table determination unit 113 determines that route update for the link ek is not necessary when there is no destination network with a different next transfer destination before and after the failure of the link ek. Therefore, as described above, the link ek belongs to the set Nn, and the alternative route tables 1311 to 131n corresponding to the link ek are not created. This completes the operation method.

  The above is the description of the operation method for determining whether or not the route information in the main route table 122 needs to be updated when the link ek has a failure.

  The above is the description of the communication network in the present embodiment.

(Second Embodiment)
Next, the communication network of the second embodiment will be described.

  The communication network of the present embodiment is different from the first embodiment in the link target for determining whether or not each node constituting the communication network creates an alternative route table. In the first embodiment, each node determines whether to create an alternative route table for all links in the communication network. In this embodiment, each node determines whether or not to create an alternative route table only for the link connected to its own node. Further, in this embodiment, each node is different from the first embodiment in that each node specifies not only its own node, but also another node specifies a link for which an alternative route table should be created and notifies the other node of the link. As a result, each node performs a determination process for the link connected to its own node, creates an alternative route table for the link determined to be required to create an alternative route table, and receives notification from other nodes. Since it is only necessary to create an alternative route table for the link for which the alternative route table is to be created, it is possible to reduce the amount of calculation for calculating the alternative route table and the memory amount for storing the alternative route table.

[Description of configuration]
First, the configuration of the nodes constituting the communication network in the present embodiment will be described. FIG. 7 is a diagram illustrating a configuration of the node 1 in the present embodiment. The node 1 in this embodiment has substantially the same configuration as that in the first embodiment. Therefore, repeated description of the same parts as in the first embodiment is omitted, and different parts are mainly described. Moreover, about the structure similar to 1st Embodiment, the same code | symbol is provided and demonstrated.

  Similarly to the first embodiment, the node 1 of the present embodiment includes a route control unit 11, a packet transfer unit 12, an alternative route table management unit 13, and network interfaces (hereinafter referred to as IF) 21 to 2n. In this embodiment, the creation instruction communication unit 14 is provided.

  As in the first embodiment, the communication network of the present embodiment includes a plurality of nodes 1 as shown in FIG. 7, and each node 1 is connected to another by links 31 to 3n connected to IFs 21 to 2n. To establish a communication network.

  First, the route control unit 11 will be described. Similarly to the first embodiment, the route control unit 11 includes a topology information exchange unit 111, a main route calculation unit 112, and an alternative route table calculation unit 114, and in this embodiment, an alternative route table determination unit. Instead of 113, a connection link alternative route table 115 is provided.

  First, the topology information exchanging unit 111 is the same as in the first embodiment. That is, the topology information exchanging unit 111 exchanges topology information with adjacent nodes using a path control protocol such as OSPF. Further, when a failure notification is input, topology information exchanging section 111 detects that a change has occurred in the topology of the communication network and notifies the adjacent node of the change in topology information.

  Next, the main route calculation unit 112 is the same as in the first embodiment. That is, the main route calculation unit 112 calculates route information to be recorded in the main route table 122 based on the topology information, and updates the route information in the main route table 122.

  Next, the connection link alternative route table determination unit 115 determines whether or not an alternative route table should be created. The connected link alternative route table determination unit 115 determines whether or not alternative route tables 1311 to 131n should be created for each of the links 31 to 3n connected to the IFs 21 to 2n. That is, the connected link alternative route table determination unit 115 determines whether or not the alternative route tables 1311 to 131n should be created only for the link connected to the own node. The connected link alternative route table determination unit 115 notifies the alternative route table calculation unit 114 of the determination result. The determination result includes a link determined to create an alternative route table.

  Moreover, the connection link alternative route table determination part 115 specifies the other node which should produce the alternative route tables 1311-131n corresponding to the links 31-3n. The connected link alternative route table determination unit 115 determines another node (hereinafter referred to as calculation designation) that should be created as an alternative route table 1311 to 131n for a specific link (hereinafter referred to as a selected connection link) among the links 31 to 3n. A creation instruction message for the node is output to the creation instruction communication unit 14.

  The creation instruction message is a message requesting the calculation designated node to create the alternative route tables 1311 to 131n corresponding to the selected connection link. FIG. 8A is a diagram showing a payload of a creation instruction message in the present embodiment. As shown in FIG. 8A, the creation instruction message stores a “Network Address” field 70 and a “Network Subnet Mask” field 71 in the payload. The creation instruction message is transmitted as a packet with an IP header and a TCP header or UDP header added to the payload. The communication protocol is not limited to these. In the “Network Address” field 70 and the “Network Subnet Mask” field 71, the destination 41 and the mask length 42 corresponding to the interface 44 (selected connection link) are recorded in the main route table 122 shown in FIG. 2A, respectively. Information to be recorded in the “Network Address” field 70 and the “Network Subnet Mask” field 71 can be acquired by referring to “Network LSA” for transmitting and receiving topology information in the case of a network in which OSPF operates. For reference, FIG. 8B shows the structure of the payload of “Network LSA” in the conventional OSPF. Information corresponding to the “Network Address” field 70 is stored in the “Link” State ID ”field 72 in FIG. 8B, and the“ Network Subnet Mask ”field 71 is stored in the“ Network Subnet Mask ”field 73 in FIG. 8B. Information corresponding to is stored.

  Next, the alternative route table calculation unit 114 calculates the alternative route information to be recorded in the alternative route tables 1311 to 131n, as in the first embodiment. The alternative route table calculation unit 114 calculates the alternative route information to be recorded in the alternative route tables 1311 to 131n corresponding to the links that the connection link alternative route table determination unit 115 determines to generate the alternative route tables 1311 to 131n. . The alternative route table calculation unit 114 calculates alternative route information on the assumption that a failure has occurred in the links for which the alternative route tables 1311 to 131n are to be created. The alternative route table calculation unit 114 records the calculated alternative route information in the corresponding alternative route tables 1311 to 131n in the alternative route table recording unit 131 of the alternative route table management unit 13 described later.

  The alternative route table calculation unit 114 also receives a creation instruction message from the creation instruction communication unit 14 described later. The alternative route table calculation unit 114 specifies a link for which the alternative route tables 1311 to 131n are to be created based on the information stored in the creation instruction message. The alternative route table calculation unit 114 calculates alternative route information when it is assumed that a failure has occurred in the specified link, and the alternative route table 1311-131n calculated in the alternative route table recording unit 131 is calculated. Record route information.

  Next, the creation instruction communication unit 14 will be described. The creation instruction communication unit 14 includes a creation instruction transmission unit 141 and a creation instruction reception unit 142.

  First, the creation instruction transmission unit 141 transmits the creation instruction message input from the connection link alternative route table determination unit 115 to the calculation designated node via the packet transfer unit 12.

  Next, the creation instruction reception unit 142 outputs a creation instruction message received from another node to the alternative route table calculation unit 114 via the packet transfer unit 12.

  Next, the packet transfer unit 12 will be described. The packet transfer unit 12 is the same as that in the first embodiment. That is, the packet transfer unit 12 includes a routing processing unit 121 and a main route table 122. The main route table 122 is a data table in which route information is recorded. Next, the routing processing unit 121 performs transfer processing of the received packet based on the main route table 122.

  Next, the alternative route table management unit 13 will be described. The alternative route table management unit 13 is the same as in the first embodiment. That is, the alternative route table management unit 13 includes an alternative route table storage unit 131 and a route table update unit 132. The alternative route table storage unit 131 records the alternative route tables 1311 to 131n, and the alternative route tables 1311 to 131n update the route information recorded in the main route table when a failure occurs in the communication network. To record alternative route information. When the failure notification is input from the topology information exchanging unit 111, the route table updating unit 132 updates the main route table 122 using the alternative route tables 1311 to 131n.

  The above is the description of the configuration of the communication network in the present embodiment. As described above, in this embodiment, the connected link alternative route table determination unit 115 of each node 1 should create the alternative route tables 1311 to 131n only for the links 31 to 3n connected to the IFs 21 to 2n. Determine. Further, the alternative route calculation unit 114 determines the link determined to create the alternative route tables 1311 to 131n in the determination result of the connection link alternative route table determination unit 115, and the other received by the creation instruction reception unit 142. Only the alternative route tables 1311 to 131n respectively corresponding to the links corresponding to the network addresses included in the creation instruction message from the node are created. Therefore, it is possible to suppress the calculation amount of the connection link alternative route table determination unit 115 and the alternative route table calculation unit 114, and also to suppress the memory capacity of the alternative route table storage unit 131 that stores the alternative route tables 1311 to 131n. Is possible.

[Description of operation method]
Next, the operation method of the communication network in this embodiment will be described. First, an operation method for creating an alternative route table in the present embodiment will be described with reference to FIG. FIG. 9 shows an operation flow for creating an alternative route table in the present embodiment.

(Step S50)
The connected link alternative route table determination unit 115 selects one arbitrary link (hereinafter referred to as a selected connection link) that is not subjected to the determination process according to this operation method from the links 31 to 3n connected to the IFs 21 to 2n. To do. The connection link alternative route table determination unit 115 sets the selected connection link to ek.

(Step S51)
The alternative route calculation unit 114 calculates alternative route information to be recorded in the main route table 122 when it is assumed that a failure has occurred in the selected connection link ek selected by the connection link alternative route table determination unit 115. The alternative route calculation unit 114 records the calculated alternative route information in the alternative route tables 1311 to 131n corresponding to the link ek. In this step, when a failure occurs in the selected connection link ek, it is not determined whether or not the route information for the leaf node is changed before and after the failure of the selected connection link ek. As explained with reference to FIG. 5B, the closer the link is to the own node, the higher the possibility that the route information of the own node will be affected at the time of failure. Furthermore, the selected connection link ek is directly connected to the own node. This is because since it is a connected link, it is considered that the route information in the main route table 122 must be updated whenever a failure occurs in the selected connection link ek. Note that, as described in the first embodiment, an operation method for determining whether or not the route information of the main route table 122 needs to be updated for the selected connection link ek may be used.

(Step S52)
The alternative route calculation unit 114 outputs the shortest path tree generated in the process of calculating the alternative route information of the selected connection link ek (hereinafter, the shortest path tree at the time of failure) to the connection link alternative route table determination unit 115.

(Step S53)
The connected link alternative route table determination unit 115 acquires from the main route calculation unit 112 the shortest path tree generated in the process of calculating route information to be recorded in the main route table 122. This shortest path tree is generated in a state where no failure has occurred in all the links in the communication network.

(Step S54)
The connection link alternative route table determination unit 115 determines the other node 1 existing in the communication network based on the shortest path tree at the time of failure acquired from the alternative route calculation unit 114 and the shortest path tree acquired from the main route calculation unit 112. Among them, a node that needs to calculate alternative route information (hereinafter, a calculation designated node) is specified. A method for specifying the calculation designated node will be described later.

(Step S55)
The connection link alternative route table determination unit 115 generates a creation instruction message instructing creation of an alternative route table for the connection selection link ek, and outputs it to the creation instruction transmission unit 141 of the creation instruction communication unit 14. The creation instruction transmission unit 141 transmits a creation instruction message to the calculation designated node via the packet transfer unit 12.

(Step S56)
The connected link alternative route table determination unit 115 determines whether the determination process according to this operation method has been performed on all the links 31 to 3n. If the determination process has not been completed for all the links 31 to 3n, the process returns to step S50 in order to newly perform the determination process for an arbitrary selected connection link ek. On the other hand, when the determination process is performed on all the links 31 to 3n, the operation method ends.

  The above is the description of the operation method for creating the alternative route table in the present embodiment. In the present embodiment, alternative route tables 1311 to 131n corresponding to the connection selection link ek selected from the links 31 to 3n are created in this way, and the alternative route tables 1311 to 131n corresponding to the selected connection link ek are created. A calculation designation node that needs to be created is specified, and a creation instruction message is transmitted to the calculation designation node so as to create the alternative route tables 1311 to 131n corresponding to the selected connection link ek.

  Next, a method for specifying a node (calculation designated node) that needs to create the alternative route tables 1311 to 131n corresponding to the selected connection link ek in the present embodiment will be described. This description explains in detail the operation method of step S54 described above. FIG. 10 is an operation flow for specifying a calculation designated node in the present embodiment.

(Step S60)
Connecting link alternative route table determination section 115, the selectivity connection link ek selected in step S50 described above, the self-node to generate a reverse shortest path tree T ^R to the end point (hereinafter, the node r in this description).

(Step S61)
The connected link alternative route table determination unit 115 generates a set Vu, which is a set of calculation designated nodes, and initializes Vu.

(Step S62)
The connection link alternative route table determination unit 115 is based on the current shortest path tree (before the failure of the selected connection link ek) recorded in the main route table 122 (hereinafter, the shortest path tree T) acquired in step S53. In the route information, the destination node to which the next transfer destination is connected via the selected connection link ek is extracted as a processing target. That is, in this case, among the destination nodes recorded in the main route table 122, a destination node that requires a change of the next transfer destination becomes a processing target when a failure occurs in the selected connection link ek. The connected link alternative route table determination unit 115 selects an arbitrary node d that has not performed the subsequent processing in this operation method from among the extracted processing target nodes (hereinafter, processing target nodes).

(Step S63)
The connected link alternative route table determination unit 115 extracts a path from the node r (self node) to the node d based on the shortest path tree at the time of failure (hereinafter referred to as the shortest path tree at the time of failure) acquired in step S52 described above. The connected link alternative route table determination unit 115 identifies the next node of the own node r in the extracted path and sets it as the node n.

(Step S64)
The connected link alternative route table determination unit 115 subtracts the value Cd obtained by subtracting the cost of the path from the node r to the node d in the shortest path tree T before the failure from the cost of the path from the node r to the node d in the shortest path tree Ti at the time of failure. calculate.

(Step S65)
Connecting link alternative route table determination section 115, sum cost of the path from the node r in the shortest path tree T before fault to node n, the path from node n in the opposite direction of the shortest path tree T ^R to node r and cost The calculated value Cn is calculated.

(Step S66)
The connected link alternative route table determination unit 115 compares the values of Cn and Cd. If Cn is equal to or less than Cd, the process proceeds to step S67. On the other hand, if Cn is greater than Cd, the process proceeds to step S69.

(Step S67)
When Cn is equal to or less than Cd, the connected link alternative route table determination unit 115 identifies the node n as a designated calculation node that needs to create an alternative route table. The connected link alternative route table determination unit 115 adds the node n to the set Vu.

(Step S68)
Based on the failure time shortest path tree Ti, the connection link alternative route table determination unit 115 identifies a node positioned next to the node n in the path from the node r to the node d, and sets the node as the node n. Thereafter, the process returns to step S65.

(Step S69)
When Cn is larger than Cd, the connected link alternative route table determination unit 115 determines whether the determination processing for all the processing target nodes extracted in step S62 is completed. If the determination process has not been completed for all the processing target nodes, the process returns to step S62 in order to select a new node d. On the other hand, when the determination victory has been completed for all the processing target nodes, the operation flow ends. At this point, the nodes included in the set Vu are calculation designated nodes that are determined to require the creation of an alternative routing table.

  The method for specifying the calculation designated node in the present embodiment has been described above. In the present embodiment, the calculation designation node is calculated in this way. Note that the method for specifying the calculation designated node is not limited to the above-described method.

  Next, in this embodiment, an operation method when a creation instruction message is received from another node will be described. FIG. 11 shows an operation flow when a creation instruction message is received from another node in this embodiment.

(Step S70)
The creation instruction receiving unit 142 receives a creation instruction message from another node via the packet transfer unit 12. The alternative route table calculation unit 114 extracts information on the link for which the alternative route tables 1311 to 131n stored in the creation instruction message are to be created.

(Step S71)
The alternative route table calculation unit 114 calculates, for the link extracted from the creation instruction message, alternative route information used when a failure occurs in the link.

(Step S72)
The alternative route table calculation unit 114 records the calculated alternative route information in the alternative route tables 1311 to 131n corresponding to the links extracted from the creation instruction message in the alternative route table storage unit 131.

  The above is the description of the operation method when a creation instruction message is received from another node. In this way, the alternative route tables 1311 to 131n corresponding to the links stored in the received creation instruction message are created.

  The above is the description of the communication network in the present embodiment.

  Up to this point, the communication network of the present invention has been described. According to the first embodiment of the communication network of the present invention, in each node 1 configuring the communication network, the alternative route table determination unit 113 sets the alternative route tables 1311 to 131n for the links existing in the communication network. Determine whether to create. The alternative route table calculation unit 114 creates only the alternative route tables 1311 to 131n corresponding to the links determined to create the alternative route tables 1311 to 131n. Therefore, the calculation amount of the alternative route table calculation unit 114 can be reduced, and the memory capacity of the alternative route storage unit 131 that stores the alternative route tables 1311 to 131n can be reduced.

  Further, according to the second embodiment of the communication network of the present invention, each node 1 determines whether or not to create the alternative route tables 1311 to 131n only for the links connected to the node 1 itself. In the present embodiment, each node 1 identifies not only its own node 1 but also a link for which another node 1 should create an alternative route table, and notifies the other node 1 of the link. As a result, each node 1 performs a determination process on the link connected to its own node 1 to create the alternative route tables 1311 to 131n for the links that are determined to require the creation of the alternative route tables 1311 to 131n. Since the alternative route tables 1311 to 131n for the links for which the alternative route tables 1311 to 131n notified from the other nodes 1 should be created, the calculation amount for calculating the alternative route tables 1311 to 131n, and the alternative It is possible to reduce the amount of memory for storing the route tables 1311 to 131n.

  The first embodiment and the second embodiment cannot be implemented only independently. It can also be realized by combining them. In each embodiment, only the case where a failure occurs in the link has been described. However, the present invention can also be applied when a failure occurs in a node. In this case, an alternative route table corresponding to each node is created. In FIG. 4, the process is performed on the links included in the path extracted in step S21. When handling a node failure, instead of setting each link to “e1, e2,... Em” in step S22, each node included in the path is set to “n1, n2. Perform the process. That is, instead of targeting each link in the path, processing may be performed for each node in the path. In FIG. 6, it is assumed that a failure has occurred in the link ek in step S41, but route information is created assuming that a failure has occurred in the node nk and all the links connected to the node nk. do it. Further, when creating an alternative route table to be actually used, route information assuming that a failure has occurred in the node nk and all the links connected to the node nk may be created. Further, in the creation instruction message, information that can uniquely identify the node nk is stored instead of the “Network Address” field 70. The information that can uniquely identify the node nk is, for example, the IP address of the node nk. By making such changes, the present invention can be applied to node failures. That is, the present invention can be applied to network resources constituting a communication network including nodes and links.

  Also, the alternative route table storage unit 131 becomes unnecessary or becomes unnecessary when the alternative route tables 1311 to 131n become unnecessary due to a change in the topology of the communication network. The alternative route information recorded in the alternative route tables 1311 to 131n may be deleted. As a result, the memory capacity can be further suppressed.

  Note that each network node included in the communication network of the present invention can realize the function to be executed by hardware or software. When implemented by software, a computer program introduced into each network node can be recorded on an information recording medium such as a CD-R (Compact Disc Recordable) or an HDD (Hard Disk Drive). . The computer program can be introduced into each network node using such a recording medium.

  While the present invention has been described with reference to the embodiments, the present invention is not limited to the above embodiments. Various changes that can be understood by those skilled in the art can be made to the configuration and details of the present invention within the scope of the present invention.

1 node 11 route control unit 12 packet transfer unit 13 alternative route table management unit 14 creation instruction communication unit 21 to 2n network interface 31 to 3n link 41 destination 42 mask length 43 next transfer destination 44 interface 51 destination 52 mask length 53 next transfer destination 54 Interface 60 Root node 61-1 to 5 Leaf node 62 Path 70 Network Address field (creation instruction message)
71 Network Subnet Mask field (creation instruction message)
72 Link State ID field (Network LSA)
73 Network Subnet Mask field (Network LSA)
111 Topology Information Exchange Unit 112 Main Route Calculation Unit 113 Alternative Route Table Determination Unit 114 Alternative Route Table Calculation Unit 115 Connected Link Alternative Route Table Determination Unit 121 Routing Processing Unit 122 Main Route Table 131 Alternative Route Table Storage Unit 132 Route Table Update Unit 141 Creation instruction transmission unit 142 Creation instruction reception units 1311 to 131n Alternative route table

Claims (18)

A communication network comprising a plurality of network nodes,
Each of the plurality of network nodes is
Multiple interfaces,
A main route table recording route information in the communication network;
A routing processing unit that forwards packets input from the plurality of interfaces based on the main route table;
An alternative that is provided corresponding to a network resource that constitutes the communication network and that records alternative route information of the route information to be updated among the route information recorded in the main route table when the network resource fails An alternative route table storage unit for storing the route table;
The network resource includes the plurality of network nodes and links connecting the plurality of network nodes, and when a failure occurs in a selected network resource selected from the network resources, An alternative route table determination unit that determines whether to create the alternative route table corresponding to the selected network resource based on whether or not the route information needs to be updated;
An alternative route table calculation unit for calculating the alternative route information to be recorded in the selected alternative route table corresponding to the selected network resource determined to create the alternative route table;
A route table update unit that updates the route information of the main route table using the alternative route information recorded in the alternative route table corresponding to the network resource in which the failure has occurred when detecting the failure ;
A topology information exchange unit that transmits and receives topology information of the communication network with an adjacent network node in the network;
A main route calculation unit that generates a shortest path tree of the network based on the topology information and updates the route information recorded in the main route table based on the shortest path tree ;
The alternative route table determination unit selects an arbitrary selected leaf node from leaf nodes included in the shortest path tree, extracts a path to the selected leaf node from the shortest path tree, and is included in the path When the selected network resource is selected from the network resources, and the selected network resource is determined to be the network resource for which the alternative route table is to be created, the selected network resource among the network resources existing in the path A communication network that decides to create the alternative routing table for all the network resources closer to its own network node . The communication network according to claim 1,
The alternative route table determination unit obtains the route information from the main route table, and calculates failure time route information to be recorded in the main route table when it is assumed that a failure has occurred in the selected network resource. And determining whether or not to create the alternative route table corresponding to the selected network resource based on whether or not the failure time route information and the route information are different. A communication network according to claim 2, wherein
When the failure path information and the path information are compared, and the next transfer destination network nodes corresponding to the same destination network included in the failure path information and the path information are different, A communication network that is determined to create the alternative routing table corresponding to a selected network resource. A communication network according to any one of claims 1 to 3 ,
When the alternative route table determination unit determines that the selected network resource is the network resource that does not need to create the alternative route table, among the network resources existing in the path, the alternative leaf table determines the selected leaf from the selected network resource. A communication network that determines that it is not necessary to create the alternative routing table for all the network resources close to a node. A communication network according to any one of claims 1 to 4 ,
The alternative route table determination unit is a communication network that selects the selected network resource from the links connected to the plurality of interfaces. A communication network according to claim 5 , wherein
A creation instruction communication unit that transmits and receives a creation instruction message that instructs creation of the alternative routing table corresponding to the selected network resource;
The alternative route table determination unit is configured to calculate the alternative route table corresponding to the selected network resource when it is assumed that a failure has occurred in the selected network resource among the plurality of network nodes. Identify
The creation instruction communication unit transmits the creation instruction message to the calculation designated network node. The communication network according to claim 6 ,
The creation instruction communication unit receives the creation instruction message from the plurality of network nodes,
The alternative calculation table calculation unit identifies the selected network resource for which the alternative route table should be created based on the information stored in the creation instruction message, and is recorded in the alternative route table corresponding to the selected network resource. A communication network that calculates the alternative route information to be recorded and records the alternative route information in the alternative route table corresponding to the selected network resource. A communication network according to claim 6 or 7 ,
The creation instruction message records a destination network address corresponding to the link selected as the selected network resource in the main route table, and a subnet mask of the destination network address,
The alternative route table calculation unit is a communication network that identifies the link selected as the selected network resource based on the destination network address and a subnet mask of the destination network address. A network node constituting the communication network according to claim 1 . In a communication network comprising a plurality of network nodes,
Recording route information in the communication network;
Forwarding packets input from a plurality of interfaces based on the main routing table;
An alternative that is provided corresponding to a network resource that constitutes the communication network and that records alternative route information of the route information to be updated among the route information recorded in the main route table when the network resource fails Storing a routing table;
The network resource includes the plurality of network nodes and a link connecting the plurality of network nodes, and when a failure occurs in the selected network resource for selecting the network resource, the route in the main route table Determining whether to create the alternative routing table corresponding to the selected network resource based on whether an update of information is necessary;
Calculating the alternative route information to be recorded in a selected alternative route table corresponding to the network resource determined to create the alternative route table;
Updating the route information in the main route table using the alternative route information recorded in the alternative route table corresponding to the network resource in which the failure has occurred when detecting the failure ;
Transmitting and receiving topology information of the communication network with an adjacent network node in the network;
Generating a shortest path tree of the network based on the topology information;
Updating the route information recorded in the main route table based on the shortest path tree ; and
Determining whether to create the alternative routing table corresponding to the selected network resource,
Selecting an arbitrary selected leaf node from among the leaf nodes included in the shortest path tree;
Extracting a path to the selected leaf node from the shortest path tree;
Selecting the selected network resource from the network resources included in the path;
When the selected network resource is determined as the network resource for which the alternative route table is to be created, among the network resources existing in the path, for all the network resources closer to the network node than the selected network resource Determining to create the alternative routing table
Communication path control method including The communication path control method according to claim 10 ,
Determining whether to create the alternative routing table corresponding to the selected network resource,
Obtaining the route information;
Calculating failure path information to be recorded in the main path table when it is assumed that a failure has occurred in the selected network resource;
Determining whether or not to create the alternative route table corresponding to the selected network resource based on whether or not the failure route information and the route information are different. The communication path control method according to claim 11 ,
The step of determining based on whether or not the failure path information and the path information are different,
Comparing the failure path information with the path information;
When the next transfer destination network node corresponding to the same destination network included in each of the route information at the time of failure and the route information is different, it is determined to create the alternative route table corresponding to the selected network resource A communication path control method including steps. The communication path control method according to any one of claims 10 to 12 ,
Determining whether to create the alternative routing table corresponding to the selected network resource,
When the selected network resource is determined as the network resource that does not need to create the alternative routing table, all the network resources that are closer to the selected leaf node than the selected network resource among the network resources existing in the path In contrast, the communication path control method includes a step of determining that it is not necessary to create the alternative routing table. A communication path control method according to any one of claims 10 to 13 ,
Determining whether to create the alternative routing table corresponding to the selected network resource,
A communication path control method including a step of selecting the selected network resource from the links connected to the plurality of interfaces. The communication path control method according to claim 14 ,
Further comprising transmitting and receiving a creation instruction message instructing creation of the alternative routing table corresponding to the selected network resource,
Determining whether to create the alternative routing table corresponding to the selected network resource,
Specifying a calculation-designated network node that should create the alternative routing table corresponding to the selected network resource when it is assumed that a failure has occurred in the selected network resource from the plurality of network nodes;
The step of transmitting and receiving the creation instruction message includes:
A communication path control method including a step of transmitting the creation instruction message to the calculation designated network node. The communication path control method according to claim 15 ,
The step of transmitting and receiving the creation instruction message includes:
Receiving the creation instruction message from the plurality of network nodes;
The step of calculating the alternative route information includes:
Identifying the selected network resource to create the alternate routing table based on information stored in the creation instruction message;
Calculating the alternative route information to be recorded in an alternative route table corresponding to the selected network resource;
Recording the alternative route information in the alternative route table corresponding to the selected network resource. The communication path control method according to claim 16 ,
The creation instruction message records a destination network address corresponding to the link selected as the selected network resource in the main route table, and a subnet mask of the destination network address,
Identifying the selected network resource for which the alternative routing table should be created includes
A communication path control method including a step of identifying the selected link selected as the selected network resource based on a destination network address and a subnet mask of the destination network address. A computer program that causes a computer to execute the communication path control method according to claim 10 .

Images