The current structure of the Internet, with hosts behind network address translation (NAT) boxes, causes well-known problems for P2P applications. There are several proposals, e.g., STUN, UPnP, MIDCOM, TURN among others, to enable P2P UDP communication for nodes behind NAT boxes, but each technique offers a partial solution that works in special limited cases and fails in others. In this paper, we present a framework based on the use of IPv4+4 addresses and the standard IPv4 Loose Source Record Route (LSRR) option that offers a complete solution to the secure seamless P2P UDP communication problem. Our proposal requires no changes whatsoever to end-host protocol stacks and Internet routers. The only requirement is a simple upgrade of border routers with a new LSRR-based packet forwarding algorithm for the P2P UDP traffic. We detail our implementation of a Linux-based border router that runs the proposed forwarding algorithm, and describe how applications requiring P2P UDP communication such as Voice over IP (VoIP) using SIP can benefit from our framework. © 2008 Elsevier Ltd. All rights reserved.