A Feasible Path Selection QoS Routing Algorithm with two Constraints in Packet Switched Networks
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:61806", author = "P.S.Prakash and S.Selvan", title = "A Feasible Path Selection QoS Routing Algorithm with two Constraints in Packet Switched Networks", 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", volume = "2", number = "3", pages = "910-7", }
