The expression of search termination criteria in service discovery requests. When a client is to make a service discovery request, the client includes the service criteria that the service can use to verify whether they provide a matching service. However, the client also includes search termination criteria that specifies the criteria that the client will use to terminate the request. When deciding whether or not to send a response to the service discovery request, the service may elect not to send a response to the service discovery request if its logic determines that there is reduced chance that the response would be received by the client prior to the client terminating the request.