JP2011066536A - Route control device - Google Patents

Abstract

Provided is a path control device capable of configuring a network that is appropriately bypassed when a node or link fails using a relatively small number of routing tables.
When a node u1 receives an IP packet of a destination d when a node u5 is out of order, the IP packet is transferred through a route of u1->u2->u3->u4->w1->w2-> d. In particular, the rerouting route (u1 →) using the second routing table is rewritten by rewriting the state in which the u2 with the i label, u3 with the o label added, and u4 with the s label added are included in the IP packet. After passing through u2 → u3), the first route table is used to enter the tunnel through the shortest path (u3 → u4), and after leaving the tunnel, the second route table is used (u4 → w1), and then the first The route is such that the route table is used (w1 → w2 → d).
[Selection] Figure 8

Description

  The present invention relates to a path control device that sets a detour when an abnormal state such as a failure occurs on a network path.

  Conventionally, a route control device such as a router has a routing table indicating a correspondence between a destination on the network and a next transfer destination to reach this destination. The next transfer destination is determined by comparing with the routing table. Since a failure or the like may occur on the route to the next transfer destination router and transfer cannot be performed, a technique for preparing a spare route table in advance is known.

There are two types of failure on the route. A link failure and a node failure.
Then, even if any one link on the route to the destination fails, setting an appropriate detour for the failure of the link is called “link protection”. Moreover, even if any one node fails, setting an appropriate detour for the failure of the node is referred to as “node protection”.

As one measure for realizing the link protection and the node protection, a technique for increasing the number of route tables is known (see Non-Patent Documents 1 to 5). For example, Non-Patent Document 1 attempts to realize link protection by preparing a route table for each interface (port) of each node.
Non-Patent Document 2 proposes a route table calculation method that realizes link protection using a similar method.

In Non-Patent Document 4, several routing tables are required to guarantee link protection and node protection, and generally three to five additional tables are required, depending on the size of the network. It is said.
Further, in Non-Patent Document 5, the number of additional tables necessary for dealing with various failures is two to three, which is smaller than that in Non-Patent Document 4, but in a general case, There is no disclosure as to whether one route table is required.

On the other hand, if the routing table is increased unnecessarily, the processing load on each node may increase. For this reason, Non-Patent Document 6 attempts to set an appropriate detour while avoiding an increase in the number of routing tables by using the state embedded in the packet header as a detour.
The technique disclosed in Non-Patent Document 6 will be described. As shown in FIG. 14, the network 100 includes nodes u1 to u5, w1, w2, and d.

Each node includes a destination node d and a route table indicating a next transfer destination node (next hop) to reach the node d, that is, a normal first route table (1st) and a spare second route. A table (2nd) is provided. In FIG. 14, the routes to the next hop in the first route table and the second route table are indicated by arrows “first route”, “second route”, and arrows, respectively.
Here, the network rules in FIG. 14 are as follows.

(Rule 1) A state label indicating which of the first and second route tables should be used is added to the IP packet, and state 0 should use the first route table and state 1 should use the second route table. It shows that.
(Rule 2) A node that cannot transfer an IP packet, for example, by detecting a link failure leading to the next hop in the first routing table changes the IP packet from the default state 0 to the state 1, and the second route Forward to next hop in table.

(Rule 3) The node associated with the s flag changes the state from state 1 to state 0 when it receives the state 1 IP packet. The node after this node uses the first routing table due to the change to the state 0.
Non-Patent Document 6 introduces a mechanism for further changing the state in order to prevent IP packet loops, but the description thereof is omitted because it is not closely related to this discussion.

  A specific operation example under this rule will be described. For example, when the node u1 receives the IP packet of the destination d and does not detect a link failure, the node u1 moves to the next hop u5 in the first routing table. The IP packet is transferred, and the node u5 is also transferred to the next hop d in the first route table of the node u5. That is, the IP packet is transferred as u1 → u5 → d.

Further, as shown in FIG. 15, when the node u1 receives the IP packet of the destination d and detects a link failure between u5 and d, the flow of u1 → u5 → u4 → w1 → w2 → d become.
That is,
(1) Node u1: Transfers an IP packet to the next hop u5 in the first routing table. (2) Node u5: Since a link failure is detected between u5-d, the state of the IP packet is changed from state 0 to state 1. Change and forward the IP packet not to the first routing table but to the next hop u4 of the second routing table. (3) Node u4: Since the state of the IP packet is in the state 1, to the next hop w1 of the second routing table Forward IP packets. However, since the s flag is associated, the state is changed from the state 1 to the state 0 before the transfer. (4) Node w1: Since the state of the IP packet is the state 0, the next hop w2 in the first routing table (5) Node w2: Since the state of the IP packet is in state 0, the IP packet is transferred to the next hop d in the first routing table.

  As described above, according to Non-Patent Document 6, even if any one link existing on the route to the destination node fails, an appropriate detour can be set for the failure of the link (link protection). In addition, since a route table calculated in advance is used, a detour can be set instantaneously after a failure is detected.

S. Lee, Y. Yu, S. Nelakuditi, Z.L.Zhang, and C-N. Chuah, "Proactive vs. Reactive Approaches to Failure Resilient Routing," In Proceings of IEEE INFOCOM '04, Mar. 2004. Z. Zhong, S. Nelakuditi, Y. Yu, S. Lee, J. Wang, and C.N. Chuah, "Failure Inferencing Based Fast Rerouting for Handling Transient Link and Node Failures," In Proceings of IEEE Global Internet, Mar. 2005. J. Wang and S. Nelakuditi, "IP Fast Reroute with Failure Inferencing," In Proceedings of SIGCOMM workshop (INM) 2007, pp.268-273, 2007. A. Kvalbein, AF Hansen, T. Cicic, S. Gjessing, and O. Lysne, "Multiple routing configurations for fast IP network recovery," IEEE / ACM Transactions on Networking, Vol.17, Issue.2, pp.473- 486, 2009. T. Cicic, A.F. Hansen, A. Kvalbein, M, Hartmann, R. Martin and M. Menth, "Relaxed multiple routing configurations for IP fast reroute," In Proceings of NOMS2008, pp.457-464, 2008. Takuya Yoshihiro, "A Single Backup-Table Rerouting Scheme for Fast Failure Protection in OSPF", IEICE Transactions on Communications, Vol. E91-B, No. 9, pp. 2838-2847, 2008.9. (IEICE / IEEE Joint Special Section on (Autonomous Decentralized Systems Theories and Application Deployments)

By the way, in the network technology, the link protection is also important, but the node failure occurrence rate is too high to be ignored. For this reason, realizing node protection has become an important issue.
However, the technique of Non-Patent Document 6 described above may not function effectively for this node protection.

  Specifically, as shown in FIG. 16, in the network 102, when the node u1 receives an IP packet whose destination is d and the node u5 is out of order, the IP packet is u1 → u2 → u3 → Since it is transferred as u4 → w1 → w2 → d, it can be bypassed. However, the node u3 has the same u4 as the next hop in the first route table and the next hop in the second route table. Therefore, when the node u3 receives the IP packet of the destination d and detects a link failure with the u4, the node u3 cannot determine the next appropriate transfer destination and cannot bypass (see FIG. 17). ), Resulting in IP packet loss.

To deal with this, it may be possible to respond by increasing the number of routing tables, such as preparing routing tables according to link failures, node failures, etc. I want to avoid this because it causes an increase in processing load.
The present invention has been made under such circumstances, and it is intended to provide a path control device capable of configuring a network that appropriately bypasses when a node or link fails using a relatively small number of routing tables. Objective.

  A routing control device according to the present invention is a node that constitutes a network, and controls a forwarding destination of a packet, and receives a packet storing information indicating a destination and a state relating to determination of the forwarding destination. The first route table in which the receiving unit, the destination node, and the first node existing on the first route to the destination node are associated with each other, the destination node, and the second route to the destination node. A second routing table that associates the second node with each other, a storage unit that stores, for each destination node, label information that represents the rewrite contents stored in the packet, and received by the receiving unit If the state indicated in the information stored in the packet is the state 0 and transfer to the first node is possible, the packet is transferred to the first node, and the state is 0, and the first node Transfer to If not possible, transfer the packet to the second node, and if the label information indicates the addition of the first label, rewrite from the state 0 to the state 3 before the transfer, and add the first label Is not rewritten from state 0 to state 1 before transfer, and if it is state 1, the packet is transferred to the second node, and the label information indicates the addition of the second label. For example, the state is rewritten from state 1 to state 2 before transfer, and if the addition of the first label is not indicated but the addition of the first label is indicated, the state is rewritten from state 1 to state 3 before the transfer. For example, if the packet is transferred to the first node and the label information indicates the addition of the third label, the state 2 is rewritten from the state 2 to the state 1 before the transfer. The packet to the first node Characterized in that it comprises a transfer control unit for transferring the door, the.

  The path control device according to the present invention is a node that constitutes a network, and is a route control device that controls a packet transfer destination, and stores a destination and information indicating a state related to determination of the transfer destination. When the encapsulated packet addressed to the own node is received, the packet after the decapsulation is handled as a received packet, the destination node, and the first route to the destination node. For each destination node, a first route table in which the first node is associated, a destination node, a second route table in which the second node existing on the second route to the destination node is associated, and for each destination node, The storage unit that stores label information that represents the rewriting contents of the state stored in the packet, and the state indicated in the information stored in the packet received by the reception unit is state 0 If the transfer to the first node is possible, the packet is transferred to the first node. If the packet is in state 0, and the transfer to the first node is not possible, the packet is sent to the second node. If the label information corresponding to the destination of the packet indicates the addition of the first label, the state is rewritten from the state 0 to the state 3 before the transfer. If the label information does not indicate the addition of the first label, the transfer is performed. If the state is changed from state 0 to state 1 and is in state 1, the packet is transferred to the second node, and the label information corresponding to the destination of the packet indicates the addition of the second label. Rewrite from state 1 to state 2 before transfer, if the addition of the second label is not indicated but the addition of the first label is indicated, rewrite from state 1 to state 3 before transfer and if state 2 Received packets The state is rewritten from the state 2 to the state 1, and the state of the packet is set to the node that is the first node when the label information corresponding to the destination of the packet indicates the addition of the third label. A transfer control unit that encapsulates the packet to be included in 0, transfers the encapsulated packet to the first node, and transfers the packet to the first node if in state 3; It is characterized by providing.

A path control device according to the present invention is a node that constitutes a network and controls a transfer destination of a packet, and stores a packet that stores information indicating a destination and a state related to determination of the transfer destination. , A first route table in which a destination node and a first node existing on the first route to the destination node are associated, a destination node, and a second route to the destination node A storage unit that stores a second routing table that associates the second node existing in the network with each other, and label information that represents the rewrite contents stored in the packet for each destination node, and is received by the receiving unit If the state indicated in the information stored in the received packet is state 0 and transfer to the first node is possible, the packet is transferred to the first node, state 0 is To 1 node If the transfer is not possible, the packet is transferred to the second node. If the label information corresponding to the destination of the packet indicates the addition of the first label, the state is changed from the state 0 to the state 3 before the transfer. If it does not indicate the addition of the first label, it is rewritten from state 0 to state 1 before transfer, and if it is state 1, the packet is transferred to the second node, and is sent to the destination of the packet. If the corresponding label information indicates the addition of the second label, it is rewritten from the state 1 to the state 2 before the transfer, and if the second label is not indicated but the addition of the first label is indicated, the transfer is performed before the transfer. If state 1 is rewritten from state 1 and state 2 is received, the state of the received packet is rewritten from state 2 to state 1 so that the received packet is routed to the route corresponding to the first route table. To be After adding another to MPLS labels, and the MPLS label by transfers to node identified, if the state 3, the transfer control unit that transfers the packet to the first node,
It is characterized by having.

  The method in the routing control system according to the present invention is a method in a routing control system including a plurality of nodes constituting a network, and each node has a first route to a destination node and the destination node. A storage step for storing the second route, which is a different detour from the first route, and if the transfer of the packet using the first route is not possible at each node, indicates that the packet is being detoured A detour start step of transferring a packet using the second route after adding the information, and each node receiving a packet with information indicating that the detour is in progress, the packet is transmitted using the second route. The local node in spite of having received a packet with a detour step to transfer and a packet with information indicating that it is detouring at each node. If the predetermined condition relating to the route to reach the destination node is satisfied, the detouring tunnel step of forwarding the packet using the first route table instead of the second route used in the detouring step; It is characterized by providing.

  According to the route control device of the present invention, by rewriting the state from the state 0 to the state 4 with the first to third labels, it is possible to determine which of the first route table and the second route table is used as the transfer destination. It can be determined flexibly, and a detour can be appropriately set when a node or link fails.

Diagram showing network overview Functional block diagram of node u2 The figure which shows the definition of the variable which relates to algorithm “CreateBackupTable-NP” Diagram showing the algorithm "CreateBackupTable-NP" Diagram showing procedure "findBackupPath" Diagram showing procedure "setBackupNextHops" Flowchart showing the flow of processing related to IP packet reception The figure which shows the 1st and 2nd routing table in each node, and also true / false of each label Sequence diagram showing the flow of processing in each node when node u5 fails The figure which shows the network configuration etc. which concern on a modification The figure which shows the network configuration etc. concerning the modification which utilizes encapsulation The figure which shows the network structure etc. which concern on the modification using MPLS. (A) The figure which shows the content of the header part of an IP packet, (b) The flowchart regarding the change to detouring (state 3) The figure which shows the network structure which followed the nonpatent literature 6 The figure which shows the link failure between u5-d in the network of FIG. The figure which shows a network configuration when trying to perform node protection in nonpatent literature 6 The figure which shows the link failure between u3-u4 in the network of FIG.

Hereinafter, embodiments will be described with reference to the drawings.
<Configuration>
As shown in FIG. 1, the network 1 includes eight nodes u1 to u5, w1, w2, and d. Each node includes a router, and performs communication according to the IP protocol in the network layer. Each node is assumed to operate according to an OSPF (Open Shortest Path First) routing protocol.

The header portion of the IP packet flowing through the network includes a destination IP address and a TOS (Type Of Service) field, and this TOS stores the state (there are four types from state 0 to state 3). Used as a region.
FIG. 2 shows a functional block diagram of the node u2. Since each node has basically the same configuration, only node u2 will be described as a representative.

The node u2 includes an interface unit 10, a topology unit 12, a reception unit 14, a transfer unit 16, a transfer destination determination unit 18, a failure detection unit 20, a state control unit 22, a control unit 24 that controls each unit, a calculation unit 30, and a storage unit. 40.
The interface unit 10 includes a line interface (port) for connecting to another node, and realizes data exchange with the other node.

The topology unit 12 transmits topology information called LSA (Link State Advertisement) including the ID of the node (adjacent node) connected to the node and the cost of the interface to other nodes. A topology map is created based on topology information collected from other nodes.
The receiving unit 14 receives an IP packet or the like via the interface unit 10.

The transfer unit 16 transfers an IP packet or the like to the transfer destination determined by the transfer destination determination unit 18 via the interface unit 10.
The failure detection unit 20 detects a failure in an adjacent node by using a message or the like periodically exchanged with the adjacent node.
The state control unit 22 reads and rewrites the state included in the TOS (Type Of Service) field in the header portion of the IP packet received by the receiving unit 14. This rewriting is performed based on the presence / absence of failure detection by the failure detection unit 20 and the label table 46 in the storage unit 40.

The state includes “state 0” indicating that the shortest path is being transferred, “state 1” indicating that the detour is being transferred, “state 2” indicating that the tunnel is being transferred, and after the detour There are four types of "state 3" indicating The function and rewrite condition of each state will be described later.
The calculation unit 30 includes a first route table calculation unit 32, a second route table calculation unit 34, and a label calculation unit 36. The algorithm of the calculation unit 30 will be described later. The calculation results of the calculation unit 30 are set and stored in the storage unit 40 as a first route table 42, a second route table 44, and a label table 46.

  The first routing table 42 is a normal (primary) routing table in which a “destination” 42 a indicating a destination node is associated with a “next hop” 42 b for reaching the destination node. In FIG. 2, “destination” describes only the node d, and other destinations (nodes u1, u3, u4, u5, w1, w2) are omitted. The second route table 44 is a backup (backup) route table, and as in the first route table 42, the “destination” 44a indicating the destination node and the “next hop” 44b for reaching the destination node are associated with each other. It is a table.

The label table 46 is a table indicating true / false for each label of “destination” 46a and three labels “s” 46b, “i” 46c, and “o” 46d. The example of the label table 46 in FIG. 2 indicates that the i-label is true and the s-label and the o-label are false for the destination node d.
<Algorithm>
Next, an algorithm for determining the processing contents of the calculation unit 30 will be described.

First, the first route table 42 is calculated by a method generally used in OSPF. That is, the next hop to reach the destination node is determined by obtaining the shortest path using Dijkstra's shortest path calculation algorithm based on the topology map created in the topology unit 12.
Next, an algorithm for obtaining the second route table 44 and the label table 46 will be described below.

First, the definition of variables will be described with reference to FIG. G (V, E) is a directed graph representing a network. V is a set of nodes, and E is a set of directed links. The function f: e (εE) → R represents the weight of each link. p _d (v) represents the next hop to the destination d in the first route table of the node v, and b _d [v] represents the next hop to the destination d in the second route table of the node v. The shortest path tree to the destination d represented by p _d (v) is called a transfer tree T _d . In T _d, v the parent node of (∈ V) and p (v), v a set of descendent nodes (∈ V) expressed as _D d (v). A set of child nodes of v (∈V) is represented as C _d (v). Further, with respect to _{T d,} representing a subtree derived node v the (∈ V) as the root and _T ^{d v.}

The s-label, i-label, and o-label for the destination d of the node v are represented as s _d [v], i _d [v], and o _d [v]. Similarly, a t-label for the destination d of the node v is defined and expressed as t _d [v]. The t-label is a node that forms a tunnel with the shortest path in the detour, that is, a node between the i-label and the o-label (exactly, included from the node next to the i-label node to the o-label node). This is a label that is temporarily set to a node that includes both ends.

In addition, nodes whose labels are true are called s-label nodes, i-label nodes, o-label nodes, and t-label nodes, respectively.
In the method of this algorithm, the route from when the IP packet is transferred to the next hop of the second routing table at the node uεV and then to the post-detour state (state 3) is defined as the “detour” of u. .

That is, if p _d (v _k ) = v _{k + 1} for each node on the detour p = (u (= v ₁ ), v ₂ ,..., V _n ) and 1 ≦ k <n. , V _k must be t-label nodes, and if t _d [v _k ] = false and t _d [v _{k + 1} ] = true, then v _k is an i-label node, t _d [v _k ] = true If t _d [v _{k + 1} ] = false, v _k must be an o-label node, and v _n−1 must be an s-label node.

When dealing with a node failure, the detour p of v needs to be able to transfer IP packets up to d without passing through p (v). For this purpose, it is only necessary that the node w outside T _d ^{p (v)} at the end node of ^p does not belong to D _d (p (v)). For v∈V, T _d ^{p (v)} is called an “NP avoidance region”, and a detour p having a start point v and an end point w outside the T _d ^{p (v)} is defined as “ It is called “NP detour”.

On the other hand, when dealing with a link failure, the detour p of v needs to be able to transfer IP packets up to d without passing through the link (v, p (v)). For this purpose, end node w of p may if external T _d ^v. Therefore, for vεV, T _d ^{v is referred} to as “LP avoidance region”, and the detour p whose start point is v and whose end point is w (a node outside T _d ^v ) is the “LP detour” of v Call it.

  For the detour p, a maximal partial path qεp composed only of t-label nodes is called a “tunnel section” of p. Conversely, for a t-label node v, there is only one detour p set when the t-label is added to that node, and one of the tunnel sections of p including v Is called the tunnel section. For the t-label node v, the route of v is traced in the direction opposite to p, and the route to reach the node that is not the t-label node is called “v reverse flow route”. A detour route in which a packet is transferred from the t-label node v to the shortest path tunnel (that is, a detour route in which a packet in “state 2” is transferred from v) is referred to as a “tunnel detour” of v. In addition, a route connecting these routes p and q is expressed as p + q.

The algorithm “CreateBackupTable-NP” for obtaining the second routing table will be described with reference to FIGS. 5 and 6 show procedures used in the algorithm of FIG.
Since this algorithm operates for each destination d, the destination d and one shortest path tree T _d to the destination _d are taken as inputs. For this reason, in each node u, an algorithm is executed for each of d where u is dεV- {u}, and the entries of the second routing table relating to the output destination d and the labels of s, i, o From u (own node) is extracted and used for IP packet transfer.

In the algorithm shown in FIG. 4, initialization processing on the first to eighth lines is performed. Then, the node v is visited in the order of breadth-first search of _Td (line 9), and for each child node of v, if the second route table is not set, an NP detour is searched (line 10-12). If found, this is set (lines 13-15). Thereafter, for each child node of v, if the second routing table is not set, the LP detour is searched (line 18-20), and if found, this is set (line 21-23). . The reason for searching and setting the detours in this order is to ensure that the root nodes of the avoidance area of the detour to be searched are in the order close to the root of _Td . By this procedure, the second route table for the destination d and the labels of s, i, o are calculated.

  “FindBackupPath” (search for a detour) used in the 12th and 20th lines of this algorithm is performed by the procedure “findBackupPath” shown in FIG. 5 for both the LP detour and the NP detour. This procedure “findBackupPath” takes as input the start node u of the detour, the destination node d, and the root node r of the avoidance area. When searching for an NP detour, the root p (u) of the NP avoidance area is input as r, and when searching for an LP detour, u is used.

The procedure “findBackupPath” in FIG. 5 basically searches for a detour by repeatedly executing Dijkstra's shortest path calculation algorithm with a slight change. As a framework of the operation, a graph is created by removing nodes (or links) to be bypassed from G, and then Dijkstra's algorithm is executed with u as the starting point, and it bypasses to the tunnel section of each node v extracted from Q Node w ∈ S ₁ ∪S ₂ ∪S _{3 which} is the end point of the road (S ₁ is a set of nodes outside the avoidance area, and S ₂ is a second route table not defined among nodes not included in S ₁ When a node set, S ₃ is a set of t-label nodes not included in S ₁ ∪S ₂ ), a path that connects a path from u to v and a path along T _d from v to w Is returned as a detour p. (Accurately, p is a partial path of the detour, but for convenience, it will be referred to as a detour.) At this time, the link (x, w) that ends with the node w belonging to S ₁ ∪S ₂ ∪S ₃ ) Is used as the weight of f (x, w) plus the distance to reach d after reaching the w through the detour. That is, in the case of w∈S ₁ , the distance of the shortest path from w to d is added, and in the case of w∈S ₂ , when the detour is taken from w (that is, the second path in “state 1”) The distance from w to d) (if forwarded using the table), and if w∈S ₃ then if w tunnel section included the root r of the avoidance region, it passed the back flow path of w The distance from w to d in the case is added, and when r is not included, the distance from w to d when passing through the tunnel path of w is added. By doing this, it is possible to search for vεS ₁ ∪S ₂ ∪S ₃ that can reach the destination d in the shortest possible time.

The exception processing, to discover the nodes w which belongs to S _3, when w of tunnel section comprises a root r avoidance region returns a different path from the above by p. In other words, a path obtained by connecting three paths, a path from u to v, a path along _Td from v to w, and a backflow path of w is returned as p. As described above, this procedure returns the detour p to be set. By setting the second route table and the labels of s, i, and o based on this detour, a detour from u to d can be set.

This procedure “findBackupPath” will be described with reference to FIG. 5. Variables are initialized on the 1st to 27th lines. In the first to fifth lines, a graph G ′ = (V ′, E ′) for calculating a detour is generated. In the case of u = r, the LP bypass is searched, so that G ′ is obtained by removing the link (r, p (r)) from G in the second line. Otherwise, an NP detour is searched, so that G ′ is obtained by removing node r from G in the fourth line. The 6th to 8th lines initialize the node sets S ₁ , S _2, and S ₃ that are the end points of the detour when searching for the detour. In lines 9-25, the values of dist _u [v] and bdist _u [v] are initialized for each node vεV ′. Each is a variable temporarily used in the procedure, the distance from u to v, respectively, and the distance from v to d when passing through the detour via u to v (described above) to d Represents. 13-15 line to the node V∈S ₁ belonging to the _{S 1,} 16-18 row to the node V∈S ₂ belongs to _{S 2,} also 19-25 line nodes belonging to _{S 3} The value of bdist _u [v] is given for vεS ₃ respectively. The 26th line puts u into the set Q (node set used for executing the Dijkstra algorithm) as the start point of the Dijkstra algorithm, and the 27th line initializes the distance of u to 0.

The 28th and subsequent lines are loops for finding a detour. In the 29th to 30th lines, the node v having the minimum distance is extracted from Q. In the 31st to 32nd lines, w∈S ₁ ∪S on the path from u to v on T _d (including u and v). If w such that ₂ ∪S ₃ is included, the one closest to v is set as w. In lines 33-35, in the case of w∈S ₁ ∪S ₂ , the aforementioned detour p (that is, the discovered route from u to v and the route along T _d from v to w) are connected. the return and returns detour p corresponding to the case of W∈S ₃ is 36-42 line. The 44th to 52nd lines are a part for operating Dijkstra's algorithm. As described above, the link (v, w) is operated by adding the weight represented by bdist _d [w]. The second condition on the 48th line is a part that does not exist in Dijkstra's algorithm. This is to select a detour that is as close as possible to _Td when there are multiple equidistant detours. It is a condition. If no detour is found until the end, null is returned (line 54).

Next, “setBackupNextHops” (setting of the next hop) called in the 14th and 22nd lines (FIG. 4) of this algorithm will be described. The procedure “setBackupNextHops” shown in FIG. 6 sets the detour p found by “findBackupPath” or the like as the second path table and s, i, o, t-label, and the IP packet from the starting point u of p to the destination d. Process to be able to transfer. This procedure takes as input the destination node d, the detour p = (u ₁ , u ₂ ,..., U _n ) to be set, and the root node r of the avoidance area. In the first line, a loop is made so as to set the second route table in order from the end of the detour, and the entry and label of the second route table are set. Lines 8-14 are processing when k <n−1, that is, uk _{+ 1} is not a terminal node of p, and lines 15-23 are processing when uk _{+ 1} is a terminal node of p, 2-7 The line performs processing common to both cases. In lines 2-7, t-label addition and setting of the second routing table are performed as processing common to both cases. 2-4 line indicates the processing when the entry of the first routing table entry and the second routing table of u _k are equal (i.e., when the IP packet passes through the tunnel), added t- label in the third row Then, the previous hop for tracing the detour in the reverse direction (that is, indicating the reverse flow path) is stored in ph _d ^t . In other cases, the second routing table is set in the sixth line. Thereafter, i, o, and s-labels are set. 9-10 line, different second routing table entry as the first in _{u k,} and when the same in _{u k + 1,} by adding i- label to _{u k,} the first routing table from _{u k + 1} Set to forward IP packets using a tunnel. 11-12 row, first and second routing table entry in _{u k} is the same, and if different in _{u k + 1,} IP packet by adding o- label _{u k} is the process to escape from the tunnel To do. Lines 16-17 add an s-label when the end of p is outside the avoidance area. Lines 18-19 show that the end of p is a t-label node (the end node is always a t-label node if the second routing table is not set), and before entering the tunnel from here, I-label is added to the node. The 20th to 21st lines add an o-label to the previous node when transferring through a tunnel at the end of p to another detour.

The above is the algorithm for obtaining the second routing table and each label, and for every p found, the second routing table and each label can be set so that the IP packet passes through p.
<Theoretical results on the algorithm>
The algorithm guarantees that for every bi-directional network, a second routing table and three labels (s, i, o-labels) that can handle any one node failure can be calculated. More precisely, for any node v, if v NP detours exist, one of them can be set, and if there is no NP detour, v LP detours exist. Then it is guaranteed that one of them can be set. In other words, considering that a node failure can be bypassed and a link failure can also be bypassed, this algorithm can cope with all one-node failures and one link failures that can be bypassed.

I prove this from this. First, the following definitions and lemmas necessary for proof are shown.
Definition 1: Any two nodes v and wεp are selected for the path p. If v is located upstream of w on p and w is an ancestor of v on _Td , the partial path of p with v as the start point and w as the end point is called a slope section. When all the slope sections on p are on _Td , p is called an appropriate path.

Lemma 1: Let q be a detour of node u and p be one of the partial paths of q starting from u. If p is an appropriate path, every t-label node v on p has an NP detour, which is the backflow path of v.
Proof: If p has no slope interval, the lemma is satisfied. Therefore, it is assumed that there is a slope section on p, the start point is v, and the end point is w (this slope section is hereinafter referred to as [v, w]). Let x be the node immediately before w on p, and v ′ be the node immediately before v on p. Since p is an appropriate route, all nodes on the slope section are t-label nodes. That is, when p is set, the second route table of these nodes is not set, and a reverse flow route can be set as a detour. If v ′ is a descendant of w on _Td , the interval [v ′, w] on p is again a slope interval, and the same discussion as above is possible. Since u is clearly not a descendant of w, it is always possible to discover v ′ that is not a descendant of w by expanding the slope section in this way. If v ′ is not a descendant of w, v ′ is outside T _d ^{w and} is outside the NP avoidance region for all nodes in the interval [v ′, x]. Therefore, for all the nodes in the section [v ′, x], the reverse flow path is an NP detour. (End of proof)
Lemma 1 indicates that if the detour p to be set is an appropriate route, all nodes on p (except the start node if p is an LP detour) can have an NP detour. . Actually, the algorithm CreateBackupTables-NP always calculates and sets an appropriate route as a detour, thereby guaranteeing a detour for all nodes (although only when a detour exists). This is shown by the following lemma and theorem.

Lemma 2: The procedure findBackupPath always returns an appropriate path.
Proof: In the procedure findBackupPath, Dijkstra's shortest path calculation algorithm operates with u as the starting point, and the path returned by the procedure can in principle be divided into two parts. In other words, it divides the path p from u calculated by Dijkstra's algorithm to v, v from _{w (∈S 1 ∪S 2 ∪S 3} ) path q along the _{T d} to. (There is an exception, but this will be described later. Also, there may be a case where v = w.) Here, a weight bdist _d [] different from the link weight generally used in the Dijkstra algorithm is added. Nevertheless, p is the shortest path under the weighting function f from u to v. This is because bdist _d [] is added only to the link connected to the terminal node on p, and the same value is added to all links connected to the same terminal node. Further, the 29th and 48th lines of the procedure findBackupPath implement a mechanism in which a path along _Td is preferentially selected when there are a plurality of equidistant paths. Therefore, p is an appropriate route, and a route p + q obtained by adding the shortest route q along _Td is also an appropriate route. (End of proof)
By the way, as an exception to the above, findBackupPath may return a path in which a backflow path of w is connected to p + q. In this case, all the nodes on the backflow path (excluding the terminal) are t-label nodes, and the algorithm finds a node w that is w∈S ₁ ∪S ₂ ∪S ₃ in the ancestor of the node v extracted from Q Since it ends immediately, no node other than v on p has a node on the backflow path in its ancestor (on _Td ). Therefore, a route obtained by connecting a backflow route to p + q is also an appropriate route.

  Theorem 1: The algorithm CreateBackupTable-NP can calculate a second routing table and a label that satisfy the following condition for an arbitrary node pair (s, d). Condition: If there is an NP detour from s to the destination d, s can use an appropriate route as a detour. If there is no NP detour and there is an LP detour, s can use what is an appropriate route as a detour.

Proof: The algorithm CreateBackupTable-NP repeatedly visits the node v in the order of breadth-first search of _Td , and repeatedly calculates and sets the detour of the child node u. In each iterative process of detour calculation, it is proved by mathematical induction that all nodes for which the second path table is set have detours that satisfy the theorem, and that the detour is always an appropriate path. .
Consider first a node u for which a detour is calculated. Let r be the root node of the avoidance area at this time. Since the first time no node included in S ₂ ∪S _3, if detour to reach outside the avoidance area T _d ^r from u is present, the algorithm discovers one X∈S ₁ of the terminal node Obviously we can do it. Here, the discovered path p is one of the shortest paths under f from u to x, and if there are a plurality of equal cost paths in the 29th and 48th line processing, it follows _Td . Therefore, the detour p of u is an appropriate route. Here, when a detour for u is set, detours for all nodes except the t-label node and the terminal node on p are also set. Since these nodes are descendants of r on _Td , x is outside these NP avoidance regions. That is, p is an NP detour for all nodes for which the second routing table is set.

Next, it is assumed that the condition is satisfied until the k-th iteration, and the detour calculated and set by the k + 1-th process indicates that the condition is also satisfied. If there is a path from the start node u to the outside of the _T ^{d r,} the algorithm can be always found w∈S ₁ ∪S ₂ ∪S _3. If wεS ₁ is found, the condition is satisfied from the above discussion.

If wεS ₂ is found, let p be the discovered path from u to v, p ′ be the path along T _d from v to w, and q be the (already set) detour of w Road. q is a more appropriate route than assumed, and q does not include r from vεD _d (r). Further, the algorithm for the avoidance area is wide order to calculate the (roots i.e. avoidance area is sequentially closer to the destination d) bypass passage, q can reach external T _d ^r. Therefore, the path p + p ′ + q is a detour of u. On the other hand, from Lemma 2, this detour of u is a connection of two appropriate paths p + p ′ and q. The algorithm takes a node from Q and determines a detour as soon as it finds a node w with wεS ₁ ∪S ₂ ∪S ₃ in its ancestor. Thus, all of _{x 1 ∈ (p + p '} ), for the set of _{x 2 ∈q,} if a descendant on the _{T d x 1} is _{x 2, p + p' +} q on the interval _{[x 1, x} 2] Is included in _Td . That is, the route p + p ′ + q is an appropriate route. At this time, all nodes for which the second routing table is set have NP detours as described above.

Finally, if w ∈ S ₃ , let p be the discovered path from u to v, p ′ be the path along T _d from v to w, and q ₁ be the tunnel detour for w. , the _{q 2} to the reverse flow path of w. If q ₁ does not include r, p + p ′ + q ₁ is a detour that can reach the outside of T _d ^r by an argument similar to the case of wεS ₂ above, and is an appropriate route. On the other hand, if q ₁ comprises r, Both w and r are within the tunnel section of w since q ₁ is suitable route. Therefore, from Lemma 1, the backward flow path of w can reach the outside of T _d ^r , and p + p ′ + q ₂ is a detour of u. From Lemma 2, p + p ′ + q ₂ is an appropriate route. At this time, all nodes for which the second routing table is set have NP detours as described above.

As described above, all nodes for which the second routing table is set (except for u) in the (k + 1) th iteration process have detours that satisfy the theorem. (End of proof)
<Operation>
Next, a processing flow from IP packet reception to IP packet transfer in the node u2 will be described with reference to FIG. It should be noted that each node (nodes u1, u3, u4, u5, w1, w2) other than the node u2 shown in FIG. 1 performs the same operation.

First, when the receiving unit 14 receives an IP packet (S10), the state control unit 22 reads the state included in the header of the received IP packet (S11).
If the state is 0 (S12: Yes) and the failure detection unit 20 has not detected a failure of the next hop in the first route table 42 (S13: No), the transfer unit 16 is the next hop in the first route table 42. The IP packet is transferred to (S14). As described above, as long as there is no failure in the next hop of the first route table 42, the state remains 0 and is transferred to the next hop of the first route table 42.

  If the failure detection unit 20 detects a failure of the next hop (S13: Yes), the transfer unit 16 transfers the IP packet to the next hop in the second route table 44 (S18). Before the transfer, the state control unit 22 refers to the label table 46, and if the s-label is not true (S15: No, S16), the state is rewritten from the state 0 to the state 1 (S16), and the s-label is true. If so (S15: Yes), the state is rewritten from the state 0 to the state 3 (S17).

  If the state is not 0 but 1 (S12: No, S21: Yes), the transfer unit 16 transfers the IP packet to the next hop of the second route table 44 (S26). Before the transfer, the state control unit 22 refers to the label table 46, and if the i-label is true, it is rewritten from the state 1 to the state 2 (S22: Yes, S23). If the label is true, it is rewritten from state 1 to state 3 (S22: No, S24: Yes, S25).

If the state is not 1 but 2 (S21: No, S31: Yes), the transfer unit 16 transfers the IP packet to the next hop of the first route table 42 (S34). Before the transfer, the state control unit 22 refers to the label table 46 and rewrites the state 2 to the state 1 if the o-label is true (S32: Yes, S33).
If the state is 3 instead of 2 (S31: No, S41), the transfer unit 16 transfers the IP packet to the next hop of the first route table 42 (S42).

FIG. 8 shows the result of calculation according to the algorithm described above for the first and second routing tables and each label in the network 1 of FIG.
In FIG. 8, the first route table, the second route table, and each label indicate true / false beside each of the nodes u1 to u5, w1, and w2. For example, in the node u2, the next hop shown in the first route table is u1, the next hop shown in the second route table is u3, the i label is true, the o-label, and the s-label are false. ing.

For example, when the node u1 receives the IP packet of the destination d, the operation of each node when the node u5 fails is as follows (1) to (6) (see FIG. 9).
(1) Upon receipt of the state 0 IP packet (S12: Yes), the node u1 detects a failure of the next hop u5 in the first routing table (S13: Yes), and rewrites the state from 0 to 1 (S16). ) And forward to u2 of the next hop shown in the second route table (S18).

(2) When the node u2 receives the state 1 IP packet (S21: Yes), the i-label is true, so the state is rewritten from 1 to 2 (S22: Yes, S23), and the next route table shows Forward to hop u3 (S26).
(3) Upon receiving the state 2 IP packet (S31: Yes), the node u3 rewrites the state from 2 to 1 because the o-label is true (S32: Yes, S33), and the next hop u4 in the first routing table (S34).

(4) When the node u4 receives the state 1 IP packet (S21: Yes), since the s-label is true, the state is rewritten from 1 to 3 (S22: No, S24: Yes, S25), and the second route table To the next hop w1 (S26).
(5) Upon receiving the state 3 IP packet (S41), the node w1 transfers the packet to the next hop w2 of the first routing table (S42).

(6) Upon receiving the state 3 IP packet (S41), the node w2 transfers the packet to the next hop d in the first routing table (S42).
As described above, even when the node u5 fails, the IP packet can be safely delivered to the destination node d through the detour such as the node u1 → u2 → u3 → u4 → w1 → w2 → d.

  As described above, according to the present embodiment, the state of the IP packet is rewritten using the s, i, and o labels associated with the destination of the IP packet, and the first route table and the second route are rewritten. It is possible to set various tables to be used. In particular, in the detour after the detection of the node failure, even though the detour is once entered (u1 → u2 → u3), the first route table is used on the way to enter the tunnel through the shortest path (u3 → u4). After leaving the tunnel, an appropriate detour can be set flexibly by using the second route table (u4 → w1) and then using the first route table (w1 → w2 → d). .

In this way, node protection can be realized with only two routing tables, the first routing table and the second routing table. In addition, since the four states are inserted into the TOS field of the IP packet header with a light information amount of 2 bits, the influence on the network is slight.
<Supplement>
As mentioned above, although embodiment of this invention was described, this invention is not limited to said content, It can implement also in the various forms for achieving the objective of this invention, the objective related to it, or an incidental, for example, It may be the following.

1. In the embodiment, only the example when the node u5 has failed (FIG. 8) has been described. However, according to the embodiment, an IP packet in which any of the nodes u1 to u5, w1, and w2 is the destination d Even if another node is faulty when the node is received, it is possible to appropriately guarantee a detour, that is, it is possible to realize node protection.
Further, even if an arbitrary link has failed, a detour can be appropriately ensured, that is, link protection can be realized.

2. An example in which the embodiment is applied to a network having a different form from that in FIG. 1 (FIG. 8) will be described below as a modification. FIG. 10 is a diagram illustrating a network configuration according to a modification. FIG. 10A shows a network configuration (topology), FIG. 10B shows a first route table and an o-label, and FIG. 10C shows a second route table, an i-label, and an s-label.
Also in the network of FIG. 10, node protection can be realized as in the embodiment. For example, when node 2 receives an IP packet whose destination is node 6, and node 3 is out of order,
(1) When node 2 detects a failure of node 3, node 2 rewrites the state of the IP packet from 0 to 1, and forwards the IP packet to node 7 of the next hop shown in the second route table.

(2) Since the state of the IP packet is 1, the node 7 transfers the IP packet to the node 9 of the next hop shown in the second route table. Since the i-label is true, the state is rewritten from 1 to 2 before transfer.
(3) Since the state of the IP packet is 2, the node 9 transfers the IP packet to the next hop node 4 shown in the first route table. Since the o-label is true, the state is rewritten from 2 to 1 before transfer.

(4) Since the state of the IP packet is 1, the node 4 transfers the IP packet to the node 5 of the next hop shown in the second route table. Since the s-label is true, the state is rewritten from 1 to 3 before transfer.
(5) Since the state of the IP packet is 3, the node 5 transfers the IP packet to the next hop node 8 shown in the first route table.

(6) Since the state of the IP packet is 3, the node 8 transfers the IP packet to the node 6 of the next hop shown in the first route table.
In this way, node protection can also be performed in this modification.
3. As a method of using the first routing table in the middle of the detour, it is possible to combine with an encapsulation technique, or a label switching technique including MPLS (Multi Protocol Label Switching) and ATM (Asynchronous Transfer Mode).

As for encapsulation, there are typical tunneling technologies that encapsulate IP packets in IP packets defined in RFC2003, but tunneling between different protocols as defined in RFC1701 and RFC3931. A technique of encapsulating such a layer 2 frame (such as Ethernet (registered trademark)) in IP can be used as appropriate.
A specific example in the case of using encapsulation is shown in FIG. In FIG. 11, as in FIGS. 8 and 14, the routes to the next hop in the first route table and the second route table are indicated by arrows “first route”, “second route”, respectively. .

When the node u1 fails, the packet is transferred through a route of u1->u2->u3->u4->u5->u6->u7-> d. Basically, the behavior is different only from the node u3 to the node u5, and only the details during this time will be described below.
(1) In node u3, an IP packet (state 1, destination d) is put in the payload part and a packet containing destination u5 and state 0 (default state) is created in the header part (encapsulation) To the node u4 on the first route. An IP packet (state 1, destination d) is included in the encapsulated packet.

(2) Since the state of the received IP packet is 0, the node u4 sends the IP packet to the node u5 indicated in the first route table.
(3) Since the destination of the received IP packet is the node itself, the node u5 releases the encapsulation of the packet and takes out the IP packet (state 1, destination d) from the contents (payload portion). Then, since the extracted IP packet (state 1, destination d) is in state 1, it is sent to node u6 in the second routing table.

  The encapsulated “u3” is a node on the first path as viewed from the node u2 to which the i-label is added (the node that first receives the packet of state 2), and the encapsulated packet The destination “u5” is a node on the first route as seen from the node u4 to which the o-label is added. By setting the encapsulation start node and the destination node in this way, it is possible to set a tunnel section (section from u3 to u5) passing through the first path (shortest path) during the detour.

Note that the encapsulation start node can be changed as appropriate, for example, “u2” instead of “u3”.
Next, a description will be given using MPLS as an example in combination with the label switching technique. MPLS is a technology that adds an MPLS label to a packet, and transfers a packet with an MPLS label using a preset route corresponding to the MPLS label. The MPLS label is added during route control. It can be deleted or manipulated. MPLS is used for load distribution and the like because it allows more flexible route setting than conventional route control using the shortest route.

A specific example in the case of using MPLS is shown in FIG. In this example, only details from the node u3 to the node u5 will be described below.
(1) At node u3, the label “7”, which is an MPLS label, is added to the IP packet (state 1, destination d). In the MPLS network, the transfer destination is determined based on only the label, not the destination of the IP header. Therefore, the packet is transferred using an LSP (Label Switch Path) corresponding to the label “7”. Here, it is assumed that the label “7” has an end point (destination) set to a route passing through the first route (shortest route) from u3 → u4 → u5 at the node u5.

(2) The node u4 sends the IP packet to the node u5 according to the label “7” added to the received IP packet.
(3) Since the label “7” added to the received IP packet is destined for the node “node”, the node u4 removes the label “7” from this IP packet. Since the IP packet with the label “7” removed is in the state 1, the IP packet is sent to the node u6 indicated in the second route table.

  Note that “u3” to which the label “7” is added is a node (a node that first receives the packet of the state 2) in the first path as viewed from the node u2 to which the i-label is added, and the label “ The route according to 7 "passes through the first route (shortest route) and the end point of the route is" u5 ". When MPLS is used, a tunnel section (section from u3 to u5) passing through the first path (shortest path) can be set in the detour as in the case of the above encapsulation.

In FIG. 12, the label “7” is described as being set so as to pass through the first route (shortest route). However, considering the efficiency, the shortest route is desirable, but not limited to this. The route may be different from the route (detour), and is not necessarily the shortest route.
4). In the embodiment, an example applied to an OSPF (Open Shortest Path First) routing protocol has been described. OSPF has the advantage that it enables very efficient operation in a medium-sized network.

The method described in the embodiment can be applied not only to OSPF but also to link state routing such as IS-IS (Intermediate System to Intermediate System).
Furthermore, static routing, that is, first and second routing tables, labels, and the like may be manually set for each node.

5. In the embodiment, the calculation unit 30 of each node individually calculates a table and a label. Instead, the above calculation is performed by a server having excellent processing capability, and each node receives a calculation result from the server. You may set tables and labels.
6). In the embodiment, Dijkstra is taken as an example of the shortest path calculation algorithm. However, the present invention is not limited to this, and other shortest path calculation algorithms such as the Warshall-Floyd method can be applied.

  7. In the embodiment, the next hop in the first route table is an adjacent node (shortest node) existing on the shortest route to reach the destination node d, and the next hop in the second route table is to reach the destination node d. Although it has been described that it is an adjacent node (detour node) existing on the detour route, the method of deriving the next hop in the first route table is not limited to this. For example, if the network design does not focus on efficiency (or can be ignored), a node that is not the shortest node may be set in the first routing table.

  8). In the embodiment, it has been described that the state is rewritten from the state 0 to the state 1 when a failure of the failure detection unit 20 is detected. However, the first route table is not limited to such failure detection, for example, congestion is detected. It may be a condition that transfer to the next hop cannot be performed smoothly. In addition, rewriting from the state 0 to the state 1 may be performed based on the detection result by using a message exchanged with an adjacent node, a current flowing through the link, an optical signal, and the like as periodic detection targets.

9. In the flowchart of FIG. 7, when the next hop in the second routing table does not exist, such as when the calculation of the second routing table is incomplete when trying to transfer to the next hop in the second routing table, the state is rewritten to state 3. May be forwarded to the next hop of the first routing table.
10. The present embodiment can be applied to a wireless ad hoc network, a wireless mesh network, a sensor network, and other various networks that require route control.

11. The first and second route tables described in the embodiment and the algorithm for calculating each label are merely examples and are not limited thereto.
12 In the embodiment, the state is described as including the state in the TOS field of the IPv4 IP packet. However, in IPv6, for example, the state can be included in the extended field of the header portion.

  13. In the embodiment, the IP packet has been described as an example. However, the present invention is not limited to the application of only the IP packet, and can be applied to all schemes that transfer packets using a routing table. In addition to IP, the present invention can also be applied to a protocol such as IPX (Internetwork Packet eXchange). In addition, it can be applied to other proprietary communication protocols for wireless communication.

14 In the embodiment, immediately after passing the node of the s-label, the state is changed to the state 3 after the detour (FIGS. 9 and 7: S24: Yes, S25), so that the further detour after the detour cannot be performed. However, the present invention is not limited to this, and a plurality of detours may be allowed by changing to the default state 0 instead of changing to the state 3.
Specifically, as shown in FIG. 13A, an area for storing the number of detours is set in the header portion of the IP packet.

  Then, as shown in FIG. 13B, if the s-label is true (S24: Yes), referring to the detour area stored in the IP packet, if the detour count is 3 or less, for example (S51) : Yes), the detour count is incremented (S52), and the state is changed from state 1 to state 0 (S53). If the number of bypasses is not 3 or less (S51: No), the state is changed from state 1 to state 3 (S25).

In FIG. 13B, the same step number is assigned to the same step as in FIG.
By doing so, it is possible to allow the IP packet to be detoured up to three times, thereby contributing to reduction of packet loss.

  The route control device according to the present invention is useful as a network device such as a router.

DESCRIPTION OF SYMBOLS 1 Network 14 Reception part 16 Transfer part 20 Failure detection part 22 State control part 30 Calculation part 32 1st routing table calculation part 34 2nd routing table calculation part 36 Label calculation part 42 1st routing table 44 2nd routing table 46 Label table u1-u5, w1, w2 nodes (routers)
d Destination node (destination router)

Claims (4)

A node constituting a network, a path control device for controlling a forwarding destination of a packet,
A receiving unit that receives a packet that stores a destination and information indicating a state relating to determination of a transfer destination;
A first route table in which a destination node is associated with a first node existing on the first route to the destination node;
A second route table in which the destination node is associated with the second node existing on the second route to the destination node;
For each destination node, label information indicating the rewrite contents stored in the packet,
A storage unit for storing
The state indicated in the information stored in the packet received by the receiving unit,
If it is in state 0 and transfer to the first node is possible, transfer the packet to the first node;
If it is in state 0 and transfer to the first node is not possible, the packet is transferred to the second node, and the label information corresponding to the destination of the packet indicates the addition of the first label. Rewrite from state 0 to state 3 before transfer, and rewrite from state 0 to state 1 before transfer if the first label is not indicated.
If it is in state 1, the packet is transferred to the second node, and if the label information corresponding to the destination of the packet indicates the addition of the second label, the state is changed from state 1 to state 2 before transfer. Rewrite, if not showing the addition of the second label but showing the addition of the first label, rewrite from state 1 to state 3 before transfer,
If in state 2, the packet is transferred to the first node, and if the label information corresponding to the destination of the packet indicates the addition of a third label, the state 1 is transferred from the state 2 before the transfer. Rewritten,
If it is in state 3, a transfer control unit that transfers the packet to the first node;
A path control device comprising: A node constituting a network, a path control device for controlling a forwarding destination of a packet,
Receiving a packet storing information indicating a state related to determination of a destination and a transfer destination;
When receiving an encapsulated packet addressed to the own node, a receiving unit that handles the packet after decapsulation as a received packet;
A first route table in which a destination node is associated with a first node existing on the first route to the destination node;
A second route table in which the destination node is associated with the second node existing on the second route to the destination node;
For each destination node, label information indicating the rewrite contents stored in the packet,
A storage unit for storing
The state indicated in the information stored in the packet received by the receiving unit,
If it is in state 0 and transfer to the first node is possible, transfer the packet to the first node;
If it is in state 0 and transfer to the first node is not possible, the packet is transferred to the second node, and the label information corresponding to the destination of the packet indicates the addition of the first label. Rewrite from state 0 to state 3 before transfer, and rewrite from state 0 to state 1 before transfer if the first label is not indicated.
If it is in state 1, the packet is transferred to the second node, and if the label information corresponding to the destination of the packet indicates the addition of the second label, the state is changed from state 1 to state 2 before transfer. Rewrite, if not showing the addition of the second label but showing the addition of the first label, rewrite from state 1 to state 3 before transfer,
If it is state 2, the state of the received packet is rewritten from state 2 to state 1, and the packet is viewed from the node whose label information corresponding to the destination of the packet indicates the addition of the third label. Encapsulating a node that is a first node as a destination and enclosing it in a packet that is in state 0, forwarding the encapsulated packet to the first node,
If it is in state 3, a transfer control unit that transfers the packet to the first node;
A path control device comprising: A node constituting a network, a path control device for controlling a forwarding destination of a packet,
A receiver that receives a packet that stores information indicating a destination and a state relating to determination of a transfer destination;
A first route table in which a destination node is associated with a first node existing on the first route to the destination node;
A second route table in which the destination node is associated with the second node existing on the second route to the destination node;
For each destination node, label information indicating the rewrite contents stored in the packet,
A storage unit for storing
The state indicated in the information stored in the packet received by the receiving unit,
If it is in state 0 and transfer to the first node is possible, transfer the packet to the first node;
If it is in state 0 and transfer to the first node is not possible, the packet is transferred to the second node, and the label information corresponding to the destination of the packet indicates the addition of the first label. Rewrite from state 0 to state 3 before transfer, and rewrite from state 0 to state 1 before transfer if the first label is not indicated.
If it is in state 1, the packet is transferred to the second node, and if the label information corresponding to the destination of the packet indicates the addition of the second label, the state is changed from state 1 to state 2 before transfer. Rewrite, if not showing the addition of the second label but showing the addition of the first label, rewrite from state 1 to state 3 before transfer,
If it is state 2, the state of the received packet is rewritten from state 2 to state 1, and an MPLS label for identifying the route corresponding to the first route table is added to the received packet. Then forward to the node identified by the MPLS label,
If it is in state 3, a transfer control unit that transfers the packet to the first node;
A path control device comprising: A method in a routing system composed of a plurality of nodes constituting a network,
In each node, a storage step of storing a first route that reaches the destination node and a second route that reaches the destination node and is a different route from the first route;
In each node, if transfer of a packet using the first route is not possible, a detour start step of transferring the packet using the second route after adding information indicating that the packet is being detoured to the packet;
When each node receives a packet to which information indicating that it is detouring is added, a detouring step of forwarding the packet using the second route;
If each node satisfies a predetermined condition related to a route to reach the destination node with respect to its own node even though it has received a packet with information indicating that it is detouring, In place of the second route used in the step, the detour tunnel step for forwarding the packet using the first route table;
A method in a routing system comprising:

Images