Placement et chaînage dynamique de fonctions réseau sur multiples centres de données

The multiplicity and diversity of applications in telecommunication networks have caused their rapid evolution, and have increased network complexity. To reduce network installation costs and complexity, operators have exploited the virtualization of network functions and their chaining. This is possible because of the portability and flexibility that virtual functions bring. However, to be able to use these chains of virtualized functions, it is necessary to host them in data centers as efficiently as possible. Although the optimization of service function chains is present in the litterature, we have made some original contributions in this work. We take into account the fact that datacenter hosting prices vary over time, that transmission delays are not the same all the time and that chain throughput demands change as well. In addition, there are relationships between chains and functions such as symmetry, incompatibility, affinity and migration that have been specifically modeled in this work. We propose an integer linear program that minimizes the cost of placing a service function chain in a data center network over a day, taking into account the quality of service, the capabilities of the datacenters and interdependencies between chains and functions. To solve big instances of the problem, we develop greedy and tabu search heuristics and we study their behavior according to the type of functions in the datacenters.

Résumé

La multiplicité et la diversité d'applications dans les réseaux de télécommunications ont causé leur évolution rapide et leur complexification. Pour pouvoir donc diminuer et leurs coûts d'installation et leur complexité, les opérateurs ont exploité la virtualisation des fonctions réseaux et leur chaînage. Ceci est possible grâce à la portabilité et à la flexibilité qu'apportent les fonctions virtuelles. Mais pour pouvoir utiliser ces chaînes de fonctions virtualisées, il faut les héberger dans des centres de données, et ce, le plus efficacement possible. Bien que l'optimisation du placement des fonctions virtuelles soit présent dans la littérature, nous avons apporté des contributions originales. Nous avons tenu compte du fait que les prix des hébergements dans les centres de données varient avec le temps, que les délais de transmission ne sont pas les mêmes tout le temps et que les demandes en chaînes changent aussi. De plus, il existe des relations entre les chaines et les fonctions telles que la symétrie, l'affinité, la migration et l'incompatibilité qui ont été spécifiquement modélisés dans notre travail. Nous avons proposé un nouveau modèle sous la forme d'un programme linéaire en nombre entiers qui minimise le coût de placement d'une chaine dans un réseau de centre de données sur une journée en tenant compte de la qualité de service, des capacités des centres de données et des interdépendances entre les chaines et les fonctions. Pour résoudre les grandes instances du problème, nous avons développé des heuristiques gloutonne et tabou et nous avons étudié leur comportement en fonction du type de fonctions dans les centres de données.