Multiple additively constrained path selection.

被引:11
作者
Cheng, G
Ansari, N
机构
[1] Advanced Networking Lab., Dept. of Elec. and Comp. Engineering, New Jersey Institute of Technology, Newark
来源
IEE PROCEEDINGS-COMMUNICATIONS | 2002年 / 149卷 / 5-6期
关键词
D O I
10.1049/ip-com:20020672
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 [电气工程]; 0809 [电子科学与技术];
摘要
Finding a feasible path subject to multiple constraints in a network is an NP-complete problem and has been extensively studied. However, current algorithms suffer either high computational complexity or low success ratio in finding feasible paths. The authors propose a novel extended Bellman-Ford algorithm (EB), from which they present a high-performance algorithm with low computational complexity in finding feasible paths with multiple additive constraints. Through analysis and simulations, it is shown that the algorithm outperforms its contenders in the success rate of finding a feasible path as well as in terms of scalability; the proposed algorithm can achieve almost 100% success ratio as long as a feasible path exists. Furthermore, the worst case computational complexity is only twice that of the Bellman-Ford algorithm.
引用
收藏
页码:237 / 241
页数:5
相关论文
共 16 条
[1]
Distributed QoS routing with imprecise state information [J].
Chen, SG ;
Nahrstedt, K .
7TH INTERNATIONAL CONFERENCE ON COMPUTER COMMUNICATIONS AND NETWORKS - PROCEEDINGS, 1998, :614-621
[2]
An overview of quality of service routing for next-generation high-speed networks: Problems and solutions [J].
Chen, SG ;
Nahrstedt, K .
IEEE NETWORK, 1998, 12 (06) :64-79
[3]
Chen SG, 1998, ICC 98 - 1998 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS VOLS 1-3, P874, DOI 10.1109/ICC.1998.685137
[4]
Doar MB, 1996, IEEE GLOBECOM 1996 - GLOBAL INTERNET'96, CONFERENCE RECORD, P86, DOI 10.1109/GLOCOM.1996.586131
[5]
Eppstein D., 1994, Proceedings. 35th Annual Symposium on Foundations of Computer Science (Cat. No.94CH35717), P154, DOI 10.1109/SFCS.1994.365697
[6]
Guerin R, 1997, IEEE INFOCOM SER, P75, DOI 10.1109/INFCOM.1997.635116
[7]
Search space reduction in QoS routing [J].
Guo, L ;
Matta, I .
19TH IEEE INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING SYSTEMS, PROCEEDINGS, 1999, :142-149
[8]
Jüttner A, 2001, IEEE INFOCOM SER, P859, DOI 10.1109/INFCOM.2001.916277
[9]
Korkmaz T, 2000, PERF E R SI, V28, P318, DOI 10.1145/345063.339427
[10]
QoS routing in networks with uncertain parameters [J].
Lorenz, DH ;
Orda, A .
IEEE-ACM TRANSACTIONS ON NETWORKING, 1998, 6 (06) :768-778