Subject: [rmcat] Sender or Receiver based CC (was RE: Send timestamps)

From: Ingemar Johansson S <[email-masked]>
Date: Tue, 18 Dec 2012 09:50:02 +0000

Hi
Thanks Harald and Stefan
OK, understand. The concept is then to do atleast the delay based rate adaptation in the receiving end. The feedback the sender would then be either an absolute bitrate value or a relative increase/decrease value depending on the algorithm.

Change subject line as I deviate from the original thread a little.
I believe this has been discussed before but repeat it.

What about packet loss  and ECN marks ? ,  bufferbloat will eventually go away, may take 5 years, 10 years, 20 years, don't know. I see it unlikely that a delay based algo will be able to tune it self such that it will efficiently avoid packet drops, for instance a queue with the CoDel algorithm may drop/mark packets even at very low queue depths because of its inherent design. So the algo needs to be reactive to packet loss/marks (not a particularly controversial point)

Here one can chose two paths for the packet loss/mark based rate adaptation.
Sender based rate adaptation: Requires feedback of packet drops/mark, the accuracy depends on how the feedback is used.
Receiver based rate adaptation: Feedback is only a rate command.

It would seems like the receiver based algo is to prefer. There are however at least two reasons to why a sender based algo is to prefer.

1)      Ack-clocking, while TCP is not 100% perfect it has sofar avoided collapsing the internet completely.  A big reason is ack-clocking meaning that sudden increases of RTT is reacted to quite fast. At the same time that packet loss/marks are reported, it is also possible to report back successfully received packets. Only a receiver based algo may be too slow in this respect. For the ack-clocking to work some timeliness of the feedback is required, RTCP may be too infrequent, inband feedback has been suggested as a solution earlier.

2)      ConEx: I believe that the future will require that applications expose the congestion that they cause. A ConEx enabled endpoint is required to state caused congestion, this means that the receiver must feedback the packet loss/marks accurately, inband feedback may be to prefer here as it is more timely than RTCP.
Both of the statements above implines that one may as well to the packet loss/mark based rate adaptation the sender side.

I have deliberately only considered communication between two peers in this email. More advanced cases may of course add other concerns.

/Ingemar

From: Harald Alvestrand [mailto:[email-masked]]
Sent: den 17 december 2012 20:37
To: Ingemar Johansson S
Cc: [email-masked]
Subject: Re: [rmcat] Send timestamps

On 12/17/2012 03:45 PM, Ingemar Johansson S wrote:
Hi

I believe that it can make sense to use a separate timestamp for congestion control but I may need to read and understand some more. A few reflections though.

Unless I miss something, this is quite close to the TCP timestamps which are used for congestion avoidance in TCP Vegas and LEDBAT.
The problem in Vegas is that it is sensitive to congestion in the feedback path, not shure though how much concern that should be.
If we keep a model of computation-at-receiver, it's not a problem at all.

LEDBAT modifies this and implement the concept of base delay, but suffers from late comers advantage.
Both the above assume that one ACKs are returned to the sender almost immediately (delay ACK adds some uncertanity here) also one don't need to synchronize clocks.
Here I get unsure about what to do with the received timestamps, I guess you can compute a delta between sent and received timestamp but unless you have exactly synchronized clocks in sender(s) and receiver(s), you will have an unknown offset that can possibly also drift due to clock skew.

As Stefan says - since we measure ~a moving average of difference between the (receive timestamp - send timestamp) of successive packets, not an absolute transit time, value, this is not likely to be an issue.

I have a hard time imagining clock drift so severe that it will significantly influence the deltas of packets that are sent less than a second apart. Clock jumps (like leap seconds) may be a measurable, but extremely transient, influence.

---

From: Michael Welzl <[email-masked]>
Date: Tue, 18 Dec 2012 11:05:45 +0100

Hi,

In line:

On 18. des. 2012, at 10:50, Ingemar Johansson S wrote:

> What about packet loss  and ECN marks ? ,  bufferbloat will eventually go away, may take 5 years, 10 years, 20 years, don’t know. I see it unlikely that a delay based algo will be able to tune it self such that it will efficiently avoid packet drops, for instance a queue with the CoDel algorithm may drop/mark packets even at very low queue depths because of its inherent design. So the algo needs to be reactive to packet loss/marks (not a particularly controversial point)

Indeed, I think we all agree on this?

> 1)      Ack-clocking, while TCP is not 100% perfect it has sofar avoided collapsing the internet completely.  A big reason is ack-clocking meaning that sudden increases of RTT is reacted to quite f…

I think that ACK clocking is not really an option for a rate based scheme with reasonably limited feedback anyway. You say that ACK-clocking is a big reason for TCP preventing the Internet from collapsing. I challenge that notion (I can hear the sound from the audience...). Yes it has been said again and again that ACK-clocking has that seminal role, but show me some proof. I don't remember seeing a paper which convincingly shows exactly that.

We can, on the other hand, say that rate based congestion controls (as used at the app layer in UDP based apps already) haven't yet driven the Internet into collapse...

I would argue that the more important thing seems to be to have a timeout, reacting on a reasonable RTT based time scale, and that can be achieved with a rate based scheme.

> 2)      ConEx: I believe that the future will require that applications expose the congestion that they cause. A ConEx enabled endpoint is required to state caused congestion, this means that the r…

I would suggest to standardize RMCAT extensions for ConEx later, when we see a need due to widespread ConEx deployment   ;-)

> I have deliberately only considered communication between two peers in this email. More advanced cases may of course add other concerns.

Cheers,
Michael

> Both the above assume that one ACKs are returned to the sender almost immediately (delay ACK adds some uncertanity here) also one don’t need to synchronize clocks.

---

From: Ingemar Johansson S <[email-masked]>
Date: Tue, 18 Dec 2012 10:31:09 +0000

Hi

As regards to ACK-clocking
What comes into mind is the work on TWFC
http://www.slideshare.net/soohyunc/pfld-ne-t09
There should be full paper somewhere, don't find it though.

ConEx: Yes, need to see it fly, might take a while, might take like forever....
I put this as a future consideration. If we build something completely receiver based however we may end up with a headache in the future if ConEx flies as one will then anyway need to feed back packet loss/marks to the sender.

/Ingemar

From: Michael Welzl [mailto:[email-masked]]
Sent: den 18 december 2012 11:06
To: Ingemar Johansson S
Cc: Harald Alvestrand; [email-masked]; [email-masked]
Subject: Re: [rmcat] Sender or Receiver based CC (was RE: Send timestamps)

Hi,

In line:

Hi
Thanks Harald and Stefan

/Ingemar

Cheers,
Michael

From: Harald Alvestrand [mailto:[email-masked]]<mailto:[mailto:[email-masked]]>
Sent: den 17 december 2012 20:37
To: Ingemar Johansson S
Cc: [email-masked]<mailto:[email-masked]>
Subject: Re: [rmcat] Send timestamps

---

From: Saverio Mascolo <[email-masked]>
Date: Tue, 18 Dec 2012 11:39:24 +0100

dear michael,

we showed in a 1999 paper entitled "Congestion control in high-speed
communication networks using the Smith principle":

http://c3lab.poliba.it/images/3/3a/Automatica.pdf

  that ack clocking is equivalent to implement a Smith predictor, which is
 important to react fast. In other ways, ack clocking  takes into account
the in flight packets that can be a lot (=bandwith times rtt).

This need was also recognized in the second version of TFRC.

Regards,
Saverio

On Tue, Dec 18, 2012 at 11:05 AM, Michael Welzl <[email-masked]> wrote:

> Hi****
> Thanks Harald and Stefan****
> OK, understand. The concept is then to do atleast the delay based rate
> adaptation in the receiving end. The feedback the sender would then be
> either an absolute bitrate value or a relative increase/decrease value
> depending on the algorithm.****
> ** **
> Change subject line as I deviate from the original thread a little.****
> I believe this has been discussed before but repeat it.****
> ** **
> What about packet loss  and ECN marks ? ,  bufferbloat will eventually go
> away, may take 5 years, 10 years, 20 years, don’t know. I see it unlikely
> that a delay based algo will be able to tune it self such that it will
> efficiently avoid packet drops, for instance a queue with the CoDel
> algorithm may drop/mark packets even at very low queue depths because of
> its inherent design. So the algo needs to be reactive to packet loss/marks
> (not a particularly controversial point)
>
>
> ** **
> Here one can chose two paths for the packet loss/mark based rate
> adaptation.****
> Sender based rate adaptation: Requires feedback of packet drops/mark, the
> accuracy depends on how the feedback is used.****
> ****
> ** **
> It would seems like the receiver based algo is to prefer. There are
> however at least two reasons to why a sender based algo is to prefer.****
> 1)      Ack-clocking, while TCP is not 100% perfect it has sofar avoided
> collapsing the internet completely.  A big reason is ack-clocking meaning
> that sudden increases of RTT is reacted to quite fast. At the same time
> that packet loss/marks are reported, it is also possible to report back
> successfully received packets. Only a receiver based algo may be too slow
> in this respect. For the ack-clocking to work some timeliness of the
> feedback is required, RTCP may be too infrequent, inband feedback has been
> suggested as a solution earlier.
>
>
> I think that ACK clocking is not really an option for a rate based scheme
> with reasonably limited feedback anyway. You say that ACK-clocking is a big
> reason for TCP preventing the Internet from collapsing. I challenge that
> notion (I can hear the sound from the audience...). Yes it has been said
> again and again that ACK-clocking has that seminal role, but show me some
> proof. I don't remember seeing a paper which convincingly shows exactly
> that.
>
> We can, on the other hand, say that rate based congestion controls (as
> used at the app layer in UDP based apps already) haven't yet driven the
> Internet into collapse...
>
> I would argue that the more important thing seems to be to have a timeout,
> reacting on a reasonable RTT based time scale, and that can be achieved
> with a rate based scheme.
>
>
> ****
> 2)      ConEx: I believe that the future will require that applications
> expose the congestion that they cause. A ConEx enabled endpoint is required
> to state caused congestion, this means that the receiver must feedback the
> packet loss/marks accurately, inband feedback may be to prefer here as it
> is more timely than RTCP.
>
>
> I would suggest to standardize RMCAT extensions for ConEx later, when we
> see a need due to widespread ConEx deployment   ;-)
>
>
>  ****
> Both of the statements above implines that one may as well to the packet
> loss/mark based rate adaptation the sender side.
>
> ****
> ** **
> I have deliberately only considered communication between two peers in
> this email. More advanced cases may of course add other concerns.****
> ** **
> /Ingemar****
>
>
> Cheers,
> Michael
>
>
>
> ** **
> ** **
>  *From:* Harald Alvestrand [mailto:[email-masked]]
> *Sent:* den 17 december 2012 20:37
> *To:* Ingemar Johansson S
> *Cc:* [email-masked]
> *Subject:* Re: [rmcat] Send timestamps****
> ** **
> On 12/17/2012 03:45 PM, Ingemar Johansson S wrote:****
>
> Hi****
>  ****
> I believe that it can make sense to use a separate timestamp for
> congestion control but I may need to read and understand some more. A few
> reflections though.****
>  ****
> Unless I miss something, this is quite close to the TCP timestamps which
> are used for congestion avoidance in TCP Vegas and LEDBAT.****
> The problem in Vegas is that it is sensitive to congestion in the feedback
> path, not shure though how much concern that should be.****
>
> ****
> LEDBAT modifies this and implement the concept of base delay, but suffers
> from late comers advantage.****
> Both the above assume that one ACKs are returned to the sender almost
> immediately (delay ACK adds some uncertanity here) also one don’t need to
> synchronize clocks.****
> Here I get unsure about what to do with the received timestamps, I guess
> you can compute a delta between sent and received timestamp but unless you
> have exactly synchronized clocks in sender(s) and receiver(s), you will
> have an unknown offset that can possibly also drift due to clock skew.****
>
>
> As Stefan says - since we measure ~a moving average of difference between
> the (receive timestamp - send timestamp) of successive packets, not an
> absolute transit time, value, this is not likely to be an issue.
>
> I have a hard time imagining clock drift so severe that it will
> significantly influence the deltas of packets that are sent less than a
> second apart. Clock jumps (like leap seconds) may be a measurable, but
> extremely transient, influence.****
>
>
>

-- 
Saverio Mascolo, Full Professor
Dipartimento di Elettrotecnica ed Elettronica
Politecnico di Bari
Via Orabona 4, 70125 Bari Italy
Tel. +39 080 5963621
Fax. +39 080 5963410
email:[email-masked]

http://c3lab.poliba.it

=================================
 This message may contain confidential and/or legally privileged
information.
  If you are not the intended recipient of the message, please destroy it.
 Any unauthorized dissemination, distribution, or copying of the material in
 this message, and any attachments to the message, is strictly forbidden.

---

From: Michael Welzl <[email-masked]>
Date: Tue, 18 Dec 2012 11:45:27 +0100

On 18. des. 2012, at 11:31, Ingemar Johansson S wrote:

> There should be full paper somewhere, don’t find it though.  

Oh yes, you totally have a point there. The thesis surely has all the details, it is at:
http://tfwc.hackerslab.eu/docs
(It seems that the pfldnet2009 page doesn't work anymore. I was on the org. committee, and at the conference, so that paper is in fact on my shelves somewhere...  :-)   )

Anyway, this isn't making the point that ACK clocking is "a big reason for TCP preventing the Internet from collapsing". Sure it's a benefit, and of course we can find situations where ACK-clocked protocols do better, no doubt about that.

> I put this as a future consideration. If we build something completely receiver based however we may end up with a headache in the future if ConEx flies as one will then anyway need to feed back pa…

So this is where we differ: I don't believe that this would be a major headache. The point of keeping stuff at the receiver is just to reduce the feedback frequency. Inevitably, if you need the sender to have a more up-to-date picture of things, you'll have to increase that frequency, and possibly you'd also want to somehow extend the feedback format for ConEx. I don't think that's going to be such a big deal to retrofit, if it really becomes necessary.

Cheers,
Michael

---

From: Michael Welzl <[email-masked]>
Date: Tue, 18 Dec 2012 11:50:58 +0100

Hi Saverio,

"important to react fast" != "prevent the Internet from collapsing".

Of course I agree that ACK clocking makes sense, and I understand that it gives you tight control of the number of packets in flight, which can make your control much better. What I'm challenging is the notion that this is an absolute necessity, or else the Internet would melt. Would it really, if we'd all use e.g. TFRC instead of TCP?  (argh, I hate to imagine that particular scenario  :-)   TFRC is perhaps not an ideal example here...)

Anyway, I guess that, for reasonable operation in the public Internet, rate-based control with per-RTT feedback and timeouts based on that, you can do well enough under most circumstances. That's all I'm saying.

Cheers,
Michael

On 18. des. 2012, at 11:39, Saverio Mascolo wrote:

> dear michael,
> 
> we showed in a 1999 paper entitled "Congestion control in high-speed communication networks using the Smith principle":
> 
>   that ack clocking is equivalent to implement a Smith predictor, which is  important to react fast. In other ways, ack clocking  takes into account the in flight packets that can be a lot (=bandwith times rtt).
> 
>  This message may contain confidential and/or legally privileged information.

---

From: Ingemar Johansson S <[email-masked]>
Date: Wed, 19 Dec 2012 13:20:58 +0000

Hi

Yes, you are probably right, I should probably have avoided the term "collapse",
Question is if ack-clocking provides a benefit large enough to motivate the higher feedback rate (even though the feedback can perhaps be inband?).
One possible use case is wireless access such as LTE uplink where congestion can build up quite quickly, don't have any proof that ack-clocking can improve things here however.

/Ingemar

From: Michael Welzl [mailto:[email-masked]]
Sent: den 18 december 2012 11:45
To: Ingemar Johansson S
Cc: Harald Alvestrand; [email-masked]; [email-masked]
Subject: Re: [rmcat] Sender or Receiver based CC (was RE: Send timestamps)

Hi

Cheers,
Michael

/Ingemar

From: Michael Welzl [mailto:[email-masked]]<mailto:[mailto:[email-masked]]>
Sent: den 18 december 2012 11:06
To: Ingemar Johansson S
Cc: Harald Alvestrand; [email-masked]<mailto:[email-masked]>; [email-masked]<mailto:[email-masked]>
Subject: Re: [rmcat] Sender or Receiver based CC (was RE: Send timestamps)

Hi,

In line:

Hi
Thanks Harald and Stefan

/Ingemar

Cheers,
Michael

---

From: Michael Welzl <[email-masked]>
Date: Wed, 19 Dec 2012 16:42:13 +0100

On Dec 19, 2012, at 2:20 PM, Ingemar Johansson S <[email-masked]> wrote:

> Hi
>  
> Yes, you are probably right, I should probably have avoided the term “collapse”,

exactly! spot on

> One possible use case is wireless access such as LTE uplink where congestion can build up quite quickly, don’t have any proof that ack-clocking can improve things here however.

…. but other wireless links actually make a point for feedback reduction (on wlans, in typical mostly-download scenarios, most of the collisions are your data + your acks….

---

From: Saverio Mascolo <[email-masked]>
Date: Wed, 19 Dec 2012 18:53:45 +0100

Ack clocking is fundamental since it is an intrinsic stabilizer of the
network, one packet out - one packet in. This out-in is also executed at
the right time, "real time" as it has to be for dynamic control.

Saverio

On Wednesday, December 19, 2012, Ingemar Johansson S wrote:

>  Hi****
>
> ** **
>
> Yes, you are probably right, I should probably have avoided the term
> “collapse”, ****
>
> Question is if ack-clocking provides a benefit large enough to motivate
> the higher feedback rate (even though the feedback can perhaps be inband?).
> ****
>
> One possible use case is wireless access such as LTE uplink where
> congestion can build up quite quickly, don’t have any proof that
> ack-clocking can improve things here however.****
>
> ** **
>
> ** **
>
> /Ingemar****
>
> ** **
>
> *From:* Michael Welzl [mailto:[email-masked] <javascript:_e({},
> 'cvml', [email-masked]');>]
> *Sent:* den 18 december 2012 11:45
> *Cc:* Harald Alvestrand; [email-masked] <javascript:_e({}, 'cvml',
> [email-masked]');>; [email-masked] <javascript:_e({}, 'cvml',
> [email-masked]');>
> *Subject:* Re: [rmcat] Sender or Receiver based CC (was RE: Send
> timestamps)****
>
> ** **
>
> ** **
>
> On 18. des. 2012, at 11:31, Ingemar Johansson S wrote:****
>
>
>
> ****
>
> Hi****
>
>  ****
>
> As regards to ACK-clocking****
>
> What comes into mind is the work on TWFC****
>
> http://www.slideshare.net/soohyunc/pfld-ne-t09****
>
> There should be full paper somewhere, don’t find it though.  ****
>
> ** **
>
> Oh yes, you totally have a point there. The thesis surely has all the
> details, it is at:****
>
> http://tfwc.hackerslab.eu/docs****
>
> (It seems that the pfldnet2009 page doesn't work anymore. I was on the
> org. committee, and at the conference, so that paper is in fact on my
> shelves somewhere...  :-)   )****
>
> ** **
>
> Anyway, this isn't making the point that ACK clocking is "a big reason for
> TCP preventing the Internet from collapsing". Sure it's a benefit, and of
> course we can find situations where ACK-clocked protocols do better, no
> doubt about that.****
>
> ** **
>
> ** **
>
>   ConEx: Yes, need to see it fly, might take a while, might take like
> forever....****
>
> I put this as a future consideration. If we build something completely
> receiver based however we may end up with a headache in the future if ConEx
> flies as one will then anyway need to feed back packet loss/marks to the
> sender.****
>
>  ** **
>
> So this is where we differ: I don't believe that this would be a major
> headache. The point of keeping stuff at the receiver is just to reduce the
> feedback frequency. Inevitably, if you need the sender to have a more
> up-to-date picture of things, you'll have to increase that frequency, and
> possibly you'd also want to somehow extend the feedback format for ConEx. I
> don't think that's going to be such a big deal to retrofit, if it really
> becomes necessary.****
>
> ** **
>
> Cheers,****
>
> Michael****
>
> ** **
>
> ** **
>
>
>
> ****
>
>  ****
>
> /Ingemar****
>
>  ****
>
> *From*
>

http://c3lab.poliba.it

---

From: Michael Welzl <[email-masked]>
Date: Thu, 20 Dec 2012 00:37:08 +0100

Saverio - all that a rate based protocol does is relax this rule somewhat. The way you describe it, and the way TCP does it, is on a per-packet granularity. The question is: what granularity is really needed? I think Ingemar has precisely phrased the key question: is the benefit enough to motivate the higher feedback rate? This is an engineering trade-off, how do we make the right decision here?

Here's a pragmatic thought, from looking at draft-alvestrand-rtcweb-congestion (I'll call it RRTCC in the rest of this email, but it's high time for a better acronym if you ask me … may I suggest ResiDedi? That stands for "Receiver-side Delay Difference"  :-)   ) - with this mechanism, in the absence of feedback (e.g. due to extremely heavy congestion in both directions), the sender will keep increasing its rate until a time of 2*t_max_fb_interval is reached. The value of this parameter is not given - but: if it is larger than TCP's RTO, competing TCPs along the same paths might be pushed into timeout, and RRTCC flow would just keep increasing its rate…

That doesn't seem good to me. Let's say we fix it, by requiring this interval to be an RTT, which is a conservative lower bound for an RTO - a case of no RTT variation (probably unrealistic in the presence of congestion). Now we can ask ourselves: why care about TCPs on the exact same path only? What about TCPs whose RTT is dramatically different, e.g. shorter?

A TCP with a large RTT will exhibit the same behavior towards a short-RTT TCP as described for RRTCC above: the short-RTT TCP will already have a timeout while the long-RTT TCP will still keep increasing. We could say that the Internet has maintained reasonable performance with the existing TCP behavior and RTT variations, and so, mimicking the long-vs-short-RTT thing by requiring RRTCC to timeout after 1 RTT (or any better resemblance of an RTO we can come up with) would seem okay.

Can we stretch that further? Say, we react after 2 RTTs… isn't that like saying: would we get reasonable Internet service even if RTT variations were twice as large?
Well, if that is the case, then the answer is no, I think - from anecdotal evidence: Andrew McGregor would tell you that the big RTT differences people in New Zealand experience make some things work rather badly, and (if I understood him right) that's what makes him so excited about FQ_CoDel - being where he is, he really experiences the difference of FQ (with CoDel limiting the delay). I have heard similar stories from others, and had similar experiences in Australia.

So, would it be reasonable to conclude that RTT variation as it is is already bad enough, and hence RRTCC's sender timeout shouldn't be more than 1 RTO, which we could pick to be 1 RTT  (note, as an alternative, e.g. TFRC chooses RTO=4*RTT, but without any justification AFAIK)?

Then note, of course: if that logic works, it applies to any mechanism, not just RRTCC...

I wonder what people think about this. I suspect that my logic is broken, in some way, somewhere up there in the text…

Cheers,
Michael

On Dec 19, 2012, at 6:53 PM, Saverio Mascolo <[email-masked]> wrote:

> Ack clocking is fundamental since it is an intrinsic stabilizer of the network, one packet out - one packet in. This out-in is also executed at the right time, "real time" as it has to be for dynamic control.
> 
> Saverio
> 
> From

---

From: Harald Alvestrand <[email-masked]>
Date: Thu, 20 Dec 2012 09:23:31 +0100

On 12/20/2012 12:37 AM, Michael Welzl wrote:
> That doesn't seem good to me.
No, and it's why the RRTCC algorithm requires a sender-side limiter 
based on the TFRC equation in addition to the receiver-side estimator.

In addition, it makes sense to implement Colin Perkins' "circuit 
breakers" algorithm, which mandates stopping the flow on two RTCP 
retransmission intervals without feedback packets.

Any receiver-side belt requires *some* sender-side suspenders.

Rest of message is beyond easy comprehension for me while on vacation.....

>   Let's say we fix it, by requiring this interval to be an RTT, which is a conservative lower bound for an RTO - a case of no RTT variation (probably unrealistic in the presence of congestion). Now we can ask ourselves: why care about TCPs on the exact same path only? What about TCPs whose RTT is dramatically different, e.g. shorter?
>