AEAD algorithm design defects

[zhou0]

What version of shadowsocks-libev are you using?

3.0.2 to 3.0.5

What operating system are you using?

doesn't matter

What did you do?

use AEAD cipher

What did you expect to see?

good throughput and low latency

What did you see instead?

bad throughput , unnecessary latency. In aead mode, It happens very often that after you read from socket buffer ( upper limit is 2048 in ss-libev ) just to find that buffer is shorter than the payload length ( It is 16*1024 in theory, but in libev it is also 2048 ) , so you have to suspend the decryption and wait for next socket buffer read. If we limit the payload length to 2014 ( 2048 - 34 ), there will be much better chance that very read leads to a decryption instead of waiting for more.

What is your config in detail (with all sensitive info masked)?

nothing.

[madeye]

There no additional constraints for chunk size in shadowsocks protocol, except the 16KB limitation for our two reserved bits in chunk length.

The 2048 socket buffer is a design choice for shadowsocks-libev, You're free to use any other size in your implementation.

If we limit the payload length to 2014 ( 2048 - 34 ), there will be much better chance that very read leads to a decryption instead of waiting for more.

You may run benchmark here to prove your assumption.

[zhou0]

the 2048 buffer limit also set the upper limit of the AEAD payload length limit. Because every buffer read is encrypted and written right away. Of course you can queue several buffer read and encrypt just once instead of encryting every read. But doing so will cause the client to wait for more , the result is worse .

[madeye]

But doing so will cause the client to wait for more , the result is worse .

As mentioned before, you need to prove your assumption, which I believe is wrong.

[zhou0]

It is easy to prove that There is an optimal payload length. Let us see these two extreme situations, one, we AEAD every single byte, this generate a 35 bytes long cipher text for 1 byte plain text. This is bad. in another extreme, we encrypt 256GB and generate a 256GB+ 34 bytes cipher text, this is also bad because the client has to wait too long for 256GB to get encrypted. libev set the theoretical payload length limit to 16*1024 but problem is the optimal payload length should be less than the actual buffer size limit, not more than that. mysocks also use 2048 as buffer size limit. Of course if another implementation uses buffer size limit other than 2048 the same point still holds.

[madeye]

When we talking about any performance issue, first we need to figure out the bottleneck.

You assumption here is the "wait for more" would cause performance issue. But is it the real bottleneck? Actually not. Most of your CPU time are used in the crypto library and the kernel network stack. When running shadowsocks on a embedded device, this bottleneck would becomes even obvious.

If you really want to improve the peak performance on loopback, the best way is just enlarging the socket buffer size, which would save CPU time for syscalls (copies between kernel and user space). But note that "this peak performance" here is actually not really useful, as shadowsocks-libev is already I/O bound for real world usage.

[zhou0]

wait for more is wait for more read buffer IO. so It is a bottleneck in aead. If we reduce chances of wait for more, the end user could get that part of data earlier.

[madeye]

wait for more is wait for more read buffer IO. so It is a bottleneck in aead. If we reduce chances of wait for more, the end user could get that part of data earlier.

It looks you are confused with latency and throughput. Please refer to Little's law [1] and [2] for more details.

In short, "wait for more" won't hurt your throughput, instead, it may even improve it.

[1] https://en.wikipedia.org/wiki/Little%27s_law
[2] http://blog.flux7.com/blogs/benchmarks/littles-law

[zhou0]

the blog says improving latency improves throughput at the same time. so these two are related.

the effect of longer payload length is reducing the total amount of traffic at the price of latency.
the effect of shorter payload length is shorter latency at the price of more network traffic.

because the end user is usually consuming the stream at the rate of lower than the maximum bandwidth , so the increased amount of network traffic does not have any effect on the end user.
but latency is obviously noticeable and unbearable. so more weight should be given to reduce latency.

by the way, how do you get the magic number 16*1024? any proof that this is close to the optimal?

[madeye]

It looks that we're still not on the same page. I suggest to post your questions here: https://github.com/shadowsocks/shadowsocks-org/issues. Hope there are some guys can help to answer your questions.

In terms of the limitation of chunk size, it's part of SIP004 and well discussed here: shadowsocks/shadowsocks-org#30 (comment)

[zhou0]

ok.