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.
References
-
-
1)
-
Guo, L., Matta, I.: `Search space reduction in QoS routing', Proceedings of 19th IEEE International Conference on Distributed computing systems, 1999, p. 142–149.
-
2)
-
Doar, M.B.: `A better model for generating test networks', Proceedings of GLOBECOM’96, 1996, p. 86–93.
-
3)
-
Gang, L., Ramakrishnan, K.G.: `A* Prune: an algorithm for finding k shortest paths subject to multiple constraints', Proceedings of IEEE INFOCOM 2001, 2001, Anchorage, AK, USA, 2, p. 743–749.
-
4)
-
D.H. Lorenz ,
A. Orda
.
QoS routing in networks with uncertain parameters.
IEEE/ACM Trans. Netw.
,
6 ,
768 -
778
-
5)
-
Pomavalzi, C., Chakraborty, G., Shiratori, N.: `QoS based routing algorithm in integrated services packet networks', Proceedings of IEEE 1997 Conference on Network protocols, 1997, Atlanta, GA, USA, p. 167–174.
-
6)
-
Wang, J., Wang, W., Chen, J., Chen, S.: `A randomized QoS routing algorithm on networks with inaccurate link-state information', Proceedings of WCC-ICCT 2000, 2002, Beijing, China, 2, p. 1617–1622.
-
7)
-
Eppstein, D.: `Finding the k shortest path', Proceedings of 35th Annual Symposium on Foundations of computer science, 1994, p. 154–165.
-
8)
-
S. Chen ,
K. Nahsted
.
An overview of quality of service routing for next-generation high-speed network: problems and solutions.
IEEE Netw.
,
6 ,
64 -
79
-
9)
-
Z. Wang ,
J. Crowcroft
.
Quality of service routing for supporting multimedia applications.
IEEE J. Sel. Areas Commun.
,
7 ,
1228 -
1234
-
10)
-
Chen, S., Nahrstedt, K.: `Distributed QoS routing with imprecise state information', Proceedings of 7th International Conference on Computer communications and networks, 1998, p. 614–621.
-
11)
-
Guerin, R., Orda, A.: `QoS based routing in networks with inaccurate information: theory and algorithms', Proceedings of INFOCOM’97, 1997, Kobe, Japan, p. 75–83.
-
12)
-
Korkmaz, T., Krunz, M., Tragoudas, S.: `An efficient algorithms for finding a path subject to two additive constraints', Proceedings of ACM SIGMETRICS’2000, 2000, p. 318–327.
-
13)
-
Chen, S., Nahrstedt, K.: `On finding multi-constrained path', Proceedings of IEEE ICC’98, 1998, 2, p. 874–899.
-
14)
-
Juttner, A., Szyiatovszki, B., Mecs, , Rajko, I.: `Lagrange releaxation based method for the QoS routing problem', Proceedings of IEEE INFOCOM 2001, 2001, Anchorage, AK, USA, 2, p. 859–868.
-
15)
-
A. Shaikh ,
J. Rexford ,
K.G. Shin
.
Evaluating the impact of stale link state on quality-of-service routing.
IEEE/ACM Trans. Netw.
,
2 ,
162 -
176
-
16)
-
Lorenz, D.H., Orda, A.: `QoS routing in networks with uncertain parameters', Proceedings of INFOCOM’98, 1998, San Francisco, CA, USA, 1, p. 3–10.
http://iet.metastore.ingenta.com/content/journals/10.1049/ip-com_20020672
Related content
content/journals/10.1049/ip-com_20020672
pub_keyword,iet_inspecKeyword,pub_concept
6
6