Multicast protocol with reduced buffering requirements

• US 6,724,770 B1
• Filed: 02/17/2000
• Issued: 04/20/2004
• Est. Priority Date: 02/17/2000
• Status: Expired due to Term

• Current Assignee: Kenneth P. Birman
• Original Assignee: Kenneth P. Birman
• Inventors: Van Renesse, Robbert
• Primary Examiner(s): Hsu, Alpus H.
• Assistant Examiner(s): TRAN, THIEN D
• Application Number:
  US09/506,054
• Time in Patent Office: 1,524 Days
• Field of Search: 370/389, 370/390, 370/394, 370/432, 370/312, 711/211, 711/212, 711/216, 711/217, 711/218
• US Class Current: 370/432
• 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

Abstract

A scalable multicast protocol buffers the multicast messages at a subset of “C” members, where C is selected to reduce to an acceptable level the probability that a given message will be lost before it reaches at least one of the C members. When a member receives a multicast message, the member determines whether or not it should buffer the message by manipulating a string of bytes that is unique to both the message and the member and determining if the result is less than a calculated value C/n, where “n” is the number of known members. When one of the C bufferers thereafter receives a gossip message that indicates that the multicast message has been lost to the gossiping member, the bufferer retransmits the message to the gossiping member. When a member that is not one of the C bufferers receives such a gossip message, the member determines which members are bufferers of the lost message and requests that one of the bufferers retransmit the message to the gossiping member. The selected member identifies the bufferers by manipulating the byte strings associated with the lost message and the respective members that are known to the selected member. The selected member then sends to one of the identified bufferers a request for retransmission of the lost message to the gossiping member. The multicast protocol may further include a mechanism to detect catastrophic failures in the multicast transmission. Each member includes the buffer discussed above and a relatively small, fixed-size “short-term” buffer that holds a limited number of the received messages in the order in which the messages are received. A member monitors any holes or gaps in the sequences of incoming messages, and detects a catastrophic failure when a received gossip message identifies one of the same holes or gaps. When such a failure is detected, the member sends a request for multicast retransmission of the associated missing message to the sender, and the sender multicasts the message to the group from the short term buffer.

Claims

1. A method of multicasting messages over a group of members in a network, the method including the steps of:

A. multicasting the message over the group;

B. determining, at one or more of the members receiving the message, if the one or more members are bufferers of the message by

i. at each of the one or more members, manipulating a string of bytes that is unique to both the message and the member in accordance with a hash function by

a. XOR'"'"'ing the respective bytes of the byte string with a hash value;

b. entering a stored table with the results of step a and selecting a table entry;

c. XOR'"'"'ing the selected table entry with the hash value to up date the hash value;

d. repeating steps a-c for all of the bytes in the byte string, and

e. dividing the result by a predetermined integer to produce a final hash value as the result;

ii. determining if the result of the manipulation is less than a value calculated by the member;

C. at the one or more members that are bufferers of the message, buffering and delivering the message;

D. at the one or more members that are not bufferers of the message, delivering the message.

2. The method of claim 1 wherein the step of determining if the result of the manipulation is less than a value calculated by the member includes using as the calculated value C/n, where C is selected based on the probability of a lost message and n is the number of group members that are known to the member.

3. The method of claim 1 further including the steps of

E. at one or more members storing received multicast messages in relatively small short term buffers;

F. at a given member detecting a gap in a sequence of the received messages;

G. including in a gossip message information that identifies the detected gaps;

H. if a received gossip message identifies a gap that is also detected by the member that received the gossip message, sending to the source of the associated message sequence a request for a multicast retransmission of the message that corresponds to the detected gap; and

I. at the source, multicasting the message over the group from the short term buffer.

4. The method of claim 3 wherein the size of the short term buffer is based on the rate of multicast message transmission for the group.

5. The method of claim 3 further including the steps of

J. selecting a member at random and sending to the selected member a gossip message that includes a list of messages delivered by a gossiping member;

K. determining at the selected member if a message is lost to the gossiping member;

L. for a lost message, retransmitting the message from the selected member to the gossiping member if the selected member is a bufferer of the lost message;

M. if the selected member is not a bufferer of the lost message, determining at the selected member which members are bufferers of the lost message and sending to one of the bufferers a request for retransmission of the lost message to the gossiping member.

6. A method of multicasting messages over a group of members in a network, the method including the steps of:

A. multicasting the message over the group;

B. determining, at one or more of the members receiving the message, if the one or more members are bufferers of the message by

i. manipulating a string of bytes that is unique to the message and a given member,

ii. determining the given member is a bufferer if the result of the manipulation is less than a calculated value C/n, where C is selected based on the probability of a lost message and n is a number of known group members;

C. at the one or more members that are bufferers of the message, buffering and delivering the message;

D. at the one or more members that are not bufferers of the message, delivering the message;

E. selecting a member at random and sending to the selected member a gossip message that includes a list of messages delivered by a gossiping member;

F. determining at the selected member if a message is lost to the gossiping member;

G. for a lost message, retransmitting the message from the selected member to the gossiping member if the selected member is a bufferer of the lost message;

H. if the selected member is not a bufferer of the lost message, determining at the selected member which members are bufferers of the lost message and sending to one of the bufferers a request for retransmission of the lost message to the gossiping member.

7. The method of claim 6 wherein the step of manipulating the string of bytes includes manipulating the bytes in accordance with a hash function.

8. The method of claim 7 wherein the hash function includes the steps of

a. XOR'"'"'ing the respective bytes of the byte string with a hash value;

b. entering a stored table with the results of step a and selecting a table entry;

c. XOR'"'"'ing the selected table entry with the hash value to update the hash value;

d. repeating steps a-c for all of the bytes in the byte string; and

e. dividing the result by a predetermined integer to produce a final hash value as the result.

9. A system of networked members, each member including:

A. message receivers for receiving messages;

B. a processor for determining if the member is a bufferer of a received multicast message by manipulating a string of bytes that is unique to both the message and the member, and, the processor including

a. a first XOR gate for XOR'"'"'ing the respective bytes of the byte string with a hash value;

b. a stored table that is entered with the result produced by the first XOR gate;

c. a second XOR gate for XOR'"'"'ing the selected table entry with the hash value to update the hash value; and

d. a divider, for dividing by a predetermined value the hash value produced by the second XOR gate after all of the bytes of the byte string are submitted to the first XOR gate, to produce the results the processor determining if the member is a bufferer if the result of the manipulation is less than a calculated value;

C. a buffer for retaining received multicast messages for which the member is a bufferer;

D. message delivering subsystems for delivering the received messages; and

E. a gossiping subsystem for

i. determining from a received gossip message if a multicast message is lost to a gossiping member sending the gossip message

ii. if the member is a bufferer of the lost message, retransmitting the lost message to the gossiping member,

iii. if the member is not a buffer of the lost message, determining which members are bufferers and sending to one of the buffers a request to retransmit the lost message to the gossiping member.

10. The system of claim 9 wherein the processor determines if the result of the manipulation is less than a calculated value C/n, where C is selected based on the probability of a lost message and n is the number of group members that are known to the processor.

11. The system of claim 9 wherein

a. further including at each member

i. a relatively small short term buffer for retaining received multicast messages in the order in which the messages are received;

ii. means for detecting a gap in a sequence of the received messages; and

b. the gossiping subsystem further

i. includes in a gossip message information that identifies the detected gaps, and

ii. if a received gossip message includes information about a gap that is also detected by the member that received the gossip message, sending to a source of the messages associated with the gap a multicast retransmission request.

12. The system of claim 11 wherein the size of the short term buffer is based on the rate of multicast message transmission for the members.