[GNUnet-developers] What's next (was: Fwd: Asymmetric load patch)

[Christian Grothoff]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi!

I thought it would be good to share a part of this discussion with the other 
developers.

On Sunday 28 July 2002 06:48 am, you wrote:
> After the current patch I'm at loss what should be done.
> Clearly autodetecting bandwidth is no critical issue. At
> the moment I have some problems in mind, but they can't
> be "fixed" with a simple patch.
>
> The amount of (padding) noise transmitted. Stats
> for the last night
>
> #NOISE     received:     39470k send:    107306k
> #octets    received:     61633k send:    143987k
>
> On a university pipe like you have over there, that is nothing,
> but nevertheless signifies quite inefficient operation at the
> current gnunet scale: 74% of the up traffic was noise (63%
> for down)! As the noise padding (fixed size packets)
> seems one of the central ideas of gnunet, I have no idea
> if this could/should be addressed. It seems wasteful
> though, as in limited bandwidth environment using
> noise padding forces the node to drop actual traffic which
> could've been handled if noise was not used. Atleast
> it appears that way with naive thinking.

Ok, let's see. First some good news. If the load goes up, I have
seen dramatically less noise (25%). Yet, you are definitely right
that this is still bad. The obvious thing to do would be to drop the
requirement for noise and have only people use it that want to afford it. This 
solution would cause 2 big problems:
a) you can only change the upstream efficiency with that, not what you receive
b) it causes perverse economics (and having right economics is what GNUnet is 
about). The reason is that 'A' could trade-off efficiency against anonymity 
by not padding a message to 'B' with noise. But (given an adversary C that 
monitors the packet sizes between A and B) this would also decrease the 
anonymity set  of B, since C can tell for small messages that they do not 
contain content and thus have a better chance of determining that B is the 
originator of some large message than if A had padded all of its messages. 
Thus we should not go down this path.

What can be done? 
1) Well, the simplest thing would be to increase the latency.
If we on average give a buffer 5 minutes to fill before we force sending it 
out, this would definitely require less noise than if we take 5 seconds.  
This would help if network traffic is very low, and as stated at the 
beginning, if network traffic is very high, the efficiency (% noise) is 
automatically already better. This is again a bad solution since we already 
sometimes have a not-so-great response time (trade-off).

2) The best solution I can come up with would require a ton of really 
hard-to-write code. The idea is the following. Currently, an inbound packet 
is processed and the processing code calls 'appendToBuffer' without 
considering which buffers would be most appropriate for queueing. The message 
is queued instantly and messages can only be appended to the buffer. After 
some delay the buffer is send.

This has the following problems:
a) there is a delay (a couple of seconds) between looking at the load and 
making the policy decision "to send or not to send" and actually sending it. 
This time-difference may be too long.
b) The buffer is never rearranged. Example: A buffer contains 600 bytes of
queries. The next message are 1048 byte content. Since the maximum size
is smaller than 1500 bytes, the 600 bytes are padded with nearly 800 bytes of 
random noise, send and the 1048 byte are put into the emptied buffer. The 
reason is the 'append only' implementation (not the protocol!). 

If the buffer-queueing code would 'understand' the messages (which it could), 
it might have taken the 1k message and 400 bytes worth of queries, send those 
and left 200 bytes of queries in the buffer, resulting in practially no 
noise.

c) The message-queueing code does not take the 'buffer status' into account. 
Given a query that has been decided to be forwarded to 4 other nodes, it does
not terribly matter to which of the say 8 connected other nodes it goes (yes,
we are biasing the random choices, but we could use additional factors in our
bias). Putting the query in an empty buffer is likely to trigger a lot of 
noise when the buffer is flushed - putting it into a 'nearly full' one would 
be better. In fact, we may even want to make the choise to how many nodes (4) 
we want to forward the query to dependent on the buffer-status. In some 
sense, the cost of forwarding the query is mostly dependent on that status!


Thus writing more intelligent message queueing code would be a good direction. 
Messages that can go to 'any' node (forwarded HELO, our own HELO, 3QUERY) 
could be queued specially and then used in a way that optimally fills 
buffers. Note that this code would have to keep track of how old messages 
are, how important they are (to how many more to forward), and to which nodes
(slot number sufficient) they already have been forwarded. Also the code 
should give some delivery guarantees to avoid syndroms like 'dropping all 
messages because all buffers are emtpy and I would have to add noise' (and 
could make use of policy decisions that are made closer (in terms of time) to 
the action). 
While this would not get rid of all noise, depending on the number of 
connections and the load on the network, it should be able to dramatically 
reduce noise.

If noise is going down dramatically after these modifications, another 
possible change would be the addition of a new message type 'MULTIQUERY' that 
would contain n queries that all have the same originator. 3QUERY (52 bytes) 
has a 20 byte host identity that in most cases will be the same for all 
3QUERY messages. Thus we could save up to 40% of the size of query 
messages. Note that this would currently not help since the reduction would in 
99% of all cases just lead to adding noise. 

Christian
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE9RCVy9tNtMeXQLkIRArtEAJ9GvILTIydCuP72u9gfFKE+H1NBVACfVWuQ
9wioL5Xu6lsibMpsM0Qt168=
=qgfv
-----END PGP SIGNATURE-----