[Codel] why RED is not considered as a solution to bufferbloat.

[Codel] why RED is not considered as a solution to bufferbloat.

[sahil grover]

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

(i) First of all,i want to know whether RED was implemented or not?
if not then what were the reasons(major) ?
anyone please tell me in simple words here only,because i don't want to
read any paper like "RED in a different light".

(ii)Second, as we all know RED controls the  average queue size from
growing.
So it also controls delay in a way or  we can say  is a solution to
bufferbloat problem. Then why it was not considered.

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

Re: [Codel] why RED is not considered as a solution to bufferbloat.

[Jonathan Morton]

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

Simply put, RED is a very old algorithm, one of the first viable AQM
algorithms. However, it proved to be so difficult to configure properly
that almost nobody uses it, even though many carrier grade routers
implement it.

Codel not only performs better than an ideally configured RED, but is far
easier to configure. This makes it much more deployable.

- Jonathan Morton

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

Re: [Codel] why RED is not considered as a solution to bufferbloat.

[sahil grover]

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

So we can say Codel is better than other AQM???

On Tue, Feb 24, 2015 at 9:24 PM, Jonathan Morton <chromatix99@gmail.com>
wrote:

> Simply put, RED is a very old algorithm, one of the first viable AQM
> algorithms. However, it proved to be so difficult to configure properly
> that almost nobody uses it, even though many carrier grade routers
> implement it.
>
> Codel not only performs better than an ideally configured RED, but is far
> easier to configure. This makes it much more deployable.
>
> - Jonathan Morton
>

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

Re: [Codel] why RED is not considered as a solution to bufferbloat.

[Jonathan Morton]

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

Most of us on this list believe that to be true, in many cases after
performing experiments ourselves, or at least looking through data
generated by others' experiments.

However, if as I suspect you are investigating various AQM algorithms as
part of your education, you should probably examine the data yourselves and
come to your own conclusions. You may even get extra credit for being able
to describe the difference between AQM and Fair Queuing, and how they can
be combined (as in fq_codel) to give the benefits of both types in one go.
But for that, you ARE going to need to read some boring papers like "RED in
a different light".

- Jonathan Morton

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

Re: [Codel] why RED is not considered as a solution to bufferbloat.

[Dave Taht]

On Tue, Feb 24, 2015 at 8:32 AM, Jonathan Morton <chromatix99@gmail.com> wrote:
> Most of us on this list believe that to be true, in many cases after
> performing experiments ourselves, or at least looking through data generated
> by others' experiments.
>
> However, if as I suspect you are investigating various AQM algorithms as
> part of your education, you should probably examine the data yourselves and
> come to your own conclusions. You may even get extra credit for being able
> to describe the difference between AQM and Fair Queuing, and how they can be
> combined (as in fq_codel) to give the benefits of both types in one go. But
> for that, you ARE going to need to read some boring papers like "RED in a
> different light".

It is not particularly easy to keep up with the onslought of AQM
literature since the bufferbloat effort started, but a review of stuff
since 2011, or even as late at 2013 via google scholar should be
illuminating. Many papers use RED as a reference, but nearly all of
them miss the major points in the original bufferbloat experiments.
Those experiment, long ago documented on Jim´s earliest writings on
the subject, available in video form, in various papers etc. One
example:

https://gettys.wordpress.com/2012/02/01/bufferbloat-demonstration-videos/

where jim performed an upload and a ping, at the same time, on a
network optimized for downloads and and obviously not tested for
uploads. The later rrul test suite (in netperf-wrapper, open source,
anybody can use it, and I really wish they did) was designed to
exercise both directions of the link with tcp data, and do a latency
measurement, at the same time.

Either experiment is consistently not replicated by experimenters *to
date*, it frustrates me, and the only thing that gives hope is the
slow progress in science of resolving the problems in this experiment:

http://en.wikipedia.org/wiki/Oil_drop_experiment#Millikan.27s_experiment_as_an_example_of_psychological_effects_in_scientific_methodology

But I am not willing to wait 70 years to get it all sorted out!

The core observation I have is :

Drop tail queues and AQMs do not do well in the face of cross traffic,
(a mixture of small ack packets and larger data packets at saturating
loads). This is apparently one of those problems that most aqm-ers
(but not van and kathie!) wish to sweep under the rug, as if having a
car that can steer on a downhill run only, was acceptable and safe to
society at large.

I made for-damn-sure that there was a rrul-like test for that scenario
in the ns3 code now being mainlined, in the hope that new
experimenters and designers of new algorithms would rigorously test
for circumstances with cross traffic. I think I should also have got
around to doing one in ns2.

Moving on, codel was co-designed by the RED guy - van jacobson - and
if you don´t  believe him when he explains how RED was flawed, please
stay away from my networks.

http://www.pollere.net/Pdfdocs/QrantJul06.pdf

There is no information in average queue length.

The whole story about red in a different light, is sad and amusing at
the same time, when someone finds he has made a mistake, and tries to
retract it, and cant get published, and the pile on and noise level
since by folk since writing RED related papers, even since we managed
to get the correctly contradictory information on RED out there, is
annoying.

If *all* future aqm oriented papers made sure to address the
cross-traffic problem - that  mixture of big and small packets under
saturating loads - with their latest-aqm-idea-de-jure as part of their
*core criteria for worthiness* - it would be a better world.

While I certainly believe that you can make an AQM that works better
with cross traffic - and actually have some revisions for codel that
do so -

You cannot predict the traffic load or traffic types going in either
direction in most environments and thus you *must* handle it at peak
load in both directions, well, in order to have a deployable solution.
For all the aqm-related papers of DASH and web traffic down, there are
nearly none that test torrent/scp/dropbox or videoconferencing traffic
up, at the same time. I would like to be in a world where I could
refuse to read any paper that did not address the cross traffic
problem, AND such papers were summarily rejected before publication.

So, thus, codel is a AQM that combines well with FQ, unlike all other
AQMs published to date - and nearly nobody that uses it, uses it
without also doing FQ.

As it is, fq_codel is deploying rapidly across the edge where it was
designed to go, and I see nearly no implementations of RED in the
field from extensive talks with operators and firmware makers around
the world. *None*, in my last poll at the New Zealand network
operators group meeting.

Some form of fair queuing, on the other hand, was deployed by over 1/3
the network operators there. (Convincing advocates of FQ that AQM is
also needed, has often been a frustrating exercise as well!)

Lastly, if you have trouble reading english, there is always google translate.


> - Jonathan Morton
>
>
> _______________________________________________
> Codel mailing list
> Codel@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/codel
>



-- 
Dave Täht
Let's make wifi fast, less jittery and reliable again!

https://plus.google.com/u/0/107942175615993706558/posts/TVX3o84jjmb

Re: [Codel] why RED is not considered as a solution to bufferbloat.

[Dave Taht]

and I meant to mention my other big kvetch...

Nearly no paper tests an asymmetric network, where upload speeds are a
fraction of the download speeds. This leads to acks dominating
upstream traffic, and A) a big upload is starved, or B) that upload
acks starves the download by a providers desparate attempts to
optimize - the combination of any traffic accros sthat link gets
subject to crazy ideas like ack prioritization and other scenarios
that break other forms of traffic.

As this is actually how the edge of the internet is deployed - DSL has
ratios of 6 and even 20 to 1, cable modems are in the range of 6 and
10 to 1, the only technology that is symmetric is fiber - it totally
boggles my mind that this is not also the standard benchmark test of
an aqm or fq algorithm.

The lack of an asymmetric network test should also be a fundamental
bar to publication of any new paper on the AQM or FQ subjects.

So we fixed that, in creating ns3 tests as well. It turned out to be
hard to do, we had a ton of bugs to sort out in the code (now mostly
done except for getting fq_codel itself mainlined) and I have no idea
if ns2 has the same problems or not, but it certainly explains why so
little in the liturature actually sees the real problems.

And lastly - on another subject entirely - no aqm we know of yet is
correctly structured to deal with the taxi-stand topology half duplex
nature of wifi and wireless, and no sim I have yet tried looks
anything like measured reality.

we're working on it.

On Tue, Feb 24, 2015 at 10:00 AM, Dave Taht <dave.taht@gmail.com> wrote:
> On Tue, Feb 24, 2015 at 8:32 AM, Jonathan Morton <chromatix99@gmail.com> wrote:
>> Most of us on this list believe that to be true, in many cases after
>> performing experiments ourselves, or at least looking through data generated
>> by others' experiments.
>>
>> However, if as I suspect you are investigating various AQM algorithms as
>> part of your education, you should probably examine the data yourselves and
>> come to your own conclusions. You may even get extra credit for being able
>> to describe the difference between AQM and Fair Queuing, and how they can be
>> combined (as in fq_codel) to give the benefits of both types in one go. But
>> for that, you ARE going to need to read some boring papers like "RED in a
>> different light".
>
> It is not particularly easy to keep up with the onslought of AQM
> literature since the bufferbloat effort started, but a review of stuff
> since 2011, or even as late at 2013 via google scholar should be
> illuminating. Many papers use RED as a reference, but nearly all of
> them miss the major points in the original bufferbloat experiments.
> Those experiment, long ago documented on Jim´s earliest writings on
> the subject, available in video form, in various papers etc. One
> example:
>
> https://gettys.wordpress.com/2012/02/01/bufferbloat-demonstration-videos/
>
> where jim performed an upload and a ping, at the same time, on a
> network optimized for downloads and and obviously not tested for
> uploads. The later rrul test suite (in netperf-wrapper, open source,
> anybody can use it, and I really wish they did) was designed to
> exercise both directions of the link with tcp data, and do a latency
> measurement, at the same time.
>
> Either experiment is consistently not replicated by experimenters *to
> date*, it frustrates me, and the only thing that gives hope is the
> slow progress in science of resolving the problems in this experiment:
>
> http://en.wikipedia.org/wiki/Oil_drop_experiment#Millikan.27s_experiment_as_an_example_of_psychological_effects_in_scientific_methodology
>
> But I am not willing to wait 70 years to get it all sorted out!
>
> The core observation I have is :
>
> Drop tail queues and AQMs do not do well in the face of cross traffic,
> (a mixture of small ack packets and larger data packets at saturating
> loads). This is apparently one of those problems that most aqm-ers
> (but not van and kathie!) wish to sweep under the rug, as if having a
> car that can steer on a downhill run only, was acceptable and safe to
> society at large.
>
> I made for-damn-sure that there was a rrul-like test for that scenario
> in the ns3 code now being mainlined, in the hope that new
> experimenters and designers of new algorithms would rigorously test
> for circumstances with cross traffic. I think I should also have got
> around to doing one in ns2.
>
> Moving on, codel was co-designed by the RED guy - van jacobson - and
> if you don´t  believe him when he explains how RED was flawed, please
> stay away from my networks.
>
> http://www.pollere.net/Pdfdocs/QrantJul06.pdf
>
> There is no information in average queue length.
>
> The whole story about red in a different light, is sad and amusing at
> the same time, when someone finds he has made a mistake, and tries to
> retract it, and cant get published, and the pile on and noise level
> since by folk since writing RED related papers, even since we managed
> to get the correctly contradictory information on RED out there, is
> annoying.
>
> If *all* future aqm oriented papers made sure to address the
> cross-traffic problem - that  mixture of big and small packets under
> saturating loads - with their latest-aqm-idea-de-jure as part of their
> *core criteria for worthiness* - it would be a better world.
>
> While I certainly believe that you can make an AQM that works better
> with cross traffic - and actually have some revisions for codel that
> do so -
>
> You cannot predict the traffic load or traffic types going in either
> direction in most environments and thus you *must* handle it at peak
> load in both directions, well, in order to have a deployable solution.
> For all the aqm-related papers of DASH and web traffic down, there are
> nearly none that test torrent/scp/dropbox or videoconferencing traffic
> up, at the same time. I would like to be in a world where I could
> refuse to read any paper that did not address the cross traffic
> problem, AND such papers were summarily rejected before publication.
>
> So, thus, codel is a AQM that combines well with FQ, unlike all other
> AQMs published to date - and nearly nobody that uses it, uses it
> without also doing FQ.
>
> As it is, fq_codel is deploying rapidly across the edge where it was
> designed to go, and I see nearly no implementations of RED in the
> field from extensive talks with operators and firmware makers around
> the world. *None*, in my last poll at the New Zealand network
> operators group meeting.
>
> Some form of fair queuing, on the other hand, was deployed by over 1/3
> the network operators there. (Convincing advocates of FQ that AQM is
> also needed, has often been a frustrating exercise as well!)
>
> Lastly, if you have trouble reading english, there is always google translate.
>
>
>> - Jonathan Morton
>>
>>
>> _______________________________________________
>> Codel mailing list
>> Codel@lists.bufferbloat.net
>> https://lists.bufferbloat.net/listinfo/codel
>>
>
>
>
> --
> Dave Täht
> Let's make wifi fast, less jittery and reliable again!
>
> https://plus.google.com/u/0/107942175615993706558/posts/TVX3o84jjmb



-- 
Dave Täht
Let's make wifi fast, less jittery and reliable again!

https://plus.google.com/u/0/107942175615993706558/posts/TVX3o84jjmb

Re: [Codel] why RED is not considered as a solution to bufferbloat.

[sahil grover]

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

Hi again,
Jonathan Morton,Richard Scheffenegger and anyone please reply:
As explained by Jonathan Morton,Richard Scheffenegger in above posts that
one of the advantage of codel over RED is that codel does its
work(drop/mark) at dequeue stage.
But i am not still getting it like how??
How does it make difference whether packet is dropped/marked at enqueue
stage or dequeue stage?

Lets first talk about packet is marked(forget about dropping),then whether
 it is marked at enqueue stage ,the marked packet have to go through that
 buffer.
Then what makes the difference?

On Wed, Feb 25, 2015 at 11:40 PM, Dave Taht <dave.taht@gmail.com> wrote:

> no prob.
>
> On Wed, Feb 25, 2015 at 9:34 AM, sahil grover <sahilgrover013@gmail.com>
> wrote:
> > Thanks for sharing
> > :)
> >
> > On Tue, Feb 24, 2015 at 11:45 PM, Dave Taht <dave.taht@gmail.com> wrote:
> >>
> >> and I meant to mention my other big kvetch...
> >>
> >> Nearly no paper tests an asymmetric network, where upload speeds are a
> >> fraction of the download speeds. This leads to acks dominating
> >> upstream traffic, and A) a big upload is starved, or B) that upload
> >> acks starves the download by a providers desparate attempts to
> >> optimize - the combination of any traffic accros sthat link gets
> >> subject to crazy ideas like ack prioritization and other scenarios
> >> that break other forms of traffic.
> >>
> >> As this is actually how the edge of the internet is deployed - DSL has
> >> ratios of 6 and even 20 to 1, cable modems are in the range of 6 and
> >> 10 to 1, the only technology that is symmetric is fiber - it totally
> >> boggles my mind that this is not also the standard benchmark test of
> >> an aqm or fq algorithm.
> >>
> >> The lack of an asymmetric network test should also be a fundamental
> >> bar to publication of any new paper on the AQM or FQ subjects.
> >>
> >> So we fixed that, in creating ns3 tests as well. It turned out to be
> >> hard to do, we had a ton of bugs to sort out in the code (now mostly
> >> done except for getting fq_codel itself mainlined) and I have no idea
> >> if ns2 has the same problems or not, but it certainly explains why so
> >> little in the liturature actually sees the real problems.
> >>
> >> And lastly - on another subject entirely - no aqm we know of yet is
> >> correctly structured to deal with the taxi-stand topology half duplex
> >> nature of wifi and wireless, and no sim I have yet tried looks
> >> anything like measured reality.
> >>
> >> we're working on it.
> >>
> >> On Tue, Feb 24, 2015 at 10:00 AM, Dave Taht <dave.taht@gmail.com>
> wrote:
> >> > On Tue, Feb 24, 2015 at 8:32 AM, Jonathan Morton <
> chromatix99@gmail.com>
> >> > wrote:
> >> >> Most of us on this list believe that to be true, in many cases after
> >> >> performing experiments ourselves, or at least looking through data
> >> >> generated
> >> >> by others' experiments.
> >> >>
> >> >> However, if as I suspect you are investigating various AQM algorithms
> >> >> as
> >> >> part of your education, you should probably examine the data
> yourselves
> >> >> and
> >> >> come to your own conclusions. You may even get extra credit for being
> >> >> able
> >> >> to describe the difference between AQM and Fair Queuing, and how they
> >> >> can be
> >> >> combined (as in fq_codel) to give the benefits of both types in one
> go.
> >> >> But
> >> >> for that, you ARE going to need to read some boring papers like "RED
> in
> >> >> a
> >> >> different light".
> >> >
> >> > It is not particularly easy to keep up with the onslought of AQM
> >> > literature since the bufferbloat effort started, but a review of stuff
> >> > since 2011, or even as late at 2013 via google scholar should be
> >> > illuminating. Many papers use RED as a reference, but nearly all of
> >> > them miss the major points in the original bufferbloat experiments.
> >> > Those experiment, long ago documented on Jim´s earliest writings on
> >> > the subject, available in video form, in various papers etc. One
> >> > example:
> >> >
> >> >
> >> >
> https://gettys.wordpress.com/2012/02/01/bufferbloat-demonstration-videos/
> >> >
> >> > where jim performed an upload and a ping, at the same time, on a
> >> > network optimized for downloads and and obviously not tested for
> >> > uploads. The later rrul test suite (in netperf-wrapper, open source,
> >> > anybody can use it, and I really wish they did) was designed to
> >> > exercise both directions of the link with tcp data, and do a latency
> >> > measurement, at the same time.
> >> >
> >> > Either experiment is consistently not replicated by experimenters *to
> >> > date*, it frustrates me, and the only thing that gives hope is the
> >> > slow progress in science of resolving the problems in this experiment:
> >> >
> >> >
> >> >
> http://en.wikipedia.org/wiki/Oil_drop_experiment#Millikan.27s_experiment_as_an_example_of_psychological_effects_in_scientific_methodology
> >> >
> >> > But I am not willing to wait 70 years to get it all sorted out!
> >> >
> >> > The core observation I have is :
> >> >
> >> > Drop tail queues and AQMs do not do well in the face of cross traffic,
> >> > (a mixture of small ack packets and larger data packets at saturating
> >> > loads). This is apparently one of those problems that most aqm-ers
> >> > (but not van and kathie!) wish to sweep under the rug, as if having a
> >> > car that can steer on a downhill run only, was acceptable and safe to
> >> > society at large.
> >> >
> >> > I made for-damn-sure that there was a rrul-like test for that scenario
> >> > in the ns3 code now being mainlined, in the hope that new
> >> > experimenters and designers of new algorithms would rigorously test
> >> > for circumstances with cross traffic. I think I should also have got
> >> > around to doing one in ns2.
> >> >
> >> > Moving on, codel was co-designed by the RED guy - van jacobson - and
> >> > if you don´t  believe him when he explains how RED was flawed, please
> >> > stay away from my networks.
> >> >
> >> > http://www.pollere.net/Pdfdocs/QrantJul06.pdf
> >> >
> >> > There is no information in average queue length.
> >> >
> >> > The whole story about red in a different light, is sad and amusing at
> >> > the same time, when someone finds he has made a mistake, and tries to
> >> > retract it, and cant get published, and the pile on and noise level
> >> > since by folk since writing RED related papers, even since we managed
> >> > to get the correctly contradictory information on RED out there, is
> >> > annoying.
> >> >
> >> > If *all* future aqm oriented papers made sure to address the
> >> > cross-traffic problem - that  mixture of big and small packets under
> >> > saturating loads - with their latest-aqm-idea-de-jure as part of their
> >> > *core criteria for worthiness* - it would be a better world.
> >> >
> >> > While I certainly believe that you can make an AQM that works better
> >> > with cross traffic - and actually have some revisions for codel that
> >> > do so -
> >> >
> >> > You cannot predict the traffic load or traffic types going in either
> >> > direction in most environments and thus you *must* handle it at peak
> >> > load in both directions, well, in order to have a deployable solution.
> >> > For all the aqm-related papers of DASH and web traffic down, there are
> >> > nearly none that test torrent/scp/dropbox or videoconferencing traffic
> >> > up, at the same time. I would like to be in a world where I could
> >> > refuse to read any paper that did not address the cross traffic
> >> > problem, AND such papers were summarily rejected before publication.
> >> >
> >> > So, thus, codel is a AQM that combines well with FQ, unlike all other
> >> > AQMs published to date - and nearly nobody that uses it, uses it
> >> > without also doing FQ.
> >> >
> >> > As it is, fq_codel is deploying rapidly across the edge where it was
> >> > designed to go, and I see nearly no implementations of RED in the
> >> > field from extensive talks with operators and firmware makers around
> >> > the world. *None*, in my last poll at the New Zealand network
> >> > operators group meeting.
> >> >
> >> > Some form of fair queuing, on the other hand, was deployed by over 1/3
> >> > the network operators there. (Convincing advocates of FQ that AQM is
> >> > also needed, has often been a frustrating exercise as well!)
> >> >
> >> > Lastly, if you have trouble reading english, there is always google
> >> > translate.
> >> >
> >> >
> >> >> - Jonathan Morton
> >> >>
> >> >>
> >> >> _______________________________________________
> >> >> Codel mailing list
> >> >> Codel@lists.bufferbloat.net
> >> >> https://lists.bufferbloat.net/listinfo/codel
> >> >>
> >> >
> >> >
> >> >
> >> > --
> >> > Dave Täht
> >> > Let's make wifi fast, less jittery and reliable again!
> >> >
> >> > https://plus.google.com/u/0/107942175615993706558/posts/TVX3o84jjmb
> >>
> >>
> >>
> >> --
> >> Dave Täht
> >> Let's make wifi fast, less jittery and reliable again!
> >>
> >> https://plus.google.com/u/0/107942175615993706558/posts/TVX3o84jjmb
> >
> >
>
>
>
> --
> Dave Täht
> Let's make wifi fast, less jittery and reliable again!
>
> https://plus.google.com/u/0/107942175615993706558/posts/TVX3o84jjmb
>

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

Re: [Codel] why RED is not considered as a solution to bufferbloat.

[Jonathan Morton]

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

Okay, let me walk you through this.

Let's say you are managing a fairly slow link, on the order of 1 megabit.
The receiver on the far side of it is running a modern OS and has opened
its receive window to a whole megabyte. It would take about 10 seconds to
pass a whole receive window through the link.

This is a common situation in the real world, by the way.

Now, let's suppose that the sender was constrained to a slower send rate,
say half a megabit, for reasons unrelated to the network. Maybe it's a
streaming video service on a mostly static image, so it only needs to send
small delta frames and compressed audio. It has therefore opened the
congestion window as wide as it will go, to the limit of the receive
window. But then the action starts, there's a complete scene change, and a
big burst of data is sent all at once, because the congestion window
permits it.

So the queue you're managing suddenly has a megabyte of data in it. Unless
you do something about it, your induced latency just leapt up to ten
seconds, and the VoIP call your user was on at the time will drop out.

Now, let's compare the behaviour of two AQMs: Codel and something almost,
but not entirely, unlike Codel. Specifically, it does everything that Codel
does, but at enqueue instead of dequeue time.

Both of them will let the entire burst into the queue. Codel only takes
action if the queue remains more full than its threshold for more than
100ms. Since this burst arrives all at once, and the queue stayed nice and
empty up until now, neither AQM will decide to mark or drop packets at that
moment.

Now, packets are slowly delivered across the link. Each one takes about
15ms to deliver. They are answered by acks, and the sender obligingly sends
fresh packets to replace them. After about six or seven packets have been
delivered, both AQMs will decide to start marking packets (this is an ECN
enabled flow). Let's assume that the next packet after this point will be
marked. This will be the receiver's first clue that congestion is occurring.

For Codel, the next packet available to mark will be the eighth packet. So
the receiver learns about the congestion event 120 ms after it began. It
will echo the congestion mark back to the sender in the corresponding ack,
which will immediately halve the congestion window. It will still take at
least ten seconds to drain the queue.

For NotCodel, the next available packet for marking is the one a megabyte
later than the eighth packet. The receiver won't see that packet until
10120 ms after the congestion event began. So the sender will happily keep
the queue ten seconds long for the next ten seconds, instead of backing off
straight away. It will take at least TWENTY seconds to drain the queue.

Note that even if the link bandwidth was 10 megabits rather than one, with
the same receive window size, it would still take one second to drain the
queue with Codel and two seconds with NotCodel.

This relatively simple traffic situation demonstrates that marking on
dequeue rather than enqueue is twice as effective at managing queue length.

- Jonathan Morton

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

Re: [Codel] why RED is not considered as a solution to bufferbloat.

[sahil grover]

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

Jonathan,
crystal clear now..
i mean the way u explain, Hats off seriously.
well,i  need to learn some more.
My question is how tcp reacts to packet drop,
like if we talk about packet marking then with acknowledgement from
receiver, tcp sender gets the congestion signal(if i am not wrong)
but if packet is dropped then what is mechanism?
 is it related with (a) 3 duplicate acknowledgement or (b)timeout event?


On Thu, Feb 26, 2015 at 7:26 PM, Jonathan Morton <chromatix99@gmail.com>
wrote:

> Okay, let me walk you through this.
>
> Let's say you are managing a fairly slow link, on the order of 1 megabit.
> The receiver on the far side of it is running a modern OS and has opened
> its receive window to a whole megabyte. It would take about 10 seconds to
> pass a whole receive window through the link.
>
> This is a common situation in the real world, by the way.
>
> Now, let's suppose that the sender was constrained to a slower send rate,
> say half a megabit, for reasons unrelated to the network. Maybe it's a
> streaming video service on a mostly static image, so it only needs to send
> small delta frames and compressed audio. It has therefore opened the
> congestion window as wide as it will go, to the limit of the receive
> window. But then the action starts, there's a complete scene change, and a
> big burst of data is sent all at once, because the congestion window
> permits it.
>
> So the queue you're managing suddenly has a megabyte of data in it. Unless
> you do something about it, your induced latency just leapt up to ten
> seconds, and the VoIP call your user was on at the time will drop out.
>
> Now, let's compare the behaviour of two AQMs: Codel and something almost,
> but not entirely, unlike Codel. Specifically, it does everything that Codel
> does, but at enqueue instead of dequeue time.
>
> Both of them will let the entire burst into the queue. Codel only takes
> action if the queue remains more full than its threshold for more than
> 100ms. Since this burst arrives all at once, and the queue stayed nice and
> empty up until now, neither AQM will decide to mark or drop packets at that
> moment.
>
> Now, packets are slowly delivered across the link. Each one takes about
> 15ms to deliver. They are answered by acks, and the sender obligingly sends
> fresh packets to replace them. After about six or seven packets have been
> delivered, both AQMs will decide to start marking packets (this is an ECN
> enabled flow). Let's assume that the next packet after this point will be
> marked. This will be the receiver's first clue that congestion is occurring.
>
> For Codel, the next packet available to mark will be the eighth packet. So
> the receiver learns about the congestion event 120 ms after it began. It
> will echo the congestion mark back to the sender in the corresponding ack,
> which will immediately halve the congestion window. It will still take at
> least ten seconds to drain the queue.
>
> For NotCodel, the next available packet for marking is the one a megabyte
> later than the eighth packet. The receiver won't see that packet until
> 10120 ms after the congestion event began. So the sender will happily keep
> the queue ten seconds long for the next ten seconds, instead of backing off
> straight away. It will take at least TWENTY seconds to drain the queue.
>
> Note that even if the link bandwidth was 10 megabits rather than one, with
> the same receive window size, it would still take one second to drain the
> queue with Codel and two seconds with NotCodel.
>
> This relatively simple traffic situation demonstrates that marking on
> dequeue rather than enqueue is twice as effective at managing queue length.
>
> - Jonathan Morton
>

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

Re: [Codel] why RED is not considered as a solution to bufferbloat.

[Richard Scheffenegger]

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

Sahil,

A TCP Sender will reduce the congestion window in a similar fashion to both a) first ECE bit received in a window (flight of packets worth one RTT), and of course, b) exceeding the DupThresh limit of duplicate acks, again in one RTT worth of segments. The typical reaction in these two cases is a multiplicative reduction of the size of the congestion window, with the muliplication factor 0.5 - with other words, the sending rate is halved. (Some variants of TCP deviate from this factor of 0,5, but it's always a multiplicative decrease (the second half of AIMD - additive increase, multiplicative decrease; the general control law that results in stable network operating under load).

A retransmission timeout causes the sending TCP to reduce it's sending rate much more significantly - after an RTO, it restarts the TCP sending rate much like from a clean start, often even more gentle, as the initial window is reduced to only 1 or 2 segments (instead of 4 to 10)).


Regarding the absolute number of losses - note that it's only one loss (or mark) per RTT that halves the sending rate; with large congestion window, you could drop dozends or even hundreds of segments, and the sending TCP will still only half the sending rate. As long as all these losses occur within the first RTT. Another loss after the first RTT, and the TCP sender will react again (thus send only at 1/4 from the original rate).

This is the reason why looking at raw drop numbers it not all that helpful byitself, the overall combination of goodput and  latency (which, in case of TCP, includes queuing-induced latency, transmission latency and loss recovery latency) are much more relevant. With ECN, the loss recovery latency is virtually zero, as the congestion signal is explicitly signaled from the network to the end hosts.

Unfortunately, Latency hasn't been a big topic for ISPs; Datacenter operators care much much more about latency (and it's easier there to deploy solutions, like ECN with an AQM set up with good parameters for that limited environment).

Hope this helps,
  Richard

  ----- Original Message ----- 
  From: sahil grover 
  To: Jonathan Morton 
  Cc: codel@lists.bufferbloat.net ; Richard Scheffenegger 
  Sent: Friday, February 27, 2015 3:34 PM
  Subject: Re: [Codel] why RED is not considered as a solution to bufferbloat.


  Jonathan,
  crystal clear now..
  i mean the way u explain, Hats off seriously.
  well,i  need to learn some more.
  My question is how tcp reacts to packet drop,
  like if we talk about packet marking then with acknowledgement from receiver, tcp sender gets the congestion signal(if i am not wrong)
  but if packet is dropped then what is mechanism?
   is it related with (a) 3 duplicate acknowledgement or (b)timeout event?




  On Thu, Feb 26, 2015 at 7:26 PM, Jonathan Morton <chromatix99@gmail.com> wrote:

    Okay, let me walk you through this.

    Let's say you are managing a fairly slow link, on the order of 1 megabit. The receiver on the far side of it is running a modern OS and has opened its receive window to a whole megabyte. It would take about 10 seconds to pass a whole receive window through the link.

    This is a common situation in the real world, by the way.

    Now, let's suppose that the sender was constrained to a slower send rate, say half a megabit, for reasons unrelated to the network. Maybe it's a streaming video service on a mostly static image, so it only needs to send small delta frames and compressed audio. It has therefore opened the congestion window as wide as it will go, to the limit of the receive window. But then the action starts, there's a complete scene change, and a big burst of data is sent all at once, because the congestion window permits it.

    So the queue you're managing suddenly has a megabyte of data in it. Unless you do something about it, your induced latency just leapt up to ten seconds, and the VoIP call your user was on at the time will drop out.

    Now, let's compare the behaviour of two AQMs: Codel and something almost, but not entirely, unlike Codel. Specifically, it does everything that Codel does, but at enqueue instead of dequeue time.

    Both of them will let the entire burst into the queue. Codel only takes action if the queue remains more full than its threshold for more than 100ms. Since this burst arrives all at once, and the queue stayed nice and empty up until now, neither AQM will decide to mark or drop packets at that moment.

    Now, packets are slowly delivered across the link. Each one takes about 15ms to deliver. They are answered by acks, and the sender obligingly sends fresh packets to replace them. After about six or seven packets have been delivered, both AQMs will decide to start marking packets (this is an ECN enabled flow). Let's assume that the next packet after this point will be marked. This will be the receiver's first clue that congestion is occurring.

    For Codel, the next packet available to mark will be the eighth packet. So the receiver learns about the congestion event 120 ms after it began. It will echo the congestion mark back to the sender in the corresponding ack, which will immediately halve the congestion window. It will still take at least ten seconds to drain the queue.

    For NotCodel, the next available packet for marking is the one a megabyte later than the eighth packet. The receiver won't see that packet until 10120 ms after the congestion event began. So the sender will happily keep the queue ten seconds long for the next ten seconds, instead of backing off straight away. It will take at least TWENTY seconds to drain the queue.

    Note that even if the link bandwidth was 10 megabits rather than one, with the same receive window size, it would still take one second to drain the queue with Codel and two seconds with NotCodel.

    This relatively simple traffic situation demonstrates that marking on dequeue rather than enqueue is twice as effective at managing queue length.

    - Jonathan Morton




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

Re: [Codel] why RED is not considered as a solution to bufferbloat.

[Greg White]

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

This is a common misconception.

The "NotCodel" approach, operating entirely at enqueue time, will have to predict buffering latency for a packet when it is enqueued (likely based on queue depth and expected dequeue rate), as opposed to CoDel which measures the buffering latency for the packet after it has been experienced.  If dequeue rate is predictable (true for some links, less so for others) then the NotCodel approach can be designed such that it will drop (or mark) *the same packets* that the CoDel approach would.

In some hardware, it is much more feasible to perform these operations at enqueue time rather than at dequeue time.  Implementers of such systems shouldn't be dissuaded from implementing CoDel (especially if their dequeue rate is reasonably predictable).

We experimented with an implementation of "NotCodel"  (we called it CoDel-DT, for drop tail) and that code is in the ns-2.36 release candidate.  One caveat, the control law in that implementation does not precisely match CoDel, and so there will be some slight differences in results between the two.

-Greg

From: Jonathan Morton <chromatix99@gmail.com<mailto:chromatix99@gmail.com>>
Date: Thursday, February 26, 2015 at 6:56 AM
To: sahil grover <sahilgrover013@gmail.com<mailto:sahilgrover013@gmail.com>>
Cc: "codel@lists.bufferbloat.net<mailto:codel@lists.bufferbloat.net>" <codel@lists.bufferbloat.net<mailto:codel@lists.bufferbloat.net>>
Subject: Re: [Codel] why RED is not considered as a solution to bufferbloat.


Okay, let me walk you through this.

Let's say you are managing a fairly slow link, on the order of 1 megabit. The receiver on the far side of it is running a modern OS and has opened its receive window to a whole megabyte. It would take about 10 seconds to pass a whole receive window through the link.

This is a common situation in the real world, by the way.

Now, let's suppose that the sender was constrained to a slower send rate, say half a megabit, for reasons unrelated to the network. Maybe it's a streaming video service on a mostly static image, so it only needs to send small delta frames and compressed audio. It has therefore opened the congestion window as wide as it will go, to the limit of the receive window. But then the action starts, there's a complete scene change, and a big burst of data is sent all at once, because the congestion window permits it.

So the queue you're managing suddenly has a megabyte of data in it. Unless you do something about it, your induced latency just leapt up to ten seconds, and the VoIP call your user was on at the time will drop out.

Now, let's compare the behaviour of two AQMs: Codel and something almost, but not entirely, unlike Codel. Specifically, it does everything that Codel does, but at enqueue instead of dequeue time.

Both of them will let the entire burst into the queue. Codel only takes action if the queue remains more full than its threshold for more than 100ms. Since this burst arrives all at once, and the queue stayed nice and empty up until now, neither AQM will decide to mark or drop packets at that moment.

Now, packets are slowly delivered across the link. Each one takes about 15ms to deliver. They are answered by acks, and the sender obligingly sends fresh packets to replace them. After about six or seven packets have been delivered, both AQMs will decide to start marking packets (this is an ECN enabled flow). Let's assume that the next packet after this point will be marked. This will be the receiver's first clue that congestion is occurring.

For Codel, the next packet available to mark will be the eighth packet. So the receiver learns about the congestion event 120 ms after it began. It will echo the congestion mark back to the sender in the corresponding ack, which will immediately halve the congestion window. It will still take at least ten seconds to drain the queue.

For NotCodel, the next available packet for marking is the one a megabyte later than the eighth packet. The receiver won't see that packet until 10120 ms after the congestion event began. So the sender will happily keep the queue ten seconds long for the next ten seconds, instead of backing off straight away. It will take at least TWENTY seconds to drain the queue.

Note that even if the link bandwidth was 10 megabits rather than one, with the same receive window size, it would still take one second to drain the queue with Codel and two seconds with NotCodel.

This relatively simple traffic situation demonstrates that marking on dequeue rather than enqueue is twice as effective at managing queue length.

- Jonathan Morton

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

Re: [Codel] why RED is not considered as a solution to bufferbloat.

[Jonathan Morton]

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

> If dequeue rate is predictable (true for some links, less so for others)
then the NotCodel approach can be designed such that it will drop (or mark)
*the same packets* that the CoDel approach would.

In other words, in certain specific cases it is possible to behave as
though you were head-dropping even though you actually aren't. And that's
fine, as long as you don't forget that head-drop is the gold standard and
you're just faking it. It's a general technique used in all sorts of
hardware and software.

But as soon as conditions change from that fairly ideal situation, you
start having to genuinely do the work at the head of the queue in order to
obtain the accurate sojourn times. Given the audience that I wrote that
explanation for (you have seen the calibre of their questions...), I
thought it best to keep away from gritty implementation details in order to
keep it conceptually simple.

And even on switched Ethernet - one of the more obvious candidates for the
technique - the line rate can vary unexpectedly. Pause frames are the most
likely cause, and one possible source of pause frames is a cable or DSL
modem signalling its own link rate back to the host. But until the link is
unpaused, the head packet can't be dequeued, and the sojourn time of it and
any other packets behind it increases, throwing off any estimates that
might have been taken at enqueue time. The likely symptoms would be similar
to running normal Codel on an overbuffered Ethernet device without BQL.

- Jonathan Morton

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

Re: [Codel] why RED is not considered as a solution to bufferbloat.

[Kathleen Nichols]

Or even read the "boring code".

On 2/24/15 8:32 AM, Jonathan Morton wrote:
> Most of us on this list believe that to be true, in many cases after
> performing experiments ourselves, or at least looking through data
> generated by others' experiments.
> 
> However, if as I suspect you are investigating various AQM algorithms as
> part of your education, you should probably examine the data yourselves
> and come to your own conclusions. You may even get extra credit for
> being able to describe the difference between AQM and Fair Queuing, and
> how they can be combined (as in fq_codel) to give the benefits of both
> types in one go. But for that, you ARE going to need to read some boring
> papers like "RED in a different light".
> 
> - Jonathan Morton
> 
> 
> 
> _______________________________________________
> Codel mailing list
> Codel@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/codel
> 

Re: [Codel] why RED is not considered as a solution to bufferbloat.

[Richard Scheffenegger]

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

Sahil.,

Codel tries to address the problems that RED couldn't; First, the input signal into the algorithm (sojourn time vs. average queue depth) is of a different quality; Second, Codel (in it's plain form) does drop/mark on dequeue, while RED drops/marks on enqueue. This means, that [TCP] congestion control loop is much quicker with Codel over RED; thus the reaction by the sender will probably be timely and relevant for that congestion epoch.  With RED; the congestion signal (that lost packet) has to traverse the filled-up buffer first, thus the control loop time is much larger (includes the instantaneous queue length of the buffer) - and is further delayed by the averaging going on.

Codel, by design, doesn't need to be tuned specifically for one particular drain rate (bandwidht) of the queue - unlike RED; So it adjusts much better to variable bandwidth MACs (Wifi, DOCSIS).

I've been told, that RED is easier to implement in HW due to that action being all done on enqueue. With PIE, there exists another AQM that tries to re-use the hw engines that exist for RED, but the control algorithms try to use a different input signal - making the best of that.


If you follow the AQM work in IETF, there is strong consensus steer to these more modern AQMs.

Best regards,
  Richard


  ----- Original Message ----- 
  From: sahil grover 
  To: Jonathan Morton 
  Cc: codel@lists.bufferbloat.net 
  Sent: Tuesday, February 24, 2015 5:20 PM
  Subject: Re: [Codel] why RED is not considered as a solution to bufferbloat.


  So we can say Codel is better than other AQM???


  On Tue, Feb 24, 2015 at 9:24 PM, Jonathan Morton <chromatix99@gmail.com> wrote:

    Simply put, RED is a very old algorithm, one of the first viable AQM algorithms. However, it proved to be so difficult to configure properly that almost nobody uses it, even though many carrier grade routers implement it.

    Codel not only performs better than an ideally configured RED, but is far easier to configure. This makes it much more deployable.

    - Jonathan Morton






------------------------------------------------------------------------------


  _______________________________________________
  Codel mailing list
  Codel@lists.bufferbloat.net
  https://lists.bufferbloat.net/listinfo/codel

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

Re: [Codel] why RED is not considered as a solution to bufferbloat.

[sahil grover]

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

Thanks a lot Jonathan,Eddy and Richard.
With the help of you people i have cleared many concepts.
But still one point is not clear.
Richard Sir you said that Codel is better in notifying congestion to TCP
senders.
But Sir how,i know codel does it at dequeue stage while RED does at enqueue
stage.
The thing is  congestion signal has to traverse the buffer.
Then how does it make difference that whether it is at enqueue or dequeue.i
mean how it is quicker with codel?




On Tue, Feb 24, 2015 at 8:33 AM, Richard Scheffenegger <rscheff@gmx.at>
wrote:

>  Sahil.,
>
> Codel tries to address the problems that RED couldn't; First, the input
> signal into the algorithm (sojourn time vs. average queue depth) is of a
> different quality; Second, Codel (in it's plain form) does drop/mark on
> dequeue, while RED drops/marks on enqueue. This means, that [TCP]
> congestion control loop is much quicker with Codel over RED; thus the
> reaction by the sender will probably be timely and relevant for that
> congestion epoch.  With RED; the congestion signal (that lost packet) has
> to traverse the filled-up buffer first, thus the control loop time is much
> larger (includes the instantaneous queue length of the buffer) - and is
> further delayed by the averaging going on.
>
> Codel, by design, doesn't need to be tuned specifically for one particular
> drain rate (bandwidht) of the queue - unlike RED; So it adjusts much better
> to variable bandwidth MACs (Wifi, DOCSIS).
>
> I've been told, that RED is easier to implement in HW due to that action
> being all done on enqueue. With PIE, there exists another AQM that tries to
> re-use the hw engines that exist for RED, but the control algorithms try to
> use a different input signal - making the best of that.
>
>
> If you follow the AQM work in IETF, there is strong consensus steer to
> these more modern AQMs.
>
> Best regards,
>   Richard
>
>
>
> ----- Original Message -----
> *From:* sahil grover <sahilgrover013@gmail.com>
> *To:* Jonathan Morton <chromatix99@gmail.com>
> *Cc:* codel@lists.bufferbloat.net
> *Sent:* Tuesday, February 24, 2015 5:20 PM
> *Subject:* Re: [Codel] why RED is not considered as a solution to
> bufferbloat.
>
> So we can say Codel is better than other AQM???
>
> On Tue, Feb 24, 2015 at 9:24 PM, Jonathan Morton <chromatix99@gmail.com>
> wrote:
>
>> Simply put, RED is a very old algorithm, one of the first viable AQM
>> algorithms. However, it proved to be so difficult to configure properly
>> that almost nobody uses it, even though many carrier grade routers
>> implement it.
>>
>> Codel not only performs better than an ideally configured RED, but is far
>> easier to configure. This makes it much more deployable.
>>
>> - Jonathan Morton
>>
>
>  ------------------------------
>
> _______________________________________________
> Codel mailing list
> Codel@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/codel
>
>

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

Re: [Codel] why RED is not considered as a solution to bufferbloat.

[Jonathan Morton]

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

To answer that question, simply think about the lifetime of a packet in the
queue. It is enqueued, spends some time waiting there (very little if the
link isn't congested, potentially much more if it is), then is dequeued.

So the difference in time between enqueue and dequeue is...?

- Jonathan Morton

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

Re: [Codel] why RED is not considered as a solution to bufferbloat.

[Wesley Eddy]

On 2/24/2015 10:37 AM, sahil grover wrote:
> (i) First of all,i want to know whether RED was implemented or not? 
> if not then what were the reasons(major) ?
> anyone please tell me in simple words here only,because i don't want to
> read any paper like "RED in a different light".
> 
> (ii)Second, as we all know RED controls the  average queue size from
> growing.
> So it also controls delay in a way or  we can say  is a solution to
> bufferbloat problem. Then why it was not considered.
> 


There is an IETF document from the AQM working group which contains
some discussion towards your first question, at least:
https://tools.ietf.org/html/draft-ietf-aqm-recommendation-10
(this should be published as an RFC "soon")

Specifically, the text says:

   With an appropriate set of parameters, RED is an effective algorithm.
   However, dynamically predicting this set of parameters was found to
   be difficult.  As a result, RED has not been enabled by default, and
   its present use in the Internet is limited.  Other AQM algorithms
   have been developed since RC2309 was published, some of which are
   self-tuning within a range of applicability.  Hence, while this memo
   continues to recommend the deployment of AQM, it no longer recommends
   that RED or any other specific algorithm is used as a default;
   instead it provides recommendations on how to select appropriate
   algorithms and that a recommended algorithm is able to automate any
   required tuning for common deployment scenarios.


-- 
Wes Eddy
MTI Systems