Un estudio sobre algoritmos basados en restricciones: objetivos ingeniería de tráfico y calidad de servicio
Resumen
El enrutamiento en Internet está basado en la dirección destino y en un algoritmo del camino más corto, esto conlleva a que se congestionen ciertos enlaces debido a que se seleccionan los mismos caminos para muchas comunicaciones. Por otro lado, los algoritmos basados en restricciones toman las decisiones de selección del camino con base en un conjunto de requerimientos que permite escoger el camino más óptimo para un conjunto de restricciones específi co, resolviendo el problema del enrutamiento del camino más corto y proporcionando ventajas adicionales como el soporte de calidad de servicio e ingeniería de tráfi co . En la literatura se ha demostrado que los procesos de los objetivos de ingeniería de tráfi co son NP-díficil, y los de calidad de servicio son NP-completo, esto conduce a que sea un tema abierto para hacer propuestas de algoritmos heurísticos. Por tanto, en este artículo se presenta una revisión general de los algoritmos basados en restricciones propuestos como solución al problema de enrutamiento convencional de Internet en los últimos 15 años, los cuales se han organizado en tres categorías según los objetivos trazados en cada uno de ellos. Estas categorías están enfocadas a las problemáticas actuales en Internet que son la provisión de ingeniería de tráfi co y calidad de servicio. Se presenta una breve descripción de cada uno, resaltando las restricciones utilizadas y los objetivos trazados. Un conocimiento de la taxonomía de estos algoritmos y sus objetivos permite plantear nuevas alternativas al enrutamiento para redes de nueva generación, con nuevas exigencias en sus servicios.
Descargas
Citas
D. Medhi, Network Routing: Algorithms, Protocols, and Architectures, San Francisco, EE.UU: Morgan Kaufmann, 2007.
S. Floyd and M. Allman, “Comments on the Usefulness of Simple Best-Effort Traffic,” IETF RFC5290, 2008.
Y. Ossama and S. Fahmi, “Constraint-Based Routing in the Internet: Basic Principles and Recent Research,” IEEE Communications Surveys, vol. 5, no. 1, pp.2-13, 2003.
F. Kuipers, P. Van Mieghem, T. Korkmaz and M. Krunz, “An Overview of Constraint-Based Path Selection Algorithms for QoS Routing,” IEEE Communications Magazine, pp. 50-55, 2002.
P. Nayak and G. R. Murthy, “Survey on Constrained Based Path Selection QoS Routing Algorithms: MCP and MCOP Problems,” Journal of Information Systems and Communication, pp. 384-390, 2013.
M. Kodialam y T. V. Lakshman, «Minimum interference routing of bandwidth guaranteed tunnels with MPLS traffic engineering applications,» IEEE Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. INFOCOM 2000, vol. 2, pp. 884 - 893, 2000.
A. Karaman, “Constraint-Based Routing in Traffic Engineering,” Computer Networks, pp. 49-54, 2006.
D. Awduche y e. al, « Overview and Principles of Internet Traffic Engineering,» IETF RFC3272, 2002.
L. Y. Becerra and J. Padilla, “Estudio de Propuestas para Soportar Ingeniería de tráfico en Internet,” Entre Ciencia e Ingeniería, vol. 6, no. 11, pp. 53-76, 2012.
E. Rosen, A. Viswanathan and R. Callon, “Multiprotocol Label Switching Architecture,” IETF RFC3031, 2001.
R. Guerin, A. Orda and D. Williams, “QoS routing mechanisms and OSPF extensions,” IEEE GLOBECOM, pp. 1903-1908, 1997.
Z. Wang and J. Crowcroft, “Quality-of-Service Routing for Supporting Multimedia Applications,” IEEE Journal of Selected Areas in Communications,, Vols. Vol. 14,, no. Issue 7, pp. pp.1228--1234, 1996.
J. A. Khan and H. M. Alnuweir, “A Fuzzy Constraint-Based Routing Algorithm for Traffic Engineering,” IEEE GLOBECOM, pp. 1366-1372, 2004.
S. Suri, M. Waldvogel, D. Bauer and P. Ramesh Warkhede, “Profilebased routing and traffic engineering,” Computer Communications, pp. 351-365, 2003.
J. Wang, S. Patek, H. Wang and J. Liebeherr, “Traffic Engineering with AIMD in MPLS Networks,” Lecture Notes in Computer Science, pp. 192-210, 2002.
J. C. d. Oliveira, C. Scoglio, I. F. Akyildiz and G. Uhl, “New preemption policies for DiffServ-aware traffic engineering to minimize rerouting in MPLS networks,” Journal IEEE/ACM Transactions on Networking, pp. 733-745, 2004.
H. Y. Cho, J. Y. Lee y B. C. Kim, «Multi-path Constraint-based Routing Algorithms for MPLS Traffic Engineering.,» IEEE International Conference on Communications., 2003.
J. Tang, C. Siew and G. Feng, “Parallel LSPs for constraint-based routing and load balancing in MPLS networks,” IEEE Proceedings - Communications, vol. 152, no. 1, pp. 6-12, 2005.
E.-S. M. El-Alfy, «Flow-Based Path Selection for Internet Traffic Engineering with NSGA-II,» IEEE 17th International Conference on Telecommunications (ICT)., pp. 621 - 627, 2010.
Y. Zeng and Y. Luo, “A Multi-Constrained Routing Optimization Algorithm in the IP Networks,” 11th International Conference on Natural Computation (ICNC) IEEE, pp. 314 - 318, 2015.
K. Deb, S. Agrawal, A. Pratab, and y T. Meyarivan, «A fast elitist nondominated sorting genetic algorithm for multiobjective optimization:NSGA-II,» IEEE Transactions on Evolutionary Computation, vol. 6, nº 2, p. 182–197., 2002.
P. V. Mieghem and F. A. Kuipers, “Concepts of exact QoS routing algorithms,” IEEE/ACM Transactions on Networking, vol. 12, no. 5,pp. 851 - 864, 2004.
T. Korkmaz and M. M. Krunz, “Routing multimedia traffic with QoS guarantees,” IEEE Transactions on Multimedia , vol. 5, no. 3, pp.429 - 443, 2003.
J. M. Jaffe, “Algorithms for finding paths with multiple constraints,” Networks: An International Journal, pp. 95-116, 1984.
A. Iwata, R. Izmailov, D.-S. Lee, B. Sengupta, G.Ramamurthy and H. Suzuki, “ATM routing algorithm with multiple QoS requirements for multimedia,” IEICE Transactions and Communications, pp. 999-1006, 1996.
H. D. Neve and P. V. Mieghem, “TAMCRA: A Tunable Accuracy Multiple Constraints Routing Algorithm,” Computer Communications, pp. 667-679, 2000.
P. V. Mieghem, H. D. Neve and F. A. Kuipers, “Hop-by-Hop Quality of Service Routing,” Computer Networks, pp. 407-423, 2001.
S. Chen and K. Nahrstedt , “On Finding Multi-constrained Paths,” IEEE, pp. 874-879, 1998.
T. Korkmaz and M. Krunz , “A randomized algorithm for finding a path subject to multiple QoS constraints,” Computer Networks, pp. 251-268, 2001.
T. Korkmaz and M. Krunz, “Multi Constrained Optimal Path Selection,” IEEE INFOCOM, pp. 834-843, 2001.
G. Liu and K. Ramakrishnan, “A*Prune: an algorithm for finding K shortest paths subject to multiple constraints,” IEEE INFOCOM, pp.743-749, 2001.
G. Feng, “The revisit of QoS routing based on non-linear Lagrange relaxation,” International Journal of Communication Systems, pp. 9-22, 2005.
Y. Li, J. Harms and R. Holte, “Fast Exact MultiConstraint Shortest Path Algorithms,” Proceedings of IEEE ICC, pp. 123-130, 2007.
S. Chen, M. Song and S. Sahni, “Two Techniques for Fast Computation of Constrained Shortest Paths,” IEEE/ACM Transactions on Networking , pp. 105-115, 2008.
W. Liu, W. Low and Y. Fang, “An efficient quality of service routing algorithm for delay-sensitive,” Computer Networks, no. 47, pp. 87-104, 2005.
M. Baradaran and M. H. Yaghmaee, “A Constraint Based RoutingAlgorithm For Multimedia Networking,” IAENG International Journal of Computer Science, vol. 33, no. 2, p. 8, 2007.
P. Prakash and S. Selvan, “A Feasible Path Selection QoS Routing Algorithm with two Constraints in Packet Switched Networks,” World Academy of Science: Engineering and Technology, pp. 444-450, 2008.
G. Y. Handler y I. Zang, «A dual algorithm for the constrained shortest path problem,» Networks, pp. 293-310, 1980.
L. Guo and I. Matta, “Search space reduction in QoS routing,” Computer Networks, pp. 73-88, 2003.
X. Yuan and X. Liu, “Heuristic algorithms for multi-constrained quality of service routing,” IEEE INFOCOM, pp. 844-853, 2001.
F. A. Kuipers and P. V. Mieghem, “Bi-directional Search in QoS Routing,” Lecture Notes in Computer Science, pp. 102-111, 2003.
T. Anjali and C. Scoglio, “Traffic Routing in MPLS Networks Based on QoS Estimation and Forecast,” IEEE Global Telecommunications Conference, vol. 2, pp. 1135 - 1139, 2004.
H. Lin, D. Xue-wu and X. Jin, “Multi-Constrained Routing Based on Tabu Search,” IEEE International Conference on Control and Automation, pp. 157 - 161, 2007.
G. vincent and T.Sasipraba, “An Efficient Routing Algorithm for Improving the QoS in Internet,” International Conference on Emerging Trends in Robotics and Communication Technologies (INTERACT), International Conference on, pp. 381 - 387, 2010.
S.-M. Dragos, “Hierarchical QoS Routing by Using Multi-Constrained Macro-Routing,” 7th International Conference on Next Generation Web Services Practices (NWeSP)., pp. 105 - 112, 2011.
H. Cui, J. Li, X. Liu and Y. Cai, “Particle Swarm Optimization for Multi-constrained Routing in Telecommunication Networks,” I.J.Computer Network and Information Security,, pp. 10-17, 2011.
B. Zhang, J. Hao and H. T. Mouftah, “Bidirectional Multi- Constrained Routing Algorithms,” IEEE TRANSACTIONS ON COMPUTERS, vol. 63, no. 9, pp. 2174 - 2186, 2014.
C. T. PhuongThanh, H. H. Nam and T. C. Hung, “A heuristic algorithm for bandwidth delay constrained routing,” International Conference on Advanced Technologies for Communications, pp. 99 - 104, 2014.
S. Avallone and G. Ventre, “Q-BATE: A QoS Constraint-based Traffic Engineering Routing Algorithm,” IEEE-2nd Conference on Next Generation Internet Design and Engineering, p. 8pp., 2006.
S. Kulkarni, R. Sharma and I. Mishra, “New Bandwidth Guaranteed QoS Routing Algorithm for MPLS Networks,” Journal of Emerging Trends in Computing and Information Sciences, vol. 3, no. 3, pp.384-389, 2012.
V. Kher, A. Arman and D. S. Saini, “Hybrid evolutionary MPLS Tunneling Algorithm based on high priority bits,” International conference on futuristic trend in computational analysis and knowledge management, pp. 495-499, 2015.
<
Revista Entre Ciencia e Ingeniería .png)
entrecei@ucp.edu.co.png)
ISSN (Impreso) 1909-8367 - ISSN (En Línea) 2539-4169
Attribution-NonCommercial 4.0 International (CC By-NC 4.0)
.png)
Carrera 21 No. 49-95 Av. de las Américas, Pereira, Risaralda, Colombia