Method for multicasting a message on a computer network

• US 7,089,323 B2
• Filed: 06/21/2002
• Issued: 08/08/2006
• Est. Priority Date: 06/21/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jones, Michael B., Theimer, Marvin M., Gummadi, Krishna P.
• Primary Examiner(s): Thomson, William
• Assistant Examiner(s): CAO, DIEM K
• Application Number:
  US10/177,335
• Publication Number:
  US 20040006650A1
• Time in Patent Office: 1,509 Days
• Field of Search: 370/255, 370/218, 709238-244, 709/200
• US Class Current: 709/238
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

A method for multicasting a message in a computer network is described, in which at least some nodes of a multicast group transmit fault recovery information to other nodes of the group in addition to, or as part of, the message itself. The fault recovery information allows nodes to determine what dissemination responsibility should be assigned to successor nodes in the event that one or more nodes of the multicast group fail.

Claims

1. A method for disseminating a message to nodes of a multicast group, the multicast group being organized into a tree-structured hierarchy, the method comprising:

transmitting the multicast message from a node of the multicast group to a plurality of other nodes of the multicast group, wherein each node has an identification number that is an integer;

transmitting, along with the multicast message;

an indication of the responsibility that each node of the plurality of other nodes has with respect to disseminating the multicast message further down the multicast tree; and

an indication of how responsibilities are to be divided up among the nodes of the multicast group should one or more of the nodes of the multicast group fail;

wherein the transmitting step comprises transmitting, to a receiving node, a tag comprising a first identification number of a node that represents a boundary of the receiving node'"'"'s area of responsibility, the identification number being usable to route messages to the node, the area of responsibility being the range of nodes to which the receiving node is responsible for further disseminating the message, and a second identification number of a node that represents a boundary of the area of responsibility of an additional node, other than the receiving node, the area of responsibility being the range of nodes to which the additional node is responsible for further disseminating the message.

2. A computer-readable storage medium having stored thereon computer-executable instructions for performing the method claim 1.

3. The method of claim 1, further comprising:

receiving the tag;

detecting that a node of the multicast group has failed;

identifying a node of the multicast group as a successor node to the failed node; and

transmitting to the successor node an indication of the successor node'"'"'s area of responsibility based on the received tag.

4. A method for disseminating a message to nodes of a multicast group, the method comprising:

at a first node of the multicast group;

delegating responsibility for forwarding the message to a first plurality of other nodes of the multicast group, wherein each node of the multicast group has a node number;

transmitting to a second node of the multicast group, the second node being one of the first plurality of nodes, information about the responsibility delegated to the second node, wherein the information identifies a second plurality of other nodes of the multicast group, the second plurality comprising nodes to which the second node is responsible for ensuring the message is sent, the responsibility information further identifies a boundary of nodes for which the second node is responsible for ensuring that copies of the message are sent, and the responsibility information is a boundary node number of one of the nodes of the multicast group and indicates that the second node is responsible for insuring that all nodes with node numbers that are between its own and the boundary node number receive the message;

determining whether an indication that the second node has fulfilled at least some of its responsibility has been received; and

based on the determining step, transmitting, to a third node of the multicast group, the information about the responsibility delegated to the second node, so that the third node can assume the responsibility of the second node.

5. A computer-readable storage medium having stored thereon computer-executable instructions for performing the method of claim 4.

6. The method of claim 4, further comprising transmitting the multicast message to the second node.

7. The method of claim 4, further comprising:

at the second node, determining whether the third node has failed; and

based on the determining step, transmitting the information about the responsibility of a third node to a successor node of the third node, thereby allowing the successor node to fulfill the responsibility of the third node.

8. A method for disseminating a message to nodes of a multicast group, the method comprising:

at a first node of the multicast group;

delegating responsibility for forwarding the message to a first plurality of other nodes of the multicast group;

transmitting to a second node of the multicast group, the second node being one of the first plurality of nodes, information regarding the responsibility delegated to the second node, wherein the information identifies a second plurality of other nodes of the multicast group, the second plurality comprising nodes to which the second node is responsible for ensuring the message is sent, and the information about the responsibility further identifies a node at the boundary of the second node'"'"'s responsibility;

transmitting to the second node information about the responsibility of a third node of the multicast group, wherein the third node is one of the first plurality of nodes, thereby allowing the second node to initiate recovery of the multicast group should the third node fail;

at the second node;

dividing up responsibility for forwarding the message among nodes whose node numbers are between the first node'"'"'s node number and the number of the node at the boundary of the second node'"'"'s responsibility;

determining whether the third node has failed; and

based on the determining step, transmitting the information about the responsibility of the third node to a successor node of the third node, thereby allowing the successor node to fulfill the responsibility of the third node.

9. A computer-readable storage medium having stored thereon computer-readable executable instructions for performing the method of claim 8.

10. The method of claim 8, further comprising transmitting the multicast message to the second node.

11. The method of claim 8, wherein each node of the multicast group has a node number, and the information about the responsibility delegated to the second node is a boundary node number of one of the nodes of the multicast group and indicates that the second node is responsible for insuring that all nodes with node numbers that are between its own number and the boundary node number receive the message.

12. A method for disseminating a message to nodes of a multicast group, wherein each node has an identification number that is an integer, the method comprising:

a node of the multicast group receiving a multicast message that includes information that identifies previous nodes of the multicast group through which the message has passed prior to being received, wherein the information further comprises a tag comprising a first identification number of a node that represents a boundary of the receiving node'"'"'s area of responsibility, the identification number being usable to route messages to the node, the area of responsibility being the range of nodes to which the receiving node is responsible for further disseminating the message, and a second identification number of a node that represents a boundary of the area of responsibility of an additional node, other than the receiving node, the area of responsibility being the range of nodes to which the additional node is responsible for further disseminating the message;

the receiving node deriving, based on the information received with the multicast message, the identity of the nodes of the multicast group to which the receiving node is responsible for sending the message; and

the receiving node transmitting, based on the deriving step, the multicast message to the nodes to which the receiving node is responsible for sending the message.

13. A computer-readable storage medium having stored thereon computer-readable executable instructions for performing the method of claim 12.

14. The method of claim 12, further comprising:

the receiving node determining, based on the information in the multicast message, whether any other nodes of the multicast group have failed, wherein the deriving step is based at least in part on the determining step.

15. A method for multicasting a message to a plurality of computer nodes of a multicast tree, each of the plurality of computer nodes having a node ID, the method comprising:

a first node of the plurality of nodes transmitting at least a tag and a copy of the message to a second node of the plurality of nodes, wherein the tag comprises the node ID of a third node of the plurality of nodes, the third node being a sibling of the second node within the multicast tree;

the second node interpreting the tag as indicating that the second node is responsible for ensuring that a copy of the message is sent to each node of the plurality of nodes whose node ID is between the second node'"'"'s node ID and the node ID of the third node, not including the third node;

the second node sending a copy of the message to at least one of its descendent nodes of the multicast tree;

the second node determining that it has successfully transmitted a copy of the message to a certain number of levels of its descendent nodes in the multicast tree; and

the second node transmitting a confirmation to the first node to indicate that it has successfully transmitted a copy of the message to the certain number of levels of its descendent nodes in the multicast tree.

16. The method of claim 15, further comprising:

the second node determining that it has successfully transmitted a copy of the message to its descendent nodes at least two levels down in the multicast tree; and

the second node transmitting a confirmation to the first node to indicate that it has successfully transmitted a copy of the message to its descendent nodes at least two levels down in the multicast tree.

17. A method for multicasting a message to a plurality of compute nodes of a multicast tree, each of the plurality of computer nodes having a node ID, the method comprising:

a first node of the plurality of nodes transmitting at least a tag and a copy of the message to a second node of the plurality of nodes, wherein the tag comprises the node ID of a third node of the plurality of nodes and the node ID of a fourth node of the plurality of nodes, the third node and the fourth node each being a sibling of the second node within the multicast tree, the tag further comprises the node ID of at least one other node in addition to the third node, and wherein the second node interprets the tag as additionally indicating that the second node is responsible for ensuring that a copy of the message is sent to additional nodes up to, but not including, the other node; and

the second node interpreting the tag as indicating

that the second node is responsible for ensuring that a copy of the message is sent to each node of the plurality of nodes whose node ID is between the second node'"'"'s node ID and the node ID of the third node, not including the third node;

that the second node is responsible for ensuring that the third node is periodically queried to determine whether the third node is alive,

and that the third node is responsible for ensuring that a copy of the message is sent to each node of the plurality of nodes whose node ID is between the third node'"'"'s node ID and the node ID of the fourth node, not including the fourth node.