High-speed packet networks will begin to support services that need Quality-of-Service (QoS) guarantees. Guaranteeing QoS typically translates to reserving resources for the duration of a call. We propose a state-dependent routing scheme that builds on any base state-independent routing scheme, by routing flows which are blocked on their primary paths (as selected by the state-independent scheme) onto alternate paths in a manner that is guaranteed—under certain Poisson assumptions— to improve on the performance of the base state-independent scheme. Our scheme only requires each node to have state information of those links that are incident on it. Such a scheme is of value when either the base state-independent scheme is already in place and a complete overhaul of the routing algorithm is undesirable, or when the state (reserved flows) of a link changes fast enough that the timely update of state information is infeasible to all possible call-originators. The performance improvements due to our controlled alternate routing scheme are borne out from simulations conducted on a fully-connected 4-node network, as well as on a sparsely-connected 12-node network modeled on the NSFNet T3 Backbone.