A selection function based distributed algorithm for delay-constraint least-cost unicast routing

It is well-known that distributed delay-constrained least-cost (DCLC) unicast routing problem is NP-complete. In this paper we propose an efficient distributed algorithm, namely, selection function based DCLC (SF-DCLC), based on a novel selection function for the DCLC problem. The proposed SF-DCLC algorithm requires limited network state information at each network node and is always able to find a loop-free path satisfying the delay bound if such paths exist. Simulation study show that the SF-DCLC is not as sensitive to the delay bound and network size as some other DCLC routing algorithms, and attains very low cost-inefficiency (less than 3% to the optimal One) in various network scenarios we simulate. The most attractive feature of SF-DCLC is that SF-DCLC has very high probability to find the optimal solution or a near-optimal solution in polynomial time with low computational complexity and message complexity.