From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qt1-x82e.google.com (mail-qt1-x82e.google.com [IPv6:2607:f8b0:4864:20::82e]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id 4C09D3B29E for ; Thu, 29 Nov 2018 17:31:08 -0500 (EST) Received: by mail-qt1-x82e.google.com with SMTP id l11so3932795qtp.0 for ; Thu, 29 Nov 2018 14:31:08 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=1tzGc5bjpwapp55ENiviwz2frUgMHAXVjVi/5E9xSXg=; b=jAYCnFPSuoD10jC+UZns9p/rvsS4px9LUW7+qfzFIMxO7njD5Rrjf4VeTDH9c/HBc3 zBRPhGzlXBUTd84wPI6R2i83u17v8gSXyIXOluG+QS56UlRS56EHLhOTgNlS+E21KBEP /qSbeNWqTUuOnYpxFy/UrNKbWNHvZkGkGiFzl54/dUc2eLv0mFtSKSdOgySxGSxqhhxJ PXoOvyVCSxHp479V7mjo64Q5vzONFR3clHsyY6Qng+CDyZkCO/P02gdudS9vq3fPA66W ZwNfr5hFwsk8l0lhr6LBnlBJQV7s/T/b5RE1DlnSSIDqivm0YsciwCNvpOFRpKzOplWc suxA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=1tzGc5bjpwapp55ENiviwz2frUgMHAXVjVi/5E9xSXg=; b=YEz1TpfgemCXIr1th9+Zi/mBKuPFLB6s9h7nu1QAHQlIfjmIfVueB10itM9W1TxVoc ZkGYrNJzCrTUM6GRWBZA6JLxVKFxcFY91l2xBSFKed3UPY1oZ7624NF/n4E1dYQ48BKn W+f+ZU0FlyQpejmHOdUu/ZEatdn2FGaREEN9qQ9MKy0dp8qmScorFjXi+gBchge/Cuxl 1A6WMD4odozrcGObfgIdu2dHoFNpNW57G2dMZq3J+kIx5GYwuJ0nXJfIinDA+7WGVNQd NbGyPKJC9uhI6HJpLY9bWh1+7+t6KesGkuJwR8ycHaWtqG3tFCZ3/6k3VehBEkf2kVpl czOw== X-Gm-Message-State: AA+aEWbf1GZMypnfqA9EB9O6tVYZc1NkM1MrOn+MyfSra+4X3L2DTD2+ H+ZFdrRN2l7rGIHIAl7S1kXHgT9bSHdP713Rk9w= X-Google-Smtp-Source: AFSGD/VuJQeFGU3EFlFY64tAQJggNzPWonezLVd39ApPFALeRxY+eSmIzbyxTOMlkqumY4Kya9wj+BawdaxvG593Txg= X-Received: by 2002:ac8:85d:: with SMTP id x29mr3239542qth.379.1543530667675; Thu, 29 Nov 2018 14:31:07 -0800 (PST) MIME-Version: 1.0 References: <65EAC6C1-4688-46B6-A575-A6C7F2C066C5@heistp.net> In-Reply-To: From: Luca Muscariello Date: Thu, 29 Nov 2018 23:30:55 +0100 Message-ID: To: mario.hock@kit.edu, "Bless, Roland (TM)" , bloat Content-Type: multipart/alternative; boundary="00000000000025940c057bd53d9e" Subject: Re: [Bloat] when does the CoDel part of fq_codel help in the real world? X-BeenThere: bloat@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: General list for discussing Bufferbloat List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 29 Nov 2018 22:31:08 -0000 --00000000000025940c057bd53d9e Content-Type: text/plain; charset="UTF-8" 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 is designed in a way that t is (almost) > synchronized among the competing flows.) > > Generally, other ways of determining a suitable X(t) are conceivable. In > our approach X(t) is a monotonically increasing function, but it is > regularly reset as LoLa cycles between its states; i.e., after a queuing > delay of 5ms is reached, the queue is drained and everything starts > again. (Thus, the timespan where X(t) is monotonically increased is > called a "round of fair flow balancing".) > > This way we can overcome the constraint given in [1]: > > """ > THEOREM 6 (FAIRNESS/DELAY TRADEOFF). For congestion control mechanisms > that have steady state throughput of the kind R = f(d, p), for some > function f, delay d and feedback p, if the feedback is based on purely > end to end delay measurements, you can either have fairness or a fixed > delay, but not both simultaneously > """ > > [1] "ECN or Delay: Lessons Learnt from Analysis of DCQCN and TIMELY" > Yibo Zhu et al., https://dl.acm.org/citation.cfm?id=2999593 > > Best, Mario > > > Am 29.11.18 um 17:09 schrieb Luca Muscariello: > > Hi Roland, > > > > It took me quite a lot of time to find this message in the thread... > > I read the paper you sent and I guess this is the first of a series as > > many things stay uncovered. > > > > Just a quick question: why is X(t) always increasing with t? > > > > > > On Tue, Nov 27, 2018 at 11:26 AM Bless, Roland (TM) > > > wrote: > > > > Hi Luca, > > > > Am 27.11.18 um 10:24 schrieb Luca Muscariello: > > > A congestion controlled protocol such as TCP or others, including > > QUIC, > > > LEDBAT and so on > > > need at least the BDP in the transmission queue to get full link > > > efficiency, i.e. the queue never empties out. > > > > This is not true. There are congestion control algorithms > > (e.g., TCP LoLa [1] or BBRv2) that can fully utilize the bottleneck > link > > capacity without filling the buffer to its maximum capacity. The BDP > > rule of thumb basically stems from the older loss-based congestion > > control variants that profit from the standing queue that they built > > over time when they detect a loss: > > while they back-off and stop sending, the queue keeps the bottleneck > > output busy and you'll not see underutilization of the link. > Moreover, > > once you get good loss de-synchronization, the buffer size > requirement > > for multiple long-lived flows decreases. > > > > > This gives rule of thumbs to size buffers which is also very > > practical > > > and thanks to flow isolation becomes very accurate. > > > > The positive effect of buffers is merely their role to absorb > > short-term bursts (i.e., mismatch in arrival and departure rates) > > instead of dropping packets. One does not need a big buffer to > > fully utilize a link (with perfect knowledge you can keep the link > > saturated even without a single packet waiting in the buffer). > > Furthermore, large buffers (e.g., using the BDP rule of thumb) > > are not useful/practical anymore at very high speed such as 100 > Gbit/s: > > memory is also quite costly at such high speeds... > > > > Regards, > > Roland > > > > [1] M. Hock, F. Neumeister, M. Zitterbart, R. Bless. > > TCP LoLa: Congestion Control for Low Latencies and High Throughput. > > Local Computer Networks (LCN), 2017 IEEE 42nd Conference on, pp. > > 215-218, Singapore, Singapore, October 2017 > > http://doc.tm.kit.edu/2017-LCN-lola-paper-authors-copy.pdf > > > > > Which is: > > > > > > 1) find a way to keep the number of backlogged flows at a > > reasonable value. > > > This largely depends on the minimum fair rate an application may > > need in > > > the long term. > > > We discussed a little bit of available mechanisms to achieve that > > in the > > > literature. > > > > > > 2) fix the largest RTT you want to serve at full utilization and > size > > > the buffer using BDP * N_backlogged. > > > Or the other way round: check how much memory you can use > > > in the router/line card/device and for a fixed N, compute the > largest > > > RTT you can serve at full utilization. > > > > > > 3) there is still some memory to dimension for sparse flows in > > addition > > > to that, but this is not based on BDP. > > > It is just enough to compute the total utilization of sparse > > flows and > > > use the same simple model Toke has used > > > to compute the (de)prioritization probability. > > > > > > This procedure would allow to size FQ_codel but also SFQ. > > > It would be interesting to compare the two under this buffer > sizing. > > > It would also be interesting to compare another mechanism that we > > have > > > mentioned during the defense > > > which is AFD + a sparse flow queue. Which is, BTW, already > > available in > > > Cisco nexus switches for data centres. > > > > > > I think that the the codel part would still provide the ECN > feature, > > > that all the others cannot have. > > > However the others, the last one especially can be implemented in > > > silicon with reasonable cost. > > > > > > _______________________________________________ > > Bloat mailing list > > Bloat@lists.bufferbloat.net > > https://lists.bufferbloat.net/listinfo/bloat > > > --00000000000025940c057bd53d9e Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
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 eq= ual to the link capacity.
The input rate can be instantaneously b= elow or above the link capacity.
Even If the link is never idle a= nd the output rate is always C for all t.

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

This theorem can be valid only if the input rate of a que= ue 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=C2=A0
at the link. So to conclude,=C2=A0 this th= eorem if valid iff input =3D=3D output rate then the queue is always zero, = i.e.=C2=A0 d=3D0.

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




On Thu, Nov 29, 2018 at 6:07 P= M Mario Hock <mario.hock@kit.edu> 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&qu= ot; 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 is designed in a way that t is (almost)
synchronized among the competing flows.)

Generally, other ways of determining a suitable X(t) are conceivable. In our approach X(t) is a monotonically increasing function, but it is
regularly reset as LoLa cycles between its states; i.e., after a queuing delay of 5ms is reached, the queue is drained and everything starts
again. (Thus, the timespan where X(t) is monotonically increased is
called a "round of fair flow balancing".)

This way we can overcome the constraint given in [1]:

"""
THEOREM 6 (FAIRNESS/DELAY TRADEOFF). For congestion control mechanisms
that have steady state throughput of the kind R =3D f(d, p), for some
function f, delay d and feedback p, if the feedback is based on purely
end to end delay measurements, you can either have fairness or a fixed
delay, but not both simultaneously
"""

[1] "ECN or Delay: Lessons Learnt from Analysis of DCQCN and TIMELY&qu= ot;
Yibo Zhu et al., https://dl.acm.org/citation.cfm?id=3D29= 99593

Best, Mario


Am 29.11.18 um 17:09 schrieb Luca Muscariello:
> Hi Roland,
>
> It took me quite a lot of time to find this message in the thread... > I read the paper you sent and I guess this is the first of a series as=
> many things stay uncovered.
>
> Just a quick question: why is X(t) always increasing with=C2=A0 t?
>
>
> On Tue, Nov 27, 2018 at 11:26 AM Bless, Roland (TM)
> <roland.b= less@kit.edu <mailto:roland.bless@kit.edu>> wrote:
>
>=C2=A0 =C2=A0 =C2=A0Hi Luca,
>
>=C2=A0 =C2=A0 =C2=A0Am 27.11.18 um 10:24 schrieb Luca Muscariello:
>=C2=A0 =C2=A0 =C2=A0 > A congestion controlled protocol such as TCP = or others, including
>=C2=A0 =C2=A0 =C2=A0QUIC,
>=C2=A0 =C2=A0 =C2=A0 > LEDBAT and so on
>=C2=A0 =C2=A0 =C2=A0 > need at least the BDP in the transmission que= ue to get full link
>=C2=A0 =C2=A0 =C2=A0 > efficiency, i.e. the queue never empties out.=
>
>=C2=A0 =C2=A0 =C2=A0This is not true. There are congestion control algo= rithms
>=C2=A0 =C2=A0 =C2=A0(e.g., TCP LoLa [1] or BBRv2) that can fully utiliz= e the bottleneck link
>=C2=A0 =C2=A0 =C2=A0capacity without filling the buffer to its maximum = capacity. The BDP
>=C2=A0 =C2=A0 =C2=A0rule of thumb basically stems from the older loss-b= ased congestion
>=C2=A0 =C2=A0 =C2=A0control variants that profit from the standing queu= e that they built
>=C2=A0 =C2=A0 =C2=A0over time when they detect a loss:
>=C2=A0 =C2=A0 =C2=A0while they back-off and stop sending, the queue kee= ps the bottleneck
>=C2=A0 =C2=A0 =C2=A0output busy and you'll not see underutilization= of the link. Moreover,
>=C2=A0 =C2=A0 =C2=A0once you get good loss de-synchronization, the buff= er size requirement
>=C2=A0 =C2=A0 =C2=A0for multiple long-lived flows decreases.
>
>=C2=A0 =C2=A0 =C2=A0 > This gives rule of thumbs to size buffers whi= ch is also very
>=C2=A0 =C2=A0 =C2=A0practical
>=C2=A0 =C2=A0 =C2=A0 > and thanks to flow isolation becomes very acc= urate.
>
>=C2=A0 =C2=A0 =C2=A0The positive effect of buffers is merely their role= to absorb
>=C2=A0 =C2=A0 =C2=A0short-term bursts (i.e., mismatch in arrival and de= parture rates)
>=C2=A0 =C2=A0 =C2=A0instead of dropping packets. One does not need a bi= g buffer to
>=C2=A0 =C2=A0 =C2=A0fully utilize a link (with perfect knowledge you ca= n keep the link
>=C2=A0 =C2=A0 =C2=A0saturated even without a single packet waiting in t= he buffer).
>=C2=A0 =C2=A0 =C2=A0Furthermore, large buffers (e.g., using the BDP rul= e of thumb)
>=C2=A0 =C2=A0 =C2=A0are not useful/practical anymore at very high speed= such as 100 Gbit/s:
>=C2=A0 =C2=A0 =C2=A0memory is also quite costly at such high speeds...<= br> >
>=C2=A0 =C2=A0 =C2=A0Regards,
>=C2=A0 =C2=A0 =C2=A0 =C2=A0Roland
>
>=C2=A0 =C2=A0 =C2=A0[1] M. Hock, F. Neumeister, M. Zitterbart, R. Bless= .
>=C2=A0 =C2=A0 =C2=A0TCP LoLa: Congestion Control for Low Latencies and = High Throughput.
>=C2=A0 =C2=A0 =C2=A0Local Computer Networks (LCN), 2017 IEEE 42nd Confe= rence on, pp.
>=C2=A0 =C2=A0 =C2=A0215-218, Singapore, Singapore, October 2017
>=C2=A0 =C2=A0 =C2=A0http://doc.tm.kit.= edu/2017-LCN-lola-paper-authors-copy.pdf
>
>=C2=A0 =C2=A0 =C2=A0 > Which is:
>=C2=A0 =C2=A0 =C2=A0 >
>=C2=A0 =C2=A0 =C2=A0 > 1) find a way to keep the number of backlogge= d flows at a
>=C2=A0 =C2=A0 =C2=A0reasonable value.
>=C2=A0 =C2=A0 =C2=A0 > This largely depends on the minimum fair rate= an application may
>=C2=A0 =C2=A0 =C2=A0need in
>=C2=A0 =C2=A0 =C2=A0 > the long term.
>=C2=A0 =C2=A0 =C2=A0 > We discussed a little bit of available mechan= isms to achieve that
>=C2=A0 =C2=A0 =C2=A0in the
>=C2=A0 =C2=A0 =C2=A0 > literature.
>=C2=A0 =C2=A0 =C2=A0 >
>=C2=A0 =C2=A0 =C2=A0 > 2) fix the largest RTT you want to serve at f= ull utilization and size
>=C2=A0 =C2=A0 =C2=A0 > the buffer using BDP * N_backlogged.
>=C2=A0 =C2=A0 =C2=A0 > Or the other way round: check how much memory= you can use
>=C2=A0 =C2=A0 =C2=A0 > in the router/line card/device and for a fixe= d N, compute the largest
>=C2=A0 =C2=A0 =C2=A0 > RTT you can serve at full utilization.
>=C2=A0 =C2=A0 =C2=A0 >
>=C2=A0 =C2=A0 =C2=A0 > 3) there is still some memory to dimension fo= r sparse flows in
>=C2=A0 =C2=A0 =C2=A0addition
>=C2=A0 =C2=A0 =C2=A0 > to that, but this is not based on BDP.
>=C2=A0 =C2=A0 =C2=A0 > It is just enough to compute the total utiliz= ation of sparse
>=C2=A0 =C2=A0 =C2=A0flows and
>=C2=A0 =C2=A0 =C2=A0 > use the same simple model Toke has used
>=C2=A0 =C2=A0 =C2=A0 > to compute the (de)prioritization probability= .
>=C2=A0 =C2=A0 =C2=A0 >
>=C2=A0 =C2=A0 =C2=A0 > This procedure would allow to size FQ_codel b= ut also SFQ.
>=C2=A0 =C2=A0 =C2=A0 > It would be interesting to compare the two un= der this buffer sizing.
>=C2=A0 =C2=A0 =C2=A0 > It would also be interesting to compare anoth= er mechanism that we
>=C2=A0 =C2=A0 =C2=A0have
>=C2=A0 =C2=A0 =C2=A0 > mentioned during the defense
>=C2=A0 =C2=A0 =C2=A0 > which is AFD=C2=A0+ a sparse flow queue. Whic= h is, BTW, already
>=C2=A0 =C2=A0 =C2=A0available in
>=C2=A0 =C2=A0 =C2=A0 > Cisco nexus switches for data centres.
>=C2=A0 =C2=A0 =C2=A0 >
>=C2=A0 =C2=A0 =C2=A0 > I think that the the codel part would still p= rovide the ECN feature,
>=C2=A0 =C2=A0 =C2=A0 > that all the others cannot have.
>=C2=A0 =C2=A0 =C2=A0 > However the others, the last one especially c= an be implemented in
>=C2=A0 =C2=A0 =C2=A0 > silicon with reasonable cost.
>
>
> _______________________________________________
> Bloat mailing list
> Bloat= @lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/bloat >
--00000000000025940c057bd53d9e--