[Codel] FQ_Codel v. FQ_LQD

[Codel] FQ_Codel v. FQ_LQD

[James Roberts]

I have not been following Bufferbloat but a colleague forwarded to me the latest post from Dave Täht about FQ_Codel. It is good to see the virtues of fair queuing are being rediscovered. 

I think the work by Suter and co-authors on FQ in high capacity routers is particularly relevant:

B. Suter, T. Lakshman, D. Stiliadis, A. Choudhury, Buffer Management Schemes
for Supporting TCP in Gigabit Routers with Per-Flow Queuing, IEEE Journal in
Selected Areas un Communications, August 1999. (http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=772451)

They may have been the first to introduce "head drop". Actually they advocated dropping from the front of the flow queue with longest backlog (FQ_LQD). I am not sure why a more sophisticated AQM, like RED, ARED or Codel, is better than longest queue drop.

Another advantage of FQ_Codel highlighted in the report by Toke Høiland-Jørgensen (notified on the list) is to give priority to packets of newly active flows. This idea was already proposed in our papers:

A. Kortebi, S. Oueslati and J. Roberts. Cross-protect: implicit service differentiation and admission control,  IEEE HPSR 2004, Phoenix, USA, April 2004. 
A. Kortebi, S. Oueslati, J. Roberts. Implicit service differentiation using Deficit Round Robin,  Proceedings of ITC 19, Beijing, August 2005. 

I have long been advocating per flow fairness as the basis of effective traffic control so I hope you won't mind me recalling this prior work.

Jim Roberts

Re: [Codel] FQ_Codel v. FQ_LQD

[Dave Taht]

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

Also nice:

http://perso.rd.francetelecom.fr/oueslati/Pub/xp-hpsr.pdf

I'd been just down the street from you (at LINCS) multiple times in the
past year. Pouring through the rest of your canon now...

as for your referenced:

http://www.tlc-networks.polito.it/oldsite/muscariello/papers/Kortebi-f18.pdf

It is unfortunate that Stochastic Fair Queueing and and "Start Time Fair
Queuing" have an overloaded acronym. But I tend to agree that "flow" is the
word we should be using rather than "fair". Good stuff, tho, and shows a
potential hardware implementation....

As for codel vs "longest queue drop" - codel is tcp friendly, and with the
early signalling can drop from the head of multiple queues where they are
exceeding the target delay rather than just the largest one. And it drops
gently (being tcp friendly), working on end to end signaling rather than
attacking the immediate source of congestion.

The "drop from longest queue" IS an error out condition in fq_codel, but
it's rarely hit (and rather cpu intensive when it is hit) as queue length
is managed long beforehand by codel.

I do regard admission control and slow start behavior as something of an
ongoing problem and more work on this front is indicated.

I just gave a talk on some of this at stanford (
http://netseminar.stanford.edu )

I just finished reading your 1999 paper. Very, very nice.

http://ect.bell-labs.com/who/stiliadi/papers/jsac99.pdf

I will update my fq_codel slides to point to the 1996 paper as to 'first
implementation" of head drop, but now that I know another phrase for it,
perhaps it goes back even further than this?

"T. Lakshman, A. Neidhart, and T. Ott, “The drop-from-front strategy in TCP
over ATM and its interworking with other control features,” in Proceedings
of IEEE INFOCOM’96, (San Francisco, CA), pp. 1242–1250, 1996."


Lastly, from the conclusion:

 "When TCP has to compete with more aggressive sources or in asymmetric
networks, with a perpetu- ally congested reverse path , FCFS-RED, FQ-RED or
any other global dropping policy perform very poorly.

The decision of whether to incur the expense of fair queueing depends on
the performance and sta- bility expected of the system. We have shown that
by using fair queueing in combination with appro- priate packet dropping
(and not by fair queueing alone) performance and fairness is enhanced in
any case but particularly in situations that involve loss insensitive,
non-responsive flows.

If the simplicity of FCFS is to be traded for the higher stability and
fairness of fair queueing, then there is little reason to persist with
using a global dropping strategy. For little additional cost, ALQD can
complement an efficient WFQ scheduling im- plementation to provide good
fairness and provide nearly perfect flow isolation and protection."

After running more traffic than I care to think about through qfq+codel,
fq_codel and sfqred... agree with the experimental methods in the paper...
and with the conclusion. Nice work. Sure wish I'd known of it a while ago...



On Tue, Feb 12, 2013 at 4:29 AM, James Roberts <James.Roberts@inria.fr>wrote:

> I have not been following Bufferbloat but a colleague forwarded to me the
> latest post from Dave Täht about FQ_Codel. It is good to see the virtues of
> fair queuing are being rediscovered.
>
> I think the work by Suter and co-authors on FQ in high capacity routers is
> particularly relevant:
>
> B. Suter, T. Lakshman, D. Stiliadis, A. Choudhury, Buffer Management
> Schemes
> for Supporting TCP in Gigabit Routers with Per-Flow Queuing, IEEE Journal
> in
> Selected Areas un Communications, August 1999. (
> http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=772451)
>
> They may have been the first to introduce "head drop". Actually they
> advocated dropping from the front of the flow queue with longest backlog
> (FQ_LQD). I am not sure why a more sophisticated AQM, like RED, ARED or
> Codel, is better than longest queue drop.
>
> Another advantage of FQ_Codel highlighted in the report by Toke
> Høiland-Jørgensen (notified on the list) is to give priority to packets of
> newly active flows. This idea was already proposed in our papers:
>
> A. Kortebi, S. Oueslati and J. Roberts. Cross-protect: implicit service
> differentiation and admission control,  IEEE HPSR 2004, Phoenix, USA, April
> 2004.
> A. Kortebi, S. Oueslati, J. Roberts. Implicit service differentiation
> using Deficit Round Robin,  Proceedings of ITC 19, Beijing, August 2005.
>
> I have long been advocating per flow fairness as the basis of effective
> traffic control so I hope you won't mind me recalling this prior work.
>
> Jim Roberts
> _______________________________________________
> Codel mailing list
> Codel@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/codel
>



-- 
Dave Täht

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

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