Abstract: In this paper we present an efficient routing algorithm for Quality-of-Service (QoS) connections requiring deterministic end-to-end delay bounds. Such routing selects paths with enough resources to accommodate the connections and satisfies their QoS. We assume that the connection scheduling, connection admissibility and state advertisement at every node is based on the Rate-Controlled Static Priority (RCSP) algorithm. We provide conditions to efficiently and a path that satisfies the QoS constraints. The performance of the QoS routing algorithm can be seriously degraded if the states are outdated and/or has high advertisement overhead. We propose conditions coupled to the RCSP algorithm that provide efficient state updates.