Subject: [tcpm] RTTM + timestamps

From: "Scheffenegger, Richard" <[email-masked]>
Date: Mon, 10 Jan 2011 18:24:47 -0000

Hi group,

in order not to spam the whole group, I would like to learn who is
interested in the heuristics and signaling around round-trip
measurement, timestamps and possible synergies between TS and other
option, as well as some empirical measurements around currently deployed
tcp stacks that diverge from the IETF specs in these aspects.

In the light of some recent developments (ie. LEDBAT, path-chirp/chirp
CC), and more efficient (end-of-flow / non-congestion) loss recovery,
improvements in that space may be of interest to a larger group of
implementers too...

With your feedback, I would like to learn the extent of possible
interest, before going further with my work in that area!

Best regards,

	Richard Scheffenegger

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Mon, 17 Jan 2011 13:48:22 -0000

Hi group,

After having received some feedback off-list so far, I would like to summarize what I learned so far. Also, I invite everyone to discuss these points. There are benefits for the research community both empirical as well as theoretical, as well as mobile and high-speed network operators and implementers.

o) one-way delay based (and delay variation based) congestion controls would benefit from knowing the clock resolution on both sides. Some research in that area is done by Mirja Kuehlewind and Bob Briscoe (http://bobbriscoe.net/pubs.html#chirp_impl), as well as David Hayes (http://caia.swin.edu.au/reports/100219A/CAIA-TR-100219A.pdf)

o) RTT variance during loss episodes is not deeply researched. Current heuristics (RFC1122, RFC1323, Karn's algorithm, RFC2988) explicitly exclude (and prevent) the use of RTT samples when loss occurs. However, solving the retransmission ambiguity problem - and the related reliable ACK delivery problem - may allow the refinement of these algorithms further, as well as enabling new research to distinguish between corruption loss (without RTT / one-way delay impact) and congestion loss (with RTT / one-way delay impact). This appears to be a rather neglected field however, especially when it comes to large scale, public internet investigations. Due to the very nature of this, passive investigations without signals contained within the headers are only of limited use in empirical research here.

o) A side-effect of Van Jacobson's algorithm is that RTO spikes when the path RTT suddenly drops. With the decrease of the path RTT, the variance grows. As the variance has a large effect on the calculated RTO, this leads to potentially very lengthy timeouts even though the RTT is much shorter. This particular problem has been addressed in some stacks, and the lessons learned from the deployment there could be used to update the RTO calculation specs. 

o) Enabling of spurious RTO detection (Eifel, D-SACK, F-RTO) in the last years also make it possible to dynamically identify instances when the RTT estimation or RTO calculation where mislead, allowing to use a more conservative algorithm for certain paths / times.

o) Retransmission ambiguity detection during loss recovery would allow an additional level of loss recovery control without reverting to timer-based methods. As with the deployment of SACK, separating "what" to send from "when" to send it could be driven one step further. In particular, less conservative loss recovery schemes which do not trade principles of packet conservation against timeliness, require a reliable way of prompt and best possible feedback from the receiver about any delivered segment and their ordering. SACK alone goes quite a long way, but using Timestamp information in addition could remove any ambiguity. However, the current specs in RFC1323 make that use impossible, thus a modified signaling (receiver behavior) is a necessity.

The first central aspect of the above mentioned points is to resolve the retransmission ambiguity, and the second to give the end host a better understanding of their respective partners behavior.

I strongly believe that much about the retransmission ambiguity can be solved by exploiting synergistic signaling between the TCP SACK option and Timestamp option. In particular, the receiver-side state required by RFC1323 to choose which Timestamp to reflect when a non-contiguous segment is received could be alleviated, when the TCP session is also using SACK. (The presence of a SACK field indicates some out of sequence delivery. The current stipulations were made, afaik, to ensure that no unduly small RTT sample is entered into the RTO calculation, when ACK loss occurs. But again, SACK disambiguates between a in-sequence ACK, and a duplicate ACK).

For the second aspect, the single most important aspect to convey would be the tcp clock resolution. For this, no signaling exists yet. However, there appears to be a downward-compatible method to extend the Timestamp SYN option, to include this signal.

According to RFC1323, TSecr is unused in the SYN segment, and most stacks appear to ignore that value. An enhanced signaling could set this initial TSecr field. To convey some feedback from the receiver to the sender in the SYN|ACK, while maintaining compatibility with stacks that do not evaluate the contents of this SYN TSecr, a simple XOR between the SYN|TSopt field and the clients respective settings could be employed.

The sender would compare the TSecr value in the SYN|ACK with it's initial sent TSval, and if they are identical, conclude to deal with an unenhanced client (no SACK+TS synergy, no one-way delay/variance CC). If the TSecr in the SYN|ACK would be different, the negotiated heuristics can be enabled for that TCP session - decoded by an XOR from the original TSval. 

SYN:
+-------+-------+---------------------+---------------------+
|Kind=8 |  10   |   TS Value (TSval)  |TS Echo Reply (TSecr)|
+-------+-------+---------------------+---------------------+
    1       1              4                     4
With TSecr containing, ie. A 16-bit Flag field plus a 16-bit IEEE float indicating the TCP clock resolution (duration or frequency), or a 8-bit Flag field plus two 12-bit floats for negotiation of an acceptable clock range. Also, perhaps a CIDR-like prefix bitstring may be of interest for future extensions, ie:

1 1 x x x - future
1 0 1 x x - use 2x12 bit floats
1 0 0 1 x - use 1x16 bit float

A few potentially meaningful flag bits discussed so far could be

TS-extension flag (always set; this limits the senders initial TS selection...)
  Reserved
    TS-negotiate range (w/ 2x 12bit floats)
    TS-fixed rate (w/ 16bit float)
      Modified exponent offset (-21 instead of -15, for very high speed networks)
        SACK+TS synergy (always reflect TS of last received segment)
          High-Precision (use HW late in data path for TS insertion, exclude much jitter)

Note that binary16 allows a dynamic range (with some lost precision) from 2^15 down to 2^-24, while a 12-bit representation, omitting sign and most significant exponent bit, plus least two significant fraction bits, would still allow a range between 2^0 to 2^-22. 

Binary16:
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|Si|   Exponent   |          Fraction           |
|gn|offset shifted|                             |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

12-bit subsample:
      +--+--+--+--+--+--+--+--+--+--+--+--+
      |  exponent |        fraction       |
      +--+--+--+--+--+--+--+--+--+--+--+--+

However even this dynamic range may not be enough to allow a tcp clock to run at the sending rate of minimal IP frames at very high (100 Gbit/s, 1Tbit/s) speeds. Using a different exponent offset shift, and omitting one additional fraction bit instead of one exponent bit in the 12 bit value should be discussed.
   +--+--+--+--+--+--+--+--+--+--+--+--+
   |   exponent   |        fraction    |
   +--+--+--+--+--+--+--+--+--+--+--+--+

From: Scheffenegger, Richard 
Sent: Montag, 10. Jänner 2011 19:25
To: [email-masked]; [email-masked]
Subject: [tcpm] RTTM + timestamps

Hi group,
in order not to spam the whole group, I would like to learn who is interested in the heuristics and signaling around round-trip measurement, timestamps and possible synergies between TS and other option, as well as some empirical measurements around currently deployed tcp stacks that diverge from the IETF specs in these aspects.
In the light of some recent developments (ie. LEDBAT, path-chirp/chirp CC), and more efficient (end-of-flow / non-congestion) loss recovery, improvements in that space may be of interest to a larger group of implementers too...
With your feedback, I would like to learn the extent of possible interest, before going further with my work in that area!
Best regards,
Richard Scheffenegger

---

From: Alexander Zimmermann <[email-masked]>
Date: Mon, 17 Jan 2011 15:35:15 +0100

Hi Richard,

some rash thoughts...

Am 17.01.2011 um 14:48 schrieb Scheffenegger, Richard:

> o) RTT variance during loss episodes is not deeply researched. Current heuristics (RFC1122, RFC1323, Karn's algorithm, RFC2988) explicitly exclude (and prevent) the use of RTT samples when loss occurs.

Eh... With RFC1323, you take RTT samples when loss occurs.

>  However, solving the retransmission ambiguity problem -

The problem is solved, isn't it? Eifel?

> and the related reliable ACK delivery problem - may allow the refinement of these algorithms further, as well as enabling new research to distinguish between corruption loss (without RTT / one-way delay impact) and congestion loss (with RTT / one-way delay impact).

This is not new. Ask Michael Welzl ;-)

And a citation form Sally Floyd to that topic:

"Inferring congestion vs. corruption at the transport level. There are also papers that investigate
algorithms for the transport end-nodes to infer that certain drops are from corruption rather than
congestion, without explicit feedback from routers. My own view would be that the burden is on such
approaches to show that they are not ignoring legitimate congestion indications from the network."

eg: S.Biaz and N. Vaidya. Discriminating Congestion Losses from Wireless Losses Using Interarrival
Times at the Receiver. IEEE Symposium on Application-Specific Systems and Software Engineering and
Technology, Mar 1999.

> This appears to be a rather neglected field however, especially when it comes to large scale, public internet investigations. Due to the very nature of this, passive investigations without signals contained within the headers are only of limited use in empirical research here.
> 
> o) Retransmission ambiguity detection during loss recovery

(what we already have)

> would allow an additional level of loss recovery control without reverting to timer-based methods.

I don't get this point.

> As with the deployment of SACK, separating "what" to send from "when" to send it could be driven one step further. In particular, less conservative loss recovery schemes which do not trade principles of packet conservation against timeliness, require a reliable way of prompt and best possible feedback from the receiver about any delivered segment and their ordering. SACK alone goes quite a long way, but using Timestamp information in addition could remove any ambiguity.

Which ambiguity do you mean here?

> However, the current specs in RFC1323 make that use impossible, thus a modified signaling (receiver behavior) is a necessity.
> 
> 
> 
> 
> 
> The first central aspect of the above mentioned points is to resolve the retransmission ambiguity

Again, Eifel?

> , and the second to give the end host a better understanding of their respective partners behavior.
> 

//
// Dipl.-Inform. Alexander Zimmermann
// Department of Computer Science, Informatik 4
// RWTH Aachen University
// Ahornstr. 55, 52056 Aachen, Germany
// phone: (49-241) 80-21422, fax: (49-241) 80-22222
// email: [email-masked]
// web: http://www.umic-mesh.net
//

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Mon, 17 Jan 2011 15:48:34 -0000

HI Alex,

> > o) RTT variance during loss episodes is not deeply researched.
> > Current heuristics (RFC1122, RFC1323, Karn's algorithm, RFC2988)
> > explicitly exclude (and prevent) the use of RTT samples when loss
> > occurs.
> 

True, but these samples are a worst-case upper bound, since the last
in-sequence delivered segment - if you are running "stateless" on the
sender. With a stateful sender, that keeps sending timestamps
independent of the TS option, and matches the (S)ACKed packets to this
(potentially very lengthy) list, you can - to some extent - circumvent
this issue.

However, it does not help you with re-retransmissions still.

Probably my wording was poor, what I intended to say was to get the best
possible RTT measurement with each delivered (and (S)ACKed) segment
possible, without incurring undue overhead (state) in the sender.

The deliberate withholding of TS info according to RFC1323 - in order to
address the problem of unreliably delivered ACKs, and - at the time -
non-availability of SACK, was what triggered this point.

> The problem is solved, isn't it? Eifel?

Only for cumulative/partial ACKs, and only then in theory, because IPR
restrictions prevent Eifel from being deployed in any commercial stack.
(There is only a single OS compatible with the IPR requirements for all
the Eifel algorithms).

For segments that are delivered out-of-sequence, it still exists.

> 
> > and the related reliable ACK delivery problem - may allow the
> refinement of these algorithms further, as well as enabling new
> research to distinguish between corruption loss (without RTT / one-way
> delay impact) and congestion loss (with RTT / one-way delay impact).
> 
> "Inferring congestion vs. corruption at the transport level. There are
> also papers that investigate algorithms for the transport end-nodes to
> infer that certain drops are from corruption rather than congestion,
> without explicit feedback from routers. My own view would be that the
> burden is on such approaches to show that they are not ignoring
> legitimate congestion indications from the network."
> 
> eg: S.Biaz and N. Vaidya. Discriminating Congestion Losses from
> Wireless Losses Using Interarrival Times at the Receiver. IEEE
> Symposium on Application-Specific Systems and Software Engineering and
> Technology, Mar 1999.

Thanks for the reference! Still you need some way of getting most
accurate RTT samples back to the sender, right?

> > o) Retransmission ambiguity detection during loss recovery

Not really, you'll not get a lower TS back for a long delayed segment,
which was already retransmitted; also, if the retransmitted segment is
beyond some (still existing hole), Eifel + RFC1323 still fail to
disambiguate between original and retransmitted segment, when it's
delivered.

> reverting to timer-based methods.

Ok, this revolves around lost retransmission detection at the
end-of-stream / below RecoveryPoint. First, LRD is again not widely
available (only one particular stack has that feature), nor officially
specified. Second, it depends on the ack of a segment beyond recovery
point to find that a retransmission was lost.

However, if the sender can infer the exact ordering in which all the
segements (original, retransmitted, reordered,...) were delivered to the
client, it can make a more informed choice if one particular segement
was lost (again), before going beyond RecoveryPoint (ie. Retransmit as
soon as the segment re-transmitted (!) dupthresh segments later than the
one in question, is received; For emphasis, I really mean the
re-transmitted segment, not the the delivery of a delayed original
segment (because that would be in indication, that there is a good
chance of the still-lost segement to be delivered via a slower path;
re-sending then would violate the packet conservation principle).

> 
> > As with the deployment of SACK, separating "what" to send from
"when"
> to send it could be driven one step further. In particular, less
> conservative loss recovery schemes which do not trade principles of
> packet conservation against timeliness, require a reliable way of
> prompt and best possible feedback from the receiver about any
delivered
> segment and their ordering. SACK alone goes quite a long way, but
using
> Timestamp information in addition could remove any ambiguity.
> 

Hope I made this clear already: For out-of-sequence delivered,
retransmitted segments. Under certain circumstances, the sender may
re-transmit one segment more than twice, and it should be possible to
discriminate between each individual instance of that segment by using
SACK+TS information.

I can send around a sketch of such a less-conservative SACK loss
recovery scheme, using SACK+TS information, for detailed discussions
about it...?

Best regards,
   Richard

---

From: "SCHARF, Michael" <[email-masked]>
Date: Mon, 17 Jan 2011 21:52:01 +0100

Richard,

I happened to look at the RTO calculation and RTO spike issue a long time ago. For whatever it is worth, I scanned that old work and extracted some references that may or may not be well-known. A number of algorithms have indeed been developed to address these issues (e. g., Linux stack), and several papers tried to further optimize the timer calculation in particular for mobile environments, including amongst others:

R. Ludwig und K. Sklower. The Eifel Retransmission Timer. ACM SIGCOMM Computer Communications Review, 30(3), 2000, pp. 17–27 [this is not the actual Eifel algorithm]

H. Ekstroem and R. Ludwig, “The Peak-Hopper: A New End-to-End Retransmission Timer for Reliable Unicast Transport,” Proc. IEEE INFOCOM, 2004

K. Jacobsson, H. Hjalmarsson, N. Moeller and K. H. Johansson, "Round-Trip time estimation in communication networks using adaptive Kalman filtering"

A. Kesselman, Y. Mansour, "Optimizing TCP Retransmission Timeout", Springer LNCS 3421, 2005

I. Psaras, V. Tsaoussidis, "Why TCP timers (still) don't work well", Computer Networks, Volume 51, Issue 8, 6 June 2007

etc.

And, BTW, a young wannabe-TCP researcher once tried to systematically understand the RTO spikes resulting from RFC 2988:

Michael Scharf, Marc C. Necker, Bernd Gloss: "The Sensitivity of TCP to Sudden Delay Variations in Mobile Networks", Springer LNCS 3042, 2004, pp. 76-87

If a better RTT estimation or RTO calculation was indeed needed, these papers might contain some interesting starting points.

Michael

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Mon, 17 Jan 2011 22:57:34 -0000

Hi Michael,

again thank you for these references!

I wanted to bring this particular issue up, to discuss if an improved RTO calculation should be brought into a hypothetical I-D talking about improved signaling using existing options.

The one currently used by Linux has the merit of extremely wide deployment, and being conservative (only improves one particular aspect over the current standard calculation).

For non-technical issues, "Eifel" algorithms offer less good choice for any such future I-D work... (restrictions on IPR prevent the use in commercial implementations unfortunately).

However, I think most of these scenarios would also benefit from obtaining good feedback about the RTT samples (with the additional side-info, if the RTT was obtained off a reordered or retransmitted segment). But current signaling doesn't yield that feedback back from the client.

 Best regards,
   Richard

From: SCHARF, Michael [mailto:[email-masked]] 
Sent: Montag, 17. Jänner 2011 21:52
To: Scheffenegger, Richard; [email-masked]; [email-masked]; [email-masked]
Cc: Matt Mathis; Mark Allman
Subject: Re: [tcpm] RTTM + timestamps

Richard,

R. Ludwig und K. Sklower. The Eifel Retransmission Timer. ACM SIGCOMM Computer Communications Review, 30(3), 2000, pp. 17-27 [this is not the actual Eifel algorithm]

H. Ekstroem and R. Ludwig, "The Peak-Hopper: A New End-to-End Retransmission Timer for Reliable Unicast Transport," Proc. IEEE INFOCOM, 2004

etc.

Michael

---

From: Alexander Zimmermann <[email-masked]>
Date: Tue, 18 Jan 2011 08:53:12 +0100

And don't forget also Mark's work

Using Spurious Retransmissions to Adapt the Retransmission Timeout
http://tools.ietf.org/html/draft-allman-rto-backoff-05

Am 17.01.2011 um 21:52 schrieb SCHARF, Michael:

> _______________________________________________
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tcpm

//