Network Address Translation (NAT) is a technique commonly used to share one public IPv4 address among several hosts located behind a NAT device. NAT devices typically block session requests originating from outside, causing NAT traversal problem that prevents the establishment of peer-to-peer (P2P) sessions. There have been many proposals for the NAT traversal problem. However, existing methods induce high connectivity check delay and resource demand when finding a communicating path, calling for a routine that determines the path best suited for a given pair of communicating peers. This study proposes CAN, a Context-Aware NAT traversal scheme which gathers and exchanges network-context information to find the most appropriate path for two communicating peers behind NAT devices. We have implemented CAN and conducted extensive experiments with off-the-shelf NAT devices to compare the performance of CAN with Interactivity Connectivity Establishment (ICE), the most acknowledged approach to creating a session across NATs. Experimental results show that CAN outperforms ICE in terms of direct communication ratio, connectivity check delay and message overload when checking connectivity.