On the extended Bellman-Ford algorithm to solve two-constrained quality of service routing problems

Two-constrained quality of service (QoS) routing finds a route in the network that satisfies two independent quality of service constraints. This problem is NP-hard and a number of heuristic algorithms have been proposed to solve the problem. This paper considers two heuristics, namely the limited granularity heuristic and the limited path heuristic, that can be applied to the extended Bellman-Ford algorithm to efficiently solve two-constrained QoS routing problems. Analytical and simulation studies are conducted to compare the effectiveness of the heuristics in finding the paths that satisfy the QoS constraints and the time/space requirements of the heuristics. The major results of this paper include the following. First, the paper proves an optimal limited granularity heuristic scheme. The scheme is optimal in the sense that it provides an optimal worst-case guarantee in finding the paths that satisfy the QoS constraints among all limited granularity heuristic schemes. Second, the paper shows that, in polynomial time, the limited path heuristic has very high probability of finding a path in a randomly generated graph that satisfies the QoS constraints if such a path exists