The Delay-Constrained Least-Cost(DCLC) routing problem is known to be NP complete, hence various heuristic methods have been proposed for this problem. However, these heuristic methods have poor scalability as the network scale increases. In this paper we propose a new method based on Markov Decision Process (MDP) theory to address the scalability issue of the DCLC routing problem. The proposed algorithm combines the benefit of the hierarchical routing with the advantage of the probabilistic routing in decreasing the advertisement of the network state information. Simulation results show that the proposed method improves the scalability significantly.
['Yue Han', 'Zengji Liu', 'Mingwu Yao', 'Jungang Yang']
A scalable algorithm for finding delay-constraint least-cost end-to-end path