Subject: [Tsvwg] Rethinking Karn's algorithm

From: Reiner Ludwig <[email-masked]>
Date: Tue, 25 Mar 2003 23:22:46 +0100

instead of an explicit out-of-band "Link Up"-Trigger to jump-start a TCP 
sender that is stuck with a backed-off RTO, we could also rethink Karn's 
algorithm ...

The motivation for the backoff of the RTO is to eventually "catch" a valid 
RTT timing which - according to Karn's algorithm - should not be taken from 
data segments that had been retransmitted (retransmission ambiguity).

But:
1. With timestamps, we can also take valid RTTs from retransmitted segments.
2. Without timestamps and a timeout for segment N, we could delay making
    the RTO more conservative until the ACK for N is received. According to
    Karn's algorithm we should not take an RTT for segment N, anyway. What
    really matters is that the RTO has been made more conservative when
    segment N+1 is sent. The question of how the RTO is made more conservative
    is a separate issue. Probably different alternatives exist.

Either way, we could allow the TCP sender to retransmit the oldest 
outstanding segment every RTO, i.e., without backoff!

There might be an (academic?) issue with persistent congestion, although 
that was not a consideration in Karn's SIGCOMM '87 paper. Still, sending 
one packet every RTO (without backoff) seems sufficiently conservative. 
Anyway, backing off to ultimately 64 seconds seems far too conservative.

///Reiner

_______________________________________________
tsvwg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tsvwg

---

From: "Armando L. Caro Jr." <[email-masked]>
Date: Tue, 25 Mar 2003 19:05:04 -0500 (EST)

>     is a separate issue. Probably different alternatives exist.

Yes I agree.

Although the motivation is different... We have investigated using
Timestamps in SCTP for obtaining a more accurate RTT estimate of alternate
destination paths. In SCTP, the alternate destinations are used only for
retransmissions (and heartbeats).  Hence, the RTO of the alternate
destinations generally are more conservative than necessary... reducing
throughput of the association. We found that using Timestamps
significantly improves performance simply because more RTT measurements
are obtained for the alternate destinations, and thus the RTOs are more
accurate.

The motivation for and a BRIEF description of the SCTP TIMESTAMP
Chunk is in the following paper:

Transport Layer Multihoming For Fault Tolerance In FCS Networks
Armando L. Caro Jr., Paul D. Amer, Randall R. Stewart
CTA 2003, April 2003
www.cis.udel.edu/~acaro/papers

We are currently writing the paper which presents the results. The paper
should be available in a couple of weeks.

> Anyway, backing off to ultimately 64 seconds seems far too conservative.

I agree that 64 seconds (60 secs with SCTP) is much too conservative.
However, I don't understand why you think multiple RTOs without backoff is
ok or even conservative. I think I am missing something here... If the
timeout occurs because the RTO is too small, how will the sender know to
increase the RTO?

~armando

0--                                                  --0
| Armando L. Caro Jr.      |  Protocol Engineering Lab |
| www.cis.udel.edu/~acaro  |    University of Delaware |
0--                                                  --0

---

From: Reiner Ludwig <[email-masked]>
Date: Thu, 27 Mar 2003 13:08:14 +0100

At 01:05 26.03.2003, Armando L. Caro Jr. wrote:
>ok or even conservative. I think I am missing something here...

I didn't mean conservative in terms of adapting the RTO to a potentially 
increased RTT, but conservative in terms of impact on the congestion state 
in the network.
For a potentially severly congested bottleneck, having the end-points send 
one packet per RTO seems sufficiently conservative. I.e., every router in 
today's Internet should at least be able to handle a certain peak number of 
flows (depending on some worst case traffic estimate for that location in 
the topology) each sending with a minimum rate of one packet per RTO.

I guess the times when LANs where interconnected by slow dial-up 
connections are long gone ... and if they still exist then they certainly 
don't pose a threat to the stability of the (public) Internet.

>If the
>timeout occurs because the RTO is too small,

If that was the reason for the timeout, it is quite likely that the ACK for 
the retransmitted segment will arrive shortly after the RTO, and even more 
likely before a second timeout with a non-backed-off RTO.

>how will the sender know [how] to
>increase the RTO?

I guess several options exist. One option would be to allow timing of 
retransmitted segments even without timestamps by taking as the RTT the 
time between sending the original segment and the receipt of the ACK, 
independent of whether that ACK was triggered by the original or some 
retransmit. Alternatively, with the current retransmission timer [RFC2988] 
we could require that when timestamps are not used then SRTT should be 
doubled once the ACK for oldest outstanding segment arrives after a timeout.

///Reiner

---

From: "Armando L. Caro Jr." <[email-masked]>
Date: Thu, 27 Mar 2003 13:38:22 -0500 (EST)

Reiner,

Thanks for the clarification... I like this idea.

~armando

0--                                                  --0

---

From: Mark Allman <[email-masked]>
Date: Thu, 27 Mar 2003 16:07:22 -0500

I don't follow this at all...

> The motivation for the backoff of the RTO is to eventually "catch"
> a valid RTT timing which - according to Karn's algorithm - should
> not be taken from data segments that had been retransmitted
> (retransmission ambiguity).
>
> [...]
>
> There might be an (academic?) issue with persistent congestion,
> although that was not a consideration in Karn's SIGCOMM '87 paper.

The Karn and Partridge paper was about managing the RTO estimator
and timer.  The 1988 Jacobson paper motivated the backoff in terms
of congestion control:

    "Another timer mistake is in the backoff after a retransmit: If
    a packet has to be retransmitted more than once, how should the
    retransmits be spaced?  For a transport endpoint embedded in a
    network of unknown topology and with an unknown, unknowable and
    constantly changing population of competing conversations, only
    one scheme has any hope of working---exponential backoff"

My own intuition says that backoff is simply continuing the notion
of halving the sending rate that drives the cwnd adjustments.

allman

--
Mark Allman -- BBN/NASA GRC -- http://roland.grc.nasa.gov/~mallman/
_______________________________________________
tsvwg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tsvwg

---

From: Reiner Ludwig <[email-masked]>
Date: Fri, 28 Mar 2003 09:39:54 +0100

>of halving the sending rate that drives the cwnd adjustments.

I definitely believe that this was the right approach for the Internet some 
15 years ago. At that time the Internet was really a collection of LANs 
interconnected by slow dial-up lines (potentially even only 
semi-permanent). But today's Internet looks different. For example, quoting 
from 
ftp://ftp.rfc-editor.org/in-notes/internet-drafts/draft-iab-research-funding-00.txt:

   "One of the factors that has blunted the demand for QoS has been the
    transition of the Internet infrastructure from heavy congestion in
    the early 1990s, to overprovisioning in backbones and in many
    international links now."

So, in general I strongly believe that we have to ask ourselves - and not 
only with respect to Karn's algorithm - whether we still need to be so 
ultra-conservative with end-point algorithms.

Concerning Karn's algorithm, I'm not advocating "retransmit every 
non-backed-off RTO forever". We do not want to see the Internet poluted 
with a bunch of half-broken TCP connections that would do that. But, there 
are certainly different alternatives. For example, a TCP sender could 
retransmit every non-backed-off RTO for the first 30 seconds, every 2xRTO 
for the following 60 seconds, every 4xRTO for the following 120 seconds, 
etc. until the sending application gives up, or after some upper bound R2 
as defined in RFC1122. That is also an exponential backoff.

///Reiner

PS.: Apart from Karn's algorithm, I even believe that with the current 
economics behind the operation of today's (best-effort) Internet, it should 
be possible to allow end-points a minimum send rate (e.g., 5 kb/s) as long 
as they get receiver feedback every N RTTs. I think that this is needed if 
we are serious about wide-scale deployment of decent-quality services like 
streaming and VoIP over best-effort.

---

From: Mark Allman <[email-masked]>
Date: Fri, 28 Mar 2003 09:19:16 -0500

> So, in general I strongly believe that we have to ask ourselves -
> and not only with respect to Karn's algorithm - whether we still
> need to be so ultra-conservative with end-point algorithms.

That's a fine question and a fertile area for research maybe.  But,
I'll disagree quite strongly that anything like this is ready for
the IETF.

I don't think you have made the case that the RTO should be the
lower bound on the sending rate.  An RTO of 30 or 60 seconds doesn't
"just happen"; rather it takes lots of repeated losses to make it
happen.  Clearly, in that environment you have a network that is
badly busted in some way (which you have direct evidence of).  I
don't understand the motivation in being terribly aggressive in this
situation.

(And, I am still firmly in the camp that says that the RTO should be
the last resort for loss repair and we should continue to refine
other mechanisms to avoid RTOs.  And, if we can largely do that then
I don't much care how conservative the RTO is.)

allman

---

From: Reiner Ludwig <[email-masked]>
Date: Mon, 31 Mar 2003 11:30:34 +0200

>don't understand the motivation in being terribly aggressive in this

There is certainly a broad range for viable solutions between "terribly 
aggressive" and "ultra-conservative".

If you think that "Rethinking Karn's algorithm" to make it less 
conservative in *some* way is not ready for the IETF, I wonder about your 
view on an explicit out-of-band "Link Up"-Trigger. How ready is that for 
the IETF?

I mean, *the least* we could do is to discuss a new upper bound for the RTO 
back-off. What's the motivation for the current upper bound of 60 seconds?

///Reiner

---

From: Mark Allman <[email-masked]>
Date: Mon, 31 Mar 2003 07:28:05 -0500

> conservative in *some* way is not ready for the IETF, I wonder
> about your view on an explicit out-of-band "Link Up"-Trigger. How
> ready is that for the IETF?

It's a decent question.  Personally, I think it's OK.  I think we
can craft a transport-level response to be reasonable when receiving
explicit information from the network.  On the other hand, the RTO
backoff is done in the abscence of any information.

> I mean, *the least* we could do is to discuss a new upper bound
> for the RTO back-off. What's the motivation for the current upper
> bound of 60 seconds?

??

The only thing I have to say about this is that the current maximum
is of the right order of magnitude, I think.  Trying to optimize the
value after that is dubious, I think.  (That is, I believe it should
be conservative.  And, if it is then that means that it will be
gross in some situations.)  If we can get explicit information to
cut a very long backoff down then maybe that is OK.

allman

---

From: Reiner Ludwig <[email-masked]>
Date: Mon, 31 Mar 2003 14:56:15 +0200

At 14:28 31.03.2003, Mark Allman wrote:

>explicit information from the network.

With a less conservative version of Karn's algorithm, we would instead have 
a true end-to-end solution to the problem. That is, with a few changed 
lines of TCP sender code (or even only a single '#define') we would save 
the IETF extra work (a TRIGTRAN WG), and would avoid the deployment issues 
associated with "Link Up"-Triggers & corresponding TCP sender responses.

///Reiner

---

From: Mark Allman <[email-masked]>
Date: Mon, 31 Mar 2003 08:17:24 -0500

> With a less conservative version of Karn's algorithm, we would
> instead have a true end-to-end solution to the problem. 

I doubt it.  My own opinion is that any end2end "solution" that
would obviate the need for a link-up trigger would be too
aggressive.  I.e., there is fundemental tension between (1) probing
often enough to be very responsive on paths that have links that go
down and (2) not sending a whole lot of chud into a network that is
dropping your packets and is quite unresponsive.

> That is, with a few changed lines of TCP sender code (or even only
> a single '#define') we would save the IETF extra work (a TRIGTRAN
> WG), and would avoid the deployment issues associated with "Link
> Up"-Triggers & corresponding TCP sender responses.

IETF resources are not the only costs here.

allman

---

From: Reiner Ludwig <[email-masked]>
Date: Mon, 31 Mar 2003 15:31:56 +0200

At 15:17 31.03.2003, Mark Allman wrote:
>My own opinion is that any end2end "solution" that

I think, you have nicely summarized the tension that needs to be debated, 
but I would add that (2) needs to be weighed against the extra traffic that 
such triggers would cause. I.e., the traffic caused by all the routers that 
send explicit out-of-band link-up triggers (at some rate?) to a potentially 
large number of flows active in those routers.

[In addition, some of the trigger-receivers might not (cannot) even care, 
e.g., because they don't have any new data to sent, or because they don't 
understand the trigger, or because they never get them because the trigger 
was filtered by a firewall, etc.]

///Reiner

---

From: Spencer Dawkins <[email-masked]>
Date: Mon, 31 Mar 2003 05:55:36 -0800 (PST)

Hi, Reiner,

I believe that post-IETF 56, what's actually on the table in
TRIGTRAN is end-systems resending one "last packet" at link-up
time, not routers sending triggers.

The considerations you're listing would make explicit requests
for TRIGTRAN coverage more attractive, but what's been expressed
to me is that explicit requests would have to be a LOT more
attractive to require (even edge) routers to maintain
per-connection state - so that's why I've backed off on routers
sending triggers, at this time.

Spencer

---

From: Reiner Ludwig <[email-masked]>
Date: Mon, 31 Mar 2003 16:12:42 +0200

>time, not routers sending triggers.

Fine. But don't we have exactly that already in section 8.2 ("Recovery from 
Subnetwork Outages") of draft-ietf-pilc-link-design-13.txt which is a 
soon-to-be-BCP-RFC:

    "[...]
    It is therefore highly desirable that a subnetwork subject to outages
    not silently discard packets during an outage. Ideally, it should
    define an interface to the next higher layer (i.e., IP) that allows
    it to refuse packets during an outage, and to automatically ask IP
    for new packets when it is again able to deliver them. If it cannot
    do this, then the subnetwork should hold onto at least some of the
    packets it accepts during an outage and attempt to deliver them when
    the subnetwork comes back up. When packets are discarded, IP should
    be notified so that the appropriate ICMP messages can be sent.

    Note that it is *not* necessary to completely avoid dropping packets
    during an outage. The purpose of holding onto a packet during an
    outage, either in the subnetwork or at the IP layer, is so that its
    eventual delivery will implicitly notify TCP that the subnetwork is
    again operational. [...]"

And this works for both, hosts and routers.

///Reiner

---

From: Spencer Dawkins <[email-masked]>
Date: Mon, 31 Mar 2003 06:23:25 -0800 (PST)

Hi, Reiner,

Yeah, exactly - what I'm talking about is a more completely
specified variant of this. For instance, we might (this is an
observation, not a suggestion) recommend that host
implementations resend a packet, but not router implementations
(as your posting notes, the recommendation in LINK allows both,
but doesn't prefer one or the other).

Spencer

---

From: Mark Allman <[email-masked]>
Date: Mon, 31 Mar 2003 13:03:48 -0500

> I think, you have nicely summarized the tension that needs to be
> debated, but I would add that (2) needs to be weighed against the
> extra traffic that such triggers would cause. I.e., the traffic
> caused by all the routers that send explicit out-of-band link-up
> triggers (at some rate?) to a potentially large number of flows
> active in those routers.
> 
> [In addition, some of the trigger-receivers might not (cannot)
> even care, e.g., because they don't have any new data to sent, or
> because they don't understand the trigger, or because they never
> get them because the trigger was filtered by a firewall, etc.]

Yes, you'd want to consider that.

The trigger traffic is bounded, though, by the number of flows (per
some window of time).  Whereas, it is fairly difficult to quantify
the probing approach in any sort of realistic or meaningful way, it
would seem to me.

allman