Preliminares de la adaptación del algoritmo PA-VNE para la reasignación de redes virtuales mapeadas y la selección entre diferentes tipos de métricas

Nestor Alzate Mejia; José Roberto de A. Amazonas; Juan Felipe Botero

Nestor Alzate Mejia universidad Católica de Pereira
José Roberto de A. Amazonas EPUSP, Sao Paulo (Brasil)
Juan Felipe Botero Universidad de Antioquia

Palabras clave: Algebra de Caminos, backtracking, mapeo de redes virtuales,, redes definidas por software, relación competitiva, virtualización de redes

Resumen

La arquitectura actual de la internet no permite la introducción de innovaciones debido, entre otras razones, a la competencia entre proveedores de servicio. Como una posible solución a este problema, se ha propuesto, la virtualización de red. Para la implementación de esta tecnología se necesita de un algoritmo que pueda ubicar las redes virtuales sobre los recursos de la red física, de una forma óptima, según las métricas a considerar. Este artículo presenta los avances preliminares de la investigación acerca de la optimización del algoritmo PA-VNE y su implementación en una red definida por software.

Descargas

La descarga de datos todavía no está disponible.

Biografía del autor

Nestor Alzate Mejia, universidad Católica de Pereira

Se graduó como Ingeniero de Sistemas de la Universidad Cooperativa de Colombia. Obtuvo el título de Especialista en Telecomunicaciones de la Universidad Autónoma de Bucaramanga. Es aspirante a Magister en Ingeniería de Sistemas y Computación de la Universidad Tecnológica de Pereira. Actualmente es profesor de tiempo completo en la Universidad Católica de Pereira. Sus principales intereses de investigación son la Virtualización de Redes y las Redes Definidas por Software.

José Roberto de A. Amazonas, EPUSP, Sao Paulo (Brasil)

Graduado en ingeniería eléctrica de la Escuela Politécnica de la Universidad de São Paulo (EPUSP), Brasil, en 1979. Recibió el M.Sc., Ph.D. y grados postdoctorales de EPUSP en 1983, 1988 y 1996, respectivamente. Es profesor asociado del Departamento de Telecomunicaciones e Ingeniería de Control en EPUSP, donde está a cargo de la educación e investigación de comunicaciones ópticas y redes de comunicaciones de alta velocidad. Ocupó diversos cargos en universidades de Brasil y Europa. También ha dirigido la investigación en colaboración con varias empresas brasileñas, europeas y norteamericanas. Sus intereses de investigación se encuentran en el área de las comunicaciones ópticas, redes cableadas e inalámbricas, la calidad de servicio (QoS) y el aprendizaje a distancia.

Juan Felipe Botero, Universidad de Antioquia

Es profesor en el Departamento de Ingeniería Electrónica y de Telecomunicaciones de la Universidad de Antioquia, Medellín, Colombia. En 2006, recibió su grado en Ingeniería de Sistemas por la Universidad de Antioquia. En 2008 y 2013 recibió sus grados de M.Sc. y Ph.D. en Ingeniería Telemática por la Universidad Politécnica de Cataluña, Barcelona, España. En 2013, se unió al Grupo de Investigación en Telecomunicaciones Aplicadas (GITA), que actualmente dirige. Sus principales intereses de investigación incluyen calidad de servicio, redes definidas por software, virtualización de redes, computación en la nube, optimización y asignación de recursos en diferentes arquitecturas de red.

Citas

. Turner, “Virtualizing the Net - a strategy for enabling network innovation [Keynote 2],” in High Performance Interconnects, 2004. Proceedings. 12th Annual IEEE Symposium on, 2004, pp. 2-2.

N. M. M. K. Chowdhury and R. Boutaba, “A survey of network virtualization,” Computer Networks, vol. 54, pp. 862-876, 4/8/ 2010.

N. M. M. K. Chowdhury and R. Boutaba, “Network virtualization: state of the art and research challenges,” Communications Magazine, IEEE, vol. 47, pp. 20-26, 2009.

O. Braham, A. Amamou, and G. Pujolle, “Virtual Network Urbanization,” in Communications: Wireless in Developing Countries and Networks of the Future. vol. 327, A. Pont, G. Pujolle, and S. V. Raghavan, Eds., ed: Springer Berlin Heidelberg, 2010, pp. 182-193.

Z. Sheng, Q. Zhuzhong, W. Jie, L. Sanglu, and L. Epstein, “Virtual Network Embedding with Opportunistic Resource Sharing,” Parallel and Distributed Systems, IEEE Transactions on, vol. 25, pp. 816-827, 2014.

A. Fischer, J. F. Botero, M. Till Beck, H. de Meer, and X. Hesselbach, “Virtual Network Embedding: A Survey,” Communications Surveys & Tutorials, IEEE, vol. 15, pp. 1888-1906, 2013.

Z. Zhang, S. Su, Y. Lin, X. Cheng, K. Shuang, and P. Xu, “Adaptive multi-objective artificial immune system based virtual network embedding,” Journal of Network and Computer Applications, vol. 53, pp. 140-155, 7// 2015.

X. Guan, B.-Y. Choi, and S. Song, “Energy efficient virtual network embedding for green data centers using data center topology and future migration,” Computer Communications, 2015.

G. Schaffrath, C. Werle, P. Papadimitriou, A. Feldmann, R. Bless, A. Greenhalgh, et al., “Network virtualization architecture: proposal and initial prototype,” presented at the Proceedings of the 1st ACM workshop on Virtualized infrastructure systems and architectures, Barcelona, Spain, 2009.

H. Yoonseon, L. Jian, C. Jae-Yoon, Y. Jae-Hyoung, and J. W. K. Hong, “SAVE: Energy-aware Virtual Data Center embedding and Traffic Engineering using SDN,” in Network Softwarization (NetSoft), 2015 1st IEEE Conference on, 2015, pp. 1-9.

M. Jammal, T. Singh, A. Shami, R. Asal, and Y. Li, “Software defined networking: State of the art and research challenges,” Computer Networks, vol. 72, pp. 74-98, 10/29/ 2014.

J. F. Botero, M. Molina, X. Hesselbach-Serra, and J. R. Amazonas, “A novel paths algebra-based strategy to flexibly solve the link mapping stage of VNE problems,” Journal of Network and Computer Applications, vol. 36, pp. 1735-1752, 11// 2013.

Y. Yuan, C. Wang, N. Zhu, C. Wan, and C. Wang, “Virtual Network Embedding Algorithm Based Connective Degree and Comprehensive Capacity,” in Intelligent Computing Theories. vol. 7995, D.-S. Huang, V. Bevilacqua, J. Figueroa, and P. Premaratne, Eds., ed: Springer Berlin Heidelberg, 2013, pp. 250-258.

I. Fajjari, N. Aitsaadi, G. Pujolle, and H. Zimmermann, “AdaptiveVNE: A flexible resource allocation for virtual network embedding algorithm,” in Global Communications Conference (GLOBECOM), 2012 IEEE, 2012, pp. 2640-2646.

I. Fajjari, N. Aitsaadi, G. Pujolle, and H. Zimmermann, “An optimised dynamic resource allocation algorithm for Cloud’s backbone network,” in Local Computer Networks (LCN), 2012 IEEE 37th Conference on, 2012, pp. 252-255.

H. Di, H. Yu, V. Anand, L. Li, G. Sun, and B. Dong, “Efficient Online Virtual Network Mapping Using Resource Evaluation,” Journal of Network and Systems Management, vol. 20, pp. 468-488, 2012/12/01 2012.

J. Lischka and H. Karl, “A virtual network mapping algorithm based on subgraph isomorphism detection,” presented at the Proceedings of the 1st ACM workshop on Virtualized infrastructure systems and architectures, Barcelona, Spain, 2009.

S. Escriche Fernández, “Network virtualization and traffic engineering in Software-Defined Networks,” Master thesis, Universitat Politècnica de Catalunya, 2014.

G. Even, M. Medina, G. Schaffrath, and S. Schmid, “Competitive and deterministic embeddings of virtual networks,” Theoretical Computer Science, vol. 496, pp. 184-194, 7/22/ 2013.

L. Xing, L. Hancheng, Z. Wei, and H. Peilin, “VNE-RFD: Virtual network embedding with resource fragmentation consideration,” in Global Communications Conference (GLOBECOM), 2014 IEEE, 2014, pp. 1842-1847.

B. Wanis, N. Samaan, and A. Karmouch, “Substrate network house cleaning via live virtual network migration,” in Communications (ICC), 2013 IEEE International Conference on, 2013, pp. 2256-2261.

H. Jmila, I. Houidi, and D. Zeghlache, “RSforEVN: Node reallocation algorithm for virtual networks adaptation,” in Computers and Communication (ISCC), 2014 IEEE Symposium on, 2014, pp. 1-7.

T. Phuong Nga, L. Casucci, and A. Timm-Giel, “Optimal mapping of virtual networks considering reactive reconfiguration,” in Cloud Universidad Católica de Pereira Networking (CLOUDNET), 2012 IEEE 1st International Conference on, 2012, pp. 35-40.

J. F. Botero, “Study, evaluation and contributions to new algorithms for the embedding problem in a network virtualization environment,” Thesis Doctoral, Universitat Politècnica de Catalunya, 2013.

N. Feamster, J. Rexford, and E. Zegura, “The road to SDN: an intellectual history of programmable networks,” SIGCOMM Comput. Commun. Rev., vol. 44, pp. 87-98, 2014.

M. Casado, N. Foster, and A. Guha, “Abstractions for softwaredefined networks,” Commun. ACM, vol. 57, pp. 86-95, 2014.

Y. Jarraya, T. Madi, and M. Debbabi, “A Survey and a Layered Taxonomy of Software-Defined Networking,” Communications Surveys & Tutorials, IEEE, vol. 16, pp. 1955-1980, 2014.

R. Guerzoni, R. Trivisonno, I. Vaishnavi, Z. Despotovic, A. Hecker, S. Beker, et al., “A novel approach to virtual networks embedding for SDN management and orchestration,” in Network Operations and Management Symposium (NOMS), 2014 IEEE, 2014, pp. 1-7.

C. Papagianni, G. Androulidakis, and S. Papavassiliou, “Virtual Topology Mapping in SDN-Enabled Clouds,” in Network Cloud Computing and Applications (NCCA), 2014 IEEE 3rd Symposium on, 2014, pp. 62-67.

M. Demirci and M. Ammar, “Design and analysis of techniques for mapping virtual networks to software-defined network substrates,” Computer Communications, vol. 45, pp. 1-10, 6/1/ 2014.

D. Drutskoy, E. Keller, and J. Rexford, “Scalable Network Virtualization in Software-Defined Networks,” Internet Computing, IEEE, vol. 17, pp. 20-27, 2013.

R. Riggio, F. De Pellegrini, E. Salvadori, M. Gerola, and R. Doriguzzi Corin, “Progressive virtual topology embedding in OpenFlow networks,” in Integrated Network Management (IM 2013), 2013 IFIP/IEEE International Symposium on, 2013, pp. 1122-1128.

H. Wen, P. Tiwary, and T. Le-Ngoc, “Network Virtualization: Overview,” in Wireless Virtualization, ed: Springer International Publishing, 2013, pp. 5-10.

N. Fernandes, M. D. Moreira, I. Moraes, L. Ferraz, R. Couto, H. T. Carvalho, et al., “Virtual networks: isolation, performance, and trends,” annals of telecommunications - annales des télécommunications, vol. 66, pp. 339-355, 2011/06/01 2011.

X. Chen, C. Li, and Y. Jiang, “Optimization Model and Algorithm for Energy Efficient Virtual Node Embedding,” Communications Letters, IEEE, vol. 19, pp. 1327-1330, 2015.

J. Liao, M. Feng, S. Qing, T. Li, and J. Wang, “LIVE: Learning and Inference for Virtual Network Embedding,” Journal of Network and Systems Management, pp. 1-30, 2015/05/13 2015.

M. Rahman, I. Aib, and R. Boutaba, “Survivable Virtual Network Embedding,” in NETWORKING 2010. vol. 6091, M. Crovella, L. Feeney, D. Rubenstein, and S. V. Raghavan, Eds., ed: Springer Berlin Heidelberg, 2010, pp. 40-52.

M. Melo, J. Carapinha, S. Sargento, L. Torres, P. Tran, U. Killat, et al., “Virtual Network Mapping – An Optimization Problem,” in Mobile Networks and Management. vol. 97, K. Pentikousis, R. Aguiar, S. Sargento, and R. Agüero, Eds., ed: Springer Berlin Heidelberg, 2012, pp. 187-200.

F. Zhu and H. Wang, “A modified ACO algorithm for virtual network embedding based on graph decomposition,” Computer Communications.

D. Jian, H. Tao, W. Jian, H. Wenbo, L. Jiang, and L. Yunjie, “Virtual network embedding through node connectivity,” The Journal of China Universities of Posts and Telecommunications, vol. 22, pp. 17- 56, 2// 2015.

A. Jarray and A. Karmouch, “Decomposition Approaches for Virtual Network Embedding With One-Shot Node and Link Mapping,” Networking, IEEE/ACM Transactions on, vol. PP, pp. 1-1, 2014.

Z. Ye, L. Yong, J. Depeng, S. Li, and Z. Lieguang, “A virtual network embedding scheme with two-stage node mapping based on physical resource migration,” in Communication Systems (ICCS), 2010 IEEE International Conference on, 2010, pp. 761-766.

L. Wenzhi, X. Yang, M. Shaowu, and T. Xiongyan, “Completing virtual network embedding all in one mathematical programming,” in Electronics, Communications and Control (ICECC), 2011 International Conference on, 2011, pp. 183-185.

G. Xiujiao, Y. Hongfang, V. Anand, G. Sun, and D. Hao, “A new algorithm with coordinated node and link mapping for virtual network embedding based on LP relaxation,” in Communications and Photonics Conference and Exhibition (ACP), 2010 Asia, 2010, pp. 152-153.

W. de Paula Herman and J. R. de Almeida Amazonas, “Hop-byhop Routing Convergence Analysis Based on Paths Algebra,” in Electronics, Robotics and Automotive Mechanics Conference, 2007. CERMA 2007, 2007, pp. 9-14.

Y. YoungSeok and B. A. Myers, “An exploratory study of backtracking strategies used by developers,” in Cooperative and Human Aspects of Software Engineering (CHASE), 2012 5th International Workshop on, 2012, pp. 138-144.

A. Chmeiss, Sai, x, and L. s, “Constraint satisfaction problems : backtrack search revisited,” in Tools with Artificial Intelligence, 2004. ICTAI 2004. 16th IEEE International Conference on, 2004, pp. 252-257.

K. T. Herley, A. Pietracaprina, and G. Pucci, “Deterministic parallel backtrack search,” Theoretical Computer Science, vol. 270, pp. 309- 324, 1/6/ 2002.

R. Solis-Oba and G. Persiano, “Special Issue on Approximation and Online Algorithms,” Theory of Computing Systems, vol. 56, pp. 1-2, 2015/01/01 2015.

A. Hakiri, A. Gokhale, P. Berthou, D. C. Schmidt, and T. Gayraud, “Software-Defined Networking: Challenges and research opportunities for Future Internet,” Computer Networks, vol. 75, Part A, pp. 453-471, 12/24/ 2014.

Y. Xingbin, H. Shanguo, W. Shouyu, W. Di, G. Yuming, N. Xiaobing, et al., “Software defined virtualization platform based on doubleFlowVisors in multiple domain networks,” in Communications and Networking in China (CHINACOM), 2013 8th International ICST Conference on, 2013, pp. 776-780.

R. Jain and S. Paul, “Network virtualization and software defined networking for cloud computing: a survey,” Communications Magazine, IEEE, vol. 51, pp. 24-31, 2013.

K. Bakshi, “Considerations for Software Defined Networking (SDN): Approaches and use cases,” in Aerospace Conference, 2013 IEEE, 2013, pp. 1-9.

Z. Boyang, G. Wen, Z. Shanshan, L. Xinjia, D. Zhong, W. Chunming, et al., “Virtual network mapping for multi-domain data plane in Software-Defined Networks,” in Wireless Communications, Vehicular Technology, Information Theory and Aerospace & Electronic Systems (VITAE), 2014 4th International Conference on, 2014, pp. 1-5.

Y. Xin, I. Baldine, A. Mandal, C. Heermann, J. Chase, and A. Yumerefendi, “Embedding virtual topologies in networked clouds,” presented at the Proceedings of the 6th International Conference on Future Internet Technologies, Seoul, Republic of Korea, 2011.

H. Wen, P. Tiwary, and T. Le-Ngoc, “Network Virtualization Technologies and Techniques,” in Wireless Virtualization, ed: Springer International Publishing, 2013, pp. 25-40.

D. Meyer, “The Software-Defined-Networking Research Group,” Internet Computing, IEEE, vol. 17, pp. 84-87, 2013.

S. Salsano, N. Blefari-Melazzi, A. Detti, G. Morabito, and L. Veltri, “Information centric networking over SDN and OpenFlow: Architectural aspects and experiments on the OFELIA testbed,” Computer Networks, vol. 57, pp. 3207-3221, 11/13/ 2013.

M. Berman, J. S. Chase, L. Landweber, A. Nakao, M. Ott, D. Raychaudhuri, et al., “GENI: A federated testbed for innovative network experiments,” Computer Networks, vol. 61, pp. 5-23, 3/14/ 2014.

M. H. Raza, S. C. Sivakumar, A. Nafarieh, and B. Robertson, “A Comparison of Software Defined Network (SDN) Implementation Strategies,” Procedia Computer Science, vol. 32, pp. 1050-1055, // 2014.

R. Sherwood, G. Gibb, K.-K. Yap, G. Appenzeller, M. Casado, N. McKeown, et al., “FlowVisor: A Network Virtualization Layer,” Deutsche Telekom Inc. R&D Lab, Stanford University, Nicira Networks2009.

D. Schwerdel, B. Reuther, T. Zinner, P. Müller, and P. Tran-Gia, “Future Internet research and experimentation: The G-Lab approach,” Computer Networks, vol. 61, pp. 102-117, 3/14/ 2014.

J. F. Botero, X. Hesselbach, M. Duelli, D. Schlosser, A. Fischer, and H. de Meer, “Energy Efficient Virtual Network Embedding,” Communications Letters, IEEE, vol. 16, pp. 756-759, 2012.

L. Nonde, T. E. H. El-Gorashi, and J. M. H. Elmirghani, “Green Virtual Network Embedding in optical OFDM cloud networks,” in Transparent Optical Networks (ICTON), 2014 16th International Conference on, 2014, pp. 1-5.

Y. Zilong, A. N. Patel, P. N. Ji, Q. Chunming, and W. Ting, “Virtual infrastructure embedding over software-defined flex-grid optical networks,” in Globecom Workshops (GC Wkshps), 2013 IEEE, 2013, pp. 1204-1209.

D. Simeonidou, R. Nejabati, and M. P. Channegowda, “Software defined optical networks technology and infrastructure: Enabling software-defined optical network operations,” in Optical Fiber Communication Conference and Exposition and the National Fiber Optic Engineers Conference (OFC/NFOEC), 2013, 2013, pp. 1-3.

M. F. Bari, R. Boutaba, R. Esteves, L. Z. Granville, M. Podlesny, M. G. Rabbani, et al., “Data Center Network Virtualization: A Survey,” Communications Surveys & Tutorials, IEEE, vol. 15, pp. 909-928, 2013.

S. Mehraghdam, M. Keller, and H. Karl, “Specifying and placing chains of virtual network functions,” in Cloud Networking (CloudNet), 2014 IEEE 3rd International Conference on, 2014, pp. 7-13.

M. R. C. Faizul Bari, Shihabur; Ahmed, Reaz; Boutaba, Raouf, “ On Orchestrating Virtualized Network Functions,” 2015.

Preliminares de la adaptación del algoritmo PA-VNE para la reasignación de redes virtuales mapeadas y la selección entre diferentes tipos de métricas

Resumen

Descargas

Biografía del autor

Citas

Revista Entre Ciencia e Ingeniería

Attribution-NonCommercial 4.0 International (CC By-NC 4.0)