<p>We present the analysis and design of a Small World VoIP system (SW-VoIP) which is geared towards customers that are communicating with their Small World of social contacts. We use the term Small World to refer to the Peer-to-Peer (P2P) network of a client and his contacts both incoming and outbound. We reconstruct the small world of a user by collecting calling patterns over a configurable period of time. We enable user mobility by using a stepwise social identity to an IP address binding propagation model. We propose an efficient algorithm to locate users by electing popular users and leveraging the users closeness. We also introduce a self-stabilized load balancing mechanism to optimize the system performance under heavy network traffic. We evaluate our SW-VoIP system performance by simulating the user’s lookup process using real-world telephone logs. Our experimental results show that our SW-VoIP system offers a better performance in optimizing the required routing path and reducing the average lookup delay when compared to traditional, non small-world P2P VoIP systems.</p>