Distributed service (or resource) discovery (DSD) is becoming an important research area in service-oriented computing (SOC) because many software applications are now developed with services from different vendors. Most of the current DSD approaches follow the techniques used in peer-to-peer (P2P) applications. It is estimated that 70 of the Internet traffic today is consumed by these P2P applications. Also, the volume of P2P traffic is on the rise. P2P and DSD applications function by forming an overlay on top of the existing Internet protocol (IP) layer (underlay layer). The query routing mechanism of the current P2P applications functions purely on the overlay without incorporating the topological and routing knowledge of the underlay. Consequently, Internet service providers (ISPs) are tested to their limits due to underlay-ignorant query forwarding that is employed by the overlay applications such as P2P and DSD. This underlay-ignorant query forwarding leads to inefficient usage of the underlying links because the peers in the overlay are ignorant of the location of their neighbours in the underlay. As a result, ISPs need to handle large volumes of traffic as transiting nodes, which results in increased inter-ISP traffic. Moreover, the neighbours that could be reached through the same path in the underlay are not known in the overlay, and therefore the traffic is redundantly sent in the underlying links, consuming their bandwidth and causing high interlayer communication overhead. © 2014 by Taylor #& Francis Group, LLC.