La présente invention concerne un procédé d'allocation dynamique de débits pour un réseau de communication, notamment un réseau du type à hauts débits tel qu'un réseau ATM (Asynchronous Transfer Mode).

Les réseaux ATM ont été conçus pour pouvoir supporter des flux de données multimédia, tels que des données, des sons, des images et de la vidéo. La technologie ATM permet à un même support de transmettre des flux présentant des débits et des demandes de performance différents. Pour pouvoir présenter de telles caractéristiques, les réseaux ATM sont prévus pour pouvoir gérer les ressources et garantir une qualité de service.

Avant d'être établie, une connexion doit en faire la demande au réseau en précisant les caractéristiques souhaitées, et notamment le débit qu'elle entend réserver et la qualité de service désirée. Au besoin, elle précise, dans sa requête, le débit minimum que le réseau doit lui garantir. Si le réseau juge qu'il a les ressources

suffisantes pour satisfaire la demande, alors il établit la connexion mais il garantit également le débit et la qualité de service demandés.

Différentes classes de service ont été définies qui, selon la nature des sources de données et des demandes en performance et en qualité souhaitées par les connexions correspondantes, définissent à leur tour un protocole de contrôle des trafics sur ces connexions. Les classes généralement considérées sont les suivantes : la classe dite CBR (Constant Bit Rate), la classe qui est dite VBR (Variable Bit Rate), la classe dite ABR (Available Bit Rate) et une classe voisine de la classe ABR, la classe dite ABT (ATM Block Transfer).

Pour schématiser, on peut dire que dans la classe CBR, une qualité de service de haut niveau est spécifiée alors qu'aucune qualité de service en terme de temps de transfert ou de gigue n'est explicitement spécifiée dans la classe ABR. Dans la classe VBR, un certain nombre de paramètres de contrôle est défini au moment de la connexion, ces paramètres une fois définis servant au réseau pour garantir une qualité de service.

Les mécanismes qui sont généralement mis en oeuvre pour les classes de service dite ABR et ABT, seules considérées ici, sont les suivants. Pour chacune des connexions actives, de manière périodique, une cellule spécialisée, dite par la suite cellule de gestion de ressources, va parcourir l'ensemble du trajet suivi par les cellules usager de cette connexion. A la réception de cette cellule sur un noeud du réseau, un protocole est mis en oeuvre pour vérifier que le débit alloué jusqu'ici à la connexion n'excède pas une valeur déterminée en fonction des autres connexions du moment. Si tel est le cas, ce noeud va allouer à la connexion un nouveau débit dont la valeur sera placée dans la cellule de gestion de ressources. Arrivée à une extrémité du trajet suivi par les cellules usager, la cellule de gestion de ressources est retournée vers la source de la connexion concernée avec la plus petite valeur de débit autorisée le long du parcours. La source devra alors adapter son débit à cette nouvelle valeur.

Un procédé d'allocation est prévu pour être mis en oeuvre aux noeuds d'un réseau. Il permet d'allouer, à chacune des sources dont les connexions convergent sur

un noeud du réseau et suite à une requête de débit formulée par ladite source, un débit de cellules de manière à partager la bande maxima offerte par le lien de sortie dudit noeud.

Une description des mécanismes mis en oeuvre pour le contrôle du trafic dans la classe ABR est par exemple faite par F. BONOMI et K. W. FENDICK dans un article intitulé"The rate-based flow control framework for the Available Bit Rate Atm service"paru dans IEEE Network de Mars/Avril 1995.

Les procédés d'allocation de débit connus sont généralement mis en oeuvre pour des connexions supportant des données et font utilisation dans les noeuds de files du type FIFO, ce qui ne peut être envisagé pour la transmission de vidéo du fait de la spécificité de celle-ci en ce qui concerne les débits qui sont nécessairement élevés, les temps de retard de transmission qui ne peuvent être trop importants, etc.

Le but de la présente invention est donc de proposer un procédé d'allocation de débit permettant un partage équitable de la bande passante utilisée par différentes sources temps réel, notamment des sources vidéo.

A cet effet, un procédé selon l'invention est caractérisé en ce qu'il consiste, lors de cycles successifs, à : a) au début de chaque cycle, affecter à chacune desdites connexions un débit, et b) pendant le cycle, à allouer, d'une part, à chaque connexion dont le débit requis est supérieur au débit qui lui a été affecté, le débit qui lui a été affecté, ladite connexion étant alors comptabilisée et marquée en tant que connexion écrêtée, et, d'autre part, à chaque connexion dont le débit requis est inférieur au débit qui lui a été affecté, soit le débit déjà alloué au cycle précédent si à ce cycle précédent ladite connexion n'avait pas été marquée en tant que connexion écrêtée, soit le débit requis si au cycle précédent ladite connexion avait été marquée en tant que connexion écrêtée, la différence entre la valeur du débit affecté et la valeur du débit alloué étant alors comptabilisée en tant que valeur de débit non-alloué,

c) et, à la fin dudit cycle, calculer une nouvelle valeur de débit à affecter au cycle suivant à chacune desdites connexions sur la base de la valeur comptabilisée de débit non-alloué et le nombre de connexions écrêtées.

Selon une autre caractéristique de l'invention, il consiste à affecter à chacune desdites sources, lors d'un cycle initial, un débit correspondant au partage équitable entre toutes les sources de la bande maxima offerte par le lien de sortie dudit noeud.

Selon une autre caractéristique de l'invention, il consiste à calculer la nouvelle valeur de débit à affecter au cycle suivant à chacune des connexions écrêtées en partageant équitablement le débit non-alloué entre lesdites connexions écrêtées.

Selon une autre caractéristique de l'invention, il consiste à calculer la nouvelle valeur de débit à affecter au cycle suivant à chacune desdites connexions en partageant équitablement entre lesdites connexions écrêtées ledit débit non-alloué auquel on ôte la valeur de débit affecté en excès.

Selon une autre caractéristique de l'invention, il est prévu pour que la période de chaque cycle soit supérieure à la période de renégociation mise en oeuvre par les équipements dudit réseau.

Selon une autre caractéristique de l'invention, il est prévu pour que la période de chaque cycle soit supérieure à la période de renégociation mise en oeuvre par les équipements dudit réseau augmentée de la durée maxima des temps respectivement mis par des cellules de gestion de ressources desdites connexions pour effectuer le trajet complet de la source considérée à l'autre extrémité du réseau et revenir à ladite source.

Selon une autre caractéristique de l'invention, il est prévu pour compter les requêtes émanant de chacune des sources, ledit procédé n'examinant que les requêtes qui ont un même numéro d'ordre.

Selon une autre caractéristique de l'invention, il est prévu pour marquer une connexion après réception de la requête de la source correspondante, ladite marque étant annulée au début de chaque cycle, et ledit procédé n'examinant que les requêtes des sources dont les connexions sont déjà marquées.

Selon une autre caractéristique de l'invention, il consiste à pondérer les débits respectivement affectés aux sources. Chaque facteur de pondération dépend avantageusement du débit minimum garanti demandé par la source correspondante. Il est par exemple égal au débit minimum garanti demandé par ladite source divisé par la somme totale des débits minimum garantis respectivement demandés par toutes les sources. Le débit qui est affecté à une source peut alors être égal à une valeur de débit commune à toutes les sources que multiplie ledit facteur de pondération.

Selon une autre caractéristique de l'invention, à la réception de la requête d'une source dont la connexion n'avait pas été marquée au cycle précédent en tant que connexion écrêtée, et lorsque le débit maintenant requis est supérieur au débit qui avait été alloué au cycle précédent, il consiste à interrompre le cycle en cours et à recommencer un nouveau cycle à partir de cette requête, le débit affecté à chaque source étant le débit le plus élevé entre le débit courant de la connexion concernée et la valeur de débit équitablement répartie entre toutes les sources.

Selon une autre caractéristique de l'invention, il consiste à conserver dans le contexte de chaque connexion un numéro caractérisant le cycle.

Les caractéristiques de l'invention mentionnées ci-dessus, ainsi que d'autres, apparaîtront plus clairement à la lecture de la description suivante d'un exemple de réalisation faite en relation avec le dessin joint qui illustre le procédé selon l'invention à partir d'un exemple arbitraire.

Le procédé selon l'invention est implanté dans chaque noeud d'un réseau. Là, pour chaque communication active qui converge sur le noeud considéré, est tenu un registre Reg dans lequel est stockée la valeur de débit qui est allouée à cette communication. A des temps espacés d'une période T, la source de chaque communication émet une cellule de gestion de ressources RM sur le trajet de la communication. Au départ, cette cellule RM porte la valeur de débit requis par la source. A chaque noeud, sont comparées la valeur portée par la cellule de gestion RM et celle qui est stockée dans le registre Reg du noeud. Si la valeur de débit stockée dans le registre Reg est inférieure à la valeur de débit portée par la cellule de gestion

RM, alors cette dernière est modifiée en prenant la valeur stockée dans le registre Reg.

Par contre, si elle est égale ou supérieure, alors la valeur portée par la cellule de gestion RM n'est pas modifiée.

Arrivée à l'extrémité du réseau, la cellule de gestion RM est retournée vers la source. Elle porte alors la plus petite valeur de débit qui a été allouée à la communication par le réseau et qui est donc autorisée par celui-ci le long du trajet de la communication. La source adapte alors son débit d'émission de cellules usager à cette nouvelle valeur.

On notera que l'on nomme ici cellules usager, les cellules qui portent les données, par exemple des données d'image et de son, émises par la source à destination de son interlocuteur.

Le procédé selon l'invention concerne donc l'allocation d'un débit à une communication. Cette allocation est dynamique en ce sens qu'elle fait l'objet d'une renégociation de débit qui est effectuée avec la périodicité T d'émission des cellules gestion de ressources RM. Ainsi, pour chaque communication qui converge sur lui, chaque noeud du réseau voit passer, dans une période T, une seule et unique requête de renégociation de débit et y répond, au moyen du procédé de l'invention, en y allouant un débit pour ses cellules usager.

Le procédé de l'invention est donc mis en oeuvre selon des cycles successifs de période T. On va décrire les différentes étapes du procédé telles qu'elles apparaissent dans un cycle.

Si on appelle C la bande maxima que peut supporter le lien de sortie du noeud considéré, une répartition la plus équitable possible entre les N sources dont les connexions convergent sur ce noeud alloue à chaque source la valeur de débit C l N.

En conséquence, lors d'un cycle initial, cette valeur RI = C l N est placée dans chacun des registres Reg respectivement liés aux communications actives.

Lors de chaque cycle, lorsque le noeud reçoit la cellule de gestion de ressources RM émise d'une source dont la connexion converge sur lui, deux cas peuvent se présenter.

Dans un premier cas, la valeur Rq qui est requise par la source et qui est portée par la cellule RM est inférieure à la valeur RI. Alors, un registre RA comptabilisant la quantité A de bande qui n'a pas été allouée pendant le cycle courant est incrémenté de la différence RI - Rq. Par ailleurs, la communication est marquée comme ne pouvant pas augmenter son débit au-dessus de la valeur Rq.

Dans l'autre cas, la valeur requise Rq est supérieure à la valeur R1. La demande de la source est dite écrêtée à la valeur RI et est marquée en conséquence. On incrémente par ailleurs un compteur m qui compte le nombre de demandes écrêtées.

A la fin du cycle, lorsque toutes les sources ont transmis leur cellule de gestion de ressources RM, c'est-à-dire après un temps T correspondant à la période d'émission des cellules RM par les sources, la situation est la suivante.

Les communications dont les demandes de débit Rq sont inférieures à la valeur R1 sont marquées comme ne pouvant augmenter leur débit au-delà de cette valeur Rq. Pour les autres, la valeur du débit qui leur est allouée est pour l'instant égale à la valeur Rl. La totalité de la bande non encore allouée durant le cycle est stockée dans le registre A et le nombre de communications écrêtées est stocké dans le compteur m.

On connaît ainsi le nombre de connexions qui souhaitent augmenter leur débit et la bande qui reste disponible pour cette augmentation. Selon l'invention, on autorise les connexions qui ont été écrêtées à augmenter, au cycle suivant, leur débit d'une valeur correspondant à la bande du lien de sortie du noeud qui n'a pas été encore allouée divisée par le nombre m de communications écrêtées.

Ainsi, au cycle suivant, on remet en oeuvre le procédé de l'invention avec une nouvelle valeur de R1 et en n'autorisant que les connexions précédemment écrêtées à augmenter leur débit.

On va maintenant expliciter le procédé selon l'invention en prenant d'abord un exemple arbitraire illustratif dans lequel trois communications C1, C2 et C3 sont mises en jeu (voir la Fig. 1). La première C1 a une demande de débit correspondant à deux unités, la seconde C2 à six unités et la troisième C3 à neuf unités. La capacité maximale C du lien de sortie du noeud est de quinze unités (C = 15).

Lors du cycle initial CYI, on va affecter à chaque communication un débit équitablement partagé R1 dont la valeur est donc R1 = C/N où N est le nombre de communications actives convergeant sur le noeud considéré. Ici N = 3. On a donc RI = 5. Le débit total affecté est N Rl soit quinze unités.

Selon la terminologie adoptée ici, l'affectation d'un débit à une communication n'est pas l'allocation. Pour une connexion qui a été précédemment écrêtée, la valeur du débit affecté est la valeur maxima de débit que le noeud peut allouer à cette connexion.

Par contre, pour une connexion qui n'a pas été précédemment écrêtée, la valeur du débit affecté est sans rapport avec la valeur de débit alloué. La différence entre la valeur du débit affecté et la valeur du débit alloué est comptabilisée en tant que valeur de bande non allouée.

Ainsi, à la communication Cl, on alloue deux unités et il reste donc trois unités qui n'ont pas été allouées et qui sont alors comptabilisées dans le registre R ( = 3).

A chacune des communications C2 et C3 qui ont été écrêtées à la valeur de cinq unités, on n'alloue que ces cinq unités. Pour ces communications C2 et C3 seulement, la valeur de débit alloué est égale à la valeur de débit affecté.

A la fin de ce cycle, on a donc A = 3 et m = 2 (nombre de communications écrêtées = 2).

Au cycle suivant CY2, on va distribuer équitablement les trois unités qui n'ont pas été allouées au cycle précédent CY, à chacune des deux communications écrêtées C2 et C3, soit #/m = 3/2 = 1,5 unité par communication. Pour ce faire, on va affecter à chaque communication active sur le noeud considéré un débit équitablement partagé R1 de (5 + 1,5) unités soit 6,5 unités. Le débit total affecté est alors de N R1 = 6,5 x 3 = 19,5 unités.

A la communication C1, on alloue deux unités et il reste, par rapport aux 6,5 unités affectées, 4,5 unités non allouées. A la communication C2, on alloue six unités correspondant à sa requête, et il reste donc 0,5 unité non allouée qui ajoutée aux 4,5 unités déjà non-allouées de la communication C1 donnent cinq unités non allouées.

A la communication C3, on alloue 6,5 unités. Cette communication C3 est la seule qui a été écrêtée durant ce cycle. A la fin du cycle, on a donc A = 5 et m = 1.

Pour le calcul de la bande à partager au cycle suivant, on doit retrancher, des cinq unités non allouées, le débit affecté en excédent par rapport à la capacité maxima <BR> <BR> <BR> <BR> C du lien de sortie du noeud, c'est-à-dire (N Rl - C) ~ (19, 5 - 15) = 4, 5 unités. La bande à partager au cycle suivant sera donc égale à : 5 - 4,5 = 0,5 unité qui va permettre de calculer la nouvelle valeur de R1 égale maintenant à 6,5 + 0, 5 = 7 unités.

Au cycle CY3, on va affecter à chaque communication active 7 unités correspondant à la nouvelle valeur de R1. Le débit total affecté est donc de 3 x 7 unités, soit 21 unités. On peut constater qu'à la fin du cycle CY3, # sera égal à 6. La bande à partager au cycle suivant sera alors de A - (N Rl - C) = 0.

Le processus se poursuit ainsi de cycle en cycle.

On va maintenant formaliser le procédé selon l'invention.

La bande disponible pour l'ensemble des communications est la bande disponible sur le lien de sortie du noeud, soit C.

Le débit total qui est équitablement affecté, au débit de chaque cycle, est noté Da et sa valeur est égale à N Rl, d'où : Da=N-Rl Or, ce débit total affecté Da peut être supérieur à la capacité maxima C du lien de sortie du noeud. Il en résulte qu'un débit a été affecté de manière excédentaire par rapport à cette capacité. Ce débit excédentaire De a donc pour valeur : De=Da-C= NRI-C.

On peut donc écrire la relation suivante : C=Da-De=Da- (NR1-C) =Da+ (C-NRI)

A la fin de chaque cycle, le débit total affecté Da a été, dans une première partie, alloué et, dans une seconde partie, non-alloué. Dans la partie allouée, se trouvent, d'une <BR> <BR> part, le débit effectivement alloué aux connexions qui sont écrêtées, soit m. Rl, où m représente le nombre de connexions écrêtées et R1 le débit affecté à chaque communication et, d'autre part, le débit total alloué aux connexions non écrêtées, soit Débii. non -écrétées Quant à la seconde partie non-allouée, elle a été comptabilisée dans le registre R. On peut donc écrire : Da=mRl+ Débit+ non-écrétées soit, en remplaçant dans l'expression précédente : C=m Rl+ (C-N Rl) + Débit+0 non-écrétées ce qui peut se réécrire de la manière suivante : . C c-N. Ry+el C = m Rl + + Débit non-écrétées On voit, par cette relation, que si l'on attribue, au prochain cycle et aux m connexions qui ont été écrêtées précédemment, la valeur qui est comprise entre parenthèses, la bande sera équitablement partagée et sera complètement utilisée.

Selon l'invention, on va procéder de la manière suivante. Au prochain cycle, on va recommencer la mise en oeuvre du procédé de l'invention en autorisant les seules connexions qui ont été écrêtées à augmenter de nouveau leur débit. Pour ce faire, on modifie la valeur de Rï qui est maintenant égale à :

(C - N . R1) + #<BR> <BR> <BR> <BR> R1 = R1 +<BR> m Ainsi, au début de chaque cycle, on se trouve avec un certain nombre de connexions qui ne sont pas autorisées à augmenter leur débit alors que les autres le sont et, ce, jusqu'à une valeur qui correspond à la valeur qui est stockée dans le registre Rl. Puis les connexions sont examinées les unes après les autres par le procédé explicité ci-dessus, pour qu'à la fin du cycle, on puisse déterminer le débit disponible non encore alloué A et le nombre m de connexions écrêtées. De là, on recalcule une nouvelle valeur de R1 qui sera utilisée pour l'examen du cycle suivant. Ce processus se poursuit donc de manière continue de cycle en cycle.

Selon l'invention, si une connexion qui n'a pas été écrêtée lors du cycle précédent souhaite, au cycle courant, augmenter son débit, on interrompt le cycle courant. Puis on modifie la valeur qui est stockée dans le registre Rï et on lance un nouveau cycle à partir de cette connexion. La nouvelle valeur de Rï est égale au maximum entre la valeur de débit précédemment allouée à la connexion concernée et la valeur de débit équitablement répartie 51N, C étant le débit disponible sur le lien de sortie du noeud considéré et N étant le nombre de connexions actives au moment considéré.

Selon un premier mode de réalisation de la présente invention, et afin de s'assurer que, lors d'une période, une renégociation de débit a bien eu lieu pour chaque connexion active convergeant sur le noeud considéré, on prévoit un compteur prévu pour compter les requêtes émanant de chacune des sources, le procédé étant alors prévu pour n'examiner que les connexions qui ont un même numéro d'ordre.

Selon un autre mode de réalisation de la présente invention, on prévoit que la période de modification du registre Rï est plus importante que la période de renégociation mise en oeuvre par les équipements du réseau prévus à cet effet.

Avantageusement, on augmente cette période de la valeur maximale des temps respectivement mis par les cellules de gestion de ressources RM des connexions actives

pour effectuer le trajet complet de la source à l'autre extrémité du réseau et revenir à la source. Ainsi, on est sûr que l'ensemble des sources a eu le temps de se mettre en conformité avec les débits autorisés par les différents noeuds du réseau, mise en conformité qui ne peut avoir lieu qu'après que la cellule de gestion de ressources RM qui est porteuse de l'information correspondant au débit alloué à la source ait eu le temps de retourner jusqu'à la source. Cette manière de faire permet au procédé une certaine robustesse par rapport à la rupture de certaines liaisons.

Au cas où une connexion ferait deux requêtes dans une même période, il ne serait pas tenu compte de la seconde pour qu'elle ne perturbe pas la répartition de la bande passante entre les sources. Chaque connexion est pour ce faire marquée une fois avoir effectué une requête et cette marque est effacée au début de chaque cycle. Ainsi, dans un cycle donné, une demande n'est donc plus acceptée si elle émane d'une connexion qui a déjà été marquée.

Selon un autre mode de réalisation de l'invention, pour éviter qu'une même connexion soit analysée deux fois durant un même cycle, on affecte, à chaque cycle, un numéro d'ordre qui est incrémenté d'une unité à chaque nouveau cycle. Ce numéro d'ordre est mémorisé pour chaque connexion après son analyse dans le cycle. Ainsi, supposons que l'on soit dans le cycle Cy. Dans ce cycle, avant analyse, à une connexion donné, est mémorisé le numéro Cy - l. Après analyse, est mémorisé le numéro Cy.

Avant d'allouer un débit à une source, on vérifie que le numéro d'ordre mémorisé pour la connexion considérée est inférieur d'une unité à celui du cycle courant. Si tel est le cas, l'allocation est mise en oeuvre. Sinon, elle n'est pas mise en oeuvre, car cela signifie que ladite connexion a déjà été analysée dans le cycle courant.

Lorsqu'on interrompt un cycle Cy, suite à une demande de débit d'une connexion non-écrêtée supérieure à ce qu'elle a jusqu'alors demandé, et qu'on recommence un nouveau cycle, on va affecter à ce cycle un numéro égal au numéro du cycle interrompu Cy plus deux unités. Chaque vérification aboutit ainsi à une nouvelle allocation.

Dans le procédé qui vient d'être décrit, le débit demandé par la source vidéo correspondant à son débit maximum demandé est fixe dans le temps au moins à l'échelle de quelques cycles. L'utilisateur peut, s'il le désire, modifier ce paramètre mais, en pratique, il le fera rarement. Si toutefois pour des raisons de taille de réseau ou autres, les demandes des sources devaient être très souvent modifiées, on a pu montrer que le procédé de l'invention tend alors vers une allocation des débits à la valeur C/N si bien que l'on perd l'avantage de pouvoir utiliser la bande disponible pour la partager entre les sources dont les demandes sont les plus élevées.

Dans le procédé qui vient d'être décrit, chaque source fait une demande de débit maximum. Or, le procédé s'applique également au cas où l'on voudrait tenir compte d'une équité qui serait proportionnelle aux débits minimum garantis des sources. Pour ce faire, on procéderait de la manière suivante.

On divise la valeur C du débit disponible sur le lien de sortie du noeud considéré par la somme des débits minima garantis Dmg ; (i = 1 à N). On obtient alors un facteur qui permet la pondération de chaque débit équitablement affecté, noté ici Ri. En effet, on a alors : où DMG ; est le facteur de pondération appliqué à la source Ci.

Chaque connexion Ci est donc écrêtée à la valeur de débit Ri. Si l'on considère un registre R dans lequel est stockée la valeur du débit total affecté à toutes les connexions, la valeur de débit Ri affectée à une connexion sera égale à : R ; = DMG ;. R A la fin de chaque cycle, la valeur recalculée de ce registre sera donnée par la relation suivante analogue à celle mentionnée ci-dessus :

c-R. DMG ; +e 1=1 N C-2Î+A R=R+'°1"''1v -R+ WR+0 DMG ; DMG ; écrétées écrétées où représente la somme des facteurs de pondération, A représente de débit non-alloué et DMG ; écrétées représente la somme des facteurs de pondération des seules connexions qui ont été écrêtées.