End To End --- -- --- Communications over an unreliable link can be made reliable by a simple end-to-end protocol. Each end sends messages which it numbers, 1, 2, 3, 4, etc. What is actually sent for each message is the packet: checksum acknowledgment number message The acknowledgment ACK is such that all messages with numbers less than or equal to ACK have been correctly received. The number is the number of the message being sent (and is not zero). The checksum is the checksum of the acknowledgment, the number, and the message, and is used to test whether the packet has been correctly re- ceived. In addition there are also `null packets' that contain no message, and have the form: checksum acknowledgment 0 The receiver maintains three items of data: ACKOUT, the number of the last message received correctly, ACKIN, the largest acknowledgment received, and Q, a queue of messages that are to be or have been sent but have not yet been acknowledged as having been correctly received. ACKOUT and ACKIN are initialized to 0, and Q is initial- ly empty. When the receiver receives a packet, the receiver uses the checksum to see if the packet is correct. Whenever the receiver receives a correct packet contain- ing an acknowledgment ACK, if ACK > ACKIN, the receiver discards ACK - ACKIN messages from the front of Q, as these have been received correctly, and then sets ACKIN = ACK. Whenever the receive receives a correct packet whose number equals ACKOUT + 1, the receive adds 1 to ACKOUT and processes the message. Processing a message adds output messages to the end of Q. Whenever the receiver receives a packet, correct or not, and has done the above processing, the receiver sends one or more packets each containing the value of ACKOUT after the above processing in the packet acknowledgment field. If Q is empty, one null packet is sent. If Q is not empty, one packet containing each message in Q is sent, in the order the messages appear in Q, with the first packet having message number ACKIN+1, the next message number ACKIN+2, etc. However, Q itself is NOT changed by this process: no messages are removed from Q just because they have been sent. As a special exception, if a correct null packet is re- ceived with acknowledgment matching ACKIN and Q empty, then no reply packet is sent. Otherwise the two ends would be sending null packets back and forth indefin- itely. This protocol can handle two kinds of link errors. The first is a message that is corrupted, so it has a bad checksum, or is just completely lost, so it never ar- rives. This may mean that a subsequent message will ar- rive before it can be used, and will have to be discard- ed. The second kind of link error is when a copy of an old message that was successfully received and processed arrives long after the original copy arrived. You have been asked to write the code of one end of the link. For your end, message processing is as follows. Each message is string of text consisting of just space characters and letters. In this a maximal string of letters is called a `word'. You are to find the words of each message in order, and output for each word one message that contains just the word, with NO space char- acters. NOTES: You need NOT check for protocol errors due to bugs in the code at other end of the link. An example of such an error would be acknowledging a message that has not yet been sent. A more subtle example is sending two different messages with the same message number. In this last case the above algorithm will process only the first message whose message number equals ACKOUT + 1 at the time its packet is received. Input ----- Each packet is represented by a line with the format: checksum An unsigned integer. 1 space character acknowledgment An unsigned integer. 1 space character number An unsigned integer. 1 space character message 0 or more space char- acters and letters. line feed This is NOT part of the message. A correct checksum is just the sum of the acknowledg- ment, the number, and the ASCII codes of all the charac- ters in the message. No packet contains more than 80 characters. No checksum, acknowledgment, or number has a sign or high order zeros. The input ends with an end of file. Output ------ For each input packet, echo the packet on a line with the preface `* ', that is, a * character followed by a single space character. Then do the processing above and output zero or more packets as required by the al- gorithm. The output packets have the same format as the input packets (and do NOT have any `* ' prefix). Sample Input ------ ----- 1101 0 1 hello there 749 2 2 goodbye 1814 3 3 this is a duplicate 1814 3 3 this is a duplicate 7 7 0 2141 7 4 this has a bad checksum 1279 7 4 this does not 8 8 0 9 9 0 10 10 0 10 10 0 Sample Output ------ ------ * 1101 0 1 hello there 534 1 1 hello 539 1 2 there * 749 2 2 goodbye 750 2 3 goodbye * 1814 3 3 this is a duplicate 447 3 4 this 228 3 5 is 106 3 6 a 965 3 7 duplicate * 1814 3 3 this is a duplicate 447 3 4 this 228 3 5 is 106 3 6 a 965 3 7 duplicate * 7 7 0 3 3 0 * 2141 7 4 this has a bad checksum 3 3 0 * 1279 7 4 this does not 452 4 8 this 440 4 9 does 351 4 10 not * 8 8 0 440 4 9 does 351 4 10 not * 9 9 0 351 4 10 not * 10 10 0 4 4 0 * 10 10 0 Further Information ------- ----------- Real algorithms also use a clock and send packets when they have not received any packet in a sufficiently long time and Q is non-empty. Sometimes they send packets periodically even when Q is empty in order to detect when the link has failed. Real algorithms only send the low order bits of the acknowledgment and message number. Real algorithms use more sophisticated checksums. If you think carefully about our algorithm, you will see that there is an efficiency problem with it if both ends of the link use our algorithm (with different message processing, of course), because we can send a batch of more than one packet in response to a single packet. This can be fixed by batching more than one message in one packet, or by other means. There is an amusing theorem of computer science that says that if you have two unreliable links connected, as in X <----------> Y <----------> Z you CANNOT make communications from X to Z reliable by making each of the two links reliable. The problem is that if Y fails and then restarts, and X has sent a message to Y just before Y fails, X cannot tell whether the message was forwarded to Z or not, and therefore the message may be lost if X does not resend it or duplicated if X does resend it. The solution is for X and Z to run the end-to-end algor- ithm themselves, without Y participating in the algor- ithm (Y merely forwards packets). This does not mean that making the two links reliable will not improve efficiency or maintainability; just that it will not guarantee reliability of XZ communications. File: endtoend.txt Author: Bob Walton Date: Mon Oct 16 10:46:36 EDT 2006 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file. RCS Info (may not be true date or author): $Author: walton $ $Date: 2006/10/16 14:45:08 $ $RCSfile: endtoend.txt,v $ $Revision: 1.8 $