Reliable multicast for small groups

• US 6,415,312 B1
• Filed: 01/29/1999
• Issued: 07/02/2002
• Est. Priority Date: 01/29/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Boivie, Richard H.
• Primary Examiner(s): Barot, Bharat
• Application Number:
  US09/240,546
• Time in Patent Office: 1,250 Days
• Field of Search: 709/200-204, 709/212-214, 709/227-228, 709/232-233, 709/236-238, 370/400-401, 370/408-409, 370/259-260, 370/351, 370/355-356, 714/746-750
• US Class Current: 709/200
• CPC Class Codes: H04L 1/1803 Stop-and-wait protocols
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 2001/0092 Error control systems characterised by the topology of the transmission link

Abstract

A system for reliable multicast transmission [multicasting data packets] in a packet-based data network includes mechanisms for performing the following: (1) preparing at least one packet comprising a payload portion and multicast route information, an error detection mechanism; (2) transmitting the packet to at least one intermediate node for delivery to at least two destination nodes; (3) waiting for a period of time for at least one acknowledgment signal indicating receipt of the at least one packet by at least one destination node; and (4) retransmitting a packet to a set of destination nodes from which no positive acknowledgment has been received. The multicast routing information includes information for use by the at least one intermediate node to forward the packet to at least two destination nodes.

Claims

1. A method for reliable multicast transmission in a packet-based data network comprising the source node steps of:

preparing at least one packet comprising a payload portion, multicast route information, and an error detection mechanism;

transmitting the packet from a source node to at least one intermediate node for delivery to at least two destination nodes;

waiting for a period of time for at least one acknowledgment signal indicating receipt of the at least one packet by at least one receiving node; and

retransmitting a duplicate packet from the source node to a set of destination nodes from which no positive acknowledgment has been received;

wherein the multicast routing information specifies the routing by which the packet is to be transmitted from the source node to the at least two destination nodes and wherein the multicast routing information specifies the least one intermediate node and the at least two destination nodes that are to receive the packet.

2. The method of claim 1 wherein the duplicate packet comprises:

a multicast distribution tree that specifies a subset of destinations that are to receive the duplicate packet and wherein the multicast distribution tree specifies the routing by which the duplicate packet is to be communicated.

3. The method of claim 2 wherein the step of retransmitting further comprises the step of:

adjusting the multicast routing tree responsive to receipt of acknowledgment signals.

4. The method of claim 1 wherein the retransmitting step comprises the step of retransmitting the packet when no positive acknowledgment signal has been received within a retransmission period of time.

5. The method of claim 1 wherein the retransmitting step comprises the step of retransmitting the packet when a negative acknowledgment signal has been received.

6. The method of claim 5 wherein the retransmission occurs immediately upon receipt of the negative acknowledgment signal.

7. The method of claim 5 wherein the retransmission occurs within a predetermined period upon receipt of the negative acknowledgment signal.

8. The method of claim 4 further comprising the receiving node steps of:

adapting the retransmission period of time to a period greater than the time elapsed from transmission of a packet to the time of receipt of at least one corresponding acknowledgment signal.

9. The method of claim 4 further comprising the steps of:

determining the response time for at least one acknowledgment signal;

adapting the retransmission period of time responsive to said determination.

10. The method of claim 1 wherein the step of preparing at least one packet further comprises the step of including a sequence number.

11. The method of claim 1 wherein the error determination mechanism comprises a checksum determination.

12. The method of claim 1 wherein the error determination mechanism comprises a cyclic redundancy check determination.

13. The method of claim 1 wherein the error determination mechanism comprises a parity bit determination.

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

destination acknowledgment signals from a subset of the destination nodes; and

retransmitting to all the destination nodes.

15. The method of claim 1 further comprising the steps of:

destination acknowledgment signals from a subset of the destination nodes; and

re-transmitting only to a subset of the destination nodes that did not receive the packet.

16. The method of claim 15 where in the step of waiting a period of time or until an acknowledgment ha s been received from each of the destination nodes.

17. The method for multicasting data packets in a packet-based data network of claim 10, further comprising the destination node steps of:

receiving at least one packet sent by the source node;

processing the sequence number and an error detection mechanism; and

transmitting an acknowledgment signal indicating receipt of the at least one packet when the processing step indicates no error.

18. A computer readable medium comprising instructions for:

preparing at least one packet comprising a payload portion and multicast routing information;

transmitting the packet from a source node to at least one intermediate node for delivery to at least two destination nodes;

waiting for a period of time for at least one acknowledgment signal indicating receipt of the at least one packet by at least one destination node; and

retransmitting a duplicate packet from the source node to a set of destination nodes from which no positive acknowledgment has been received;

wherein the multicast routing information specifics the routing by which the packet is to be transmitted from the source node to the at least two destination nodes and wherein the multicast routing information specifies the at least one intermediate node and the at least two destination nodes that are to receive the packet.

19. The computer readable medium of claim 18 wherein the computer readable medium comprises at least one data packet for transmission in a data network.

20. A system for reliable multicast transmission in a packet-based data network comprising:

means for preparing at least one packet comprising a payload portion, multicast route information and an error detection mechanism;

means for transmitting the packet from a source node to at least one intermediate node for delivery to at least two destination nodes;

means for waiting for at least one acknowledgment signal indicating receipt of the at least one packet by at least one destination node; and

means for retransmitting a duplicate packet from a source node to a set of destination nodes from which no positive acknowledgement has been received;

wherein the multicast routing information specifies the routing by which the packet is to be transmitted from the source node to the at least two destination nodes and wherein the multicast routing information specifies the at least on intermediate node and the at least two destination nodes that are to receive the packet.