Abstract
It is well known that the Delay-Constrained Least-Cost (DCLC) unicast routing problem is NP-complete, hence various heuristic algorithms have been developed for this problem. In this paper, we propose a more 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 node and is always able to find a loop-free path satisfying the delay bound if such paths exist. Simulation study shows that SF-DCLC is not as sensitive to the delay bound and the size of networks as some other DCLC routing algorithms, and has very low cost-inefficiency compared to the optimal one in various network scenarios we have studied. A noteworthy feature of SF-DCLC is that SF-DCLC has very high probability of finding the optimal solution in polynomial time with low computational complexity and message complexity. © 2004 Elsevier B.V. All rights reserved.
| Original language | English |
|---|---|
| Pages (from-to) | 87-104 |
| Journal | Computer Networks |
| Volume | 47 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 14 Jan 2005 |
| Externally published | Yes |
Bibliographical note
Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].Research Keywords
- DCLC
- QoS
- Routing