1. A method of routing a service query in an overlay network, wherein nodes in the overlay network are operable to store information associated with attributes and attribute values for services, the method comprising: receiving a query including a plurality of attributes and attribute values describing a desired service; routing the query as a single query to a destination in the overlay network using different attributes in the query at different hops in the overlay network, wherein, at a first node, a first attribute value for a first attribute in the query is used to identify a second node as one of the hops, and at a second node, a second different attribute value for a second is attribute in the query is used to identify a third node as one of the hops; designating the destination to store advertisements describing a plurality or available services, wherein each of the plurality of available services has the same attributes and the same attribute values as the attributes and attribute values describing the desired service, and at the destination, determining whether the desired service is available from any advertisements stored at the destination.