Mechanism for splicing trees

• US 6,798,739 B1
• Filed: 06/07/2000
• Issued: 09/28/2004
• Est. Priority Date: 06/07/1999
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Lee, Cheng Yin
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): RYMAN, DANIEL J
• Application Number:
  US09/588,904
• Time in Patent Office: 1,574 Days
• Field of Search: 370/216, 370/217, 370/221, 370/225, 370/390, 370/256, 370/408, 370/432, 709/221, 709/238
• US Class Current: 370/216
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A method for detecting a routing loop when repairing a bidirectional multicast distribution tree is disclosed. According to the method, a splice message is launched from an originating node attempting to join a bidirectional multicast tree and is sent to a root-node to find out if a routing loop is formed when a node is joining the multicast distribution tree. Depending on the multicast application requirement, when a routing loop is detected during the repairing of a multicast distribution tree, the severed node may abort, or the repair can be deferred until the connection to the root-node is re-established. The loop detection and loop prevention method of the invention may be used as a loop avoidance mechanism with any protocol for repairing a partitioned tree.

Claims

1. A method for avoiding routing loops when repairing a bidirection multicast distribution tree, comprising the steps of:

(a) launching a splice message from an originating node attempting to join said bidirectional multicast distribution tree and transmitting said splice message towards a root-node along a communications path;

(b) creating transient forwarding states in each node along said communications path for said multicast distribution tree wherein said splice message is forwarded by one or more nodes before reaching the root-node;

(c) transmitting a splice acknowledgment message from only said root-node in response to receiving said splice message;

(d) declaring loop-free if said splice message is not returned to said originating node and said splice acknowledgment message generated by said root-node is received by said originating node.

2. The method of claim 1, further comprising making said transient forwarding states permanent after performing step (d).

3. The method of claim 1, further including the step of:

(e) if said splice acknowledgment message is not received during a pre-established time interval, terminating repairing said multicast distribution tree, after performing step (c).

4. The method of claim 1, further including the step of:

(f) deferring repairing said multicast distribution tree if said splice message is returned to said originating node, after performing step (c).

5. The method of claim 4, wherein said step (f) further comprises attempting to join said multicast distribution tree via an equal cost route.

6. The method of claim 4, wherein said step (f) further comprises waiting a predetermined period of time before attempting to join said multicast distribution tree via a next hop.

7. The method of claim 4, wherein said step (f) further comprises flushing the subtree having said originating node as the parent node and allowing downstream nodes to individually join said multicast distribution tree.

8. A computer-readable medium containing computer executable instructions for avoiding routing loops when repairing a bidirectional multicast distribution tree, comprising the steps of:

(a) launching a splice message from an originating node attempting to join said bidirectional multicast distribution tree and transmitting said splice message towards a root-node along a communications path;

(b) creating transient forwarding states in each node along said communications path for said multicast distribution tree wherein said splice message is forwarded by one or more nodes before reaching the root-node;

(c) transmitting a splice acknowledgment message from only said root-node in response to receiving said splice message;

(d) declaring loop-free if said splice message is not returned to said originating node and said splice acknowledgment message generated by said root-node is received by said originating node.

9. The computer-readable medium of claim 8, further performing the step of:

if said splice acknowledgment message is not received during a pre-established time interval, terminating repairing said multicast distribution tree, after performing step (c).

10. The computer-readable medium of claim 8, further performing the step of:

deferring repairing said multicast distribution tree if said splice message is returned to said originating node, after performing step (c).

11. The computer-readable medium of claim 10, further comprising the substep of attempting to join said multicast distribution tree via an equal cost route.

12. The computer-readable medium of claim 10, further comprising the substep of waiting for a predetermined period of time before attempting to join said multicast distribution tree via a next hop.

13. The computer-readable medium of claim 10, further comprising the substep of flushing the subtree having said originating node as the parent node and allowing downstream nodes to individually join said multicast distribution tree.