Stateful network address translation protocol implemented over a data network

A method, comprising:

• receiving, at a first network device configured to perform Network Address Translation (NAT), a first NAT transaction message which includes updated NAT information, the first NAT transaction message being generated by a second network device configured to perform NAT, the updated NAT information including information relating to updates or modifications to be performed on NAT information stored at a first NAT data structure, the first NAT data structure being managed by the first network device;
• modifying, by the first network device, the NAT information stored at the first NAT data structure in the event that the second network device that generated the first NAT transaction message is authorized to modify the first NAT data structure, wherein the modifying is performed using the updated NAT information from the first NAT transaction message to thereby achieve synchronization of the NAT information stored on the first and second network devices;
• and
• preventing modification, by the first network device, of the NAT information stored at the first NAT data structure in the event that the second network device that generated the first NAT transaction message is not authorized to modify the first NAT data structure.