A distributed heuristic algorithm on delay-constrained least-cost unicast routing
Wang Zhengying, Shi Bingxin, Zou Ling · 2002
The delay-constrained least-cost unicast routing problem is NP-complete. We present a distributed heuristic algorithm, called the distributed DCLC unicast routing heuristic based on selection function (DCLC-DSF). DCLC-DSF, which is a dynamic routing algorithm with re-routing and negotiation mechanism, only requires the local information to be kept at each node: the delay and cost of neighbor links. In the worst case, for a network with e links and n nodes, the message complexity of DCLC-DSF is O(/spl lambda/e), and the computation complexity of each node is O(n/sup 2/), where /spl lambda/ is the maximum node degree of the network, while for a stable network, the message complexity is O(e). The simulation results also show that, on the average, DCLC-DSF requires much fewer messages. Therefore, DCLC-DSF scales well to large-scale networks. We picture the protocol of DCLC-DSF by a finite state machine. We also use simulation to compare DCLC-DSF to the optimal DCLC algorithm CBF and the least-delay path algorithm LDP. The results show that DCLC-DSF path costs are within 5-8% from these of the optimal solution. Our work is ongoing.