Well-known VPN solutions

IPsec

Extension of IPv6, but can also be used for IPv4 or other protocols

Comes with key exchange algorithm (IKE)

Directly applies to IP datagrams
no overhead
must be supported in kernel

FreeS/WAN is a well known implementation for Linux, KAME for BSD.