US 6,724,770 B1 · Multicast protocol with reduced buffering requirements

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.

Claims12

Dependent claims

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.

8 more elements

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 more elements

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.

11 more elements

Dependencies are inferred from the claim text.

Multicast protocol with reduced buffering requirements

Life of this patent

Multicast protocol with reduced buffering requirements

Life of this patent

Abstract

Claims12