Recently P2P (Peer-to-Peer) has been proposed to improve the scalability of the traditional VoIP (voice over IP) systems. However, P2P makes VoIP service unreliable because P2P networks probably scale up and the service nodes are very likely to fail or leave the P2P networks when VoIP service is offering. To deal with this issue, we propose a service quality assurance mechanism. The whole proposition includes a relay overlay algorithm and a dynamic relay algorithm. In the scheme, VoIP system can select the successor of the failed relay nodes without adding extra backup nodes. The simulation results demonstrate that our algorithms maintain 70% voice dialogs correctly in the presence of relay nodes failure with the delay remaining below 150ms. The results also show that the system architecture is feasible and scalable.