Coerced Delay and Multi Additive Constraints QoS Routing Schemes
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:64821", author = "P.S. Prakash and S. Selvan", title = "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.", keywords = "Routing, Quality-of-Service (QoS), additive
constraints, shortest path, delay coercion.", volume = "3", number = "3", pages = "839-10", }
