Nothing Special   »   [go: up one dir, main page]

FR3062976A1 - Procede et dispositif de determination de chemin de routage econome en energie - Google Patents

Procede et dispositif de determination de chemin de routage econome en energie Download PDF

Info

Publication number
FR3062976A1
FR3062976A1 FR1751146A FR1751146A FR3062976A1 FR 3062976 A1 FR3062976 A1 FR 3062976A1 FR 1751146 A FR1751146 A FR 1751146A FR 1751146 A FR1751146 A FR 1751146A FR 3062976 A1 FR3062976 A1 FR 3062976A1
Authority
FR
France
Prior art keywords
network
links
path
energy consumption
determining
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
FR1751146A
Other languages
English (en)
Other versions
FR3062976B1 (fr
Inventor
Siwar Ben Hadj Said
Alexandre Petrescu
Christophe Jeanneteau
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Commissariat a lEnergie Atomique et aux Energies Alternatives CEA
Original Assignee
Commissariat a lEnergie Atomique CEA
Commissariat a lEnergie Atomique et aux Energies Alternatives CEA
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Commissariat a lEnergie Atomique CEA, Commissariat a lEnergie Atomique et aux Energies Alternatives CEA filed Critical Commissariat a lEnergie Atomique CEA
Priority to FR1751146A priority Critical patent/FR3062976B1/fr
Priority to PCT/EP2018/052216 priority patent/WO2018145945A1/fr
Priority to EP18701196.0A priority patent/EP3580898A1/fr
Publication of FR3062976A1 publication Critical patent/FR3062976A1/fr
Application granted granted Critical
Publication of FR3062976B1 publication Critical patent/FR3062976B1/fr
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00Routing or path finding of packets in data switching networks
    • H04L45/12Shortest path evaluation
    • H04L45/124Shortest path evaluation using a combination of metrics
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00Routing or path finding of packets in data switching networks
    • H04L45/18Loop-free operations

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Mobile Radio Communication Systems (AREA)

Abstract

La présente invention concerne un procédé et un dispositif de détermination de chemin de routage de données qui permet de réduire la consommation d'énergie totale dans les réseaux. Le procédé tient compte à la fois de la bande passante disponible du chemin et de la consommation énergétique des liens sans dégrader la qualité de service offerte aux utilisateurs.

Description

Titulaire(s) : COMMISSARIAT A L'ENERGIE ATOMIQUE ET AUX ENERGIES ALTERNATIVES Etablissement public.
Demande(s) d’extension
Mandataire(s) : MARKS & CLERK FRANCE Société en nom collectif.
PROCEDE ET DISPOSITIF DE DETERMINATION DE CHEMIN DE ROUTAGE ECONOME EN ENERGIE.
(5/2 La présente invention concerne un procédé et un dispositif de détermination de chemin de routage de données qui permet de réduire la consommation d'énergie totale dans les réseaux. Le procédé tient compte à la fois de la bande passante disponible du chemin et de la consommation énergétique des liens sans dégrader la qualité de service offerte aux utilisateurs.
FR 3 062 976 - A1
200
Figure FR3062976A1_D0001
Figure FR3062976A1_D0002
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.
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 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 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 1a et 1b illustrent pour une même configuration de 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 cœur (104). Les deux parties du réseau sont couplées via un routeur (103) aussi appelé nœud de bord. Le réseau comprend dans chaque partie, des nœuds 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 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 1a et 1b 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.
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 1a, le routage des paquets (chemin 116) est fait en se basant sur la métrique de la bande passante. Ainsi, les liens avec la plus grande passante sont favorisés. Cette politique de routage entraîne 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 1b, le routage 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 entraîne une consommation énergétique totale du chemin de 74W.
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. 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 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 nœuds ayant une puissance énergétique limitée comme les réseaux ad-hoc ou capteurs. En effet, dans un tel contexte, l'énergie du nœud est une ressource critique qui doit être utilisée 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 nœuds ou de la qualité de la liaison est la plus appropriée pour préserver l'énergie de nœuds.
La demande de brevet U.S. 2013/0315257 A1 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 nœud. Chaque nœud reçoit la consommation énergétique du reste des nœuds qui se trouvent dans le même domaine de routage. Il envoie également sa consommation énergétique vers les autres nœuds. 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 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 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 à 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 disponibilité du réseau.
La demande de brevet U.S. 2015/0222537 A1 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. 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 nœuds du réseau. Ainsi, pour le bon déroulement de l’algorithme, la méthode a besoin des paramètres suivants : le nœud source, le nœud destination, des données sur la topologie du réseau ainsi que des données sur l’état du trafic dans chaque nœud. 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 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 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
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 nœuds, et sans dégrader la qualité de service offerte aux utilisateurs.
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 utilisées.
D’une manière générale, le procédé de l’invention s’appuie sur la mise en œuvre 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 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 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 ;
- 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 ;
- 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 performance prioritaire recherchée, qu’elle soit d’assurer la qualité de service pour les flux, ou de réduire la consommation énergétique.
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 é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 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 œuvre un algorithme de Yen, qui permet de trouver les k meilleurs 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 nœud source et un nœud destinataire d’un réseau comprenant une pluralité de nœuds et de liens entre les nœuds, les liens présentant au 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 nœud source et le nœud 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 valeur croissante ou décroissante de la second 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 ;
- le procédé comprend 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 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 nœuds du 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 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 nœud source et le nœud 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 l’étape de sélection consiste à sélectionner le chemin présentant la bande passante disponible la plus élevée entre le nœud source et le nœud 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 selon des paramètres de qualité de service pour le flux de données ;
- 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 routage de paquets de données entre un nœud source et un nœud destinataire d’un réseau comprenant une pluralité de nœuds et de liens entre les nœuds, les liens présentant au moins des premières et seconde métriques de performance, le dispositif comprenant des moyens pour mettre en œuvre les étapes du procédé revendiqué.
Selon les modes de réalisation :
- les liens entre les nœuds 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 à router dans un réseau des paquets de données entre un nœud source et un nœud destinataire parmi une pluralité de nœuds 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é.
Dans une réalisation, le dispositif revendiqué est implémenté dans au moins un nœud 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 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 nœuds et de liens entre les nœuds, les liens présentant au 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 l’adresse d’un nœud source et l’adresse d’un nœud 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 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 apparaître en appui de la description d’un mode préféré d’implémentation de l’invention mais non limitatif, avec référence aux figures ci-dessous :
Les figures 1a et 1b 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 enchaînement 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;
La figure 5 illustre un enchaînement d’étapes selon une variante du procédé de l’invention dans un autre mode de réalisation ;
La figure 6 illustre un enchaînement d’étapes du procédé de l’invention dans un mode de réalisation pour un réseau SDN ;
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é 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 nœuds et de leur consommation énergétique.
La figure 2 illustre un enchaînement d’étapes (200) du procédé 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 1a et 1b. Le procédé Gogreen peut aussi être opéré dans des réseaux mettant en œuvre un protocole de routage distribué, comme par exemple le protocole OSPF. 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 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 nœuds du réseau où chaque lien entre les nœuds 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 ‘k’ étant un nombre entier prédéfini.
Typiquement, ‘k’ varie entre 1 et 5 pour un graphe ayant des nœuds 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 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 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 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 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 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. 712-716), 1971) qui permet de générer les ‘k’ plus courts chemins sans 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 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.
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 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 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 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 consommation énergétique, et la deuxième métrique ‘w2=BP’ est bande 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 (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 (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 é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.
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 enchaînement d’étapes (500) d’une variante 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 connaître au préalable les exigences spécifiques du trafic à router en 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 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 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, lOWatts), ch2 = (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 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 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 (516) ce chemin pour initier la transmission des données entre la source et la destination. Si plusieurs chemins sont candidats (branche NON de
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 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 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 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.
La figure 6 illustre un enchaînement 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 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) comprend des commutateurs SDN pour le transfert du trafic de 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 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 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 PACKETJN >> venant d’un commutateur ou 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
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 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).
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 sousgroupes de flux.
Ainsi, l’exécution du procédé GoGreen fournit le chemin de routage 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 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 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.
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
- 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 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 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 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, I2, I3) 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 chaque lien de ce chemin. Ainsi la bande passante du premier lien 11 devient 9Mbps, celle du deuxième lien I2 devient 8Mbps et celle du troisième lien I3 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 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 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 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 exhaustif et doit permettre à l’homme du métier d’apporter des modifications et variantes d’implémentation en conservant les mêmes principes.

Claims (22)

  1. Revendications
    1. Procédé de détermination de chemin de routage de paquets de données entre un nœud source et un nœud destinataire d’un réseau comprenant une pluralité de nœuds et de liens entre les nœuds, 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 nœud source et le nœud 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. 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. 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 sousensemble de candidats représentant les meilleurs chemins sans boucle, et où l’étape de classement consiste à classer le sousensemble de candidats.
  4. 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 nœuds 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. 6. Procédé selon l’une quelconque des revendications 1 à 5 dans lequel les métriques de performance sont la bande passante disponible et la consommation énergétique de chaque lien.
  7. 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 deuxième métrique est la consommation énergétique.
  8. 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 de sélection consiste à sélectionner le chemin présentant la plus petite consommation énergétique entre le nœud source et le nœud destinataire.
  9. 9. Procédé selon l’une quelconque des revendications 1 à 6 dans lequel la première métrique est la consommation énergétique et la deuxième métrique est la bande passante disponible.
  10. 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 passante disponible la plus élevée entre le nœud source et le nœud destinataire.
  11. 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 sous-ensemble de candidats selon des paramètres de qualité de service pour le flux de données.
  12. 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 perte maximal de paquets de données, la gigue.
  13. 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 à 12, lorsque ledit programme est exécuté sur un ordinateur.
  14. 14. Dispositif de détermination de chemin de routage de paquets de données entre un nœud source et un nœud destinataire d’un réseau comprenant une pluralité de nœuds et de liens entre les nœuds, les liens présentant au moins des premières et seconde métriques de performance, le dispositif comprenant des moyens pour mettre en œuvre les étapes du procédé selon l’une quelconque des revendications 1 à 12.
  15. 15. Le dispositif selon la revendication 14 dans lequel les liens entre les nœuds du réseau sont filaires et/ou non filaires.
  16. 16. Le dispositif selon la revendication 14 ou 15 dans lequel les paquets de données sont des paquets d’un flux de données multimedia.
  17. 17. Un système de communication apte à router dans un réseau des paquets de données entre un nœud source et un nœud destinataire parmi une pluralité de nœuds 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.
  18. 18. Le système selon la revendication 17 dans lequel ledit au moins un dispositif est implémenté dans au moins un nœud du réseau.
  19. 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 moins un dispositif est implémenté dans le contrôleur SDN dudit réseau.
  20. 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 comprenant une pluralité de nœuds et de liens entre les nœuds, 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 nœud source et l’adresse d’un nœud destinataire pour le flux, le 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 nœud source et le nœud destinataire selon l’une quelconque des revendications 1 à 12.
  21. 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. 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.
    1/7
    3062
    Fibre 1 Gbits/s 100-300 ports Tx/Rx puissance = 2.7W per port
    Fibre 10 Gbits/s > 42 ports Tx/Rx puissance = 13W per port
    Fibre 1 Gbits/s > 300 ports Tx/Rx puissance = 1.9W per port
    2/7
    3062
    200
    202 /
    204 /
FR1751146A 2017-02-13 2017-02-13 Procede et dispositif de determination de chemin de routage econome en energie Active FR3062976B1 (fr)

Priority Applications (3)

Application Number Priority Date Filing Date Title
FR1751146A FR3062976B1 (fr) 2017-02-13 2017-02-13 Procede et dispositif de determination de chemin de routage econome en energie
PCT/EP2018/052216 WO2018145945A1 (fr) 2017-02-13 2018-01-30 Procede et dispositif de determination de chemin de routage econome en energie
EP18701196.0A EP3580898A1 (fr) 2017-02-13 2018-01-30 Procede et dispositif de determination de chemin de routage econome en energie

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR1751146 2017-02-13
FR1751146A FR3062976B1 (fr) 2017-02-13 2017-02-13 Procede et dispositif de determination de chemin de routage econome en energie

Publications (2)

Publication Number Publication Date
FR3062976A1 true FR3062976A1 (fr) 2018-08-17
FR3062976B1 FR3062976B1 (fr) 2021-06-04

Family

ID=58707755

Family Applications (1)

Application Number Title Priority Date Filing Date
FR1751146A Active FR3062976B1 (fr) 2017-02-13 2017-02-13 Procede et dispositif de determination de chemin de routage econome en energie

Country Status (3)

Country Link
EP (1) EP3580898A1 (fr)
FR (1) FR3062976B1 (fr)
WO (1) WO2018145945A1 (fr)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114827018A (zh) * 2021-01-28 2022-07-29 北京邮电大学 一种基于服务类别的sdn路由选择方法、装置及电子设备

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN110740487B (zh) * 2019-09-17 2021-10-29 天津大学 一种能量有效且避障的水下路由方法
FR3126576B1 (fr) * 2021-09-01 2024-08-30 Latelec Procédé de détermination d’une topologie d’interconnexion entre commutateurs d’un réseau de communication, produit programme d’ordinateur et dispositif correspondants.
CN114531716A (zh) * 2021-12-21 2022-05-24 中国人民解放军空军工程大学 一种基于能耗和链路质量的路由选择方法
CN115987870B (zh) * 2022-12-09 2024-05-28 山西大学 一种基于链路关联度的互联网绿色路由节能方法

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6301244B1 (en) * 1998-12-11 2001-10-09 Nortel Networks Limited QoS-oriented one-to-all route selection method for communication networks
US20160234234A1 (en) * 2015-02-05 2016-08-11 Cisco Technology, Inc. Orchestrating the Use of Network Resources in Software Defined Networking Applications

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP2656662A4 (fr) 2010-12-20 2017-08-23 Telefonaktiebolaget LM Ericsson (publ) Routage et commutation économes en énergie
CN103685011B (zh) 2012-09-14 2017-03-15 华为技术有限公司 一种确定节能路由的方法和装置

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6301244B1 (en) * 1998-12-11 2001-10-09 Nortel Networks Limited QoS-oriented one-to-all route selection method for communication networks
US20160234234A1 (en) * 2015-02-05 2016-08-11 Cisco Technology, Inc. Orchestrating the Use of Network Resources in Software Defined Networking Applications

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114827018A (zh) * 2021-01-28 2022-07-29 北京邮电大学 一种基于服务类别的sdn路由选择方法、装置及电子设备
CN114827018B (zh) * 2021-01-28 2023-09-08 北京邮电大学 一种基于服务类别的sdn路由选择方法、装置及电子设备

Also Published As

Publication number Publication date
FR3062976B1 (fr) 2021-06-04
WO2018145945A1 (fr) 2018-08-16
EP3580898A1 (fr) 2019-12-18

Similar Documents

Publication Publication Date Title
EP1589709B1 (fr) Procédé de routage dans un réseau ad hoc
WO2018145945A1 (fr) Procede et dispositif de determination de chemin de routage econome en energie
EP2695443B1 (fr) Procede pour optimiser les capacites d'un reseau de telecommunication de type ad- hoc
EP2005668A1 (fr) Procede de routage dans un reseau ad hoc
EP1817880A1 (fr) Procede et systeme d'adaptation dynamique de metrique de qualite de service dans un reseau ad hoc
EP2510656A1 (fr) Procede de routage qualitatif dans un reseau de communication multi sauts, equipement de gestion de noeud de reseau
WO2019234333A1 (fr) Procédé de sélection d'une route dans un réseau ad hoc
WO2011086250A1 (fr) Liason virtuelle entre operateur de reseau
EP1803263A1 (fr) Procede et dispositif de controle d'admission a un service a qualite de service garantie dans un reseau mpls
CN103312612A (zh) 多约束服务质量路由选择的优化方法及系统
EP2997717A1 (fr) Procede et dispositif de selection d'interface de communication
EP2345210A1 (fr) Gestion de topologie de routage dans un reseau
EP2572479A1 (fr) Procede de routage a etats de liens pour router des flux de donnees dans un reseau maille comprenant des n uds relies par des liens a trois etats
Muscariello et al. Do next generation networks need path diversity?
EP4020926B1 (fr) Procédé de routage pour router un flux élastique dans un réseau de transport
Wang et al. QoS multicast routing based on simulated annealing algorithm
Ilie et al. Unicast QoS routing in overlay networks
He et al. Smart routing: fine-grained stall management of video streams in mobile core networks
WO2024068725A1 (fr) Procédé de gestion du trafic de données entre une entité source et une entité destinataire, entité et programme d'ordinateur correspondants
Byun et al. A tracker-based P2P system for live multimedia streaming services
Dragan et al. Multimedia sharing over opportunistic networks
FR3061397B1 (fr) Procede et systeme d'echanges de donnees
Cai et al. Qcast: A qos-aware peer-to-peer streaming system with dht-based multicast
Famaey et al. Towards intelligent scheduling of multimedia content in future access networks
Ding et al. An improved service-aware multipath algorithm for wireless multimedia sensor networks

Legal Events

Date Code Title Description
PLFP Fee payment

Year of fee payment: 2

PLSC Publication of the preliminary search report

Effective date: 20180817

PLFP Fee payment

Year of fee payment: 4

PLFP Fee payment

Year of fee payment: 5

PLFP Fee payment

Year of fee payment: 6

PLFP Fee payment

Year of fee payment: 7

PLFP Fee payment

Year of fee payment: 8