For security and share of Internet IP addresses, NAT (Network Address Translation) firewalls are widely used to isolate the private networks from Internet in some enterprises/organizations. Unfortunately, NATs block the data transmitted directly between two clients under different private networks in many P2P (Peer to Peer) applications. A protocol, STUN, has been proposed by IETF to solve the problem. But if the NAT is Symmetric NAT, the STUN can?t tackle it effectively. Another protocol of TURN has been proposed to complement the limitation of STUN, however, it brings the additional cost of resources. Now, almost all the research into the problem are concentrated on using middle server to transmit data among clients although this way brings the additional consumption of network bandwidth and transmission delays at the same time. To solve this problem, this paper makes many practices in Symmetric NAT traversal and proposes a new algorithm PS-STUN that can traversal Symmetric NAT and transmits data directly between the clients in the situations where the STUN isn?t enabling. Through emulation tests, we prove that the algorithm is efficient and can solve the Symmetric NAT traversal trouble about STUN.