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.
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/ > >
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 ... > devikSFQ 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 |-/ | |...\|_________________________________________________________|/...|
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/ > >
> 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.
Hi there! On Tue, 4 Jun 2002, Martin Devera wrote:> 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.I''ve done some in this direction , probably needs more work, and it''s poorly tested - expect b00ms ;) This adds a new qdisc for now - esfq which is a 100% clone of original sfq. - You can set all sfq parameters: hash table size, queue depths, queue limits. - You can choose from 3 hash types: original(classic), dst ip, src ip. Things to consider: perturbation with dst and src hashes is not good IMHO, you can try with perturb 0 if it couses trouble. Please, see the attached files. Plaing with it gives interesting results: higher depth -> makes flows equal slower small depth -> makes flows equal faster limit kills big delays when set at about 75-85% of depth. Needs testings and mesurements - that''s why i made it separate qdisc and not a patch over sfq, i wanted to compare both. Any feedback good or bad is welcome. -- have fun, alex