Method and apparatus for group communication with end-to-end reliability

• US 7,355,975 B2
• Filed: 04/30/2004
• Issued: 04/08/2008
• Est. Priority Date: 04/30/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Liu, Zhen, Chaintreau, Augustin, Riabov, Anton, Baccelli, Francois
• Primary Examiner(s): Ngo; Ricky Q.
• Assistant Examiner(s): Mui; Gary
• Application Number:
  US10/835,815
• Publication Number:
  US 20050243722A1
• Time in Patent Office: 1,439 Days
• Field of Search: 370/231, 370/413, 370/221, 370/235, 370/242, 370/255, 370/256, 370/389, 370/390, 370/394, 370/395.52, 370/224, 370/254, 370/351, 370/412, 370/428
• US Class Current: 370/235
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback

Abstract

The present invention addresses scalability and end-to-end reliability in overlay multicast networks. A simple end-system multicast architecture that is both scalable in throughput and reliable in an end-to-end way is used. In this architecture, the transfers between nodes use TCP with backpressure mechanisms to provide data packet transfers between intermediate nodes having finite-size forwarding buffers. There is also a finite-size backup buffer in each node to store copies of packets which are copied out from the receiver window to the forwarding buffers. These backup buffers are used when TCP connections are re-established to supply copies of data packets for the children nodes after their parent node fails, maintaining a complete sequence of data packets to all nodes within the multicast overlay network. The architecture provides end-to-end reliability, tolerates multiple simultaneous node failures and provides positive throughput for any group size and any buffer size.

Claims

1. A method for delivering data packets from a source node to a plurality of end-system nodes in a multicast overlay network tree with scalable group communication throughput and end-to-end reliability, the method comprising:

providing at least one backup buffer in each one of a group of end-system nodes in the multicast network tree;

storing copies of data packets transferred from an input buffer to an output buffer in one of the group of end-system nodes in the backup buffer;

sizing the back-up buffer in accordance with maximum sizes of the input and output buffers and a number of simultaneous end-system node failures to be accommodated in the multicast overlay network; and

preventing data packet losses between end-system nodes in the multicast overlay tree using communication protocols or backpressure mechanisms.

2. The method of claim 1, wherein the step of storing copies of data packets further comprises storing copies of data packets transferred from an input buffer to each one of a plurality of output buffers in a single end-system node, each output buffer corresponding to a separate downstream connection.

3. The method of claim 1, wherein the step of preventing data packet losses comprises preventing overflow in the input buffers located in the end-system nodes using the backpressure mechanisms by communicating available space in an input buffer of a given node to other nodes in the multicast overlay tree;

and communicating significant reductions in available space in the input buffer of the given node to the other nodes.

4. The method of claim 1, wherein the step of preventing data packet losses comprises preventing overflow in the output buffers located in the end-system nodes using the backpressurc mechanisms by blocking transfer of a data packet from an input buffer to an output buffer of a given node unless sufficient space exists in the output buffer to accommodate the data packet.

5. A method for delivering data packets from a source node to a plurality of end-system nodes in a multicast overlay tree with scalable group communication throughput and end-to-end reliability, the method comprising:

providing at least one backup buffer in each one of a group of end-system nodes in the multicast network tree;

storing copies of data packets transferred from an input buffer to an output buffer in one of the group of end-system nodes in the backup buffer;

sizing the back-up buffer in accordance with maximum sizes of the input and output buffers and a number of simultaneous end-system node failures to be accommodated in the multicast overlay network;

detecting at least one end-system node failure in the multicast overlay tree; and

reconnecting orphaned end-system nodes created by the failure of the one end-system node to the multicast overlay tree to provide reliable data packet transfer to all remaining end-system nodes in the multicast overlay tree while maintaining the delivery of a complete sequence of data packets from the source node to each one of the remaining end-system nodes.

6. The method of claim 5, wherein the step of detecting at least one end-system node failure further comprises detecting a plurality of simultaneous end-system node failures, and the step of reconnecting orphaned end-system nodes further comprises simultaneously reconnecting to the multicast overlay tree all of the orphaned end-system nodes that were created by the plurality of end-system node failures.

8. The method of claim 5, wherein the step of detecting at least one end-system node failure comprises using heart beat probes or using keep-alive signals.

9. The method of claim 5, wherein the step of reconnecting orphaned end-system nodes further comprises:

reconnecting each orphaned end-system node of the failed end-system node to a substitute mother node belonging to a subtree of a surviving ancestor node of the failed end-system node; and

retransmitting copies of data packets stored in the backup buffer in the surviving ancestor node through the subtree.

10. The method of claim 9, wherein the surviving ancestor node is the first surviving node in a path from the failed end-system node to the source node.

11. The method of claim 9, wherein the step of reconnecting each one of the orphaned nodes further comprises using a greedy heuristic.

12. The method of claim 11, wherein the step of using the greedy heuristic comprises:

selecting an orphaned subtree having a largest depth from a plurality of orphaned subtrees rooted at orphaned daughter nodes of the failed end-system node;

choosing a substitute mother node that is closest to the source node;

connecting the selected orphaned subtree to the chosen substitute mother node; and

repeating the selection of orphaned subtrees until all orphaned subtrees have been connected to substitute mother nodes.

13. The method of claim 9, wherein the step of retransmitting copies of data packets stored in the backup buffer comprises providing each reconnected orphaned node with a sufficient amount of copies of data packets such that each reconnected orphaned node receives a complete sequence of data packets from the source node.

14. The method of claim 9, further comprising:

distributing information about the reconnected orphaned nodes in the multicast overlay tree up the tree to the source node; and

distributing ancestor end-system node information to the reconnected orphaned nodes.

15. The method of claim 5, further comprising:

forwarding the stored copies of the data packets from each backup buffer to the reconnected orphaned nodes.

16. The method of claim 5, wherein each backup buffer, input buffer and output buffer comprises a finite size.

17. The method of claim 5, wherein the size of each backup buffer is B_BACK, and B_BACK≧

m)B_OUT^max+B_IN^max)+B_OUT^max, where B_OUT^max is a maximum output buffer size, B_IN^max is a maximum input buffer size and in is the number of simultaneous end-system node failures that can be accommodated by the data packet copies stored in the backup buffer.

18. The method of claim 5, further comprising disconnecting an end-system node from the multicast overlay tree by:

notifying a mother node and all daughter nodes of the end-system node to be disconnected about of the pending disconnection;

disconnecting the end-system node from the mother node and all of the daughter nodes;

reconnecting each disconnected daughter node of the disconnected end-system node to a substitute mother node belonging to a subtree of a surviving ancestor node of the disconnected end-system node; and

retransmitting copies of data packets stored in a backup buffer in the surviving ancestor node through the subtree.

19. The method of claim 5, further comprising connecting a new end-system node to the multicast overlay tree by:

contacting the source node;

identifying a mother node for connecting a new end-system node; and

connecting the new end-system node to the identified mother node.

20. The method of claim 19, further comprising notifying the new end-system node regarding buffer size constraints in the multicast overlay tree.

21. The method of claim 19, wherein the identified mother node comprises a distant leaf node to provide the great amount of transmitted data from the source node to the new end-system node.

22. The method of claim 19, wherein the step of identifying a mother node comprises identifying an active end-system node having sufficient available out-degree capacity to accommodate the new end-system node.

23. The method of claim 19, further comprising distributing updated topology information throughout the multicast overlay tree.

7. The method of clam 5, further comprising using overlay tree topology stored in one or more end-system nodes to facilitate reconnecting the orphaned end-system nodes to the multicast overlay tree.

24. A method for delivering data packets from a source node to a plurality of end-system nodes in an multicast overlay tree with scalable group communication throughput and end-to-end reliability, the method comprising:

providing at least one backup buffer in each one of a group of end-system nodes in the multicast network tree;

storing copies of data packets transferred from an input buffer to an output buffer in one of the group of end-system nodes in the backup buffer;

sizing the back-up buffer in accordance with maximum sizes of the input and output buffers and a number of simultaneous end-system node failures to be accommodated in the multicast overlay network;

preventing data packet losses between end-system nodes in the multicast overlay tree using communication protocols or backpressure mechanisms;

detecting at least one end-system node failure in the multicast overlay tree; and

reconnecting orphaned end-system nodes created by the failure of the one end-system node to the multicast overlay tree to provide reliable data packet transfer to all remaining end-system nodes in the multicast overlay tree while maintaining the delivery of a complete sequence of data packets from the source node to each one of the remaining end-system nodes.

25. The method of claim 24, wherein the step of preventing data packet losses comprises:

using a transmission control protocol to transfer data packets between end-system nodes in the multicast overlay tree; and

preventing overflow in input and output buffers in the end-system nodes using the backpressure mechanisms.

26. The method of claim 25, wherein the backpressure mechanisms comprise:

communicating available space in an input buffer of a given end-system node to other end-system nodes in the multicast overlay tree;

communicating significant reductions in available space in the input buffer of the given end-system node to the other end-system nodes; and

blocking transfer of a data packet from the input buffer to an output buffer of the given end-system node unless sufficient space exists in the output buffer to accommodate the data packet.

27. The method of claim 24, wherein the step of detecting at least one end-system node failure further comprises detecting a plurality of simultaneous end-system node failures, and the step of reconnecting orphaned end-system nodes further comprises simultaneously reconnecting to the multicast overlay tree all of the orphaned end-system nodes created by the plurality of end-system node failures by:

reconnecting each orphaned node of each failed node to substitute mother nodes belonging to subtrees of surviving ancestor nodes of the failed nodes; and

copies of data packets stored in the backup buffers in the surviving ancestor nodes through all subtrees.

28. The method of claim 27, wherein the step of reconnecting each one of the orphaned nodes comprises using a greedy heuristic comprising:

selecting an orphaned subtree having a largest depth from a plurality of orphaned subtrees rooted at orphaned daughter nodes of the failed node;

choosing a substitute mother node that is closest to the source node;

connecting the selected orphaned subtree to the chosen substitute mother node; and

repeating the selection of orphaned subtrees until all orphaned subtrees have been connected to substitute mother nodes.

29. The method of claim 27, further comprising:

distributing information about the reconnected orphaned nodes in the multicast overlay tree up the tree to the source node; and

distributing ancestor end-system node information to the reconnected orphaned nodes.

30. The method of claim 24, further comprising:

forwarding the stored copies of the data packets from each backup buffer to the reconnected orphaned nodes.

31. The method of claim 24, wherein the size of each backup buffer is B_BACK, and B_BACK≧

m(B_OUT^max+B_IN^max)+B_OUT^max, where B_OUT^max is a maximum output buffer size, B_IN^max is a maximum input buffer size and ,n is the number of simultaneous end-system node failures that can be accommodated by the data packet copies stored in the backup buffer.

32. The method of claim 24, further comprising disconnecting an end-system node from the multicast overlay tree by:

notifying a mother node and all daughter nodes of the end-system node to be

disconnected about of the pending disconnection;

disconnecting the end-system node from the mother node and all of the daughter nodes;

reconnecting each disconnected daughter node of the disconnected end-system node to a substitute mother node belonging to a subtree of a surviving ancestor node of the disconnected end-system node; and

retransmitting copies of data packets stored in a backup buffer in the surviving ancestor node through the subtree.

33. The method of claim 24, further comprising connecting a new end-system node to the multicast overlay tree by:

contacting the source node;

identifying a mother node having sufficient available out-degree capacity to accommodate the new end-system node;

connecting the new end-system node to the identified mother node;

notifying the new end-system node regarding buffer size constraints in the multicast overlay tree; and

distributing updated topology information throughout the multicast overlay tree.

34. A computer readable medium encoded with computer executable instructions, the computer executable instructions when read by a computer causes the computer to perform a method for delivering data packets from a source node to a plurality of end-system nodes in a multicast overlay tree with scalable group communication throughput and end-to-end reliability, the method comprising:

providing at least one backup buffer in each one of a group of end-system nodes in the multicast network tree;

storing copies of data packets transferred from an input buffer to an output buffer in one of the group of end-system nodes in the backup buffer;

sizing the back-up buffer in accordance with maximum sizes of the input and output buffers and a number of simultaneous end-system node failures to be accommodated in the multicast overlay network; and

preventing data packet losses between end-system nodes in the multicast overlay tree using communication protocols or backpressure mechanisms.

35. The computer readable medium of claim 34, wherein the step of preventing data packet losses comprises:

using a transmission control protocol to transfer data packets between end-system nodes in the multicast overlay tree; and

preventing overflow in input and output buffers in the end-system nodes using the backpressure mechanisms.

36. The computer readable medium of claim 35, wherein the backpressure mechanisms comprise:

communicating available space in an input buffer of a given end-system node to other end-system nodes in the multicast overlay tree;

communicating significant reductions in available space in the input buffer of the given end-system node to the other end-system nodes; and

blocking transfer of a data packet from the input buffer to an output buffer of the given end-system node unless sufficient space exists in the output buffer to accommodate the data packet.

37. A computer readable medium encoded with computer executable institutions, the computer executable instructions when read by a computer causes the computer to perform a method for delivering data packets from a source node to a plurality of end-system nodes in a multicast overlay tree with scalable group communication throughput and end-to-end reliability, the method comprising:

providing at least one backup buffer in each one of a group of end-system nodes in the multicast network tree;

storing copies of data packets transferred from an input buffer to an output buffer in one of the group of end-system nodes in the backup buffer;

sizing the back-up buffer in accordance with maximum sizes of the input and output buffers and a number of simultaneous end-system node failures to be accommodated in the multicast overlay network; and

detecting at least one end-system node failure in the multicast overlay tree; and

reconnecting orphaned end-system nodes created by the failure of the one end-system node to the multicast overlay tree to provide reliable data packet transfer to all remaining end-system nodes in the multicast overlay tree while maintaining the delivery of a complete sequence of data packets from the source node to each one of the remaining end-system nodes.

38. The computer readable medium of claim 37, wherein the step of reconnecting orphaned end-system nodes further comprises:

reconnecting each orphaned end-system node of the failed end-system node to a substitute mother node belonging to a subtree of a surviving ancestor node of the failed end-system node; and

retransmitting copies of data packets stored in a backup buffer in the surviving ancestor node through the subtree.

39. The computer readable medium of claim 38, wherein:

the surviving ancestor node is the first surviving node in a path from the failed end-system node to the source node; and

the step of reconnecting each one of the orphaned end-system nodes comprises using a greedy heuristic.

40. The computer readable medium of claim 39, wherein the step of using the greedy heuristic comprises:

selecting an orphaned subtree having a largest depth from a plurality of orphaned subtrees rooted at orphaned daughter nodes of the failed end-system node;

choosing a substitute mother node that is closest to the source node;

connecting the selected orphaned subtree to the chosen substitute mother node; and

repeating the selection of orphaned subtrees until all orphaned subtrees have been connected to substitute mother nodes.

41. The computer readable medium of claim 37, wherein the step of detecting at least one end-system node failure further comprises detecting a plurality of simultaneous end-system node failures, and the step of reconnecting orphaned end-system nodes further comprises simultaneously reconnecting to the multicast overlay tree all of the orphaned end-system nodes created by the plurality of end-system node failures by:

reconnecting each orphaned node of each failed node to substitute mother nodes belonging to subtrees of surviving ancestor nodes of the failed nodes; and

retransmitting copies of data packets stored in backup buffers in the surviving ancestor nodes through all subtrees.

42. The computer readable medium of claim 37, wherein the method further comprises:

forwarding the stored copies of the data packets from each backup buffer to the reconnected orphaned nodes;

wherein the size of each backup buffer is B_BACK, and B_BACK≧

m(B_OUT^max+B_IN^max)+B_OUT^max, where B_OUT^max is a maximum output buffer size, B_IN^maxis a maximum input buffer size and in is the number of simultaneous node failures that can be accommodated by the data packet copies stored in the backup buffer.

43. The computer readable medium of claim 37, wherein the method further comprises disconnecting an end-system node from the multicast overlay tree by:

notifying a mother node and all daughter nodes of the end-system node to be disconnected about of the pending disconnection;

disconnecting the end-system node from the mother node and all of the daughter nodes;

reconnecting each disconnected daughter node of the disconnected end-system node to a substitute mother node belonging to a subtree of a surviving ancestor node of the disconnected end-system node; and

retransmitting copies of data packets stored in a backup buffer in the surviving ancestor node through the entire subtree.

44. The computer readable medium of claim 37, wherein the method further comprises connecting a new end-system node to the multicast overlay tree by:

contacting the source node;

identifying a mother node having sufficient available out-degree capacity to accommodate the new end-system node;

connecting the new end-system node to the identified mother node;

notifying the new end-system node regarding buffer size constraints in the multicast overlay tree; and

distributing updated topology information throughout the multicast overlay tree.