So, I also learned another new lesson recently that the Linux kernel way back in the day used to properly load balance routes (nexthop weights) by making use of a routing cache to remember which connection is associated with which route. Then, that cache implementation was removed and replaced instead with sending individual packets randomly down each route listed (similar to how I was initially approaching the OpenVPN load balancing between multiple threads). This, however, would break connection states and packet ordering as the two route links may be going to separate places entirely. Then, the Linux kernel developers decided to implement a basic hash mapping algorithm that would associate a connection stream with the same routing hop, always. This is a very limited form of load balancing as the same source+destination address will always map to the same hash which will always match the same routing path every time (this will be even more limiting also if you are using a source NAT).

It turns out there is another trick to get some more dynamically distributed load balanced routing under Linux which is to make use of the iptables mangle table and connmark a new connection state so that the conntrack table can save+restore the specified packet markings. You can then set an ip rule to pick up these firewall markers and associate them to a different routing table. In addition to this, you are able to use a random algorithm or modding algorithm to evenly set different marks giving you even greater routing variety!

$ipt -t mangle -A PREROUTING -i lan -m mark --mark 0x0 -j CONNMARK --restore-mark
$ipt -t mangle -A PREROUTING -i lan -m statistic --mode nth --every 2 --packet 0 -m mark --mark 0x0 -j MARK --set-mark 8
$ipt -t mangle -A PREROUTING -i lan -m statistic --mode nth --every 1 --packet 0 -m mark --mark 0x0 -j MARK --set-mark 9
$ipt -t mangle -A PREROUTING -i lan -m mark ! --mark 0x0 -j CONNMARK --save-mark

echo "8 vpna" >> /etc/iproute2/rt_tables
echo "9 vpnb" >> /etc/iproute2/rt_tables
ip rule add fwmark 8 table vpna
ip rule add fwmark 9 table vpnb

You can then now add your VPN tunnel routing rules to both new ip routing tables, for example, vpna and vpnb!

~