A Characterized and Optimized Approach for End-to-End Delay Constrained QoS Routing

Authors: P.S.Prakash, S.Selvan

Abstract:

QoS Routing aims to find paths between senders and receivers satisfying the QoS requirements of the application which efficiently using the network resources and underlying routing algorithm to be able to find low-cost paths that satisfy given QoS constraints. The problem of finding least-cost routing is known to be NP hard or complete and some algorithms have been proposed to find a near optimal solution. But these heuristics or algorithms either impose relationships among the link metrics to reduce the complexity of the problem which may limit the general applicability of the heuristic, or are too costly in terms of execution time to be applicable to large networks. In this paper, we analyzed two algorithms namely Characterized Delay Constrained Routing (CDCR) and Optimized Delay Constrained Routing (ODCR). The CDCR algorithm dealt an approach for delay constrained routing that captures the trade-off between cost minimization and risk level regarding the delay constraint. The ODCR which uses an adaptive path weight function together with an additional constraint imposed on the path cost, to restrict search space and hence ODCR finds near optimal solution in much quicker time.

Keywords: QoS, Delay, Routing, Optimization

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

References:

[1] Internet traffic Engineering IETF Working Group ftp://ftpext.eng.us.uu.net/tewg
[2] Z.Wang and J Crowcroff "Quality-of-Service routing for supporting Multimedia Applications. IEEE Journal on Select Areas in communication14(7):1188-1234 September 1996..
[3] R.Widyono, "The Design and Evolution of Routing Algorithm for Real- Time channels" Technical Report ICSI,International Computer Science Institute V.C.Berkeley, June 1994.
[4] H.F salama,D.S.Reeves and Y.Viniotis. "A Distributed Algorithm for Delay -Constrained Unicast Routing.In Proc IEEE INFOCOMM -97,April 97.
[5] J.Chen, "New approaches to routing for large scale data networks", Ph.D Thesis, Department of Computer Science, Rice University, 2000.
[6] H.De Nere and Van Mieghan, "A multiple Quality of Service Routing Algorithm for PNNI. IEEE ATM -98, PP 306-314, May 1998.
[7] E.I Chong,S.Maddila and S. Morley " On finding Single source single Destination k shortest paths, International Conference on Computing and information -98 pp40-47 July 1998.
[8] Y.Lenug, G.Li, Z.B.Xu, " A generic algorithm for multiple destination routing Problem" IEEE transaction of Evolutionary Computation, 2(4),2001.
[9] Inet Toopology Generator http://topology.eecs.unich.edu.
[10] S.Chen, K.nahsted, "An overview of quality of service routing for nextgeneration high-speed networks:problems and solution", IEEE network 12(6), pp64-79,1998
[11] Z.Wang, J.Crowcroft, "Quality-of-Service routing for supporting multimedia application, IEEE Journal on selected Areas in communications pp1228-1234,14(7),1996.
[12] Bernard M.Waxman, "Routing of Multipoint Connections", IEEE Journal on Selected areas in Communications,Vol 6, No.9, Dec 1988,pp 1617-1622.