Reliable multicast

• US 7,346,699 B1
• Filed: 05/24/2000
• Issued: 03/18/2008
• Est. Priority Date: 05/24/1999
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Scott, Kimberly K., Worley, Fred B., Krause, Michael R.
• Primary Examiner(s): Wiley; David
• Assistant Examiner(s): ENGLAND, DAVID E
• Application Number:
  US09/578,019
• Time in Patent Office: 2,855 Days
• Field of Search: 700/201, 714/478, 709230-237, 709/224, 370412-418, 370/429
• US Class Current: 709/232
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes
• CPC Class Codes: H04L 45/46 Cluster building

Abstract

A reliable multicast service is operated between a source device and multiple destination devices participating in a multicast group. The source device includes a first source application instance (AI) producing a first unit of work stream, and communication services (CS). Each destination device in the multicast group includes CS, and at least one destination AI which consumes units of work. Communication services/fabric provide communication between the source device and the multiple destination devices. Multiple source and destination resources (SDRs) implement corresponding multiple reliable transport services between the source device and corresponding multiple destination devices in the multicast group for delivery of the first unit of work stream to the corresponding destination devices and guaranteeing strong ordering of the first unit of work stream received at the corresponding destination devices.

Claims

1. A data processing system comprising:

a source device participating in a multicast group and including;

a first source application instance (AI) producing a first unit of work stream; and

communication services (CS);

multiple destination devices participating in the multicast group, each destination device in the multicast group including;

at least one destination AI which consumes units of work; and

CS;

communication services/fabric providing communication between the source device and the multiple destination devices;

multiple source and destination resources (SDRs), each SDR implementing an independent reliable transport service between the source device and a corresponding one of the multiple destination devices in the multicast group for delivery of the first unit of work stream at the corresponding one of the multiple destination devices and guaranteeing strong ordering of the first unit of work stream received at the corresponding one of the multiple destination devices, wherein each SDR includes;

first SDR resources at the source device having at least one queue configured to hold transmitted from the source device to the corresponding one of the multiple destination devices but not acknowledged units of work and not yet transmitted units of work; and

second SDR resources at the corresponding one of the multiple destination devices having state information including an expected next sequence number value indicating an expected defined order corresponding to a next unit of work to be received; and

wherein the CS in the source device correlates the independent reliable transport services and verifies that a predetermined percentage of destination AIs in the multicast group reliably receives each unit of work or a cumulative set of units of work in the first unit of work stream in the expected defined order.

2. The data processing system of claim 1 wherein the predetermined percentage is 100% of the destination AIs.

3. The data processing system of claim 1 wherein the predetermined percentage is less than 100% of the destination AIs.

4. The data processing system of claim 1 wherein the CS in the source device includes:

an acknowledgement counter which counts acknowledgements received from the corresponding destination devices in the multicast group indicating that the corresponding destination device has received a unit of work or a cumulative set of units of work in the first unit of work stream.

5. The data processing system of claim 4 wherein the CS in the source device generates a completion event when the acknowledgement counter indicates that the predetermined percentage of destination AIs in the multicast group have acknowledged the unit of work or a cumulative set of units of work has been received.

6. The data processing system of claim 1 wherein the CS in the source device includes:

a bit-mask array which assigns a unique bit for each destination AI in the multicast group and clears each bit as a corresponding acknowledgment is received from the corresponding destination device in the multicast group indicating that the corresponding destination device has received a unit of work or the cumulative set of units of work in the first unit of work stream.

7. The data processing system of claim 6 wherein the CS in the source device generates a completion event when the bit-mask array has the predetermined percentage of bits cleared in the bit-mask array indicating that the predetermined percentage of destination AIs in the multicast group have acknowledged the unit of work or the cumulative set of units of work has been received.

8. The data processing system of claim 1 wherein the CS in the source device replicates the first unit of work stream for transmission to the destination AIs in the multicast group.

9. The data processing system of claim 1 wherein the communication services/fabric includes at least one replicater component for replicating the first unit of work stream for transmission to the destination AIs in the multicast group.

10. The data processing system of claim 1 wherein the data processing system further comprises:

at least one middleware AI.

11. The data processing system of claim 10 wherein the CS in the source device includes a timing window and if the timing window expires without necessary conditions for a completion event occurring, then the middleware AI or CS tracks and resolves missing acknowledgments.

12. The data processing system of claim 10 wherein a given AI joins the multicast group by performing a multicast join operation, and the middleware AI or CS determines whether the given AI can join the multicast group, validates access rights, and informs the devices participating in the multicast group of changes in the group.

13. The data processing system of claim 10 wherein a given AI leaves the multicast group by performing a multicast leave operation, and the middleware AI or CS informs the devices participating in the multicast group to remove the given AI from the destination list, to complete all in-flight units of work as though the given AI were still present, and to not target the given AI for units of work not yet launched.

14. The data processing system of claim 10 wherein an AI, middleware AI, or CS performs a get attribute operation to query current attributes of the multicast group.

15. The data processing system of claim 10 wherein an AI, middleware AI, or CS performs a set attribute operation to set multicast group attributes.

16. The data processing system of claim 10 wherein middleware AI performs a remove member operation to remove a given AI from the multicast group without involving the given AI.

17. The data processing system of claim 1 wherein an agreed to multicast address is employed to address AIs in the multicast group.

18. The data processing system of claim 17 wherein the CS in each device participating in the multicast group interprets the agreed to multicast address and responds to the agreed to multicast address to perform a reliable multicast operation on behalf of the corresponding destination AI.

19. The data processing system of claim 1 wherein the data processing system performs a reliable multicast operation having substantially the same semantic behavior relative to a given AI as an unreliable multicast operation.

20. The data processing system of claim 1 wherein the multiple SDRs are grouped into multiple SDR groups, wherein each of the multiple SDR groups includes at least one SDR and is assigned a unique priority level for effecting throughput and response time of units of work transmitted by the at least one SDR.

21. The data processing system of claim 1 wherein the source device also functions as a destination device and at least one of the destination devices also functions as a source device.

22. The data processing system of claim 1 wherein each SDR includes:

source SDR resources, at the source device, transmitting the first unit of work stream in a serial unit of work stream having units of work in a defined order over the communication services/fabric; and

destination SDR resources, at the corresponding destination device, receiving the serial unit of work stream, and demultiplexing the serial unit of work stream into units of work provided to the corresponding at least one destination AI.

23. The data processing system of claim 22 wherein the destination SDR resources provide a negative acknowledgement (NAK) for a unit of work received ahead of its defined order.

24. The data processing system of claim 22 wherein the destination SDR resources drop a unit of work received ahead of its defined order.

25. The data processing system of claim 22 wherein the destination SDR resources provide a positive acknowledgement (ACK) for each unit of work which is successfully received and processed by the destination SDR resources.

26. The data processing system of claim 22 wherein the destination SDR resources provide a cumulative positive acknowledgement (ACK) for a set of units of work that indicate that all units of work in the set of units of work up to and including a current unit of work have been successfully received and processed by the destination SDR resources.

27. The data processing system of claim 17 wherein the destination SDR resources drop a unit of work in response to an indication that the unit of work is a duplicate unit of work.

28. A method of processing data comprising:

producing a first unit of work stream with a first source application instance (AI) at a source device participating in a multicast group;

reproducing the first unit of work stream;

establishing multiple source and destination resources (SDRs), each SDR including;

first SDR resources at the source device having at least one queue for holding transmitted from the source device to a corresponding one of the multiple destination devices but not acknowledged units of work and not yet transmitted units of work; and

second SDR resources at the corresponding one of multiple destination devices participating in the multicast group having state information including an expected next sequence number value indicating an expected defined order corresponding to a next unit of work to be received;

implementing corresponding multiple independent reliable transport services with the multiple SDRs, each independent reliable transport service being implemented between the source device and the corresponding one of multiple destination devices, each destination device having at least one destination AI;

multicasting the reproduced first unit of work stream over a communication services/fabric with the multiple independent reliable transport services;

guaranteeing strong ordering of the first unit of work stream received at the corresponding one of multiple destination devices; and

correlating the independent reliable transport services including verifying that a predetermined percentage of destination devices in the multicast group reliably has received each unit of work or a cumulative set of units of work in the first unit of work stream in the expected defined order.

29. The method of claim 28 further comprising the step of:

consuming the fat unit of work stream with the at least one destination AI at each of the multiple destination devices participating in the multicast group.

30. The method of claim 28 wherein the predetermined percentage is 100% of the destination devices.

31. The method of claim 28 wherein the predetermined percentage is less than 100% of the destination devices.

32. The method of claim 28 further comprising the steps of:

providing acknowledgments from the corresponding destination devices in the multicast group indicating that the corresponding destination device has received a unit of work or a cumulative set of units of work in the first unit of work stream; and

counting acknowledgements received at the source device.

33. The method of claim 32 further comprising the step of:

generating a completion event when the acknowledgement counter indicates that the predetermined percentage of destination devices in the multicast group have acknowledged the unit of work or the cumulative set of units of work has been received.

34. The method of claim 28 further comprising the steps of:

assigning a unique bit for each destination device in the multicast group in a bit-mask array; and

clearing each bit as a corresponding acknowledgment is received from the corresponding destination device in the multicast group indicating that the corresponding destination device has received a unit of work or a cumulative set of units of work in the first unit of work stream.

35. The method of claim 34 further comprising the step of:

generating a completion event when the bit-mask array has the predetermined percentage of bits cleared in the bit-mask array indicating that the predetermined percentage of destination AIs in the multicast group have acknowledged the unit of work or the cumulative set of units of work has been received.

36. The method of claim 28 further comprising the step of:

maintaining a timing window; and

if the timing window expires without necessary conditions for a completion event occurring, tracking and resolving missing acknowledgments.

37. The method of claim 28 further comprising the steps of:

performing a multicast join operation to join a given AI into the multicast group including the steps of;

determining whether the given AI can join the multicast group;

validating access rights; and

informing the devices participating in the multicast group of changes in the group.

38. The method of claim 28 further comprising the steps of:

performing a multicast leave operation to permit a given AI to leave the multicast group including informing the devices participating in the multicast group to remove the given AI from the destination list, to complete all in-flight units of work as though the given AI were still present, and to not target the given AI for units of work not yet launched.

39. The method of claim 28 further comprising the step of:

performing a get attribute operation to query current attributes of the multicast group.

40. The method of claim 28 further comprising the step of:

performing a set attribute operation to set multicast group attributes.

41. The method of claim 28 further comprising the step of:

performing a remove member operation to remove a given AI from the multicast group without involving the given AI.

42. The method of claim 28 further comprising the step of:

addressing AIs in the multicast group with an agreed to multicast address.

43. The method of claim 28 further comprising the steps of:

grouping the multiple reliable transport services into multiple reliable transport service groups, wherein each of the multiple reliable transport service groups includes at least one reliable transport service; and

assigning a unique priority level to each reliable transport service group for effecting throughput and response time of units of work transmitted by the at least one reliable transport service.

44. The method of claim 28 wherein the source device also functions as a destination device and at least one of the destination devices also functions as a source device.

45. The method of claim 28 further comprising the step of:

providing a negative acknowledgement (NAK) for a unit of work received at a corresponding destination device ahead of a defined order assigned to the unit of work.

46. The method of claim 28 further comprising the step of:

dropping a unit of work received at a corresponding destination device ahead of a defined order assigned to the unit of work.

47. The method of claim 28 further comprising the step of:

temporarily storing a unit of work received at a corresponding destination device ahead of a defined order assigned to the unit of work.

48. The method of claim 47 further comprising the step of:

performing a resynchronization operation to recover a missing intermediate unit of work.

49. The method of claim 28 further comprising the step of:

providing a positive acknowledgement (ACK) for each unit of work which is successfully received and processed at a corresponding destination device.

50. The method of claim 28 further comprising the step of:

providing a cumulative positive acknowledgement (ACK) for a set of units of work that indicate that all units of work in the set of units of work up to and including a current unit of work have been successfully received and processed at a corresponding destination device.

51. The method of claim 28 further comprising the steps of:

indicating that the unit of work is a duplicate unit of work based on the unit of work being received at a corresponding destination device behind a defined order assigned to the unit of work; and

dropping the unit of work in response to the indication that the unit of work is a duplicate unit of work.