Patent ID: 8843600

Claim:
A computer-implemented method comprising: receiving, by one or more programmed computing systems of a configurable network service that provides private computer networks to remote clients, information from a first client regarding a first virtual computer network having multiple computing nodes, the received information indicating a plurality of virtual network addresses for the first virtual computer network and including information about use by the first virtual computer network of a network-accessible Lightweight Directory Access Protocol (“LDAP”) service made available by the configurable network service, wherein the LDAP service is external to the first virtual computer network and includes a pool of multiple LDAP computer servers for use by the first virtual computer network; assigning, by the one or more programmed computing systems, one of the plurality of virtual network addresses to represent the LDAP service within the first virtual computer network, and associating other of the plurality of virtual network addresses with the multiple computing nodes; encoding, by the one or more programmed computing systems, and for a first communication sent by one of the multiple computing nodes to a virtual network address associated with another of the multiple computing nodes, the first communication in a manner specific to a substrate network on which the first virtual computer network is overlaid, and forwarding the encoded first communication over the substrate network to a location of the another computing node within the substrate network; and for a second communication sent by one of the multiple computing nodes to the one virtual network address assigned to represent the LDAP service, selecting, by the one or more programmed computing systems, one of the multiple LDAP computer servers of the pool to use for the second communication based at least in part on whether the second communication is of a type that corresponds to a data write request or a data read request; and initiating, by the one or more programmed computing systems, providing functionality of the LDAP service to the first virtual computer network by encoding the second communication in a manner specific to the substrate network, and forwarding the encoded second communication over the substrate network to the selected one LDAP computer server.