Research Article
A Two-Time Scale MDP-Based Routing Algorithm For DCLC Problem
@INPROCEEDINGS{10.1109/CHINACOM.2009.5339824, author={HAN Yue and LIU Zeng-ji and QIU Zhi-liang and ZHOU Quan}, title={A Two-Time Scale MDP-Based Routing Algorithm For DCLC Problem}, proceedings={ChinaCom2009-Advances in Internet Symposium}, publisher={IEEE}, proceedings_a={CHINACOM2009-AIS}, year={2009}, month={11}, keywords={DCLC; unicast routing algorithm; MDP; scalability}, doi={10.1109/CHINACOM.2009.5339824} }- HAN Yue
LIU Zeng-ji
QIU Zhi-liang
ZHOU Quan
Year: 2009
A Two-Time Scale MDP-Based Routing Algorithm For DCLC Problem
CHINACOM2009-AIS
IEEE
DOI: 10.1109/CHINACOM.2009.5339824
Abstract
The delay constrained least cost (DCLC) problem is to find the least cost path in a network subject to a delay constraint. Due to its NP-complete property, many heuristic methods have been proposed. However, these methods suffer from either high computation and communication complexity or low success ratio in finding the optimal path, or lack of scalability. In this paper, a new delay constrained least cost unicast routing algorithm called two-time scale MDP based DCLC is proposed. Based on the proposed two-time scale MDP model for DCLC problem, we define the optimal value function and the optimality equation. By using the policy iteration for solving the optimality equation, we always find the optimal path w.r.t the optimal policy in the probabilistic sense. The most attractive feature of the proposed algorithm is that it attains well scalability for the insensitivity to the network size. Extensive analyses show that the proposed algorithm not only has low computation and communication complexity, but also improves the load balance of large scale networks.
