Brevet FR2829648A1 — publié le 20030314

La présente invention a pour objet un procédé d'ordonnancement de la transmission des données informatiques entre différentes interfaces de communication permettant, d'une part, de garantir une bande passante minimale selon des classes de service prédéfinies en fonction de la nature des données concernées, d'autre part, de réallouer les restants de bandes passantes éventuellement inutilisés, de façon à optimiser la qualité de service au sein d'un ensemble de transmission. Ce procédé peut s'appliquer dans tous les contextes de communication entre machines, tels que les réseaux classiques IPv4 et IPv6, ainsi qu'à différents autres types de réseaux, et s'adapter aux différents équipements de réseaux, tels que les routeurs et les stations hôtes par exemple, comme aux technologies Internet. En plus de sa fonction d'optimisation du trafic de données, il peut être aussi bien utilisé pour limiter le débit des données injectées dans une fonction logicielle. On sait en effet l'importance qu'ont prise aujourd'hui les communications dans le monde informatique : d'une part, le nombre d'interfaces de réseaux est en croissance constante, en même temps que les volumes de données échangées par chaque interface de communication tendent à augmenter ; d'autre part, le développement rapide des applications multimédia engendre un accroissement important des volumes de données à transmettre, en comparaison avec les applications traditionnelles, et demande également une bonne homogénéité des débits de transmission. Dans ce contexte, la résolution des problèmes d'engorgement et la suppression des points de congestion sont des impératifs de plus en plus essentiels pour assurer une qualité de service acceptable. Or, on connaît les procédés d'ordonnancement originels qui traitaient toutes les communications sur le même niveau de priorité selon la technique communément dénommée best effort . L'invention apporte une amélioration relative aux procédés d'ordonnancement grâce à un système de crédit, en assurant en outre la ré-attribution des bandes passantes non utilisées. Le procédé selon l'invention fait appel aux définitions suivantes : - une Bande Passante caractérise un débit de transfert, en bits/seconde par exemple ; - un Paquet de Données est l'unité de transfert suivant laquelle est découpé un ensemble de données à transmettre ; - une Classe de Service identifie les traitements d'ordonnancement à appliquer aux paquets. En vue d'effectuer l'ordonnancement de la transmission des paquets de données informatiques entre différentes interfaces de communication avec une bande passante prédéterminée, le procédé selon l'invention met en oeuvre au moins trois types de traitements, à savoir : un traitement d'entrée des paquets, un traitement de réallocation de bande passante et un traitement des paquets en file d'attente. Ces traitements ont pour effet, d'une part, de garantir des bandes passantes minimales aux paquets de données transmis en fonction de classes d'appartenance prédéfinies pour ces données et, d'autre part, si la bande passante attribuée n'a pas été entièrement consommée, de l'attribuer à d'autres paquets selon leur niveau de priorité, afin d'optimiser la bande passante dans son ensemble. La fonction de Traitement d'Entrée des Paquets est activée à chaque fois qu'un nouveau paquet adressé par l'application émettrice est reçu à l'entrée de ce mécanisme ; son rôle est de vérifier si le paquet concerné peut être ré-émis immédiatement, c'est-à-dire si la bande passante affectée à la classe de service à laquelle appartient ce paquet est suffisante compte tenu du trafic en cours ; si tel n'est pas le cas, ladite fonction tente de placer le paquet dans une file d'attente. La fonction de Réallocation de Bande Passante est activée périodiquement par une tâche cyclique dont la durée de période est dénommée par la suite DP. La fonction correspond à la fin d'un cycle. Elle permet de réallouer la bande passante éventuellement inutilisée par certaines classes de service à d'autres classes pour lesquelles il existe des paquets en file d'attente. La fonction de Traitement des Paquets en File d'attente, activée cycliquement juste après la fonction précédente et marquant le début d'un nouveau cycle, ouveau cycl%" assure le traitement des paquets déjà en file d'attente dans la limite des bandes passantes autorisées. Les trois fonctions principales précitées du mécanisme selon l'invention utilisent des données communes, dénommées respectivement Cartes, Classes et Ctx-paquets et dont les structures sont les suivantes : Une Carte caractérise une interface de sortie du mécanisme selon l'invention et est identifiée par : - une bande passante maximale, désignée par la suite sous l'abréviation BMCA ; - un compteur du crédit actuellement disponible sur l'interface concernée, c'est-à-dire du volume d'information qui peut actuellement être émis à travers cette interface sans dépasser la bande passante autorisée BMCA, désigné par la suite CDCA. Une Classe correspond à une classe de service pour une carte donnée. Elle est caractérisée par : - une bande passante minimale garantie pour la classe, désignée par la suite BMCL ; - un compteur du crédit actuellement disponible pour la classe concernée, c'est-à-dire du volume d'information qui peut actuellement être émis pour cette classe sans dépasser la bande passante garantie BMCL, désigné par la suite CDCL ; - un identifiant d'une file d'attente de taille limitée associée à cette classe ; - une valeur du crédit de dépassement maximum affecté à cette classe, désignée par la suite CPMCL ; - un compteur du crédit de dépassement qui correspond au volume d'information qui peut être émis par cette classe en surplus du crédit disponible CDCL, désigné par la suite CPCL. Un élément Ctx-paquet est créé par le mécanisme de l'invention et associé à chaque paquet traité. Il comprend les informations suivantes : - un pointeur vers le paquet ; - un identifiant de la classe à laquelle appartient le paquet ; - une valeur du volume du paquet, désignée par la suite VP ; - un compteur du reste à émettre , c'est-à-dire de la part du volume de paquet VP qui n'est pas encore traitée si le crédit CDCL de la classe à laquelle appartient ce paquet est insuffisant, désigné par la suite compteur RAE. Dans les différentes définitions de structures qui précèdent, les bandes passantes ou débits d'information peuvent avantageusement être valorisés en nombre de bits/seconde, et les volumes d'information en nombre de bits. Compte tenu desdites définitions, un mode de mise en oeuvre du procédé selon l'invention sera décrit ci-après, à titre d'exemple non limitatif, avec référence aux dessins annexés dans lesquels : La figure 1 représente de façon schématique un mécanisme montrant l'articulation des trois fonctions principales de l'invention dans leur contexte de fonctionnement ; Les figures 2,3 et 4 donnent respectivement des organigrammes de fonctionnement détaillés de chacune de ces trois fonctions principales : Traitement d'Entrée des Paquets, Réallocation de Bande Passante et Traitement des Paquets en File d'attente. Conformément au mécanisme général illustré sur la figure 1, lorsque des paquets de données sont adressés par une application émettrice 1 à destination d'une application réceptrice 2, ils sont pris en charge par la fonction de Traitement d'Entrée des Paquets 3 qui peut soit les ré-émettre directement vers l'application 2 si les crédits disponibles des classes auxquelles appartiennent ces paquets sont suffisants, soit sinon les placer dans les files d'attente FA 1, FA2,..., FAn affectées à chacune des classes, à moins qu'ils n'aient été rejetés en cas de saturation des files d'attente par un dispositif extérieur à l'invention. Une horloge 4 active périodiquement et successivement les fonctions de Réallocation de Bande Passante 5 et de Traitement des Paquets en File d'attente 6, qui reprennent en charge les paquets dans les files d'attente successivement pour tenter de les ré-émettre vers l'application 2, par la fonction 5 lorsqu'il existe des excédents de bande passante non utilisés par d'autres classes, et par la fonction 6 lorsque les crédits disponibles des classes concernées sont devenus suffisants. Le cadre 7 en traits interrompus indique la délimitation du procédé selon l'invention. La figure 2 donne l'organigramme de la fonction de Traitement d'Entrée des Paquets pour un paquet, suivant l'algorithme de fonctionnement déjà décrit plus haut, avec les mêmes notations pour les différentes grandeurs traitées : VP = Volume du paquet CDCL = Crédit disponible pour la classe à laquelle appartient le paquet CDCA = Crédit disponible pour la carte correspondant à cette classe RAE = Compteur du volume du paquet restant à émettre Selon cet organigramme, la fonction de Traitement d'Entrée des Paquets enchaîne, pour chaque paquet traité, les étapes suivantes : - Entrée d'un paquet de classe CL et de volume VP (bloc BI). - Création d'un élément Ctx-paquet associé au paquet concerné, dans lequel le compteur RAE est initialisé à la valeur du volume de paquet VP (bloc B2). - Comparaison du volume VP avec le crédit disponible CDCL de la classe à laquelle appartient le paquet (bloc B3). - Si le volume VP est inférieur ou égal au crédit CDCL, le paquet peut être émis immédiatement, avec les traitements suivants : - marquage du paquet, selon un procédé extérieur à l'invention, - envoi du paquet à destination de l'application réceptrice, - déduction du volume VP du crédit CDCL, - déduction du volume VP du crédit disponible CDCA de la carte concernée, - libération de l'élément Ctx-paquet, - fin du traitement (bloc B4). - Si le volume VP est supérieur au crédit CDCL, le paquet ne peut être émis immédiatement. Il est alors possible de mettre en oeuvre une procédure du type communément dénommé drop policy pour déterminer, selon l'état de remplissage de la file d'attente associée à la classe concernée, si le paquet doit être conservé (bloc Bs). - Si tel est le cas, les opérations réalisées sont : - déduction du crédit CDCL du crédit de la carte CDCA (CDCA CDCA-CDCL), - déduction du crédit CDCL du compteur RAE de l'élément Ctx- paquet (RAE = RAE-CDCL), - mise à zéro du crédit CDCL (CDCL = 0), - insertion du paquet dans la file d'attente concernée (bloc B7), - fin du traitement. - Si le paquet doit être supprimé (bloc B5), les seules opérations effectuées sont : - libération de l'élément Ctx-paquet (bloc Bug), - rejet du paquet et fin du traitement (bloc Bio). La figure 3 donne l'organigramme de la fonction de Réallocation de Bande Passante, suivant l'algorithme de fonctionnement déjà décrit plus haut, avec les mêmes notations pour les différentes grandeurs traitées : CPCL = Crédit de dépassement actuellement autorisé pour la classe à laquelle appartient le paquet CPMCL = Crédit de dépassement maximal attribué à cette classe Selon cet algorithme, la fonction de Réallocation de Bande Passante, activée périodiquement, réalise, pour toutes les classes rangées par ordre de priorité décroissante ayant des paquets en file d'attente successivement, les traitements suivants : Remise du crédit de dépassement CPCL de la classe concernée à sa valeur maximale autorisée CPMCL (CPCL = CPMCL) (bloc CI). Comparaison du compteur RAE extrait de l'élément Ctx-paquet du paquet placé en tête de file d'attente (bloc C2) avec le crédit CPCL (bloc C3). Si le compteur RAE est inférieur ou égal au crédit RAEG = min (CPCL, CDCA) minimum entre les deux valeurs], le paquet peut être émis, avec les étapes suivantes : - marquage du paquet, selon un procédé à définir extérieur à l'invention, - envoi du paquet à destination de l'application réceptrice, - déduction du compteur RAE du crédit de dépassement CPCL, - déduction du compteur RAE du crédit disponible de la carte concernée CDCA, - libération de l'élément Ctx-paquet du paquet traité, (bloc C4) - test pour détecter le dernier paquet (bloc Cs), - passage au paquet suivant en file d'attente si ce n'est pas un dernier paquet (bloc C6) ; - s'il n'y a plus de paquets en attente pour la classe en cours, passage à la classe suivante (bloc C7) avec détection de la dernière classe (bloc Ce) ; - s'il n'y a plus de classe à traiter (bloc Cg) alors, fin des traitements. - Si le compteur RAE est supérieur au crédit RAEG (bloc C3), le paquet ne peut être émis et les traitements successifs sont alors : - déduction du crédit RAEG du compteur RAE, - déduction du crédit RAEG du crédit de la carte concernée CDCA, - déduction du crédit RAEG du crédit CPCL, (bloc CIl) - passage à la classe suivante (bloc C7) ; - s'il n'y a plus de classe à traiter (bloc Cg) alors, fin des traitements. La figure 4 donne l'organigramme de la fonction de Traitement des Paquets en File d'attente, suivant l'algorithme de fonctionnement déjà décrit plus haut, avec les mêmes notations pour les différentes grandeurs traitées : BMCA = Bande passante maximale attribuée à l'interface de sortie correspondant à chaque carte DP = Durée de la période de l'horloge BMCL = Bande passante minimale affectée à la classe à laquelle appartient le paquet traité Cette fonction de Traitement des Paquets en File d'attente, activée périodiquement juste après la fonction précédente, agit comme cette dernière pour une carte donnée sur chaque classe successivement, ces classes étant traitées dans un ordre de priorité décroissante. Pour une carte donnée, la fonction rétablit à sa valeur maximale, c'est-à-dire au produit du débit maximal de l'interface associée à cette carte BMCA par la durée DP de la période d'activation de la fonction, le crédit CDCA de la carte (bloc D2). Les traitements effectués pour chaque classe sont ensuite : - Remise du crédit disponible CDCL de la classe concernée à sa valeur initiale, c'est-à-dire au produit de la bande passante minimale affectée à cette classe BMCL par la durée DP de la période d'activation (bloc D3). - Comparaison du compteur RAE extrait de l'élément Ctx-paquet du paquet placé en tête de file d'attente (bloc D4) avec le crédit CDCL (bloc Dus). - Si le compteur RAE est inférieur ou égal au crédit CDCL, le paquet peut être émis, avec les étapes suivantes : - marquage du paquet, selon un procédé à définir extérieur à l'invention, - envoi du paquet à destination de l'application réceptrice, - déduction du compteur RAE du crédit de dépassement CDCL, - déduction du compteur RAE du crédit disponible de la carte concernée CDCA, - libération de l'élément Ctx-paquet du paquet traité, (bloc D6) - passage au paquet suivant en file d'attente après détection du dernier paquet (bloc D7) ; - s'il n'y a plus de paquets en attente pour la classe en cours, passage à la classe suivante (bloc Dg) après détection de la dernière classe (bloc D9) ; - s'il n'y a plus de classe à traiter, fin des traitements. - Si le compteur RAE est supérieur au crédit CDCL, le paquet ne peut être émis et les traitements successifs sont alors : - déduction du crédit CDCL du compteur RAE (RAE = RAE- CDCL), - déduction du crédit CDCL du crédit de la carte concernée CDCA (CDCA-CDCA-CDCL), - remise à zéro du crédit CDCL (CDCL = 0), (bloc Du) - passage à la classe suivante (bloc Dg) ; - s'il n'y a plus de classe à traiter, fin des traitements. Il convient de noter que les traitements nécessaires au fonctionnement du procédé selon l'invention mais ne faisant pas partie de celle-ci, à savoir : - la gestion des files d'attente suivant l'un des mécanismes connus sous les noms de FIFO, LIFO ou autres, - la logique de suppression éventuelle de paquets lorsque des files d'attente arrivent à saturation, - le marquage des paquets en fonction de la classe à laquelle ils appartiennent, correspondent à des outils logiciels déjà connus et disponibles sur le marché. Il faut également remarquer que le procédé selon l'invention peut être réalisé aussi bien par des moyens matériels que par des moyens logiciels. Bien entendu, l'invention ne se limite pas au mode d'exécution précédemment décrit. Ainsi, notamment, les fonctions de Réallocation de Bande Passante 5 et de Traitement des Paquets en File d'attente 6 (figure 1) pourraient être permutées, la fonction de réallocation s'effectuant après la fonction de traitement des paquets en file d'attente. REVENDICATIONS 1. Procédé pour l'ordonnancement de la transmission de paquets de données informatiques entre différentes interfaces de communication, avec une bande passante prédéterminée, caractérisé en ce qu'il met en oeuvre au moins trois types de traitements, à savoir : un traitement d'entrée des paquets, un traitement de réallocation de la bande passante et un traitement des paquets en file d'attente ; ces traitements ayant pour effet, d'une part, de garantir des bandes passantes minimales aux paquets de données transmis, en fonction de classes d'appartenance prédéfinies de ces données selon leur niveau de priorité et, d'autre part, de réattribuer les excédents de bandes passantes éventuellement non utilisées, afin d'optimiser dans son ensemble la vitesse du trafic de transmission. 2. Procédé selon la revendication 1, caractérisé en ce que le traitement d'entrée des paquets est activé à chaque réception d'un nouveau paquet adressé par l'application émettrice, ce traitement consistant à vérifier si le paquet concerné peut être ré-émis immédiatement, dans le cas où la bande passante affectée à la classe de service à laquelle appartient ce paquet est suffisante compte tenu du trafic en cours et le placement du paquet dans une file d'attente dans le cas contraire. 3. Procédé selon l'une des revendications 1 et 2, caractérisé en ce que le traitement d'entrée des paquets comprend, pour chaque paquet, la succession d'étapes suivantes : - Création d'un élément Ctx-paquet associé au paquet concerné, dans lequel le compteur du"reste à émettre"est initialisé à la valeur du volume de paquet VP (bloc B2) - Comparaison du volume VP avec le crédit disponible CDCL de la classe à laquelle appartient le paquet (bloc B3) - L'émission immédiate du paquet si le volume VP est inférieur ou égal au crédit CDCL avec marquage du paquet, envoi du paquet à l'application réceptrice, déduction du volume VP du crédit CDCL, déduction du volume VP du crédit disponible CDCA de la carte concernée et libération de l'élément Ctx-paquet - Si le volume VP est supérieur au crédit CDCL, l'essai de mise en file d'attente du paquet avec mise en oeuvre d'une procédure pour déterminer, selon l'état de remplissage de la file d'attente, si le paquet doit être conservé (bloc B$) - Si le paquet doit être conservé, la déduction du crédit CDCL du crédit de la carte CDCA, la déduction du crédit CDCL du compteur RAE de l'élément Ctx-paquet, la mise à zéro du crédit CDCL (bloc B6) - Si le paquet doit être supprimé, la libération de l'élément Ctx-paquet (bloc B9) 4. Procédé selon l'une des revendications précédentes, caractérisé en ce que le traitement de réallocation de bande passante activée périodiquement par une tâche cyclique de période DP et correspondant à la fin d'un cycle, consiste à réallouer la bande passante éventuellement inutilisée par certaines classes de service à d'autres classes pour lesquelles il existe des paquets en file d'attente. 5. Procédé selon la revendication 4, caractérisé en ce que le traitement de réallocation de bande passante comprend : - La remise du crédit de dépassement CPCL de la classe concernée à sa valeur maximale autorisée CPMCL (bloc CI) - La comparaison du compteur RAE extrait de l'élément Ctx-paquet du paquet placé en tête de file d'attente (bloc C2) avec le crédit RAEG Si le compteur RAE est inférieur ou égal au crédit RAEG (bloc C3), l'émission du paquet ( (bloc C4) avec le marquage du paquet, l'envoi du paquet à destination de l'application réceptrice, la déduction du compteur RAE du crédit de dépassement CPCL, la déduction du compteur RAE du crédit disponible de la carte concernée CDCA, la libération de l'élément Ctx-paquet du paquet traité, le passage du paquet suivant (bloc C6) en file d'attente, le passage à la classe suivante (bloc Cg) s'il n'y a plus de paquets en attente pour la classe en cours (bloc Cs), la fin du traitement intervenant s'il n'y a plus de classe à traiter (bloc Cg) - Si le compteur RAE est supérieur au crédit RAEG (bloc C3), la déduction du crédit RAEG du compteur RAE, la déduction du crédit RAEG du crédit de la carte concernée CDCA, la déduction du crédit RAEG du crédit CPCL (bloc Cn), le passage à la classe suivante et s'il n'y a plus de classe à traiter, la fin des traitements. 6. Procédé selon l'une des revendications précédentes, caractérisé en ce que le traitement des paquets en file d'attente est activé cycliquement après le traitement de Réallocation de Bande Passante et assure le traitement des paquets déjà en file d'attente dans la limite des bandes passantes autorisées. 7. Procédé selon la revendication 6, caractérisé en ce que le traitement des paquets en file d'attente s'effectue pour une carte donnée successivement sur chaque classe, ces classes étant traitées dans un ordre de priorité décroissante. 8. Procédé selon l'une des revendications 6 et 7, caractérisé en ce que pour une carte donnée le traitement des paquets en file d'attente comprend le rétablissement du crédit CDCA de la carte à sa valeur maximale, le remise du crédit disponible CDCL de la classe concernée à sa valeur initiale ; la comparaison du compteur RAE extrait de l'élément Ctxpaquet du paquet placé en tête de file d'attente avec le crédit CDCL, puis, d'une part, si le compteur RAE est inférieur ou égal au crédit CDCL l'émission du paquet avec marquage du paquet, envoi de paquet à destination de l'application réceptrice, déduction du compteur RAE du crédit de dépassement CDCL, déduction du compteur RAE du crédit disponible de la carte concernée CDCA, libération de l'élément Ctx-paquet du paquet traité, passage du paquet suivant en file d'attente, s'il n'y a plus de paquet en attente pour la classe en cours, passage à la classe suivante, fin des traitements dans le cas où il n'y a plus de classe à traiter et, d'autre part, si le compteur RAE est supérieur au crédit CDCL, la déduction du crédit CDCL du compteur RAE, la déduction du crédit CDCL du crédit de la carte concernée CDCA, la remise à zéro du crédit CDCL, le passage à la classe suivante et, s'il n'y a plus de classe à traiter, la fin des traitements. 9. Procédé selon la revendication 1, caractérisé en ce que les bandes passantes garanties pour chaque classe d'appartenance des données à transmettre sont définies en valeur absolue et non en pourcentage d'une bande passante globale. 10. Procédé selon la revendication 1, caractérisé en ce que les fonctions de Réallocation de Bande Passante et de Traitement des Paquets en File d'attente sont activées successivement mais de manière indépendante par une horloge périodique assurant un contrôle temporel rigoureux des volumes de données autorisés à la transmission. 11. Procédé selon la revendication 1, caractérisé en ce que les paramètres de bande passante minimale et de volume de dépassement autorisé pour chaque classe d'appartenance sont déterminés par l'administrateur du réseau de transmission concerné. 12. Procédé selon la revendication 1, caractérisé en ce qu'il s'applique à tous les types de réseaux de transmission classiques et peut être intégré à tous les types d'équipements de réseaux tels que stations hôtes ou routeurs, comme aux technologies du réseau Internet. 13. Procédé selon la revendication 1, caractérisé en ce qu'il est réalisé aussi bien par des moyens matériels que par des moyens logiciels. 14. Procédé selon la revendication 1, caractérisé en ce qu'il est utilisé pour limiter les débits de données injectées à l'entrée d'une fonction logicielle. 15. Procédé selon la revendication 1, caractérisé en ce que les fonctions de réallocation de bande passante (5) s'effectuent après la fonction de traitement des paquets en file d'attente (6).