Do you control both services?
If so, the first thing I’d personally consider is batching, because I sometimes find that sending X requests at once results in much less processing than X time sending one request, and that can really do wonders for performance/stability.
Other than that, pooling + queueing + shedding can be used to control the load, i.e. to make sure that the target service doesn’t get overloaded. More recently I tend to bypass popular pooling libraries (poolboy & friends), and instead use my own parent library which I find has the good balance of flexibility/simplicity for these kinds of challenges.
