Packet loss with LocalDiscovery

[Etienne Dechamps]

Good news: I have found the root cause for the bug, and came up with a fix.

Surprisingly, this is caused by a bug in hash_function(). Because of a 
small mistake in the inner loop, the function will only ever use the 
first 4 bytes of data, and will never look at the remaining bytes.

Incidentally, the node UDP address cache uses this function with a key 
of type sockaddr_in. This structure contains the IP protocol and port in 
the first 4 bytes, and the IP address in the remaining bytes. With the 
broken hash function, this means that all addresses that have the same 
IP protocol and port will return the same hash.

This is demonstrated by the following test code:
https://github.com/dechamps/tinc/compare/1828908...hashtest

Which outputs the following:
     Hash test: 10.172.1.1:656 (10.172.1.1 port 656) -> 144
     Hash test: 10.172.1.5:656 (10.172.1.5 port 656) -> 144
     Hash test: 94.23.24.223:656 (94.23.24.223 port 656) -> 144
     Hash test: 127.0.0.1:656 (127.0.0.1 port 656) -> 144
     Hash test: 1.2.3.4:656 (1.2.3.4 port 656) -> 144
     Hash test: 10.172.1.1:655 (10.172.1.1 port 655) -> 104
     Hash test: 10.172.1.5:655 (10.172.1.5 port 655) -> 104
     Hash test: 94.23.24.223:655 (94.23.24.223 port 655) -> 104
     Hash test: 127.0.0.1:655 (127.0.0.1 port 655) -> 104
     Hash test: 1.2.3.4:655 (1.2.3.4 port 655) -> 104
     Hash test: 10.172.1.1:42 (10.172.1.1 port 42) -> 80
     Hash test: 10.172.1.5:42 (10.172.1.5 port 42) -> 80
     Hash test: 94.23.24.223:42 (94.23.24.223 port 42) -> 80
     Hash test: 127.0.0.1:42 (127.0.0.1 port 42) -> 80
     Hash test: 1.2.3.4:42 (1.2.3.4 port 42) -> 80

To make things worse, tinc's hash table doesn't care about collisions, 
meaning, two keys with the same hash value will override each other. 
This means that if two nodes happen to use the same port number, they 
can't appear in the node UDP address cache at the same time.

Unfortunately, that matches the situation that I put myself in:
- Node "kobol" sits somewhere on the Internet, IP address 94.23.24.223
- Node "zyklos" is on my LAN, local IP address 10.172.1.1
- Node "firefly" is on my LAN, local IP address 10.172.1.5

All these nodes use port 656. Now, here's what happens when 
LocalDiscovery comes into play:

1. LocalDiscovery succeeds, zyklos and firefly are speaking locally, and 
their UDP address cache contains each other's local addresses:
     [144 (2148532224 % 256 = 144)] 10.172.1.5 port 656 -> firefly

2. At some point, kobol will attempt to communicate with one of the two 
nodes. This could happen because they need to negotiate PMTU again, 
which happens every PingInterval seconds.

3. If communication succeeds over UDP, kobol's address will override the 
existing contents of the node's UDP address cache:
     [144 (2148532224 % 256 = 144)] 94.23.24.223 port 656 -> kobol

4. As a result, when the node receives data from the other local node, 
it will not find its address in the UDP address cache and will have to 
fall back to try_harder() to find out from which node it just received data.

5. If one of the nodes starts talking simultaneously with kobol and the 
other local node (e.g. in my test, the two local nodes are pinging each 
other while kobol is renegociating PMTU at the same time), then they 
will constantly override each other in the cache, and try_harder() will 
be called several times per second.

6. Unfortunately, there is what seems to be a "safety" (Oracle 
protection) measure in try_harder() that will make it refuse to "try 
harder" more than one time per second, dropping packets instead.

In summary: when a node is communicating with more than one other node 
simultaneously, the UDP address cache is constantly being overridden, 
try_harder() is called lots of time per second, and as a result, 
throughput is limited to at most one packet per second, which is of 
course completely impractical.

Here's the fix: https://github.com/gsliepen/tinc/pull/5

On 15/07/2013 19:45, Etienne Dechamps wrote:
> Hi,
>
> I believe I have found a bug with regard to the LocalDiscovery feature.
> This is on tinc-1.1pre7 between two Windows nodes.
>
> Steps to reproduce:
> - Get two nodes talking using LocalDiscovery (e.g. put them on the same
> LAN behind a NAT with no metaconnection to each other)
> - Make one ping the other.
>
> Expected result:
> - The two nodes should ping each other without any packet loss,
> hopefully at LAN latencies.
>
> Actual result:
> - I'm experiencing packet loss every (PingInterval) seconds. Each packet
> loss "episode" lasts roughly 1 second and during that time all packets
> are lost. Apparently it happens each time the nodes are exchanging PMTU
> probes. Packet loss correlates with "Sending/Got MTU probe" messages. It
> also materializes in the form of "Received UDP packet from unknown
> source <LAN Address>" messages.
> - There seems to be some "flapping" with regard to the local host
> discovery itself, meaning that it sometimes reverts to the "normal" mode
> of communication for a brief time for no reason. This can be seen as
> elevated latencies.
>
> For aggressive PingInterval values (e.g. 3 seconds) this makes the link
> between the two nodes basically unusable with 30%+ packet loss.
>
> My hypothesis is that during PMTU discovery tinc "forgets" about the
> other node's locally discovered address, which results in packet loss
> because it doesn't recognize packets coming from the local address
> anymore and makes it revert to "classic mode" for a brief time. Then
> after a moment local discovery kicks in again and fixes the situation,
> until PMTU discovery happens again, and so on.
>
> I will continue investigating and try to come up with a fix.


-- 
Etienne Dechamps