[LARTC] SFQ improvement ideas

[LARTC] SFQ improvement ideas

[devik]

Hello,

I've several ideas. Maybe someone has some time to implement them ?

1) Backlog depth limit

Currently total limit of SFQ is 128 packets. SFQ tries
to keep lengths of all flows to be roughly the same. It
means that there can be one flow with 128 packets backlog.

It would be nice to have control over maximal lenght of
backlog. To be able to control max delay introduced.

2) Interactive traffic isolation

Cisco IOS implements WFQ which has one queue per flow and
common queue for interactive traffic. Packets are queued
into interactive queue for some time and after it is clear
that they constitute large flow they are assigned private
queue. Interactive queue has higher prio.

Nice effect is that short conversations are handled faster
and long downloads are isolated with lower priority.

It could be implemented in SFQ by attaching token bucket filter
to each flow bucket (there is 1024 buckets). If the flow conforms
to the bucket then it is low-load traffic (interactive) and
hi-load otherwise.
Dequeue routine should be changed to DRR dequeue from low-load
flows then hi-load then again lo-load ....
In other words to perform DRR among two DRRs.

Of course one couldn't use "perturb" here as it would fool bucket
filters.

3) Hash select

Default SFQ impl. uses src(ip+port)+dst(ip+port) to distinguish
connections. It might be useful to be able to set src(ip)+dst(ip)
for example (do disallow users to fool SFQ by creating more connections)
or src(ip)+dst(ip+port) to make it yet better. I'd suggest tc
parameters like "hash " followed by set of "dip,sip,sport,dport,proto"
arguments (e.g. ... sfq hash dip sip dport).


Comments, ideas, volunteers ?
devik


_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

Re: [LARTC] SFQ improvement ideas

[John Huttley]

----- Original Message ----- 
From: "devik" <devik@cdi.cz>
To: <lartc@mailman.ds9a.nl>
Sent: Monday, January 14, 2002 8:21 AM
Subject: [LARTC] SFQ improvement ideas


> Hello,
> 
> I've several ideas. Maybe someone has some time to implement them ?

I can't program, but I can think of one other thing..

Thats the ability to adjust rate limits dynamically ( /proc?)

At the moment the quickest, easiest way of changing things is to reboot.

tc change   is too painful to use.

Regards
John


_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

Re: [LARTC] SFQ improvement ideas

[Daniel Wittenberg]

To change, can't you just do:
tc del dev eth0 root handle 1:

(or whatever your handles are, you get the idea)

Shouldn't that essentially "flush" all the shaping under then 1: handle?

Dan

On Sun, 2002-01-13 at 15:06, John Huttley wrote:
> 
> ----- Original Message ----- 
> From: "devik" <devik@cdi.cz>
> To: <lartc@mailman.ds9a.nl>
> Sent: Monday, January 14, 2002 8:21 AM
> Subject: [LARTC] SFQ improvement ideas
> 
> 
> > Hello,
> > 
> > I've several ideas. Maybe someone has some time to implement them ?
> 
> I can't program, but I can think of one other thing..
> 
> Thats the ability to adjust rate limits dynamically ( /proc?)
> 
> At the moment the quickest, easiest way of changing things is to reboot.
> 
> tc change   is too painful to use.
> 
> Regards
> John
> 
> 
> _______________________________________________
> LARTC mailing list / LARTC@mailman.ds9a.nl
> http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/



_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

Re: [LARTC] SFQ improvement ideas

[John Huttley]

> To change, can't you just do:
> tc del dev eth0 root handle 1:
>
> (or whatever your handles are, you get the idea)
>
> Shouldn't that essentially "flush" all the shaping under then 1: handle?

This is not a valid command.

The other way is to stop and start networking. Really, I'd just rather
reboot and be done with it.

Regards

John



_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

Re: [LARTC] SFQ improvement ideas

[Daniel Wittenberg]

really?  I didn't see it complaining, and it appeared to be so by the
help if you look at the docs...so what is this really doing, and what is
the del command for?  I'm just learning, so I'm only going by what I've
read so far.

*is now confused*

Dan

On Sun, 2002-01-13 at 20:02, John Huttley wrote:
> 
> 
> > To change, can't you just do:
> > tc del dev eth0 root handle 1:
> >
> > (or whatever your handles are, you get the idea)
> >
> > Shouldn't that essentially "flush" all the shaping under then 1: handle?
> 
> This is not a valid command.
> 
> The other way is to stop and start networking. Really, I'd just rather
> reboot and be done with it.
> 
> Regards
> 
> John
> 
> 
> 
> _______________________________________________
> LARTC mailing list / LARTC@mailman.ds9a.nl
> http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/


_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

[LARTC] SFQ improvement ideas

[Don Cohen]

I'm glad to see this, since I was planning to make a similar proposal.

 > 1) Backlog depth limit
 > 
 > Currently total limit of SFQ is 128 packets. SFQ tries
 > to keep lengths of all flows to be roughly the same. It
 > means that there can be one flow with 128 packets backlog.
 > 
 > It would be nice to have control over maximal lenght of
 > backlog. To be able to control max delay introduced.

I have an alternative suggestion, which I think might profitably be
added to a number of qdiscs:
 a parameter for the maximum delay allowed for forwarded packets
When you dequeue a packet that is older than that (current time minus
arrival time stamp) you drop it.

This seems trivial to implement and accomplishes the goal much more 
accurately than limiting the size of a flow.  The time a packet spends
in the queue is determined by how many packets arrive for other flows
as well as the length of its own.  The worst case is that it's at the
end of a long flow, say 64 long, and 64 other flows are sending
packets just in time to be served.  So it has to wait for 64 other
packets for each packet ahead of it in its own flow.  And, of course,
to add to the delay, all of the packets involved could be long.

On the other hand a packet that's 128'th in its own queue might only
have to wait for 127 other packets to be sent, and if they're all
short this might not be a long time.

It seems more reasonable to just say don't bother to send any packets
over 5 sec old.

 > 2) Interactive traffic isolation
 > 
 > Cisco IOS implements WFQ which has one queue per flow and
 > common queue for interactive traffic. Packets are queued
 > into interactive queue for some time and after it is clear
 > that they constitute large flow they are assigned private
 > queue. Interactive queue has higher prio.
I was not aware of this distinction between interactive an other.
How do you recognize interactive other than by low rate?
Do you have a pointer to doc?  

 > Nice effect is that short conversations are handled faster
 > and long downloads are isolated with lower priority.
Isn't this just what you get from a queue for each flow?
I thought that's what WFQ did.

 > 3) Hash select
 > 
 > Default SFQ impl. uses src(ip+port)+dst(ip+port) to distinguish
 > connections. It might be useful to be able to set src(ip)+dst(ip)
 > for example (do disallow users to fool SFQ by creating more connections)
 > or src(ip)+dst(ip+port) to make it yet better. I'd suggest tc
 > parameters like "hash " followed by set of "dip,sip,sport,dport,proto"
 > arguments (e.g. ... sfq hash dip sip dport).

I agree (in fact was going to propose exactly this).
The real use I see is that people keep asking for what amounts to hash
only on one address (e.g., fair service to all internal machines).
_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

Re: [LARTC] SFQ improvement ideas

[Martin Devera]

> > To change, can't you just do:
> > tc del dev eth0 root handle 1:
> >
> > (or whatever your handles are, you get the idea)
> >
> > Shouldn't that essentially "flush" all the shaping under then 1: handle?
> 
> This is not a valid command.
> 
> The other way is to stop and start networking. Really, I'd just rather
> reboot and be done with it.

The command is not exactly as it should be but when you
write it correcly it works.
I don't reboot my routers because it'd disrupt a traffic. 
Rather I use tc change or tc del and it works perfectly here.
If not, report it as bug.
devik

_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

Re: [LARTC] SFQ improvement ideas

[Martin Devera]

It should be tc qdisc del .... You miss the "qdisc".
devik

> really?  I didn't see it complaining, and it appeared to be so by the
> help if you look at the docs...so what is this really doing, and what is
> the del command for?  I'm just learning, so I'm only going by what I've
> read so far.

_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

Re: [LARTC] SFQ improvement ideas

[Martin Devera]

> I can't program, but I can think of one other thing..
> Thats the ability to adjust rate limits dynamically ( /proc?)
> At the moment the quickest, easiest way of changing things is to reboot.
> tc change   is too painful to use.

it is not the best interface I can imagine but it works.
You only need to know how to use it. Why don't use /proc ?
Read archives. There are reasons (ANK stated them IIRC).
devik

_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

Re: [LARTC] SFQ improvement ideas

[Martin Devera]

> I have an alternative suggestion, which I think might profitably be
> added to a number of qdiscs:
>  a parameter for the maximum delay allowed for forwarded packets
> When you dequeue a packet that is older than that (current time minus
> arrival time stamp) you drop it.

It would be definitely nice. But it is not cheap to implement.
SFQ has constant complexity. To discard old packets you would need
either sorted queues (log N) or cycle on head of queue until all
expired ones are deleted. But it doesn't preserve fairnes IMHO.
In any way I'll think about it :)

>  > 2) Interactive traffic isolation
>  > 
>  > Cisco IOS implements WFQ which has one queue per flow and
>  > common queue for interactive traffic. Packets are queued
>  > into interactive queue for some time and after it is clear
>  > that they constitute large flow they are assigned private
>  > queue. Interactive queue has higher prio.
> I was not aware of this distinction between interactive an other.
> How do you recognize interactive other than by low rate?
> Do you have a pointer to doc?  

it is better determined by bytes send. Hi-load traffic is for
example long ftp download.. I'm not sure how to detect them yet.
See www.cisco.com, IOS documentation, QoS section.

>  > Nice effect is that short conversations are handled faster
>  > and long downloads are isolated with lower priority.
> Isn't this just what you get from a queue for each flow?
> I thought that's what WFQ did.

No. For flows A,B,C,X where X is interactive one the nornal SFQ 
schedule is: ABCDXABCDX.... and WFQ is AXBXCXAXBXCX.... Thus lower
delay.

>  > parameters like "hash " followed by set of "dip,sip,sport,dport,proto"
>  > arguments (e.g. ... sfq hash dip sip dport).
> 
> I agree (in fact was going to propose exactly this).
> The real use I see is that people keep asking for what amounts to hash
> only on one address (e.g., fair service to all internal machines).

Fine. We can agree on this one. You did some things with SFQ,
could you implement it ?
devik

_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

Re: [LARTC] SFQ improvement ideas

[Michael T. Babcock]

On Sun, Jan 13, 2002 at 08:21:51PM +0100, devik wrote:
> 1) Backlog depth limit

This would be nice; through proc ... but I believe it is
already being worked on by Alexey.

> 2) Interactive traffic isolation

SFQ is designed specifically to _not_ have manual isolation
of queues; use CBQ with SFQ to do this.

CBQ (all) ---- (filter interactive) --- SFQ #1
           \-- (filter everything else) --- SFQ #2

SFQ uses a hashing system to distinguish flows which is fast;
eliminating that would slow it down.  If you want simplicity
(and not CBQ), use HTB.  A classful round-robin queue would
be nice (which would do what you describe), but it would be
placed the way CBQ is above.

> 3) Hash select
> 
> Default SFQ impl. uses src(ip+port)+dst(ip+port) to distinguish
> connections. It might be useful to be able to set src(ip)+dst(ip)
> for example (do disallow users to fool SFQ by creating more connections)
> or src(ip)+dst(ip+port) to make it yet better. I'd suggest tc
> parameters like "hash " followed by set of "dip,sip,sport,dport,proto"
> arguments (e.g. ... sfq hash dip sip dport).

I agree here; it would probably be easier to just turn on or off each of
the hash criteria.

tc qdisc add dev eth0 sfq hash sip hash dip hash dport
or
tc qdisc add dev eth0 sfq hash sip hash dip
-- 
Michael T. Babcock
CTO, FibreSpeed Ltd.     (Hosting, Security, Consultation, Database, etc)
http://www.fibrespeed.net/~mbabcock/
_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

Re: [LARTC] SFQ improvement ideas

[Don Cohen]

 > From: Martin Devera <devik@cdi.cz>
 > > I have an alternative suggestion, which I think might profitably be
 > > added to a number of qdiscs:
 > >  a parameter for the maximum delay allowed for forwarded packets
 > > When you dequeue a packet that is older than that (current time minus
 > > arrival time stamp) you drop it.
 > 
 > It would be definitely nice. But it is not cheap to implement.
 > SFQ has constant complexity. To discard old packets you would need
 > either sorted queues (log N) or cycle on head of queue until all
 > expired ones are deleted. But it doesn't preserve fairnes IMHO.
 > In any way I'll think about it :)
You're thinking of removing a packet when it has been in the queue too
long.  I'm thinking of something much easier.  When you dequeue just
check to see it's not too old.  If it is then discard it and go on to
the next one.  I admit that this could result in a large amount of
work for one packet dequeued, but that work translates into much more
time saved by not sending old packets.

 > >  > 2) Interactive traffic isolation
 > >  > 
 > >  > Cisco IOS implements WFQ which has one queue per flow and
 > >  > common queue for interactive traffic. Packets are queued
 > >  > into interactive queue for some time and after it is clear
 > >  > that they constitute large flow they are assigned private
 > >  > queue. Interactive queue has higher prio.
 > > I was not aware of this distinction between interactive an other.
 > > How do you recognize interactive other than by low rate?
 > > Do you have a pointer to doc?  
 > 
 > it is better determined by bytes send. Hi-load traffic is for
 > example long ftp download.. I'm not sure how to detect them yet.
 > See www.cisco.com, IOS documentation, QoS section.
I have looked there.  Perhaps we simply interpret the contents
differently.  

 > >  > Nice effect is that short conversations are handled faster
 > >  > and long downloads are isolated with lower priority.
 > > Isn't this just what you get from a queue for each flow?
 > > I thought that's what WFQ did.
 > 
 > No. For flows A,B,C,X where X is interactive one the nornal SFQ 
 > schedule is: ABCDXABCDX.... and WFQ is AXBXCXAXBXCX.... Thus lower
 > delay.
(Except for the D's I guess.)
Again, where do you see this?  I've not seen anything in Cisco doc
that says this.

 > >  > parameters like "hash " followed by set of "dip,sip,sport,dport,proto"
 > >  > arguments (e.g. ... sfq hash dip sip dport).
 > > 
 > > I agree (in fact was going to propose exactly this).
 > > The real use I see is that people keep asking for what amounts to hash
 > > only on one address (e.g., fair service to all internal machines).
 > 
 > Fine. We can agree on this one. You did some things with SFQ,
 > could you implement it ?
Maybe, but not immediately.

 > 
 > 
 > 
 > --__--__--
 > 
 > _______________________________________________
 > LARTC mailing list
 > LARTC@mailman.ds9a.nl
 > http://mailman.ds9a.nl/mailman/listinfo/lartc
 > 
 > 
 > End of LARTC Digest
_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

Re: [LARTC] SFQ improvement ideas

[Martin Devera]

> > 1) Backlog depth limit
> 
> This would be nice; through proc ... but I believe it is
> already being worked on by Alexey.

How do you know it ? I'd like to have such info too :)
By the way what is he working on ? Depth limit or proc interface ?
 
> > 2) Interactive traffic isolation
> 
> SFQ is designed specifically to _not_ have manual isolation
> of queues; use CBQ with SFQ to do this.

I know. But I want it to do automatic isolation. Based on
life of connection. When connection is determined to be
long download then it will resort into another queue.
But you may be right. Recently I started to think to use
iptables connection tracking to find these and use filters
to assign them different sfq ..

> (and not CBQ), use HTB.  A classful round-robin queue would

grrr .. I didn't design HTB just for simplicity but for
precise results ;-)

> > parameters like "hash " followed by set of "dip,sip,sport,dport,proto"
> > arguments (e.g. ... sfq hash dip sip dport).
> 
> I agree here; it would probably be easier to just turn on or off each of
> the hash criteria.
> 
> tc qdisc add dev eth0 sfq hash sip hash dip hash dport
> or
> tc qdisc add dev eth0 sfq hash sip hash dip

well it was my first idea but then I realized that it would be 
complex to do tc .. change on it. Maybe we could introduce
nohash too ..

devik

_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

Re: [LARTC] SFQ improvement ideas

[Martin Devera]

>  > either sorted queues (log N) or cycle on head of queue until all
>  > expired ones are deleted. But it doesn't preserve fairnes IMHO.
>  > In any way I'll think about it :)
> You're thinking of removing a packet when it has been in the queue too
> long.  I'm thinking of something much easier.  When you dequeue just
> check to see it's not too old.  If it is then discard it and go on to
> the next one.  I admit that this could result in a large amount of
> work for one packet dequeued, but that work translates into much more
> time saved by not sending old packets.

It is exactly what I meant by "cycle on head of queue". But
compare it with queue depth limiting. When you know rate and depth
you can compute the oldest packet on the queue. So that it will
assure the same for you but with less of work and less of storage
(packets are dropped at enqueue). 
 
>  > it is better determined by bytes send. Hi-load traffic is for
>  > example long ftp download.. I'm not sure how to detect them yet.
>  > See www.cisco.com, IOS documentation, QoS section.
> I have looked there.  Perhaps we simply interpret the contents
> differently.  

Maybe :) How do you interpret it ?
 
>  > >  > Nice effect is that short conversations are handled faster
>  > >  > and long downloads are isolated with lower priority.
>  > > Isn't this just what you get from a queue for each flow?
>  > > I thought that's what WFQ did.
>  > 
>  > No. For flows A,B,C,X where X is interactive one the nornal SFQ 
>  > schedule is: ABCDXABCDX.... and WFQ is AXBXCXAXBXCX.... Thus lower
>  > delay.
> (Except for the D's I guess.)
> Again, where do you see this?  I've not seen anything in Cisco doc
> that says this.

I quote: 
(http://www.cisco.com/univercd/cc/td/doc/product/software/ios113ed/113ed_cr/fun_c/fcprt4/fcperfrm.htm#xtocid128886)
------
Weighted fair queueing can manage duplex data streams, such as those
between pairs of applications, and simplex data streams such as voice
or video. From the perspective of weighted fair queueing, there are two
categories of data streams: high-bandwidth sessions and low-bandwidth
sessions. Low-bandwidth traffic has effective priority over high-bandwidth
traffic, and high-bandwidth traffic shares the transmission service
proportionally according to assigned weights. 
------

devik

_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/