Systems and methods are disclosed that facilitate the management of network address information utilized by hosted computing devices. Each host computing device includes a local network and port address management component that is configured with port address translation information for the specific host computing device. Additionally, one or more edge computing devices also include a local network and port address management component that is configured with network and port address translation information. The network and port address translation information facilitates the correlation of internal network address information associated with a virtual machine instance with a tuple of an externally accessible network address and port address information. The local network and port address translation management components utilize the network and port address translation information to translate communication requests to and from the virtual machine instances without requiring a centralized network and port address translation component.