[LARTC] ESFQ not so fair?

[LARTC] ESFQ not so fair?

[Michał Margula]

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]
_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc

Re: [LARTC] ESFQ not so fair?

[Andy Furniss]

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

_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc

Re: [LARTC] ESFQ not so fair?

[Michał Margula]

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]
_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc

Re: [LARTC] ESFQ not so fair?

[Patrick McHardy]

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.
_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc

Re: [LARTC] ESFQ not so fair?

[Andy Furniss]

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.

_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc

Re: [LARTC] ESFQ not so fair?

[Andy Furniss]

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.

_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc

Re: [LARTC] ESFQ not so fair?

[Corey Hickey]

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
_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc

Re: [LARTC] ESFQ not so fair?

[Michał Margula]

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]
_______________________________________________
LARTC mailing list
LARTC@mailman.ds9a.nl
http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc