<p>Network address translation of messages transported over an autonomous system between multiple network elements is contemplated. The network address translation may be performed by instructing one network element to translate upstream messages for a particular messaging paths and a different network element to translate downstream messages for the same messaging path, thereby providing split network address translation.</p>