In one embodiment a method and apparatus are provided that automatically establish an real time protocol (RTP) tunnel between an originator node or router and a terminator node or router, wherein the terminator node is close to a remote RTP peer. A method includes detecting a new flow of RTP packets wherein the RTP packets are encoded with a destination Internet Protocol (IP) address. Responsive to detecting the new flow, a probe is sent towards a same IP address as the destination IP address of the RTP packets. A response to the probe is received, the response including an identifier of a node that generated the response. Then, using the identifier, a tunnel is established with the node that generated the response, and thereafter compressed packets (compressed headers, compressed payloads, or both) are passed via the tunnel.