Estimated Path Selection for the Delay Constrained Least Cost Path

Lecture Notes in Computer Science, vol. 3746, pp. 112-122, Nov. 2005 (SCI, IF 0.402)

Moonseong Kim, Young-Cheol Bang, and Hyunseung Choo


The development of efficient Quality of Service (QoS) routing algorithms in high speed networks is very difficult since divergent services require various quality conditions. If the QoS parameter we concern is to measure the delay on that link, then the routing algorithm obtains the Least Delay (LD) path. Meanwhile, if the parameter is to measure of the link cost, then it calculates the Least Cost (LC) path. The Delay Constrained Least Cost (DCLC) path problem of the mixed issues on LD and LC has been shown to be NP-hard. The path cost of LD path is relatively more expensive than that of LC path, and the path delay of LC path is relatively higher than that of LD path in DCLC problem. In this paper, we propose Estimated Path Selection (EPS) algorithm for the DCLC problem and investigate its performance. It employs a new parameter which is probabilistic combination of cost and delay. We have performed empirical evaluation that compares our proposed EPS with the DCUR in various network situations. It significantly affects the performance that the normalized surcharge is improved up to about 105%. The time complexity is O(l + nlogn) which is comparable to well-known previous works.





View Full Text