Voice over IP (VoIP) is one of the most popular Internet applications. Many VoIP protocols (e.g. SIP) are based on a central-server scheme in which a caller needs to query the central server first for the callee's information (e.g. IP address) before it can connect to them. However, such a centralized architecture has some drawbacks, such as an unbalanced load and a single point of the failure. As a result, some researchers have proposed the use of peer-to-peer (P2P) techniques for VoIP communication. However, compared to a centralized approach, setting up a VoIP connection over multiple hops could potentially take a longer time and might discourage users from utilizing this service. In this paper, we set out to study the performance of existing P2P protocols for VoIP applications in a more realistic setting based on traces collected from the Skype network. The Skype traces are used as an input to model the VoIP network topology. We evaluated the performance of three types of distribute hash table(DHT) protocols, namely, flat DHT, hierarchical DHT and proximity DHT, in terms of their lookup latency for the connection setup phase of VoIP applications. In addition, to understand the feasibility of using infrastructure-less VoIP in the real world, we adopted pair comparison techniques to evaluate the quality of the user experience. Finally, we proposed a new hybrid protocol for the infrastructure-less VoIP communication. We concluded that current P2P protocols for VoIP are not satisfactory as compared to the traditional centralized approach and there is still a lot of room for improvement.