Because of the constant reduction of available public network addresses and the necessity to secure networks, middleboxes such as network address translators and firewalls have become quite common. Because they are designed around the client-server paradigm, they break connectivity when protocols based on different paradigms are used (e.g., VoIP or P2P applications). Centralized solutions for middlebox traversal are not an optimal choice because they introduce bottlenecks and single point-of-failures. To overcome these issues, this article presents a distributed connectivity service solution that integrates relay functionality directly in user nodes. Although the article focuses on applications using the Session Initialization Protocol, the proposed solution is general and can be extended to other application scenarios.