[Codel] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Codel] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Dave Taht]

Greg White and his team over at cablelabs have just published their
latest simulation results of the aqm algorithms under test on
simulated cable modems.

This paper is vastly expanded from the presentation at ietf 86 iccrg,
including great descriptions the effects of latency on web, voice, and
gaming traffic, and of codel, fq_codel, and pie. There's an excellent
and deep section on the characteristics of gaming traffic, a ton of
new graphs and analysis, and much much more.

http://www.cablelabs.com/downloads/pubs/Active_Queue_Management_Algorithms_DOCSIS_3_0.pdf

While I have a few quibbles, I'll reserve them until after more folk
have had a chance to read this.

It's good stuff.

-- 
Dave Täht

Fixing bufferbloat with cerowrt: http://www.teklibre.com/cerowrt/subscribe.html

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Simon Barber]

Interesting to note that sfq-codel's reaction to a non conforming flow 
is of course to start dropping more aggressively to make it conform, 
leading to the high loss rates for whatever is hashed together with a 
VoIP flow that does not reduce it's bandwidth.

One downside to SFQ really.

Simon

On Wed 01 May 2013 04:23:00 AM PDT, Dave Taht wrote:
> Greg White and his team over at cablelabs have just published their
> latest simulation results of the aqm algorithms under test on
> simulated cable modems.
>
> This paper is vastly expanded from the presentation at ietf 86 iccrg,
> including great descriptions the effects of latency on web, voice, and
> gaming traffic, and of codel, fq_codel, and pie. There's an excellent
> and deep section on the characteristics of gaming traffic, a ton of
> new graphs and analysis, and much much more.
>
> http://www.cablelabs.com/downloads/pubs/Active_Queue_Management_Algorithms_DOCSIS_3_0.pdf
>
> While I have a few quibbles, I'll reserve them until after more folk
> have had a chance to read this.
>
> It's good stuff.
>

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Jonathan Morton]

On 1 May, 2013, at 11:26 pm, Simon Barber wrote:

> Interesting to note that sfq-codel's reaction to a non conforming flow is of course to start dropping more aggressively to make it conform, leading to the high loss rates for whatever is hashed together with a VoIP flow that does not reduce it's bandwidth.
> 
> One downside to SFQ really.

The only real solution, for the scenario where this happens, would be to somehow identify all the BitTorrent traffic and stuff it into a single bucket, where it has to compete on equal terms with the single VoIP flow.  The big unanswered question is then: can this realistically be done?  Does BitTorrent traffic get marked as the bulk, low priority traffic it is, for example?

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Simon Barber]

Or one could use more queues in SFQ, so that the chance of 2 streams 
sharing a queue is small. Even perhaps use a different strategy than 
hashing to distribute traffic to queues, although whatever strategy is 
used needs to be resistant to DoS attacks. Or one could classify the 
VoIP traffic and prioritise that. Another possibility is a heuristic 
approach - don't mix long lived bulk data streams in the same bucket as 
others.

Simon

On Wed 01 May 2013 05:00:27 PM PDT, Jonathan Morton wrote:
>
> On 1 May, 2013, at 11:26 pm, Simon Barber wrote:
>
>> Interesting to note that sfq-codel's reaction to a non conforming flow is of course to start dropping more aggressively to make it conform, leading to the high loss rates for whatever is hashed together with a VoIP flow that does not reduce it's bandwidth.
>>
>> One downside to SFQ really.
>
> The only real solution, for the scenario where this happens, would be to somehow identify all the BitTorrent traffic and stuff it into a single bucket, where it has to compete on equal terms with the single VoIP flow.  The big unanswered question is then: can this realistically be done?  Does BitTorrent traffic get marked as the bulk, low priority traffic it is, for example?

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Andrew McGregor]

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

It is quite reasonable for edge devices to not use SFQ but actual FQ with
one queue per flow (and some reasonable garbage collection heuristic).  Or
to use a few thousand queues.

Most of the time connection tracking will be enabled on an edge router
anyway, so the device is paying that overhead already.  May as well use it.


On Thu, May 2, 2013 at 12:20 PM, Simon Barber <simon@superduper.net> wrote:

> Or one could use more queues in SFQ, so that the chance of 2 streams
> sharing a queue is small. Even perhaps use a different strategy than
> hashing to distribute traffic to queues, although whatever strategy is used
> needs to be resistant to DoS attacks. Or one could classify the VoIP
> traffic and prioritise that. Another possibility is a heuristic approach -
> don't mix long lived bulk data streams in the same bucket as others.
>
> Simon
>
>
> On Wed 01 May 2013 05:00:27 PM PDT, Jonathan Morton wrote:
>
>>
>> On 1 May, 2013, at 11:26 pm, Simon Barber wrote:
>>
>>  Interesting to note that sfq-codel's reaction to a non conforming flow
>>> is of course to start dropping more aggressively to make it conform,
>>> leading to the high loss rates for whatever is hashed together with a VoIP
>>> flow that does not reduce it's bandwidth.
>>>
>>> One downside to SFQ really.
>>>
>>
>> The only real solution, for the scenario where this happens, would be to
>> somehow identify all the BitTorrent traffic and stuff it into a single
>> bucket, where it has to compete on equal terms with the single VoIP flow.
>>  The big unanswered question is then: can this realistically be done?  Does
>> BitTorrent traffic get marked as the bulk, low priority traffic it is, for
>> example?
>>
> ______________________________**_________________
> Codel mailing list
> Codel@lists.bufferbloat.net
> https://lists.bufferbloat.net/**listinfo/codel<https://lists.bufferbloat.net/listinfo/codel>
>

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

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Jonathan Morton]

On 2 May, 2013, at 5:20 am, Simon Barber wrote:

> Or one could use more queues in SFQ, so that the chance of 2 streams sharing a queue is small.

CableLabs actually did try that - increasing the number of queues - and found that it made things worse.  This, I think, extends to true "fair queueing" with flows explicitly rather than stochastically identified.  The reason is that with a very large number of flows, the bandwidth (or the packet throughput) is still shared evenly between them, and there is not enough bandwidth in the VoIP flow's share to allow it to work correctly.  With a relatively small number of flow buckets, the responsive flows hashed to the same bucket get out of the way of the unresponsive VoIP flow.

In short, a very large number of flow buckets prioritises BitTorrent over anything latency-sensitive, because BitTorrent uses a very large number of individual flows.

By contrast, putting all the BitTorrent flows into one bucket (or a depressed-priority queue with it's own SFQ buckets), or else elevating the VoIP traffic explicitly to a prioritised queue, would share the bandwidth more favourably to the VoIP flow, allowing it to use as much as it needed.  Either, or indeed both simultaneously, would do the job reasonably well, although an elevated priority queue should be bandwidth limited to a fraction of capacity to avoid the temptation of abuse by bulk flows.  Then there would be no performance objection to using a large number of flow buckets.

I can easily see a four-tier system working for most consumers, just so long as the traffic for each tier can be identified - each tier would have it's own fq_codel queue:

1) Network control traffic, eg. DNS, ICMP, even SYNs and pure ACKs - max 1/16th bandwidth, top priority

2) Latency-sensitive unresponsive flows, eg. VoIP and gaming - max 1/4 bandwidth, high priority

3) Ordinary bulk traffic, eg. web browsing, email, general purpose protocols - no bandwidth limit, normal priority

4) Background traffic, eg. BitTorrent - no bandwidth limit, low priority, voluntarily marked, competes at 1:4 with normal.

Obviously, the classification system implementing that must have some idea of what bandwidth is actually available at any given moment, but it is not necessary to explicitly restrict the top tiers' bandwidth when the link is otherwise idle.  Practical algorithms could be found to approximate the correct behaviour on a saturated link, while simply letting all traffic through on an unsaturated link.  Basic installations could already do this using HTB and assuming a link bandwidth.

Even better, of course, would be some system that allows BitTorrent to yield as though it were a smaller number of flows than it really is.  The "swarm" behaviour is very unusual among network protocols.  LEDBAT via uTP already does a good job on a per-flow basis, but since it's all under control of a single application, the necessary information should be available at that point.  I am reminded of the way Azureus adjusts global bandwidth limits - both incoming and outgoing - to match reality, based on both periodic and continuous measurements.

 - Jonathan Morton

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Simon Perreault]

Le 2013-05-02 14:04, Jonathan Morton a écrit :
> In short, a very large number of flow buckets prioritises BitTorrent
> over anything latency-sensitive, because BitTorrent uses a very large
> number of individual flows.

And this is exactly why (S)FQ sucks.

Need more bandwidth? Open a new socket!

Simon

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Jesper Dangaard Brouer]

On Wed, 01 May 2013 19:20:06 -0700 Simon Barber <simon@superduper.net>
wrote:

> Or one could use more queues in SFQ, so that the chance of 2 streams 
> sharing a queue is small. Even perhaps use a different strategy than 
> hashing to distribute traffic to queues, although whatever strategy
> is used needs to be resistant to DoS attacks. Or one could classify
> the VoIP traffic and prioritise that. Another possibility is a
> heuristic approach - don't mix long lived bulk data streams in the
> same bucket as others.

The Linux implementation of fq_codel is actually doing a really nice
trick to distinguish between new and old flows.  Giving new flows
precedence and avoiding they get exposed to a round-robin delay from
all the old "bulk" data streams.

A flow is considered "new" if no packets for the given flow exists in
the queue.  It does not have to be a truly new-flow, it just have to
send packets "slow"/paced enough, that the queue is empty when the next
packet arrive.

Perhaps VoIP would fit this traffic profile, and thus would work better
with the Linux fq_codel implementation, compared to the SFQ-Codel used
in the simulation.

Looking at the implementation, it does have the problem that the match
for "if the flow already have packets in the queue" just looks to see
if the hash bucket is empty.  Thus 2 stream sharing a hash queue throw
this off.

--
Best regards,
  Jesper Dangaard Brouer
  MSc.CS, Sr. Network Kernel Developer at Red Hat
  Author of http://www.iptv-analyzer.org
  LinkedIn: http://www.linkedin.com/in/brouer

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Jonathan Morton]

On 6 May, 2013, at 8:54 pm, Jesper Dangaard Brouer wrote:

> A flow is considered "new" if no packets for the given flow exists in
> the queue.  It does not have to be a truly new-flow, it just have to
> send packets "slow"/paced enough, that the queue is empty when the next
> packet arrive.
> 
> Perhaps VoIP would fit this traffic profile, and thus would work better
> with the Linux fq_codel implementation, compared to the SFQ-Codel used
> in the simulation.

That doesn't work, because the with a sufficient number of BT flows, the flow queue containing the VoIP flow is the fullest queue, not the emptiest.  That's independent of the number of flow queues, including the infinite case.  Think about it carefully.

 - Jonathan Morton

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Jesper Dangaard Brouer]

On Mon, 6 May 2013 21:46:35 +0300 Jonathan Morton
<chromatix99@gmail.com> wrote: 
> On 6 May, 2013, at 8:54 pm, Jesper Dangaard Brouer wrote:
> 
> > A flow is considered "new" if no packets for the given flow exists
> > in the queue.  It does not have to be a truly new-flow, it just
> > have to send packets "slow"/paced enough, that the queue is empty
> > when the next packet arrive.
> > 
> > Perhaps VoIP would fit this traffic profile, and thus would work
> > better with the Linux fq_codel implementation, compared to the
> > SFQ-Codel used in the simulation.
> 
> That doesn't work, because the with a sufficient number of BT flows,
> the flow queue containing the VoIP flow is the fullest queue, not the
> emptiest.  That's independent of the number of flow queues, including
> the infinite case.  Think about it carefully.

Yes, I agree.

And as I mentioned, with the fq_codel implementation details, this is
going to hit even earlier, as we have a limited number of flow/hash
queues.

> Looking at the implementation, it does have the problem that the match
> for "if the flow already have packets in the queue" just looks to see
> if the hash bucket is empty.  Thus 2 stream sharing a hash queue throw
> this off.

--
Best regards,
  Jesper Dangaard Brouer
  MSc.CS, Sr. Network Kernel Developer at Red Hat
  Author of http://www.iptv-analyzer.org
  LinkedIn: http://www.linkedin.com/in/brouer

Re: [Codel] [Cerowrt-devel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Michael Richardson]

>>>>> "Simon" == Simon Barber <simon@superduper.net> writes:
    Simon> Or one could use more queues in SFQ, so that the chance of 2
    Simon> streams sharing 
    Simon> a queue is small. Even perhaps use a different strategy than
    Simon> hashing to 
    Simon> distribute traffic to queues, although whatever strategy is
    Simon> used needs to be 
    Simon> resistant to DoS attacks. Or one could classify the VoIP traffic and
    Simon> prioritise that. Another possibility is a heuristic approach
    Simon> - don't mix long 
    Simon> lived bulk data streams in the same bucket as others.

1) try to give each IPv6 non-zero flow label stream to it's own bucket.
   (use a closed hashing strategy)
   Yes, this leverages an IPv6 feature which should promote v6...

2) otherwise, hash TCP and UDP streams into seperate pools.  On simple
   networks with no gaming, this results in VoIP RTP flows and DNS
   always getting their own stream.
   On networks with agressive UDP flows which do not react, one needs
   another method to seperate the flows and penalize them individually.
   if NAT is involved, then conn-tracking can basically give every flow
   it's own queue, because they are already uniquely identified.

   I think that the number of queues for TCP streams can be smaller than
   for UDP streams, as the TCP streams are more likely to respond to
   congestion signals.

-- 
]               Never tell me the odds!                 | ipv6 mesh networks [ 
]   Michael Richardson, Sandelman Software Works        | network architect  [ 
]     mcr@sandelman.ca  http://www.sandelman.ca/        |   ruby on rails    [ 
	

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Greg White]

BTW, the SFQ-CoDel code does support the "new" flows concept in much the
same way as the linux code, so this was already included in the simulation
results. 



On 5/6/13 2:47 PM, "Jesper Dangaard Brouer" <jbrouer@redhat.com> wrote:

>On Mon, 6 May 2013 21:46:35 +0300 Jonathan Morton
><chromatix99@gmail.com> wrote:
>> On 6 May, 2013, at 8:54 pm, Jesper Dangaard Brouer wrote:
>> 
>> > A flow is considered "new" if no packets for the given flow exists
>> > in the queue.  It does not have to be a truly new-flow, it just
>> > have to send packets "slow"/paced enough, that the queue is empty
>> > when the next packet arrive.
>> > 
>> > Perhaps VoIP would fit this traffic profile, and thus would work
>> > better with the Linux fq_codel implementation, compared to the
>> > SFQ-Codel used in the simulation.
>> 
>> That doesn't work, because the with a sufficient number of BT flows,
>> the flow queue containing the VoIP flow is the fullest queue, not the
>> emptiest.  That's independent of the number of flow queues, including
>> the infinite case.  Think about it carefully.
>
>Yes, I agree.
>
>And as I mentioned, with the fq_codel implementation details, this is
>going to hit even earlier, as we have a limited number of flow/hash
>queues.
>
>> Looking at the implementation, it does have the problem that the match
>> for "if the flow already have packets in the queue" just looks to see
>> if the hash bucket is empty.  Thus 2 stream sharing a hash queue throw
>> this off.
>
>--
>Best regards,
>  Jesper Dangaard Brouer
>  MSc.CS, Sr. Network Kernel Developer at Red Hat
>  Author of http://www.iptv-analyzer.org
>  LinkedIn: http://www.linkedin.com/in/brouer
>_______________________________________________
>Codel mailing list
>Codel@lists.bufferbloat.net
>https://lists.bufferbloat.net/listinfo/codel

Re: [Codel] [Bloat] [Cerowrt-devel] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Greg White]

This presumes that UDP is the only traffic that is latency sensitive (we
also consider web traffic to be latency sensitive), and that TCP carries
the bulk data that causes problems for latency sensitive traffic (AFAIK
BitTorrent uTP is layered on top of UDP).

I'm not sure that a TCP/UDP distinction ends up helping in the end.

-Greg



On 5/7/13 7:31 AM, "Michael Richardson" <mcr@sandelman.ca> wrote:

>
>>>>>> "Simon" == Simon Barber <simon@superduper.net> writes:
>    Simon> Or one could use more queues in SFQ, so that the chance of 2
>    Simon> streams sharing
>    Simon> a queue is small. Even perhaps use a different strategy than
>    Simon> hashing to
>    Simon> distribute traffic to queues, although whatever strategy is
>    Simon> used needs to be
>    Simon> resistant to DoS attacks. Or one could classify the VoIP
>traffic and
>    Simon> prioritise that. Another possibility is a heuristic approach
>    Simon> - don't mix long
>    Simon> lived bulk data streams in the same bucket as others.
>
>1) try to give each IPv6 non-zero flow label stream to it's own bucket.
>   (use a closed hashing strategy)
>   Yes, this leverages an IPv6 feature which should promote v6...
>
>2) otherwise, hash TCP and UDP streams into seperate pools.  On simple
>   networks with no gaming, this results in VoIP RTP flows and DNS
>   always getting their own stream.
>   On networks with agressive UDP flows which do not react, one needs
>   another method to seperate the flows and penalize them individually.
>   if NAT is involved, then conn-tracking can basically give every flow
>   it's own queue, because they are already uniquely identified.
>
>   I think that the number of queues for TCP streams can be smaller than
>   for UDP streams, as the TCP streams are more likely to respond to
>   congestion signals.
>
>-- 
>]               Never tell me the odds!                 | ipv6 mesh
>networks [ 
>]   Michael Richardson, Sandelman Software Works        | network
>architect  [ 
>]     mcr@sandelman.ca  http://www.sandelman.ca/        |   ruby on rails
>   [ 
>	
>
>_______________________________________________
>Bloat mailing list
>Bloat@lists.bufferbloat.net
>https://lists.bufferbloat.net/listinfo/bloat

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Wes Felter]

On 5/7/13 11:30 AM, Greg White wrote:
> This presumes that UDP is the only traffic that is latency sensitive (we
> also consider web traffic to be latency sensitive), and that TCP carries
> the bulk data that causes problems for latency sensitive traffic (AFAIK
> BitTorrent uTP is layered on top of UDP).
>
> I'm not sure that a TCP/UDP distinction ends up helping in the end.

I agree. We already have ToS/DiffServ so I would be hesitant to try to 
encode some other heuristic into a scheduler. (If your traffic isn't 
properly marked you can use some heuristic iptables rules to remark it, 
keeping classification orthogonal from scheduling.)

Is it time for prio_fq_codel or wfq_codel? That's what comes to mind 
when seeing the BitTorrent vs. VoIP results.

-- 
Wes Felter
IBM Research - Austin

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Eric Dumazet]

On Tue, 2013-05-07 at 14:56 -0500, Wes Felter wrote:

> Is it time for prio_fq_codel or wfq_codel? That's what comes to mind 
> when seeing the BitTorrent vs. VoIP results.

Sure !

eth=eth0
tc qdisc del dev $eth root 2>/dev/null
tc -batch << EOF
qdisc add dev $eth root handle 1: prio bands 3 
qdisc add dev $eth parent 1:1 handle 11: fq_codel
qdisc add dev $eth parent 1:2 handle 12: fq_codel
qdisc add dev $eth parent 1:3 handle 13: fq_codel
EOF

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Dave Taht]

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

Eric, you supplied the prio scheduler example as an example of how it
shouldn't work, right?

On Tue, May 7, 2013 at 1:30 PM, Eric Dumazet <eric.dumazet@gmail.com> wrote:

> On Tue, 2013-05-07 at 14:56 -0500, Wes Felter wrote:
>
> > Is it time for prio_fq_codel or wfq_codel? That's what comes to mind
> > when seeing the BitTorrent vs. VoIP results.
>
>
0) If evenly distributed, packet loss as high as reported here wouldn't
actually affect VOIP much.

I'd really like to have a better grip on the packet size, timing and other
behavior of new codecs, notably VP8. Anyone?

One thing that fq_codel enables is silence suppression actually can work,
so there is no need to send VOIP as CBR, and most speech is silence.

1)  All of the torrent clients I've looked at come, by default, with an
upload rate limiter set to a very low value in the 50-150k range, so that
the upload component of torrent problem has already been *solved via market
demand*.

I would certainly like those running windows and mac to let us know what
the defaults are on a variety of torrent these days... If everybody here
could just download one randomly

http://en.wikipedia.org/wiki/Comparison_of_BitTorrent_clients

and try it on distributing some popular, but legal data,

http://www.gutenberg.org/wiki/Gutenberg:The_CD_and_DVD_Project

through their existing gateways and/or through cerowrt/openwrt?

we'd be able to update here, and wikipedia with some info on that.

A lot of people have been running scared of torrent for a long time, and my
limited experience with current clients indicates strongly that it's not a
huge problem anymore. I tend to see torrent packets marked CS1 too, which
is either an artefact of all the DPI people ended up doing on it, or the
clients co-operating....

Also LEDBAT and uTP seem to behave very differently, and I have some doubts
about the quality of the TCP-ledbat model used in this study.

2) I have fiddled with various forms of wfq (qfq, some of my own stuff,
prioritization, and currently a toy model with a very limited number of
queues with a very well defined set of prioritizations)

3) It seems possible to make fq_codel's drop strategy a little more
aggressive when there are high numbers of flows in multiple ways.

The horizontal standing queue problem in fq_codel is bothersome and has
been discussed on this list several times since day one. It comes from the
original codel single queue "maxpacket" concept where dropping from a queue
with a single packet in it is a bad idea - among other things it might
stomp on packets in RTO or FIN, etc, etc. (note that maxpacket itself is an
artifact of the ns2 code - it may not be necessary to keep a MTU's worth of
packets around, merely a single packet might be fine)

I long ago created a version of codel (codel3.h) that ripped out all single
queue assumptions from the codel code... in preparation for finding
something that worked better when there were multiple queues in play.

I have a "special" version of fq_codel (efq_codel) in cerowrt where I have
fiddled with various tweaks and tests and options. I've been pretty good
about not documenting this until now, because everything I've tried to date
was not much of an improvement, (nor did I have the robust set of test and
edge cases I do now)

My most recent idea for increasing fq_codel drop behavior under load
involves relaxing the exit-the-drop-scheduler-at-maxpacket strategy when it
would otherwise drop, and the measured delay in that fq_codel queue exceeds
the current interval * X, maybe with an added qualification of packet size
> 1000.

It's hacky but I've repeatedly proven to myself that the most trivial of
changes like this can have enormous side effects... and this is targetted
specifically at the behavior of torrents, as best as I understand it.






> Sure !
>
> eth=eth0
> tc qdisc del dev $eth root 2>/dev/null
> tc -batch << EOF
> qdisc add dev $eth root handle 1: prio bands 3
> qdisc add dev $eth parent 1:1 handle 11: fq_codel
> qdisc add dev $eth parent 1:2 handle 12: fq_codel
> qdisc add dev $eth parent 1:3 handle 13: fq_codel
> EOF
>
>
Heh. I am hoping you are providing this as a negative proof!? as the strict
prioritization of this particular linux scheduler means that a single full
rate TCP flow in class 1:1 will completely starve classes 1:2 and 1:3.


..snip snip..

static struct sk_buff *prio_dequeue(struct Qdisc *sch)
{
        struct prio_sched_data *q = qdisc_priv(sch);
        int prio;

        for (prio = 0; prio < q->bands; prio++) {
                struct Qdisc *qdisc = q->queues[prio];
                struct sk_buff *skb = qdisc_dequeue_peeked(qdisc);
                if (skb) {
                        qdisc_bstats_update(sch, skb);
                        sch->q.qlen--;
                        return skb;
                }
        }
        return NULL;

}



Some level of fairness between service classes is needed too. My most
common setting for the "cake" shaper has been 20% minimum for the
background traffic, for example. I am unsure if codel is really the right
thing for the highest priority qdisc, as everything

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



-- 
Dave Täht

Fixing bufferbloat with cerowrt:
http://www.teklibre.com/cerowrt/subscribe.html

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

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Eric Dumazet]

On Wed, 2013-05-08 at 15:25 -0700, Dave Taht wrote:


> Heh. I am hoping you are providing this as a negative proof!? as the
> strict prioritization of this particular linux scheduler means that a
> single full rate TCP flow in class 1:1 will completely starve classes
> 1:2 and 1:3.
> 
> Some level of fairness between service classes is needed too. My most
> common setting for the "cake" shaper has been 20% minimum for the
> background traffic, for example. I am unsure if codel is really the
> right thing for the highest priority qdisc, as everything
> 

PRIO qdisc does strict priority, like pfifo_fast.

If your high prio traffic is also using 100% of the bandwith, then there
is a fundamental problem about classifying this so called high prio
traffic.

On my hosts, high prio traffic uses less than 0.1 % of the bandwidth,
so I do not need to have DRR kind of setup.

And the low priority traffic has no minimum guaranteed bandwidth.

There is no 'magic solution' for every needs. The solution I gave is
good enough if you need to have some strict priorities, as a replacement
to current pfifo_fast, and if all traffic is not miss classified.

A setup using DRR instead of PRIO is also possible.

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Andrew McGregor]

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

Strict priority plays very badly with unmanaged devices... HTB or DRR will
have many fewer 'the network is broken' corner cases.

Or indeed, fq_codel extended with more queue lists and a matrix of
transition rules.


On Thu, May 9, 2013 at 8:54 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:

> On Wed, 2013-05-08 at 15:25 -0700, Dave Taht wrote:
>
>
> > Heh. I am hoping you are providing this as a negative proof!? as the
> > strict prioritization of this particular linux scheduler means that a
> > single full rate TCP flow in class 1:1 will completely starve classes
> > 1:2 and 1:3.
> >
> > Some level of fairness between service classes is needed too. My most
> > common setting for the "cake" shaper has been 20% minimum for the
> > background traffic, for example. I am unsure if codel is really the
> > right thing for the highest priority qdisc, as everything
> >
>
> PRIO qdisc does strict priority, like pfifo_fast.
>
> If your high prio traffic is also using 100% of the bandwith, then there
> is a fundamental problem about classifying this so called high prio
> traffic.
>
> On my hosts, high prio traffic uses less than 0.1 % of the bandwidth,
> so I do not need to have DRR kind of setup.
>
> And the low priority traffic has no minimum guaranteed bandwidth.
>
> There is no 'magic solution' for every needs. The solution I gave is
> good enough if you need to have some strict priorities, as a replacement
> to current pfifo_fast, and if all traffic is not miss classified.
>
> A setup using DRR instead of PRIO is also possible.
>
>
> _______________________________________________
> Codel mailing list
> Codel@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/codel
>

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

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Dan Siemon]

On Thu, 2013-05-02 at 15:04 +0300, Jonathan Morton wrote:
> I can easily see a four-tier system working for most consumers, just
> so long as the traffic for each tier can be identified - each tier
> would have it's own fq_codel queue:
> 
> 1) Network control traffic, eg. DNS, ICMP, even SYNs and pure ACKs -
> max 1/16th bandwidth, top priority
> 
> 2) Latency-sensitive unresponsive flows, eg. VoIP and gaming - max 1/4
> bandwidth, high priority
> 
> 3) Ordinary bulk traffic, eg. web browsing, email, general purpose
> protocols - no bandwidth limit, normal priority
> 
> 4) Background traffic, eg. BitTorrent - no bandwidth limit, low
> priority, voluntarily marked, competes at 1:4 with normal.

The above is close to what I implemented:
http://git.coverfire.com/?p=linux-qos-scripts.git;a=blob;f=src-3tos.sh;h=3e88c2fa5f2feb0163c052086541ba17579a3c37;hb=HEAD

The above aims for per-host fairness and three tiers per host. Each tier
has an fq_codel QDisc (configurable).

Some performance results can be found at:
http://www.coverfire.com/archives/2013/01/01/improving-my-home-internet-performance/

It's pretty easy to configure the Transmission Bittorrent client to mark
packets.

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Tristan Seligmann]

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

On Tue, May 14, 2013 at 4:26 AM, Dan Siemon <dan@coverfire.com> wrote:

> It's pretty easy to configure the Transmission Bittorrent client to mark
> packets.
>

 Unfortunately this only helps with outgoing traffic. Marking on inbound
traffic is at the mercy of the torrent peer and your ISP (in my case, my
ISP seems to overwrite the TOS/DS field indiscriminately, not that you
would want to trust the marking for inbound traffic anyway), and matching
by port is also not feasible as outgoing connections involve a random port
on my side, and an arbitrary port on the peer's side.
-- 
mithrandi, i Ainil en-Balandor, a faer Ambar

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

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Dave Taht]

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

On Mon, May 13, 2013 at 9:56 PM, Tristan Seligmann
<mithrandi@mithrandi.net>wrote:

> On Tue, May 14, 2013 at 4:26 AM, Dan Siemon <dan@coverfire.com> wrote:
>
>> It's pretty easy to configure the Transmission Bittorrent client to mark
>> packets.
>>
>
It is not clear to me that transmission correctly marks uTP traffic,
particularly on IPv6. grep the current sources for "TCLASS"?


>
>  Unfortunately this only helps with outgoing traffic. Marking on inbound
> traffic is at the mercy of the torrent peer and your ISP (in my case, my
> ISP seems to overwrite the TOS/DS field indiscriminately, not that you
> would want to trust the marking for inbound traffic anyway), and matching
> by port is also not feasible as outgoing connections involve a random port
> on my side, and an arbitrary port on the peer's side.
>

It is very evident that incoming traffic needs to be re-marked at the
gateway, as a huge percentage of traffic I see at one of my sites is marked
background that shouldn't be. (or there's a bug in my script)

Inappropriately marking traffic as background has side effects on stuff
inside the gateway, particularly on wifi, as it gets tossed into the hw
background queue, which has different scheduling characteristics than best
effort.

As for dealing with incoming vs outgoing traffic, it might be possible to
use connection tracking to successfully re-mark traffic on incoming to
match the outgoing.



> --
> mithrandi, i Ainil en-Balandor, a faer Ambar
>
> _______________________________________________
> Bloat mailing list
> Bloat@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/bloat
>
>


-- 
Dave Täht

Fixing bufferbloat with cerowrt:
http://www.teklibre.com/cerowrt/subscribe.html

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

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Jesper Dangaard Brouer]

On Mon, 13 May 2013 22:26:04 -0400
Dan Siemon <dan@coverfire.com> wrote:

> On Thu, 2013-05-02 at 15:04 +0300, Jonathan Morton wrote:
> > I can easily see a four-tier system working for most consumers, just
> > so long as the traffic for each tier can be identified - each tier
> > would have it's own fq_codel queue:

I generally like it, but some notes below.

> > 1) Network control traffic, eg. DNS, ICMP, even SYNs and pure ACKs -
> > max 1/16th bandwidth, top priority

I used a separate queue for ACK packets, and directly calculated the
needed bandwidth for ACK packets based on the downstream link.
See:
 http://sourceforge.net/p/adsl-optimizer/code/HEAD/tree/trunk/kode/optimizer/queues/include/functions.inc#l94

(My future idea was to implement an ACK aware qdisc, that would drop
accumulative ACK packets or delay ACKs to influence downstream behavior)

> > 2) Latency-sensitive unresponsive flows, eg. VoIP and gaming - max
> > 1/4 bandwidth, high priority
> > 
> > 3) Ordinary bulk traffic, eg. web browsing, email, general purpose
> > protocols - no bandwidth limit, normal priority

So, these two above is "known-good" traffic, that gets categorized into
these.

> > 4) Background traffic, eg. BitTorrent - no bandwidth limit, low
> > priority, voluntarily marked, competes at 1:4 with normal.

I worked with two classes for this, (1) a default fall-through traffic
class, where uncategorized traffic end-up. (2) a known "bad" low-prio
traffic class, for traffic I could categorize as BitTorrent etc.

http://sourceforge.net/p/adsl-optimizer/code/HEAD/tree/trunk/kode/optimizer/queues/htb/optimizer_htb.sh#l227


> The above is close to what I implemented:
> http://git.coverfire.com/?p=linux-qos-scripts.git;a=blob;f=src-3tos.sh;h=3e88c2fa5f2feb0163c052086541ba17579a3c37;hb=HEAD

Nice, and thank you for mentioning my (old) site: http://www.adsl-optimizer.dk

And actually have a script that mentions (and can use) the ADSL
linklayer options :-)


> The above aims for per-host fairness and three tiers per host. Each
> tier has an fq_codel QDisc (configurable).
> 
> Some performance results can be found at:
> http://www.coverfire.com/archives/2013/01/01/improving-my-home-internet-performance/

p.s. I love your "ping-exp" tool and the nice graphs it generates!

Others go clone:
 git clone http://git.coverfire.com/ping-exp.git


-- 
Best regards,
  Jesper Dangaard Brouer
  MSc.CS, Sr. Network Kernel Developer at Red Hat
  Author of http://www.iptv-analyzer.org
  LinkedIn: http://www.linkedin.com/in/brouer

Re: [Codel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Eric Dumazet]

On Tue, 2013-05-14 at 03:24 -0700, Dave Taht wrote:

> 
> As for dealing with incoming vs outgoing traffic, it might be possible
> to use connection tracking to successfully re-mark traffic on incoming
> to match the outgoing. 

Indeed, we had a discussion about that during Netfilter workshop 2013 in
Copenhagen.

(ability to use conntracking from ingress tc filter)

Re: [Codel] [Cerowrt-devel] [Bloat] Latest codel, fq_codel, and pie sim study from cablelabs now available

[Michael Richardson]

>>>>> "Tristan" == Tristan Seligmann <mithrandi@mithrandi.net> writes:
    >> It's pretty easy to configure the Transmission Bittorrent client to mark
    >> packets.
    >> 

    Tristan> Unfortunately this only helps with outgoing traffic. Marking on inbound
    Tristan> traffic is at the mercy of the torrent peer and your ISP (in my case, my
    Tristan> ISP seems to overwrite the TOS/DS field indiscriminately,
    Tristan> not that you

Ultimately, one wants PCP and/or RSVP and/or NSIS from the torrent
client to the local router, as the torrent client knows the 5-tuple of
the incoming packets.  Local router would in utopian world, in a diffedge
scenario be able to communicate that policy to ISP edge router, but at
least, the local router can police that flow.

-- 
]               Never tell me the odds!                 | ipv6 mesh networks [ 
]   Michael Richardson, Sandelman Software Works        | network architect  [ 
]     mcr@sandelman.ca  http://www.sandelman.ca/        |   ruby on rails    [