A communication device such as a Voice over Internet Protocol (VoIP) gateway multiplexes data intended for multiple voice connections within a single IP packet. If it is known in advance that packets for multiple connections between a given Originating Exchange (OEX) and Terminating Exchange (TEX) will travel between the Originating Gateway and Terminating Gateway, voice samples are multiplexed into the same VoIP packet. This “cell multiplexing” is accomplished by adding a cell header field to each cell payload portion. The cell header field indicates at least a connection identifier, so that the terminating gateway can route the payload to the correct TEX trunk. The scheme permits greatly improved efficiency in the carrying of VoIP traffic, especially where efficient voice coders are used.