Two additive-constrained path selection in the presence of inaccurate state information

We study quality-of-service (QoS) routing, particularly two additive-constrained path selection problem, in the presence of inaccurate state information. We formulate this problem as Most-Probable Two-Additive-Constrained Path (MP-TACP) problem. To solve it, we follow a probabilistic approach and propose an algorithm called MP-TACPA. In general, MP-TACPA uses pre- and on-demand computation along with both linear and nonlinear search techniques. In contrast to previous algorithms using similar techniques, MP-TACPA takes into account the inaccuracies along with new bounds and heuristics including look ahead and dominance probability. Extensive simulations show that MP-TACPA behaves very well in the presence of inaccurate state information. Specifically, it gives higher success rate in finding feasible paths than existing solutions that assume the availability of exact state information. In addition, its average computational cost and thus response time is better than typical on-demand path selection algorithms.