.png){kind=icon}
Return
A distributed algorithm for delay-constrained unicast routing
.png){kind=icon}
OA
AI
DOI：10.1109/90.842145.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper, we study the NP-hard delay-constrained least cost (DCLC) path problem. A solution to this problem is needed to provide real-time communication service to connection-oriented applications, such as video and voice. We propose a simple, distributed heuristic solution, called the delay-constrained unicast routing (DCUR) algorithm. DCUR requires limited network state information to be kept at each node: a cost vector and a delay vector. We prove DCUR's correctness by showing that it is always capable of constructing a loop-free delay-constrained path within finite time, if such a path exists. The worst case message complexity of DCUR is O(\V\(2)) messages, where \V\ is the number of nodes. However, simulation results show that, on the average, DCUR requires much fewer messages. Therefore, DCUR scales well to large networks. We also use simulation to compare DCUR to the optimal algorithm, and to the least delay path algorithm. Our results show that DCUR's path costs are within 10% of those of the optimal solution.
Keywords:
delay constraints
distributed algorithms
quality of service
routing
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
I
IF:
3.6
Papers:
4.4K
Citations:
9.5K
Organization
No organization information available
Cited Papers
.png){kind=icon}
ShareSaveShareSave
ShareSave no more
no more