Internet Engineering Task Force INTERNET-DRAFT Author Transport Working Group Ken Toney Category: Informational Nortel Networks February 1999 Expires: September 1999 PURDET Reliable Transport Extensions on UDP < draft-toney-purdet-00.txt > Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." To view the list Internet-Draft Shadow Directories, see http://www.ietf.org/shadow.html. Abstract Originally this draft started out as "Reliable Extensions To UDP". Instead of calling it "Reliable Extensions To UDP", it was decided to use an anagram, PURDET, to represent what this draft was about. This PURDET specification defines a very lightweight protocol with minimal transport functions necessary to provide reliability and flow control over non-reliable UDP transport. It is intended to be very easy to implement, to have a small footprint on the OS to allow high fan-out, and support simple control of the connection. PURDET supports sequencing, flow control, multiplexing/protocol identification (using an optional field), error retransmission, and link loss detection. PURDET is a work in progress presented for comment. The author hopes this represents positive progress towards a reliability approach appropriate to the needs of real time control and similar applications. Toney [Page 1] INTERNET-DRAFT draft-toney-purdet-00.txt Table of Contents 1.0 Introduction 1.1 Definitions 2.0 Protocol Overview 2.1 Message Types 2.2 Connection Management 2.3 State Variables 2.4 Flow Control 2.5 Error Control 2.6 Suggested implementation of INFO delay timers 2.7 Suggested implementation of optional SREJ delay timers 2.8 Suggested implementation of DISC delay timers 2.9 SEI session endpoint identifier 3.0 Extended Header Format 3.1 Connect Request (CR) 3.2 Unnumbered Acknowledgement (UA) 3.3 Information message (INFO) 3.4 Ready Receive (RR) 3.5 Select/Reject message (SREJ) 3.6 Disconnect (DISC) 4.0 References 5.0 Acknowledgements 6.0 Author's Address Appendix A: Acknowledgment Timeouts A.1 Calculating Adaptive Acknowledgment Timeout A.2 Flow Control: Adjusting for Timeout Appendix B: Examples of sequence numbering B.1 Lock-step tunnel establishment B.2 Multiple packets acknowledged B.3 Lost packet with retransmission Toney [Page 2] INTERNET-DRAFT draft-toney-purdet-00.txt 1.0 Introduction The extensions defined in this specification are mandatory for all PURDET extensions operating over a non-reliable transport (e.g. UDP). PURDET supports the following functions: - Sequence preservation using sequence numbers and a reordering buffer - Flow control using a 32 bit sliding window suitable to high bandwidth transport medium - Multiplexing using the optional SEI mechanism to identify individual streams/destinations - each stream can have its own separate flow control window. - Protocol identification can also be done using the SEI mechanism to distinguish different protocols transported - Error correction using selective retransmission - timer backoff and a limit on retransmission attempts are supported to reduce potential for congestion - Link loss detection based on delivery failure Other functions such as load sharing are left to a higher level process. Services that require reliable delivery and guaranteed ordering in a IP-based datagram-oriented manner with real-time performance may want to use PURDET. PURDET can be extended to have multiple streams, sessions, or payloads for a given connection. An example application would be in an IP-based small-message product that has a large number of payloads (ie. ISUP, SCCP, DSS1) that each needs to send reliably to many other IP-based small-message products. Another example would be real time control of a large number of client devices from a central server. Use of TCP would require creating a socket for each payload and thus a port, 4 timers, and a window would be allocated. The more TCP sockets used, the more resources that are used by the OS to manage these sockets. Also the due to the small-message nature of these applications, a TCP implementation would try to fill up much larger buffers and in turn delay transmission. This could result in potentially unacceptable delays in message delivery. PURDET is a work in progress presented for comment.The author hopes this represents positive progress towards a reliability approach appropriate to the needs of real time control and similar applications. Toney [Page 3] INTERNET-DRAFT draft-toney-purdet-00.txt 1.1 Definitions In this document, several words are used to signify the requirements of the specification. These words are often capitalized. MUST This word, or the adjective "required", means that the definition is an absolute requirement of the specification. MUST NOT This phrase means that the definition is an absolute prohibition of the specification. SHOULD This word, or the adjective "recommended", means that there may exist valid reasons in particular circumstances to ignore this item, but the full implications must be understood and carefully weighed before choosing a different course. MAY This word, or the adjective "optional", means that this item is one of an allowed set of alternatives. An implementation which does not include this option MUST be prepared to interoperate with another implementation which does include the option. 2.0 Protocol Overview This section provides a detailed overview of how reliable transport can be optionally provided by PURDET. If you using PURDET, it provides the following capabilities: Connection Management Error Control Flow Control Sequencing Integrity 2.1 Message Types There are six different types of PURDET messages: Connection Request (CR), Unnumbered Acknowledgement (UA), Information (INFO), Receive Ready (RR), Select for Reject (SREJ), and Disconnect (DISC). 2.2 Connection Management The following types of PURDET messages are used in connection management: Connection Request (CR), Unnumbered Acknowledgement (UA), Disconnect (DISC). Toney [Page 4] INTERNET-DRAFT draft-toney-purdet-00.txt A peer requests a connection opened to another peer using a Connection Request (CR). If a Unnumbered Acknowledgement (UA) does not arrive from the peer in a predetermined time, another CR will be sent for some predetermined (provisionly 3 retries) number of retries. It is required to send a UA for multiple CR requests before any INFO packets have been. This situation occurs when UA are not being received by the peer. No Information (INFO) messages can be sent until the a UA (connection granted) has been received by both peers. This will handle the situation of both peers attempting to connect at the same time. A Disconnect (DISC) can be sent from a peer to signal the closing of the connection. The DISC will be the final (Ns from the remote peer) sequence numbered message that the remote peer uses to determine all INFO messages have been received. The DISC will contain the Vr number and Vr number will not be incremented. The remote peer must reply with a DISC message also. This will handle the situation of both peers attempting to disconnect at the same time. The application is notified of a successful disconnect when all messages have been sent and acknowledged plus a received DISC that is used to determine all messages have been received. If the Ns value in DISC does not match the Vr value, the application is notified of Unsuccessful disconnect. It is required that the DISC message be the last message sent from a peer, retransmissions are not required of these messages. It is recommended for both peers that all messages be sent and acknowledged before a DISC is sent. This implementation will make the application user responsible for knowing when to disconnect. 2.3 State Variables In this document, the sequence number state for each peer is represented for clarity of discussion by distinct pairs of state variables, Vr and Vs. Vr represents the value of the next in-sequence message expected to be received for a given session by a peer. Vs represents the sequence number to be placed in the Ns field of the next INFO message sent to a given peer. Each state is initialized such that the first message sent and the first message expected to be received to/from each peer has an Ns value of 0. This corresponds to initializing Vs and Vr to 0 for each peer. 2.3 Sequence Integrity The following types of PURDET messages are used in sequence integrity: Information (INFO) Toney [Page 5] INTERNET-DRAFT draft-toney-purdet-00.txt Two required fields in the PURDET INFO header that are important to the operation of PURDET the are Nr (Next Received) Ns (Next Send). A single sequence number state is maintained for all PURDET INFO messages to a given peer. The sequence number starts at 0. Each subsequent INFO packet is sent with the sequence number of the range modulo 2^32. Every time a peer sends an new INFO message, the current Vs value is copied into the NS field of the new INFO message and then Vs is incremented by 1 (modulo 2^32). INFO messages include the current value of Vr for the corresponding peer in their Nr field. When an INFO message is received with an Ns value that matches the peer's current Vr value, Vr is incremented by 1 (modulo 2^32). It is important to note that Vr is not modified if a message is received with a value of Ns greater than the current Vr value. Retransmission of lost packets will eventually provide the receiving peer with its next expected message. If the Ns value is less than the Vr or greater than the value of Vr plus the window size, the INFO message is discarded. If the Ns value is inside the window it would be considered out-of-order and handled under Error Control section. A RR is used to communicate a Nr field. It is used to update the peers Vr. It is sent when an INFO message is not available to your peer in a predetermined time (recommended 100 milliseconds). 2.4 Flow Control The following types of PURDET messages are used in flow control: Information (INFO), Receive Ready (RR), Select for Reject (SREJ). When transmitting INFO packets, a PURDET peer must obey the granted window size offered by its peer. A PURDET peer MUST NOT send new INFO packets when its peer's window is closed (the number of packets unacknowledged is equal to the advertised, or assumed, window size). Unacknowledged previously transmitted INFO packets may be retransmitted while the peer's window is closed due INFO timer or SREJ message. 2.5 Error Control The following types of PURDET messages are used in flow control: Select for Reject (SREJ). The sequence number is thus a free running counter represented modulo 2^32 (4,294,967,296). For purposes of detecting duplication, a received sequence less than or equal to the last received value if its value lies in the range of the last value and its 2^32 minus the window size successor. For example, if the Toney [Page 6] INTERNET-DRAFT draft-toney-purdet-00.txt window size is 16 and last received sequence number was 15, then received packets with Ns values in the range ( 32...(2^32),0...15 ) would be considered duplicates and would be silently discarded. An INFO packet with sequence number 16 would be treated as the next in-sequence packet and other INFO packets within the windowed sequences numbers are considered out-of-order. It is required for PURDET Messages received out-of-order to be queued for later ordered delivery. The Messages will be queued until the missing sequence arrives or until a predetermined time the connection is disconnected (DISC). Any failed delivery of a message will cause the connection to disconnect. It is recommended to send a DISC message to the peer for a failed delivery. The transport can be implemented for delivery of INFO messages received out-of-order to reduce latency. A SREJ is used to request a retransmission of an INFO message from the peer. It can be send from each peer when an out-of-order sequence is received. It is recommend to wait a short period of time to handle re-ordered packets before sending a SREJ message. The Ns sent identifies a unique sequence missing. The peer should do a retransmission of the INFO message of that sequence number. It is recommended that up to three SREJ messages be sent. Any failed delivery of a message will cause the connection to disconnect. It is recommended to send a DISC message to the peer for a failed delivery. 2.6 Suggested implementation of INFO delay timers In order for a PURDET implementation to be able to retransmit INFO messages, it MUST queue transmitted messages until the messages are acknowledged. It must also maintain a retransmission timer that determines when to assume that either a sent message did not arrive at the peer or the acknowledgment sent by the peer was lost. See Appendix A for a recommended retransmit timer implementation. There are two example methods for implementing the retransmission procedure. One method is for the sender to resend the entire window of unacknowledged messages when the retransmit timeout expires. This is the simplest method, but is inefficient when a receiver is not rotating the window due to congestion. The alternative method is to only resend the first message in the window (the first unacknowledged message) until an acknowledgment is received. This acknowledgment will indicate to the receiver the next, if any, message in the current window that needs to be retransmitted. A particular implementation may use either or both methods if desired. When a PURDET node has retransmitted an INFO message to a given peer the maximum number of times (the recommended value is 3) the connection will be disconnected. An optional disconnect message can be sent and is recommended. Toney [Page 7] INTERNET-DRAFT draft-toney-purdet-00.txt 2.7 Suggested implementation of optional SREJ delay timers The SREJ message indicates a missing sequence number. The SREJ timer should be long enough to check for out-of-order deliver. When a PURDET node has retransmitted a SREJ message to a given peer the maximum number of times (the recommended value is 3) the connection will be disconnected. An optional disconnect message can be sent and is recommended. 2.8 Suggested implementation of DISC delay timers The DISC message signal is the last sequence number. The state of the connection changes to closing, but uses the same delay timer as a SREJ message. Failure to get an acknowledgement of a DISC message will mean the connection has become unreliable. 2.9 SEI session endpoint identifier An optional field for the PURDET header is the session endpoint identifier (SEI). The SEI is used to deliver all messages to a unique area in an application (I.e ISUP messages). The SEI value, once assigned, never changes for the life of the connection. The SEI is based on the source IP address, source port, source session identifier (SI), destination IP address, destination port, and destination SI. The session identifier will be a unique identifier for each peer and will be a modulo 2^16 number. The SEI itself will be a 2^32 number having the destination SI and source SI concatenated together. In other words, the first 16 bits is from the destination SI and second 16 bits source SI. The IP and UDP header can be used to infer the remaining information needed to uniquely identify an endpoint for each given peer. 3.0 Header Formats This section defines the fields in the different PURDET headers that allows PURDET to provide reliability. The "PURDET Version" is a 6 bit field that is used to identify PURDET and the version of PURDET. Values to be Determined. The C flag is for CRC checking. The S flag is for use of the SEI. If these are 0 (for false) then all fields using SEI and CRC will be omitted. The Session Endpointer Identifier(SEI) and CRC are optional fields that are set to be used (or not) by the connect request message. Toney [Page 8] INTERNET-DRAFT draft-toney-purdet-00.txt 3.1 Connect Request (CR) 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Version |C|S| 10 | Granted Window Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Session Endpointer Identifier SEI | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Flag "S" -- SEI FLAG This is the only time this flag is valid. Once connection established the use policy on SEI is set for the life of the connection. An UA(denied connection) may be returned if the peer has SEI functionality implemented or not implemented. Flag "C" -- CRC Flag This flag signals if CRC's are generated. Window Size This is used by a peer to inform its peer of its granted window size. The size indicated is the number of packets that it is willing to accept before the window is full. 3.2 Unnumbered Acknowledgement (UA) A summary of the PURDET UA format is shown below. The fields are transmitted from left to right. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Version |C|S| ACK ID | Granted Window Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Session Endpointer Identifier SEI | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ACK ID Flags The ACK ID Flag field is eight bits, and is used in order to identify the following: Attribute code 11: Means connection accepted and ready to accept INFO messages. The window size must be used for sending to this connection. Attribute code 12: Means connection denied. Means SEI peer not founds Attribute code 14: Do not have SEI implemented. Toney [Page 9] INTERNET-DRAFT draft-toney-purdet-00.txt Window Size A sending peer MUST stop sending new PURDET messages when this many messages are outstanding (sent but not yet acknowledged). 3.3 Information message (INFO) A summary of the PURDET INFO format is shown below. The fields are transmitted from left to right. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Version |C|S| 20 | Bytes of Data | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Next Send (Ns) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Next Receive (Nr) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | DATA...(of some byte length) | CRC | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Session Endpointer Identifier SEI | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Flag "C" -- CRC Flag This flag signals if CRC's are generated. Bytes of Data This value represent number of bytes. The CRC and/or SEI will start at the next byte. Next Send The Next Send (Ns) is copied from the send sequence number state variable, Vs, at the time the message is transmitted. Vs is incremented after copying. Next Received Nr is copied from the receive sequence number state variable, Vr. Toney [Page 10] INTERNET-DRAFT draft-toney-purdet-00.txt 3.4 Ready Receive (RR) A summary of the PURDET RR format is shown below. The fields are transmitted from left to right. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Version |C|S| 31 | spare | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Received (Nr) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Session Endpointer Identifier SEI | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Message type RR and is sent if no INFO message can be sent in a predetermined time (recommended 100 milliseconds). 3.5 Select/Reject message (SREJ) Message type SREJ and can be sent when out-of-order sequence received. The value Ns represents missing sequence. A summary of the PURDET SREJ format is shown below. The fields are transmitted from left to right. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Version |C|S| 32 | spare | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Next Send (Ns) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Session Endpointer Identifier SEI | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Next Send The value Ns represents the missing sequence number that needs to be retransmitted. 3.6 Disconnect (DISC) A summary of the PURDET DISC format is shown below. The fields are transmitted from left to right. This message is used to end and terminate the connection. Toney [Page 11] INTERNET-DRAFT draft-toney-purdet-00.txt 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Version |C|S| 255 | Next Send High 16 bits | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Next Send Low 16 bits | SEI High 16 bits | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | SEI Low 16 bits | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4.0 References [1] Reynolds, Postel, "Assigned Numbers", RFC 1700, October 1994. [2] Postel, "User Datagram Protocol", RFC 768, August 1980. [3] Calhoun, Zorn, Pan, "DIAMETER Framework", Internet- Draft, draft-calhoun-DIAMETER-framework-00.txt, May 1998 [4] Calhoun, Rubens, "DIAMETER Base Protocol", Internet-Draft, draft-calhoun-DIAMETER-05.txt, May 1998. [5] K. Hamzeh, T. Kolar, M. Littlewood, G. Singh Pall, J. Taarud, A. J. Valencia, W. Verthein, W.M. Townsley, B. Palter, A. Rubens "Layer Two Tunneling Protocol (L2TP)", Internet-Draft, May 1998 [6] P. R. Calhoun, A. C. Rubens "DIAMETER Reliable Transport Extensions", Internet-Draft, November 1998 5.0 Acknowledgements The Authors would like to acknowledge the following people for their contribution in the development of the PURDET protocol: Asa Atallah, Joe Harvell, Greg Graham, Venky Raju, Michael Thomas Greg Sidebottom, Peter Blatherwick, Lyndon Ong 6.0 Author's Address Questions about this memo can be directed to: Kenneth Toney Nortel Networks, INC 2530 Lakeside Blvd Richardson TX 75083 USA Phone: (972)684-7146 email: ktoney@nortel.com Toney [Page 12] INTERNET-DRAFT draft-toney-purdet-00.txt Appendix A: Acknowledgment Timeouts PURDET uses sliding windows and timeouts to provide flow-control across the underlying medium and to perform efficient data buffering to keep two PURDET peers' receive window full without causing receive buffer overflow. PURDET requires that a timeout be used to recover from dropped packets. When the timeout for a peer expires, the previously transmitted message with Ns value equal to the highest in-sequence value of Nr received from the peer is retransmitted. The receiving peer does not advance its value for the receive sequence number state, Vr, until it receives a message with Ns equal to its current value of Vr. This rule assures that all subsequent acknowledgements to this peer will contain an Nr value equal to the Ns value of the first missing message until a message with the missing Ns value is received. The exact implementation of the acknowledgment timeout is vendor- specific. It is suggested that an adaptive timeout be implemented with backoff for flow control. The timeout mechanism proposed here has the following properties: Independent timeouts for each peer. A device will have to maintain and calculate timeouts for every active peer. An administrator-adjustable maximum timeout, MaxTimeOut, unique to each device. An adaptive timeout mechanism that compensates for changing throughput. To reduce packet processing overhead, vendors may choose not to recompute the adaptive timeout for every received acknowledgment. The result of this overhead reduction is that the timeout will not respond as quickly to rapid network changes. Timer backoff on timeout to reduce congestion. The backed-off timer value is limited by the configurable maximum timeout value. Timer backoff is done every time an acknowledgment timeout occurs. In general, this mechanism has the desirable behavior of quickly backing off upon a timeout and of slowly decreasing the timeout value as packets are delivered without errors. Toney [Page 13] INTERNET-DRAFT draft-toney-purdet-00.txt A.1 Calculating Adaptive Acknowledgment Timeout We must decide how much time to allow for acknowledgments to return. If the timeout is set too high, we may wait an unnecessarily long time for dropped packets. If the timeout is too short, we may time out just before the acknowledgment arrives. The acknowledgment timeout should also be reasonable and responsive to changing network conditions. The suggested adaptive algorithm detailed below is based on the TCP 1989 implementation and is explained in Richard Steven's book TCP/IP Illustrated, Volume 1 (page 300). 'n' means this iteration of the calculation, and 'n-1' refers to values from the last calculation. DIFF[n] = SAMPLE[n] - RTT[n-1] DEV[n] = DEV[n-1] + (beta * (|DIFF[n]| - DEV[n-1])) RTT[n] = RTT[n-1] + (alpha * DIFF[n]) ATO[n] = MIN (RTT[n] + (chi * DEV[n]), MaxTimeOut) DIFF represents the error between the last estimated round-trip time and the measured time. DIFF is calculated on each iteration. DEV is the estimated mean deviation. This approximates the standard deviation. DEV is calculated on each iteration and stored for use in the next iteration. Initially, it is set to 0. RTT is the estimated round-trip time of an average packet. RTT is calculated on each iteration and stored for use in the next iteration. Initially, it is set to PPD. ATO is the adaptive timeout for the next transmitted packet. ATO is calculated on each iteration. Its value is limited, by the MIN function, to be a maximum of the configured MaxTimeOut value. Alpha is the gain for the round trip estimate error and is typically 1/8 (0.125). Beta is the gain for the deviation and is typically 1/4 (0.250). Chi is the gain for the timeout and is typically set to 4. Toney [Page 14] INTERNET-DRAFT draft-toney-purdet-00.txt To eliminate division operations for fractional gain elements, the entire set of equations can be scaled. With the suggested gain constants, they should be scaled by 8 to eliminate all division. To simplify calculations, all gain values are kept to powers of two so that shift operations can be used in place of multiplication or division. The above calculations are carried out each time an acknowledgment is received for a packet that was not retransmitted (no timeout occurred). A.2 Flow Control: Adjusting for Timeout This section describes how the calculation of ATO is modified in the case where a timeout does occur. When a timeout occurs, the timeout value should be adjusted rapidly upward. To compensate for shifting internetwork time delays, a strategy must be employed to increase the timeout when it expires. A simple formula called Karn's Algorithm is used in TCP implementations and may be used in implementing the backoff timers for the PURDET peers. Notice that in addition to increasing the timeout, we also shrink the size of the window as described in the next section. Karn's timer backoff algorithm, as used in TCP, is: NewTIMEOUT = delta * TIMEOUT Adapted to our timeout calculations, for an interval in which a timeout occurs, the new timeout interval ATO is calculated as: RTT[n] = delta * RTT[n-1] DEV[n] = DEV[n-1] ATO[n] = MIN (RTT[n] + (chi * DEV[n]), MaxTimeOut) In this modified calculation of ATO, only the two values that contribute to ATO and that are stored for the next iteration are calculated. RTT is scaled by delta, and DEV is unmodified. DIFF is not carried forward and is not used in this scenario. A value of 2 for Delta, the timeout gain factor for RTT, is suggested. Appendix B: Examples of sequence numbering This appendix uses several common scenarios to illustrate how sequence number state progresses and is interpreted. B.1 Lock-step session establishment In this example, a PURDET host establishes communication with a peer, with the exchange involving each side alternating in the sending of messages. This example is contrived, in that the final acknowledgement typically would be included in the INFO message. Toney [Page 15] INTERNET-DRAFT draft-toney-purdet-00.txt PURDET Host A PURDET Host B -> INFO Nr: 0, Ns: 0 (RR) <- Nr: 1 -> INFO Nr: 0, Ns: 1 (delay) (RR) <- Nr: 2 B.2 Multiple packets acknowledged This example shows a flow of packets from PURDET Host B to Host A, with Host A having no traffic of its own. Host A is waiting 1/4 of its timeout interval, and then acknowledging all packets seen since the last interval. PURDET Host A PURDET Host B (previous packet flow precedes this) -> (RR) Nr: 7000 (INFO) <- Nr: 1000, Ns: 7000 (INFO) <- Nr: 1000, Ns: 7001 (INFO) <- Nr: 1000, Ns: 7002 (Host A's timer indicates it should acknowledge pending traffic) -> (RR) Nr: 7003 Toney [Page 16]