Techniques are described herein that are capable of load-balancing establishment of connections among groups of connector servers in a public computer network by performing operations that include receiving a connection request from a connector client in a private computer network, requesting establishment of a connection between the connector client and one of the connector servers in the public computer network. A number of connections between the private computer network and each group is determined. An identified group is selected from the groups based at least in part on a number of connections between the private computer network and the identified group being less than or equal to a number of connections between the private computer network and each other group. The connection request is provided toward the identified group, which enables establishment of the connection between the connector client and a connector server in the identified group.