Coerced Delay and Multi Additive Constraints QoS Routing Schemes

Authors: P.S. Prakash, S. Selvan

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.

Keywords: Routing, Quality-of-Service (QoS), additive constraints, shortest path, delay coercion.

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

References:

[1] 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.
[2] 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.
[3] 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.
[4] 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.
[5] 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.
[6] Kevin Fall, Kannan Varathan, "The ns Manuals, The Vint Project", University of California, Berkeley, USA, March 2007, pp. 28-130.
[7] 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.
[8] Larry L. Peterson, Bruce S. Davie Book, "Computer Networks: A System Approach, 4/e" Morgan Kaufmann Publications, San Francisco, CA, USA, 2007.
[9] 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.
[10] 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.
[11] 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.
[12] 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.
[13] 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.
[14] 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.
[15] 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.
[16] 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.
[17] 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.
[18] 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.