Multicast routing using core based trees

• US 5,331,637 A
• Filed: 07/30/1993
• Issued: 07/19/1994
• Est. Priority Date: 07/30/1993
• Status: Expired due to Term

• Current Assignee: Relay IP Incorporated (Marathon Patent Group, Inc.)
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Francis, Paul T., Ballardie, Anthony J., Crowcroft, Jonathan A.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Jung, Min
• Application Number:
  US08/100,634
• Time in Patent Office: 354 Days
• Field of Search: 370/94.1, 370/94.3, 370/60, 370/54, 370/16, 340/827
• US Class Current: 370/408
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 12/1877 Measures taken prior to transmission

Abstract

A method for routing multicast packets in a network is disclosed. A node s101 wishing to join a particular multicast group transmits a packet via a sequence of nodes (r101, r102, r104, r107) including a core node r107 on the multicast tree corresponding to the particular multicast group which the node wishes to join. The packet contains a request to join the particular multicast group and the multicast address of the core node r107 of the multicast tree corresponding to the particular multicast group. The packet is received at each node r101, r102, r104, r107 of the sequence of nodes. Each node r101, r102, r104, r107 which receives the packet writes an address of the node s101, r101, r102, r104 from which the packet was received in an entry of a multicast forwarding table maintained thereat which entry is indexed by the multicast address of the core node r107. If the node r101, r102, r 104 which received the packet is not on the multicast tree of the particular multicast group, the node r101, r102, r104 writes an address of the next node r102, r104, r107 of the sequence of nodes in the multicast forwarding table entry indexed by the multicast address of the core node r107. The packet is then retransmitted to the next node r102, r104, r107 of the sequence of nodes.

Claims

1. A method for enabling a particular node to join a particular multicast group of nodes in a network comprising a plurality of nodes, said method comprising the steps of:

transmitting from said particular node a join request control packet indicating a multicast address of a core node on a multicast tree corresponding to said multicast group,

receiving said join request control packet at another node,

writing an address of the node from which said join request control packet was received in an entry of a forwarding table maintained at said other node, which entry is indexed by said multicast address of said core node, and

if said other node is not already on said multicast tree of said particular multicast group, writing an address of a next node on a path to said core node in said forwarding table entry indexed by said multicast address of said core node and retransmitting said packet from said other node to said next node.

2. The method of claim 1 further comprising the step of:

retrieving an entry from a unicast forwarding table maintained at said other node, which entry is indexed by said multicast address of said core node, wherein said retrieved entry indicates said next node on said path to said core node.

3. The method of claim 1 further comprising the step of:

deleting a specific node on said multicast tree by transmitting from said specific node to an adjacent node on a branch to said core node a quit request control packet requesting to be deleted from said multicast tree.

4. The method of claim 3 wherein said specific node requests to be deleted from said multicast tree if said specific node is not directly connected to any nodes which are members of said particular multicast group, and if said specific node is not on a path between a member of said particular multicast group and said core node.

5. The method of claim 3 further comprising the step of:

at said adjacent node, deleting an address of said specific node from an entry of a forwarding table maintained at said adjacent node.

6. The method of claim 1 wherein said multicast tree includes one or more interconnected auxiliary core nodes connected to said core node, said auxiliary core nodes being assigned a priority in descending order, said method further comprising the step of:

(a) if a specific node on said multicast tree detects a failed node on a branch to said core node, transmitting from said specific node a join request control packet to said auxiliary core node having the highest priority, and p1 repeating step (a) for each auxiliary core node in descending priority until said specific node rejoins said multicast tree.

7. The method of claim 1 further comprising the step of:

if a specific node on said multicast tree detects a failure on a branch to said core node, transmitting a flush tree control packet to each other node on said multicast tree connected to said specific node to cause said other nodes to rejoin said multicast tree.

8. The method of claim 1 wherein said packet transmitted from said particular node indicates that said particular node is rejoining said multicast tree and said method further comprises the steps of:

detecting at said particular node wishing to rejoin said multicast tree, a loop including only nodes on said multicast tree, and

transmitting to a next node on a branch to said core node a quit request control packet to eliminate said loop.

9. The method of claim 8 further comprising the step of:

if said join request control packet transmitted from said particular node returns to said particular node, determining that a loop exists including only nodes on said multicast tree.

10. The method of claim 8 further comprising the steps of:

receiving said join request control packet at said other node already on said multicast tree, and

retransmitting a copy of said received join request control packet to each other node on said multicast tree connected to said other node.

11. The method of claim 1 wherein said multicast tree comprises a plurality of core nodes which each have a unique multicast address.

12. A method for enabling a particular node to join a particular multicast group of nodes in a network, said multicast group having a multicast tree including a core node, said method comprising the steps of:

transmitting a join request control packet containing a multicast address of said core node from said particular node to a node already on said multicast tree using unicast routing,

at said node already on said multicast tree, writing an address of the node from which said join request control packet was received in an entry of a forwarding table maintained at said node already on said multicast tree, which entry is indexed by said multicast address of said core node, and

transmitting a join acknowledgement control packet to said particular node.

13. The method of claim 12 further comprising the step of:

prior to receiving said join request control packet at said node already on said multicast tree, receiving said packet at a node not yet on said multicast tree,

writing in an entry of a forwarding table maintained at said node not yet on said multicast tree, which entry is indexed by said multicast address of said core node, an address of the node from which said join request control packet was received and an address of a next node on a path to said node already on said multicast tree, and

transmitting said join request control packet to said next node.

14. The method of claim 13 further comprising the steps of:

receiving said join acknowledgement control packet at said node not yet on said multicast tree,

maintaining a state indicating that said node not yet on said multicast tree is on said multicast tree, and

retransmitting said join acknowledgement packet to said particular node.

15. A method for transmitting a data packet to a multicast group of nodes in a network using a multicast tree of nodes associated with said group comprising the steps of:

at each node on a multicast tree corresponding to said multicast group, retrieving an entry from a forwarding table maintained at each node and indexed by a multicast address of a core node indicated by said data packet, and transmitting a copy of said data packet to each node indicated by said retrieved entry except a node from which said packet was received.,

said multicast tree having been constructed by the steps of;

transmitting from a particular node wishing to join said particular multicast group a join request control packet indicating a multicast address of said core node, receiving said join request control packet at another node, writing an address of the node from which said join request was received in an entry of a forwarding table maintained at said other node, which entry is indexed by said multicast address of said core node, and if said other node is not already on said multicast tree of said particular multicast group, writing an address of a next node on a path to said core node in said forwarding table entry indexed by said multicast address of said core node and retransmitting said packet form said other node to said next node.

16. A method for transmitting a data packet from a source node which is not a member of a multicast group of nodes to a multicast group of nodes in a network using a multicast tree of nodes associated with said group comprising the steps of:

transmitting said data packet containing a multicast address of a core node on said multicast tree from said source node to a node on said multicast tree using unicast routing,

said packet being transmitted on said multicast tree by the steps of;

at each node on a multicast tree corresponding to said multicast group, retrieving an entry from a forwarding table maintained at each node and indexed by a multicast address of a core node indicated by said data packet, and transmitting a copy of said data packet to each node indicated by said retrieved entry except a node from which said packet was received.