Label switched path set up scheme with reduced need for label set up retry operation

[0002] 1. Field of the Invention

[0003] The present invention relates to a node device having a label switching function and a method for setting up a label switched path.

[0004] 2. Description of the Background Art

[0005] In a network layer protocol in which IP (Internet Protocol) nodes are inter-connected on a network, there is a scheme for realizing high speed packet transfer called MPLS (Multi-Protocol Label Switching).

[0006] In the MPLS, the label switching is carried out by allocating specific “labels” to specific packet flows between nodes and setting an input side label and an output side label in correspondence at each node, so that the IP processing can be omitted and a high speed packet transfer can be realized. For example, in the case where the link layer is ATM, VPI(Virtual Path Identifier)/VCI (Virtual Channel Identifier) will be used as a label. A route through which the packet flow is label switched is called a label switched path. In the following description, the label switched path will be referred to simply as a path.

[0007] In the case of constructing the path, a label distribution protocol is used. The label distribution protocol exchanges control messages (path control messages) between nodes on a packet flow route in order to notify a correspondence between a flow identifier for identifying the packet flow in network global fashion and a label for identifying the packet flow in link local fashion.

[0008] In general, the path control message is transferred according to the layer 3 route information, but when the layer 3 route is looping, there are possibilities for the path control message to loop or a looping path to form.

[0009] In order to resolve this problem, there is a loop prevention method disclosed in “Internet-Draft, draft-ohba-mpls-loop-prevention-00.txt”, in which the ingress node information is contained in the path control message and each node stores the ingress node address (ingress node information) and the hop count from the ingress node for each branch on the input side of the path, and notifies to the downstream side the ingress node information which has the largest hop count from the ingress node among all the stored ingress node information along with the largest hop count +1. In addition, in the case of adding a new branch on the input side of the current path, or in the case of updating the ingress node information or the hop count from the ingress node for the existing input side branch, if the same ingress node information is already registered for another input side branch with respect to the same flow, it is judged that a loop will be formed so that the addition/updating of the input side branch is not carried out.

[0010] This loop prevention method has an advantage over the path vector scheme (in which each node that forwards the path control message adds its own address to the label allocation message and it is judged as a loop is the received label allocation message has the own address already written therein) in that the message length becomes fixed regardless of the hop count.

[0011] However, this loop prevention method has the following problem at a time of the route change.

[0012] For instance, consider a case where a path through a sequence of node devices R11→R12→R13→R14→R15→R16 on the layer 3 route is formed as shown in FIG. 1.

[0013] In this case, each node device on the path stores a flow identifier (flowid), an input link information (input physical link information (input interface)+input label)) for identifying the path, and “R11” as the ingress node information. The input link information (input link) is an information set in correspondence to the output link information (output link) and used in the label switching, which is obtained from a label obtained from the link identifier and an information on a physical link that exchanged the message. The physical link information will be denoted as Iij (i: an upstream node number of the link, j: a downstream node number of the link), and the link will be denoted as “physical link information: label”.

[0014] FIG. 2 shows the state of a flow table provided in the node device R15 in the case of the path shown in FIG. 1.

[0015] In this case, when the route change occurs at R12 and the next hop leading to Flowid=R16 is changed from R13 to R17, the label allocation release message (RELEASE message) specifying (flowid=R16, ingress=R11) is sent on the old route from R12, while the label allocation request message (SETUP message) specifying (flowid=R16, ingress=R11) is sent on the new route from R12.

[0016] Now, if the SETUP message reaches to R15 before the RELEASE message, another entry with flowid=R16 and ingress=R11 is already set in correspondence to the input link (I1516: x1516) when the SETUP message for the input link (I1715: x1715) is received, so that R15 judges that it is a loop even though it is actually not a loop.

[0017] As a result, the label allocation failure (SETUP_NACK) message will be returned from R15 to R17. At this point, R17 carries out the retransmission (retry) of the SETUP message after a prescribed period of time, but the retry would have to be repeated many times before the RELEASE message arrives from the old route if the retry interval is set too short, whereas a considerable amount of time would elapse before the path is switched to the new route if the retry interval is set too long. Yet, it is generally difficult to determine the optimum value for the retry interval, so that there is a need for a loop prevention mechanism that can minimize the need of the retry.

[0018] It is therefore an object of the present invention to provide a label switched path set up scheme which is capable of detecting a loop of the label switched path efficiently and quickly, and which can enable the switching of the label switched path even in the case where conventionally a label switch path loop would be erroneously detected at a time of the route change, without requiring a label set up retry operation from a previous hop node device of the node device that have erroneously detected the loop which would have been necessary conventionally.

[0019] According to one aspect of the present invention there is provided a method for setting up a label switched path, comprising the steps of: judging whether the label switched path forms a loop or not at a node that received a request message regarding a label switched path set up for a packet flow, on a basis of label switched path information stored in a first mode at said node that received the request message, the request message including a flow identifier for identifying the packet flow and information indicating that it is a message currently awaiting a response regarding the packet flow, and the first mode indicating that a message from which the label switched path information originates is a message currently awaiting a response; storing the flow identifier contained in the request message as the label switched path information in the first mode at said node device that received the request message, and transferring the request message from said node that received the request message to another node on a route of the packet flow, when said node that received the request message cannot judge that the label switched path does not form a loop; returning a response message for the request message from said node that received the request message when said node that received the request message judges that the label switched path does not form a loop; and changing the label switched path information currently stored in the first mode at a node that received the response message into a second mode different from the first mode such that the label switched path information that is changed into the second mode will not be used subsequently in judging whether any requested label switched path forms a loop or not at said node that received the response message and the label switched path will become available at said node that received the response message.

[0020] According to another aspect of the present invention there is provided a node device for setting up a label switched path, comprising: a judging unit configured to judge whether the label switched path forms a loop or not upon receiving a request message regarding the label switched path set up for a packet flow, on a basis of label switched path information stored in a first mode at a memory of said node device, the request message including a flow identifier for identifying the packet flow and information indicating that it is a message currently awaiting a response regarding the packet flow, and the first mode indicating that a message from which the label switched path information originates is a message currently awaiting a response; a first processing unit configured to store the flow identifier contained in the request message as the label switched path information in the first mode at the memory and transfer the request message to another node on a route of the packet flow, when the judging unit cannot judge that the label switched path does not form a loop, and to return a response message for the request message when the judging unit judges that the label switched path does not form a loop; and a second processing unit configured to change the label switched path information currently stored in the first mode at the memory into a second mode different from the first mode upon receiving the response message, such that the label switched path information that is changed into the second mode will not be used subsequently in judging whether any requested label switched path forms a loop or not at said node device and the label switched path will become available at said node device.

[0021] According to another aspect of the present invention there is provided a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a node device for setting up a label switched path, the computer readable program code means includes: first computer readable program code means for causing said computer to judge whether the label switched path forms a loop or not upon receiving a request message regarding the label switched path set up for a packet flow, on a basis of label switched path information stored in a first mode at a memory of said node device, the request message including a flow identifier for identifying the packet flow and information indicating that it is a message currently awaiting a response regarding the packet flow, and the first mode indicating that a message from which the label switched path information originates is a message currently awaiting a response; second computer readable program code means for causing said computer to store the flow identifier contained in the request message as the label switched path information in the first mode at the memory and transfer the request message to another node on a route of the packet flow, when the first computer readable program code means cannot judge that the label switched path does not form a loop, and to return a response message for the request message when the first computer readable program code means judges that the label switched path does not form a loop; and third computer readable program code means for causing said computer to change the label switched path information currently stored in the first mode at the memory into a second mode different from the first mode upon receiving the response message, such that the label switched path information that is changed into the second mode will not be used subsequently in judging whether any requested label switched path forms a loop or not at said node device and the label switched path will become available at said node device.

[0022] Other features and advantages of the present invention will become apparent from the following description taken in conjunction with the accompanying drawings.

[0023] FIG. 1 is a diagram showing an exemplary network for explaining a conventional loop prevention method.

[0024] FIG. 2 is a diagram showing a flow table in one node of the network shown in FIG. 1.

[0025] FIG. 3 is a diagram showing one exemplary network formed by connecting node devices according to one embodiment of the present invention.

[0026] FIG. 4 is a diagram showing an exemplary label switched path that is set up by one embodiment of the present invention in the network shown in FIG. 3.

[0027] FIG. 5 is a diagram for explaining an exemplary operation of a node device according to one embodiment of the present invention in the case of a route change in the network shown in FIG. 3.

[0028] FIG. 6 is a diagram for explaining an exemplary operation of a node device according to one embodiment of the present invention in the case of a route change in the network shown in FIG. 3.

[0029] FIG. 7 is a diagram showing an exemplary label switched path that is obtained as a result of the router change in the network shown in FIG. 3.

[0030] FIG. 8 is a diagram for explaining an exemplary operation of a node device according to one embodiment of the present invention in the case of a further route change in the network shown in FIG. 3.

[0031] FIG. 9 is a diagram for explaining an exemplary operation of a node device according to one embodiment of the present invention in the case of a further route change in the network shown in FIG. 3.

[0032] FIG. 10 is a diagram showing an exemplary label switched path that is obtained as a result of the further router change in the network shown in FIG. 3.

[0033] FIG. 11 is a diagram showing another exemplary network formed by connecting node devices according to one embodiment of the present invention.

[0034] FIG. 12 is a diagram showing an exemplary label switched path that is set up by one embodiment of the present invention in the network shown in FIG. 11.

[0035] FIG. 13 is a diagram for explaining an exemplary operation of a node device according to one embodiment of the present invention in the case of a route change in the network shown in FIG. 11.

[0036] FIG. 14 is a diagram showing an exemplary label switched path that is obtained as a result of the router change in the network shown in FIG. 11.

[0037] FIG. 15 is a diagram for explaining an exemplary operation of a node device according to one embodiment of the present invention in the case of a further route change in the network shown in FIG. 11.

[0038] FIG. 16 is a diagram showing an exemplary configuration of an internal database used for a loop detection in one embodiment of the present invention.

[0039] FIG. 17 is a diagram showing a further detail of an exemplary configuration of an internal database used for a loop detection in one embodiment of the present invention.

[0040] FIG. 18 is a flow chart of an exemplary operation of a node device according to one embodiment of the present invention at a time of thread receiving.

[0041] FIG. 19 is a flow chart of an exemplary operation of a node device according to one embodiment of the present invention at a time of route change occurrence.

[0042] FIG. 20 is a diagram showing a format of a message exchanged among node devices for the purpose of loop detection according to one embodiment of the present invention.

[0043] FIG. 21 is a block diagram showing an exemplary configuration of a node device according to one embodiment of the present invention.

[0044] FIG. 22 is a block diagram showing a detail configuration of a control message processing unit in the node device of FIG. 21.

[0045] Now, one embodiment of the label switched path set up scheme according to the present invention will be described with references to the drawings.

[0046] First, the terms used in the following description and a basic configuration of a node device according to the present invention will be described.

[0047] <Definition of Directions>

[0048] At each node, for each label switched path (hereafter abbreviated as path), a side that is closer to the ingress node will be referred to as “input side” (or “upstream side”) and a side that is closer to the egress node will be referred to as “output side” (or “downstream side”).

[0049] Also, at each node, a label that is allocated to an input side neighboring node (upstream side neighboring node) will be referred to as “input side label” (hereafter abbreviated as input label), and a label that is allocated to an output side neighboring node (downstream side neighboring node) will be referred to as “output side label” (hereafter abbreviated as output label).

[0050] <Neighboring Node>

[0051] A neighboring node is a node other than the own node to which packets can reach without a label rewriting, which is not necessarily neighboring from a viewpoint of the network protocol. For example, in the case of stacking the label, the neighboring node can be a node that is distanced by two hops or more from a viewpoint of the network protocol when the stack level becomes deep.

[0052] <Link>

[0053] Each node has “states” related to an individual input label or output label of a given path. A state related to the input label will be referred to as “input link” and a state related to the output label will be referred to as “output link”. In the case of deleting the link, a notice for deleting the link is notified to the neighboring nodes.

[0054] <Flow>

[0055] A flow (packet flow) is a set of packets that flow through a path. The flow is specified by a flow identifier (flow ID).

[0056] <Proxy Ingress Node>

[0057] A proxy ingress node is a node that “actively” activates the path generation. Here, “actively” implies “without using a path set up request from an upstream side neighboring node directly as a trigger”. A term “passively” will be used as an opposite of “actively”.

[0058] The proxy ingress node is either (1) an ingress node, (2) a node having an input link which requests the allocation of an output label to a downstream side neighboring node due to the route change, or (3) a node having an input link which newly recognized a downstream side neighboring node.

[0059] <Path Length>

[0060] At a given node, the largest number among the hop counts up to the own node from ingress nodes on the upstream side of the own node will be referred to as a path length. In the case of notifying the path length to the downstream side neighboring node, a value obtained by incrementing the path length at the own node by one will be notified. In order to manage the path length, there is a need to store an information on the path length that is notified from the upstream side neighboring node, for each input link of the path.

[0061] In the case where the route is looping, the accurate path length becomes indeterminate. In such a case, a special value <unknown> can be used as the path length. It is assumed that the path length value of <unknown> is larger than the path length values other than <unknown>. When the path length value <unknown> is incremented by one, the resulting path length value is also <unknown>.

[0062] <Thread>

[0063] When the proxy ingress node requests the allocation of an output label for some path to the downstream side neighboring node regarding some flow, the proxy ingress node generates a “thread” which is an information containing at least an identifier for uniquely identifying in the network a message regarding a path set up for which ACK regarding that flow is awaited, and forwards this “thread” by including it in the message to the downstream side neighboring node, in order to detect and prevent a loop of the path. This thread is a concept newly introduced in the present invention. In the following, forwaring the “thread” by including it in the message will be simply referred to as “notifying the thread”. Similarly, receiving the message regarding the path set up that contains the thread will be simply referred to as “receiving the thread”. Also, receiving ACK for the message regarding the path set up that contains the thread will be simply referred to as “receiving ACK for the thread”.

[0064] A thread has at least an identifier (thread color). This thread color is also a concept newly introduced in the present invention. Threads with the same thread color will be regarded as the same thread. Also, a thread may also have an information (thread length) regarding the path length. Here, the ingress node generates a thread with the thread length equal to 0.

[0065] In general, a thread is denoted by (thread color, thread length), and in the case where threads do not contain the thread length information, all the threads will have the same setting of the thread length=<unknown> in this embodiment.

[0066] <Thread Forwarding>

[0067] Each node processes received threads in their received order. Also, there is a need to guarantee the thread transfer order between the neighboring nodes.

[0068] In the case of forwarding a thread to the downstream side neighboring node, the thread length is incremented by one. A thread will be forwarded up to a node that can judge whether the path will be looping or not.

[0069] A thread that is forwarded to the downstream side neighboring node corresponds to some output link of the node that forwarded it, and a thread received from the upstream side neighboring node corresponds to some input link of that node.

[0070] The forwarded thread is set in a forwarding state until ACK for confirming that the thread will not be looping is returned from the downstream side neighboring node.

[0071] As an exception, a thread that does not require ACK will be defined in the case of notifying only the update of the path length to the path for which it is already confirmed that the thread will not be looping. A thread that does not require ACK will be identified by the thread color=0.

[0072] <Thread Deletion>

[0073] The proxy ingress node can actively delete a correspondence between an output link and a thread, but cannot actively delete a correspondence between an input link and a thread. Nodes other than the proxy ingress node cannot actively delete a correspondence between an input link or an output link and a thread.

[0074] In the case of deleting some link which is in correspondence to some thread, that some thread will also be deleted.

[0075] When the proxy ingress node actively deletes a correspondence between some input link and a thread, if the input link is not deleted, a thread at the output link corresponding to that input link will not be deleted.

[0076] When a node other than the proxy ingress node actively deletes a correspondence between some input link and a thread, if no other thread that does not form a loop is set in correspondence to the other input link of the same path, a thread at the output link corresponding to that input link will be deleted.

[0077] In the case of deleting a thread that is corresponding to an output link, the deletion of the thread is notified to the downstream side neighboring node.

[0078] <Thread Looping>

[0079] A thread is said to be looping when a node that is forwarding the thread receives the same thread at an input link that is different from an input link through which that thread.has been received, or when that node is forwarding the same thread as the received thread at an output link.

[0080] <Thread Merging>

[0081] When a node receives a thread, if the received thread is not looping and there exists another thread which belongs to the same path, the thread merging is carried out. On the contrary, when a thread corresponding to some input link is to be deleted, the thread will be unmerged. If another thread that does not form a loop is still corresponding to the other input link after the deletion, a thread corresponding to the output link will not be deleted.

[0082] One thread among those threads which are to be merged is selected according to a selection method which is commonly used throughout the network, and the thread color/thread length of the selected thread will be set as the thread color/thread length of the merged thread. As a selection method for the case of using the thread length, there is a method in which the thread length of the merged thread is set to be the largest value among the thread lengths of the threads that are merged, and the thread color of the merged thread is set to be the thread color of a thread that has the largest thread length, where the thread color of a thread that has the largest thread color value (numerical value indicating the thread color) among those threads which have the largest thread length value will be used when there are plural threads which have the largest thread length value.

[0083] <Thread Updating>

[0084] When a node receives a thread that is corresponding to some input link and the thread color or the thread length of a thread that is currently in correspondence to that input link is different from that of the received thread, the received thread is set in correspondence to that input link. The updating of the thread color/thread length is immediately notified to the downstream side neighboring node in the case where the threads are not merged or in the case where the threads are merged and the thread color/thread length of the merged thread changes.

[0085] In addition, when some node is updating the information of a thread corresponding to some output link and a further updating with respect to this thread occurs, the new updating is notified to the downstream side neighboring node without waiting for the completion of the previous updating.

[0086] By forwarding threads, the following path set up that prevents loops is realized.

[0087] <Path Loop Prevention Algorithm>

[0088] A thread is forwarded until: (i) it reaches to the egress node, (ii) there exists an established path whose path length is not <unknown> and the thread length of the thread becomes less than or equal to that path length, or (iii) the thread forms a loop or the thread length that is not <unknown> reaches to a threshold.

[0089] When the thread forwarding is finished because of either (i) or (ii) above, it is guaranteed that the thread will not form a loop. At this point, it is also guaranteed that the label switched path does not form a loop either so that ACK with respect to the thread is returned hop by hop to the upstream side nodes. A node that transmitted/received ACK clears the forwarding state of the thread.

[0090] When ACK is returned up to the proxy ingress node that generated the thread, the label switching becomes possible.

[0091] On the other hand, when the thread forwarding is finished because of (iii) above, if the thread forms a loop, the thread length is set to be <unknown>. If the thread length is updated as a result of this, the updated thread length is notified to the downstream side nodes. At this point, the correspondence between the input link and the output link of the looping thread will be maintained. Note that, in the case of not using the thread length, the thread length is always <unknown> so that the update of the thread length will not be notified to the downstream side nodes.

[0092] If the route change occurs at the proxy ingress node, a new thread is generated and the generated thread is forwarded to the new route. Before notifying the thread to the new route, any threads in the forwarding state that are corresponding to the output links on the old route are deleted, the deletion of these threads is notified on the old route, and threads on their upstream side and the generated thread are connected (inputs and outputs are related).

[0093] When a node receives a thread and the received thread does not form a loop, the path length may be set equal to the received thread length either immediately or upon receiving ACK with respect to the thread.

[0094] In the case of notifying only the update of the path length to the downstream side neighboring node in the established path, a thread with the thread color=0 and the thread length=the updated thread length incremented by one will be used. A thread with the thread color=0 will be forwarded to the downstream until the path length updating stops and no ACK is required.

[0095] Note that the present invention is applicable to any definition of a flow. Also, the timing at which the ingress node activates the path set up can be either topology driven in which case it is a timing at which a routing table entry for that flow is generated, or flow driven in which case it is a timing at which packets matching that flow actually start flowing.

[0096] There can be various criteria for judging packets belonging to the identical flow, including: (1) those packets for which the destination IP address is the same are judged as belonging to the identical flow, (2) those packets for which a portion of the destination IP address corresponding to a network mask is the same are judged as belonging to the identical flow, (3) those packets for which a set of the source IP address and the destination IP address is the same are judged as belonging to the identical flow, (4) those packets for which a set of a portion of the source IP address corresponding to the first network mask and a portion of the destination IP address corresponding to the second network mask is the same are judged as belonging to the identical flow, (5) those packets which pass through a node that has a specific IP address are judged as belonging to the identical flow, and (6)) those packets for which the source and/or destination port numbers are the same in addition to any of (1) to (5) above are judged as belonging to the identical flow.

[0097] The present invention is also applicable to either (1) the case (called Ingress control) of generating the label switched path by the initiative of the ingress node, or (2) the case (called Egress Control) of generating the label switched path by the initiative of the egress node.

[0098] As for the timing at which a node device that is to be the ingress node transmits the label allocation request message, the following options are available, for example.

[0099] (1) Each node device transmits the label allocation request message at a timing of the generation of a routing table for the destination.

[0100] (2) Each node device transmits the label allocation request message at a timing at which traffics with respect to the destination exceed a threshold after the generation of a routing table for the destination.

[0101] (3) Only a node device that meets conditions that traffic with respect to the destination exceed a threshold after the generation of a routing table for the destination and a previous hop node device of the traffics (datagrams) does not support the label distribution protocol of this embodiment, transmits the label allocation request message by judging the own node as the ingress node at a timing at which these conditions are met (see Internet-Draft<draft-ietf-rolcnhrp-14.txt> “NBMA Next Hop Resolution Protocol (NHRP)”, for example).

[0102] In the following, this embodiment will be described in further detail using some concrete examples.

[0103] A node device of this embodiment has an IP (Internet Protocol) processing function and a label switching function according to the protocol of the present invention. Also a node device other than a node device located at an endpoint which does not carry out relaying may also have a router function. For instance, in FIG. 3, node devices R1 to R4 and R7 to R11 can have the router function while the router function is unnecessary at node devices R5 and R6 when they are located at endpoints and do not carry out relaying.

[0104] In the following description, it is assumed that those packets for which the destination IP address is the same are to be judged as belonging to the identical flow, and the description will be given by focusing on a specific flow. Also, the following examples are directed to the case of carrying out the merging (in which a node device carries out the path merging by setting the same output link information in correspondence to a plurality of input side labels for which the flow identifier is the same). Also, in the following examples, it is assumed that the path length is to be set equal to the thread length of a thread when ACK for the thread is returned.

[0105] The path has an input link for storing an information of the received thread with respect to each input, and an output link for storing an information of the transmitted thread with respect to each output. Also, the path has an information (flow ID) on a flow that is to be label switched on the path, an information on the path length, a flag (ingress flag) indicating whether the own node is the ingress node or not, and a flag (confirmation flag) indicating whether the path is awaiting ACK with respect to the thread or not.

[0106] The thread is identified by (thread color, thread length), and in the following examples, the thread color is to be denoted by “address of proxy ingress node: local ID”.

[0107] Here, the local ID is an identifier that is newly allocated whenever a thread is newly generated at each proxy ingress node. Note, however, that the description of the local ID will be omitted and the thread color is denoted by “address of proxy ingress node” in the following in the case of the local ID=0.

[0108] Also, in the following examples, values of the thread color are to be compared by comparing values of the proxy ingress node addresses (if there are threads for which the proxy ingress node address is the same but sequence numbers are different, values of the thread color are to be compared by comparing values of the sequence numbers). Note that, in the following examples, the proxy ingress node address will be denoted by a symbol such as R1, and for i>j, it is assumed that the value of the proxy ingress node address Ri is greater than the value of the proxy ingress node address Rj.

[0109] The confirmation flag of the path is turned off in the case of forwarding a thread to the downstream and turned on in the case of receiving ACK for the thread forwarding. In the case of multicast, it is turned on when ACK for the thread forwarding is received from all the output links.

[0110] The input link is identified by an input interface and a link identifier, while an output link is identified by an output interface and a link identifier. The link identifier can be locally allocated at an interface, and a label or any other ID can be used as the link identifier.

[0111] As already mentioned, the present invention is equally applicable to the case of path generation by the ingress node initiative and the case of path generation by the egress node initiative, but the following examples will be directed to the case of path generation by the ingress node initiative. The case of path generation by the egress node initiative is basically the same as the case of path generation by the ingress node initiative except that a node that newly received the label allocation request from the downstream side neighboring node of the flow will become the ingress node, generate a thread and forward it to the downstream side neighboring node.

[0112] Note also that, in the following description, “a=b” denotes that a value or content of “a” is “b”, “a==b” denotes that “a” is equal to “b” (or “a” is “b”), “a!=b” denotes that “a” is not equal to “b” (or “a” is not “b”), “a:=b” denotes that “b” is substituted into or set to “a”, “a>=b” denotes that “a” is greater than or equal to “b”, “a||b” denotes that “a” AND “b”, and “a && b” denotes “a” OR “b”.

[0113] <First Concrete Example>

[0114] First, the label switched path set up operation to be carried out by a node device according to one embodiment of the present invention will be described using a concrete example.

[0115] FIG. 3 shows an exemplary label switched network formed by connecting node devices of this embodiment. In FIG. 3, all or a part of node devices R1 to R11 may be connected to other node devices that are not shown in the figure.

[0116] In FIG. 3, a link between neighboring nodes indicates that the label switching is possible between these nodes, and an arrowhead of the link indicates a direction of a current next hop of a flow. Note that FIG. 3 also shows exemplary thread contents which will be explained later on.

[0117] Now, in the configuration of FIG. 3, suppose that a node device R1 and a node device R6 start the path set up almost simultaneously.

[0118] The node device Ri turns the ingress flag on, generates an output link between the own node device and a node device R2, generates a thread (R1, 0), stores the thread (R1, 0) at the output link, and notifies a thread (R1, 1) to the node device R2. Similarly, the node device R6 turns the ingress flag on, generates an output link between the own node device and a node device R7, generates a thread (R6, 0), stores the thread (R6, 0) at the output link, and notifies a thread (R6, 1) to the node device R7. At this point, the thread is entered into a label allocation request message (SETUP).

[0119] Upon receiving the thread (R1, 1), the node device R2 generates a new input link between the own node device and the node device Ri, and stores the thread (R1, 1). Then, the node device R2 generates an output link between the own node device and a node device R3, stores the received thread (R1, 1) at the output link, and notifies a thread (R1, 2) obtained by incrementing the thread length of the received thread (R1, 1) by 1, to the node device R3.

[0120] Upon receiving the thread (R6, 1), the node device R7 generates a new input link between the own node device and the node device R6, and stores the thread (R6, 1). Then, the node device R7 generates an output link between the own node device and a node device R8, stores the received thread (R1, 1) at the output link, and notifies a thread (R6, 2) obtained by incrementing the thread length of the received thread (R6, 1) by 1, to the node device R8.

[0121] Upon receiving the thread (R6, 2), the node device R8 generates a new input link between the own node device and the node device R7, and stores the thread (R6, 2). Then, the node device R8 generates an output link between the own node device and a node device R3, stores the received thread (R6, 2) at the output link, and notifies a thread (R6, 3) obtained by incrementing the thread length of the received thread (R6, 2) by 1, to the node device R3.

[0122] Suppose here that the node device R3 received the thread generated by the node device R1 earlier than the thread generated by the node device R6.

[0123] Then, upon receiving the thread (R1, 2), the node device R3 generates a new input link between the own node device and the node device R2, and stores the thread (R1, 2). Then, the node device R3 generates an output link between the own node device and a node device R4, stores the received thread (R1, 2) at the output link, and notifies a thread (R1, 3) obtained by incrementing the thread length of the received thread (R1, 2) by 1, to the node device R4.

[0124] After that, upon receiving the thread (R6, 3), the node device R3 generates a new input link between the own node device and the node device R8, and stores the thread (R6, 3). Here, the output link between the own node device and the node device R4 already exists, so that the thread merging is carried out. In this case, the thread length=3 of the received thread (R6, 3) is larger than the thread length=2 of the thread (R1, 2) currently stored at the output link, so that the thread (R1, 2) currently stored at the output link is replaced by the received thread (R6, 3) and a thread (R6, 4) obtained by incrementing the thread length of the received thread (R6, 3) by 1 is notified to the node device R4.

[0125] The node device R4 receives the thread (R1, 3) first. At this point, the node device R4 generates a new input link between the own node device and the node device R3, and stores the thread (R1, 3). Then, the node device R4 generates an output link between the own node device and a node device R9, stores the received thread (R1, 3) at the output link, and notifies a thread (R1, 4) obtained by incrementing the thread length of the received thread (R1, 3) by 1, to the node device R9.

[0126] The node device R4 next receives the thread (R6, 4). At this point, the input link between the own node device and the node device R3 already exists, so that the thread (R1, 3) currently stored at the input link is replaced by the received thread (R6, 4). Also, the output link between the own node device and the node device R9 already exists, so that the thread (R1, 3) currently stored at the output link is replaced by the received thread (R6, 4) and a thread (R6, 5) obtained by incrementing the thread length of the received thread (R6, 4) by 1 is notified to the node device R9.

[0127] Each one of node devices R9 and R10 carries out the operation similar to that of the node device R4.

[0128] As a result, the node device R3 receives the thread (R1, 6) and (R6, 7) in this order from the node device R10.

[0129] First, upon receiving the thread (R1, 6), the node device R3 generates a new input link between the own node device and the node device R10, and stores the thread (R1, 6). At this point, the same thread is already stored at the input link between the own node device and the node device R2 so that a loop of the thread is detected. In this case, the thread merging is not carried out and ACK is not returned. In addition, the node device R3 updates the thread length of the thread (R6. 3) stored at the output link between the own node device and the node device R4 to <unknown>, and notifies a thread (R6, <unknown>) obtained by incrementing the thread length of the updated thread (R6, <unknown>) by 1, to the node device R4.

[0130] Next, upon receiving the thread (R6, 7), the node device R3 stores the thread (R6, 7) at the input link already existing between the own node device and the node device R10. At this point, the same thread is already stored at the input link between the own node device and the node device R8 so that a loop of the thread is detected. In this case, the thread merging is not carried out and ACK is not returned. Here, the thread length of the thread (R6, <unknown>) already stored at the output link between the own node device and the node device R4 will not be updated from <unknown>, so that the update of the thread length is not notified to the node device R4.

[0131] Finally, upon receiving the thread (R6, <unknown>), the node device R3 stores the thread (R6, <unknown>) at the input link already existing between the own node device and the node device R10. At this point, the same thread is already stored at the input link between the own node device and the node device R8 so that a loop of the thread is detected. In this case, the thread merging is not carried out and ACK is not returned. Here, the thread length of the thread (R6, <unknown>) already stored at the output link between the own node device and the node device R4 will not be updated from <unknown>, so that the update of the thread length is not notified to the node device R4.

[0132] As a result, the merged thread as indicated by a dashed line in FIG. 4 will remain. Note that in FIG. 4, symbols such as R1 and R6 attached to different portions of the dashed line indicate the thread colors at the respective portions.

[0133] Next, the case where the route change occurs at the node device R10 in the state of FIG. 4 so that a next hop node is changed from the node device R3 to a node device R11 will be described with references to FIG. 5 and FIG. 6 which show a thread and a message to be notified in this case.

[0134] When the next hop node of the node device R10 is changed from the node device R3 to the node device R11, the node device R10 first deletes the output link between the own node device and the node device R3 on the old route, and notifies the deletion of the thread (R6, <unknown>) that has been stored there (see FIG. 5). The notification of thread deletion is realized by transmitting a thread deletion message. Next, the node device R10 generates a thread (R10, <unknown>), generates an output link between the own node device and the node device R11 on the new route, stores the thread (R10, <unknown>) at the output link, and notifies a thread (R10, <unknown>) obtained by incrementing the thread length of the generated thread (R10, <unknown>) by 1, to the node device R11 (see FIG. 6).

[0135] When the node device R3 receives the deletion notice for the thread (R6, <unknown>), the node device R3 deletes the corresponding input link.

[0136] On the other hand, upon receiving the thread (R10, <unknown>), the node device R11 generates a new link between the own node and the node device R10, and stores the received thread (R10, <unknown>). Then, the node device R11 generates an output link between the own node device and the node device R1, stores the received thread (R10, <unknown>) at the output link, and notifies a thread (R10, <unknown>) obtained by incrementing the thread length of the received thread (R10, <unknown>) by 1, to the node device R1.

[0137] Upon receiving the thread (R10, <unknown>), the node device R1 generates a new input link between the own node device and the node device R11, and stores the received thread (R10, <unknown>). Here, the output link between the own node device and the node device R2 already exists, so that the thread merging is carried out. In this case, the thread length=<unknown> of the received thread (R10, <unknown>) is larger than the thread length=0 of the thread (R1, 0) currently stored at the output link, so that the thread (R1, 0) currently stored at the output link is replaced by the received thread (R10, <unknown>) and a thread (R10, <unknown>) obtained by incrementing the thread length of the received thread (R10, <unknown>) by 1 is notified to the node device R2.

[0138] The node device R2 receives the thread (R10, <unknown>). At this point, the input link between the own node device and the node device Ri already exists, so that the thread (R1, 1) currently stored at the input link is replaced by the received thread (R10, <unknown>). Also, the output link between the own node device and the node device R3 already exists, so that the thread (R1, 1) currently stored at the output link is replaced by the received thread (R10, <unknown>) and a thread (R10, <unknown>) obtained by incrementing the thread length of the received thread (R10, <unknown>) by 1 is notified to the node device R3.

[0139] The node device R3 receives the thread (R10, <unknown>). At this point, the input link between the own node device and the node device R2 already exists, so that the thread (R1, 2) currently stored at the input link is replaced by the received thread (R10, <unknown>). Also, the output link between the own node device and the node device R4 already exists, so that the thread (R6, 3) currently stored at the output link is replaced by the received thread (R10, <unknown>) and a thread (R10, <unknown>) obtained by incrementing the thread length of the received thread (R10, <unknown>) by 1 is notified to the node device R4. This thread will be forwarded up to the node device R10 (see FIG. 6). At this point, the node device R10 detects a loop of the thread (R10, <unknown>), but the thread length is already <unknown> so that the update of the thread length is not notified to the node device R11.

[0140] As a result, the merged thread as indicated by a dashed line in FIG. 7 will remain.

[0141] Next, the case where the route change occurs at the node device R4 in the state of FIG. 7 so that a next hop node is changed from the node device R9 to a node device R5 will be described with references to FIG. 8 and FIG. 9 which show a thread and messages to be notified in this case. Here, FIG. 8 corresponds to Pattern 1 described below, while FIG. 9 corresponds to Pattern 2 described below.

[0142] When the next hop node of the node device R4 is changed from the node device R9 to the node device R5, the node device R4 first deletes the output link between the own node device and the node device R9 on the old route, and notifies the deletion of the thread (R10, <unknown>) that has been stored there (see FIG. 8 and FIG. 9). The notification of thread deletion is realized by transmitting a thread deletion message. Next, the node device R4 generates a thread (R4, <unknown>), generates an output link between the own node device and the node device R5 on the new route, stores the thread (R4, <unknown>) at the output link, and notifies a thread (R4, <unknown>) obtained by incrementing the thread length of the generated thread (R4, <unknown>) by 1, to the node device R5.

[0143] When the node device R5 which is the egress node receives the thread (R4, <unknown>), the node device R5 generates a new input link between the own node device and the node device R4, sets the path length to <unknown>, and returns ACK for the received thread. Here, a label allocation success message is used as ACK for the received thread. At this point, the node device R5 sets the thread color to be stored at the generated input link to 0.

[0144] On the other hand, suppose that the thread deletion on the old route is notified up to the node device R11 while deleting the input link and the output link at each node.

[0145] Now, the thread deletion notice is forwarded on the old route and ACK for the thread is forwarded on the new route, but the subsequent operation will be different depending on which one of these arrives first. In the following, two cases including (1) the case where the thread deletion notice forwarded on the old route arrives at the ingress node earlier than ACK for the thread forwarded on the new route, and (2) the case where the thread deletion notice forwarded on the old route arrives at the ingress node later than ACK for the thread forwarded on the new route, will be described separately as Pattern 1 and Pattern 2, respectively.

[0146] (Pattern 1)

[0147] First, the case where the thread deletion notice forwarded on the old route arrives at the ingress node earlier than ACK for the thread forwarded on the new route will be considered.

[0148] Upon receiving the thread deletion notice from the node device R4, the node device R9 deletes the corresponding input link and the corresponding output link, and forwards the thread deletion notice to the node device R10. The node devices R10 and R11 carry out the similar operation.

[0149] When the node device R1 receives the thread deletion notice from the node device R11, the node device R1 deletes the input link between the own node device and the node device R11. The node device R1 also has the output link corresponding to the deleted input link, but this output link is not deleted because the ingress flag is on.

[0150] Upon receiving ACK from the node device R5, the node device R4 sets the path length to the thread length=<unknown> of the thread (R4, <unknown>) corresponding to ACK, returns ACK to the upstream side node device R3, and sets the thread color to be stored at the input link between the own node device and the upstream side node device R3 to 0. Upon receiving ACK, the node device R3 sets the path length to the thread length=<unknown> of the thread (R10, <unknown>) corresponding to ACK, returns ACK to the upstream side node devices R2 and R8, and sets the thread color to be stored at the input links between the own node device and the upstream side node devices R2 and R8 to 0. The node devices R8, R7 and R2 carry out the similar operation.

[0151] When the ingress node device R6 receives ACK, the node device R6 sets the path length to the thread length=0 of the thread (R6, 0) corresponding to ACK.

[0152] When the ingress node device R1 receives ACK, it becomes capable of carrying out the label switching upon receiving an ACK for the thread (R10, <unknown>) from the node device R2. In this case the node device Ri changes the path length from <unknown> to 0, and sends an update message (UPDATE) to the node device R2 with a thread (0, 1).

[0153] When the node device R2 receives the UPDATE from the node device R1 with the thread (0, 1), the node device R2 sends an UPDATE to the node device R3 with a thread (0, 2).

[0154] When the node device R3 receives the UPDATE from the node device R2 with the thread (0, 2), the path length is changed from <unknown> to 3 and the node device R3 sends an UPDATE to the node device R4 with a thread (0, 4).

[0155] Eventually the node device R5 recieves an UPDATE with a thread (0, 5) and the path length at the node device R5 is changed to 5. The node device R5 does not truen an ACK.

[0156] (Pattern 2)

[0157] Next, the case where the thread deletion notice forwarded on the old route arrives at the ingress node later than ACK for the thread forwarded on the new route, will be considered.

[0158] Upon receiving ACK from the node device R5, the node device R4 sets the path length to the thread length=<unknown> of the thread (R4, <unknown>) corresponding to ACK, returns ACK to the upstream side node device R3, and sets the thread color to be stored at the input link between the own node device and the upstream side node device R3 to 0. Upon receiving ACK, the node device R3 sets the path length to the thread length=<unknown> of the thread (R10, <unknown>) corresponding to ACK, returns ACK to the upstream side node devices R2 and R8, and sets the thread color to be stored at the input links between the own node device and the upstream side node devices R2 and R8 to 0. The node devices R1, R2, R8 and R7 carry out the similar operation.

[0159] When the ingress node device R6 receives ACK, the node device R6 sets the path length to the thread length=0 of the thread (R6, 0) corresponding to ACK.

[0160] Here, suppose that the node device R11 receives ACK from the node device R1 before receiving the thread deletion notice from the node device R11.

[0161] Then, upon receiving ACK from the node device R1, the node device R11 sets the path length to the thread length=<unknown> of the thread (R11, <unknown>) corresponding to ACK, returns ACK to the upstream side node device R10, and sets the thread color to be stored at the input link between the own node device and the upstream side node device R10 to 0. Next, the node device R11 receives the thread deletion notice from the node device R11, but the confirmation flag of the path is already on so that the input link is not deleted and the thread deletion notice is not notified to the node device R1.

[0162] When the node device R10 receives ACK from the node device R11, the corresponding output link is already absent, so that the node device R10 transmits a label release message (RELEASE) to the node device R11. Upon receiving the label release message from the node device R10, the node device R11 deletes the input link between the own node device and the node device R10 as well as the output link between the own node device and the node device R1, and forwards the label release message to the node device R1.

[0163] Upon receiving the label release message, the node device R1 deletes the input link between the own node device and the node device R11. At this point, the ingress flag is on so that the output link corresponding to the input link is not deleted, and the path length is changed from <unknown> to 0. Also, the confirmation flag of the path is on and the path length will not be increased so that the node device RI notifies a thread (0, 1) in which the thread color is set equal to 0 and the thread length is set equal to a value obtained by incrementing the path length by 1, to the node device R2. At this point, the thread (0, 1) is entered into the update message.

[0164] Each of the node devices R2, R3 and R4 that received the thread with the thread color=0 replaces the thread to be stored at the receiving link to the received thread, and then sets the larger one of the thread length of the input link that stores the thread with the thread color=0 and the thread length of the received thread, as a new path length. If the path length is updated, a thread with the thread color=0 obtained by incrementing the updated path length by 1 is notified to the downstream side node by using the update message. This notification reaches to the node device R5, and eventually the path length at the node device R5 is changed to 5. The node device R5 does not return ACK.

[0165] As a result, a path R1→R2→R3→R4→R5 as indicated by a bold line in FIG. 10 is eventually formed.

[0166] By the above operation, no matter where on the looping path does the route change occur, it becomes possible to return to the normal path without requiring any retry when the loop is released.

[0167] Here, the label allocation is not carried out at a node that is notifying a thread while there is a loop so that it is possible to save the label resources. In addition, packets of the flow for which the label allocation is not carried out can be discarded at the proxy ingress node so that it is also possible to save the network resources as well.

[0168] Note that, in the case where the route change occurs at the node device R10 in the state shown in FIG. 7 so that the next hop node of the node device R10 is changed from the node device R11 to the node device R3, the node device R10 first notifies the deletion of the thread (R10, <unknown>) to the node device R11, generates a new thread (R10:1, <unknown>), and notifies a thread (R10:1, <unknown>) obtained by incrementing the thread length of the generated thread (R10:1, <unknown>) by 1, to the node device R3. This thread is notified to the node devices R3, R4, R9, and R10, and the node device R10 receives the thread (R10:1, <unknown>) that was generated by the own node device. At this point, the thread length remains unchanged from <unknown> so that the update of the thread length is not notified to the node device R3.

[0169] <Second Concrete Example>

[0170] Next, the label switched path set up operation to be carried out by a node device according to one embodiment of the present invention will be described using another concrete example.

[0171] FIG. 11 shows another exemplary label switched network formed by connecting node devices of this embodiment. In FIG. 11, all or a part of node devices R1 to R7 may be connected to other node devices that are not shown in the figure.

[0172] In FIG. 11, a link between neighboring nodes indicates that the label switching is possible between these nodes, and an arrowhead of the link indicates a direction of a current next hop of a flow. Note that FIG. 11 also shows exemplary thread contents which will be explained later on.

[0173] It is assumed here that node devices R1, R2, R3 and R4 on the path store the path lengths 0, 1, 2 and 3, respectively.

[0174] Now, in the configuration of FIG. 11, suppose that the node device R1 starts the path set up.

[0175] The node device RI turns the ingress flag on, generates an output link between the own node device and a node device R2, generates a thread (R1, 0), stores the thread (R1, 0) at the output link, and notifies a thread (R1, 1) to the node device R2.

[0176] Upon receiving the thread (R1, 1), the node device R2 generates a new input link between the own node device and the node device R1, and stores the thread (R1, 1). Then, the node device R2 generates an output link between the own node device and a node device R3, stores the received thread (R1, 1) at the output link, and notifies a thread (R1, 2) obtained by incrementing the thread length of the received thread (R1, 1) by 1, to the node device R3. The node device R4 carries out the similar operation.

[0177] Upon receiving the thread (R1, 4) from the node device R4, the node device R5 which is the egress node generates a new input link between the own node device and the node device R4, and stores the thread (R1, 4). Then, the node device R5 sets the path length to 4 and returns ACK for the received thread. Here, a label allocation success message is used as ACK for the received thread.

[0178] Upon receiving ACK from the node device R5, the node device R4 sets the path length to the thread length=3 of the thread (R1, 3) corresponding to ACK, and returns ACK to the upstream side node device R2. The node device R2 carries out the similar operation.

[0179] When the ingress node device R1 receives ACK, the node device R1 sets the path length to the thread length=0 of the thread (R1, 0) corresponding to ACK.

[0180] In this way, a label switched path R1→R2→R3→R4→R5 as indicated by a bold line in FIG. 12 is set up.

[0181] Next, the case where the route change occurs at the node device R2 in the state of FIG. 12 so that a next hop node is changed from the node device R3 to a node device R6 will be described with reference to FIG. 13 which shows threads and messages to be notified in this case.

[0182] When the next hop node of the node device R2 is changed from the node device R3 to the node device R6, the node device R2 generates a thread (R2, 1) having the thread length equal to the current path length, generates an output link between the own node device and the node device R6 on the new route, stores the thread (R2, 1) at the output link, and notifies a thread (R2, 2) obtained by incrementing the thread length of the generated thread (R2, 1) by 1, to the node device R6.

[0183] Upon receiving the thread (R2, 2), the node device R4 generates a new input link between the own node device and the node device R2, and stores the thread (R2, 2). Then, the node device R4 generates an output link between the own node device and a node device R7, stores the received thread (R2, 2) at the output link, and notifies a thread (R2, 3) obtained by incrementing the thread length of the received thread (R2, 2) by 1, to the node device R7. The node device R7 carries out the similar operation.

[0184] Upon receiving the thread (R2, 4), the node device R4 generates a new input link between the own node device and the node device R7, and stores the thread (R2, 4). Then, the node device R4 carries out the flow merging because the output link between the own node and the node device R5 for the same flow already exists. At this point, the path length increases from 3 to 4 after the merging so that the received thread (R2, 4) is stored at the output link and a thread (R2, 5) obtained by incrementing the thread length of the received thread (R2, 4) by 1 is sent to the node device R5.

[0185] When the egress node device R5 receives the thread (R2, 5), the node device R5 sets the path length to the thread length=5 of the received thread, and returns ACK for the received thread to the node device R4.

[0186] Upon receiving ACK from the node device R5, the node device R4 sets the path length to the thread length=4 of the thread (R2, 4) corresponding to ACK, and returns ACK to the upstream side node device R7. Upon receiving ACK, the node device R7 sets the path length to the thread length=3 of the thread (R2, 3) corresponding to ACK, and returns ACK to the upstream side node device R6. The node device R6 carries out the similar operation.

[0187] When the node device R2 receives ACK from the node device R6, the label switched path R1→R2→R6→R7→R4→R5 is set up on the new route. In addition, the node device R2 deletes the output link between the own node device and the node device R3 on the old route, and transmits the label release message to the node device R3.

[0188] Upon receiving the label release message, the node device R3 deletes the input link between the own node device and the node device R2 as well as the output link between the own node device and the node device R4, and forwards the label release message to the node device R4.

[0189] Upon receiving the label release message, the node device R4 deletes the input link between the own node device and the node device R3, but the output link is not deleted because there is another input link. Also, the path length is not increased after the deletion of the input link so that the path length change with respect to the downstream side node is also not carried out.

[0190] As a result, a path as indicated by a bold line in FIG. 14 is formed.

[0191] Here, even when the label release message cannot be forwarded because of the breakdown of the physical link on the old route, the same result can be obtained if the node device R4 carries out the same operation as in the case of receiving the label release message from the node device R3, upon noticing the breakdown of the downstream side node of the physical link.

[0192] Next, the case where the route change occurs again at the node device R2 in the state of FIG. 14 so that a next hop node is changed from the node device R6 to the node device R3 will be described with reference to FIG. 15 which shows threads and messages to be notified in this case.

[0193] When the next hop node of the node device R2 is changed from the node device R6 to the node device R3, the node device R2 generates a thread (R2, 1) having the thread length equal to the current path length, generates an output link between the own node device and the node device R3 on the new route, stores the thread (R2, 1) at the output link, and notifies a thread (R2, 2) obtained by incrementing the thread length of the generated thread (R2, 1) by 1, to the node device R3.

[0194] Upon receiving the thread (R2, 2), the node device R3 generates a new input link between the own node device and the node device R2, and stores the thread (R2, 2). Then, the node device R3 generates an output link between the own node device and the node device R4, stores the received thread (R2, 2) at the output link, and notifies a thread (R2, 3) obtained by incrementing the thread length of the received thread (R2, 2) by 1, to the node device R4.

[0195] Upon receiving the thread (R2, 3), the node device R4 generates a new input link between the own node device and the node device R3, and stores the thread (R2, 3). Then, the node device R4 carries out the flow merging because the output link between the own node and the node device R5 for the same flow already exists. At this point, the path length remains unchanged from 4 after the merging so that the node device R4 returns ACK to the node device R3 immediately.

[0196] Upon receiving ACK from the node device R4, the node device R3 sets the path length to the thread length=2 of the thread (R2, 2) corresponding to ACK, and returns ACK to the upstream side node device R2.

[0197] When the node device R2 receives ACK from the node device R3, the label switched path R1→R2→R3→R4→R5 is set up on the new route. In addition, the node device R2 deletes the output link between the own node device and the node device R6 on the old route, and transmits the label release message to the node device R6.

[0198] Upon receiving the label release message, the node device R6 forwards the label release message to the node device R4. The node device R7 carries out the similar operation.

[0199] Upon receiving the label release message, the node device R4 deletes the input link between the own node device and the node device R7, but the output link is not deleted because there is another input link. Also, the path length is decreased from 4 to 3 after the deletion of the input link so that the path length of 3 is set to the downstream side node and a thread (0, 4) obtained by incrementing the path length by 1 is sent to the node device R5.

[0200] The node device R5 that received the thread with the thread color=0 sets the path length to the thread length of the received thread, but does not return ACK.

[0201] As a result, the path as indicated by a bold line in FIG. 12 is set up again.

[0202] If the new route forms a loop, ACK for the thread will not return until the loop is resolved. In this case, the path on the old route will not be released so that it is possible to continue to use the path on the old route.

[0203] Note however that the present invention is also effective in the case of setting up a path on the new route after releasing a path on the old route at a time of the route change.

[0204] In the following, an exemplary internal database, an exemplary processing procedure of a node device at a time of thread receiving, an exemplary processing procedure of a node device at which a route change occurred, and an exemplary message format according to this embodiment will be described.

[0205] First, an exemplary configuration of an internal database to be used for the loop detection in the node device of the present invention will be described.

[0206] FIG. 16 and FIG. 17 show an exemplary configuration of the internal database.

[0207] Individual label switched path information is stored in a path entry (path_entry), and a path list (path_list 10 of FIG. 16) is a linked list of path entries.

[0208] The path entry has an input link list (input link_list), an output link list (output_link_list), a flow identifier (flow_id), a path length (length), a confirmation flag (cflag), and an ingress flag (ingress_flag).

[0209] The input link list is a linked list of link entry (link_entry 20 of FIG. 16) for storing an information on individual input side link of the path.

[0210] The output link list is a linked list of link entry (link_entry 30 of FIG. 16) for storing an information on individual output side link of the path. In the case of multicast, it has a plurality of link entries. Also, even in the case of unicast, it may have two link entries for an old route and a new route at a time of the route change.

[0211] The flow identifier (or flow ID) stores an information on a flow that is label switched on this path.

[0212] The path length stores the number of hops from the most distant ingress node.

[0213] The confirmation flag is a flag for indicating whether there is a thread that is awaiting ACK or not.

[0214] The ingress flag is a flag for indicating whether it is the ingress node of the path or not.

[0215] The link entry stores information on an interface number (interface_number), a link identifier (link_id), a neighboring node address (neighbor_address), a thread (thread), a path entry (pass_entry).

[0216] The interface number is a number uniquely allocated to each logical interface within the node.

[0217] The link identifier is an identifier for identifying a link between the neighboring nodes.

[0218] The neighboring node address stores an address of a node on the other side of the link.

[0219] The thread is a pointer to a thread entry (40 of FIG. 16). The thread entry has attributes of a thread color (color) and a thread length (length). The thread entry is shared among the input/output link entries of the same path.

[0220] The path entry in the link entry is a pointer for pointing a path entry which has this link entry in the input or output link list. This enables access to the path entry information from each link, as well as access from the input link side to the output link side information or access from the output link side to the input link side information.

[0221] Next, FIG. 17 shows an exemplary thread entry to be shared among the input/output link entries in a given path entry. FIG. 17 shows link entries 20-1 to 20-3 of the input side links, a link entry 30-1 of the output side link, and thread entries 40-1 to 40-3.

[0222] FIG. 17 shows a state where three threads (5, 5), (10, 5) and (101, 2) are merged. In this case, the thread (10, 5) is shared by the input link entry and the output link entry. This implies that, among the threads (5, 5) and (10, 5) which have the largest thread length (=5), one with the largest thread color value has been selected as the thread after merging.

[0223] Next, a processing procedure of the node device at a time of thread receiving will be described. FIG. 18 shows a flow chart for an exemplary processing procedure of the node device at a time of thread receiving. Here, an exemplary case of updating the path length without waiting for ACK for the thread will be described.

[0224] First, it is set that F denotes a received flow identifier, i denotes a received interface number, j denotes a received link identifier, T denotes a received thread, and N denotes a neighboring node that transmitted the thread (step S1).

[0225] Then, a thread input processing is carried out (step S2). In the input processing, an input link Li that is uniquely specified by (received interface number i, received link identifier j) is searched, and if a corresponding entry cannot be found, it is newly created and a set of (N, T) is registered into the input link Li. Then, if paths are not to be merged, a new path entry P is created and a set of (flow identifier F, input link Li) is registered into the path entry P. If paths are to be merged, the input link Li is registered into the existing path entry P that has the flow identifier F.

[0226] Then, the following thread processing is carried out.

[0227] First, whether or not the own node is the egress node, that is, the end point of the path, or not is checked (step S3). If the own node is the egress node, the path length is set equal to the received thread length (P.length:=T.length) (step S7), an ACK notification processing is carried out (step S9) and the processing is finished.

[0228] On the other hand, if the own node is not the egress node, whether or not the confirmation flag is on (P.cflag==on?) is checked (step S4). If the confirmation flag is on, there is no thread that is waiting for ACK, so that whether or not the path length is greater than or equal to the thread length (P.length>=T.length?) is checked (step S8), and if yes, the ACK notification processing is carried out (step S9) and the processing is finished. Otherwise, whether it is a loop or not cannot be judged at this node, so that a thread notification processing is carried out (step S6) and the processing is finished.

[0229] On the other hand, when the confirmation flag is off at the step S4, whether or not the thread T forms a loop and, the path length is not equal to <unknown> or the thread length is not less than a threshold Lmax, is checked (step S5), and if not, the thread notification processing is carried out (step S6) and the processing is finished.

[0230] Otherwise, whether or not the path length is equal to <unknown> or not is checked (step S10), and if not, a path length correction processing is carried out (step S12), the thread color of the thread stored at the input link Li is set equal to 0 (T.color:=0) (step S12), and the processing is finished. If the path length is equal to <unknown>, the thread color of the thread stored at the input link Li is set equal to 0 (T.color:=0) and the processing is finished.

[0231] In the ACK notification processing, the confirmation flag of the path is turned on (P.cflag:=on), and ACK is returned to the neighboring node N.

[0232] In the thread notification processing, the confirmation flag of the path is turned off (P.cflag off), the thread merging is carried out if necessary, an output link Lo of the path entry P is newly created if it does not exist, and the thread is notified to the neighboring node specified by Lo.neighbor_address. Note that threads that are targets of the merging are those threads for which the thread length is not equal to 0 among threads registered at the input link.

[0233] In the thread length correction processing, the path length is set equal to <unknown> and a thread with the thread length equal to the path length is notified to the downstream side neighboring node specified by Lo.neighbor_address of the output link Lo of the path.

[0234] Next, the processing procedure of the node device at which the route change occurred will be described. FIG. 19 shows a flow chart for an exemplary processing procedure of the node device at which the route change occurred. Here, an exemplary case of updating the path length without waiting for ACK for the thread will be described.

[0235] This processing is to be carried out with respect to each path having a flow identifier of a flow that is to be a target of the route change.

[0236] Initially, it is set that a path that is a target of the route change processing is denoted as P (step S21).

[0237] First, whether or not this node is the egress node on the new route after the route change is checked (step S22). If this node is the egress node, the processing is finished immediately.

[0238] If this node is not the egress node, whether or not the path length is greater than or equal to a threshold Lmax is checked (P.length>=Lmax?) (step S23), and if yes, the processing is finished immediately.

[0239] Otherwise, a new thread T is generated and the thread length is set equal to the path length (T.length:=P.length) (step S24).

[0240] Then, whether or not the confirmation flag of the path P is off is checked (P.cflag==off?) (step S25), and if yes, there is a thread that is waiting for ACK on the old route so that a thread deletion processing for the old route is carried out (step S26), and a thread notification processing for the new route is carried out (step S27).

[0241] In the thread deletion processing for the old route, the deletion of the thread is notified to the downstream side neighboring node Lo.neighbor_address of the output link Lo of the path P on the old route.

[0242] On the other hand, if the confirmation flag of the path P is on at the step S25, there is no thread that is waiting for ACK on the old route, so that nothing is done with respect to the old route and the thread notification processing for the new route is carried out (step S27).

[0243] In the thread notification processing for the new route, the confirmation flag of the path P is turned off (P.cflag:=off), and the thread is notified to the downstream side neighboring node Lo.neighbor_address of the output link Lo on the new route.

[0244] Next, the format of the label delivery protocol message to be exchanged among nodes for the sake of the loop detection at the node device will be described. FIG. 20 shows an exemplary message format.

[0245] The meanings of fields constituting this message format of FIG. 20 are as follows.

[0246] A neighboring node identifier indicates an information regarding a message transmission node. As the neighboring node identifier, L3 address or [L3 address+ID locally allocated by the neighboring node (label space id)] can be used. When the L3 address is a router ID, the label space id specifies sharing or division or the label region among a plurality of interfaces of the same node or among a plurality of neighboring nodes connected to the same interface.

[0247] A message type describes a type of a message to be used by the label delivery protocol. The message type includes a label allocation request message (SETUP), a label release message (RELEASE), an update message (UPDATE), a cancel message, a label allocation success message (ACK), an update success message, and a trigger message.

[0248] A message length describes an entire length of fields subsequent to the message length field.

[0249] A flow identifier is an information for identifying a flow, and the flow identifier as described above (or that disclosed in the commonly assigned copending U.S. patent application Ser. No. 09/131,361) can be used, for example. The flow identifier comprises a flow type and a flow type specific flow definition. The flow identifier is contained at least in the label allocation request message.

[0250] A link identifier is an identifier that is unique within each interface of each node and used in order to distinguish a plurality of paths having the same flow identifier between the neighboring nodes. The label itself can be used as the link identifier.

[0251] A thread color and a thread length describe an information of a thread to be notified.

[0252] The thread color is specified by a set of an address of a node that generated the thread and a local ID locally allocated within the node. The node allocates the local ID such that the previously allocated value will not be used for the same flow. The simplest way of realizing such an allocation is to increment the local ID at the node every time the allocation is made.

[0253] The thread length indicates a hop count from the ingress node. Here, however, if the route is looping, the thread length is corrected at the node that generated the thread as described in the first concrete example.

[0254] A label is a value attached to a header of a packet that is to be label switched. It is notified to the neighboring node by the label allocation success message in the case of downstream on demand allocation, or by the label allocation request message in the case of upstream allocation or downstream allocation.

[0255] In the case of downstream on demand allocation or downstream allocation in which a thread flows through a path for which the label is not yet set up, the thread is transferred from the upstream to the downstream using the label allocation request message. In the case of upstream allocation, the thread is transferred from the upstream to the downstream using the label allocation success message. In the case where a thread flows through a path for which the label is already set up, the thread is transferred from the upstream to the downstream using the update message. In the case of releasing the label, the label release message is used, and the label release message may not include a thread field.

[0256] In the case of notifying the deletion of a thread, the cancel message is used. In the case where the cancel message flows through a path for which the label is not yet set up, the thread is deleted and the link is also deleted. In the case where the cancel message flows through a path for which the label is already set up, the thread is deleted but the link is not deleted.

[0257] In the case where ACK for the thread flows through a path for which the label is not yet set up, the label allocation success message is used. In the case where ACK for the thread flows through a path for which the label is already set up, the update success message is used. The label allocation success message and the update success message may not contain the thread information.

[0258] The trigger message is used in the case of generating a path by the initiative of the egress node, in order to notify the path set up request to the downstream side neighboring node on the new route at the route changing node.

[0259] In summary, the present invention provides a method for setting up a label switched path, in which whether the label switched path forms a loop or not is judged at a node that received a request message (such as SETUP, UPDATE) regarding a label switched path set up for a packet flow, on a basis of label switched path information stored in a first mode at the node that received the request message, where the request message includes a flow identifier for identifying the packet flow (which can be replaced by a link identifier in the case of UPDATE) and information (such as thread) indicating that it is a message currently awaiting a response (such as ACK) regarding the packet flow, and the first mode indicates that a message from which the label switched path information originates is a message currently awaiting a response. Then, the flow identifier contained in the request message is stored as the label switched path information in the first mode at the node device that received the request message (by turning the confirmation flag off, for example), and the request message is transferred from the node that received the request message to another node on a route of the packet flow, when the node that received the request message cannot judge that the label switched path does not form a loop. Also, a response message for the request message is returned from the node that received the request message when the node that received the request message judges that the label switched path does not form a loop. Then, the label switched path information currently stored in the first mode at a node that received the response message is changed into a second mode different from the first mode (by turning the confirmation flag on, for example), such that the label switched path information that is changed into the second mode will not be used subsequently in judging whether any requested label switched path forms a loop or not at the node that received the response message and the label switched path will become available at the node that received the response message.

[0260] In this way, the label switched path set up request message is transferred up to a node that can confirm that the path does not form a loop, while each node through which the message passes stores the fact that it is in a message processing state. Then, in a process where a response message is returned from that node, the message processing state of each node on the route of the path is released sequentially, and this releasing establishes the path set up, so that it suffices to make the judgement as to whether or not a loop is formed only with respect to a message (thread) for which the message processing state is currently stored, by ignoring the other messages for which the message processing state is currently not stored. Consequently, the amount of checking for the loop detection can be reduced and therefore the loop detection can be realized more easily.

[0261] In addition, at a time of the route change, the old path is already established (and hence not a subject of the loop judgement), so that even a case where the new path and the old path collide will not be erroneously judged as a loop. Consequently, it is also possible to continue to send packets through the old path until the new path is established, and it is also possible to continue to utilize the link information at a portion which is shared by the new path and the old path.

[0262] In this method, the response message may be conditionally transferred from the node that received the response message to another node that transferred the request message and currently stores the label switched path information in the first mode.

[0263] Also, in this method, the node that received the request message may not carry out transfer of the request message or returning of the response message when the node that received the request message judges that the label switched path forms a loop.

[0264] Also, in this method, the node that received the request message can judge whether the label switched path forms a loop or not, according to whether or not the label switched path information containing the flow identifier that is identical to that contained in the request message is stored in the first mode at the node that received the request message.

[0265] Also, in this method, the request message may also contain a message identifier for network globally identifying each message that is being processed for the packet flow, and the node device that received the request message can store the label switched path information containing the message identifier and the flow identifier.

[0266] In this case, the node that received the request message can judge whether the label switched path forms a loop or not, according to whether or not the label switched path information containing the flow identifier and the message identifier that are identical to those contained in the request message is stored in the first mode at the node that received the request message. Here, it is possible to make this judgement also according to whether or not a newly received message and a message that is previously received and currently being processed are related to different input side links.

[0267] Also, in this case, the message identifier may contain an identification information of a node (proxy ingress node, for example) that allocated the message identifier contained in the request message.

[0268] Also, in this method, the request message may contain another information (thread length, for example) from which a number of hops from an ingress node of the label switched path up to the node that received the request message can be obtained, and the node that received the request message can handle the request message equivalently as in a case of judging that the label switched path forms a loop, when the number of hops is judged as exceeding a prescribed value according to that another information.

[0269] Also, in this method, the node that received the request message can judge that the label switched path does not form a loop, when own node is an egress node of the label switched path or when a corresponding established label switched path exists on a downstream side of own node and it is allowed to connect the label switched path to that corresponding established label switched path (the case where the thread length is less than or equal to the path length of the established label switched path, for example).

[0270] Also, in this method, the request message can be actively transmitted by an ingress node of the label switched path, an intermediate node of an already established label switched path at which a route change occurred, or an egress node of an already established label switched path that newly recognized a downstream side neighboring node.

[0271] Also, in this method, the node that received the request message may also carry out allocation of a label contained in a link information provided for label switching purpose, at a time of returning the response message.

[0272] In this way, it becomes possible to allocate labels to be actually used for the switching after confirming that it is possible to set up a loopless label switched path end-to-end so that it is possible to save the label resources.

[0273] Also, in this method, a cancellation message (the thread deletion notice, for example) for the request message may be transmitted from a node that actively transmitted the request message, when the node that received the request message has judged that the label switched path forms a loop and a need to set up the label switched path no longer exists (in the case where the corresponding input side link information is deleted or the case there the route change occurred, for example), and the flow identifier contained in the request message as stored in the first mode at each node that transferred the request message can be maintained until the cancellation message corresponding to the request message is received.

[0274] In this way, it becomes possible to prevent the unnecessary label allocation so that it is possible to save the label resources.

[0275] Also, in this method, when the node that received the request message currently stores the label switched path information corresponding to another request message regarding the label switched path set up in the first mode and the node that received the request message cannot judge whether the label switched path forms a loop or not, the node that received the request message can handle the request message and that another request message together as a single message.

[0276] For example, in the case where the request message contains an information regarding the a number of hops from an ingress node of the label switched path up to the node that received the request message, the identifier of the message for which this hop count is larger is used as the message identifier of that single message. Then, when this newly determined message identifier (and the hop count) is different from that of the already transferred message (that is currently being processed), this change is notified to nodes on the route of the path. In this way, the number of messages and thereby the number of message processing states can be reduced.

[0277] Also, in this method, the request message may contain another information from which a number of hops from an ingress node of the label switched path up to the node that received the request message can be obtained, and the node that received the request message can correct that another information regarding the number of hops from the ingress node of the label switched path up to own node, when the node that received the request message judges that the label switched path forms a loop.

[0278] For example, by updating the hop count to a special value <unknown>, it becomes possible to prevent the hop count from being in an erroneously incremented state when a message that has been maintained in the message processing state due to loop is to be used later on.

[0279] Next, an exemplary configuration of the node device according to the present invention will be described with references to FIG. 21 and FIG. 22.

[0280] The node device 100 of FIG. 21 comprises a control message processing unit 11, a switch unit 12, a label information table 13, and a plurality of labelled frame transmission and reception units 14-1 to 14-n.

[0281] In this node device 100, the labelled frames are entered from external devices, switched at the switch unit 12, and then outputted to the external devices.

[0282] Each labelled frame transmission and reception unit 14 enters the labelled frame from the external device or the switch unit 12, refers to the label value written in the header of the frame, and if necessary, carries out the rewriting of the header of the labelled frame and the attaching/removing of an internal header which is necessary in switching frames at the switch unit 12, according to the label information stored in the label information table 13, and then outputs the labelled frame to the switch unit 12 or the external device.

[0283] The switch unit 12 is a unit for switching and outputting the labelled frame received from one labelled frame transmission and reception unit 14 to another labelled frame transmission and reception unit 14 or the control message processing unit 11 according to the internal header information.

[0284] The control message processing unit 11 carries the protocol message processing used for the purpose of the label allocation/release and the label switched path loop detection, as well as reading/writing of information with respect to the label information table according to the need.

[0285] The label information table 13 stores the flow table containing information on the input side label and the output side label.

[0286] FIG. 22 shows a detail configuration of the control message processing unit 11, which comprises a request message receiving unit 11a, a loop judging unit 11b, a processing unit 11c, a response message receiving unit 11d, and a message transfer unit 11e.

[0287] The loop judging unit 11bjudges whether the label switched path forms a loop or not upon receiving a request message regarding the label switched path set up for a packet flow through the request message receiving unit 11a, on a basis of label switched path information stored in a first mode at the label information table 13, where the request message includes a flow identifier for identifying the packet flow and information indicating that it is a message currently awaiting a response regarding the packet flow, and the first mode indicates that a message from which the label switched path information originates is a message currently awaiting a response.

[0288] The processing unit 11cstores the flow identifier contained in the request message as the label switched path information in the first mode at the label information table 13 and transfers the request message to another node on a route of the packet flow through the message transfer unit 11e, when the loop judging unit 11bcannot judge that the label switched path does not form a loop, and returns a response message for the request message through the message transfer unit 11ewhen the loop judging unit 11bjudges that the label switched path does not form a loop.

[0289] The processing unit 11calso changes the label switched path information currently stored in the first mode at the label information table 13 into a second mode different from the first mode upon receiving the response message through the response message receiving unit 11d, such that the label switched path information that is changed into the second mode will not be used subsequently in judging whether any requested label switched path forms a loop or not at this node device and the label switched path will become available at this node device.

[0290] As described, according to the present invention, there is no need for the retry mechanism for the purpose of loop prevention, and the updating of one thread can be executed without waiting for ACK at each occasion of updating, so that it is possible to realize the fast path set up.

[0291] Also, threads can be merged so that it is possible to reduce the number of messages required for the purpose of loop prevention, and the message length is bounded at a certain value and does not increase even when the path length increases unlike the path vector scheme so that it is possible to save the network resources.

[0292] Also, when the new route is looping at a time of the route change, it is possible to continue to use a path on the old route. In addition, while there is a loop, the label allocation is not carried out at the node that is notifying the thread, so that it is possible to save the label resources. Moreover, packets of the flow for which the label allocation is not carried out can be discarded at the proxy ingress node so that the network resources can also be saved.

[0293] Also, even if the thread information is lost during the thread notification due to the breakdown of the intermediate node or link, the thread transfer deadlock or the thread information contradiction can be prevented when the label delivery protocol automatically detects a disconnection of a session with the neighboring node, so that it is possible to provide a robust loop prevention mechanism.

[0294] Furthermore, there is no need to store the thread color once the path is set up, so that it is possible to reduce the amount of information to be stored while the network is in stationary state.

[0295] It is to be noted that the above description presupposes the hard state type protocol in which the label allocation message is not transmitted to the path to which the label is allocated once, but the present invention is also effective for the soft state type protocol in which the label allocation message is transmitted regularly even for the path to which the label is allocated once. In the case of the soft state type protocol, the label is released when the label allocation message is not received for a prescribed period of time.

[0296] It is also to be noted that the above described embodiment according to the present invention may be conveniently implemented using a conventional general purpose digital computer programmed according to the teachings of the present specification, as will be apparent to those skilled in the computer art. Appropriate software coding can readily be prepared by skilled programmers based on the teachings of the present disclosure, as will be apparent to those skilled in the software art.

[0297] In particular, the node device of the above described embodiment can be conveniently implemented in a form of a software package.

[0298] Such a software package can be a computer program product which employs a storage medium including stored computer code which is used to program a computer to perform the disclosed function and process of the present invention. The storage medium may include, but is not limited to, any type of conventional floppy disks, optical disks, CD-ROMs, magneto-optical disks, ROMs, RAMs, EPROMs, EEPROMs, magnetic or optical cards, or any other suitable media for storing electronic instructions.

[0299] It is also to be noted that, besides those already mentioned above, many modifications and variations of the above embodiments may be made without departing from the novel and advantageous features of the present invention. Accordingly, all such modifications and variations are intended to be included within the scope of the appended claims.