Brevet FR3062976A1 — publié le 20180817

PROCEDE ET DISPOSITIF DE DETERMINATION DE CHEMIN DE ROUTAGE ECONOME EN ENERGIE Domaine de l'invention L'invention se situe dans le domaine des réseaux informatiques et télécommunications et concerne l'optimisation du routage des flux de données dans un réseau IP. Etat de la Technique Récemment, l'efficacité énergétique est devenue un facteur clé dans la conception des réseaux cellulaires, en particulier les réseaux cellulaires de 5e génération (5G). Ce besoin est animé par une volonté de réduire l'empreinte carbone des communications, minimiser les factures de l'électricité de l'opérateur de réseau ainsi que de prolonger la durée de vie des équipements fonctionnant avec des batteries. En particulier, cette exigence est d'une importance primordiale pour les opérateurs de réseaux dont l'infrastructure réseau est en constante expansion en intégrant de nouvelles technologies d'accès et en augmentant le nombre de points d'accès pour satisfaire le nombre croissant de clients. Plusieurs études prévoient une croissance spectaculaire du trafic Internet en raison de services de médias en streaming tels que l'IPTV, la vidéo à la demande (VoD) et la vidéoconférence. En effet, ces services nécessitent des chemins de routage avec une bande passante suffisante qui permet d'assurer une faible gigue et peu de perte de paquets. Par conséquent, l'un des principaux défis dans les réseaux 5G est de trouver des chemins qui permettent de réduire la consommation d'énergie sans compromettre les autres indicateurs de performance tels que le débit de l'utilisateur, la gigue ou le pourcentage des paquets perdus. Considérant tous ces paramètres et ces contraintes, les algorithmes de routage deviennent complexes avec de multiples objectifs et contraintes. 2 3062976 L'efficacité énergétique dans les réseaux d'accès et d'agrégation 5G constitue ainsi un problème d'optimisation bi-objectif qui doit tenir compte à la fois de la bande passante disponible et de la consommation énergétique des liens, au lieu de ne seulement considérer la bande 5 passante. Par ailleurs, la Commission européenne a émis un code de conduite (CoC) sur la consommation d'énergie des équipements haut débit qui indique la consommation électrique maximale autorisée pour chaque technologie de liens. Selon ce rapport, chacune des technologies 10 a sa propre consommation énergétique indépendamment de la bande passante associée. Par exemple, une fibre point-à-point avec une bande passante de 10 Gbps consomme environ 8 Watts, alors qu'une fibre EPON avec la même bande passante consomme environ 13,4 Watts. Les figures 1 a et 1 b illustrent pour une même configuration de 15 réseau (100), la puissance qui est consommée sur un chemin de routage selon quels critères sont pris en compte pour déterminer le chemin de routage. Dans cet exemple simplifié, le réseau (100) de type 5G, est composé de deux parties : une partie dite réseau d'accès et d'agrégation (102), et une partie dite réseau coeur (104). Les deux parties du réseau 20 sont couplées via un routeur (103) aussi appelé noeud de bord. Le réseau comprend dans chaque partie, des noeuds ou routeurs (106-1, ..., 106-i, .... 106-n) qui sont connectés entre eux via des liens (108-1, ..., 108-j, ... 108-m) pouvant être de différentes technologies. Lors de la transmission ou la réception de paquets, chaque routeur 25 impliqué dans un chemin de routage développe une consommation d'énergie sur son interface réseau qui est fonction de la technologie du lien. Les valeurs indiquées sur les figures 1 a et 1 b sont données à titre d'exemple, et correspondant à des valeurs réelles données dans le code de conduite précité, pour des types de fibres de 1 Gbits/s et 10 Gbits/s, selon le nombre de ports. 3 3062976 Un terminal client (110) est connecté à une borne WiFi (112). Un utilisateur fait une requête pour une vidéo en streaming à partir d'un serveur (114) du fournisseur des contenus. Dans le cas de la figure 1 a, le routage des paquets (chemin 116) est fait en se basant sur la métrique de 5 la bande passante. Ainsi, les liens avec la plus grande passante sont favorisés. Cette politique de routage entraine une consommation énergétique totale du chemin de 132W, correspondant à la somme des consommations énergétiques de chaque lien impliqué dans le chemin entre la source et la destination. Dans le cas de la figure 1 b, le routage 10 des paquets (chemin 118) est fait en fonction de la bande passante et de la consommation énergétique des liens. Ainsi, les liens qui assurent une bande passante adéquate et qui consomment moins en termes d'énergie sont favorisés. Cette politique de routage entraine une consommation énergétique totale du chemin de 74W. 15 Cet exemple illustre la problématique liée au besoin d'avoir un protocole de routage qui permette de réduire la consommation énergétique. Il existe deux approches principales pour relever le défi d'avoir un protocole de routage qui permet de réduire la consommation énergétique. 20 La première approche consiste à proposer une nouvelle métrique de routage qui prend en considération les paramètres liés à l'énergie, comme le niveau restant de la batterie d'un équipement. Un algorithme de routage calcule les chemins en utilisant cette métrique. La deuxième approche consiste à introduire des modifications dans le protocole de 25 routage lui-même afin de réaliser des économies en termes d'énergie. Dans cette seconde approche, la métrique de routage ne subit aucune modification. En ce qui concerne la première approche, les solutions existantes ciblent les réseaux des noeuds ayant une puissance énergétique limitée 30 comme les réseaux ad-hoc ou capteurs. En effet, dans un tel contexte, l'énergie du noeud est une ressource critique qui doit être utilisée 4 3062 976 efficacement afin d'augmenter la durée de vie du réseau. Par conséquent, une métrique de routage basé sur le niveau de batterie des noeuds ou de la qualité de la liaison est la plus appropriée pour préserver l'énergie de noeuds. 5 La demande de brevet U.S. 2013/0315257 Al de Welin et al. présente une méthode qui utilise la métrique de consommation d'énergie lors de la commutation du trafic dans les routeurs ou les commutateurs. Cette métrique peut se fonder sur la consommation d'énergie dans les interfaces de liaison, dans les liaisons et dans le noeud. Chaque noeud 10 reçoit la consommation énergétique du reste des noeuds qui se trouvent dans le même domaine de routage. Il envoie également sa consommation énergétique vers les autres noeuds. Ce type de solution ne permet pas d'assurer une Qualité de Service (QoS) requise par les applications. En ne considérant que l'énergie comme unique critère de sélection de la 15 route de bout en bout, cette solution peut opter de router un trafic sensible aux latences (par exemple, appel d'urgence, télévision IP, etc.) par un chemin ne respectant pas leur besoin (par exemple, chemin long causant une grande latence). Bien que cette approche permette de réduire la consommation énergétique du réseau, en ayant considéré la 20 consommation énergétique des interfaces comme métriques, elle ne permet pas d'assurer la qualité de service demandée par les applications, en particulier les applications multimédia qui ont un besoin très spécifique en termes de débit, délais et pourcentages des paquets perdus. En ce qui concerne la seconde approche, l'idée de base consiste à 25 acheminer les paquets de données sur un sous-ensemble donné de liaisons réseau pendant les périodes de faible trafic, au moyen d'une stratégie de coordination entre les routeurs. De cette façon, les interfaces qui ne participent pas dans la commutation du trafic peuvent être mises hors tension, en mode veille, sans provoquer des problèmes de la 30 disponibilité du réseau. 5 3062 9 76 La demande de brevet U.S. 2015/0222537 Al de Zhang propose une méthode qui permet d'agréger le trafic pour désactiver des interfaces de réseaux ou les mettre en veille et utiliser ainsi le minimum possible des liens dans le réseau, réduisant ainsi la consommation globale du réseau. 5 Cette méthode utilise un algorithme de programmation linéaire dont l'objectif est de maximiser le nombre de liens à mettre en veille et prenant comme contrainte l'état du trafic dans les noeuds du réseau. Ainsi, pour le bon déroulement de l'algorithme, la méthode a besoin des paramètres suivants : le noeud source, le noeud destination, des données sur la 10 topologie du réseau ainsi que des données sur l'état du trafic dans chaque noeud. La méthode considère que la consommation d'énergie des interfaces est la même quelle que soit la technologie utilisée. De plus, la méthode n'est pas compatible avec les protocoles de routages distribués de type « Open Shortest Path First » (OSPF). En effet, une fois que 15 l'interface est désactivée, le protocole OSPF considère que le lien est en panne et va inonder le réseau avec des messages « Link-state advertisements » (LSA) pour informer les autres routeurs. Il existe alors le besoin d'une solution appropriée pour déterminer pour chaque flux à router, un chemin de routage permettant à la fois de 20 satisfaire les besoins en termes de qualité de service du flux tout en minimisant la consommation énergétique globale du réseau. La présente invention répond à ce besoin. Résumé de l'invention 25 Un objet de la présente invention est de proposer un procédé de détermination de chemin de routage qui permet de réduire la consommation d'énergie totale dans les réseaux, qui tienne compte à la fois de la bande passante disponible du chemin et de la consommation énergétique des interfaces des noeuds, et sans dégrader la qualité de 30 service offerte aux utilisateurs. 6 3062976 Un autre objet de la présente invention est de proposer un procédé de détermination de chemin de routage économe en énergie tout en préservant les contraintes de qualité de service requises par les flux de données, quelle que soit l'hétérogénéité des technologies des réseaux 5 utilisées. D'une manière générale, le procédé de l'invention s'appuie sur la mise en oeuvre d'un algorithme qui comporte deux niveaux de filtrage : un premier filtrage pour cibler l'ensemble des meilleurs chemins possibles selon une première métrique prioritaire suivi d'un second filtrage pour y 10 sélectionner le meilleur chemin selon une seconde métrique. L'invention trouvera des applications avantageuses dans tous les domaines où fournisseurs et opérateurs de réseaux de télécommunication sont désireux de réduire la consommation énergétique des réseaux tout en assurant la qualité de service requise par les flux de 15 données devant y transiter. Ainsi sans limitation, l'invention peut être implémentée: - dans le domaine des réseaux cellulaires 5G pour tout opérateur ou équipementier ; - dans le domaine des réseaux de distribution vidéo ; 20 - dans le domaine des réseaux temps-réel évènementiels (spectacles) ; - dans le domaine des réseaux domestiques ; - dans le domaine des réseaux sans-fil pour applications industrielles, dont en particulier les réseaux avec équipements alimentés par batteries ; 25 - potentiellement pour les industriels fournisseurs de solutions de communication sans-fil sans infrastructure pour la sécurité publique ou la logistique. Avantageusement, le procédé de l'invention est facile à implémenter, et adaptable suivant le besoin de l'opérateur, selon la 30 performance prioritaire recherchée, qu'elle soit d'assurer la qualité de service pour les flux, ou de réduire la consommation énergétique. 7 3062976 Si la priorité est d'assurer la qualité de service pour les flux, par exemple pour un flux vidéo, le procédé permet de déterminer les chemins ayant la meilleure bande passante disponible, puis ensuite de sélectionner parmi ceux-ci, celui qui présente la consommation 5 énergétique la plus basse. Si la priorité est de réduire la consommation énergétique, dans le cas par exemple de flux qui n'ont pas un besoin spécifique en termes de qualité de services comme certains types de communications liés à des objets connectés, le procédé permet de déterminer les chemins qui 10 présentent la plus petite consommation énergétique, puis de sélectionner parmi ceux-ci, celui qui a la meilleure bande passante disponible. Dans une implémentation préférentielle, pour calculer les meilleurs chemins suivant une métrique de performance donnée, le procédé met en oeuvre un algorithme de Yen, qui permet de trouver les k meilleurs 15 chemins sans boucle. Pour obtenir les résultats recherchés, il est proposé un procédé de détermination de chemin de routage de paquets de données entre un noeud source et un noeud destinataire d'un réseau comprenant une pluralité de noeuds et de liens entre les noeuds, les liens présentant au 20 moins des premières et seconde métriques de performance, le procédé comprenant les étapes de : - déterminer selon la première métrique de performance, un ensemble de candidats représentant des chemins ayant la meilleure valeur de la première métrique de performance entre le noeud source et le noeud 25 destinataire, un chemin incluant au moins un lien; - classer les candidats selon la seconde métrique de performance ; et - sélectionner un candidat selon le résultat de l'étape de classement. Selon des modes de réalisation : - l'étape de classement consiste à ordonner les candidats selon une 30 valeur croissante ou décroissante de la second métrique de 8 3062976 performance, et l'étape de sélection consiste à sélectionner le candidat présentant la valeur la plus haute ou la plus basse ; - le procédé comprend après l'étape de détermination, une étape pour filtrer parmi les candidats, un sous-ensemble de candidats 5 représentant les meilleurs chemins sans boucle selon une métrique de performance donnée, et où l'étape de classement consiste à classer le sous-ensemble de candidats ; - l'étape de détermination consiste à opérer un algorithme de calcul de `k' meilleurs chemins sur un graphe représentatif des noeuds du 10 réseau, 'k' étant un nombre entier prédéfini ; - l'algorithme est l'algorithme de Yen ; - les métriques de performance sont la bande passante disponible et la consommation énergétique de chaque lien ; - la première métrique est la bande passante disponible et la deuxième 15 métrique est la consommation énergétique ; - l'étape de détermination consiste à déterminer un ensemble de chemins possédant une bande passante disponible la plus élevée et l'étape de sélection consiste à sélectionner le chemin présentant la plus petite consommation énergétique entre le noeud source et le 20 noeud destinataire ; - la première métrique est la consommation énergétique et la deuxième métrique est la bande passante disponible ; - l'étape de détermination consiste à déterminer un ensemble de chemins présentant une consommation énergétique la plus petite et 25 l'étape de sélection consiste à sélectionner le chemin présentant la bande passante disponible la plus élevée entre le noeud source et le noeud destinataire ; - le procédé comprend de plus après l'étape de détermination, une étape pour filtrer parmi les candidats, un sous-ensemble de candidats 30 selon des paramètres de qualité de service pour le flux de données ; 9 3062976 - les paramètres de qualité de service sont choisis parmi le débit, la latence, le taux de perte maximal de paquets de données, la gigue. L'invention couvre un dispositif de détermination de chemin de 5 routage de paquets de données entre un noeud source et un noeud destinataire d'un réseau comprenant une pluralité de noeuds et de liens entre les noeuds, les liens présentant au moins des premières et seconde métriques de performance, le dispositif comprenant des moyens pour mettre en oeuvre les étapes du procédé revendiqué. 10 Selon les modes de réalisation : - les liens entre les noeuds du réseau sont filaires et/ou non filaires ; - les paquets de données sont des paquets d'un flux de données multimedia. L'invention couvre aussi un système de communication apte à 15 router dans un réseau des paquets de données entre un noeud source et un noeud destinataire parmi une pluralité de noeuds reliés par des liens, les liens présentant au moins des premières et seconde métriques de performance, le système comprenant au moins un dispositif tel que revendiqué. 20 Dans une réalisation, le dispositif revendiqué est implémenté dans au moins un noeud du réseau. Dans une autre réalisation, le réseau est de type « SoftwareDefined Networking » (SDN) comprenant un contrôleur SDN, et le dispositif revendiqué est implémenté dans le contrôleur SDN de ce 25 réseau. L'invention couvre aussi un procédé opéré par un contrôleur SDN dans un réseau de type « Software-Defined Networking » (SDN), pour construire une route par flux de données, le réseau comprenant une pluralité de noeuds et de liens entre les noeuds, les liens présentant au 30 moins des premières et seconde métriques de performance, le contrôleur SDN étant apte à détecter une requête de routage de flux et identifier 10 3062976 l'adresse d'un noeud source et l'adresse d'un noeud destinataire pour le flux, le procédé comprenant les étapes du procédé de détermination de chemin de routage tel que revendiqué. Selon des modes de réalisation, l'exécution des étapes du procédé 5 de détermination de chemin de routage de paquets de données est faite selon que la qualité de service pour un flux de données est prioritaire ou non L'invention peut opérer sous la forme d'un produit programme d'ordinateur qui comprend des instructions de code permettant d'effectuer 10 les étapes du procédé revendiqué lorsque le programme est exécuté sur un ordinateur. Description des figures Différents aspects et avantages de l'invention vont apparaitre en appui de la description d'un mode préféré d'implémentation de l'invention 15 mais non limitatif, avec référence aux figures ci-dessous : Les figures 1 a et 1 b illustrent la puissance qui est consommée sur un chemin de routage selon quels critères sont pris en compte pour déterminer le chemin de routage; La figure 2 illustre un enchainement d'étapes selon le procédé de 20 l'invention, pour déterminer un chemin de routage; La figure 3 détaille les étapes du procédé de l'invention dans un mode de réalisation; La figure 4 détaille les étapes du procédé de l'invention dans un autre mode de réalisation; 25 La figure 5 illustre un enchainement d'étapes selon une variante du procédé de l'invention dans un autre mode de réalisation ; La figure 6 illustre un enchainement d'étapes du procédé de l'invention dans un mode de réalisation pour un réseau SDN ; 11 3062976 La figure 7 montre schématiquement un environnement de réseau SDN dans lequel l'invention peut être implémentée. Description détaillée de l'invention Un avantage majeur du procédé de l'invention, aussi désigné 5 procédé « GoGreen », est de réduire la consommation d'énergie dans les réseaux lors du calcul d'un chemin de routage, en tenant compte à la fois de la bande passante disponible des liens entre les noeuds et de leur consommation énergétique. La figure 2 illustre un enchainement d'étapes (200) du procédé 10 GoGreen de l'invention. Le procédé permet de déterminer un chemin de routage dans des réseaux de communication, tels que par exemple, le réseau cellulaire 5G comme illustré sur les figures 1 a et I b. Le procédé Gogreen peut aussi être opéré dans des réseaux mettant en oeuvre un protocole de routage distribué, comme par exemple le protocole OSPF. 15 Dans ce dernier cas, le procédé est exécuté dans chaque routeur du réseau, et le bloc routeur « Router Link State Advertisment » (Router LSA) dans le message « Link State Update » (LSU) qui est utilisé pour que chaque routeur annonce ses interfaces, ses voisins et les valeurs des métriques pour atteindre ces voisins, est modifié pour inclure un champ 20 annonçant les deux métriques de bande passante et de consommation énergétique. Pour initier le procédé, plusieurs paramètres sont requis, à savoir : - une représentation sous forme de graphe des noeuds du réseau où 25 chaque lien entre les noeuds est caractérisé par deux métriques de performance (w1, w2) ; - une paire source-destination (src,dst) correspondant à un émetteur d'un flux de données et un récepteur du flux ; et - un nombre maximal 'k' des meilleurs chemins à calculer, le paramètre 30 'k' étant un nombre entier prédéfini. 12 3062976 Typiquement, 'k' varie entre 1 et 5 pour un graphe ayant des noeuds qui varient entre 10 et 100. Dans une première étape (202), le procédé permet de déterminer un ensemble de candidats de 'k' chemins entre la source et la destination 5 présentant la première métrique de performance 'w1'. Dans le cas où un seul candidat est proposé, le procédé sélectionne (206) directement le chemin correspondant. Dans le cas où plusieurs candidats sont obtenus du calcul précédent, le procédé permet de classer (204) les candidats selon la 10 deuxième métrique de performance 'w2'. L'étape de classement consiste à ordonner les 'k' candidats selon une valeur croissante ou décroissante de la seconde métrique de performance. Après l'étape de classement, le procédé permet de sélectionner (206) un candidat présentant la meilleure valeur pour la deuxième 15 métrique w2. L'étape de sélection consiste à sélectionner le candidat présentant la valeur la plus haute ou la plus basse dans le classement pour permettre d'activer l'émission du flux de données entre la source et la destination via ce chemin. Le candidat sélectionné correspond alors au chemin offrant des performances optimisées relativement au deux 20 métriques. Dans une implémentation, l'étape de détermination de chemins I présentant les meilleurs valeurs de la métrique de performance considérée comprend de plus avant l'étape de classement, une étape de tri des candidats pour ne conserver comme candidats que les chemins 25 sans boucle. Dans une implémentation préférentielle, l'étape de détermination des meilleurs chemins selon une métrique de performance est basée sur l'algorithme bien connu de Yen (J. K. Yen, « Finding the k shortest loopless paths in a network », Management science (vol. 17, no. 11, pp. 30 712-716), 1971) qui permet de générer les 'k' plus courts chemins sans 13 3062 9 76 boucles dans un graphe, et l'étape de classement est faite directement sur les candidats sans boucle. La figure 3 détaille les étapes (300) du procédé de l'invention, dans 5 un mode de réalisation (302) où la première métrique `w1=BP' est la bande passante disponible, et la deuxième métrique `w2=PW' est la consommation énergétique. Une telle implémentation correspond aux scénarios où la priorité de performance est donnée à la bande passante. 10 Le procédé GoGreen calcule (étape 304) les k meilleurs chemins en considérant comme première métrique la bande passante disponible (w1) des liens. Il détermine les k chemins qui possèdent la bande passante disponible la plus élevée, la bande passante d'un chemin étant considérée comme étant égale au minimum des bandes passantes des 15 liens qui constituent ce chemin. Si un seul chemin est candidat (branche OUI de 306), le procédé permet de le sélectionner (310) pour permettre d'activer l'émission du flux de données entre la source et la destination via ce chemin. Si plusieurs chemins sont candidats (branche NON de 306), le procédé permet de classer (308) les candidats selon la valeur de 20 la consommation énergétique de bout-en-bout, la consommation énergétique d'un chemin étant calculée en faisant la somme des consommations énergétiques des liens composant le chemin. A l'étape suivante (310), le procédé permet de sélectionner le chemin qui présente la plus petite consommation énergétique de bout-en-bout pour permettre 25 d'activer l'émission du flux de données entre la source et la destination via ce chemin. La figure 4 détaille les étapes (400) du procédé de l'invention, dans un mode de réalisation (402) où la première métrique `w1=PW' est la 30 consommation énergétique, et la deuxième métrique `w2=BP' est bande 14 3062976 passante disponible. Une telle implémentation correspond aux scénarios où la priorité de performance est donnée à la consommation énergétique. Le procédé GoGreen calcule (étape 404) les k meilleurs chemins en considérant comme première métrique la consommation énergétique 5 (w1) des liens. Il détermine les k chemins qui possèdent la consommation énergétique de bout-en-bout la plus basse, la consommation énergétique d'un chemin étant calculée en faisant la somme des consommations énergétiques des liens composant le chemin. Si un seul chemin est candidat (branche OUI de 406), le procédé permet de le sélectionner 10 (410) pour permettre d'activer l'émission du flux de données entre la source et la destination via ce chemin. Si plusieurs chemins sont candidats (branche NON de 406), le procédé permet de classer (408) les candidats selon la valeur de la bande passante disponible de chaque candidat, la bande passante d'un chemin étant considérée comme étant 15 égale au minimum des bandes passantes des liens qui constituent ce chemin. A l'étape suivante (410), le procédé permet de sélectionner le chemin qui présente la plus grande bande passante disponible pour permettre d'activer l'émission du flux de données entre la source et la destination via ce chemin. 20 Dans une implémentation préférentielle, l'étape de détermination (304, 404) applique un algorithme de type Yen qui permet de déterminer les k chemins les plus courts sans boucle. La figure 5 illustre un enchainement d'étapes (500) d'une variante 25 du procédé de l'invention dans un mode de réalisation où les exigences du trafic à router en termes de qualité de service (QoS) sont considérées. Cette variante s'applique particulièrement pour le cas où la consommation énergétique est la performance prioritaire. En effet, le procédé GoGreen décrit précédemment opère sans avoir besoin de 30 connaitre au préalable les exigences spécifiques du trafic à router en 15 3062976 termes de QoS (par exemple, le débit seuil requis par le trafic des données). Dans l'implémentation selon la figure 3, le procédé permet de générer les k chemins ayant la meilleure bande passante disponible. Ensuite, il sélectionne, parmi ces k chemins, celui qui a la meilleure valeur 5 de consommation énergétique. Cependant, dans ce mode, il peut arriver que le chemin sélectionné au final soit un chemin qui permet de réduire la consommation énergétique mais qui cependant ne permet pas d'assurer la qualité de service requise par le trafic à router. En effet, quand le procédé considère les exigences spécifiques de chaque flux de données 10 lors de la détermination des candidats, il peut satisfaire au mieux les différentes exigences du trafic. Par exemple, le procédé doit déterminer un chemin de routage pour un flux vidéo qui requiert un débit de 0.5 Mbits/s. Si on suppose `k=4', le procédé génère 4 chemins (ch) qui présentent les meilleurs débits : ch1 = (5Mbits/s, 10Watts), ch2 = 15 (2Mbits/s, 6Watts), ch3 = (1 Mbits/s, 4Watts) et ch4 = (0.2Mbits/s, 2Watts). Dans l'étape de sélection, le procédé va sélectionner le quatrième chemin ch4 pour router le trafic puisqu'il possède la consommation énergétique la plus petite. Cependant, le débit que le chemin ch4 peut assurer ne permet pas de satisfaire les exigences du trafic spécifique en termes de débit qui 20 est de (0.5Mbits/s). Une variante avantageuse du procédé de l'invention dans le mode de réalisation selon la figure 3, consiste à prendre en compte les exigences du trafic dans la sélection du chemin de routage. Dans cette version qui considère comme première métrique la bande passante des 25 liens (w1) et comme deuxième métrique la consommation énergétique (w2), le procédé a une connaissance préalable du débit requis par le trafic des données à router (502). Le procédé détermine un groupe 'R' des k chemins qui offrent la meilleure bande passante (504). Si le groupe R ne contient qu'un seul chemin (branche OUI de 506), le procédé sélectionne 30 (516) ce chemin pour initier la transmission des données entre la source et la destination. Si plusieurs chemins sont candidats (branche NON de 16 3062 9 76 506), le procédé permet de sélectionner (508) parmi les candidats, un sous-groupe `R_QoS' de candidats qui permettent d'assurer les exigences du trafic. Les exigences du trafic peuvent englober des paramètres de qualité de service choisis parmi le débit, la latence, le taux 5 de perte maximal de paquets de données, la gigue. Si la liste de candidats du sous-groupe R_QoS est vide (branche OUI de 510), le procédé permet de classer (512) les candidats du groupe initial R selon la seconde métrique de consommation énergétique, et sélectionner (516) parmi le groupe R le chemin présentant la meilleure 10 valeur selon la seconde métrique de consommation énergétique. Si la liste de candidats du sous-groupe R_QoS n'est pas vide (branche NON de 510), le procédé permet de classer (514) les candidats du sous-groupe R_QoS selon la seconde métrique de consommation énergétique, et sélectionner (516) parmi le groupe R_QoS le chemin 15 présentant la meilleure valeur selon la seconde métrique de consommation énergétique. Dans une réalisation particulière de l'invention, les exigences de QoS d'un flux de données peuvent être indiquées dans les entêtes des paquets du flux. 20 La figure 6 illustre un enchainement d'étapes (600) de construction de route par flux intégrant le procédé de détermination de chemin de routage de l'invention, dans un mode de réalisation où le réseau est un réseau SDN, contrôlé par un contrôleur SDN. La figure 7 montre schématiquement un environnement de réseau SDN dans lequel le 25 procédé de la figure 6 peut être implémenté au niveau du contrôleur SDN (702). Une des caractéristiques du contrôleur SDN est sa capacité à avoir une vision globale de la topologie du réseau. Ceci lui permet d'exécuter le procédé de l'invention pour calculer le chemin de routage optimal tout en tenant en compte des différents objectifs et contraintes. Le réseau (SDN) 30 comprend des commutateurs SDN pour le transfert du trafic de 17 3062976 l'utilisateur dans le plan des données. Ces équipements sont contrôlés par le contrôleur SDN. Avantageusement, l'implémentation du procédé de l'invention au niveau du contrôleur SDN n'implique aucune modification ou adaptation dans les commutateurs SDN, ni dans le protocole 5 d'échange (i.e. Openflow) entre contrôleur et commutateur. Les dispositifs du réseau dans le plan de données (par exemple, des routeurs, des commutateurs, des cellules de radio, etc.) ont juste besoin d'être équipés d'un protocole permettant la configuration de leur table de routage par le contrôleur SDN, comme par exemple le protocole OpenFlow, alors que le 10 calcul du chemin de routage est effectué dans le contrôleur SDN, par exemple dans un « data center » ou un serveur ayant de hautes performances. Le procédé (600) est déclenché par l'arrivée d'un nouveau message OpenFlow « OF PACKET_IN » venant d'un commutateur ou 15 routeur donné. Ce message permet au contrôleur SDN de détecter (602) le besoin de router un nouveau flux au sein du réseau. A partir de ce message, le contrôleur SDN identifie l'adresse source, l'adresse destination, le protocole de transport utilisé, le numéro de port source et destination. Dans une étape suivante, le procédé permet au contrôleur 20 SDN de déterminer (604) si la qualité de service QoS est prioritaire en fonction de différents paramètres tels que le protocole de transport utilisé, le numéro de port qui permet d'identifier l'application et l'adresse de destination. Si la QoS est prioritaire (branche OUI de 604), le procédé exécute les étapes de sélection du chemin de routage suivant le mode 25 opératoire décrit quand la priorité est la bande passante (selon la figure 3 ou sa variante selon la figure 5). Dans le cas contraire où la QoS n'est pas prioritaire (branche NON de 604), le procédé exécute les étapes de sélection du chemin de routage suivant le mode opératoire décrit quand la priorité est la consommation énergétique (selon la figure 4). 18 3062 9 76 Dans chaque mode opératoire, le contrôleur SDN peut décider d'utiliser des valeurs du paramètre k différentes pour différents sous-groupes de flux. Ainsi, l'exécution du procédé GoGreen fournit le chemin de routage 5 qui permet de satisfaire les besoins du flux. Le contrôleur SDN détermine (610) les commutateurs/routeurs qui font partie de ce chemin de routage. Puis, il prépare (612) les messages « OF PACKET_OUT » qui permettent de configurer (614) ces commutateurs/routeurs. Une fois le chemin établi dans le plan des donnés, le contrôleur 10 SDN met à jour (616) la valeur de la bande passante disponible des liens sur lesquels le flux a été routé. Quand la transmission du flux de données est terminée, le commutateur/routeur envoie un message vers le contrôleur SDN pour lui indiquer la fin de la transmission du flux à son niveau. Ceci permet au contrôleur de mettre à jour la valeur de bande 15 passante disponible des liens. En effet, dans le protocole OpenFlow, chaque règle de commutation dans un commutateur/routeur est associée à une minuterie qui expire lorsque le commutateur/routeur ne reçoit plus de paquet lié au flux. Dans ce cas, la règle de commutation est supprimée et un message de notification est envoyé vers le contrôleur SDN. 20 Avantageusement, le procédé de construction de route par flux décrit permet de faire coexister dans un même réseau des flux ayant des besoins différents, par l'exécution du procédé de l'invention : - en mode où la priorité est d'assurer la QoS, tout en cherchant à réduire la consommation énergétique ; et 25 - en mode où il n'y a pas de contraintes de QoS imposées mais où il est important de minimiser la consommation énergétique. Il est à noter que la bande passante disponible, à l'initialisation correspond à la bande passante nominale. Après l'installation d'un nouveau chemin pour un flux donné, la bande passante disponible 30 correspond alors à la bande passante nominale moins la charge estimée pour ce flux. Dans le cas du réseau SDN, le contrôleur SDN initialise la 19 3062976 bande passante disponible à la valeur de bande passante nominale. Après installation d'un chemin dans le plan de transfert des données pour un flux donné, le contrôleur met à jour cette métrique en soustrayant la charge estimée pour ce flux, et ceci pour chaque lien participant dans le 5 routage de ce flux. Ainsi, dans l'exemple d'une bande passante disponible de 10Mbps et d'un chemin X composé de trois liens (11, 12, 13) ayant respectivement des bandes passantes de (11 Mbps, 10Mbps, 11 Mbps), après l'installation de ce chemin pour un flux de vidéo qui a besoin de 2Mbps, le contrôleur met à jour la métrique de la bande passante de 10 chaque lien de ce chemin. Ainsi la bande passante du premier lien 11 devient 9Mbps, celle du deuxième lien 12 devient 8Mbps et celle du troisième lien 13 devient 9Mbps. Le chemin X a alors une bande passante disponible de 9Mbps. Pour déterminer la bande passante disponible d'un chemin, il suffit de déterminer le minimum parmi les valeurs de la bande 15 passante disponible des liens qui constituent ce chemin. L'homme du métier considèrera que la présente invention peut s'implémenter à partir d'éléments matériel et/ou logiciel et opérer sur un ordinateur. Elle peut être disponible en tant que produit programme 20 d'ordinateur sur un support lisible par ordinateur. Le support peut être électronique, magnétique, optique, électromagnétique ou être un support de diffusion de type infrarouge. De tels supports sont par exemple, des mémoires à semi-conducteur (Random Access Memory RAM, Read-Only Memory ROM), des bandes, des disquettes ou disques magnétiques ou 25 optiques (Compact Disk - Read Only Memory (CD-ROM), Compact Disk - Read/Write (CD-R/W) et DVD). Ainsi la présente description illustre une implémentation préférentielle de l'invention, mais n'est pas limitative. Un exemple a été choisi pour permettre une bonne compréhension des principes de l'invention, et une application concrète, mais il n'est en rien 30 exhaustif et doit permettre à l'homme du métier d'apporter des 20 3062976 modifications et variantes d'implémentation en conservant les mêmes principes. 21 REVENDICATIONS1. Procédé de détermination de chemin de routage de paquets de données entre un noeud source et un noeud destinataire d'un réseau comprenant une pluralité de noeuds et de liens entre les noeuds, les liens présentant au moins des première et seconde métriques de performance, le procédé comprenant les étapes de : - déterminer un ensemble de candidats représentant les meilleurs chemins selon la première métrique de performance, entre le noeud source et le noeud destinataire, un chemin incluant au moins un lien; - classer les candidats selon la seconde métrique de performance ; et - sélectionner un candidat selon le résultat de l'étape de classement. 2. Procédé selon la revendication 1 dans lequel l'étape de classement consiste à ordonner les candidats selon une valeur croissante ou décroissante de la seconde métrique de performance, et l'étape de sélection consiste à sélectionner le candidat présentant la valeur la plus haute ou la plus basse. 3. Procédé selon la revendication 1 ou 2 comprenant après l'étape de détermination, une étape pour filtrer parmi les candidats, un sous-ensemble de candidats représentant les meilleurs chemins sans boucle, et où l'étape de classement consiste à classer le sous- ensemble de candidats. 22 3062976 4. Procédé selon l'une quelconque des revendications 1 à 3 dans lequel l'étape de détermination consiste à opérer un algorithme de calcul de 'k' chemins les plus courts sur un graphe représentatif des noeuds du réseau, 'k' étant un nombre entier prédéfini. 5 5. Procédé selon la revendication 4 dans lequel l'algorithme est l'algorithme de Yen. 6. Procédé selon l'une quelconque des revendications 1 à 5 dans 10 lequel les métriques de performance sont la bande passante disponible et la consommation énergétique de chaque lien. 7. Procédé selon l'une quelconque des revendications 1 à 6 dans lequel la première métrique est la bande passante disponible et la 15 deuxième métrique est la consommation énergétique. 8. Procédé selon la revendication 7 dans lequel l'étape de détermination consiste à déterminer un ensemble de chemins possédant une bande passante disponible la plus élevée et l'étape 20 de sélection consiste à sélectionner le chemin présentant la plus petite consommation énergétique entre le noeud source et le noeud destinataire. 9. Procédé selon l'une quelconque des revendications 1 à 6 dans 25 lequel la première métrique est la consommation énergétique et la deuxième métrique est la bande passante disponible. 23 3062976 10. Procédé selon la revendication 9 dans lequel l'étape de détermination consiste à déterminer un ensemble de chemins présentant une consommation énergétique la plus petite et l'étape de sélection consiste à sélectionner le chemin présentant la bande 5 passante disponible la plus élevée entre le noeud source et le noeud destinataire. 11. Procédé selon la revendication 7 comprenant de plus après l'étape de détermination, une étape pour filtrer parmi les candidats, un 10 sous-ensemble de candidats selon des paramètres de qualité de service pour le flux de données. 12. Procédé selon la revendication 11 dans lequel les paramètres de qualité de service sont choisis parmi le débit, la latence, le taux de 15 perte maximal de paquets de données, la gigue. 13. Un produit programme d'ordinateur, ledit programme d'ordinateur comprenant des instructions de code permettant d'effectuer les étapes du procédé selon l'une quelconque des revendications 1 à 20 12, lorsque ledit programme est exécuté sur un ordinateur. 14. Dispositif de détermination de chemin de routage de paquets de données entre un noeud source et un noeud destinataire d'un réseau comprenant une pluralité de noeuds et de liens entre les 25 noeuds, les liens présentant au moins des premières et seconde métriques de performance, le dispositif comprenant des moyens pour mettre en oeuvre les étapes du procédé selon l'une quelconque des revendications 1 à 12. 24 3062 9 76 15. Le dispositif selon la revendication 14 dans lequel les liens entre les noeuds du réseau sont filaires et/ou non filaires. 16. Le dispositif selon la revendication 14 ou 15 dans lequel les 5 paquets de données sont des paquets d'un flux de données multimedia. 17. Un système de communication apte à router dans un réseau des paquets de données entre un noeud source et un noeud 10 destinataire parmi une pluralité de noeuds reliés par des liens, les liens présentant au moins des premières et seconde métriques de performance, le système comprenant au moins un dispositif selon l'une quelconque des revendications 14 à 16. 15 18. Le système selon la revendication 17 dans lequel ledit au moins un dispositif est implémenté dans au moins un noeud du réseau. 19. Le système selon la revendication 17 ou 18 dans lequel le réseau est de type « Software-Defined Networking » (SDN) et ledit au 20 moins un dispositif est implémenté dans le contrôleur SDN dudit réseau. 20. Procédé de construction de route par flux de données dans un réseau de type « Software-Defined Networking » (SDN), le réseau 25 comprenant une pluralité de noeuds et de liens entre les noeuds, les liens présentant au moins des premières et seconde métriques de performance, le réseau comprenant un contrôleur SDN apte à détecter une requête de routage de flux et identifier l'adresse d'un noeud source et l'adresse d'un noeud destinataire pour le flux, le 25 3062976 procédé étant opéré par ledit contrôleur SDN et comprenant les étapes du procédé de détermination de chemin de routage de paquets de données entre le noeud source et le noeud destinataire selon l'une quelconque des revendications 1 à 12. 21. Le procédé selon la revendication 20 dans lequel l'exécution des étapes du procédé de détermination de chemin de routage de paquets de données est faite selon si la qualité de service pour un flux de données est prioritaire ou non. 22. Un produit programme d'ordinateur, ledit programme d'ordinateur comprenant des instructions de code permettant d'effectuer les étapes du procédé selon l'une quelconque des revendications 20 à 21, lorsque ledit programme est exécuté sur un ordinateur. 5 10 15