Abstract
Finding a feasible path subject to multiple constraints in a network is an NP-complete problem and has been extensively studied. Many proposed source routing algorithms tackle this problem by transforming it into the shortest path selection problem, which is P-complete, with an integrated cost function that maps the multi-constraints of each link into a single cost. However, how to select an appropriate cost function is an important issue that has rarely been addressed in literature. In this paper, we provide a theoretical framework for picking a cost function that can improve the performance of source routing in terms of complexity, convergence, and probability of finding a feasible path.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 631-635 |
| Number of pages | 5 |
| Journal | IEEE International Conference on Communications |
| Volume | 1 |
| State | Published - 2003 |
| Event | 2003 International Conference on Communications (ICC 2003) - Anchorage, AK, United States Duration: May 11 2003 → May 15 2003 |
All Science Journal Classification (ASJC) codes
- Electrical and Electronic Engineering
- Computer Networks and Communications
Keywords
- Cost function
- Multiple additively constrained QoS routing
- NP-complete