Techniques for routing client requests among a group of nodes offering a service are described. A coordinator determines that performance could be improved by using affinity-based routing. In one embodiment, the coordinator calculates a Time-to-Live (TTL) metric whereby clients benefit by returning to the same cache and posts this hint to subscribers. Client's start preserving locality data in an affinity context, such that later requests for a connection can be routed to the location last visited. The coordinator measures the system over subsequent intervals. If the gradient of the goodness (viz service quality and capacity) is stable or improving, then the coordinator continues to advise subscribers to use the affinity-based technique. Alternatively, if the gradient of the goodness is deteriorating, then the coordinator posts advice to the subscribers to stop using the affinity-based technique for any instance during the next intervals.