Real-time applications such as Voice over IP, audio and video streaming require Quality of Service (QoS). Such applications are being executed over the public Internet. Since today's Internet largely supports best effort traffic, QoS routing in the best effort environment is required to support real-time applications. Some QoS routing use source routing and others use flooding of some QoS attibutes of the nodes. There were also some variants of shortest path algorithm reported in the literature. But those algorithms require changes to packet forwarding engine and logic for loop detection. We believe a better way of implementing QoS routing is to localize the QoS routing changes to the region where QoS has deteriorated and choose loop-free alternate paths. We present such an algorithm based on OSPF called LSR algorithm. In LSR algorithm, congestion notification is limited to neighbors of the congested node and the neighbors try to use alternate next hops to route packets. Alternate LSR next hop is chosen in such a way that it preserves the next hop property of OSPF routing which enables LSR algorithm to avoid loop. We present three such methods to choose an alternate LSR next hop and prove that these methods provide loop free routing. Our simulation results based on the three methods show that on an average LSR algorithm performs better than OSPF algorithm in terms of delay and jitter.
