L’Ecole doctorale : Ecole Doctorale de l’Institut Polytechnique de Paris
\net le Laboratoire de recherche SAMOVAR pr\u00e9sentent <\/p>\n
Autoris\u00e9 \u00e0 pr\u00e9senter ses travaux en vue de l\u2019obtention du Doctorat de l’Institut Polytechnique de Paris, pr\u00e9par\u00e9 \u00e0 T\u00e9l\u00e9com SudParis en : SOUTENANCE EN VISIOCONFERENCE – Dispositions exceptionnelles durant la crise sanitaire li\u00e9e au Covid19 : ordonnance n\u00b0 2020-351 du 27 mars 2020 – Arr\u00eat\u00e9 du 21 avril 2020 – NOR : ESRS2009945A<\/p>\n Membres du jury :<\/strong><\/p>\n R\u00e9sum\u00e9 :<\/strong><\/p>\n Cette th\u00e8se traite du placement optimal et heuristique de fonctions r\u00e9seau et de cha\u00eenes de fonction r\u00e9seau dans des infrastructures cloud et r\u00e9seau virtualis\u00e9es. L’\u00e9mergence de la virtualisation des fonctions r\u00e9seau, connu sous l’acronyme NFV pour Network Function Virtualization, permet de d\u00e9coupler les fonctions r\u00e9seau en mode logiciel du mat\u00e9riel d’h\u00e9bergement et de s’appuyer sur des serveurs g\u00e9n\u00e9riques et d’\u00e9viter l’usage de, et la d\u00e9pendance \u00e0, des mat\u00e9riels d\u00e9di\u00e9s voire propri\u00e9taires. Le placement de fonctions r\u00e9seau virtualis\u00e9es (repr\u00e9sent\u00e9es par VNF, Virtualized Network Functions) est NP-Difficile puisqu’il s’agit de projeter un petit graphe de ressources virtuelles sur un graphe plus grand (graphe de l’infrastructure d’h\u00e9bergement). Les solutions optimales, en particulier la programmation lin\u00e9aire en nombre entier (ILP), ne passent pas \u00e0 l’\u00e9chelle. Sachant que la demande est dynamique et peut varier dans le temps et que le r\u00e9seau est lui m\u00eame variable dans le temps, il est important de pr\u00e9voir des adaptations des placements. Cela peut s’effectuer par de l’\u00e9lasticit\u00e9 sur les ressources d’h\u00e9bergement r\u00e9serv\u00e9es \u00e0 une fonction r\u00e9seau virtualis\u00e9e, \u00e0 un graphe de service r\u00e9seau et par une extension du graphe de service lui m\u00eame en fonction du contexte et des exigences des utilisateurs ou tenants. La th\u00e8se propose une famille d’algorithmes pour le placement de cha\u00eenes de services (ou fonctions) r\u00e9seau avec la possibilit\u00e9 d’\u00e9tendre les ressources d’h\u00e9bergement des VNFs (c’est \u00e0 dire assurer l’\u00e9lasticit\u00e9 du service d’h\u00e9bergement en augmentant les ressources allou\u00e9es ou en g\u00e9n\u00e9rant plusieurs instances de VNFs pour \u00e9couler le trafic et r\u00e9pondre \u00e0 la demande) en plus du placement initial. Une solution en programmation en nombre entier est \u00e9labor\u00e9e et aussi utilis\u00e9e comme r\u00e9f\u00e9rence pour une comparaison avec l’\u00e9tat de l’art et avec les extensions propos\u00e9es. L’optimisation \u00e9tant effectu\u00e9e en instantan\u00e9e au fur \u00e0 mesure de l’arriv\u00e9e des demandes, une \u00e0 la fois, une solution qui regroupe plusieurs demandes pour y r\u00e9pondre simultan\u00e9ment, en \u00e9laborant un graphe composite, permet d’am\u00e9liorer les performances. Cette approche connue sous le nom de \u00ab\u00a0batch\u00a0\u00bb n’am\u00e9liore que partiellement la performance, la r\u00e9compense sur le long terme (en efficacit\u00e9, minimisation des ressources consomm\u00e9es, et en \u00e9quilibrage de charge) est n\u00e9cessairement limit\u00e9e. La th\u00e8se s’est pench\u00e9e aussi sur l’extension de graphes de services r\u00e9seau, de tenants, d\u00e9j\u00e0 d\u00e9ploy\u00e9s, en adoptant une approche de type arbre de recouvrement, Spanning Tree. Plus sp\u00e9cifiquement une mod\u00e9lisation du probl\u00e8me en un \u00ab\u00a0Steiner Tree Problem\u00a0\u00bb a conduit \u00e0 des performances proches de l’optimal pour des extensions de graphes au fil des demandes, en les traitant s\u00e9par\u00e9ment. Les travaux de th\u00e8se sont par la suite revenus sur la rentabilit\u00e9 sur le long terme des algorithmes, en approchant le placement de cha\u00eenes de services et fonctions r\u00e9seau comme un objectif long terme via de l’apprentissage par renforcement en se souciant plus de la rentabilit\u00e9 et de l’efficacit\u00e9 long terme des algorithmes contrairement aux approches visant exclusivement l’optimalit\u00e9 instantan\u00e9e \u00e0 chaque nouvelle demande. Cette th\u00e8se a permis de faire avancer autant que faire se peut l’\u00e9tat de l’art du placement optimal dans les infrastructures cloud et r\u00e9seau partag\u00e9es. Notamment, le probl\u00e8me, et besoin, d’extension de graphes, de tenants, d\u00e9j\u00e0 d\u00e9ploy\u00e9s, sans perturber l’h\u00e9bergement initial, a re\u00e7u peu d’attention. Pourtant ce besoin est essentiel pour r\u00e9pondre \u00e0 des d\u00e9ploiements additionnels de nouvelles fonctions et services r\u00e9seau, et pour r\u00e9agir aux d\u00e9gradations et \u00e0 l’accroissement de la demande, aux attaques et pour assurer l’introduction de nouveaux services et fonctions de s\u00e9curit\u00e9 autour du graphe initial. L’approche peut aussi r\u00e9pondre \u00e0 des modifications de graphes et d’isolations d’une partie (d\u00e9fectueuse ou compromise) d’un graphe et de son remplacement par d’autres services et graphes fiables et non alt\u00e9r\u00e9s.<\/p>\n Abstract :<\/strong><\/p>\n Network Function Virtualization (NFV) is an innovative emerging concept that decouples network functions (such as firewalls, DNS, NATs, load balancers, etc.) from dedicated hardware devices (the traditional expensive middleboxes). This decoupling enables hosting of network services, known as Virtualized Network Functions (VNFs), on commodity hardware (such as switches or servers) and thus facilitates and accelerates service deployment and management by providers, improves flexibility, leads to efficient and scalable resource usage, and reduces costs. This paradigm is a major turning point in the evolution of networking, as it introduces high expectations for enhanced economical network services, as well as major technical challenges. One of the main technical challenges in this domain is the optimal placement of the VNFs within the hosting infrastructures. This placement has a critical impact on the performance of the network, as well as on its reliability and operation cost. The VNF Placement and Chaining Problem is NP-Hard and there is a need for placement approaches that can scale with problem size and find good solutions in acceptable times. The overarching goal of this thesis is to enable dynamic virtual network resources provisioning to deal with demand fluctuation during the virtual network lifetime, and to enhance the substrate resource usage. Reserving a fixed amount of resources is inefficient to satisfy the VNF resource requirements. To cope with these problems, we propose dynamic resource management strategies. In this thesis, both exact and heuristic algorithms are designed and evaluated in terms of optimality, complexity, ability to scale, and compared with the state of the art. Elastic mechanisms and scaling algorithms are first presented to improve adaptation and deployment of virtualized network functions in NFV infrastructures to support increasing demand while increasing provider’s revenue. Since network providers not only need to control, classify and steer user and application traffic flows in their dedicated slices but also want to extend their already acquired and operational virtual networks or slices with additional service graphs, the thesis proposes extension algorithms of already hosted network functions graphs without disrupting initially deployed and active service instances. The proposed algorithms extend already deployed network services and functions graphs to respond to new demands while taking into account the constraint of minimizing the impact on the original service graphs. The extension algorithms are particularly useful and suitable for situations where already deployed graphs need to be enhanced with new features and properties (adding new functions) and modified to react to degradation and attacks such as removing a fraction of the graph and replacing with new complex and composed functions into more capable and uncompromised graphs. The thesis also addresses the VNF placement and chaining problem in an online and in a batch mode to improve performance in terms of longer time reward. An enhanced Reinforcement Learning-based approach is also proposed to improve the long term reward beyond what the previous methods can achieve. This is analyzed and realized for a load balancing objective but can be adjusted for other criteria.<\/p>\n","protected":false},"excerpt":{"rendered":" L’Ecole doctorale : Ecole Doctorale de l’Institut Polytechnique de Paris et le Laboratoire de recherche SAMOVAR pr\u00e9sentent l\u2019AVIS DE SOUTENANCE de Monsieur Omar HOUIDI Autoris\u00e9 \u00e0 pr\u00e9senter ses travaux en vue de l\u2019obtention du Doctorat de l’Institut Polytechnique de Paris, pr\u00e9par\u00e9 \u00e0 T\u00e9l\u00e9com SudParis en : R\u00e9seaux, Informations et Communications \u00ab Algorithmes exacts et heuristiques […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"ocean_post_layout":"","ocean_both_sidebars_style":"","ocean_both_sidebars_content_width":0,"ocean_both_sidebars_sidebars_width":0,"ocean_sidebar":"","ocean_second_sidebar":"","ocean_disable_margins":"enable","ocean_add_body_class":"","ocean_shortcode_before_top_bar":"","ocean_shortcode_after_top_bar":"","ocean_shortcode_before_header":"","ocean_shortcode_after_header":"","ocean_has_shortcode":"","ocean_shortcode_after_title":"","ocean_shortcode_before_footer_widgets":"","ocean_shortcode_after_footer_widgets":"","ocean_shortcode_before_footer_bottom":"","ocean_shortcode_after_footer_bottom":"","ocean_display_top_bar":"default","ocean_display_header":"default","ocean_header_style":"","ocean_center_header_left_menu":"","ocean_custom_header_template":"","ocean_custom_logo":0,"ocean_custom_retina_logo":0,"ocean_custom_logo_max_width":0,"ocean_custom_logo_tablet_max_width":0,"ocean_custom_logo_mobile_max_width":0,"ocean_custom_logo_max_height":0,"ocean_custom_logo_tablet_max_height":0,"ocean_custom_logo_mobile_max_height":0,"ocean_header_custom_menu":"","ocean_menu_typo_font_family":"","ocean_menu_typo_font_subset":"","ocean_menu_typo_font_size":0,"ocean_menu_typo_font_size_tablet":0,"ocean_menu_typo_font_size_mobile":0,"ocean_menu_typo_font_size_unit":"px","ocean_menu_typo_font_weight":"","ocean_menu_typo_font_weight_tablet":"","ocean_menu_typo_font_weight_mobile":"","ocean_menu_typo_transform":"","ocean_menu_typo_transform_tablet":"","ocean_menu_typo_transform_mobile":"","ocean_menu_typo_line_height":0,"ocean_menu_typo_line_height_tablet":0,"ocean_menu_typo_line_height_mobile":0,"ocean_menu_typo_line_height_unit":"","ocean_menu_typo_spacing":0,"ocean_menu_typo_spacing_tablet":0,"ocean_menu_typo_spacing_mobile":0,"ocean_menu_typo_spacing_unit":"","ocean_menu_link_color":"","ocean_menu_link_color_hover":"","ocean_menu_link_color_active":"","ocean_menu_link_background":"","ocean_menu_link_hover_background":"","ocean_menu_link_active_background":"","ocean_menu_social_links_bg":"","ocean_menu_social_hover_links_bg":"","ocean_menu_social_links_color":"","ocean_menu_social_hover_links_color":"","ocean_disable_title":"default","ocean_disable_heading":"default","ocean_post_title":"","ocean_post_subheading":"","ocean_post_title_style":"","ocean_post_title_background_color":"","ocean_post_title_background":0,"ocean_post_title_bg_image_position":"","ocean_post_title_bg_image_attachment":"","ocean_post_title_bg_image_repeat":"","ocean_post_title_bg_image_size":"","ocean_post_title_height":0,"ocean_post_title_bg_overlay":0.5,"ocean_post_title_bg_overlay_color":"","ocean_disable_breadcrumbs":"default","ocean_breadcrumbs_color":"","ocean_breadcrumbs_separator_color":"","ocean_breadcrumbs_links_color":"","ocean_breadcrumbs_links_hover_color":"","ocean_display_footer_widgets":"default","ocean_display_footer_bottom":"default","ocean_custom_footer_template":"","ocean_post_oembed":"","ocean_post_self_hosted_media":"","ocean_post_video_embed":"","ocean_link_format":"","ocean_link_format_target":"self","ocean_quote_format":"","ocean_quote_format_link":"post","ocean_gallery_link_images":"on","ocean_gallery_id":[],"footnotes":""},"categories":[278],"tags":[],"class_list":["post-1309","post","type-post","status-publish","format-standard","hentry","category-theses-samovar-fr","entry"],"_links":{"self":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts\/1309","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/comments?post=1309"}],"version-history":[{"count":1,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts\/1309\/revisions"}],"predecessor-version":[{"id":1395,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/posts\/1309\/revisions\/1395"}],"wp:attachment":[{"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/media?parent=1309"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/categories?post=1309"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/samovar.telecom-sudparis.eu\/index.php\/wp-json\/wp\/v2\/tags?post=1309"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nR\u00e9seaux, Informations et Communications
\n\u00ab Algorithmes exacts et heuristiques pour le chainage de services r\u00e9seaux virtualis\u00e9s \u00bb
\nle JEUDI 25 JUIN 2020 \u00e0 10h30<\/strong><\/p>\n\n\n
\n Mme Lynda MOKDAD, Professeure,
\nUniversit\u00e9 Paris-Est Cr\u00e9teil, FRANCE<\/td>\nRapporteur<\/td>\n<\/tr>\n \n M. Fr\u00e9d\u00e9ric GIROIRE, Charg\u00e9 de recherche,
\nCNRS, I3S, FRANCE<\/td>\nRapporteur<\/td>\n<\/tr>\n \n M. Marcelo DIAS DE AMORIM, Directeur de recherche au CNRS –
\nLIP6\/UPMC, FRANCE<\/td>\nExaminateur<\/td>\n<\/tr>\n \n M. Nadjib AIT SAADI, Professeur,
\nUniversit\u00e9 de Versailles Saint-Quentin-en-Yvelines , FRANCE<\/td>\nExaminateur<\/td>\n<\/tr>\n \n M. Michel KIEFFER, Professeur,
\nCentraleSupelec, Universit\u00e9 Paris-Sud, FRANCE<\/td>\nExaminateur<\/td>\n<\/tr>\n \n M. Guillaume URVOY-KELLER, Professeur,
\nCNRS, I3S, FRANCE<\/td>\nExaminateur<\/td>\n<\/tr>\n \n M. Djamal ZEGHLACHE, Professeur,
\nT\u00e9l\u00e9com SudParis, FRANCE<\/td>\nDirecteur de th\u00e8se<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n