Brevet FR2765057A1 — publié le 19981224

L'invention se rapporte à la gestion des flux de données dans les réseaux de communication locaux à accès partagés, par exemple les réseaux connus sous les appellations Ethernet ou Token Ring, en interconnexion avec les réseaux étendus, tel qu'Internet. La charge d'occupation d'un réseau local est classiquement gérée par découpage ou segmentation des capacités de transmission de celui-ci, l'administrateur de réseau allouant statistiquement ou dynamiquement des largeurs de bande en fonction de l'importance des charges des applications prévues aux différents postes du réseau et des ressources ] 0 disponibles. Le problème posé est de fournir à tout élément de réseau (réseau local, routeur, système d'applications) ou application d'un tel réseau la possibilité de transmettre, à tout instant, des flux de données avec une qualité de service supérieure, c'est-à-dire un taux d'erreur aussi faible que possible, et un délai de transmission minimal, quelle que soit la charge du flux de données de l'application à transmettre et l'état d'occupation du réseau et des autres éléments de réseau interconnectés. Le niveau de la qualité de service fourni par les protocoles de l'état de la technique résulte directement de la capacité d'accueil du réseau, partagée de façon égalitaire entre tous les utilisateurs. Ce niveau correspond à celui communément appelé "best effort" ("au mieux" en langage anglo-saxon) qui est offert à tout flux de données sur le même réseau sans tenir compte des autres flux. Des protocoles de gestion centralisée ont été développés pour gérer la transmission des données, tel que celui décrit dans l'article de Y. Bernet, R. Yavatkar et D. Hoffman, intitulé "a proposai for admission control over Internet", publié sur le réseau Internet par le IETF (initiales de Internet Engineering Task Force) sous la dénomination sbm-ethernet-03.txt>, dans sa version de février 1997. Ces protocoles sont désignés sous les initiales SBM (de "Subnet Bandwith Management", c'est- 2 2765057 à-dire gestion des largeurs de bandes de sous-réseaux). La gestion obtenue par de tels protocoles reste totalement dépendante d'un site gestionnaire central dont le rôle est le partage des ressources disponibles en largeurs de bande. La gestion centralisée fragilise le fonctionnement des réseaux, en cas de faute ou de panne de ce site. Un service de gestion localisée est décrit par exemple dans l'article de J. Wroclawski, intitulé "Specification of the Controlled-Load Network Element Service" publié sur l'lnternet par le IETF sous la dénomination , dans sa version de novembre 1996. Un tel service contrôle un ensemble de filtres de "token buckets" (signifiant: réservoirs à jetons en langage anglo-saxon) disposés à l'interface de chaque application d'un élément du réseau. Ce protocole permet de fournir de la bande passante par allocation de bandes via des files d'attente par lesquelles transitent les données en fonction des caractéristiques prédéterminées des "token buckets". Ces protocoles sont dépendants d'autres mécanismes d'échange d'informations, comme par exemple le protocole RSVP (initiales de "Resource Reservation Setup Protocol" qui signifie: protocole de mise en réservation des ressources, en langage anglo-saxon). La qualité de service d'une telle gestion à protocole décentralisé est sensiblement du type "best effort", les différentes applications partageant les mêmes ressources disponibles. Les paquets non conformes aux paramètres, traités en mode 'best effort", sont au mieux différés, les débits sont limités à une valeur maximale et les paquets de dimension supérieure à cette valeur sont refusés. Un tel protocole définit un service dit "à charge contrôlée": il peut traiter les paquets non conformes aux paramètres du réservoir, retarder les paquets qui résultent de distorsions et qui peuvent être jugés non conformes afin de pouvoir "passer" le filtre; mais il refuse les paquets de données de dimension supérieure à la dimension de référence du 3 2765057 réservoir. Au niveau de chaque élément du réseau, par exemple d'un réseau Ethernet, il est alors nécessaire de prévoir une valeur maximale des débits de flux de chaque application, sans garantir pour autant l'absence de collisions ni la perte de paquets d'information. Un filtre à "token buckets" comporte un réservoir à paramètres adaptés au mode "best effort", pour les flux de paquets de données standard, et des réservoirs à paramètres adaptés à chaque flux de paquets de données ayant des spécifications spéciales ou privilégiées, afin de permettre une mise en file d'attente et émission de ces différents flux en sortie des réservoirs en fonction des disponibilités du réseau. Ces solutions ne résolvent pas le problème posé, en particulier elles ne permettent pas de gérer l'allocation de bandes en fonction de la charge d'occupation du réseau avec une qualité de service supérieure. Pour résoudre ce problème, la présente invention propose de mettre en place un protocole de gestion décentralisé distribuant, à chaque instant, une allocation optimisée en adaptant la charge des flux des applications à transmettre aux largeurs de bande disponibles sur le réseau. Plus précisément, I'invention concerne un procédé de gestion de largeurs de bandes allouées d'un réseau local à accès partagé comprenant des postes d'applications, des bus de commutation et des transmissions de données, des filtres de "token buckets" en interface de sortie entre les postes d'application et le bus de transmission au réseau. Ce procédé comporte les étapes suivantes: - chaque élément de réseau diffuse, vers chacun des autres éléments du réseau par liaisons à travers le protocole, les largeurs de bande réservées, des flux de données à transmettre (pour le mode "best effort" et pour les modes privilégiés); chaque élément de réseau détermine alors la valeur d'un paramètre de mesure de la largeur de bande disponible pour sa liaison. 4 2765057 Pour cela, chaque élément de réseau établit une table des valeurs des paramètres transmises à l'étape précédente; - I'élément de réseau ajuste la valeur du paramètre de "best effort" en fonction de la variation du paramètre de largeur de bande disponible de façon à lui préserver une valeur positive ou nulle. Ce procédé est compatible avec l'utilisation du protocole IP (Protocole d'lnternet) pour les connexions du réseau local partagé à d'autres réseaux ou à des réseaux étendus. Ce procédé peut également tirer partie de l'utilisation RSVP avec lequel il est compatible. Lors d'une requête de réservation, le procédé de gestion de l'invention peut comporter des étapes supplémentaires afin de décider l'acceptation ou le rejet des réservations correspondantes, comportant: - la comparaison des valeurs des paramètres de "best effort" avec leur valeur minimale: un nouvel élément n'est pas admissible si tous les paramètres de "best effort" ont déjà été portés à leur valeur minimale rmin, car le paramètre de disponibilité rfr du nouvel élément est alors nécessairement négatif; I'acceptation de l'augmentation de réservation d'un flux privilégié Ar, si elle est inférieure ou égale au paramètre de disponibilité rfr de I'élément; - le refus de cette augmentation de réservation si elle vérifie la condition: Ar > E(rF + r.) au moins l'une des valeurs de disponibilité recalculées rfr reste négative après diminution des paramètres de "best effort". D'autres étapes supplémentaires peuvent être ajoutées afin de prendre en compte des situations particulières ou optimiser la répartition des réservations: - si deux éléments requièrent simultanément une même 2765057 augmentation de réservation, ces requêtes peuvent être rejetées, alors qu'une seule aurait pu aboutir; il est possible de prévoir une relance aléatoire dans le temps des demandes de réservation; - dans le cas o la file d'attente en mode "best effort" est surchargée, une augmentation de ra par diminution du paramètre de disponibilité rf peut être opérée, par exemple par mise à disposition de % de la valeur de rfr; - si la valeur réelle du paramètre de débit en mode "best effort" est sensiblement inférieur (par exemple plus de 10%) au paramètre de réservation ra, une diminution de ce paramètre ra pour rester proche de sa valeur réelle permet d'utiliser en dynamique, c'est-à-dire en fonction des besoins, la bande disponible en mode "best effort"; - dans le cas o un risque de surcharge en mode "best effort" est raisonnablement prévisible, par exemple si de nombreux paquets en mode privilégié ne sont pas conformes aux formats des modes privilégiés dans une application particulière, ces paquets sont adressés en mode "best effort" si aucune diminution de ra n'est induite. L'invention se rapporte également à une structure de filtres de "token buckets" particulière qui, en mode "best effort", comporte plusieurs files d'attente, par exemple deux files avec, respectivement, une priorité élevée pour les paquets d'une application particulière et non conformes et une faible priorité pour les paquets à traiter classiquement en mode "best effort". L'invention concerne également un protocole de gestion distribué pour la mise en oeuvre du procédé de gestion des largeurs de bande. Ce protocole est un protocole purement distribué qui réalise un double échange d'informations entre chaque élément de réseau pour ajuster les paramètres des "token buckets" en vue d'optimiser la charge d'occupation du réseau. Deux types de paramètres sont ajustés: ceux du réservoir du 6 2765057 mode "best effort" et ceux des réservoirs des modes réservés, en modulant les paramètres d'un type par rapport à ceux de l'autre afin de pondérer l'allocation des ressources respectivement entre les flux de type Ubest effort" et les flux de type privilégié en fonction des besoins. D'autres caractéristiques et avantages de l'invention ressortiront à la lecture de la description plus détaillée qui suit, accompagnée des dessins annexés qui représentent, respectivement: - la figure 1, I'organisation du protocole distribué selon l'invention; - la figure 2, le schéma synoptique de l'architecture de base du procédé de gestion des charges de flux de données d'un réseau local partagé selon l'invention; la figure 3, une variante de filtre de "token buckets" selon l'invention. Dans un réseau étendu, un service à charge contrôlée est défini par la fourniture par chaque élément de réseau (routeur, réseau local ou système d'exploitation) de spécifications relatives aux caractéristiques des flux des paquets de données de chaque application à un protocole de gestion. Comme illustré sur la figure 1, I'organisation distribuée du protocole selon l'invention utilise un classement des flux Fa, Fb, Fc de chaque application dans des filtres à "token buckets" 1 du type service à charge contrôlé, c'est-à- dire selon qu'ils appartiennent (Fa) au standard de qualité de service "best effort" ou qu'ils nécessitent (Fb, Fc) une qualité de service spéciale ou privilégiée: dans le premier cas, ils sont segmentés en paquets de format standard en file d'attente dans le registre 2a puis traités par le réservoir 3a. Dans le second cas, ils sont disposés en files d'attentes de format adapté dans des registres particuliers 2b, 2c, avant d'être traités par le réservoir correspondant 3b, 3c. Un bus de commutation 4, contrôlé par le protocole, assure la transmission vers le registre de 7 2765057 sortie 5 en connexion avec le dispositif d'accès 6 au bus de réseau R. Plus précisément, les spécifications des flux comportent l'évaluation des valeurs des paramètres des réservoirs 3a, 3b, ou 3c: débit des jetons ra, rb, ou rc (égal au rapport entre le nombre de jetons et leur durée de retour à l'état libre) et dimension (égale respectivement au nombre na,nb, ou nc de jetons) du réservoir, pour chaque application concernée. Le protocole 7 gère l'admission de chaque élément de réseau en fonction de la ressource disponible, c'est-à-dire la largeur de bande statistiquement disponible, sur la liaison de transmission 6. L'invention fournit une qualité de service supérieure en utilisant un protocole purement distribué 7, réalisant un double échange d'informations 8a et 8b entre chaque application pour ajuster les paramètres des "token buckets" en vue d'optimiser la charge d'occupation du réseau. Des règles d'ajustement des paramètres des "token buckets" gérées par le protocole permettent alors la transmission de données ayant tout type de spécifications. Selon l'invention, deux types de paramètres sont ajustés: ceux du réservoir du mode "best effort" et ceux des réservoirs des modes privilégiés, en modulant les paramètres d'un type par rapport à ceux de l'autre afin de pondérer l'allocation des ressources respectivement entre les flux de type "best effort" et les flux de type privilégié en fonction des besoins. Le schéma synoptique illustré sur la figure 2 montre l'architecture de base du procédé de gestion des flux de données d'un réseau local partagé selon l'invention. A l'étape A de cette architecture, chaque élément de réseau diffuse, vers chacun des autres éléments du réseau, les largeurs de bande réservées, pour le mode "best effort" et pour les modes privilégiés, des flux de données à transmettre à partir de ses applications. Les deux paramètres de réservation diffusés sont, par exemple, les 8 2765057 débits des réservoirs de "best effort" ra, et la somme des débits privilégiés rpr (soit rb + rz +...). Les éléments de réseau transmettent ainsi périodiquement la valeur des paramètres ra et rpr, ainsi qu'une valeur minimale de r, appelée rmin. A l'étape B, I'élément de réseau établit la largeur de bande disponible pour sa liaison. Chaque élément de réseau établit une table 11 de valeurs des paramètres ra et rpr de tous les éléments de réseau connus reliés au bus de liaison. Cette table 11 fournit la valeur de la largeur de bande disponible par calcul d'un paramètre rfr à partir de l'expression suivante: rma, l'élément sur le bus de liaison et N le nombre d'éléments du réseau. A l'étape C, I'élément de réseau ajuste la valeur du paramètre de "best effort" ra en fonction de la variation du paramètre de largeur de bande disponible rfr de façon à préserver à cette dernière une valeur positive ou nulle, afin de pouvoir toujours transmettre. Dans l'exemple de réalisation, lorsque la valeur de rfr devient négative, I'élément de réseau diminue la valeur de ra de la valeur suivante, à condition que ra ne soit pas déjà à sa valeur minimale rain: r, - ram [1-y(r.+r)] Z (ra rmm) Après communication de la nouvelle valeur de r8, l'élément du réseau ne recalcule sa valeur de disponibilité de bande rfr qu'après avoir reçu les transmissions des valeurs de débits ra des autres éléments pour obtenir une nouvelle valeur. Lorsque de nouvelles réservations sont prévues, par exemple par 9 2765057 une modification d'une application privilégiée d'un élément du réseau ou lorsqu'un nouvel élément est connecté, une étape D est appliquée dans l'exemple de réalisation afin de décider de l'acceptation ou du rejet des réservations correspondantes, comportant: - la comparaison des valeurs des paramètres de "best effort" avec leur valeur minimale: un nouvel élément n'est pas admissible si tous les paramètres de "best effort" ra ont déjà été portés à leur valeur minimale rmin, car le paramètre de disponibilité (rfr)o du nouvel élément est alors nécessairement négatif; - I'acceptation de l'augmentation de réservation d'un flux privilégié Ar, si elle est inférieure ou égale au paramètre de disponibilité (rfr)o de l'élément concerné; - le refus de cette augmentation de réservation si elle vérifie la condition: Ar > S(rp, +r,.) au moins l'une des valeurs de disponibilité recalculées rfr reste négative après diminution des paramètres de "best effort". Des étapes supplémentaires peuvent être prévues pour gérer des situations particulières ou optimiser la répartition des réservations: - si deux éléments requièrent simultanément une même augmentation de réservation, ces requêtes peuvent être rejetées, alors qu'une seule aurait pu aboutir; il est possible de prévoir une relance aléatoire dans le temps des demandes de réservation; - dans le cas o la file d'attente en mode "best effort" est surchargée, une augmentation de ra par diminution du paramètre de disponibilité rfr peut être opérée, par exemple par mise à disposition de % de la valeur de rfr; - si la valeur réelle du paramètre de débit en mode "best effort" est sensiblement inférieur (par exemple plus de 10%) au paramètre de 2765057 réservation ra, une diminution de ce paramètre ra pour rester proche de sa valeur réelle permet d'utiliser en dynamique, c'est-à-dire en fonction des besoins, la bande disponible en mode "best effort"; - dans le cas o un risque de surcharge en mode "best effort" est raisonnablement prévisible, par exemple si de nombreux paquets en mode privilégié ne sont pas conformes aux formats des modes privilégiés dans une application particulière, ces paquets sont adressés en mode "best effort" si aucune diminution de ra n'est induite. Par ailleurs certaines applications génèrent des pics de trafic avec un faible débit moyen et nécessitent une plus grande sécurité vis-à-vis des erreurs que celle offerte par le mode "best effort". Ces applications sont celles qui mettent en oeuvre des protocoles à diffusion, tels que RIP (initiales de Route Information Protocol (c'est- à-dire protocole de diffusion de route), et autres protocoles de routage), NTP (initiales de Network Time Protocol) ou RSVP. Les flux de données de ce type ne nécessitent pas de qualité de service particulière ou privilégiée. Ils ne requièrent qu'une priorité de transmission particulière. Il est alors possible d'utiliser en variante une structure de filtre de "token buckets" en mode "best effort" à plusieurs files, par exemple à deux files, comme schématisé sur la figure 3, reprenant la base de l'architecture illustrée en figure 1. Deux files d'attente 2'a et 2"a sont prévues devant le réservoir de jetons du mode "best effort" dans l'architecture présentée avec, respectivement, une priorité élevée pour les paquets de flux F'a de l'application particulière et une faible priorité pour les paquets de flux F"a à traiter classiquement en mode "best effort". Les liaisons en pointillés 30 et 31 indiquent respectivement des priorités de traitement équivalentes pour le "best effort" prioritaire 2'a et le mode privilégié 2b, pour le "best effort" non prioritaire F"a et le mode privilégié 2c. Dans un exemple de mise en oeuvre sous UNIX(r) du procédé selon I l 2765057 I'invention, le message transmis par un élément du réseau est composé de cinq nombres de 32 bits qui représentent, successivement la version du protocole utilisé et d'autres drapeaux (arrivée ou départ d'un élément de réseau), et les valeurs de ra; rmin, rpr, et rm. L'utilisation de nombres de 32 bits permet d'indiquer des valeurs de largeurs de bande allant jusqu'à 4 Gigaoctets/s. Une base de temps T = 10 s est utilisée pour commander les différents événements et la chronométrie. Au départ, I'élément de réseau 1 (figure 1) envoie sur la liaison 8a le message ci-dessus décrit avec rpr = 0, ra égal à r,,in et commence à écouter les messages provenant de la liaison 8b. Un message est envoyé toutes les 2T - t, At appartenant à l'intervalle 0-1 seconde, afin d'éviter une synchronisation entre les différents éléments du réseau. Si nécessaire et si la valeur de disponibilité de bande rfr le permet, ra peut être ajusté avant d'envoyer un message. Lorsqu'un message est reçu, la version du protocole est d'abord vérifiée. Si la version ou si la valeur de rma ne correspondent pas à celles prévues, un message d'erreur est formé. Si l'expéditeur du message est identifié, les valeurs correspondantes de la table de paramétrage sont mises à jour. Si l'expéditeur du message n'est pas connu, les informations du message viennent compléter la table. Lors de changements de valeurs de réservation qui rendent négatif rf, les nouveaux paramètres ne sont pas recalculés avant un délai de T/2 soit 5s, sauf si rft redevient positif. Si rf, reste négatif pendant plus de 3T/2 soit 15s, un message d'erreur est formé. L'invention n'est pas limitée aux exemples de réalisation décrits et représentés. Elle peut par exemple s'appliquer à la gestion des bandes passantes dans des applications multimédia sur le réseau Internet en se basant sur des liaisons de type ATM (c'est-à-dire en Mode de Transfert Asynchrone). 12 2765057 L'invention peut également être utilisée pour la répartition et le contrôle de débit dans des environnements distribués asynchrones. Par exemple, l'ordonnancement des trafics aériens ou routiers dans lesquels l'invention peut directement s'appliquer en utilisant une base de temps plus grande adaptée aux systèmes contrôlés. 13 2765057 REVENDICATIONS 1.- Procédé de gestion de largeurs de bandes allouées d'un réseau local (R) à accès partagé comprenant des postes d'applications, des bus de commutation (4) et des liaisons de transmission de données (6), des filtres de "token buckets" (1) en interface de sortie entre les postes d'application et le bus de transmission (6) au réseau (R), caractérisé en ce qu'il comporte les étapes suivantes: - diffusion de chaque élément de réseau (10) vers chacun des autres éléments du réseau, par liaisons (8a, 8b) à travers le protocole (7), de valeurs de paramètres de largeurs de bande réservées, pour le mode "best effort" et pour les modes privilégiés, des flux de données à transmettre; - détermination par chaque élément de réseau de la valeur d'un paramètre de mesure de la largeur de bande disponible pour sa liaison (6), à partir d'une table (11) des valeurs des paramètres transmises à l'étape précédente; - ajustement par l'élément de réseau de la valeur du paramètre de "best effort" en fonction de la variation du paramètre de largeur de bande disponible de façon à lui préserver une valeur positive ou nulle. 2.- Procédé de gestion selon la revendication 1, caractérisé en ce que les paramètres de réservation diffusés sont les débits des réservoirs de "best effort" ra, et la somme des débits privilégiés rpr, les éléments de réseau (10) transmettant périodiquement la valeur des paramètres ra et rpr, ainsi qu'une valeur minimale rmmn de ra. 3.- Procédé de gestion selon la revendication 1 ou 2, caractérisé en ce qu'il comporte une étape supplémentaire afin de décider de l'acceptation ou du rejet d'une augmentation de réservations, comportant: - la comparaison des valeurs des paramètres de "best effort" avec 14 2765057 leur valeur minimale: un nouvel élément n'est pas admissible si tous les paramètres de "best effort" sont déjà portés à leur valeur minimale rmin, - I'acceptation de l'augmentation de réservation d'un flux privilégié Ar, si elle est inférieure ou égale au paramètre de disponibilité rfr de I'élément; - le refus de cette augmentation de réservation si elle vérifie la condition: Ar > E(r., +r,) au moins l'une des valeurs de disponibilité recalculées rfr reste négative après diminution des paramètres de "best effort". 4.- Procédé de gestion selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il comporte l'étape supplémentaire suivante, dans le cas o deux éléments requièrent simultanément une même augmentation de réservation, une relance aléatoire dans le temps des demandes de réservation est activée. 5.- Procédé de gestion selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il comporte, dans le cas o la file d'attente en mode "best effort" est surchargée, une étape supplémentaire d'augmentation de ra par diminution du paramètre de disponibilité rfr est activée 6.- Procédé de gestion selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il comporte l'étape supplémentaire suivante si la valeur réelle du paramètre de débit en mode "best effort" est sensiblement inférieur au paramètre de réservation ra, une diminution de ce paramètre ra pour rester proche de sa valeur réelle 7.- Procédé de gestion selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il comporte l'étape supplémentaire suivante, dans le cas o un risque de surcharge en mode "best effort" est raisonnablement prévisible - ces paquets sont adressés en mode "best effort" si aucune 2765057 diminution de ra n'est induite. 8.- Structure de filtres de "token buckets" pour la mise en oeuvre du procédé selon l'une quelconque des revendications précédentes, caractérisé en ce qu'en mode "best effort", elle comporte plusieurs files d'attente, avec une priorité élevée pour les paquets d'une application particulière et une faible priorité pour les autres paquets à traiter en mode "best effort". 9.- Protocole de gestion distribué pour la mise en oeuvre du procédé de gestion des largeurs de bande selon l'une des revendications I à 7, caractérisé en ce qu'il réalise un double échange d'informations entre chaque application pour ajuster les paramètres des "token buckets" en vue d'optimiser la charge d'occupation du réseau.