Derya YILTAŞ KAPLAN

Maximum size of the pareto cost sets for multi-constrained optimal routing

Routing under multiple independent constrains in point-to-point networks has been studied for over 10 years. Its NP-hardness keeps pushing researchers to study approximate algorithms and heuristics, and many results have been published in these years. To the best of our knowledge, the nature of its average case has been explored only for the self- adaptive multiple constraints routing algorithm (SAMCRA), which is an algorithm about multiple constraints routing. In this paper, we simplify SAMCRA into a format that is convenient for our average case analysis. This variant algorithm gives optimal solutions also for very large dimensional networks such as with more than 1000 nodes. Although it runs in exponential time in the worst case, we prove that its average case time complexity is bounded by a polynomial function of the number of nodes in the network. Lastly, we give empirical results that align with our theoretical work.

PDF

___

[1] Wang CF, Ding JW, Chen TC. A routing protocol for mobile ad-hoc networks using the pro t optimization model. Int J Commun Syst 2014; 27: 2851-2869.
[2] Santhi G, Nachiappan A. A survey of QoS routing protocols for mobile ad hoc networks. International Journal of Computer Science & Information Technology (IJCSIT) 2014; 2: 125-136.
[3] Kandari S, Pandey MK. Constraint based QoS routing in MANET. In: International Conference on Advances in Engineering and Technology; 29{30 March 2014; Singapore. New York, NY, USA: IRED. pp. 63-68.
[4] Tanwar S, Kumar N, Rodrigues JJPC. A systematic review on heterogeneous routing protocols for wireless sensor network. J Netw Comput Appl 2015; 53: 39-56.
[5] Djarallah NB, Sauze NL, Pouyllau H, Lahoud S, Cousin B. Distributed E2E QoS-based path computation algorithm over multiple inter-domain route. In: 3PGCIC 2011 Sixth International Conference on P2P, Parallel, Grid, Cloud and Internet Computing; 26{28 October 2011; Barcelona, Catalonia, Spain. New York, NY, USA: IEEE. pp. 169- 176.
[6] Ali NB, Molnar M, Belghith A. Multi-constrained QoS Multicast Routing Optimization. Research Report, Institut De Recherche En Informatique Et Systemes Aleatoires, Rennes Cedex, France, 2008.
[7] Yampolskiy M, Hommel W, Lichtinger B, Fritz W, Hamm MK. Multi-domain end-to-end (E2E) routing with multiple QoS parameters-considering real world user requirements and service provider constraints. In: Second International Conference on Evolving Internet (INTERNET); 20{25 September 2010; Valencia, Spain. Red Hook, NY, USA: IARIA. pp. 9-18.
[8] Bertrand G, Lahoud S, Texier G, Molnar M. Computation of multi-constrained paths in multi-domain MPLS-TE networks. In: Next Generation Internet Networks; 1{3 July 2009; Aveiro, Portugal. New York, NY, USA: IEEE. pp. 1-8.
[9] Shin DW, Chong EKP, Siegel HJ. Multi-postpath-based lookahead multi-constraint QoS routing. J Franklin I 2012; 349: 1106-1124.
[10] Xue Q, Ganz A. Ad hoc QoS on-demand routing (AQOR) in mobile ad hoc networks. J Parallel Distr Com 2003; 63: 154-165.
[11] Yuan X, Liu X. Heuristic algorithms for multi-constrained quality of service routing. In: IEEE INFOCOM 2001 Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies; 22{26 April 2001, Anchorage, AK. New York, NY, USA: IEEE. pp. 844-853.
[12] Xue G, Sen A, Zhang W, Tang J, Thulasiraman K. Finding a path subject to many additive QoS constraints. IEEE ACM T Network 2007; 15: 201-211.
[13] Van Mieghem P, De Neve H, Kuipers F. Hop-by-hop quality of service routing. Comput Netw 2001; 37: 407-423.
[14] Van Mieghem P, Kuipers FA. Concepts of exact QoS routing algorithms. IEEE ACM T Network 2004; 12: 851-864.
[15] Van Mieghem P, Kuipers FA. On the complexity of QoS routing. Comput Commun 2003; 26: 376-387.