An upcoming real-time multimedia application requires diverse quality-of-service (QoS) requirements. Providing guaranteed QoS is essential to these applications. The current distributed routing algorithms are based on either flooding or shortest path algorithms and both tend to have high message overhead. A novel unicast distributed QoS routing algorithm based on Fano?s decoding method is investigated. This is the first known attempt to enhance an error control technique using Fano?s decoding algorithm for the purpose of QoS routing in wireline networks and which require relatively small amounts of storage for their implementation. Simulation results illustrate the efficiency of the proposed algorithm with respect to message overhead and the success ratio. It is shown that the message overhead in the proposed algorithm is lower compared to flooding and distance vector based algorithms while maintaining a similar success ratio.