JP5576837B2 - Route information update system and route information update method - Google Patents

Description

  The present invention relates to a route information update system and a route information update method at the time of equipment increase / decrease in a packet switching network such as an IP (Internet Protocol) network.

  In a network, it is important to recover a failure by quickly switching a transfer path in response to an unexpected failure and maintain a transfer quality. As a failure recovery method in an IP network, there is a dynamic recovery method using a routing protocol such as OSPF (Open Shortest Path First) (see Non-Patent Document 1).

  In OSPF, a node that detects a failure notifies (floods) failure information to all nodes. The node that has received the failure information can automatically switch the transfer route by calculating the backup route based on the network topology information excluding the failure part. However, since OSPF calculates a backup route after a failure occurs, there is a problem that it takes time in seconds to recover from the failure. Further, notification of failure information and calculation of a backup route increase depending on the scale of the IP network.

  As a method for solving such a problem, an IP-FRR (IP Fast Reroute) method that realizes high-speed failure recovery by calculating a standby route in advance has been proposed (see Non-Patent Document 2). ). In the IP-FRR method, a backup topology is created in advance, and when a failure occurs, failure recovery is performed by switching to a transfer path according to the backup topology that protects (bypasses) the corresponding failure location.

  A specific example of a failure recovery method using a backup topology in the IP-FRR system will be described with reference to FIG. FIG. 10A shows an example of a normal topology, and FIG. 10B shows an example of a backup topology.

  First, the node prepares a configuration (preliminary topology) in preparation for link breakage in advance. For example, in preparation for a case where the link 1-2 (the link between the node having the node number “1” and the node having the node number “2”) is disconnected, the node is a spare having the link 1-2 as a protection link. Create a topology in advance. The link cost of the protect link in the backup topology is given a maximum value that can be set so that the protect link is not selected as a route. Thus, when a route is calculated by the minimum cost routing that minimizes the sum of the link costs on the standby topology, a route that does not use the protected link is calculated. This spare topology is input to all nodes, and a spare system route according to the spare topology is calculated in advance (before traffic transfer) for all nodes.

  Here, a case is considered where a failure of the link 1-2 is detected on a route having the node with the node number “1” as src (originating node) and the node with the node number “5” as dst (destination node). For example, on the normal topology shown in FIG. 10A, (1) when a failure of the link 1-2 is detected, the failure detection node (the node with the node number “1”) protects the failure link. Then, the packet is transferred to the node with the node number “4” (see FIG. 10B). At this time, the failure detection node (the node with the node number “1”) knows that the link 1-2 has failed, and thus knows that the failure location can be bypassed using the backup topology A.

  However, other nodes (for example, the node having the node number “4”) cannot grasp the failure location. Therefore, the failure detection node (the node with the node number “1”) (2) selects the spare topology A to be used, and assigns the ID of the spare topology A to the header of the packet to be transferred to the node with the node number “4”. To do. When another node (here, the node having the node number “4”) on the backup path receives the packet, (3) referring to the header of this packet and selecting the backup topology A to be used. Then, the packet is transferred to the node having the node number “5”, which is the backup path in accordance with the selected backup topology A.

  As described above, the IP-FRR system that has been studied conventionally creates a plurality of spare topologies for protecting each link on the assumption that the reference topology is fixed without adding or removing nodes. In this way, high-speed recovery can be realized for any single link failure. As long as the connectivity of the backup topology is ensured, a plurality of links may be protected in the backup topology.

“OSPF Version 2”, [online], April 1998, IETF, [searched July 25, 2011], Internet <URL: http://www.ietf.org/rfc/rfc2328.txt> A.Kyalbein, A.F.Hansen, T.Cicic, S.Gjessing, and O.Lysne, “Fast IP Network Recovery using Multiple Routing Configurations,” in Proceedings of INFOCOM, Apr.2006

As described above, the IP-FRR scheme that has been studied in the past is based on the premise that the reference topology is fixed. Since the topology changes when equipment is added or removed, it is necessary to recalculate and set not only the working path but also the backup path for IP-FRR in accordance with the change in topology.
However, in Non-Patent Document 2, the case where the topology is changed is not taken into consideration. Therefore, when the topology is changed, the working path and the standby path cannot be recalculated.

  The present invention has been made in view of the above problems, and updates the route information by updating the route by optimally setting the order of the link state notification, the active route calculation, and the standby route calculation when the topology is changed. It is an object to provide a system and a route information update method.

  In order to solve the above-mentioned problem, a route information update system according to the present invention is a route information update system for updating a route of a packet flowing in a network constituted by connecting a plurality of nodes by links, and each node A network topology information DB in which a link state that is information of an interface of the link connected to each node belonging to the network is stored, and when the connected link is changed, another adjacent node A link state transmission unit that transmits the link state as a link state notification, a link state reception unit that updates the network topology information DB based on the received link state notification when the link state notification is received, When the network topology information DB is updated, the received link state communication A link state transfer unit that further transfers the network to another adjacent node, an active path calculation unit that calculates an active path based on the network topology information DB, and the network topology information DB based on the network topology information DB. Controls the order of processing of the standby path calculation unit that calculates the backup path to be used when the active path cannot be used, and the link state transfer unit, the active path calculation unit, and the backup path calculation unit A protocol control unit that performs the processing of the backup path calculation unit after the processing of the link state transfer unit and the active path calculation unit is completed. And

  In this way, the route information update system according to the present invention can transfer the link state notification to another node before the route is calculated. Therefore, the route information update system according to the present invention can transmit the link state notification to each node in the communication network earlier. In particular, when equipment is reduced, it is possible to avoid using lost equipment (link) by notifying the reduction information (link state notification) immediately.

In the route information update system according to the present invention, the protocol control unit causes the standby system route calculation unit to perform processing after the processing of the link state transfer unit and the active system route calculation unit is completed. Instead, the processing of the link state transfer unit and the active system route calculation unit is performed after the processing of the backup system route calculation unit is completed.

  By doing so, the route information update system according to the present invention can perform the calculation of the backup route prior to the transfer of the link state notification. Therefore, the path information update system according to the present invention is configured so that when a failure occurs in a state where the calculation of only the active system path is completed without the calculation of the standby system path being completed at the added node, Specifically, although there is a path that can be bypassed, the calculation of the backup system path has not been completed, so that a state where packet transfer cannot be performed does not occur. That is, since the backup path is calculated in advance, when the active path fails, packets can be reliably transmitted using the backup path as long as physical connectivity is ensured.

In the route information update system according to the present invention, the protocol control unit causes the standby system route calculation unit to perform processing after the processing of the link state transfer unit and the active system route calculation unit is completed. Instead, the processing of the link state transfer unit is performed after the processing of the working path calculation unit and the backup path calculation unit is completed.

  By doing so, the route information update system according to the present invention can complete the calculation of the working route and the standby route before the transfer of the link state notification. Therefore, the path information update system according to the present invention completes the calculation of the transfer destination active path before the calculation of the transfer source active path of the link state notification is completed, and transfers from the transfer source to the transfer destination. The phenomenon that the IP packet is lost (discarded) at the transfer source does not occur when transferring the IP packet.

  According to the route information update method and the route information update system according to the present invention, when the topology is changed, the route can be updated by optimally setting the order of the link state notification, the active route calculation, and the standby route calculation. it can.

It is a block diagram of the communication network which concerns on 1st Embodiment. It is a functional block diagram of the node which concerns on 1st Embodiment. It is a flowchart which shows the processing procedure (OSPF) of the conventional node. It is a flowchart which shows the process sequence (case 1) of the node which concerns on 1st Embodiment. It is a flowchart which shows the process sequence (case 2) of the node which concerns on 1st Embodiment. It is a flowchart which shows the process sequence (case 3) of the node which concerns on 1st Embodiment. 1 is a schematic diagram of a communication network according to a first embodiment. FIG. 7A shows a state where one node is physically added to the communication network, and FIG. 7B shows setting of interfaces and protocols of the added node and adjacent nodes. FIG. 7C shows a state in which the added node acquires information related to the topology of the communication network, and FIG. 7D shows a link state notification transmitted from the added node to other nodes. Shows how it is transferred. It is a block diagram of the communication network which concerns on 2nd Embodiment. It is a function block diagram of the control server which concerns on 2nd Embodiment. It is a figure for demonstrating the failure recovery method using the backup topology in an IP-FRR system.

[Summary of Invention]
In the conventional OSPF method, processing is performed in the order of (1) notification of “interface information (link state)” to other nodes and (2) calculation of the working system route in accordance with changes in the network topology. Had gone. In the present invention, in addition to (1) notification of link state to other nodes, (2) calculation of working route, (3) calculation of optimum route taking into account processing of standby route suggest.
Hereinafter, embodiments of the present invention will be described by dividing them into a first embodiment and a second embodiment. In the first embodiment, distributed processing in which each node performs route calculation in accordance with a change in network topology will be described. In the second embodiment, a network control device that controls a network in accordance with a change in network topology will A centralized process for performing calculation and distributing the calculated route to each node will be described.

Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
Each figure is only schematically shown so that the present invention can be fully understood. Therefore, the present invention is not limited to the illustrated example. In addition, in each figure, about the same component or the same component, the same code | symbol is attached | subjected and those overlapping description is abbreviate | omitted.

[First Embodiment]
≪Configuration of route information update system≫
Hereinafter, the configuration of a communication network 1000 as a route information update system according to the first embodiment will be described with reference to FIG. FIG. 1 is a configuration diagram of a communication network 1000 according to the first embodiment.

  A communication network 1000 serving as a route information update system includes a plurality of nodes 100 and links connecting the nodes 100. The communication network 1000 is, for example, the Internet or an intranet.

<Node>
The configuration of the node 100 according to the first embodiment will be described with reference to FIG. FIG. 2 is a functional configuration diagram of the node 100 according to the first embodiment.
The node 100 is a relay device, for example, a router. The node 100 includes a storage unit 10, a control unit 20, and a communication unit 30. The communication unit 30 is a device that is communicably connected to another node 100 via a link. The communication unit 30 includes a plurality of interfaces 3, and each interface 3 is connected to a link for each node 100 to be connected. Hereinafter, the “interface” may be abbreviated as “I / F”.

  The control unit 20 is realized by a program execution process by a CPU (Central Processing Unit) included in the node 100, a dedicated circuit, or the like. Further, the storage unit 10 includes a storage medium such as a random access memory (RAM), a read only memory (ROM), a hard disk drive (HDD), and a flash memory. When the node 100 is realized by program execution processing, the storage unit 10 stores a route information update program for realizing the function of the node 100.

  The node 100 according to the present embodiment can be realized by a program that executes the processing as described above, and the program can be provided by being stored in a computer-readable recording medium (CD-ROM or the like). Is possible. It is also possible to provide the program through a network such as the Internet.

The storage unit 10 stores a network topology information DB 11, an active system path information DB 12, and a standby system path information DB 13.
(Network topology information DB)
Information regarding the topology of the communication network 1000 is stored in the network topology information DB 11. Specifically, information of the interface 3 of the link connected to each node 100 configuring the communication network 1000 (hereinafter, “information of interface 3” may be referred to as “link state”) is stored.

  The network topology information DB 11 is, for example, a link state database (LSD) defined by OSPF. The network topology information DB 11 may be referred to as “link state notification” by omitting a notification about a link state transmitted from each node 100 (hereinafter, “link state advertisement (LSA)”). ) Is updated based on the received link state notification.

(Active route information DB)
The working path information DB 12 stores a table that defines the correspondence between the destination node 100 of the received packet and the interface 3 that outputs the received packet. Hereinafter, the table stored in the working path information DB 12 is referred to as a working path information table, and “0” is set as the table ID in the working path information table. The working path information DB 12 is created by the working path calculation unit 24 described later based on the network topology information DB 11.

(Preliminary route information DB)
Similar to the active route information DB 12, the backup route information DB 13 stores a table that defines the correspondence between the destination node 100 of the received packet and the interface 3 that outputs the received packet. Hereinafter, the table stored in the backup path information DB 13 is referred to as a backup path information table. The standby route information table is used in place of the working route information table when a failure such as a failure occurs in the node 100 or the link constituting the communication network 1000. There are a plurality of backup path information tables corresponding to the failure locations of the communication network 1000, and numbers other than “0” are set as serial numbers in the plurality of backup path information tables as table IDs.

  The control unit 20 includes a link state transmission unit 21, a link state reception unit 22, a link state transfer unit 23, an active system route calculation unit 24, a standby system route calculation unit 25, a protocol control unit 26, and a packet transfer. And a processing unit 27. Hereinafter, the function of the control unit 20 when the topology changes due to the increase / decrease of the nodes 100 will be described.

(Link state transmitter)
The link state transmission unit 21 performs setting of the interface 3 and setting of a protocol when a link connected to the interface 3 is added or changed by increasing or decreasing the number of adjacent nodes 100. Here, the setting of the interface 3 is a state in which an electric signal can be exchanged with the adjacent node 3 via a link connected to the interface 3. The setting of the protocol means that a rule for exchanging information with an adjacent node 100 via a link is determined and exchanged. By setting the interface 3 and the protocol, the node 100 can transmit and receive information to and from the adjacent node 100 via the link. Then, after setting the interface 3 and the protocol, the link state transmission unit 21 transmits information regarding the changed interface to the adjacent node 100 as a link state notification.

(Link state receiver)
The link state receiving unit 22 receives a link state notification from the adjacent node 100, and updates the network topology information DB 11 based on the received link state notification.

(Link state transfer part)
The link state transfer unit 23 transfers the received link state notification to adjacent nodes 100 excluding the node 100 that has already received the link state notification. The timing at which the link state transfer unit 23 transfers the link state notification is controlled by the protocol control unit 26 described later.

(Current route calculation part)
The working path calculation unit 24 creates a working path information table from the network topology information DB 11 using, for example, a Dijkstra algorithm used in OSPF, and updates the working path information DB 12. The timing at which the working path calculation unit 24 creates the working path information table is controlled by a protocol control unit 26 described later.

(Preliminary route calculation unit)
For example, the protection path calculation unit 25 creates a protection path information table from the network topology information DB 11 using the IP-FRR method, and updates the protection path information DB 13. The timing at which the backup path calculation unit 25 creates the backup path information table is controlled by the protocol control unit 26 described later.

(Protocol control unit)
The protocol control unit 26 controls the order of processing of the link state transfer unit 23, the active system route calculation unit 24, and the backup system route calculation unit 25, and gives instructions to execute them. In the process of the protocol control unit 26 of the node 100 that first detects the topology change, the process performed by the link state transfer unit 23 is replaced with the process performed by the link state transmission unit 21.
There are three types of cases in which the protocol control unit 26 issues processing instructions to the link state transfer unit 23, the active system route calculation unit 24, and the standby system route calculation unit 25. In the following, with reference to FIG. 3, the order of processing defined in the conventional OSPF will be described first, and thereafter, three types of cases according to the present embodiment will be described with reference to FIGS. .

<Conventional processing (OSPF)>
A conventional processing procedure defined in OSPF will be described with reference to FIG.
When a node that operates based on OSPF receives a link state notification from another node, the node forwards the received link state notification to a further adjacent node (step S10), and then the content of the received link state notification An active route reflecting the above is calculated (step S20). Thereby, in the prior art, it was possible to send a link state notification earlier to each node in the communication network, but because the standby system path is not updated at the same timing as the update of the active system path, If a failure occurs in the communication network before the backup path is updated, there is a problem that the backup path after the topology change cannot be used.

<Case 1>
Next, the processing procedure of case 1 will be described with reference to FIG.
When the protocol control unit 26 receives a link state notification from another node, the protocol control unit 26 first issues a processing instruction to the link state transfer unit 23, whereby the link state transfer unit 23 sends the link state notification to the adjacent state. To the node 100 to be transferred (step S110). Next, the protocol control unit 26 issues a processing instruction to the active route calculating unit 24, whereby the active route calculating unit 24 calculates the active route (step S120) and stores the active route information DB 12 in the active route information DB 12. Update. Next, the protocol control unit 26 issues a processing instruction to the standby system route calculation unit 25, whereby the backup system route calculation unit 25 calculates a backup system route (step S130) and stores the backup system route information DB 13 in the standby system route information DB 13. Update.
Note that the transfer of the link state notification in step S110 and the calculation of the active route in step S120 may be performed in parallel.

  The processing procedure of case 1 is control when priority is given to transfer of the link state notification. The processing procedure of case 1 is effective when immediacy is required to transfer the link state notification to another node 100, such as a topology change due to the reduction of the node 100, for example.

<Case 2>
Next, the processing procedure of case 2 will be described with reference to FIG.
When the protocol control unit 26 receives a link state notification from another node, the protocol control unit 26 first issues a processing instruction to the standby system route calculation unit 25, whereby the standby system route calculation unit 25 Is calculated (step S210), and the backup route information DB 13 is updated. Next, the protocol control unit 26 issues a processing instruction to the link state transfer unit 23, whereby the link state transfer unit 23 transfers the link state notification to the adjacent node 100 (step S220). Next, the protocol control unit 26 issues a processing instruction to the active route calculation unit 24, whereby the active route calculation unit 24 calculates the active route (step S230) and stores the active route information DB12. Update.
Note that the transfer of the link state notification in step S220 and the calculation of the active route in step S230 may be performed in parallel.

  The processing procedure of case 2 is control when it is desired to realize stable switching of route update compared to case 1. Here, the stable switching of the route update means that in case 1, since the backup route is calculated after the calculation of the active route, only the active route is temporarily used in the transition period of the route update. It is assumed that the calculation has been completed. Further, since the route calculation is performed after the link state notification is transferred, the node 100 that is the transfer source of the link state notification may transfer the IP packet before the calculation of the standby route of the transfer destination is completed. . For this reason, there is a path that can be physically bypassed when a failure occurs in a state where the calculation of only the active path is completed without completing the calculation of the standby path in the added node 100. Regardless, there is a situation where packet transfer cannot be performed because the calculation of the backup path has not been completed. However, in Case 2, since the standby path calculation is performed prior to the transfer of the link state notification, such a problem does not occur. The processing procedure of case 2 is effective when immediacy is not required for the link state notification to the other nodes 100, for example, when the topology is changed by adding the nodes 100.

<Case 3>
Next, the processing procedure of case 3 will be described with reference to FIG.
When the protocol control unit 26 receives a link state notification from another node, the protocol control unit 26 first issues a processing instruction to the active route calculation unit 24, whereby the active route calculation unit 24 causes the active route calculation unit 24 to Is calculated (step S310), and the active route information DB12 is updated. Next, the protocol control unit 26 issues a processing instruction to the standby system route calculation unit 25, whereby the backup system route calculation unit 25 calculates a backup system route (step S320) and stores the backup system route information DB 13 in the standby system route information DB 13. Update. Next, the protocol control unit 26 issues a processing instruction to the link state transfer unit 23, whereby the link state transfer unit 23 transfers the link state notification to the adjacent node 100 (step S330).
Note that the calculation of the working path in step S310 and the calculation of the standby path in step S320 may be performed in parallel, or the order of the working path is calculated after calculating the backup path by reversing the order. Calculation may be performed.

  The processing procedure of Case 3 is control when it is desired to realize more stable switching of route update compared to Case 1 and Case 2. Here, the more stable switching of the route update means that in the case 1 and the case 2, the link state notification is transferred before or in parallel with the calculation of the active route, and therefore the active route of the link state notification transfer source is changed. Before the calculation is completed, the calculation of the working path of the transfer destination is completed, and in principle, a phenomenon occurs in which the IP packet is lost (discarded) at the transfer source when the IP packet is transferred from the transfer source to the transfer destination. there's a possibility that. However, in Case 3, since the calculation of the working path and the backup path is completed before the transfer of the link state notification, such a problem does not occur. The processing procedure of case 3 waits for the calculation of the working route and the standby route, so that the propagation of the link state notification is delayed compared to case 1 or case 2, but is effective when stable switching of route update is prioritized. is there.

  Any one of the processing procedures of the cases 1 to 3 described above may be selected, or an appropriate case may be appropriately selected from the cases 1 to 3 depending on the form in which the topology is changed. Good. For example, the processing procedure of Case 2 or Case 3 is used to change the topology when the node 100 is added, and the processing procedure of Case 1 is used to change the topology when the node 100 is removed. You may make it do. In addition, the case may be selected in consideration of a place where the node 100 is increased or decreased, or the case may be selected in consideration of a time zone (amount of IP packets) where the node 100 is increased or decreased. The case may be selected in consideration of the size of the communication network 1000.

(Packet transfer processor)
Returning to FIG. 2, the packet transfer processing unit 27 determines which route the received IP packet is transferred to, and transfers the received IP packet along the determined route. Specifically, the packet transfer processing unit 27 determines the output interface 3 (I / F) using the destination ID (for example, IP address) of the IP packet and the table ID as a key, and through the determined output interface 3 The received IP packet is transmitted. The table ID specifies whether the route is a working route or a backup route, and is described, for example, in a ToS (Type of Service) field of the IP packet.
Above, description of the structure of the node 100 is complete | finished. Also, the description of the configuration of the communication network 1000 as the route information update system ends.

≪Operation of route information update system≫
Hereinafter, with reference to FIG. 7, the processing of Case 2 regarding the operation of updating the route information when the topology changes due to the addition of the node 100 to the communication network 1000 as the route information update system according to the first embodiment. Will be described as an example. In addition, about the case where a topology changes by the reduction | decrease of the node 100, detailed description is abbreviate | omitted as using the description when a topology changes with the expansion of an installation. The detailed description of the processing procedures of Case 1 and Case 3 is also omitted by using the following description.

  FIG. 7 is a schematic diagram of the communication network 1000 according to the first embodiment. FIG. 7A shows a state where one node 100 is physically added to the communication network 1000, and FIG. 7B shows interface settings and protocol settings of the added node 100 and the adjacent node 100. 7C shows a state in which the added node 100 acquires information on the topology of the communication network 1000, and FIG. 7D shows a link transmitted from the added node 100. The state notification is transferred to another node 100.

  As shown in FIG. 7A, it is assumed that the node 100 having the node number “6” is physically added to the communication network 1000 including the nodes 100 having the node numbers “1” to “5”. Then, as shown in FIG. 7B, the nodes 100 with the node numbers “1” and “6” connect the node 100 with the node number “1” and the node 100 with the node number “6”. The interface 3 of 1-6 and the protocol between nodes are set. As a result, the node 100 with the node number “1” and the node 100 with the node number “6” are ready to transmit and receive information.

  Next, as illustrated in FIG. 7C, the added node 100 with the node number “6” is connected to the communication network 1000 stored in the network topology information DB 11 from the existing node 100 with the node number “1”. Information on the topology is received (arrow 51). Information on the network topology indicated by the arrow 51 is information on the topology of the communication network 1000 composed of the nodes 100 having the node numbers “1” to “5” before the node 100 having the node number “6” is added. It is a state to get. As a result, the node 100 with the node number “6” updates the network topology information DB 11 based on the received topology information.

  Next, the protocol control unit 26 of the node 100 with the node number “6” illustrated in FIG. 7C performs an instruction according to the flowchart of FIG. As a result, the protection path calculation unit 25 of the node 100 with the node number “6” first creates a protection path information table from the network topology information DB 11 and updates the protection path information DB 13. Next, the link state transmission unit 21 of the node 100 with the node number “6” transmits information regarding the set interface 3 to the node 100 with the node number “1” as a link state notification (in FIG. 7D). Arrow 52). Next, the working route calculation unit 24 of the node 100 with the node number “6” creates a working route information table from the network topology information DB 11 and updates the working route information DB 12.

  On the other hand, the link state receiving unit 22 with the node number “1” receives information regarding the interface 3 set from the link state transmitting unit 21 of the node 100 with the added node number “6” as a link state notification (FIG. 7 ( d), the network topology information DB 11 is updated based on the received link state notification.

  Next, the protocol control unit 26 of the node 100 with the node number “1” illustrated in FIG. 7D performs an instruction according to the flowchart of FIG. As a result, first, the protection path calculation unit 25 of the node 100 with the node number “1” creates a protection path information table from the network topology information DB 11 and updates the protection path information DB 13. Next, the link state transfer unit 23 of the node 100 with the node number “1” sends the link state notification received from the node 100 with the node number “6” to the adjacent nodes 100 with the node numbers “2” and “5”. (Arrows 53 and 54). Next, the working route calculation unit 24 of the node 100 with the node number “1” creates a working route information table from the network topology information DB 11 and updates the working route information DB 12.

  On the other hand, the link state reception unit 22 of the node 100 with the node number “2” shown in FIG. 7D receives the link state notification transferred from the link state transfer unit 23 of the node 100 with the node number “1” ( Based on the received link state notification, the network topology information DB 11 is updated.

  Then, the protocol control unit 26 of the node 100 with the node number “2” illustrated in FIG. 7D performs an instruction according to the flowchart of FIG. As a result, first, the protection path calculation unit 25 of the node 100 with the node number “2” creates a protection path information table from the network topology information DB 11 and updates the protection path information DB 13. Next, the link state transfer unit 23 of the node 100 with the node number “2” transfers the link state notification received from the node 100 with the node number “1” to the adjacent node 100 with the node number “3” ( Arrow at 55). Next, the working route calculation unit 24 of the node 100 with the node number “2” creates a working route information table from the network topology information DB 11 and updates the working route information DB 12.

On the other hand, the node 100 with the node number “5” shown in FIG. 7D performs the same processing as the node 100 with the node number “2”, and receives the link state notification received from the node 100 with the node number “1”. To the node 100 of the node number “4” to be transferred (arrow 56). Next, the node 100 with the node numbers “3” and “4” also performs route calculation based on the received link state notification.
Above, description of operation | movement of the communication network 1000 as a route information update system is complete | finished.

As described above, the communication network 1000 according to the first embodiment can update the route by optimally setting the order of the link state notification, the active route calculation, and the standby route calculation when the topology is changed.
Specifically, if the procedure of case 1 is followed, the link state notification can be transferred to another node 100 before the route is calculated, so that the link state can be transmitted to each node 100 in the communication network 1000 earlier. Notifications can be sent.
In addition, according to the procedure of case 2, the backup route is calculated prior to the transfer of the link state notification. Therefore, if the active route fails, the backup route is set as long as the physical connectivity is ensured. IP packets can be transmitted reliably.
Further, according to the procedure of case 3, the calculation of the active route and the standby route is completed before the transfer of the link state notification. Therefore, when the IP packet is transferred from the transfer source node 100 to the transfer destination node 100. The phenomenon that the IP packet is lost (discarded) at the transfer source does not occur.

[Second Embodiment]
≪Configuration of route information update system≫
Hereinafter, the configuration of the communication network 1000a as the route information update system according to the second embodiment will be described with reference to FIG. FIG. 8 is a configuration diagram of the communication network 1000a according to the second embodiment.

  A communication network 1000a as a route information update system includes a network information acquisition device 300, a control server 400, a plurality of nodes 100a, and links connecting the nodes 100a. The communication network 1000a is, for example, the Internet or an intranet.

<Network information acquisition device>
The network information acquisition device 300 is, for example, an NMS (Network Management System), acquires information including information (link state) of the interface 3 from the node 100a constituting the communication network 1000a, and uses the acquired information to the control server 400. Send to.

<Control server>
With reference to FIG. 9, the structure of the control server 400 which concerns on 2nd Embodiment is demonstrated. FIG. 9 is a functional configuration diagram of the control server 400 according to the second embodiment.
The control server 400 is a device that calculates a route of the communication network 1000a and notifies the calculated route to each node 100a. The control server 400 includes a storage unit 410, a control unit 420, and a communication unit 430. The communication unit 430 is a device such as an interface for communicatively connecting to another device.

The storage unit 410 stores a network topology information DB 11, an active system path information DB 12, and a standby system path information DB 13. These pieces of information are the same as those in the first embodiment.
The control unit 420 includes an active system route calculation unit 24, a standby system route calculation unit 25, and a route distribution unit 426. The active system route calculation unit 24 and the standby system route calculation unit 25 are the same as those in the first embodiment.

(Route Distribution Department)
The route distribution unit 426 transmits (distributes) the active route calculated by the active route calculation unit 24 and the standby route calculated by the standby route calculation unit 25 to the node 100a. The route delivery unit 426 delivers routes in the order of the active route → the backup route, so that the same effect as “Case 1” of the protocol control unit 26 of the first embodiment can be obtained. Also, the route delivery unit 426 delivers routes in the order of the standby route → the active route, so that the same effect as “Case 2” of the protocol control unit 26 of the first embodiment can be obtained.

<Node>
Unlike the node 100 according to the first embodiment, the node 100a does not perform route calculation by itself, and acquires the active route and the standby route from the control server 400.
Above, description of the structure of the communication network 1000a as a path | route information update system is complete | finished.

  As described above, the communication network 1000a according to the second embodiment can obtain the same effects as the communication network 1000 according to the first embodiment.

[Modification]
The first embodiment and the second embodiment of the present invention have been described above. However, the present invention is not limited to this, and can be implemented without changing the gist thereof. The modification of 1st Embodiment and 2nd Embodiment is shown below.

(Protocol control unit)
In the protocol control unit 26 according to the first embodiment, the processing procedure for switching the order of link state notification, active path calculation, and backup path calculation has been described. Here, in the case where the communication network 1000 has a standby path for a certain active path such as a path network, the standby path cannot be calculated unless the active path is determined. In such a case, the route calculation is performed in the order of the active route → the backup route, and the “calculation” portion in the protocol control unit 26 is read as “setting for transferring IP packet”.

(Control server)
In the control server 400 in the second embodiment, the information (link state) of the interface 3 is received from the network information acquisition device 300. However, the control server 400 includes the function (link state collection unit) of the network information acquisition device 300. Thus, the control server 400 may directly receive the link state from the node 100a.

3 Interface 10 Storage unit 11 Network topology information DB
12 Active route information DB
13 Backup route information DB
DESCRIPTION OF SYMBOLS 20 Control part 21 Link state transmission part 22 Link state reception part 23 Link state transfer part 24 Active system route calculation part 25 Backup system path calculation part 26 Protocol control part 27 Packet transfer process part 30 Communication part 100,100a Node 300 Network information acquisition Device (link state collection unit)
400 Control server (route control device)
410 storage unit 420 control unit 430 communication unit 426 route distribution unit 1000, 1000a communication network (route information update system)

Claims (8)

A route information update system for updating a route of a packet flowing in a network configured by connecting a plurality of nodes by a link,
Each node
A network topology information DB in which a link state that is information of an interface of the link connected to each node belonging to the network is stored;
A link state transmitter that transmits the link state as a link state notification to another adjacent node when the connected link is changed;
A link state receiving unit that updates the network topology information DB based on the received link state notification when the link state notification is received;
When the network topology information DB is updated,
A link state transfer unit that further transfers the received link state notification to another adjacent node;
Based on the network topology information DB, an active path calculation unit that calculates an active path,
Based on the network topology information DB, a standby path calculation unit that calculates a backup path to be used when the working path cannot be used;
A protocol control unit that controls the order of processing of the link state transfer unit, the working path calculation unit, and the backup path calculation unit;
The protocol control unit
After the processing of the link state transfer unit and the active system route calculation unit, the processing of the backup system route calculation unit is performed,
A route information update system characterized by that. The protocol control unit
After the processing of the link state transfer unit and the working path calculation unit is completed, instead of causing the backup path calculation unit to perform processing,
After the processing of the standby system route calculation unit is completed, the link state transfer unit and the active system route calculation unit are processed.
The route information update system according to claim 1, wherein: The protocol control unit
After the processing of the link state transfer unit and the working path calculation unit is completed, instead of causing the backup path calculation unit to perform processing,
After the processing of the working path calculation unit and the backup path calculation unit is completed, the link state transfer unit is processed.
The route information update system according to claim 1, wherein: A route information update system composed of a network configured by connecting a plurality of nodes by links, and a route control device that calculates a route of a packet flowing through the network,
The route control device
A network topology information DB in which a link state that is information of an interface of the link connected to each node belonging to the network is stored;
A link state collection unit that collects the link state from the node when the link connected to the node is changed, and updates the network topology information DB based on the collected link state;
When the network topology information DB is updated,
Based on the network topology information DB, an active path calculation unit that calculates an active path of each of the nodes;
Based on the network topology information DB, a standby path calculation unit that calculates a standby path for each of the nodes to be used when the working path cannot be used;
A route distribution unit that distributes the active route calculated by the active route calculation unit to each node after distributing the standby route calculated by the standby route calculation unit to the node; Comprising
A route information update system characterized by that. A route information update method of a route information update system for updating a route of a packet flowing in a network configured by connecting a plurality of nodes by links,
Each node
A network topology information DB in which a link state that is information of an interface of the link connected to each node belonging to the network is stored;
A link state transmission step of transmitting the link state as a link state notification to another adjacent node when the connected link is changed;
A link state reception step of updating the network topology information DB based on the received link state notification when the link state notification is received;
When the network topology information DB is updated,
A link state transfer step of further transferring the received link state notification to the other adjacent nodes;
An active route calculation step for calculating an active route based on the network topology information DB;
Based on the network topology information DB, a backup path calculation step for calculating a backup path to be used when the working path cannot be used is executed.
The processing procedure is as follows:
After the processing of the link state transfer step and the active system route calculation step, the processing of the backup system route calculation step is executed.
A route information update method characterized by the above. The processing procedure is as follows:
After the processing of the link state transfer step and the active system route calculation step is completed, instead of executing the processing of the backup system route calculation step,
After the processing of the backup system path calculation step is completed, execute the processing of the link state transfer step and the active system path calculation step.
The route information update method according to claim 5, wherein: The processing procedure is as follows:
After the processing of the link state transfer step and the active system route calculation step is completed, instead of executing the processing of the backup system route calculation step,
After the processing of the active system route calculation step and the backup system route calculation step, the processing of the link state transfer step is executed.
The route information update method according to claim 5, wherein: A route information update method of a route information update system comprising a network configured by connecting a plurality of nodes by links and a route control device for calculating a route of a packet flowing through the network,
The route control device
A network topology information DB in which a link state that is information of an interface of the link connected to each node belonging to the network is stored;
A link state collection step of collecting the link state from the node when the link connected to the node is changed, and updating the network topology information DB based on the collected link state;
When the network topology information DB is updated,
Based on the network topology information DB, an active path calculation step for calculating an active path for each of the nodes;
Based on the network topology information DB, a standby path calculation step for calculating a standby path for each of the nodes to be used when the working path cannot be used;
A route distribution step of distributing the active route calculated in the active route calculation step to each node after distributing the standby route calculated in the standby route calculation step to the node; Run the
A route information update method characterized by the above.

Images