On doit explorer le champ des solutions possibles de manière intelligente : c’est l’objet de l’optimisation combinatoire.
Résumé
Web-R est un outil développé par Orange et destiné à tous les salariés et filiales du Groupe. Il apporte une aide à la décision dans les problèmes de placement. Ce type de problème est couramment rencontré dans le monde des télécoms, en particulier pour les architectes qui conçoivent les réseaux, ou les exploitants qui souhaitent faire évoluer leur infrastructure. Web-R peut par exemple être d’une aide précieuse pour concevoir les futurs réseaux 5G virtualisés, en calculant le placement optimal des contrôleurs, ou bien le déploiement des fonctions virtuelles en fonction des besoins des utilisateurs. Grâce à son interface graphique intuitive, Web-R permet à une personne non experte de mettre en œuvre simplement des techniques mathématiques pointues.
Article complet
Web-R est un outil interne, qu’Orange Labs (la division Recherche et Développement du groupe Orange) met à disposition du groupe Orange et ses filiales, pour résoudre des problèmes spécifiques aux métiers du monde des télécoms.
Cet outil est basé sur l’optimisation combinatoire, une branche des mathématiques qui est particulièrement utile pour résoudre les problèmes de placement ou de routage. L’exemple le plus connu des problèmes de cette branche est celui du voyageur de commerce, qui doit visiter tous les villages d’une région en minimisant son trajet. Ce problème est très difficile à résoudre pour un nombre de villages assez grand. Si l’on considère toutes les possibilités de parcours pour une tournée de 15 villages par exemple, on doit calculer les trajets de plus de 1 300 milliards de tournées. Pour 20 villages, cela passe à 2 400 milliards de milliards de tournées. C’est ce qu’on appelle l’explosion combinatoire. Puisqu’il est impossible de calculer tous les chemins possibles, on doit explorer le champ des solutions possibles de manière intelligente : c’est l’objet de l’optimisation combinatoire.
Problème du voyageur de commerce : la ligne noire représente le chemin le plus court possible qui relie les 36 points (gauche) ou les 1097 points (droite).
Par ailleurs, la virtualisation est un élément essentiel pour les futurs réseaux (tels que le futur réseau mobile 5G, par exemple). Cette évolution majeure du réseau amène son lot de questions, en particulier un certain nombre de défis de recherche à relever en optimisation combinatoire.
La virtualisation des réseaux
A l’heure actuelle, les équipements physiques des réseaux ont chacun une fonction bien précise : par exemple une station de base sert à gérer les canaux radio avec les téléphones mobiles, un pare-feu sert pour le contrôle d’accès, un routeur sert à faire transiter les données, etc… Dans un réseau virtualisé, les différentes fonctions du réseau sont exécutées dans un logiciel, qui fonctionne sur un serveur de calcul banalisé.
Les avantages de cette approche sont nombreux : tout d’abord, cela facilite la maintenance des équipements réseau, puisqu’il suffit d’une simple mise-à-jour logicielle pour mettre à niveau les équipements. Ensuite, le réseau peut être étendu en fonction des besoins du moment. Ainsi, si les limites de capacité d’un équipement sont proches d’être atteintes, il suffit d’augmenter les ressources de calcul pour le logiciel correspondant. C’est beaucoup plus simple, plus rapide et moins couteux que d’installer un nouvel équipement plus puissant, comme on le fait actuellement. De plus, on peut plus facilement configurer et piloter les fonctions réseau quand elles sont virtualisées.
La virtualisation apporte ainsi de nouvelles possibilités, mais aussi de nouvelles questions que nous allons détailler maintenant.
Comment effectuer le routage ?
Dans l’Internet, les données transitent sous forme de blocs de données, que l’on appelle paquets IP (Internet Protocol). Ces paquets IP transitent dans le réseau grâce aux routeurs. Ainsi, si vous naviguez sur un site américain depuis la France, votre navigateur va générer un paquet IP vers le site en question. Ce paquet va rejoindre un routeur régional français, puis passer par un routeur national, puis être envoyé vers un routeur américain, ou il va continuer son chemin jusqu’à sa destination. Ceci s’appelle le routage des paquets : en effet chaque routeur est connecté avec de nombreux autres routeurs, et chacun doit déterminer à qui il envoie les paquets qu’il reçoit, de manière à ce que chaque paquet arrive à bon port.
A l’heure actuelle, les routeurs ont des règles peu évolutives qui déterminent sur quelle route envoyer les paquets en fonction de leur adresse destination. Grâce à la virtualisation, on peut contrôler très finement les règles de routage et les changer en fonction de la charge du réseau par exemple. Ainsi, on peut recalculer toutes les routes de manière à éviter les congestions (i.e. les embouteillages, qui ralentissent le traitement des paquets). Ce calcul des routes correspond à un problème d’optimisation combinatoire qui peut être traité grâce à Web-R.
Comment déployer les contrôleurs ?
Dans un réseau virtualisé, les routeurs sont directement pilotés par un point de décision central appelé contrôleur. Le contrôleur coordonne les routeurs de manière à faire transiter les données dans le réseau de la manière la plus efficace possible. Cependant, pour être pilotés efficacement, les routeurs ne doivent pas être trop loin de leur contrôleur. En effet, en cas de problème sur le réseau, le routeur va interroger le contrôleur pour savoir ou faire transiter les données. Pour que le temps de réponse soit réduit au minimum, il faut que le contrôleur soit proche. Par ailleurs, le contrôleur peut être décomposé en plusieurs contrôleurs synchronisés entre eux.
Ainsi le problème qui se pose est de savoir où placer les contrôleurs, de manière à ce qu’ils soient à la fois proches des routeurs qu’ils pilotent, et proches entre eux. On veut s’assurer ainsi que le délai de communication contrôleur-routeur et entre contrôleurs ne dépasse pas une valeur au-delà de laquelle le système ne pourrait plus fonctionner correctement. Pour cette raison, ces contraintes sont appelées les contraintes de délai. De plus, un contrôleur est limité par le nombre de routeurs qu’il peut gérer : c’est la contrainte de charge.
Par ailleurs, un contrôleur peut tomber en panne. Dans ce cas, les contrôleurs restants doivent prendre en charge la gestion des routeurs du contrôleur défaillant, tout en respectant les contraintes de délai et de charge que l’on a fixées.
Problème du placement de contrôleurs : en vert Web-R indique le meilleur placement possible compte tenu des contraintes.
Ce problème de placement en respectant toutes les contraintes fixées peut être résolu grâce à Web-R. On peut ainsi visualiser le graphe des routeurs, l’emplacement des contrôleurs, et on peut faire tomber en panne un ou plusieurs contrôleurs pour voir comment se répartissent les routeurs sur leurs nouveaux contrôleurs.
Ou placer et comment chainer les fonctions virtuelles ?
Dans un réseau virtualisé, on peut déployer à la demande des fonctions réseau sur les routeurs. Ainsi, si on a besoin d’une fonction de pare-feu, on déploie simplement le logiciel d’un pare-feu sur le chemin pris par le flux de données concerné. La question se complique lorsque l’on considère de nombreux flux de données et de nombreuses fonctions à leur appliquer. Il faut appliquer ces fonctions dans le bon ordre, il faut minimiser à la fois l’énergie consommée et le nombre de fonctions à déployer, et il faut effectuer le routage le plus efficace pour tous les flux.
On a à nouveau affaire à un problème d’optimisation combinatoire, qui est traité par Web-R.
Comment diminuer l’empreinte carbone des data-centers ?
Un des avantages de la virtualisation est d’avoir un point central de décision. On peut en tirer parti pour réaliser du partage de charge économe en énergie. Si, par exemple, un client Orange souhaite regarder une vidéo à la demande sur la TV d’Orange, son décodeur TV émet une requête à destination du data-center le plus proche. Dans le data-center, il y a un serveur de calcul qui va traiter la requête et envoyer le flux vidéo demandé en retour. Parfois, si le data-center n’a plus de ressource disponible pour traiter la requête, il la redirige vers un autre data-center. C’est le partage de charge.
Il est possible ainsi de réaliser un partage de charge qui va diminuer l’empreinte carbone de l’ensemble des data-centers, en exploitant deux leviers principaux.
Le premier levier exploite la mise en veille des serveurs de calcul d’un data-center lorsqu’ils ne sont pas utilisés. On envoie les requêtes en priorité là où il y a des serveurs déjà utilisés. De cette manière, on regroupe les requêtes sur un nombre minimum de serveurs et les serveurs libérés sont mis en veille.
Le deuxième levier consiste à tirer parti au maximum des énergies renouvelables produites localement par chaque data-center. Ces énergies renouvelables proviennent de panneaux photovoltaïques ou d’éoliennes. De par leur nature, ces productions d’énergie varient au cours de la journée. De plus, le moment de la journée ou cette production est la plus forte (e.g. milieu de journée pour l’énergie solaire) ne correspond pas au pic de la demande (en soirée). Grâce au partage de charge, on peut exploiter au maximum cette énergie renouvelable et ainsi réduire les émissions de CO2.
La question de savoir comment répartir les requêtes entre les data-centers de manière à minimiser le nombre de serveurs de calculs et l’énergie consommée est aussi un problème d’optimisation combinatoire qui peut être résolue dans Web-R.
Web-R
Grâce à son interface graphique intuitive, Web-R permet à une personne non-experte de mettre en œuvre simplement des techniques mathématiques pointues. Cet outil permet de résoudre des problèmes métiers couramment rencontrés dans le monde des télécoms. On peut en quelques clics choisir les contraintes et les caractéristiques du problème que l’on souhaite résoudre.
Face au succès rencontré par cet outil et pour répondre à toutes les demandes, nous avons décidé de l’industrialiser pour qu’il soit utilisable par tous les collaborateurs du groupe Orange et de ses filiales.
Web-R permet de choisir les contraintes du problème (« Requirements ») parmi une bibliothèque de contraintes possibles (« Library »).
En savoir plus :
L’outil Web-R est nommé d’après Alfred Weber (1868-1958), un économiste et un sociologue qui a beaucoup étudié les problèmes de placement. En particulier, il a popularisé et généralisé le problème du triangle de Fermat. Ce dernier consiste à localiser un point D par rapport à trois points A, B et C de façon à minimiser la somme des distances entre D et chacun des trois autres points.
Qu’est-ce que l’optimisation combinatoire ?
Pour éviter d’explorer toutes les combinaisons possibles d’un problème, une technique très utilisée est la « séparation et évaluation« , qui consiste à calculer des bornes pour des branches de l’arbre des combinaisons possibles. Ainsi, on évite d’explorer les branches dont on sait qu’elles ne contiennes pas de solution optimale. On peut citer également d’autres techniques telles que « branch and price« , une heuristique ou une méta-heuristique, la décomposition de Benders, etc…
Le problème du voyageur de commerce
Qu’est-ce que la virtualisation des réseaux ?
