Choreography describes the observable behaviour of component Web services that collaborate in a peer-to-peer (P2P) manner. The highly distributed and dynamic nature of Web services results in performance degradation of choreography. This paper presents a new protocol which is based on the P2P paradigm. It exploits the capabilities of underlying networks such that part of the processing is carried out at the network nodes. The proposed protocol is formally specified using p-calculus on which the Web Services Choreography Description Language (WS-CDL) is based. Efficiency of the proposed protocol is tested through various simulation experiments. These experiments show that the proposed protocol significantly improves performance by reducing the system response time in the choreography of Web services.