A Feasible Path Selection QoS Routing Algorithm with two Constraints in Packet Switched Networks

Authors: P.S.Prakash, S.Selvan

Abstract:

Over the past several years, there has been a considerable amount of research within the field of Quality of Service (QoS) support for distributed multimedia systems. One of the key issues in providing end-to-end QoS guarantees in packet networks is determining a feasible path that satisfies a number of QoS constraints. The problem of finding a feasible path is NPComplete if number of constraints is more than two and cannot be exactly solved in polynomial time. We proposed Feasible Path Selection Algorithm (FPSA) that addresses issues with pertain to finding a feasible path subject to delay and cost constraints and it offers higher success rate in finding feasible paths.

Keywords: feasible path, multiple constraints, path selection, QoS routing

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1079852

References:

[1] Turgay Korkmaz, Marwan Krunz, Spyros Tragoudas, "Efficient Algorithm for Finding a Path Subject to Two Additive Constraints"., In Computer Communication Journal Vol 25, No. 3 pp. 225-238, Feb 2002.
[2] Z. Wang and J. Crowcroft, "Quality-of-Service routing for supporting multimedia applications," IEEE JSACs, vol.14, no.7, pp.1228-1234, Sept. 1996
[3] H.Salama, D. Reeves, Y.Viniotis, "A distributed Algorithm for Delay- Constrained Unicast Routing", INFOCOM-97, Japan, March 1997.
[4] G. Cheng and K.Ansari, "A New Heuristics For Finding The Delay Constraints Least Cost Path ", Proceedings of IEEE GLOBECOM 2003, San Francisco, CA,USA, Dec.2003, pp. 3205-3210.
[5] L.Guo, I.Matta, "Search space reduction in QoS routing", Proceeding of the 19th IEEE International Conference on Distributed Computing Systems, IEEE,1999 pp.142-149.
[6] F.A Kuipers, Korkmaz, M.Krunz, P.Vam Mieghem, "Overview of Constriant-Based Path Selection Algorithm for QoS Routing", IEEE communication magazine, Dec 2002.
[7] Cristina Aurrercoechea, Andrew T.Campbell and Linda Hauw, "A survey on QoS Architectures" ,IEEE/ACM Multimedia Systems, pp 138-151, May 1998.
[8] M. Curado, E. Monteiro, F. Kuipers, P. Van Mieghem, et.al., "Research challenges in QoS routing" Computer Communications, Volume 29, Issue 5, Pages 563-581, Mar 2006.
[9] D. Ghosh, V. Sarangan, R. Acharya, "Quality-of-service routing in IP networks", IEEE Transactions on Multimedia 3 (2) (2001) 200-208.
[10] G. Huston. "Next steps for the IP QoS architecture" Technical Report RFC 2990, IETF, November 2000.
[11] P. Van Mieghem, F.A. Kuipers, "Hop-by-hop quality of service routing", Computer Networks 37 (3-4) (2001) 407-423.
[12] F.A. Kuipers, T. Korkmaz, M. Krunz, P. Van Mieghem, "Performance evaluation of constraint-based path selection algorithms", IEEE Network 18 (5) (2004) 16-23
[13] A.Juttner, B. Szviatovszki, I. Mecs, Z. Rajko, "Lagrange relaxation based method for the QoS routing problem", Proceedings of the INFOCOM 2001 Conference, vol. 2, IEEE, 2001, pp. 859-868.
[14] G.Y. Handler, I. Zang, "A dual algorithm for the constrained shortest path problem" Networks 10 (1980) 293-310.
[15] M. Mehlhorn, K. Ziegelmann, "Resource constrained shortest path". In Proceedings of 8th European Symposium on Algorithms (ESA2000), 2000.
[16] T. Korkmaz, M. Krunz, "Multi-constrained optimal path selection",Proceedings of the INFOCOM 2001 Conference, vol. 2, IEEE, Anchorage, Alaska, 2001, pp. 834-843.
[17] T. Korkmaz, M. Krunz, "Routing multimedia traffic with QoS guarantees", IEEE Transactions on Multimedia 5 (3) (2003) ,429-443.
[18] S. Chen and K. Nahrstedt, "Distributed QoS routing with imprecise state information". ICCCN 1998, pp. 614-623.
[19] P. Van Mieghem (ed.), F.A. Kuipers, T. Korkmaz, M. Krunz, M. Curado, E. Monteiro, X. Masip-Bruin, J. Solé-Pareta, and S. S├ínchez- L├│pez. "Quality of Service Routing", Chapter 3 in Quality of Future Internet Services, EU-COST 263Final Report, edited by Smirnov et al. in Springer LNCS 2856, pp. 80-117, 2003.
[20] R.Guerin, A.Orda, "QoS routing in networks with inaccurate information:theory and algorithms", IEEE/ ACM Transactions on Networking 7(3) (1999) 350-364.
[21] Turgay Korkmaz, Marwan Krunz, " A randomized algorithm for finding a path subject to multiple QoS requirements" , In computer networks Journal 36 (2001) pp 251-268.
[22] Orda, A. Sprintson,"Precomputation schemes for QoS routing", IEEE/ACM Transactions on Networking 11 (4) (2003) 578-591
[23] Krishnaiyan Thulasiramn,Ying Xiao, Guoliang Xue, "Advances in QoS Path(s) Selection Problem", in processing of IEEE INFOCOM 2005 Conference,pp.164-167.
[24] Yanxing Zheng, Turgay korkmaz, W.Dou," Two additive-constrained path selection in the presence of inaccurate state information", In Computer Communications Journal, Vol. 30, pp. 2096-2112, May 2007.