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

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)1738-1742
Journal / PublicationConference Record - International Conference on Communications
Volume3
Publication statusPublished - 2003
Externally publishedYes

Conference

Title2003 International Conference on Communications (ICC 2003)
PlaceUnited States
CityAnchorage, AK
Period11 - 15 May 2003

Abstract

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 shows 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.

Research Area(s)

  • DCLC, QoS, Routing, Unicast routing

Bibliographic 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].