The routing inaccuracy problem is one of the major issues impeding the evolution and deployment of Constraint- Based Routing (CBR) techniques. This paper proposes a promising CBR strategy that combines the strengths of prediction with an innovative link-state cost. The latter explicitly integrates a two-bit counter predictor, with a novel metric that stands for the degree of inaccuracy (seen by the source node) of the state information associated with the links along a path. In our routing model, Link-State Advertisements (LSAs) are only distributed upon topological changes in the network, i.e., the state and availability of network resources along a path are predicted from the source rather than updated through conventional LSAs. As a proof-of-concept, we apply our routing strategy in the context of circuit-switched networks. We show that our approach considerably reduces the impact of routing inaccuracy on the blocking probability, while eliminating the typical LSAs caused by the traffic dynamics in CBR protocols.