[Codel] self tuning codel

[Codel] self tuning codel

[Dave Taht]

there's so much math in this that I cannot make heads or tails of it.

https://www.eee.hku.hk/~kcleung/papers/conferences/bufferbloat_multi-bottleneck:INFOCOM_2018/PID5170809.pdf

-- 

Dave Täht
CEO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-669-226-2619

Re: [Codel] self tuning codel

[Kathleen Nichols]

On 7/18/18 3:42 PM, Dave Taht wrote:
> there's so much math in this that I cannot make heads or tails of it.
>
>
https://www.eee.hku.hk/~kcleung/papers/conferences/bufferbloat_multi-bottleneck:INFOCOM_2018/PID5170809.pdf
>

Dave,

I would never presume to critique math in a paper co-authored by Steve
Low, but I wonder about the model/premise of this work (quotes are taken
directly from the paper so I don't misrepresent anything):

> We consider TCP
> Reno in our model since it is one of the most popular TCP
> algorithms and our analysis in this paper mainly focuses on
> AQM algorithms.

I think the paper constructs bottlenecks as places where the arrival
rate exceeds the departure rate?

Then, there is this:

> The essential idea of Algorithm 1 is that every AQM router
> needs to know all the packet dropping probabilities at the
> bottleneck links in order to compute the window sizes of the
> flows from (5). In fact, Algorithm 1 is motivated by the widely
> used Open Shortest Path First (OSPF) routing protocol [17].
> In OSPF, there is a designated router (DR) for every network
> segment, which is responsible for gathering and forwarding
> link state updates. Thus, we let a specific AQM router serve
> as a centralized DR in the system. All routers send packet
> dropping probability updates to DR. DR then updates its list
> of packet dropping probabilities and sends it to all routers

Does this seem possible to anyone? There's an inherent assumption here
that "dropping probabilities" are constant over a period of time that is
long compared to the time to do the above. In what I've seen of traffic
and AQMs this seems unlikely but I'm certainly not as well-informed on
this as some people.

I have suggested that the setting of interval might be something to
examine (that is to be adaptable in some way) from the beginning. So
it's nice to see someone take a cut at this but I'm not sure the basic
notion, that the interval is supposed to be giving the end hosts enough
time to respond to a drop, has been retained here.

> From (34), we observe that the range of I0 is determined by
> several factors and will vary if these factors change over time.
> A static value of I0 cannot always guarantee the stability of
> the TCP/CoDel system. Thus, we propose Self-tuning CoDel
> to dynamically adjust I0 for CoDel at every bottleneck link
> based on network conditions, as shown in Algorithm 2.

Of course, the big problem is that the time to respond, or RTD, is going
to be different for every communicating pair and will increase with
congestion. This seems like a pretty hard problem to solve *optimally*
and I don't see how this contributes to a solution since its model is
pretty simple compared to what is seen in the Internet today.

> In this subsection, we present ns-2 simulation results to
> demonstrate that our proposed Self-tuning CoDel can effectively
> improve the system stability and performance. We use
> TCP Reno as the source algorithm, and compare Self-tuning
> CoDel with CoDel and PIE, which are two popular modern
> AQM algorithms, in terms of the stability of queueing delay

So that's all I could find about the simulation model. It *appears* (but
I won't put words in anyone's mouth, I sure hate it when folks do that
to me) these are a bunch of "forever" Reno TCP flows. There are a lot of
really bad ns-2 TCP models out there. And it is really hard to get
simulations to resemble the traffic patterns I've seen in packet traces
from the Real World. I had to look twice to see this was published in
2018. What?

I also wonder about the notion of "stability" of queue delays. I would
expect a healthy system to have spikes in delay but not persistent
delay. But I'm willing to entertain other viewpoints.

So, there IS a lot of math I don't understand and stuff I might
understand if I took the time, so I just look at the un-mathy stuff and
try to figure out what is the purpose of this work? How does it apply?

	Kathie

Re: [Codel] self tuning codel

[Jonathan Morton]

> On 19 Jul, 2018, at 10:04 pm, Kathleen Nichols <nichols@pollere.com> wrote:
> 
>> Thus, we let a specific AQM router serve
>> as a centralized DR in the system. All routers send packet
>> dropping probability updates to DR. DR then updates its list
>> of packet dropping probabilities and sends it to all routers
> 
> Does this seem possible to anyone? There's an inherent assumption here
> that "dropping probabilities" are constant over a period of time that is
> long compared to the time to do the above. In what I've seen of traffic
> and AQMs this seems unlikely but I'm certainly not as well-informed on
> this as some people.

Based on the above, the approach seems completely wrong-headed to me.  AQM should not be centralised, but must act according to local conditions.  Certainly such a system would be impossible to deploy in a heterogeneous environment like the Internet.

>> every AQM router
>> needs to know all the packet dropping probabilities at the
>> bottleneck links in order to compute the window sizes of the
>> flows from (5).

As a first approximation, you can assume that if you are the bottleneck, nobody else on the same path is, and therefore their drop probabilities are all zero.  This assumes only that you're dealing with traffic that's responsive to congestion signals, as TCP is.  Transient conditions may exist where the assumption isn't entirely correct, but these are *only* transient.

The situation for UDP may of course be different.

 - Jonathan Morton

Re: [Codel] self tuning codel

[Andrew McGregor]

[-- Attachment #1: Type: text/plain, Size: 1580 bytes --]

So, it has a core assumption: that a stable arrangement of links with small
persistent delays is something that both can and should exist.

It's kind of like a fluid model, in many ways.

Thing is, I don't think it's desirable that persistent delays exist
anywhere.

Now, autotuning codel is probably a good idea... but the implementation
should be local. If you're a bottleneck, you may as well behave as if
you're the only bottleneck, even if that isn't the case, because if you're
in a distributed bottleneck situation your actions will help anyway. A
global distributed solver like is proposed here could possibly work in a
private network, but I can't see that solution flying in precisely the
place you really need it: peering.

One way to do this locally would be to identify the impulse response of the
stochastic DE describing the aggregate running through the link using
something like https://arxiv.org/abs/1309.7857 and then tune to optimal
behaviour for the resulting DE, along the lines of
https://arxiv.org/abs/1510.08439.


On Thu, Jul 19, 2018 at 8:42 AM Dave Taht <dave.taht@gmail.com> wrote:

> there's so much math in this that I cannot make heads or tails of it.
>
>
> https://www.eee.hku.hk/~kcleung/papers/conferences/bufferbloat_multi-bottleneck:INFOCOM_2018/PID5170809.pdf
>
> --
>
> Dave Täht
> CEO, TekLibre, LLC
> http://www.teklibre.com
> Tel: 1-669-226-2619
> _______________________________________________
> Codel mailing list
> Codel@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/codel
>

[-- Attachment #2: Type: text/html, Size: 2446 bytes --]