An Efficient and Optimized Multi Constrained Path Computation for Real Time Interactive Applications in Packet Switched Networks

Authors: P.S. Prakash, S. Selvan

Abstract:

Quality of Service (QoS) Routing aims to find path between source and destination satisfying the QoS requirements which efficiently using the network resources and underlying routing algorithm and to fmd low-cost paths that satisfy given QoS constraints. One of the key issues in providing end-to-end QoS guarantees in packet networks is determining feasible path that satisfies a number of QoS constraints. We present a Optimized Multi- Constrained Routing (OMCR) algorithm for the computation of constrained paths for QoS routing in computer networks. OMCR applies distance vector to construct a shortest path for each destination with reference to a given optimization metric, from which a set of feasible paths are derived at each node. OMCR is able to fmd feasible paths as well as optimize the utilization of network resources. OMCR operates with the hop-by-hop, connectionless routing model in IP Internet and does not create any loops while fmding the feasible paths. Nodes running OMCR not necessarily maintaining global view of network state such as topology, resource information and routing updates are sent only to neighboring nodes whereas its counterpart link-state routing method depend on complete network state for constrained path computation and that incurs excessive communication overhead.

Keywords: QoS Routing, Optimization, feasible path, multiple constraints.

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

References:

[1] S.Chen, K. Nahrstedt, "On finding multi-constrained paths", in: Proceedings of ICC'98 June 1998, pp. 874-879.
[2] S.Chen and K. Nahrstedt, "Distributed QoS routing with imprecise state information", ICCCN 1998, pp. 614-623.
[3] J.J. Garcia-Lunes-Aceves, Loop-free routing using diffusing computations, IEEE/ACM Transaction on computer Networks, 1(1) (1993) 130-141.
[4] D. Ghosh, V. Sarangan, R. Acharya, "Quality-of-Service routing in IP networks", IEEE Transaction of Multimedia 3(2) (2001) 200-208.
[5] Kevin R. Hutson, Terri L. Schlosser, Douglas R. Shier, "On the distributed Bellman-ford Algorithm and the Looping problem", Journal of Computing, Vol 19, No:4, Fall 2007, pp. 542-551.
[6] J.M. Jaffe, "Algorithm for finding paths with multiple constraints", IEEE Networks 14(1984) 95-116.
[7] T. Korkmaz, M. Krunz, S. Tragoudas, an efficient algorithm for finding a path to two additive constraints, in: Proceedings of the ACM SIGMETRICS, 2000, pp. 318-327.
[8] Z. Li, A distributed approach for multi-constrained path selection and routing optimization in: Proceedings of QSHINE'06, Waterloo, Ont., Canada, August 2006.
[9] P.V. Mieghem, F.A. Kuipers, Concepts of exact QoS routing algorithms , IEEE/ACM Transaction on Networks, 12(5) (2004) 851-864.
[10] P.V. Mieghem, H.D. Neve, F. Kuipers, Hop-by-hop quality of service routing, Computer Networks 37(3-4) (2001) 407-423.
[11] H.D. Neve, P.V. Mieghem, TAMCRA: a tunable accuracy multiple constraints routing algorithm, Computer Communication 23(2000), 667-679.
[12] P.S. Prakash, S. Selvan, "A feasible path selection QoS Routing Algorithm with two constraints in Packet Switched Networks", International Journal of Computer and Information Science and Engineering, pp. 129-135, Spring 2008.
[13] B. Smith, Efficient policy-based routing without virtual circuits in: Proceedings of QSHINE'04, Dallas, TX, October 2004.
[14] J.L. Sobrinho, Algebra and algorithm for QoS path computation and hop-by-hop routing in the Internet, IEEE/ACM Transaction on Networks 10(4) (2002) 541-550.
[15] Z. Wang, J. Crowcroft, "Quality-of-Service routing for supporting multimedia application", IEEE Journal on select areas in Communication 14(7) (1996) 1228-1234.
[16] J. Wang, K. Nahrstedt, Hop-by-hop routing algorithm for premium-class traffic in DiffSery networks, in proceeding of IEEE 1NFOCOM 2002.
[17] B.M. Waxman, "Routing of multipoint connection", IEEE Journal on Select Areas in Communication, 6(1988), 1617-1622.
[18] X. Yuan, Heuristic algorithm for multi-constrained quality-of-service routing, IEEE/ACM Transaction on Networks 10(2) (2002) 244-256.
[19] Z. Zhang, S. Nelakuditi, R.P. Tsang, D.H.C. Du, Adaptive proportional routing; a localized QoS Routing Approach, IEEE/ACM Transaction on Networks 10(6) (2002) 790-804.