1. The Field of the Invention
The present invention relates to electronic messaging and, more particularly, to reliable messaging using clocks with synchronized rates.
2. Background and Relevant Art
Computer systems and related technology affect many aspects of society. Indeed, the computer system's ability to process information has transformed the way we live and work. Computer systems now commonly perform a host of tasks (e.g., word processing, scheduling, and database management) that prior to the advent of the computer system were performed manually. More recently, computer systems have been coupled to one another and to other electronic devices to form both wired and wireless computer networks over which the computer systems and other electronic devices can transfer electronic data. As a result, many tasks performed at a computer system (e.g., voice communication, accessing electronic mail, controlling home electronics, Web browsing, and printing documents) include the exchange of electronic messages between a number of computer systems and/or other electronic devices via wired and/or wireless computer networks.
Networks have in fact become so prolific that a simple network-enabled computing system may communicate with any one of millions of other computing systems spread throughout the globe over a conglomeration of networks often referred to as the “Internet”. Such computing systems may include desktop, laptop, or tablet personal computers; Personal Digital Assistants (PDAs); telephones; or any other computer or device capable of communicating over a digital network.
In order to communicate over a network, one computing system (referred to herein as a “sending computing system”) constructs or otherwise accesses an electronic message and transmits the electronic message over a network to another computing system (referred to herein as a “receiving computing system”). The electronic message may be read by a human user as when the electronic message is an e-mail or instant message, or may be read, instead, by an application running on the receiving computing system. The electronic message may be constructed by an application running on the sending computing system with the possible assistance of a human user.
Although such electronic messaging advantageously allows for computing systems to exchange information, networks sometimes fail to deliver an electronic message. Depending on the importance of the electronic message, this could be quite harmful, and even catastrophic in some cases. Accordingly, reliable electronic messaging technologies have been developed.
Generally, the purpose of reliable messaging technologies is to deliver an electronic message from a source to a destination over a communication network that can loose, duplicate, reorder, and delay messages. Some electronic messages can be delivered and processed multiple times without harm. However, this is not true of all messages. In general, the safest approach is to ensure that messages are delivered once or not at all.
Some reliable messaging technologies implement acknowledgement messages. For example, Transmission Control Protocol (among other transport protocols) implements acknowledgement-based reliable messaging. Specifically, when a receiving computing system receives an electronic message from a sending computing system, the receiving computing system transmits an acknowledgement message to the sending computing system. Upon receipt of the acknowledgement message, the sending computing system may reliably take appropriate action given knowledge that the receiving computing system did in fact receive the electronic message. Otherwise, if the sending computing system does not receive the acknowledgement message, the sending computing system may take appropriate action such as retransmitting the electronic message. However sending an acknowledgement message for every received electronic message can result in a large number of acknowledgment messages that can potentially and unnecessarily consume network bandwidth.
In order to reduce the number of acknowledgement messages that need to be transmitted, cumulative acknowledgement has been developed. In cumulative acknowledgement, the sending computing system assigns a sequence number to each electronic message in a session. The sequence number for a given electronic message is typically incremented by one as compared to the previous electronic message in the session. The cumulative acknowledgement returned to the sending computing system includes the last sequence number of a contiguous series of sequence numbers representing successfully received messages. For example, suppose the receiving computing system received electronic messages having sequence numbers 1 through 50, and 55 through 99 but did not receive messages have sequence numbers 51-54. The receiving computing system may return a cumulative acknowledgment identifying only the received sequences
However, when a sending computing system fails to receive an acknowledgment message (either individual or cumulative), there may be no way for the sending computing system to determine if the electronic message failed to be delivered or if the corresponding acknowledgment message failed to be delivered. That is, the sending computing system is “in doubt” with respect to whether the receiving computing system received an electronic message. In some environments, it may acceptable to deliver and process electronic messages multiple times. Thus, in these environments (e.g., involving static Web based content), a sending computing system may retransmit an electronic message when a corresponding acknowledgment message is not received. However, in other environments, it may not be acceptable to deliver and/or process electronic messages multiple times. Thus, in these other environments (e.g., involving banking transactions), a sending computer system will not retransmit an electronic message when a corresponding acknowledgment message is not received.
To relieve a sending computing system from having to a make a retransmission decision that may be incorrect, duplicate detection mechanisms have been design. Duplicate detection mechanisms decrease the likelihood of a receiving computing system processing the same message (or sequence of messages) more than once. To implement duplicate detection mechanisms, many receiving computer systems store state information associated with sending computer systems. For example, a receiving computer system can store an indication (e.g., in a database or list) of all the previous messages (or sequence of messages) that have previously been processed (e.g., identified by the IP address of the sending computing system and the sequence number). Thus, if a received message is present in the list (i.e., the message was previously received), the received message is discarded and re-processing of the message is avoided. Receiving computing systems typically store state information for long periods of time, such as, for example, the length of a session, (potentially forever) to significantly increase the chance of duplicate detection.
Due to the number of computing systems and number of messages exchanged on networks (e.g., on the Internet), the resources needed to implement duplicate detection can be quite large. For example, at any given time on the Internet, millions of computer systems are exchanging electronic messages. Even at a single receiving computer system (e.g., a retail server), it is not uncommon to interact with thousands, or even tens of thousands, of different sending computing systems in a given day. Thus, to implement duplicate detection, these receiving computing systems may store, for long periods of time, indications of every message that is received from every sending computer system. Since each sending computing system can potentially send thousands of messages as part of a transaction, receiving computing systems may need to maintain state for large quantities (e.g., millions or tens of millions) of messages.
Some other reliable messaging technologies utilize clocks that are synchronized to absolute times. However, synchronizing clocks to absolute times requires a synchronization protocol and high connectivity. On some networks, such as, for example, the Internet, high connectivity is virtually impossible since computer systems frequently connect to and disconnect from the network. Further, reliable messaging technologies utilizing clocks with absolute synchronized times can be more expensive to implement. Accordingly, reliable messaging technologies that maintain state are more frequently used and are often required when conformance with the more stringent operational parameters of absolute clock synchronization is not possible. Thus, many networked computer systems are required to allocate, potentially significant, resources for maintaining state related to communication with other computer systems. Therefore systems, methods, and computer program products that facilitate reliable messaging in a more resource efficient manner would be advantageous.