Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-08-07
2002-12-31
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S392000, C370S396000
Reexamination Certificate
active
06501754
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a node device having a label switched path loop detection function and a label switched path loop detection method.
2. Description of the Background Art
In a network layer protocol in which IP (Internet Protocol) nodes are inter-connected on an NBMA (Non-Broadcast Multiple Access) network, there is a scheme for realizing high speed packet transfer called MPLS (Multi-Protocol Label Switching).
In the MPLS, specific “labels” are allocated to specific packet flows between nodes while a correspondence between an input side label and an output side label is stored at each node, and the label switching is carried out at each node by referring to this information, 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 will be referred to as a label switched path.
In the case of constructing the label switched path, the label allocation protocol is used. The label allocation protocol exchanges label allocation 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.
Usually every time an IP packet passes through a node, a value of an TTL (Time To Live) field (or a hop limit field or their equivalents) within its packet header is decremented by one, and the IP packet is not forwarded any further when the TTL or the like becomes 0. In this way it is possible to prevent a packet to stay in the network indefinitely even when there is a loop in the route.
However, for a packet to be transferred by the label switched path, the IP processing will not be carried out at an intermediate node so that it is impossible to decrement the TTL or the like, and consequently the packet will not leave the label switched path forever if there is a loop in the label switched path. For this reason, it is necessary to provide a label switched path loop detection mechanism or a label switched path loop prevention mechanism in the label allocation protocol.
To this end, in the conventional label allocation protocol, the following two methods are available: (1) a method in which an information on a hop count from an ingress router which originated a label allocation message with respect to the packet flow is included in the label allocation message, and it is judged that a loop is present when the hop count exceeds a threshold (see Doolan et al., “Tag Distribution Protocol”, Internet Draft, draft-doolan-tdp-spec-01.txt, May 1997); and (2) a method in which each node that forwards the label allocation message sequentially adds its own address to the label allocation message, and it is judged that a loop is present when the own address is already written in the received label allocation message (see Rosen et al., “A Proposed Architecture for MPLS”, Internet Draft, draft-rosen-mpls-arch-00.txt, July 1997).
However, the above described method (1) has been associated with a problem that it takes a considerable amount of time until the loop detection because the presence of loop cannot be ascertained until the hop count exceeds the threshold.
Note that in this method if a loop is actually formed or not cannot be ascertained, and even if a loop is actually formed, it is impossible to ascertain a node at which a loop is formed.
On the other hand, the above described method (2) has been associated with a problem that the size of the label allocation message becomes quite large.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a node device and a label switched path loop detection method which are capable of detecting a label switched path loop efficiently and quickly, in the case of constructing a label switched path to which the loop detection based on the TTL field of the IP packet is not applicable.
According to one aspect of the present invention there is provided a node device for label switching entered packets by referring to an input label information capable of identifying a packet flow to be entered and a corresponding information for specifying at least an output side interface, the node device comprising: a memory unit for storing a flow ID capable of network globally identifying a packet flow and an ingress node information regarding an ingress node of a label switched path, according to one label allocation message requesting a set up of the label switched path which is received from one previous hop node; and a judging unit for judging whether a label switched path loop is formed or not according to from which node another label allocation message that contains an identical flow ID and an identical ingress node information as said one label allocation message is received.
According to another aspect of the present invention there is provided a node device for transmitting packets to be label switched using an output label information capable of identifying a packet flow to be outputted, the node device comprising: a transmission unit for transmitting a label allocation message requesting a set up of a label switched path that contain at least an information on said node device as an ingress node information regarding an ingress node of the label switched path; and a judging unit for judging that a label switched path loop is formed upon receiving a label allocation message in which the ingress node information specifies said node device as the ingress node.
According to another aspect of the present invention there is provided a node device for label switching entered packets by referring to an input side label information capable of identifying a packet flow to be entered and a corresponding output label information capable of identifying the packet flow to be outputted, the node device comprising: an exchange unit for exchanging with a neighboring node on a route of one packet flow a label allocation message requesting a set up of a label switched path which contains a flow ID capable of network globally identifying said one packet flow and an ingress node information regarding an ingress node of the label switched path; and a judging unit for judging whether a label switched path loop is formed or not, when a label allocation message that contains a flow ID and an ingress node information that are matching with an existing label switched path is received, according to a change in the input side label information for the existing label switched path.
According to another aspect of the present invention there is provided a node device for label switching entered packets by referring to an input side label information capable of identifying a packet flow to be entered and corresponding one or a plurality of output label information capable of identifying the packet flow to be outputted, the node device comprising: an exchange unit for exchanging with each one of a previous hop node and one or a plurality of next hop nodes on a route of one packet flow a label allocation message requesting a set up of a label switched path which contains an identifier for identifying said one packet flow and an ingress node information regarding an ingress node of the label switched path; and a judging unit for detecting whether or not a message containing an identifier and an ingress node information that are identical to those of a previously exchanged message is received from a previous hop node different from one previous hop node from which the previously exchanged message is received, or whether or not a message that contains an identifier and an ingress node information that are identical to those of the previously exchanged message and changes the input side label information is received, and Judging whether a label switched path loop is formed or not according to a result of detecting.
Acc
Katsube Yasuhiro
Matsuzawa Shigeo
Ohba Yoshihiro
Takahashi Jun-ichi
Hsu Alpus H.
Nguyen Toan
LandOfFree
Scheme for label switched path loop detection at node device does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scheme for label switched path loop detection at node device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheme for label switched path loop detection at node device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2937986