A New Localized Multi-Constraint QoS Routing Algorithm

  • Tran Minh Anh Posts and Telecommunications Institute of Technology
  • Nguyen Chien Trinh Posts and Telecommunications Institute of Technology
Keywords: Localized algorithm, packet delay, packet loss, quality of service (QoS), multi-constraint routing.


The scheme of Quality of Service (QoS) routing algorithms based on local state information has recently been proposed as an alternative approach to the traditional QoS routing algorithms. By implementing this localized QoS routing algorithm, each source node predetermines and maintains a set of candidate paths for each destination. These sets of paths will help the source node to decide the most appropriate path for a connection request. Hence, it helps to avoid the problems associated with the maintenance of the global network state information. In this paper, we propose a new and effective localized QoS routing algorithm, compare its performance with those of other localized algorithms and a traditional QoS routing algorithm under the same type of network topology, QoS requirements and traffic patterns. The simulations results show that our proposed algorithm can perform better than other routing algorithms.

DOI: 10.32913/rd-ict.vol3.no14.258


C. Pornavalai, G. Chakraborty, and N. Shiratori, “QoS based routing algorithm in integrated services packet networks,” in Proceedings of International Conference on Network Protocols. IEEE, 1997, pp. 167–174.

S. Chen and K. Nahrstedt, “An overview of quality of service routing for next-generation high-speed networks: problems and solutions,” IEEE Network, vol. 12, pp. 64–79, 1998.

——, “Distributed quality-of-service routing in high-speed networks based on selective probing,” in Proceedings of 23rd Annual Conference on Local Computer Networks (LCN’98). IEEE, 1998, pp. 80–89.

F. A. Kuipers and P. F. Van Mieghem, “Conditions that impact the complexity of QoS routing,” IEEE/ACM Transactions on Networking, vol. 13, no. 4, pp. 717–730, 2005.

R. Guerin, A. Orda, and D. Williams, “QoS routing mechanisms and OSPF extensions,” in Global Telecommunications Conference. IEEE, 1997, pp. 1903–1908.

Z. Wang and J. Crowcroft, “Quality-of-service routing for supporting multimedia applications,” IEEE Journal on Selected Areas in Communications, vol. 14, no. 7, pp. 1228–1234, 1996.

R. A. Guerin and A. Orda, “QoS routing in networks with inaccurate information: theory and algorithms,” IEEE/ACM Transactions on Networking, vol. 7, no. 3, pp. 350–364,1999.

Q. Ma and P. Steenkiste, “Quality-of-Service Routing for Traffic with Performance Guarantees,” in IFIP International Workshop on Quality of Service, 1997, pp. 115–126.

P. Khadivi, S. Samavi, T. Todd, and H. Saidi, “Multiconstraint QoS routing using a new single mixed metric,” in IEEE International Conference on Communications, 2004, pp. 2042–2046.

A. Kulhari, C. Gandhi, and A. Jaiswal, “Multi-constraint Multipath QoS Routing Using Swarm Intelligence,” in International Conference on Computational Intelligence and Communication Networks. IEEE, 2014, pp. 468–471.

X. Wang, S.-H. Yu, J. Dai, and T. Luo, “A Multiple Constraint Quality of Service Routing Algorithm Base on Dominating Tree,” in International Conference on Computational Intelligence and Software Engineering (CiSE 2009). IEEE, 2009, pp. 1–4.

D.-W. Shin, E. K. Chong, and H. J. Siegel, “A multiconstraint QoS routing scheme using the depth-first search method with limited crankbacks,” in IEEE Workshop on High Performance Switching and Routing. IEEE, 2001, pp. 385–389.

“Dijkstra Algorithm.” [Online]. Available: https://www.cs.auckland.ac.nz/software/AlgAnim/dijkstra.html

N. C. Trinh and T. M. Anh, “About a new localized multicriterion routing algorithm–a solution to assure quality of network,” in Proceedings of the International Conference on Communications, Management and Telecommunications (ComManTel). IEEE, 2015, pp. 223–228.

——, “Dynamic set of paths for localized QoS routing with bandwidth-constraint,” in Proceedings of the International Conference on Electronics, Information, and Communications (ICEIC). IEEE, 2016, pp. 1–6.

S. Nelakuditi, Z.-L. Zhang, and D. H. Du, “On selection of candidate paths for proportional routing,” Computer networks, vol. 44, no. 1, pp. 79–102, 2004.

S. Nelakuditi, Z.-L. Zhang, R. P. Tsang, and D. H.-C. Du, “Adaptive proportional routing: a localized QoS routing approach,” IEEE/ACM Transactions on networking, vol. 10, no. 6, pp. 790–804, 2002.

S. Nelakuditi and Z. L. Zhang, Localized Quality of Service Routing for the Internet. Kluwer Academic, June 2003.

S. Nelakuditi and Z.-L. Zhang, “On selection of paths for multipath routing,” in International Workshop on Quality of Service. Springer, 2001, pp. 170–184.

T. A. Al Ghamdi and M. E. Woodward, “Novel localized QoS routing algorithms,” in IEEE 9th Malaysia International Conference on Communications, 2009, pp. 199–204.

F. M. Aldosari and F. Alradady, “Localized QoS routing with end-to-end delay guarantees,” in Tenth International Conference on Information Technology: New Generations (ITNG). IEEE, 2013, pp. 464–472.

ITU, Internet protocol aspects – Quality of service and network performance, ITU-T Std. Y.1500–Y.1599,

[Online]. Available: http://www.itu.int/ITU-T/recommendations/index.aspx?ser=Y

A. Varga, “The OMNeT++ Discrete Event Simulation System, the European Simulation Multiconference,” Prague, Czech Republic, 2001.

A. Shaikh, J. Rexford, and K. G. Shin, “Load-sensitive Routing of Long-lived IP Flows,” in Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, ser. SIGCOMM ’99. ACM, 1999, pp. 215–226.

J. L. Rexford and A. Shaikh, “Efficient precomputation of quality-of-service routes,” Oct. 14 2003, US Patent 6,633,544.

Regular Articles