Brevet FR2832276A1 — publié le 20030516

Dispositif et procédé d'analyse réseau à prédiction autonome L'invention concerne la surveillance et la simulation de systèmes complexes. Dans le cadre du contrôle de flux et de congestion dans des réseaux de communication, notamment de type Internet, on cherche, par analyse du débit, à déterminer l'impact des paramètres du réseau. Différentes propositions ont été faites. On retiendra, parmi les plus avancées : [1 ]- Mathis, M. Semske, J. Mahdavi, J. Ott, T. (1997) "The Macroscopic Behavior of the TCP Congestion Communication Review", 27 (3), n 4155, juillet 97, [2]- le brevet WO 01/65 772 Al, [3]-Baccelli, F. and Hong, D."A. I. M. D., Fairness and Fractal Scaling of TCP Traffic.", Technical Report, RR-1455, INRIA Rocquencourt, avril 2001, [4]-Hong, D., Lebedev D.,"Many TCP User Asymptotic Analysis of the AIMD Model", Technical Report, RR-4229, INRIA Rocquencourt, juillet 2001. [1] propose une formule pour évaluer le débit d'une source contrôlée par TCP en fonction de la probabilité de perte de paquets. [2] propose une représentation dans l'algèbre dite"MAX-PLUS"de systèmes complexes, tels que des réseaux de communication, et notamment du contrôle de flux et de congestion. Cette algèbre"MAX-PLUS"permet d'intégrer le caractère aléatoire des paramètres des réseaux, tout en considérant une pluralité de noeuds. Toutefois, [2] ne prend en compte qu'une seule source utilisant un protocole de type TCP. Dans [3] et [4] est proposé un modèle élémentaire permettant d'appréhender l'évolution jointe des débits d'un ensemble de sources TCP partageant un routeur commun. Le modèle de type croissance additive et décroissance multiplicative (AIMD) proposé permet d'évaluer la dégradation des performances due à une synchronisation des pertes dans le routeur partagé. Toutefois, un paramètre reste inconnu : la fonction de probabilité de cette synchronisation. En outre, les modèles proposés sont limités à la représentation, soit de plusieurs routeurs et d'une seule source contrôlée, soit d'un seul routeur partagé entre plusieurs sources contrôlées par TCP. De plus, les systèmes de surveillance et de simulation de ces réseaux contrôlés par TCP ne sont pas autonomes quand à la prédiction du débit obtenu par les sources. C'est à dire qu'ils ne peuvent pas s'affranchir de la nécessité d'observations physiques faites sur un réseau réel comme par exemple celle de la probabilité de pertes dans [1] ou [2], ou la loi des synchronisations dans [3] ou [4] ; à leur tour, celles-ci peuvent difficilement couvrir avec un degré raisonnable de fiabilité l'ensemble des cas possibles, notamment sur un réseau étendu. L'invention vient améliorer la situation. L'invention concerne un procédé de test et de prédiction du comportement d'un réseau informatique comprenant les étapes suivantes : a. mémoriser d'une part une représentation du réseau, comprenant des routeurs, leurs propriétés propres de transmission, et des temps de transit entre routeurs, d'autre part une configuration d'usage du réseau comprenant des classes de trafic, à chacune de ces classes est associé un nombre de sources et un trajet à travers les routeurs, b. à partir de conditions initiales choisies, appliquer répétitivement un modèle d'évolution du trafic, de type croissance additive et décroissance multiplicative, pour simuler une évolution de débits dans le réseau, en mémorisant à chaque fois un jeu de variables de débits des classes ou des sources, et c. si la répétition de l'étape b. produit une orbite périodique, revenant sensiblement sur un jeu de variables de débits des classes ou des sources déjà rencontré, examiner la suite des routeurs rencontrés, comme responsables des pertes pour évaluer le débit obtenu par chaque classe ou source. L'invention concerne également un dispositif de test et de prédiction du comportement d'un réseau informatique. Dans une caractéristique principale de l'invention, le dispositif comprend - une mémoire pour stocker : * des paramètres du réseau comprenant des routeurs, leurs propriétés propres de transmission, et des temps de transit entre routeurs, * des paramètres de configuration d'usage du réseau comprenant des classes de trafic, à chacune de ces classes associé un nombre de sources et un trajet à travers les routeurs, * un module de calcul selon un modèle d'évolution du trafic, de type croissance additive et décroissance multiplicative, - un module de traitement propre à : * à partir de conditions initiales choisies, appliquer répétitivement le modèle d'évolution du trafic, de type croissance additive et décroissance multiplicative, pour simuler une évolution des débits dans le réseau, en mémorisant à chaque fois un jeu de variables de débit des classes ou des sources, * arrêter l'application répétitive du modèle d'évolution du trafic lorsqu'une orbite périodique revenant sensiblement sur un jeu de variables de débits des classes ou des sources déjà rencontré est obtenue * examiner la suite des routeurs rencontrés, comme responsables de pertes pour évaluer le débit obtenu par chaque classe ou source. D'autres caractéristiques et avantages de l'invention apparaîtront à l'examen de la description détaillée ci-après, ainsi que des dessins annexés sur lesquels : - la figure 1 illustre un dispositif informatique comprenant un module de traitement selon l'invention, - la figure 2 illustre un réseau informatique constitué de routeurs partagés entre un ensemble de sessions, - la figure 3 représente un ordinogramme du procédé de simulation pour une analyse réseau selon l'invention, - la figure 4 représente le graphe d'évolution du débit moyen dans un routeur appartenant au trajet d'une classe. L'annexe A comprend les paramètres de réseau, les paramètres de sources et les variables du modèle auxquels la description ci-après fait référence. L'annexe B comprend des étapes de calcul d'algorithmes liés à un modèle auxquelles la description ci-après fait référence. L'annexe C comprend des estimations du taux de synchronisation suivant certaines hypothèses. L'annexe D comprend la formule mathématique à laquelle la description ci-après fait référence. Les dessins et les annexes contiennent, pour l'essentiel, des éléments de caractère certain. Ils pourront donc non seulement servir à mieux faire comprendre la description, mais aussi contribuer à la définition de l'invention, le cas échéant. La description ci-après se réfère à la publication [2] en ce qui concerne un modèle de type croissance additive et décroissance multiplicative (AIMD) utilisé. Ce modèle élémentaire permet d'appréhender l'évolution jointe des débits d'un ensemble de sources TCP partageant un routeur commun sur un réseau informatique. Dans la description, la notation v [j] désigne une variable tableau ou vecteur ("array") ayant une valeur pour chaque valeur de j. On parlera de matrice pour une variable à deux dimensions v [i, j]. La figure 1 illustre un environnement informatique comprenant une unité centrale 1 reliée à un écran 7 et des moyens de saisie 6 tel un clavier ou une souris. L'unité centrale 1 est également reliée à une carte graphique GUI 2 adaptée pour piloter l'affichage de données sur l'écran 7. Selon l'invention, l'unité centrale 1 est propre à travailler en relation avec le module de traitement 3 relié à la mémoire 4. La mémoire 4 stocke des données liées à la représentation réseau 8 et des données 9 liées à la configuration d'usage du réseau. Ces données seront plus largement décrites ci-après. La mémoire 4 comprend un module de calcul 5 qui travaille en correspondance avec le module de traitement 3. Ce module de traitement 3 est propre à appliquer répétitivement un modèle d'évolution du trafic, de type croissance additive et décroissance multiplicative, pour simuler une évolution des débits dans les routeurs du réseau. A chaque application, le module de traitement est propre à demander une mémorisation d'un jeu de variables de débit dans le réseau de façon à prévoir la prochaine époque de congestion et à remédier à la congestion prévue. La description porte sur notamment la prédiction des performances des flux, par exemple de type TCP, et la quantité de service (QoS) dans une topologie Multi-Routeurs. En d'autres termes, le dispositif et le procédé de l'invention sont utilisés entre autre lorsqu'un grand nombre de sources contrôlées par un protocole, de type TCP par exemple, partagent plusieurs routeurs. Cette simulation est basée sur une description fluide du modèle de type croissance additive et décroissance multiplicative (AIMD). La figure 2 illustre un réseau informatique du type utilisé dans l'invention. Ainsi, le réseau est constitué de plusieurs routeurs rO, rl, r2, r3 et r4, le routeur rO étant un routeur d'accès. Les routeurs sont reliés entre-eux par des liens tels que Tl relie rO à r3, T2 relie rO à r2, T3 relie r3 à r4, T4 relie rO à r4, T5 relie r3 à r4, T6 relie rO à rl. Des sources 1,2, 3 référencées par II, 12, 13 et des destinations 1,2, 3 référencées par Dl, D2, D3 sont représentées sur la figure 2. Les sources sont reliées au réseau par le routeur d'accès rO. Les destinations sont reliées au réseau par un routeur d'accès r4, r2, r3 respectivement. La présente description utilise la notion de classes (de traffic). On considérera pour le moment qu'une classe est définie par un trajet et par certaines propriétés de la transmission que l'on peut faire sur ce trajet. Différents trajets peuvent être empruntés pour relier une source à une destination. Un même trajet peut être associé à différentes classes. On associe un trajet à un"type"de classe. Un "type"de classe correspond à l'ensemble des classes définissant un même trajet ou un même chemin bout-en-bout d'une classe (annexe A2-3). Ainsi, pour un trajet reliant une des sources S à Dl, au moins deux types de classe sont définis, le type de classe définissant le trajet (T4) et le type de classe définissant le trajet (T5, T3) et passant par le routeur intermédiaire r3. Pour un trajet reliant une des sources S à D2, au moins deux types de classe sont également définis, le type de classe définissant le trajet (T2) et le type de classe définissant le trajet (Tl, T2) et passant par le routeur intermédiaire r2. Pour un trajet reliant une des sources S à D3, au moins deux types de classe sont de nouveau définis, le type de classe définissant le trajet (T5) et le type de classe définissant le trajet (T4, T3) et passant par le routeur intermédiaire r4. Une classe est définie par un trajet, un type de session, des délais de propagation et un nombre de sources. En référence à l'annexe A2, une classe peut être définie par exemple par l'ensemble des données ST, SN, SR, SB, SE. Plus explicitement, dans une classe's'donnée, si SN [s] = 100, 100 sources appartenant à la classe's'ont les mêmes caractéristiques suivantes : - même type de session F l P (File Transfer Protocol) ou HTTP (Hyper Text Transfer Protocol), - même chemin bout-en-bout, donc en particulier même temps aller-retour désigné par RTT (=rtt [s]) (annexe A3-4). Dans le reste de la description, les classes sont désignées par la variable s et les routeurs sont désignés par la variable r. La même source peut être désignée comme étant une source de classe s et une source de classe s'si les classes s et s'définissent chacune un trajet allant de la même source à la même destination comme précédemment illustré mais ayant une session différente. En outre, il y a plusieurs sources pour une même classe, c'est-à-dire plusieurs sources dont le trajet est identique pour atteindre leur destination. Le terme"époque de congestion n"désigne un instant n auquel sont calculés les débits de chaque classe s (débits égaux au débit de chaque source i de classe s). Cette"époque de congestion n"désigne de plus un instant pour lequel un routeur du réseau est dit "congestionné" ou en "état de congestion", c'est-à-dire un routeur qui aura une ou plusieurs pertes de paquets. En référence à la partie Al de l'annexe A, les paramètres du réseau désignent les paramètres des routeurs définis en Al-1, Al-2, Al-3, Al-4, Al-5. Ainsi, les routeurs, définis par leur capacité à traiter des débits de paquets, peuvent comprendre une mémoire tampon également appelée buffer, dont le rôle est de retenir une partie du débit entrant supérieur au débit sortant. En l'absence de mémoire tampon pour un routeur r, la taille de la mémoire tampon des routeurs est nulle B [r] =O. Les routeurs peuvent être de types différents comme par exemple : - de type FIFO (Fird In First Out) ou FQ (Fair Queing) désignant des types de routeurs susceptibles de perdre des paquets en débordement de file d'attente, également appelés Tail Drop, - de type RED (Random Early Detection) désignant des types de routeurs capable d'éliminer des paquets par anticipation des débordement de files d'attente. Dans l'exemple du modèle d'évolution du trafic de type croissance additive et décroissance multiplicative (AIMD), les variables sont définies en référence à la partie A3 de l'annexe A. La figure 3 illustre un exemple de réalisation de procédé de simulation pour une analyse réseau selon l'invention. Le procédé se réfère aux annexes A, B, C et D reliées au modèle d'évolution du trafic AIMD proposé en exemple. Ainsi, à l'étape 400 et en référence à la partie BO de l'annexe B, des variables du modèle sont initialisées : -en BO-1, chaque élément de la matrice p [s, r] désigne une probabilité de synchronisation des pertes de paquets, appelée taux de synchronisation défini entre 0 et 1 qui est ici supposé prédéfini selon la loi de Bernoulli. La valeur de la variable aléatoire gamma [s, r] égale à 0,5 signifie une loi de probabilité de type"pile ou face", - en BO-2, chaque élément du vecteur c [r] désigne la capacité (en paquets par seconde) qu'une source pourrait avoir de la part d'un routeur si la capacité totale de ce routeur était idéalement partagée entre les sources utilisant ce routeur r, - en BO-3, chaque élément de la matrice a [s, r] désigne une proportion du nombre de sources de classe s sur le nombre de sources utilisant le routeur r, - en BO-4, chaque élément du vecteur m-rtt [r] désigne la somme sur s des a [s, r] divisées chacune par leur temps aller-retour minimum de la classe considérée au carré, - BO-5, chaque élément de la matrice g [s, r] désigne un entier entre 0 et 1 calculé en fonction du taux de synchronisation, - en BO-6, la phase d'initialisation consiste à initialiser les débits moyens pour toutes les classes et pour toutes les époques de congestion n variant de 1 à N (n et N étant des entiers), avec la fonction fO donnée décrivant la condition initiale. Cette fonction peut être telle que, par exemple, f (s) =0 pour toute classe s. Il y a une seule contrainte sur fO : cette fonction doit être telle que pour tout'r', taul [r] de l'étape 1, définie en annexe BO, doit être positif ou nul. Cela signifie que la charge initiale doit être compatible avec les capacités du réseau. La formulation BO-1 est prédéfinie dans le cas où l'hypothèse suivante est faite : - les routeurs ont une mémoire tampon de taille nulle. De plus, pour l'exemple de réalisation du procédé, en Al-5, le type de routeur utilisé est de type FIFO et en A2-2, le type de session est de type FTP. Les étapes 410,420, 430 représentent l'itération de l'annexe B1-0 sur chaque époque de congestion des étapes 1, 2 et 3 définies ci-après. A l'étape 410, un traitement de variables est effectué pour chaque routeur r. Ainsi, l'étape 1 en annexe B1-1 définit, pour chaque routeur r à une époque de congestion n, une somme des débits de source de classes sur l'ensemble des classes selon l'époque de congestion n-1. Ainsi, somn [r] représente la charge (ou débit) totale sur le routeur'r'à la fin de l'itération précédente (lors de la première itération, soml [r] représente la charge totale sur le routeur 'r'définie par la condition initiale). Le calcul de tau-n [r] définit un temps entre l'époque de congestion n-1 donnée et l'époque de congestion n consécutive, appelé temps intercongestion virtuel pour chaque routeur r. En d'autres termes, taun [r] est la durée virtuelle de l'inter-congestion du routeur'r'qui serait effective si par exemple tous les autres routeurs étaient à capacité (c [r]) infinie. L'étape 2 de l'annexe Bl-2 permet de déterminer le temps inter-congestion minimal sur l'ensemble des temps inter-congestion virtuel des routeurs r, encore appelé temps intercongestion du réseau taun. Ce temps inter-congestion minimal désigne le temps entre l'ancienne époque de congestion et l'actuelle époque de congestion. En d'autres termes, la valeur de tau-n donne la n-ième durée inter-congestion du réseau. A l'étape 420, un traitement de débits moyens est effectué pour chaque classe s. Ainsi à l'étape 2 de l'annexe Bl-2, il est calculé en (1) le débit moyen courant xn [s] de chaque classe s à la n ème époque de congestion. (1) applique à toutes les sources le mécanisme de croissance linéaire (AI développé dans les documents présentant le modèle AIMD). La date absolue de la n-ième congestion du réseau est donné par la valeur de tempsn. Pour le routeur, appelé n ième routeur ou routeur congestionné à l'instant n, dont le temps inter-congestion virtuel est égal au temps inter-perte du réseau et qui appartient au trajet de la classe (appelé aussi chemin bout-en-bout de la classe), il est ensuite calculé en (2) de l'étape 3 de l'annexe Bl-3, le nouveau débit moyen xn [s] de chaque classe s défini à l'époque de congestion n. Ce nouveau débit moyen xn [s] calculé est plus faible que le débit moyen précédent pour éviter une congestion, une perte de paquet ou autre au niveau du ou des routeur (s) congestionné (s) à l'époque de congestion n. Le nouveau débit moyen xn [s] est calculé en fonction du taux de synchronisation et de l'ancien débit moyen correspondant. (2) de l'annexe Bl-3 applique aux sources traversant le routeur congestionné le mécanisme de décroissance multiplicative (MD) du mécanisme AIMD en moyenne. A l'étape 430, il est vérifié que les débits calculés correspondent à un état des débits déjà rencontré au préalable ou que le nombre d'itérations des étapes 410 et 420 atteint un nombre déterminé d'itérations (nombre défini par la variable Maxiter de l'étape 0 dans B 1-0). Dans le cas d'une réponse négative, l'itération des étapes 410 et 420 continue pour déterminer le prochain temps minimal inter-virtuel des routeurs et les débits correspondants. Cette itération des étapes 410 et 420 illustre la formule mathématique de l'annexe D comprenant des sommes sur les classes pour calculer le temps inter-congestion d'un routeur, un minimum à trouver parmi les temps inter-congestion des routeurs et ces opérations se répétant pour chaque époque de congestion. Ainsi les débits moyens sont calculés grâce à la matrice de synchronisation représentée par y,,,,. Dans le cas d'une réponse positive à l'étape 430, l'équation de récurrence vectorielle a une solution (sous certaines hypothèses) qui est une orbite périodique à l'étape 440. La théorie garantit l'unicité et l'existence d'une telle orbite finie. En effet, si des congestions (provoquant des pertes) arrivent infiniment souvent sur chaque routeur, une unique solution existe à l'équation de l'annexe D qui a une période finie n indépendante des conditions initiales du vecteur xn []. Cette solution est définie comme une orbite dite périodique car elle serait retrouvée dans le cas d'un nouveau cycle d'itérations. Cette orbite est caractérisée par une suite finie du type Bl-4 dans laquelle rn est la suite des routeurs où ont eu lieu une congestion (provoquant la perte ou les pertes de paquets), x~n [s] est la suite des débits moyens de classe s, tau-n est la suite des temps inter-congestion du réseau, les suites étant définies aux n époques de congestion. Cette orbite à temps discret définit complètement la trajectoire continue par linéarisation des débits définis en annexe Bl-5. Elle définit le 'squelette'du processus du débit instantané. Dans une variante de l'invention, cette orbite peut être déterminée en utilisant un modèle d'évolution de trafic autre que le modèle de type croissance additive et décroissance multiplicative. A l'étape 450, les débits moyens sont analysés. Ainsi, à cette étape, des débits instantanés sont calculés par une approche stochastique si le nombre de sources par classe est élevé (SN). Dans ce cas, les débits instantanés sont calculés à partir des suites de débits moyens obtenus. Les débits instantanés Xn [s, i] sont calculés suivant la formule B2-1 dans laquelle le temps inter-congestion du réseau à l'instant n est ajouté au précédent débit instantané X {n-l} [s, i] et ceci pour chaque classe s et pour chaque source i. Pour chaque routeur de la suite r-n compris dans le trajet que définit une classe s SR [s], le nouveau débit instantané Xn [s, i] est calculé suivant la formule B2-2. La variable aléatoire gamma [s, r] correspond au rapport des débits Xn [s, i] juste après et avant congestion. Ainsi, il est possible de connaître l'évolution des débits instantanés de chaque classe et de prévoir ainsi la performance du réseau. Quand une orbite périodique est trouvée avant un nombre maximal d'itérations, Maxiter, les résultats sur le régime stationnaire découlent de l'exploitation de l'orbite ainsi obtenue. Les résultats sur le régime transitoire (par exemple le temps nécessaire pour atteindre le régime stationnaire) peuvent également être obtenus. Si l'itération s'arrête lorsque un nombre maximal d'itérations est atteint, Maxiter, sans qu'une orbite périodique soit trouvée, il est possible visuellement d'observer si le régime stationnaire est approximativement atteint en traçant l'évolution de xn. Dans le cas où cette visualisation est difficile, on obtient un régime transitoire qui est toujours exploitable. Dans ce cas également, le temps de convergence vers le régime stationnaire est supérieur au temps de simulation temps {Maxiter}. Une valeur typique du nombre maximal d'itérations se situe entre 103 et 106 selon la taille du réseau et le nombre de sources. Dans la figure 4, le graphe d'évolution du débit moyen x dans un routeur appartenant au trajet d'une classe s est une illustration des débits moyens calculés sur un nombre d'itérations égal à 4. A l'époque de congestion n=l, le débit moyen de la classe s est x-1. A l'époque de congestion n=2 est calculé le débit moyen au point A. Dans l'exemple, le temps intercongestion virtuel du routeur considéré est égal au temps inter-congestion du réseau entre les époques de congestion 1 et 2. Ainsi, pour ce routeur appartenant au trajet de la classe s considérée, à l'époque de congestion n=2, le débit moyen x-2 du routeur est calculé en fonction du taux de synchronisation et correspond au point A'. A l'époque de congestion n=3 est calculé le débit moyen au point B. Dans l'exemple, le temps inter-congestion virtuel du routeur considéré est égal au temps inter-congestion du réseau entre les époques de congestion 2 et 3. Ainsi, pour ce routeur appartenant au trajet de la classe s considérée, à l'époque de congestion n=3, le débit moyen x-3 du routeur est calculé au point B'en fonction du taux de synchronisation. A l'époque de congestion n=4 est calculé le débit moyen au point C. Dans l'exemple, le temps inter-congestion virtuel du routeur n'est pas égal au temps inter-congestion du réseau entre les époques de congestion 3 et 4. Ainsi, pour ce routeur appartenant au trajet de la classe s considérée, aucune congestion (entraînant une perte de paquets) n'a lieu, le débit moyen x-4 est celui calculé au point C. A l'époque de congestion n=5 est calculé le débit moyen au point D. Dans l'exemple, le temps inter-congestion virtuel du routeur considéré est égal au temps inter-congestion du réseau entre les époques de congestion 4 et 5. Ainsi, à l'époque de congestion n=5, pour ce routeur appartenant au trajet de la classe s considérée, le débit moyen du routeur est calculé au point D'en fonction du taux de synchronisation. Comme ce débit moyen x-5 est égal au débit moyen x-1, et qu'il en est de même pour les autres classes auxquelles appartient ce routeur et pour d'autres routeurs du réseau, un ensemble de valeur de débits moyen définit l'orbite périodique recherchée. Une variante de l'ordinogramme représenté figure 3 est maintenant développée en référence aux annexes B3 et B4. L'algorithme proposé est une procédure directe de calcul des débits instantanés dans le cas d'une valeur petite de nombre de sources par classe SN, c'est-à-dire une valeur inférieure à une centaine de sources. Ainsi, l'initialisation des débits instantanés s'effectue à l'étape 0 de l'annexe B3. Chaque débit instantané X-n [s, i] prend la valeur d'une fonction F (s, i). Cette valeur est soit une valeur fixe donnée, soit une valeur obtenue par tirage aléatoire. Comme précédemment, l'itération de l'annexe B4-0 correspond à l'itération des étapes 1, 2 et3 des annexes B4-1, B4-2, B4-3. Dans cette variante de réalisation, on n'attend pas l'obtention d'une orbite périodique. La valeur du nombre maximal d'itérations Maxiter varie suivant, par exemple, la durée sur laquelle le réseau (temps {Maxiter}) est étudié ou les contraintes pratiques, comme le temps de simulation. Comme précédemment, l'observation visuelle graphique a posteriori permet d'avoir une idée sur le fait d'avoir atteint un régime stationnaire ou non. Ainsi, l'étape 1 de l'annexe B4-1 calcule les temps inter-congestion virtuels de chaque routeur, les débits xn étant stochastiques (en Ob). L'étape 2 de l'annexe B4-2 calcule le temps inter-congestion virtuel du réseau et, en (lb), le débit instantané courant Xn [s] de chaque classe s à la n ème époque de congestion. (lb) applique à toutes les sources le mécanisme de croissance linéaire (AI développé dans les documents présentant le modèle AIMD). A l'étape 3 de l'annexe B4-3, le mécanisme décroissance multiplicative (MD) du mécanisme AIMD est appliqué aux débits instantanés des sources traversant le routeur congestionné (en 2b). Une autre variante de l'ordinogramme représenté figure 3 est maintenant développée en référence aux annexes B5 et B6. Comme l'algorithme 2 en référence aux annexes B3 et B4, l'algorithme 3 des annexes B5 et B6 est une procédure directe de calcul des débits instantanés dans le cas d'une valeur petite de nombre de sources par classe SN et correspond au cas d'une mémoire tampon non négligeable (B [] > O). L'algorithme 3 correspond à l'algorithme 2 dans lequel ont été ajoutés des éléments d'algorithme précédés d'une étoile. Les variables suivantes ont également été ajoutées concernant la mémoire tampon des routeurs : - bbn [r] : taille de file d'attente intermédiaire à l'étape n. - bnn [r] : taille de file d'attente du routeur'r'à l'étape n. - tauO-n [r] représente le taun [r] de l'algorithme 2, c'est-à-dire le temps virtuel intercongestion obtenu si les autres routeurs sont de capacité c [r] infinie et si le routeur'r' considéré n'a pas de mémoire tampon (buffer). Ainsi, dans l'étape 0 de l'annexe B5, les éléments d'algorithme ajoutés à l'algorithme 2 sont l'initialisation à zéro des tailles de file d'attente bbn [r] et bnn [r]. A l'étape 1 de l'annexe B5-1, le calcul d'un temps inter-congestion virtuel d'un routeur à l'époque de congestion n prend en compte le temps inter-congestion virtuel du routeur sans mémoire tampon et le calcul de la taille de file d'attente intermédiaire du routeur. A l'étape 2 de l'annexe B5-2, après le calcul des temps inter-congestion du réseau tau-n aux époques de congestion n et la mise à jour des débits, les files d'attente bn-n [r] sont mises à jour suivant que, pour une époque de congestion n et un routeur donnés, le temps intercongestion du réseau est supérieur au temps tauO-n [r] ou non. D'autres modes de réalisation de l'invention sont envisagés ci-après. Ainsi, le taux de synchronisation, au lieu d'être prédéfini, est estimé dans ce qui suit. Plusieurs estimations sont possibles. En supposant la synchronisation indépendante du débit (cas RI), on aurait une approximation du taux de synchronisation du type Cl-1, L étant la probabilité de perte de paquet sur une durée de delta [s, r] en partant d'une mémoire tampon (buffer) pleine, et delta étant le délai de réaction du protocole, TCP par exemple, à une perte. Cette formule est obtenue par l'approximation que le rapport B [r]/C [r] est très inférieur à la moyenne pour chaque routeur des temps inter-congestion virtuel taun [r], en d'autres termes B [r]/C [r] moyenne de (taun [r]). Lorsqu'un débit d'entrée d'un routeur est pratiquement égal au débit de sortie de ce même routeur, et lorsque la taille de la mémoire tampon B [r] est négligeable, les variables de la formulation Cl-1 sont calculées de la façon suivante : - la probabilité L de perte de paquet est calculé selon Cl-2 et - delta [s, r] est calculé comme une proportion de temps aller-retour rtt [s] d'une classe s qui dépend de la position du routeur r. Lorsqu'un débit d'entrée d'un routeur est différent du débit de sortie de ce même routeur, et lorsque la taille de la mémoire tampon B [r] n'est pas négligeable, les variables de la formulation Cl-1 sont calculées de la façon suivante : - il faut appliquer une modification sur L telle que proposée en C3-1, où rhô représente le rapport débit d'entrée d'un routeur sur le débit de sortie. Dans le cas d'une synchronisation indépendante du débit, la variable aléatoire gamma [s, r] est déterminée suivant par exemple la loi de Bernoulli comme précédemment vu. En supposant la synchronisation dépendante du débit (cas RI), le taux de synchronisation est calculé par une approximation du type C2-1. Dans tous les cas d'estimation, le taux de synchronisation est estimé pour chaque routeur et pour chaque classe auquelle ce routeur appartient. Dans tous les cas d'estimation, la variable aléatoire gamma [s, r] est déterminée suivant par exemple un modèle linéaire, ou un modèle fonction du débit de manière exponentielle ou polynomiale. Le procédé décrit suppose donnés les paramètres du réseau et les paramètres de chaque source TCP. Le dispositif et le procédé correspondant peuvent avoir les applications typiques suivantes. Une application directe est la prédiction de la performance de la connexion pour un utilisateur typique dans une configuration de réseau donnée. La performance recherchée est par exemple le débit moyen obtenu par un utilisateur, et plus généralement un débit garanti durant un certain pourcentage du temps de connexion, un taux de perte ou toutes autres valeurs qui dépendent de la fluctuation temporelle du débit instantané. Une autre application directe est la réalisation d'un générateur de trafic TCP optimisé. D'autres application indirectes découlent de la première des applications précédentes. Ainsi, une architecture locale peut être optimisée pour un objectif de performance fixé grâce : - au dimensionnement des capacités de routeurs, - au dimensionnement de taille de mémoire tampon. Peuvent également être optimisés : - la disposition géométrique des routeurs (structure hiérarchique), - le choix de la connectivité des routeurs (hiérarchique ou peer-to-peer), - la compréhension et le diagnostic de l'architecture global par une classification des routeurs selon leur performance, la localisation des routeurs de type"goulots d'étranglement". L'invention couvre le produit logiciel comprenant les fonctions utilisées dans le procédé de test. L'invention couvre également le produit logiciel définissant les éléments du module de traitement du dispositif selon l'invention. Il est entendu que l'invention n'est pas limitée à la forme décrite ci-dessus mais s'étend à d'autres variantes de réalisation. Ainsi, dans une autre réalisation de l'invention, les sources sont de type HTTP. Dans une variante de réalisation, le taux de synchronisation est directement estimé par simulation indépendante. Selon un autre mode de réalisation, les routeurs sont de type fair queing (FQ). Cette simulation peut en outre s'appliquer à d'autres applications que celle des réseaux informatiques, par exemple à tout type de topologie réseau dans diverses domaines (réseau routier, hydraulique,...). Annexe A Al Paramètres du réseau Al-1 N~Router : nombre de routeurs ; Al-2 C [NRouter] : capacité des routeurs (unité en paquet/s) ; Al-3 B [NRouter] : taille de buffer des routeurs (unité en paquet/s) ; Al-4 L [NRouter] [NRouter] : délai de transmission (propagation pure) ; Al-5 RT[N~Router] : type de routeur : FIFO, FQ, RED etc. A2 Paramètres des classes A2-1 N~Classe : nombre de classe de sources ; A2-2 ST [NClasse] : type de session, FTP ou HTTP, de la classe ; A2-3 SN[N~Classe] : nombre de sources par classe ; A2-4 SR ~Classe] : chemin bout-en-bout d'une classe ; A2-5 SB[N~C1asse] : délai de propagation (source)- (routeur d'accès) ; A2-6 SE [N~Classe] : délai de propagation (routeur d'accès terminal)- (destination) ; A3 Description des Variables du Modèle A3-1 Xn [s, i] : débit instantané de la source'i'de la classe's'à la n-ième itération ; A3-2 xn [s, i] : débit moyen de la source'i'de la classe's'à la n-ième itération ; xn [s, i] est indépendant de'i' : on pose xn [s] = xn [s, i] A3-3 N [r] : nombre de sources utilisant le routeur'r' ; A3-4 rtt[s] : temps aller-retour de la classe's' ; A3-5 taun : n-ième temps inter-congestion du réseau ; A3-6 tau n [r] : n-ième temps inter-congestion virtuel du routeur'r' ; A3-7 gamma [s, r] : variable aléatoire de synchronisation ; Annexe B BO Initialisation BO-1 p [s, r] : = P (gamma [s, r] = 1/2) ; BO-2 c [r] : =C [r]/N [r] ; BO-3 a [s, r] : = SN [s]/N [r], si'r'dans SR [s] ; = 0 sinon ; BO-4 mrtt [r] : =sumsa [s, r]/rtt [s]/rtt [s] ; BO-5 g [s, r] : =l-p [s, r]/2 ; BO-6 Etape O n = 0 ; temps~n = 0 ; for (s=O ; s Bl Itération Bl-0 for (n=l ; n Bl-1 Etape 1 for (r=O ; r Bl-2 Etape 2 : tau-n : = min~ {r=O.. N~Router} (tau~n[r]) ; (1) x~n [s] : = x {n-l} [s] + taun/rtt [s]/rtt [s] ; temps n : = temps {n-1} + tau n ; Bl-3 Etape 3 : si (tau = tau [r] et'r'dans SR [s]) (2) xn [s] : = g [s, r] * xn [s] ; Bl-4 {r~n, x [s] n, taun} Bl-5 xn [s] xn [s] +tau- {n+l}/rtt [s]/rtt [s] B2 Algorithme 1 B2-1 Xn [s, i] : = (X {n-l} [s, i] + taun/rtt [s]/rtt [s]) ; B2-2 si ('rn'dans SR [s]) Xn [s, i] : = gamma [s, r] * Xn [s, i] ; B3 Algorithme 2-initialisation Etape 0 n =0 ; temps~n = 0 ; for (s=O ; s B4 Algorithme 2 B4-0 for (n=l ; n do Etape2 (n) ; do Etape3 (n) ; } B4-1 Etape 1 for (r=O ; r B4-2 Etape 2 tau-n : = mm {r=O.. NRouter} (taun [r]) ; (lb) Xn [s, i] : = X {n-l} [s, i] + taun/rtt [s]/rtt [s] ; temps~n : = temps {n-l} + tau~n ; B4-3 Etape 3 si (tau = tau [r] et'r'dans SR [s]) (2b) Xn [s, i] : = gamma [s, r] * Xn [s, i] ; B5 Algorithme 3-initialisation Etape 0 n = 0 ; temps~n = 0 ; for (s=O ; s B6 Algorithme 3 B6-0 for (n=l ; n B6-1 Etape 1 for (r=O ; r B6-2 Etape 2 taun : = min~ {r=O.. N~Router} (taun [r]) ; Xn [s, i] : = X {n-l} [s, i] + taun/rtt [s]/rtt [s] ; tempsn : = temps {n-l} + tau~n ; * for (r=O ; r tauO-n [r]) * bnn [r] : = bbn [r] + pow (taun-tau0n [r], 2)/2*mrtt [r] ; * e1se * bnn [r] : = MAX (O, bn-fn-11 [r]-pow (tau~n, 2)/2*m-rtt [r]) ; *} B6-3 Etape 3-idem B4-3 Annexe C Cl Estimation du Taux de synchronisation indépendant du débit (cas RI) C1-1 p (RI) [s, r] : = (l-exp (-C [r] *delta [s, r] *L/N [r]))/ (l-exp (-C [r] *delta [s, r] *L)) ; Cl-2 L = 1/ (B [r] +l) C2 Estimation du Taux de synchronisation dépendant du débit (cas RD) C2-1 p (RD) [s, r] : = p (RI) [s, r] * xn [s]/som [r] ; C3 Probabilité de perte L dans le cas d'une mémoire tampon non négligeable C3-1 L=rho^B[r] * (rho -1)/ (rho^ (B[r]+l) -1) ; Annexe D Revendications 1. Procédé de test et de prédiction du comportement d'un réseau informatique, caractérisé par les étapes suivantes : a. mémoriser d'une part une représentation du réseau (8), comprenant des routeurs (r), leurs propriétés propres de transmission (C, Al-2), et des temps de transit entre routeurs, d'autre part une configuration d'usage du réseau (9) comprenant des classes de trafic, à chacune de ces classes est associé un nombre de sources (SN, A2-3) et un trajet à travers les routeurs (SR, A2-4), b. à partir de conditions initiales choisies (400), appliquer répétitivement un modèle d'évolution du trafic (410,420), de type croissance additive et décroissance multiplicative, pour simuler une évolution de débits dans le réseau, en mémorisant à chaque fois un jeu de variables de débits des classes ou des sources, et c. si la répétition de l'étape b. produit une orbite périodique (430), revenant sensible- ment sur un jeu de variables de débits des classes ou des sources déjà rencontré, examiner la suite des routeurs rencontrés, comme responsables des pertes pour évaluer le débit obtenu par chaque classe ou source (450). 2. Procédé selon la revendication 1, caractérisé en ce que l'étape c. est également effectuée lorsque le nombre de répétitions de l'étape b. atteint un seuil (430). 3. Procédé selon l'une des revendications 1 et 2, caractérisé en ce que l'étape b. comprend bl. le calcul et la mémorisation d'un temps inter-congestion virtuel (taun [r], A3-6) pour chaque routeur. 4. Procédé selon la revendication 3, caractérisé en ce que l'étape bl. comprend également le calcul d'un temps inter-congestion virtuel minimum, en tant que temps inter-congestion effectif du réseau (taun, A3-5). 5. Procédé selon l'une des revendications 3 et 4, caractérisé en ce que l'étape b. comprend en outre : b2. à chaque instant donné, le calcul et la mémorisation d'au moins un débit de classe dont le trajet passe par un routeur congestionné (xn [s], Xn [s]). 6. Procédé selon la revendication 5, caractérisé en ce que le routeur congestionné de l'étape b2. est choisi de manière à ce qu'il vérifie une condition donnée, qui inclut le fait que le temps inter-congestion du réseau (taun, A3-5) est égal au temps inter-congestion virtuel (taun [r], A3-6) pour ce routeur congestionné. 7. Procédé selon l'une des revendications 5 et 6, caractérisé en ce que la condition donnée de l'étape b2. inclut le fait que le routeur est un des routeurs d'un trajet donné défini par une classe de trafic. 8. Procédé selon l'une des revendications précédentes, caractérisé en ce que l'étape a. comprend, pour chaque routeur, une valeur de capacité (C, A1-2), une valeur de taille de mémoire tampon (B, A1-3), une indication de type (RT, A1-5), ainsi que des valeurs de temps de propagation pure entre routeurs. 9. Procédé selon l'une des revendications précédentes, caractérisé en ce que l'étape a. comprend, pour chaque classe de trafic, un nombre de sources par classe (SN, A2-3), un trajet d'une source à une destination (SR, A2-4), une indication de type (ST, A2-2), ainsi que des valeurs de temps de propagation entre une source et un routeur d'accès (SB, A2-5) d'une part et entre un routeur d'accès terminal et une destination (SE, A2-6) d'autre part. 10. Procédé selon l'une des revendications précédentes, caractérisé en ce que le modèle d'évolution du trafic de l'étape b. comprend des variables comprenant le nombre de sources utilisant un routeur donné (N [r], A3-3), un temps aller-retour (rtt, A3-4) d'une classe défini de la source à la destination. 11. Procédé selon l'une des revendications précédentes, caractérisé en ce que le modèle d'évolution du trafic de l'étape b. comprend des variables définies selon des conditions initiales, ces variables comprenant une valeur moyenne de débit d'un routeur, valeur en théorie utilisable pour chaque source partageant ce routeur (c (r), BO-2), une valeur de proportion représentant un nombre de sources d'une classe par rapport au nombre total de sources partageant un routeur (a (s, r), BO-3), une valeur d'accélération pour un routeur (m- rtt [r], BO-4) représentant la somme sur les classes du rapport de la valeur de proportion sur un temps aller-retour de la source à la destination au carré, un taux de synchronisation (p, C1-1 ; C2-1). 12. Procédé selon l'une des revendications précédentes, caractérisé en ce que l'étape b2. comprend une formulation mathématique conforme essentiellement à l'annexe Bl-3. 13. Procédé selon la revendication10, caractérisé en ce que le taux de synchronisation est estimé de façon indépendante du débit. 14. Procédé selon la revendicationl3, caractérisé en ce que le taux de synchronisation est estimé de façon conforme à la formulation mathématique présentée en annexe C1-1 comprenant une probabilité L de perte de paquets. 15. Procédé selon la revendication 10, caractérisé en ce que le taux de synchronisation (p) est estimé conformément à la formulation mathématique de l'annexe C1-1 de façon dépendante du débit. 16. Procédé selon la revendication 15, caractérisé en ce que le taux de synchronisation (p) est estimé conformément à la formulation mathématique de l'annexe C2-1 comprenant une probabilité de perte de paquets L. 17. Procédé selon la revendication 12 et 14, caractérisé en ce que la probabilité de perte de paquets L est estimée conformément à la formulation mathématique de l'annexe Cl-2. 18. Procédé selon l'une des revendications 15 et 16, caractérisé en ce que la probabilité de perte de paquets Lest estimée conformément à la formulation mathématique de l'annexe C3- 1. 19. Procédé selon l'une des revendications précédentes, caractérisé en ce que le taux de synchronisation est calculé par simulation indépendante. 20. Procédé selon l'une des revendications précédentes, caractérisé en ce que la session représente un flux contrôlé par un protocole de type TCP. 21. Procédé selon la revendications 3, caractérisé en ce que l'étape b. comprend d'être effectuée répétitivement pour chaque routeur et pour chaque classe. 22. Dispositif de test et de prédiction du comportement d'un réseau informatique, caractérisé en ce qu'il comprend : - une mémoire (4) pour stocker : * des paramètres du réseau (8) comprenant des routeurs (r), leurs propriétés propres de transmission (C, Al-2), et des temps de transit entre routeurs, * des paramètres de configuration d'usage du réseau (9) comprenant des classes de trafic, à chacune de ces classes associé un nombre de sources (SN, A2-3) et un trajet à travers les routeurs (SR, A2-4), * un module de calcul (5) selon un modèle d'évolution du trafic, de type croissance additive et décroissance multiplicative (AIMD), - un module de traitement (3) propre à : * à partir de conditions initiales choisies, appliquer répétitivement le modèle d'évolution du trafic, de type croissance additive et décroissance multiplicative (AIMD), pour simuler une évolution des débits dans le réseau, en mémorisant à chaque fois un jeu de variables de débits des classes ou des sources (I), * arrêter l'application répétitive du modèle d'évolution du trafic lorsqu'une orbite périodique revenant sensiblement sur un jeu de variables de débits des classes ou des sources (1) déjà rencontré est obtenue * examiner la suite des routeurs rencontrés, comme responsables de pertes pour évaluer le débit obtenu par chaque classe ou source. 23. Dispositif selon la revendication 22, caractérisé en ce que le module de traitement (3) est propre à arrêter l'application répétitive du modèle d'évolution du trafic lorsque le nombre de répétitions atteint un seuil. 24. Dispositif selon l'une des revendications 22 et 23, caractérisé en ce que le module de traitement (3) est propre à calculer et à mémoriser un temps inter-congestion virtuel (taun [r], A3-6) pour chaque routeur. 25. Dispositif selon la revendication 24, caractérisé en ce que le module de traitement est propre à calculer et à mémoriser un temps inter-congestion virtuel minimum, en tant que temps inter-congestion effectif du réseau (taun, A3-5). 26. Dispositif selon l'une des revendications 24 et 25, caractérisé en ce que le module de traitement est propre en outre à calculer et à mémoriser des valeurs de débit des classes dont le trajet passe par un routeur congestionné (xn [s], Xn [s]). 27. Dispositif selon la revendication 26, caractérisé en ce que le routeur choisi l'est de manière à ce qu'il vérifie une condition donnée, qui inclut le fait que le temps intercongestion du réseau (taun, A3-5) est égal au temps inter-congestion virtuel (taun [r], A3- 6) pour ce routeur. 28. Dispositif selon la revendication 27, caractérisé en ce que la condition donnée inclut le fait que le routeur est un des routeurs d'un trajet donné défini par une classe de trafic. 29. Dispositif selon l'une des revendications précédentes, caractérisé en ce que chaque routeur comprend une valeur de capacité (C, Al-2), une valeur de taille de mémoire tampon (B, Al-3), une indication de type (RT, Al-5), ainsi que des valeurs de temps de propagation pure entre routeurs. 30. Dispositif selon l'une des revendications précédentes, caractérisé en ce que chaque classe de trafic comprend un nombre de sources par classe (SN, A2-3), un trajet d'une source à une destination (SR, A2-4), une indication de type (ST, A2-2), ainsi que des valeurs de temps de propagation entre une source et un routeur d'accès (SB, A2-5) d'une part et entre un routeur d'accès terminal et une destination (SE, A2-6) d'autre part. 31. Dispositif selon l'une des revendications précédentes, caractérisé en ce que le modèle d'évolution du trafic comprend des variables comprenant le nombre de sources utilisant un routeur donné (N [r], A3-3), un temps aller-retour (rtt, A3-4) d'une classe défini de la source à la destination. 32. Dispositif selon l'une des revendications précédentes, caractérisé en ce que le modèle d'évolution du trafic comprend des variables définies selon des conditions initiales, ces variables comprenant une valeur moyenne de débit d'un routeur, valeur en théorie utilisable pour chaque source partageant ce routeur (c (r), BO-2)), une valeur de proportion représentant un nombre de sources d'une classe par rapport au nombre total de sources partageant un routeur (a (s, r), BO-3)), une valeur d'accélération pour un routeur (m-rtt [r], BO-4) représentant la somme sur les classes du rapport de la valeur de proportion sur un temps aller-retour de la source à la destination au carré, un taux de synchronisation. 33. Dispositif selon la revendicationl2, caractérisé en ce que le calcul et la mémorisation des valeurs de débit des classes dont le trajet passe par un routeur congestionné (xn [s], Xn [s]) est effectué selon une formulation mathématique conforme essentiellement à l'annexe Bl-5. 34. Dispositif selon la revendication10, caractérisé en ce que le taux de synchronisation est estimé de façon indépendante du débit. 35. Dispositif selon la revendicationl3, caractérisé en ce que le taux de synchronisation est estimé de façon conforme à la formulation mathématique présentée en annexe C1-1 comprenant une probabilité de perte de paquets L. 36. Dispositif selon la revendication 10, caractérisé en ce que le taux de synchronisation est estimé de façon dépendante du débit. 37. Dispositif selon la revendication 15, caractérisé en ce que le taux de synchronisation est estimé conformément à la formulation mathématique de l'annexe C2-1 comprenant une probabilité de perte de paquets L. 38. Dispositif selon la revendication 12 et 14, caractérisé en ce que la probabilité de perte de paquets L est estimée conformément à la formulation mathématique de l'annexe Cl-2. 39. Dispositif selon l'une des revendications 15 et 16, caractérisé en ce que la probabilité de perte de paquets L est estimée conformément à la formulation mathématique de l'annexe C3-1. 40. Dispositif selon l'une des revendications précédentes, caractérisé en ce que le taux de synchronisation est calculé par simulation indépendante. 41. Dispositif selon l'une des revendications précédentes, caractérisé en ce que la session représente un flux contrôlé par un protocole de type TCP.