Hello! I am using since yesterday ESFQ instead of N HTB queues. It mostly works OK, but when somebody is using one single sesion (for example downloading file via FTP), it gets weird speed. For example it is 20 kilobytes pres second, then drops down to 9, then 20 again, and then slowly to 0 and stops. But when using download accelererator of some kind or bittorrent client which uses many connections, speed seems to be stable. I am using esfq that way: qdisc add dev eth0 parent 1:4 handle 4:0 esfq perturb 600 hash fwmark divisor 13 qdisc add dev eth1 parent 1:2 handle 2:0 esfq perturb 600 hash dst divisor 13 On eth0 every IP is marked with different value by IPMARK module. On eth1 it is not necessary so I use dst hash. I have more values than 2^13 so I can''t use direct hash. Any ideas? Is it possible to use bigger divisor or algorithm is not designed to deal with bigger hash? Any ideas will be appreciated! -- Michał Margula, alchemyx@uznam.net.pl, http://alchemyx.uznam.net.pl/ "W życiu piękne są tylko chwile" [Ryszard Riedel]
Michał Margula wrote:> Hello! > > I am using since yesterday ESFQ instead of N HTB queues. It mostly > works OK, but when somebody is using one single sesion (for example > downloading file via FTP), it gets weird speed. For example it is 20 > kilobytes pres second, then drops down to 9, then 20 again, and then > slowly to 0 and stops. But when using download accelererator of some > kind or bittorrent client which uses many connections, speed seems to be > stable. > > I am using esfq that way: > > qdisc add dev eth0 parent 1:4 handle 4:0 esfq perturb 600 hash > fwmark divisor 13 > qdisc add dev eth1 parent 1:2 handle 2:0 esfq perturb 600 hash dst > divisor 13 > > On eth0 every IP is marked with different value by IPMARK module. On > eth1 it is not necessary so I use dst hash. I have more values than 2^13 > so I can''t use direct hash. > > Any ideas? Is it possible to use bigger divisor or algorithm is not > designed to deal with bigger hash? Any ideas will be appreciated! >Corey Hickey changed his esfq to use jhash for dst/src/fw - copy of his announce below. Andy. Corey Hickey wrote: > In a recent thread on this list, Robert Kurjata provided me a patch to add > hashing by iptables mark to the Linux 2.4 version of ESFQ. Thanks to that > contribution, I was able to easily add support to the 2.6 port I maintain. > > I found out, however, that the existing hash algorithm results in a lot of > colllisions when the range of hashed values is small. The purturbation > spreads the collisions out a little, but the result still wasn''t very > fair, especially when hashing only three fwmark values: 0, 1 and 2. > > So, I wrote an alternative hash function. It''s quite simple, and as long > as the range of input values is smaller than the hash table (default 1024, > up to 16384), collisions will not happen at all. See the updated README > file for more details. > > Home page: > http://fatooh.org/esfq-2.6/ > > Direct URL: > http://fatooh.org/esfq-2.6/esfq-2.6.13.tar.gz > > README (also available in the tar.gz): > http://fatooh.org/esfq-2.6/current/README > > Try it out, have fun, and if you find a bug or have a suggestion please > send me an email. > > -Corey
Andy Furniss napisał(a):> > Corey Hickey changed his esfq to use jhash for dst/src/fw - copy of his > announce below. > > Andy.Thanks, but I am already using his patch :-). It happens with that patch, I haven''t tried original version at all. -- Michał Margula, alchemyx@uznam.net.pl, http://alchemyx.uznam.net.pl/ "W życiu piękne są tylko chwile" [Ryszard Riedel]
Andy Furniss wrote:> Corey Hickey changed his esfq to use jhash for dst/src/fw - copy of his > announce below. > > Andy. > > Corey Hickey wrote: >> So, I wrote an alternative hash function. It''s quite simple, and as long >> as the range of input values is smaller than the hash table (default > 1024, >> up to 16384), collisions will not happen at all. See the updated README >> file for more details.Using jhash is a probably a good idea, the "improved" hash is broken and will cause reordering in some circumstances: return (h - q->dyn_min) * (q->hash_divisor - 1) / q->dyn_range; dyn_min, dyn_max and dyn_range, as their name suggests, are adjusted dynamically, so the hash function changes whenever one of these values changes, resulting in reordering of packets belonging to a single flow.
Patrick McHardy wrote:> Andy Furniss wrote: > >>Corey Hickey changed his esfq to use jhash for dst/src/fw - copy of his >>announce below.> > Using jhash is a probably a good idea, the "improved" hash is broken > and will cause reordering in some circumstances: > > return (h - q->dyn_min) * (q->hash_divisor - 1) / q->dyn_range; > > dyn_min, dyn_max and dyn_range, as their name suggests, are adjusted > dynamically, so the hash function changes whenever one of these values > changes, resulting in reordering of packets belonging to a single flow. >Oops I thought he did use jhash don''t know where I got that from. Andy.
Michał Margula wrote:> Andy Furniss napisał(a): > >> >> Corey Hickey changed his esfq to use jhash for dst/src/fw - copy of >> his announce below. >> >> Andy. > > > Thanks, but I am already using his patch :-). It happens with that > patch, I haven''t tried original version at all. >Ahh OK - looks like Patrick spotted the problem I guess Corey will see this thread. His limit is 2^14 though, which is why I thought you must be using a different one. Andy.
Patrick McHardy wrote:> Andy Furniss wrote: >> Corey Hickey changed his esfq to use jhash for dst/src/fw - copy of his >> announce below. >> >> Andy. >> >> Corey Hickey wrote: >>> So, I wrote an alternative hash function. It''s quite simple, and as long >>> as the range of input values is smaller than the hash table (default >> 1024, >>> up to 16384), collisions will not happen at all. See the updated README >>> file for more details. > > Using jhash is a probably a good idea, the "improved" hash is broken > and will cause reordering in some circumstances: > > return (h - q->dyn_min) * (q->hash_divisor - 1) / q->dyn_range; > > dyn_min, dyn_max and dyn_range, as their name suggests, are adjusted > dynamically, so the hash function changes whenever one of these values > changes, resulting in reordering of packets belonging to a single flow.That should stabilize after it''s been running a while and has seen the normal range of IP addresses. Anyway, I agree, it''s not very good. Working on ESFQ some more has been on my long-term TODO list, but what with getting distracted by mplayer development I didn''t get around to it... and now I have 1.2 real jobs and 1.0 girlfriends and don''t have time for much programming. :) If any of you want to send patches to this list and they don''t look bad to other readers of the list I''ll happily apply them and make a new release. Other than that, I can''t help you much for now. Thanks, Corey
Corey Hickey napisał(a):>> Using jhash is a probably a good idea, the "improved" hash is broken >> and will cause reordering in some circumstances: >> >> return (h - q->dyn_min) * (q->hash_divisor - 1) / q->dyn_range; >> >> dyn_min, dyn_max and dyn_range, as their name suggests, are adjusted >> dynamically, so the hash function changes whenever one of these values >> changes, resulting in reordering of packets belonging to a single flow. > > > That should stabilize after it''s been running a while and has seen the > normal range of IP addresses. Anyway, I agree, it''s not very good. >I am changing size of HTB queue at 01:00 AM and then back at 06:00 AM. So it is quite possible that hash used by esfq will never go stable? If I know range of input values will hardcoding that into esfq help? Or maybe there is something similair to esfq with direct hash but a larger one (16 bits should be enough). I don''t care about memory usage, mostly important is performance. I am going to get uplink from another company and having another few thousands of HTB qdisc is not wise idea :-). -- Michał Margula, alchemyx@uznam.net.pl, http://alchemyx.uznam.net.pl/ "W życiu piękne są tylko chwile" [Ryszard Riedel]