SFQ buckets
Just a thought, after talking to a friend who's doing his master's work on RED and other queueing algorithms ...
... What if SFQ were to start with a minimal number of buckets, and track how 'deep' each bucket was, then go to a larger number of bits (2/4 at a time?) if the buckets hit a certain depth? Theoretically, this would mean that 'fairness' would be achieved more often in current collision situations but that a smaller number of buckets would be necessary to achieve fairness in currently low-collision situations.
I haven't looked at the SFQ code in a while, so I don't know how much benefit this would be in terms of processing time, or even how expensive it would be to change hash sizes on the fly, but at a certain level of resolution (+/- 2-4 bits), the changes wouldn't be terribly frequent anyway.
I've always been a bit of a fan of self-tuning algorithms anyway :)
Signature · 6 lines
Michael T. Babcock CTO, FibreSpeed Ltd. _______________________________________________ LARTC mailing list / [email protected] http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
Probably the more cheap way is to simply increase no of buckets. With adaptive bin number you will probably end up with linear hashing which is still fast but increasing no of bucket and keep single level search will probably be yet faster.
Just my opinion ...
devik
Quoted 16 lines · Michael T. Babcock
Just a thought, after talking to a friend who's doing his master's work on RED and other queueing algorithms ...
... What if SFQ were to start with a minimal number of buckets, and track how 'deep' each bucket was, then go to a larger number of bits (2/4 at a time?) if the buckets hit a certain depth? Theoretically, this would mean that 'fairness' would be achieved more often in current collision situations but that a smaller number of buckets would be necessary to achieve fairness in currently low-collision situations.
I haven't looked at the SFQ code in a while, so I don't know how much benefit this would be in terms of processing time, or even how expensive it would be to change hash sizes on the fly, but at a certain level of resolution (+/- 2-4 bits), the changes wouldn't be terribly frequent anyway.
Quoted 10 lines
I've always been a bit of a fan of self-tuning algorithms anyway :) --
Michael T. Babcock
CTO, FibreSpeed Ltd._______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
Quoted 6 lines · Martin Devera
Probably the more cheap way is to simply increase no of buckets. With adaptive bin number you will probably end up with linear hashing which is still fast but increasing no of bucket and keep single level search will probably be yet faster.
Just my opinion ...
devik
SFQ is connection oriented. right?
Would be a good idea to make the queues per ip rather than per tcp flow? So there would be per host fairnes.
Regards.
Signature · 10 lines
... ___________________________________________________________ ... | /| |\ | | /-| Pedro Larroy Tovar. PiotR | http://omega.resa.es/piotr |-\ | | /--| No MS-Office attachments please. |--\ | o-|--| e-mail: [email protected] |--|-o | \-| finger [email protected] for public key and info |-/ | |...\|_________________________________________________________|/...| _______________________________________________ LARTC mailing list / [email protected] http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
This is often discussed and is on "TODO" for someone ;)
Quoted 15 lines
SFQ is connection oriented. right?
Would be a good idea to make the queues per ip rather than per tcp flow? So there would be per host fairnes.Regards.
--
... ___________________________________________________________ ...| /| |\ | | /-| Pedro Larroy Tovar. PiotR | http://omega.resa.es/piotr |-\ | | /--| No MS-Office attachments please. |--\ | o-|--| e-mail: [email protected] |--|-o | \-| finger [email protected] for public key and info |-/ | |...\|_________________________________________________________|/...|
Quoted 5 lines
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
_______________________________________________
LARTC mailing list / [email protected]
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
Quoted 5 lines
This is often discussed and is on "TODO" for someone
Quoted 3 lines
SFQ is connection oriented. right?
Would be a good idea to make the queues per ip rather than per tcp flow? So there would be per host fairnes.
And all the discussions tend to lead to the conclusion that there should be an sfq option (when the queue is created) for:
a) how big the hash is
b) whether to take into account source ports or not
c) whether to take into account destination ports or not
d) etc. :)
Maybe someone who's written a qdisc would feel up to this?
Signature · 6 lines
Michael T. Babcock CTO, FibreSpeed Ltd. _______________________________________________ LARTC mailing list / [email protected] http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/