ChinaCom2009-Advances in Internet Symposium

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},
        keywords={DCLC; unicast routing algorithm; MDP; scalability},
  • HAN Yue
    LIU Zeng-ji
    QIU Zhi-liang
    ZHOU Quan
    Year: 2009
    A Two-Time Scale MDP-Based Routing Algorithm For DCLC Problem
    DOI: 10.1109/CHINACOM.2009.5339824
HAN Yue1,*, LIU Zeng-ji1,*, QIU Zhi-liang1, ZHOU Quan2,*
  • 1: ISN State Key Laboratory, Xidian University Xi’an China
  • 2: Xi’an Ist. of Space Radio Technology Xi’an China
*Contact email:,,


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.