Reliable messaging using clocks with synchronized rates

• US 20060064464A1
• Filed: 09/21/2004
• Published: 03/23/2006
• Est. Priority Date: 09/21/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Langworthy, David E., Kakivaya, Gopala Krishna R.
• Granted Patent: US 7,483,943 B2
• Time in Patent Office: Days
• US Class Current: 709/206
• CPC Class Codes: H04L 1/1621 Group acknowledgement, i.e. the acknowledgement message defining a range of identifiers, e.g. of sequence numbers
• CPC Class Codes: H04L 1/1685 the supervisory signal being transmitted in response to a specific request, e.g. to a polling signal
• CPC Class Codes: H04L 1/1848 Time-out mechanisms
• CPC Class Codes: H04L 1/188 Time-out mechanisms
• CPC Class Codes: H04L 1/1883 using multiple timers
• CPC Class Codes: H04L 63/04 for providing a confidential data exchange among entities communicating through data packet networks
• CPC Class Codes: H04L 63/06 for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols
• CPC Class Codes: H04L 69/326 in the transport layer [OSI layer 4] H04L69/16 takes precedence
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

The present invention extends to methods, systems, and computer program products for reliable messaging using clocks with synchronized rates. Embodiments of the present invention insure at-most-once delivery of messages. A source and a destination utilize clocks with synchronized rates. Messages are assigned Time-To-Live (“TTL”) values such that state information is updated the source and removed at the destination when a corresponding message timer based on a TTL value expires. Accordingly, resources consumed to maintain state information at the destination can be freed up in a shorter period of time. The source can retransmit state information to the message destination if relevant state information has been removed. Message processor instance IDs insure at-most-once delivery when a message destination suffers an involuntary memory loss. Embodiments of the present invention can also be used for exactly-once-delivery, for example, when TTL values are infinite and instance IDs are not used.

Claims

1. At a destination computer system that is network connectable along with one or more other computer systems to a network, the destination computer system and at least one of the other computer systems having synchronized clock rates, a method for reliably processing a message, the method comprising:

an act of receiving a first copy of a message having a message ID and a TTL value, the message ID identifying the position of the message in an interaction between a message source and the destination computer system, the TTL value indicating when the message is to expire;

an act of updating an interaction cache to indicate that the message has been received;

an act of receiving a second copy of the message subsequent to processing the first copy of the message, the second copy of the message having the message ID; and

an act of discarding the second copy of the message based on the interaction cache indicating that a message having the message ID was previously processed.

2. The method as recited in claim 1, wherein an act of receiving a first copy of a message comprises an act of receiving a first copy of the message that includes the message ID, an interaction ID, the TTL value, and application data, the interaction ID identifying a specific interaction between the message source and the destination computer system, the clock rate of the message source and destination computer system being synchronized.

3. The method as recited in claim 2, wherein the act of updating an interaction cache to indicate that the message has been received comprises an act of storing the message ID and the interaction ID in the interaction cache.

4. The method as recited in claim 1, further comprising:

an act of sending an acknowledgment that the message was received to the message source subsequent to processing the message.

5. The method as recited in claim 1 wherein, the act of receiving a second copy of the message comprises an act of receiving the second copy of the message prior to expiration of a countdown timer based on the TTL value.

6. The method as recited in claim 1, wherein, the act of receiving a second copy of the message comprises an act of receiving the second copy of the message subsequent to expiration of a countdown timer based on the TTL value.

7. The method as recited in claim 1, wherein the an act of discarding the second copy of the message based on the interaction cache comprises an act of determining the message ID and interaction ID included in the second message are stored in the interaction cache.

8. The method as recited in claim 1, wherein the destination computer system includes a Web server and the message source is a Web browser.

9. The method as recited in claim 1, further comprising:

an act of sending a token that includes an encrypted session key to the message source, the session key being encrypted with a private key of a public/private key pair, the session key for securing the interaction between the message source and the destination computer system.

10. The method as recited in claim 9, further comprising:

an act receiving the security token after the interaction has been removed from the interaction cache;

an act of decrypting the token to reveal the session key; and

an act of using the session key to secure the interaction even through the interaction was removed from the interaction cache.

11. At a destination computer system that is network connectable along with one or more other computer systems to a network, the destination computer system and at least one of the other computer systems having synchronized clock rates, a method for reliably processing a message, the method comprising:

an act of receiving a first copy of a message having an interaction ID, a message ID, and a TTL value, the message ID identifying the position of the message in an interaction specified by the interaction ID and the TTL value indicating when the message is to expire;

an act of removing at least the message ID from an interaction cache subsequent to expiration of a countdown timer based on the TTL value;

an act of receiving a second copy of the message subsequent to removing the message ID from the interaction cache;

an act of sending a request for an indication of the progress of the interaction ID to a message source, the message source having a clock rate that is synchronized with the clock rate of the destination computer system;

an act of receiving an indication that the interaction has progressed such that a message having the message ID can be discarded; and

an act of discarding the second copy of the message.

12. The method as recited in claim 11, further comprising:

an act of receiving the first copy of the message from the message source, the first copy of the message including application data; and

an act of delivering the application data to a corresponding message processor instance.

13. The method as recited in claim 11, further comprising:

an act of updating the interaction cache to indicate that the message has been received prior to removing the message ID from the interaction cache.

14. The method as recited in claim 11, wherein the act of removing at least the message ID from an interaction cache comprises an act of forgetting the progress of the interaction specified by the interaction ID without terminating participation in the interaction.

15. The method as recited in claim 11, further comprising:

an act of sending an acknowledgment that the message was received to the message source subsequent to processing the message.

16. The method as recited in claim 11, wherein the act of removing the message ID from the interaction cache comprises detecting that the interaction identified by the interaction ID has been idle for a specified period of time.

17. The method as recited in claim 11, wherein the act of removing the message ID from the interaction cache comprises removing the entire interaction specified by the interaction ID.

18. The method as recited in claim 11, further comprising:

an act of detecting that the interaction cache does not include a message ID for the interaction identified by the interaction ID included in the second copy of the message subsequent to receiving the second copy of the message.

19. The method as recited in claim 11, wherein the act of sending a request for an indication of the progress of the interaction ID to the message source comprises an act of sending a REQACKACK.

20. The as recited in claim 21, wherein the act of sending a REQACKACK comprises an act of sending a REQACKACK that includes one or more of the interaction ID and an instance ID

21. The method as recited in claim 11, wherein the act of receiving an indication that the interaction has progressed such that a message having the message ID can be discarded comprises an act of receiving an ACKACK from the message source, the ACKACK including the message ID and the interaction ID.

22. The method as recited in claim 11, wherein the act of receiving an indication that the interaction has progressed such that a message having the message ID can be discarded comprises an act of receiving an ACKACK that also indicates one or more additional message IDs have timed out at the message source and no longer require acknowledgement.

23. The method as recited in claim 11, wherein the act of receiving an indication that the interaction has progressed such that a message having the message ID can be discarded comprises an act of receiving progress information related to the interaction such that the destination computer system can participate in the interaction even though the progress of the interaction was previously removed from the interaction cache.

24. The method as recited in claim 11, wherein the act of receiving an indication that the interaction has progressed such that a message having the message ID can be discarded comprises an act of receiving an ACKACK that includes the message ID, an interaction ID, and a security token.

25. The method as recited in claim 11, wherein the an act of discarding the second copy of the message comprises determining the message ID and interaction ID included in the second message match the message ID and interaction ID in the ACKACK

26. The method as recited in claim 11, wherein the destination computer system includes a Web server and the message source is a Web browser.

27. At a destination computer system that is network connectable along with one or more other computer systems to a network, a method for reliably processing of a message, the method comprising:

an act of receiving a first copy of a message from a message source, the first copy of the message being associated with an established instance ID;

an act of processing the first copy of the message at a message processor instance that was initialized to have the established instance ID;

an act of detecting that the contents of memory utilized by the destination computer system were involuntarily lost;

an act of re-initializing the message processor instance to have an updated instance ID that differs from the established instance ID;

an act of receiving a second copy of the message subsequent to re-initializing the message processor instance, the second copy of the message being associated with the established instance ID; and

an act of rejecting the second copy of the message since the second copy of the message corresponds to an instance ID that is different than the updated instance ID.

28. The method as recited in claim 27, wherein the act of receiving a first copy of a message comprises an act of receiving a first copy of a message that includes the established instance ID.

29. The method as recited in claim 27, wherein the act of receiving a first copy of a message comprises:

an act of receiving the first copy of the message;

an act of sending a REQACKACK to the message source; and

an act of receiving an ACKACK that includes the established instance ID.

30. The method as recited in claim 27, wherein the act of processing the first copy of the message at a message processor comprises an act of determining that the established instance ID associated with the first message is the current instance ID of the message processor instance.

31. The method as recited in claim 27, wherein the act of processing the first copy of the message at a message processor comprises an act of delivering application data contained in the message to the message processor instance.

32. The method as recited in claim 27, wherein the act of detecting that the contents of memory utilized by the destination computer system were involuntarily lost comprises detecting that contents of an interaction cache were lost.

33. The method as recited in claim 27, wherein the act of re-initializing the message processor instance to have an updated instance ID comprises generating an updated instance ID.

34. The method as recited in claim 27, wherein the act of receiving a second copy of the message comprises an act of receiving a second copy of the message that includes the established instance ID.

35. The method as recited in claim 27, wherein the act of receiving a second copy of the message comprises:

an act of receiving the second copy of the message;

an act of sending a REQACKACK to the message source; and

an act of receiving an ACKACK that includes the established instance ID.

36. The method as recited in claim 27, wherein the act of rejecting the second copy of the message comprises an act of determining that the established instance ID and the updated instance ID differ.

37. The method as recited in claim 27, further comprising:

an act of the failing an interaction identified by an interaction ID in the message.

38. The method as recited in claim 27, wherein the destination computer system includes a Web server and the message source is a Web browser.

39. At a source computer system that is network connectable along with one or more other computer systems to a network, the source computer system and at least one of the other computer systems having synchronized clock rates, a method for reliably processing a message, the method comprising:

an act of sending a first copy of a message having an interaction ID, a message ID, and a TTL value to a message destination that has a clock rate synchronized with the clock rate of the source computer system, the message ID identifying the position of the message in an interaction specified by the interaction ID and the TTL value indicating when the message is to expire;

an act of sending a second copy of the message to the message destination subsequent to sending the first copy of the message, the second copy of the message having the interaction ID, the message ID, and an updated TTL value, the updated TTL value calculated from the TTL value and the elapsed time since the first copy of the message was sent;

an act of detecting that the message no longer requires acknowledgment; and

an act of updating an interaction cache to indicate that the message no longer requires acknowledgement.

40. The method as recited in claim 39, further comprising:

an act of setting a message timer duration based on the TTL value

41. The method as recited in claim 39, wherein the act of sending a second copy of the message comprises sending the second copy of the message at a re-transmission interval.

42. The method as recited in claim 39, further comprising:

an act of sending at least one additional copy of the message subsequent to sending the second copy of the message, each additional copy of the message including the interaction ID, the message ID, and a corresponding TTL value, each corresponding TTL value calculated from an immediately previous corresponding TTL value and the elapsed time since an immediately previous copy of the message was sent

43. The method as recited in claim 39, wherein the act of detecting that the message no longer requires acknowledgment comprises an act of receiving an Acknowledgement of the message from the message destination.

44. The method as recited in claim 39, wherein the act of detecting that the message no longer requires acknowledgment comprises an act of detecting that a message timer duration, based on the TTL value, has expired.

45. The method as recited in claim 39, wherein an act of updating an interaction cache to indicate that the message no longer requires acknowledgement comprises storing the message ID and interaction ID in the interaction cache.

46. The method as recited in claim 39, further comprising:

an act of receiving a REQACKACK from the message destination, the REQACKACK requesting the progress of the interaction identified by the interaction ID; and

an act of sending an ACKACK that indicates the interaction has progressed up to the message identified by the message ID such that the message destination is made aware that the message does not require acknowledgement.

47. The method as recited in claim 39, wherein the source computer system includes a Web browser and the message destination is a Web server.

48. The method as recited in claim 39, further comprising:

an act of sending an ACKACK that indicates that the message no longer requires acknowledgement even though an acknowledgment for the message was never received.

49. The method as recited in claim 39, further comprising:

an act of receiving a token from a message destination, the token including an encrypted session key that was encrypted with a private key of a public/private key pair, the session key for securing the interaction between the message destination and the source computer system;

an act of decrypting the token using the public key of the public/private key pair to reveal the session key; and

an act of using the reveal session to secure subsequent communication sent to the message destination.

50. The method as recited in claim 49, further comprising:

an act of subsequently sending the received token to the message destination in response to a REQACKACK so as to enable the message destination to re-establish a secure context with the source computer system.