MPLS networks require a QoS routing algorithm providing the characteristics of MPLS networks that establish a bandwidth guaranteed tunnel from source to destination. Our proposed QoS routing scheme gives a priority to multimedia traffic prone to block and differentiates network links into four classes based on link state information. Links have the different weights according to their classes and type of traffic transferred. We select the path with the minimum weight sum of links on the path. We also consider the observed blocking probability to reduce the frequency of the QoS state exchanges and supplement the out-of-date QoS information since the QoS state update results in the network overhead. Through the comparison between other existing schemes and ours, we show that our scheme with its low overhead and comparable performance is a better alternative to QoS routing schemes.