System and method for loop avoidance in multi-protocol label switching
View Patent ↗A method for avoiding loops from forming when setting up label switched paths is provided. The method uses a Label Splicing Message is followed by an Acknowledgment message to determine if loops are formed in the process of joining a new node or subtree to a multicast MPLS tree. By verifying that the path towards the root of the MPLS tree is loop-free during the construction of the tree, this method complements the loop detection mechanism provided by the label switched protocol (LDP).
1. A method for preventing routing loop from forming when joining a node to a Multi-Protocol Label Switching tree, comprising the steps of:
a) obtaining at a label switching router (LSR)a label mapping for a forwarding equivalency class (FEC);
b) determining if previous bindings exist for said FEC:
c) determining if said joining node is a signal node or a parent node of a subtree;
d) accepting the mapping for said single node if no previous bindings exist; and
if said previous bindings exist when said subtree is attached to said Multi-Protocol Label Switching tree:
e) sending a label splice message (Lsm) from said LSR to a root-node on a label switched path and returning a label splice message acknowledgement (ACK) to said LSR, and
f) accepting the mapping after receiving said ACK at said LSR;
g) terminating any further action if said LSR is waiting for a previous ACK message,
h) forwarding said Lsm to the next LSR if said LSR is not waiting for said previous ACK message.
2. A method for avoiding routing loops from forming when a node of a subtree is grafted to a Multi-Protocol Label Switching tree, comprising the steps of:
a) receiving a label binding Message at said node, said label binding including a label and a forwarding equivalency class (FEC):
b) if a label mapping request for the same FEC was not previously received at said node sending a label splice message (Lsm) towards the root of said Multi-Protocol Label Switching tree along a labelled path;
c) generating a splice acknowledgement message (ACK) by said root node in response to said Lsm;
d) declaring loop-free and accepting said binding if said node is not waiting for a previous ACK corresponding to a previously received Lsm and said ACK returns to said node on the same said labelled path; and
e) informing all member nodes said subtree was grafted to said Multi-Protocol Label Switching tree.
3. The method of claim 2 , wherein said Multi-Protocol Label Switching tree comprises a unidirectional shared tree.
4. The method of claim 3 , wherein said root of said unidirectional shared tree comprises an ingress node of said unidirectional shared tree if the core node is not included in said unidirectional shared tree.
5. The method of claim 2 , wherein said Multi-Protocol Label Switching tree comprises a source tree.
6. The method of claim 5 , wherein said root of said source tree comprise and ingress node of said source tree.
7. The method of claim 2 , wherein said Multi-Protocol Label Switching tree comprises a bidirectional shared tree.
8. The method of claim 7 , wherein said root of said bidirectional shared tree comprises the node closest to the core if said care node is not included in said bidirectional shared tree.
9. The method of claim 2 , wherein said Multi-Protocol Label Switching tree comprises a multipoint to point tree.
10. The method of claim 2 , wherein said Multi-Protocol Label Switching tree comprises a point to multipoint tree.
11. The method of claim 2 , wherein whenever there is a label mapping request for same said FEC at said node, the following substeps are performed after step (a):
merging label mapping requests; and
stop forwarding said Lsm.
12. The method of claim 2 , wherein, if said ACK is not received back by said node while said nod is waiting to receive said previous ACK, terminating grafting procedures after performing step (c).
13. The method of claim 2 , wherein, if said ACK is not received back by said node and said node is not waiting to receive said previous ACK, forwarding said Lsm after performing step (c).
14. The method of claim 2 , wherein said label splice message contains a message identifier and the address of a node which originates said label splice message, and said generating step generates the spice acknowledgement message having the message identifier and the address contained in the corresponding label splice message.
15. The method of claim 14 , further comprising the step of distinguishing a latest splice acknowledgement message from a previous splice acknowledgement message based on each massage identifier.
16. A method for preventing rooting loops from forming when splicing subtree with a Multi-Protocol Label Switching tree, comprising the steps of:
obtaining at a label switching router (LSR) a label mapping for a forwarding equivalency class (FEC):
determining if previous bindings exist for said FEC:
if said previous bindings exist, sending a label splice message from said LSR to a root-node on a label switched path;
returning a label splice message acknowledgment to said LSR on the same label switched path in response to the label spice message:
said sending step includes the step of forwarding said label splice message to a next LSR when not waiting for a previous label splice acknowledge message from said root-node and terminating any further action when waiting for said previous label splice acknowledge message; and
splicing, said subtree with said Multi-Protocol Label Switching tree when said label switching router originating said label splice message receives said label splice acknowledgement message.
17. The method of claim 16 , wherein said splicing step includes the step of sending said label mapping when splicing a node of said subtree with a Multi-Protocol Label Switching point to multipoint tree (p2mp).
18. The method of claim 16 , wherein said splicing step includes the step of accepting said label mapping when splicing a node of said subtree with a Multi-Protocol Label Switching multipoint to point tree (mp2p).
19. The method of claim 16 , wherein said label splice message contains a message identifier and the address of a node which originates said label splice message, and said generating step generates the splice acknowledgement message having the message identifier and the address contained in the corresponding label splice message.
20. The method of claim 19 , further comprising the step of distinguishing a latest splice acknowledgement message from a previous splice acknowledgement message based on each message identifier.