[LARTC] SFQ buckets

[LARTC] SFQ buckets

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

I've always been a bit of a fan of self-tuning algorithms anyway :)
-- 
Michael T. Babcock
CTO, FibreSpeed Ltd. 

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

Re: [LARTC] SFQ buckets

[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

On Tue, 4 Jun 2002, Michael T. Babcock wrote:

> 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 :)
> --
> Michael T. Babcock
> CTO, FibreSpeed Ltd.
>
> _______________________________________________
> LARTC mailing list / LARTC@mailman.ds9a.nl
> http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
>
>

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

Re: [LARTC] SFQ buckets

[PiotR]

On Tue, Jun 04, 2002 at 08:39:14PM +0200, Martin Devera wrote:
> 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.

-- 
 ... ___________________________________________________________ ...
|   /|                                                         |\   | 
|  /-| Pedro Larroy Tovar. PiotR | http://omega.resa.es/piotr  |-\  |
| /--|            No MS-Office attachments please.             |--\ |
o-|--|              e-mail: piotr@omega.resa.es                |--|-o 
|  \-|    finger piotr@omega.resa.es for public key and info   |-/  | 
|...\|_________________________________________________________|/...| 
_______________________________________________
LARTC mailing list / LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/

Re: [LARTC] SFQ buckets

[Martin Devera]

This is often discussed and is on "TODO" for someone ;)

>
> 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: piotr@omega.resa.es                |--|-o
> |  \-|    finger piotr@omega.resa.es for public key and info   |-/  |
> |...\|_________________________________________________________|/...|
> _______________________________________________
> LARTC mailing list / LARTC@mailman.ds9a.nl
> http://mailman.ds9a.nl/mailman/listinfo/lartc HOWTO: http://lartc.org/
>
>

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

RE: [LARTC] SFQ buckets

[Michael T. Babcock]

> This is often discussed and is on "TODO" for someone
> 
> > 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?
-- 
Michael T. Babcock
CTO, FibreSpeed Ltd.

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