Multiplex communications – Fault recovery
Reexamination Certificate
2000-06-07
2004-09-28
Vu, Huy D. (Department: 2665)
Multiplex communications
Fault recovery
C370S408000
Reexamination Certificate
active
06798739
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention generally relates to multicast distribution trees and in particular to a mechanism for avoiding loops when a distribution tree is constructed.
2. Related Art
Simple Multicast (SM) uses a single concept working within and between domains, by offering a simplified concept for multicast distribution using the core node “C” address and the multicast address “M” (“M” is unique for a given “C”). By leaving only “C” and M” in the data-packet header, routers along a path in the multicast distribution tree have to figure out the location of “C” using only “M”. It reduces the states necessary in routers for supporting multicast distribution while providing a simple and reliable solution with increased speed and a lower overhead.
A bidirectional distribution tree, as opposed to the per-source unidirectional distribution tree, is an effective solution for data delivery from non-core sources. Traffic can be injected from any point and data from a source node does not have to be tunneled first to the core “C”. It is also more robust since the core “C” is considered as another node in the tree and when “C” is down, the partitioned tree may still be used until the link/s to “C” is/are re-established.
A parent node in a multicast distribution tree transmits HEARTBEAT (HB) messages to its children at regular intervals and continues to send these messages even if it stops receiving HB messages from its parent such that a subtree may continue to function even if the core is dead. If the core is not dead, or if the path to the core has changed, the parent can simply re-join the multicast tree without disrupting the nodes below. The HB message carries also a “distance from the core” indication.
Keep-Alive (KA) messages are sent to a router by hops from further leafs on the distribution tree, or spanning tree. The router collects KA messages from all its children ports and transmits a KA message to the router which is one hop more than the maximum hops received from any children.
When the distance is great in the HB and KA messages, a loop is suspected and the port removed from the tree. This is a simple loop detection mechanism and can not be used for preventing loops from forming in a spanning tree at the time the tree is repaired.
There are situations like unused branches on a spanning tree, loops involving member nodes, broken/changed path to core, or dead/unreachable core, which require loop detection and/or loop prevention procedures to be provided at the time a tree is repaired.
Methods for detecting and preventing loops formed during the construction phase of a multicast tree are known in the art. For example, U.S. Pat. No. 5,331,637 issued to the same assignee, detects transient loops in unicast routing during the construction of the multicast core based tree (CBT). Transient loops are loops that occur for a short period of time but during their existence they can damage the tree similarly to the non-transient loops. The loop prevention mechanism described in U.S. Pat. No. 5,331,637 has limitations as it does not prevent loops from forming when an upstream link to the root of a tree is down, or the tree is partitioned. The entire downstream tree has to be dismantled and then the whole multicast distribution tree has to be rebuilt.
Suppose that node S shown in FIG.
1
. finds through HEARTBFAT messages that the link to the foot node A (link AS) is down and tries to reattach to the multicast distribution tree. Branch S-E-F is detached from the broken tree and the shortest path from the severed node S to A is now via node F, and other links not included in the multicast distribution tree.
According to the method disclosed in U.S. Pat. No. 5,331,637, node S attempts to maintain its connectivity to node A and to re-attach itself to the tree by sending a graft message, or JOIN request control message. The JOIN request is received in this case by node F. It is noted that, packets flowing from node E to node F will be also forwarded back to node S since S is now a downstream node of F.
Node F terminates the JOIN request and sends ACK-BACK to node S. A loop is now formed between nodes S and F, the control packets will be multicasted between F and S and after each looping the number of the control packets is doubled causing damage to the multicast distribution tree. Even if a data packet counter that counts down the time-to-live (TTL) at each hop is used, the number of control packets doubled at each looping is damaging the system before TTL=0.
Current loop detection schemes, try to detect routing loops that normally occur for a short period of time in unicast routing during the construction of the multicast distribution tree (MDT). However, there is no loop protection mechanism provided when the MDT breaks, or is partitioned and needs repairing.
The method in U.S. Pat. No. 5,331,637 uses the JOIN request control message which indicates that a loop exists and at the same time creates a loop as JOIN request must be terminated at node F. This method can not prevent the loop from forming when a node attempting to re-attach to the multicast distribution tree and the node where it grafts to happens to be a downstream node.
Accordingly, there is a need for a mechanism capable to avoid the formation of loops at the time a multicast distribution tree (MDT) is constructed such that a node joining the tree can re-attach itself to any member node.
SUMMARY OF THE INVENTION
The present invention seeks to alleviate totally or in part the drawbacks associated with the prior art multicast distribution tree construction.
According to one aspect of the invention, a method for avoiding routing loops when repairing a bidirectional multicast distribution tree, is provided. The method comprises the steps of launching a splice message from an originating node attempting to join the bidirectional multicast distribution tree and transmitting the splice message towards a root-node along a communications path; creating transient forwarding states for the multicast distribution tree along the communications path; transmitting a splice acknowledgment message from said root-node in response to receiving said splice message; declaring loop-free if the splice message is not returned to the originating node and the splice acknowledgment message generated by the root-node is received by the originating node.
The present invention is not limited to the features disclosed in the “Summary of the Invention” section; it nonetheless may reside on sub-combinations of the disclosed features.
REFERENCES:
patent: 4740954 (1988-04-01), Cotton et al.
patent: 5331637 (1994-07-01), Francis et al.
patent: 5781537 (1998-07-01), Ramaswami et al.
patent: 5831975 (1998-11-01), Chen et al.
patent: 5878232 (1999-03-01), Marimuthu
patent: 5905871 (1999-05-01), Buskens et al.
patent: 6032194 (2000-02-01), Gai et al.
patent: 6055561 (2000-04-01), Feldman et al.
patent: 6128305 (2000-10-01), Hjalmtysson et al.
patent: 6381639 (2002-04-01), Thebaut et al.
Perlman R. et al, “Simple Multicast: A Design for Simple, Low-Overhead Multicast {circumflex over ( )}M,” Feb. 1999.
Nortel Networks Limited
Ryman Daniel
Vu Huy D.
LandOfFree
Mechanism for splicing trees does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Mechanism for splicing trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mechanism for splicing trees will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3271445