Commenced in January 2007
Paper Count: 30174
Coerced Delay and Multi Additive Constraints QoS Routing Schemes
Abstract:IP networks are evolving from data communication infrastructure into many real-time applications such as video conferencing, IP telephony and require stringent Quality of Service (QoS) requirements. A rudimentary issue in QoS routing is to find a path between a source-destination pair that satisfies two or more endto- end constraints and termed to be NP hard or complete. In this context, we present an algorithm Multi Constraint Path Problem Version 3 (MCPv3), where all constraints are approximated and return a feasible path in much quicker time. We present another algorithm namely Delay Coerced Multi Constrained Routing (DCMCR) where coerce one constraint and approximate the remaining constraints. Our algorithm returns a feasible path, if exists, in polynomial time between a source-destination pair whose first weight satisfied by the first constraint and every other weight is bounded by remaining constraints by a predefined approximation factor (a). We present our experimental results with different topologies and network conditions.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1085784Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 968
 R. Anderson, F. Chung, A. Sen and G. Xue, "On disjoint path pairs with wavelength Continuity in WDM networks", in Proc. 23rd Annual Joint Conference of the IEEE Computer and Communication Societies, IEEE INFOCOM-04, vol. 1, Hong Kong, PR China, March 2004, pp. 524 - 535.
 S. Chen and K. Nahrstedt, "On finding multi-constrained paths," in Proc. of IEEE International Conference on Communication. IEEE ICC-98, Atlanta, Georgia, USA, vol. 2, Atlanta, Georgia, USA, June 1998, pp. 874-879.
 F. Ergun, R. Sinha, and L. Zhang, "An improved FPTAS for restricted shortest path," Information Process Letters, vol. 83, no. 5, September 2002, pp. 287-291.
 A. Goel, K. G. Ramakrishnan, D. Kataria, and D. Logothetis, "Efficient computation of delay-sensitive routes from one source to all destinations," In Proc. 20th Annual Joint Conference of the IEEE Computer and Communication Societies, IEEE INFOCOM-01, vol. 1, Anchorage, Alaska, USA, no. x, April 2001, pp. 854-858.
 R. Guerin and A. Orda, "QoS routing in networks with inaccurate information: Theory and algorithms," IEEE/ACM Transaction on Networks, vol. 7, no. 3, June 1999, pp. 350-364.
 Kevin Fall, Kannan Varathan, "The ns Manuals, The Vint Project", University of California, Berkeley, USA, March 2007, pp. 28-130.
 T. Korkmaz and M. Krunz, "A randomized algorithm for finding a path subject to multiple QoS requirements," International Journal of Computer and Telecommunications Networking, vol. 36, no. 2/3, July, 2005, pp. 251-268.
 Larry L. Peterson, Bruce S. Davie Book, "Computer Networks: A System Approach, 4/e" Morgan Kaufmann Publications, San Francisco, CA, USA, 2007.
 W. Liu, W. Lou and Y.Fang, "An efficient quality of service routing algorithm for delay-sensitive application", Computer Networks, vol. 47, no. 1, January 2005, pp, 87-104.
 D. H. Lorenz and D. Raz, "A simple efficient approximation scheme for the restricted shortest path problem," Operation Research Letters, vol. 28, no. 5, June 2001, pp. 213-219.
 A. Orda and A. Sprintson, "Efficient algorithms for computing disjoint QoS paths," in Proc. 23rd Annual Joint Conference of the IEEE Computer and Communication Societies, IEEE INFOCOM-04, vol.1, no.x, Hong Kong, PR China, March 2004, pp. 727-738.
 A. Orda and A. Sprintson, "Pre computation schemes for QoS routing," IEEE/ACM Transaction on Networks, vol. 11, no. 4, August 2003, pp. 578-591.
 A. Orda, "Routing with end-to-end QoS guarantees in broadband networks," IEEE/ACM Transactions on Networks, vol. 7, no. 3, June 1999, pp. 365-374.
 P. Van Mieghem and F. A. Kuipers, "Concepts of exact QoS routing algorithms," IEEE/ACM Transaction on Networks, vol. 12, no. 5, October 2004, pp. 851-864.
 Z. Wang and J. Crowcroft, "Quality-of-service routing for supporting multimedia applications," IEEE Journal on Selected Areas in Communication, vol. 14, no. 7, Sep 1996, pp. 1228-1234.
 Y. Xiao "QoS routing in communication networks: Approximation algorithms based on the primal simplex method of linear programming," IEEE Transaction on Computers, vol. 55, no. 7, July 2006, pp. 815-829.
 G. Xue, "Minimum cost QoS multicast and unicast routing in communication networks," IEEE Transactions on Communications, vol. 51, no. 5, May 2003, pp. 817-824.
 X. Yuan, "Heuristic algorithms for multi constrained quality-of-service routing," IEEE/ACM Transaction on Networks, vol. 10, no. 2, April 2002, pp. 244-256.