A method and apparatus for estimating relative network proximity between request routing agents and client agents are described herein. In one embodiment, the method includes a proximity estimation unit to send a first number of probe messages to a client agent without waiting to receive a reply message, wherein the proximity estimation unit is to receive a first set of reply messages. The apparatus also including a proximity verification unit coupled with the proximity estimation unit, to send a second number of probe messages to the client agent, and to receive a second set of reply messages.