Methods, systems and computer program products for differencing data communications using a message queue

• US 6,279,041 B1
• Filed: 11/13/1998
• Issued: 08/21/2001
• Est. Priority Date: 11/13/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wesley, Ajamu Akinwunmi, Hind, John R., Britton, Kathryn H., Baber, Stephen B., Housel, Barron C. III
• Primary Examiner(s): Meky, Moustafa M.
• Assistant Examiner(s): EDELMAN, BRADLEY E
• Application Number:
  US09/192,128
• Time in Patent Office: 1,012 Days
• Field of Search: 709/247, 709/232, 709/231, 709/230, 370/235, 370/229
• US Class Current: 709/232
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/43 Assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]
• CPC Class Codes: H04W 28/14 using intermediate storage
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]

Abstract

Method, apparatus and program products for increasing the performance of communications using differencing data communications over a message queue supporting asynchronous communications from a variety of applications executing on a source device over a shared external communication link to destination devices are provided. A data stream between the source device and the destination device is segmented based on the type of the data stream to provide a logical segmentation which increases the occurrence of repeated transmissions of a segment. The segments are then placed in the message queue as a message for transport to a destination computer. Differencing is provided by replacing the segment with an associated identifier for segments which have previously been transported to provide a reduced volume of data for transmittal based on recognition and replacement of data segments which have previously been transmitted by the source device. The destination device receives the transmitted reduced segments as messages in a receive message queue and reconstructs the data stream. Synchronization between the differencing caches of the devices is not required as the communication is asynchronous through a message queue and, if a reduced segment is not recognized, retransmission of the complete segment instead of the associated identifier may be requested and the source device creates and queues the segment as a message.

Claims

1. A method for differencing data communications using a message queue, the method comprising the steps of:

intercepting a data stream having an associated type from a host application prior to transmission of the data stream through the message queue on an external communication link to a destination computer;

segmenting the data stream based on the associated type to provide a plurality of segments;

placing message identifiers associated with the plurality of segments into the message queue;

selecting one of the plurality of segments from the message queue for transport;

determining if the selected segment has previously been transported;

reducing the selected segment to a differenced communication format based upon whether it has previously been transported to provide a reduced segment;

emitting the reduced segment;

verifying that the differenced communication format of the reduced segment is known to the destination computer;

dequeuing the selected segment; and

placing the selected segment in a differencing cache if it has not previously been transported.

2. A method according to claim 1 wherein the message identifiers associated with the plurality of segments are the associated segments.

3. A method according to claim 1 wherein the message identifiers associated with the plurality of segments are pointers to a location in memory where associated segments can be found.

4. A method according to claim 1 wherein the determining step comprises the steps of:

calculating an identifier for the selected segment; and

determining based on the calculated identifier if the selected segment corresponds to a segment saved in the differencing cache.

5. A method according to claim 4 wherein the message queue receives messages from a plurality of data streams and a synchronously emits the messages on the external communication link.

6. A method according to claim 5 wherein the messages are emitted in a first in first out sequence from the message queue and wherein the message queue has an associated maximum message size.

7. A method according to claim 4 wherein the dequeuing step includes the step of placing the identifier of the selected segment in a differencing index and wherein the determining based on the identifier step includes the step of determining if the identifier of the selected segment is in the differencing index.

8. A method according to claim 7 wherein the differencing index is associated with a least recently used list and wherein the placing step includes the step of removing a least recently used segment from the differencing cache and the differencing index if the differencing cache exceeds a size criteria.

9. A method according to claim 7 wherein the reducing step includes the step of replacing the selected segment with the identifier associated with the selected segment to provide the reduced segment if the selected segment has previously been emitted and providing the selected segment as the reduced segment if the selected segment has not previously been emitted.

10. A method according to claim 9 wherein the verifying step includes the step of receiving a message from the destination computer indicating whether the destination computer had a segment in memory corresponding to the emitted identifier.

11. A method according to claim 10 wherein the emitting step further comprises the step of emitting the selected segment rather than the identifier associated with the selected segment if the received message indicates that the destination computer did not have a segment in memory corresponding to the emitted identifier.

12. A method according to claim 7 wherein the step of placing an identifier further comprises the step of placing a pointer in the differencing cache enabling the selected segment to be located in the differencing cache.

13. A method according to claim 4 further comprising the steps performed at the destination computer of:

receiving the emitted reduced segment;

reconstructing the selected segment from the received reduced segment;

placing the reconstructed selected segment in a received message queue; and

reconstructing the data stream responsive to the received message queue.

14. A method according to claim 13 wherein the reconstructing the selected segment step includes the steps of:

determining if the reduced segment contains the selected segment;

determining if a segment associated with the reduced segment is available to the destination computer if the reduced segment does not contain the selected segment;

replacing the reduced segment with the segment associated with the reduced segment if available; and

emitting a message to a device from which the reduced segment is received requesting transmission of the selected segment if the segment associated with the reduced segment is not available.

15. A method according to claim 13 wherein the reconstructing the data stream step comprises the step of integrating segments from the received message queue into objects.

16. A method according to claim 13 further comprising the step of dequeuing the reconstructed selected segment from the received message queue after providing the reconstructed selected segment to the reconstructing step.

17. A method according to claim 16 wherein the dequeuing step includes the step of placing the identifier of the selected segment in a destination computer differencing index and placing the reconstructed selected segment in a destination computer differencing cache if the reduced segment contains the selected segment.

18. A method according to claim 1 wherein the segmenting step includes the steps of:

determining the associated type of the data stream;

selecting a rule set for segmenting the data stream based on the determined type; and

applying the selected rule set to segment the data stream.

19. A method according to claim 18 wherein the determining the associated type step comprises the step of determining the associated type of the data stream based on the data stream.

20. A method according to claim 18 wherein the associated type is a MIME type.

21. An apparatus for differencing data communications using a message queue, comprising:

means for intercepting a data stream having an associated type from a host application prior to transmission of the data stream through the message queue on an external communication link to a destination computer;

means for segmenting the data stream based on the associated type to provide a plurality of segments;

means for placing message identifiers associated with the plurality of segments into the message queue;

means for selecting one of the plurality of segments from the message queue for transport;

means for determining if the selected segment has previously been transported;

means for reducing the selected segment to a differenced communication format based upon whether it has previously been transported to provide a reduced segment;

means for emitting the reduced segment;

means for verifying that the differenced communication format of the reduced segment is known to the destination computer;

means for dequeuing the selected segment; and

means for placing the selected segment in a differencing cache if it has not previously been transported.

22. An apparatus according to claim 21 wherein the message identifiers associated with the plurality of segments are the associated segments.

23. An apparatus according to claim 21 wherein the message identifiers associated with the plurality of segments are pointers to a location in memory where associated segments can be found.

24. An apparatus according to claim 21 wherein the means for determining comprises:

means for calculating an identifier for the selected; and

means for determining based on the calculated identifier if the selected segment corresponds to a segment saved in the differencing cache.

25. An apparatus according to claim 24 wherein the message queue receives messages from a plurality of data streams and asynchronously emits the messages on the external communication link.

26. An apparatus according to claim 25 wherein the messages are emitted in a first in first out sequence from the message queue and wherein the message queue has an associated maximum message size.

27. An apparatus according to claim 24 wherein the means for dequeuing includes means for placing the identifier of the selected segment in a differencing index and wherein the means for determining based on the identifier includes means for determining if the identifier of the selected segment is in the differencing index.

28. An apparatus according to claim 27 wherein the differencing index is associated with as least recently used list and wherein the means for placing includes means for removing a least recently used segment from the differencing cache and the differencing index if the differencing cache exceeds a size criteria.

29. An apparatus according to claim 27 wherein the means for reducing includes means for replacing the selected segment with the identifier associated with the selected segment to provide the reduced segment if the selected segment has previously been emitted and providing the selected segment as the reduced segment if the selected segment has not previously been emitted.

30. An apparatus according to claim 29 wherein the means for verifying includes means for receiving a message from the destination computer indicating whether the destination computer had a segment in memory corresponding to the emitted identifier.

31. An apparatus according to claim 30 wherein the means for emitting further comprises means for emitting the selected segment rather than the identifier associated with the selected segment if the received message indicates that the destination computer did not have a segment in memory corresponding to the emitted identifier.

32. An apparatus according to claim 27 wherein the means for placing an identifier further comprises means for placing a pointer in the differencing cache enabling the selected segment to be located in the differencing cache.

33. An apparatus according to claim 24 wherein the destination computer further comprises:

means for receiving the emitted reduced segment;

means for reconstructing the selected segment from the received reduced segment;

means for placing the reconstructed selected segment in a received message queue; and

means for reconstructing the data stream responsive to the received message queue.

34. An apparatus according to claim 33 wherein the means for reconstructing the selected segment includes:

means for determining if the reduced segment contains the selected segment;

means for determining if a segment associated with the reduced segment is available to the destination computer if the reduced segment does not contain the selected segment;

means for replacing the reduced segment with the segment associated with the reduced segment if available; and

means for emittting a message to a device from which the reduced segment is received requesting transmisssion of the selected segment if the segment associated with the reduced segment is not available.

35. An apparatus according to claim 33 wherein the means for reconstructing the data stream step comprises means for integrating segments from the received message queue into objects.

36. An apparatus according to claim 33 further comprising means for dequeuing the reconstructed selected segment from the received message queue after providing the reconstructed selected segment to the reconstructing step.

37. An apparatus according to claim 36 wherein the means for dequeuing includes means for placing the identifier of the selected segment in a destination computer differencing index and placing the reconstructed selected segment in a destination computer differencing cache if the reduced segment contains the selected segment.

38. An apparatus according to claim 21 wherein the means for segmenting includes:

means for determining the associated type of the data stream;

means for selecting a rule set for segmenting the data stream based on the determined type; and

means for applying the selected rule set to segment the data stream.

39. An apparatus according to claim 38 wherein the means for determining the associated type comprises means for determining the associated type of the data stream based on the data stream.

40. An apparatus according to claim 38 wherein the associated type is a MIME type.

41. A computer program product for differencing data communications using a message queue, the computer program product comprising:

a computer-readable storage medium having computer-readable program code means embodied in said medium, said computer-readable program code means comprising;

computer readable program code means for intercepting a data stream having an associated type from a host application prior to transmission of the data stream through the message queue on an external communication link to a destination computer;

computer readable program code means for segmenting the data stream based on the associated type to provide a plurality of segments;

computer readable program code means for placing message identifiers associated with the plurality of segments into the message queue;

computer readable program code means for selecting one of the plurality of segments from the message queue for transport;

computer readable program code means for determining if the selected segment has previously been transported;

computer readable program code means for reducing the selected segment to a differenced communication format based upon whether it has previously been transported to provide a reduced segment;

computer readable program code means for emitting the reduced segment;

computer readable program code means for verifying that the differenced communication format of the reduced segment is known to the destination computer;

computer readable program code means for dequeuing the selected segment; and

computer readable program code means for placing the selected segment in a differencing cache if it has not previously been transported.

42. A computer program product according to claim 41 wherein the message identifiers associated with the plurality of segments are the associated segments.

43. A computer program product according to claim 41 wherein the message identifier associated with the plurality of segments are pointers to a location in memory where associated segments can be found.

44. A computer program product according to claim 41 wherein the computer readable program code means for determining comprises:

computer readable program code means for calculating an identifier for the selected segment; and

computer readable program code means for determining based on the calculated identifier if the selected segment corresponds to a segment saved in the differencing cache.

45. A computer program product according to claim 44 wherein the message queue receives message from a plurality of data streams and asynchronously emits the messages on the external communication link.

46. A computer program product according to claim 45 wherein the messages are emitted in a first in first out sequence from the message queue and wherein the message queue has an associated maximum message size.

47. A computer program product according to claim 44 wherein the computer readable program code means for dequeuing includes computer readable program code means for placing the identifier of the selected segment in a differencing index and wherein the computer readable program dode means for determining based on the identifier includes computer readable program code means for determining if the identifier of the selected segment is in the differencing index.

48. A computer program product according to claim 47 wherein the differencing index is associated with a least recently used list and wherein the computer readable program code means for placing includes computer readable program code means for removing a least recently used segment from the differencing cache and the differencing index if the differencing cache exceeds a size criteria.

49. A computer program product according to claim 47 wherein the computer readable program code means for reducing includes computer readable program code means for replacing the selected segment with the identifier associated with the selected segmant to provide the reduced segment if the selected segment has previously been emitted and providing the selected segment as the reduced segment if the selected segment has not previously been emitted.

50. A computer program product according to claim 49 wherein the computer readable program code means for verifying includes computer readable program code means for receiving a message form the destination computer indicating whether the destination computer had a segment in memory corresponding to the emitted identifier.

51. A computer program product according to claim 50 wherein the computer readable program code means for emitting further comprises computer readable program code means for emitting the selected segment rather than the identifier associated with the selected segment if the received message indicates that the destination computer did not have a segment in memory corresponding to the emitted identifier.

52. A computer program product according to claim 47 wherein the computer readable program code means for placing an identifier further comprises computer readable program code means for placing a pointer in the differencing cache enabling the selected segment to be located in the differencing cache.

53. A computer program product according to claim 44 further comprising code for the destination computer including:

computer readable program code means for receiving the emitted reduced segment;

computer readable program code means for reconstructing the selected segment from the received reduced segment;

computer readable program code means for placing the reconstructed selected segment in a received message queue; and

computer readable program code means for reconstructing data stream responsive to the received message queue.

54. A computer program product according to claim 53 wherein the computer readable program code means for reconstructing the selected segment includes:

computer readable program code means for determining if the reduced segment contains the selected segment;

computer readable program code means for determining if a segment associated with the reduced segment is available to the destination computer if the reduced segment does not contain the selected segment;

computer readable program code means for replacing the reduced segment with the segment associated with the reduced segment if available; and

computer readable program code means for emitting a message to a device from which the reduced segment is received requesting transmission of the selected segment if the segment associated with the reduce segment is not available.

55. A computer program product according to claim 53 wherein the computer readable program code means for reconstructing the data stream step comprises computer readable program code means for integrating segments from the received message queue into objects.

56. A computer program product according to claim 53 further comprising computer readable program code means for dequeuing the reconstructed selected segment from the received message queue after providing the reconstructed selected segment to the reconstructing step.

57. A computer program product according to claim 56 wherein the computer readable program code means for dequeuing includes computer readable program code means for placing the identifier of the selected segment in a destination computer differencing index and placing the reconstructed selected segment in a destination computer differencing cache if the reduced segment contains the selected segment.

58. A computer program product according to claim 41 wherein the computer readable program code means for segmenting includes:

computer readable program code means for determining the associated type of the data stream;

computer readable program code means for selecting a rule set for segmenting the data stream based on the determined type; and

computer readable program code means for applying the selected rule set to segment the data stream.

59. A computer program product according to claim 58 wherein the computer readable program code means for determining the associated type comprises computer readable program code means for determining the associated type of the data stream based on the data stream.

60. A computer program product according to claim 58 wherein the associated type is a MIME type.