Distributed hash table (DHT) based overlay networks offer an administration-free and fault-tolerant storage space that maps "keys" to "values". For these systems to function efficiently, their structures must fit that of the underlying network. Existing techniques for discovering network proximity information, such as landmark clustering and expanding-ring search are either inaccurate or expensive. The lack of global proximity information in overlay construction and maintenance can result in bad proximity approximation or excessive communication. To address these problems, we propose the following: (1) Combining landmark clustering and round-trip time (RTT) measurements to generate proximity information, achieving both efficiency and accuracy. (2) Controlled placement of global proximity information on the system itself as soft-state, such that nodes can independently access relevant information efficiently. (3) Publish/subscribe functionality that allows nodes to subscribe to the relevant soft-state and get notified as the state changes necessitate overlay restructuring.