1. A computer-implemented method comprising: before receiving a set of potential network addresses for establishing a network connection to a remote host, establishing one or more network connections using one or more corresponding network addresses and storing routing statistics collected for routes for each of the one or more network addresses; receiving the set of potential network addresses; evaluating stored routing statistics corresponding to each of the potential network addresses, the evaluating comprising comparing routing statistics associated with each potential network address and, when routing statistics are not available for one or more of the potential network addresses, comparing available routing statistics associated with a subnet for the one or more of the potential network addresses; prioritizing the set of potential network addresses based on the evaluation; and initially attempting to connect to the remote host using a highest priority one or more of the potential network addresses.