Re: [Bloat] when does the CoDel part of fq_codel help in the real world?

[Stephen Hemminger]

On Fri, 30 Nov 2018 06:51:34 +0100 (CET)
Mikael Abrahamsson  wrote:

> On Thu, 29 Nov 2018, Stephen Hemminger wrote:
> 
> > The problem is that any protocol is mostly blind to the underlying 
> > network (and that can change).  To use dave's analogy it is like being 
> > put in the driver seat of a vehicle blind folded.  When you step on the 
> > gas you don't know if it is a dragster, jet fighter, or a soviet 
> > tractor. The only way a protocol can tell is based on the perceived 
> > inertia and when it runs into things...  
> 
> Actually, I've made the argument to IETF TCPM that this is not true. You 
> can be able to communicate earlier data from previous flows on the same 
> connection so that new flows can re-learn this.
> 
> If no flow the past hour has been able to run faster than 1 megabit/s and 
> always PMTUD to 1460 bytes MTU outbound, then there is good chance that 
> the next flow will encounter the same thing. Why not use this information 
> when guessing how things will behave going forward?
> 

Since a majority of the flows in the world are coming from mobile, this both
makes sense but is hard.  Linux used to remember TCP metrics but this was
removed with the flow cache.
___
Bloat mailing list
Bloat@lists.bufferbloat.net
https://lists.bufferbloat.net/listinfo/bloat

Re: [Bloat] when does the CoDel part of fq_codel help in the real world?

[Dave Taht]

On Thu, Nov 29, 2018 at 9:51 PM Mikael Abrahamsson  wrote:
>
> On Thu, 29 Nov 2018, Stephen Hemminger wrote:
>
> > The problem is that any protocol is mostly blind to the underlying
> > network (and that can change).  To use dave's analogy it is like being
> > put in the driver seat of a vehicle blind folded.  When you step on the
> > gas you don't know if it is a dragster, jet fighter, or a soviet
> > tractor. The only way a protocol can tell is based on the perceived
> > inertia and when it runs into things...
>
> Actually, I've made the argument to IETF TCPM that this is not true. You
> can be able to communicate earlier data from previous flows on the same
> connection so that new flows can re-learn this.
>
> If no flow the past hour has been able to run faster than 1 megabit/s and
> always PMTUD to 1460 bytes MTU outbound, then there is good chance that
> the next flow will encounter the same thing. Why not use this information
> when guessing how things will behave going forward?

I've actually assumed that the insanely big providers actually did
this, that they did a lookup on connect into BGP ASN database (aha!
this address is 4G, This is DSL, This may be wifi, this one is weird).
Keeping a few bits of state around awhile for every ipv4 address in
the world today is trivial with today's technologies.

>
> --
> Mikael Abrahamssonemail: swm...@swm.pp.se
> ___
> Bloat mailing list
> Bloat@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/bloat



-- 

Dave Täht
CTO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-831-205-9740
___
Bloat mailing list
Bloat@lists.bufferbloat.net
https://lists.bufferbloat.net/listinfo/bloat

Re: [Bloat] when does the CoDel part of fq_codel help in the real world?

[jf]

>>If I can restate that in a more concrete way: the queue may not drain at a 
>>smooth, constant rate.  There are several real-world link technologies which 
>>exhibit this behaviour - wifi and DOCSIS come to mind, not to mention 3G/4G 
>>with variable signal strength.

This!  

Also, bottlenecks can move, such as when a DSLAMs backhaul reaches saturation 
for minutes/hours in the evenings as everyone tries to stream, and end-point 
connections drop to less than 50% of the local sync-rate worth of effective 
capacity.
Therefore AQM settings about link capacity should be thought of as a Max not 
necessarily current link capacity.

BTW- Amazing discussion, loving it.

Jonathan Foulkes

-Original Message-
From: Bloat  On Behalf Of Jonathan Morton
Sent: Friday, November 30, 2018 6:05 AM
To: Luca Muscariello 
Cc: bloat 
Subject: Re: [Bloat] when does the CoDel part of fq_codel help in the real 
world?

> On 30 Nov, 2018, at 12:32 pm, Luca Muscariello  
> wrote:
> 
> Two last comments: one should always used fluid approximation with 
> care, because they are approximations, the real model is more complex. Nobody 
> considers that the RTT varies during the connection lifetime and that ACK can 
> be delayed.
> So CWD increases in a non simple way.

If I can restate that in a more concrete way: the queue may not drain at a 
smooth, constant rate.  There are several real-world link technologies which 
exhibit this behaviour - wifi and DOCSIS come to mind, not to mention 3G/4G 
with variable signal strength.

 - Jonathan Morton

___
Bloat mailing list
Bloat@lists.bufferbloat.net
https://lists.bufferbloat.net/listinfo/bloat

___
Bloat mailing list
Bloat@lists.bufferbloat.net
https://lists.bufferbloat.net/listinfo/bloat

Re: [Bloat] when does the CoDel part of fq_codel help in the real world?

[Jonathan Morton]

> On 30 Nov, 2018, at 12:32 pm, Luca Muscariello  
> wrote:
> 
> Two last comments: one should always used fluid approximation with care, 
> because they are approximations, 
> the real model is more complex. Nobody considers that the RTT varies during 
> the connection lifetime and that ACK can be delayed.
> So CWD increases in a non simple way.

If I can restate that in a more concrete way: the queue may not drain at a 
smooth, constant rate.  There are several real-world link technologies which 
exhibit this behaviour - wifi and DOCSIS come to mind, not to mention 3G/4G 
with variable signal strength.

 - Jonathan Morton

___
Bloat mailing list
Bloat@lists.bufferbloat.net
https://lists.bufferbloat.net/listinfo/bloat

Re: [Bloat] when does the CoDel part of fq_codel help in the real world?

[Luca Muscariello]

Mario,

agreed.
Two last comments: one should always used fluid approximation with care,
because they are approximations,
the real model is more complex. Nobody considers that the RTT varies during
the connection lifetime and that ACK can be delayed.
So CWD increases in a non simple way.

This is one paper I wrote some time ago where you can get to an equilibrium
with a desired epsilon in the queue.
This protocol and LoLa seem to have similar objectives.

https://arxiv.org/pdf/1010.5623.pdf

Equations and stability conditions are worth a read. Maybe the equations
can be reused for LoLa. As you seem doing something similar,
even if the X(t) introduces non regularities which cannot  be modelled in a
simple way. Maybe yes.

In another work

G. Carofiglio and L. Muscariello, "On the Impact of TCP and Per-Flow
Scheduling on Internet Performance,"
in *IEEE/ACM Transactions on Networking*, vol. 20, no. 2, pp. 620-633,
April 2012.
https://doi.org/10.1109/TNET.2011.2164553

I, my co-author actually, did the calculations nobody wants to do to obtain
the limit cycle which is pretty messy.
They are all fluid approximations. So in practice the target queuing
latency can be larger or smaller.
These models are useful to get a preliminary idea about how the system
works and a publication...




On Fri, Nov 30, 2018 at 10:55 AM Mario Hock  wrote:

> Luca,
>
> I'm not that happy with the theorem either, since it stresses a
> limitation that can actually be overcome. However, I quoted it to
> demonstrate there is a challenge involved.
>
> In my point of view there is actually a subtle thing that's often lost
> when modeling the queue based on input rates, output rates, and, e.g.,
> queuing theory. The inflight data (e.g., controlled by the CWnds) and
> the resulting standing queue. But this standing queue is (probably) the
> major reasoning behind LoLa and CoDel.
>
> Let's simplify the situation to single sender, to ease the explanation.
> (Also holds for multiple senders.) Let the sender have a CWnd-based
> congestion control, but let's fix this CWnd for now. Also, let's assume
> the CWnd is larger than the BDP (without queuing delay); CWnd = BDP + x.
>
> In this case, the sending rate will be above the bottleneck rate, as
> long as less than x is queued at the bottleneck. This increases the
> queue. As soon as x is queued at the bottleneck, the sending rate will
> (exactly) approach the bottleneck rate. The reason is, that the BDP
> (with buffering) will now be exactly equal to the CWnd (since the RTT is
> increased).
>
> This means, a standing queue will build up. But as soon as it's there,
> sending rate will (on average) be equal to the bottleneck rate.
>
> There is also a stability condition here. If the queuing delay (for some
> reason) falls below x/rate (i.e., amount of queuing falls below x), the
> sending rate increases. If the queuing delay raises above x/rate,
> sending rate is reduced. Note: That this is all with a fixed CWnd. No
> interaction of the congestion control algorithms involved here.
>
> Therefore, there can be a long living standing queue, even if input ==
> output. Of course during the build up process input > output, however
> this build up can e.g. happen in one RTT, while the standing queue can
> survive seconds or minutes (in reality, and indefinitely in theory).
> Though, I found that this correlation is often not modeled in
> queue-theoretical models.
>
> Best, Mario
>
>
> Am 29.11.18 um 23:30 schrieb Luca Muscariello:
> > Mario,
> >
> > putting aside LoLa for a second,
> > I'm not quite sure that the theorem you cite is valid.
> >
> > According to the model R_i is the sending rate.
> > The sum across all flows bottlenecked at the link does not need to be
> > equal to the link capacity.
> > The input rate can be instantaneously below or above the link capacity.
> > Even If the link is never idle and the output rate is always C for all t.
> >
> > If the sum_i R_i = C is false because of what I said, than p_i which is
> > nothing more than
> > the shadow price of the link capacity constraint, can be a function of a
> > constant delay d, i.e. p_i = cost * d for all i.
> >
> > This theorem can be valid only if the input rate of a queue is
> > instantaneously equal to the output queue.
> > We all know that a queue exists just because there is an instantaneous
> > difference of input and output rates
> > at the link. So to conclude,  this theorem if valid iff input == output
> > rate then the queue is always zero, i.e.  d=0.
> >
> > The theorem is either an artefact of the model or just wrong. Or I'm
> > missing something...
> >
> >
> >
> >
> >
> >
> > On Thu, Nov 29, 2018 at 6:07 PM Mario Hock  > > wrote:
> >
> > Hi Luca,
> >
> > I'm answering on behalf of Roland, since I am a co-author of the
> paper.
> >
> > This is an excellent question, since it goes right at the heart of
> how
> > LoLa works.
> >
> > Indeed, the paper is a first of a series. A se

Re: [Bloat] when does the CoDel part of fq_codel help in the real world?

[Mario Hock]

Luca,

I'm not that happy with the theorem either, since it stresses a 
limitation that can actually be overcome. However, I quoted it to 
demonstrate there is a challenge involved.


In my point of view there is actually a subtle thing that's often lost 
when modeling the queue based on input rates, output rates, and, e.g., 
queuing theory. The inflight data (e.g., controlled by the CWnds) and 
the resulting standing queue. But this standing queue is (probably) the 
major reasoning behind LoLa and CoDel.


Let's simplify the situation to single sender, to ease the explanation. 
(Also holds for multiple senders.) Let the sender have a CWnd-based 
congestion control, but let's fix this CWnd for now. Also, let's assume 
the CWnd is larger than the BDP (without queuing delay); CWnd = BDP + x.


In this case, the sending rate will be above the bottleneck rate, as 
long as less than x is queued at the bottleneck. This increases the 
queue. As soon as x is queued at the bottleneck, the sending rate will 
(exactly) approach the bottleneck rate. The reason is, that the BDP 
(with buffering) will now be exactly equal to the CWnd (since the RTT is 
increased).


This means, a standing queue will build up. But as soon as it's there, 
sending rate will (on average) be equal to the bottleneck rate.


There is also a stability condition here. If the queuing delay (for some 
reason) falls below x/rate (i.e., amount of queuing falls below x), the 
sending rate increases. If the queuing delay raises above x/rate, 
sending rate is reduced. Note: That this is all with a fixed CWnd. No 
interaction of the congestion control algorithms involved here.


Therefore, there can be a long living standing queue, even if input == 
output. Of course during the build up process input > output, however 
this build up can e.g. happen in one RTT, while the standing queue can 
survive seconds or minutes (in reality, and indefinitely in theory). 
Though, I found that this correlation is often not modeled in 
queue-theoretical models.


Best, Mario


Am 29.11.18 um 23:30 schrieb Luca Muscariello:

Mario,

putting aside LoLa for a second,
I'm not quite sure that the theorem you cite is valid.

According to the model R_i is the sending rate.
The sum across all flows bottlenecked at the link does not need to be 
equal to the link capacity.

The input rate can be instantaneously below or above the link capacity.
Even If the link is never idle and the output rate is always C for all t.

If the sum_i R_i = C is false because of what I said, than p_i which is 
nothing more than
the shadow price of the link capacity constraint, can be a function of a 
constant delay d, i.e. p_i = cost * d for all i.


This theorem can be valid only if the input rate of a queue is 
instantaneously equal to the output queue.
We all know that a queue exists just because there is an instantaneous 
difference of input and output rates
at the link. So to conclude,  this theorem if valid iff input == output 
rate then the queue is always zero, i.e.  d=0.


The theorem is either an artefact of the model or just wrong. Or I'm 
missing something...







On Thu, Nov 29, 2018 at 6:07 PM Mario Hock > wrote:


Hi Luca,

I'm answering on behalf of Roland, since I am a co-author of the paper.

This is an excellent question, since it goes right at the heart of how
LoLa works.

Indeed, the paper is a first of a series. A second one, looking deeper
into the fair flow balancing mechanism, is currently under submission.

Similar as other delay based congestion controls, LoLa tries to achieve
fairness by allowing each flow to buffer the same amount of data at the
bottleneck. We have this, e.g., in TCP Vegas, and (in a way) also in
Copa (a recently proposed congestion control) and many others. If this
is achieved, we get flow rate fairness independent of a flow's RTT.

Usually (in other congestion controls) this "allowed amount of data" is
fixed per flow. We presume that this approach does not scale well to
high speed networks. Since the queuing delay resulting from this amount
of data is reduced with increasing bottleneck rate. Thus, it becomes
harder to measure it right. This can easily be seen (and proven) for
TCP
Vegas.

Note: Just using higher fixed values is not an option, since it would
not work at lower speeds anymore and also not with a large number of
flows.

Therefore, LoLa tries to find a suitable value for the "allowed amount
of data" dynamically. This is X(t).

Our approach is to grow X(t) over time during the Fair Flow Balancing
phase. This phase ends when the queuing delay reaches 5ms. Thus, (in
the
ideal case) at the end of Fair Flow Balancing, X(t) is just as large
that all flows at bottleneck create a queuing delay of 5ms, and all
flows contribute equally to this queue. Hence, flow rate fairness is
achieved. (Note that LoLa