Scalability is one of the. key issues that must be resolved for VoIP to become popular. In traditional RTP/UDP/IP stream, for each call request, a single connection (a pair of UDP ports) has to be established between the VoIP gateways. This not limits only the number of audio streams between the gateways, but also requires a large state (memory) to be maintained at each gateway. This means limited capacity gateways. To make these gateways more scalable for supporting the rapid growth in VoIP services, a new efficient asynchronous multiplexing scheme, which uses G.729 coder, for public VoIP services is proposed. The proposed scheme limits the packet size to the Maximum Transmission Unit (MTU) of the physical transmission link to avoid the fragmentation of voice packet. It ensures an accepted end-to-end delay, and increases the scalability of the current VoIP gateway.