Skip to contentSkip to conversation

SFQ improvement ideas

LARTC devik 5 participants 14 messages Jan 13, 2002 – Jan 16, 2002

lore
Share & tools
lore

devik

author
#0 lore raw

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 / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

#1 lore raw

----- Original Message -----
From: "devik" <[email protected]>
To: <[email protected]>
Sent: Monday, January 14, 2002 8:21 AM
Subject: [LARTC] SFQ improvement ideas

Quoted 3 lines

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 / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

#2 lore raw
In reply to devik

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

Quoted 20 lines · John Huttley

----- Original Message -----
From: "devik" <[email protected]>
To: <[email protected]>
Sent: Monday, January 14, 2002 8:21 AM
Subject: [LARTC] SFQ improvement ideas

Quoted 3 lines

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.

Quoted 7 lines

Regards
John

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

#3 lore raw
In reply to devik
Quoted 8 lines

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 / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

#4 lore raw
In reply to 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.

*is now confused*

Dan

Quoted 16 lines · John Huttley
Quoted 8 lines

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

Quoted 7 lines

John

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

#5 lore raw
In reply to devik

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

Quoted 8 lines

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.

Quoted 7 lines

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?

Quoted 2 lines

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.

Quoted 8 lines

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 / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

#6 lore raw
In reply to devik
Quoted 11 lines
Quoted 6 lines

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 / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

#7 lore raw
In reply to devik

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

Quoted 4 lines

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 / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

#8 lore raw
In reply to devik
Quoted 4 lines

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 / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

#9 lore raw
In reply to devik
Quoted 5 lines

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 :)

Quoted 10 lines
Quoted 7 lines

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.

Quoted 4 lines
Quoted 2 lines

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.

Quoted 6 lines
Quoted 2 lines

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 / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

#10 lore raw
In reply to devik
Quoted 1 line · devik

1) Backlog depth limit

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

Quoted 1 line

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.

Quoted 8 lines

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

Signature · 6 lines
Michael T. Babcock
CTO, FibreSpeed Ltd.     (Hosting, Security, Consultation, Database, etc)
http://www.fibrespeed.net/~mbabcock/
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/
#11 lore raw
In reply to devik
Quoted 7 lines

From: Martin Devera <[email protected]>

Quoted 5 lines

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.

Quoted 5 lines

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.

Quoted 11 lines
Quoted 10 lines
Quoted 7 lines

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?

Quoted 3 lines

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.

Quoted 8 lines
Quoted 4 lines
Quoted 2 lines

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.

Quoted 9 lines
Quoted 6 lines
Quoted 2 lines

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.

Quoted 5 lines

--__--__--

Quoted 7 lines

_______________________________________________
LARTC mailing list
[email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc

End of LARTC Digest

_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

#12 lore raw
In reply to devik
Quoted 4 lines
Quoted 1 line

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 ?

Quoted 4 lines
Quoted 1 line

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 ..

Quoted 1 line

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

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

Quoted 9 lines
Quoted 2 lines

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 / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/

#13 lore raw
In reply to devik
Quoted 9 lines
Quoted 3 lines

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).

Quoted 5 lines
Quoted 3 lines

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 ?

Quoted 11 lines
Quoted 8 lines
Quoted 4 lines
Quoted 2 lines

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 / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://ds9a.nl/lartc/