Techniques are described for managing communications sent to and/or from multiple computing nodes, such as for a group of computing nodes that are part of one or more private networks. In at least some situations, the techniques are used in conjunction with providing network address translation (“NAT”) functionality to a group of computing nodes that share one or more networks, such as to provide NAT functionality in a distributed and asymmetric manner using multiple computing devices that perform different types of operations at different locations within the private network.