Apparatus and methods for communicating messages between communication devices are disclosed. The method includes receiving, from a second communication device, a message with a compressed header and a compression token, the compression token replacing routing information compressed out of an original header of the message. The method also includes determining, using the compression token, whether the routing information is stored on a first communication device, and requesting, if the routing information is not stored on the first communication device, that the second communication device send the routing information to the first communication device. And the first communication device routes the message to a destination device based upon the routing information.