1. A method, comprising: performing, by one or more computing devices: receiving a request for a network-based service; subsequent to receiving the request, admitting one or more service requests, wherein admitting one or more service requests comprises: determining that the requested service is dependent on two or more constrained resources; and for each of the two or more constrained resources: dispensing, to the received request, a respective resource token based on an availability of tokens in a respective token bucket, wherein a number of tokens in the respective bucket is based on availability of a respective constrained resource; subsequent to the received request obtaining a resource token for each of the two or more constrained resources on which the requested service is dependent, allocating the two or more constrained resources, wherein allocating the two or more constrained resources comprises: determining when to schedule the received request based on one or more criteria; and subsequent to said determining when to schedule the received request based on one or more criteria, allocating execution threads on which to execute the two or more constrained resources to the received request.