Brevet FR2907291A1 — publié le 20080418

-1- La présente invention concerne un procédé de simulation de l'état d'un réseau de télécommunications. On considère par exemple un réseau de télécommunication de type TCP/IP comprenant une pluralité de routeurs constituant des noeuds du réseau, au sein duquel sont échangés des paquets de données. On sait que le développement à venir de l'usage d'Internet rend nécessaire de simuler les futurs états du trafic en son sein afin de mieux anticiper les moyens à mettre en place. Il est connu de l'état de la technique, notamment du document intitulé Time- stepped Hybrid Simulation (TSHS) for Large Scale Networks , des auteurs Guo, Y. et al. publié en 2000 dans Proc. Infocom, pp.441-450, un procédé de simulation de l'état d'un réseau de télécommunications dans lequel on discrétise le temps de simulation en une succession de dates et on simule l'état du réseau à chaque date. Ce procédé de simulation consiste tout d'abord à simuler la présence, à une même date donnée, de paquets de données à un même noeud du réseau, chacun de ces paquets étant destiné à être acheminé jusqu'à un noeud de destination qui lui est propre. Le procédé comprend une étape suivante au cours de laquelle on simule successivement, l'acheminement de chacun desdits paquets jusqu'à son noeud de destination. Pour simuler l'acheminement de chaque paquet, on détermine pour chaque noeud, le lien de sortie vers le prochain noeud et on détermine la date de présence du paquet au noeud suivant. On procède ensuite de la même manière avec les paquets de données présents, à la date donnée, à d'autres noeuds du réseau. Le chemin à suivre par un paquet est déterminé grâce à des informations contenues dans l'en-tête du paquet et/ou dans les routeurs du réseau. En pratique, le routage et l'acheminement du paquet sont des opérations simples et rapides en elles-mêmes. Cependant, lorsqu'on souhaite simuler un grand réseau, le nombre de paquets à router dans le réseau est important si bien que l'on est confronté à une quantité considérable de paquets à router. Ainsi, le procédé de l'état de la technique n'est pas adapté à la simulation de grands réseaux car il est trop coûteux en ressources de calcul et/ou trop lent à mettre en oeuvre. L'invention a pour but de proposer un procédé de simulation de l'état d'un réseau de télécommunications permettant de simuler des réseaux de toutes tailles sans requérir trop de ressources de calcul. A cet effet, l'invention a pour objet un procédé de simulation de l'état d'un réseau de télécommunications, comprenant les étapes consistant à : 2907291 -2-simuler la présence, à une même date, de paquets de données à un même premier noeud du réseau, paquets dont on souhaite simuler l'acheminement jusqu'à un même deuxième noeud du réseau ; et - simuler de façon globale l'acheminement d'au moins une quantité, au moins égale 5 à deux, desdits paquets. On entend par simuler la présence de paquets, soit simuler un par un chaque paquet, soit simuler de façon globale la présence d'une quantité de paquets. Grâce à l'invention, on réduit le nombre de paquets de données à router puisqu'on simule, de façon globale, l'acheminement d'une pluralité de paquets, présents en un 10 même premier noeud et tous destinés à être acheminés vers un même deuxième noeud. En d'autres termes, pour simuler l'acheminement de la quantité desdits paquets, on considère que tous lesdits paquets sont identiques, ce qui permet de ne simuler l'acheminement que d'un seul de ces paquets tout en tenant compte du nombre de paquets dans le groupe. On réduit ainsi d'autant les ressources de calcul nécessaires à 15 cette simulation. Le procédé de simulation selon l'invention peut en outre comporter l'une ou plusieurs des caractéristiques suivantes. - Durant l'étape de simulation d'acheminement, on simule l'acheminement de la quantité de paquets selon un chemin prédéterminé. Dans le procédé de simulation de 20 l'état de la technique, à chaque fois qu'un paquet est présent à un noeud, on détermine le lien de sortie qu'il doit suivre pour être acheminé jusqu'au noeud suivant. Grâce à l'invention, le chemin pour router un paquet depuis le premier noeud jusqu'au deuxième noeud n'est calculé qu'une fois, au début de la simulation de l'acheminement, et ce, quel que soit le nombre de noeuds intercalés entre les premier et deuxième noeuds. Il en 25 résulte un gain important dans les ressources de calcul nécessaires à la mise en oeuvre du procédé de simulation. - Lors de la mise en oeuvre de l'étape d'acheminement : o si un chemin pour acheminer un paquet depuis le premier noeud jusqu'au deuxième noeud a déjà été déterminé antérieurement à la mise en oeuvre de 30 cette étape, on utilise ce chemin prédéterminé pour simuler l'acheminement de la quantité de paquets, et o sinon, on détermine ce chemin et on l'utilise pour simuler l'acheminement de la quantité de paquets. Pour pouvoir réutiliser des chemins déterminés antérieurement, on garde en 35 mémoire ces chemins en relation avec les premier et deuxième noeuds auxquels ils correspondent. Grâce à l'invention, on ne détermine qu'une fois le chemin prédéterminé 2907291 -3- pour acheminer des paquets entre deux noeuds du réseau. Par exemple, lorsqu'on souhaite simuler un flux entre deux équipements du réseau, on détermine au plus une fois le chemin pour acheminer les paquets du flux tandis qu'avec le procédé de l'état de la technique, il est nécessaire de calculer ce chemin pour chaque paquet. Il en résulte un 5 important gain supplémentaire dans les ressources de calcul nécessaires à la mise en oeuvre du procédé de simulation. - Au cours de l'étape de simulation d'acheminement, on détermineune information relative à au moins un paquet, parmi la quantité desdits paquets, perdu au cours de l'acheminement. Par exemple, on détermine un nombre de paquets perdus, parmi la 10 quantité de paquets, au cours de l'acheminement du premier noeud jusqu'au deuxième noeud. On peut également déterminer une proportion de paquets perdus. Cela permet de simuler plus précisément un réseau de type TCP/IP qui est configuré pour gérer les pertes de paquets. - On simule au moins deux flux distincts de paquets acheminés sur le réseau, les 15 flux étant agencés de telle façon qu'il existe au moins un paquet de chaque flux présent, à ladite date, au premier noeud et destiné à être acheminé jusqu'au deuxième noeud. Un flux de paquets correspond à un échange de paquets entre deux équipements du réseau, généralement entre équipements situés sur des terminaisons du réseau. Dans le cas d'un grand réseau, tel que le réseau Internet, les paquets du flux transitent généralement par 20 un sous-réseau du réseau Internet appelé réseau fédérateur Internet ou backbone en anglais. Les noeuds du réseau fédérateur sont qualifiés de noeuds de coeur. Il est fréquent que plusieurs flux distincts soient routés au moins localement entre des mêmes premier et deuxième noeuds de coeur, ce qui permet de mettre en oeuvre l'invention en simulant de manière globale l'acheminement des paquets de ces flux dans le réseau fédérateur. 25 - On conserve une information relative à la répartition des paquets de chaque flux dans la quantité de paquets. Sur le réseau fédérateur, les paquets des flux sont traités de manière globale. Pour pouvoir les répartir entre flux lorsqu'ils sortent du réseau fédérateur par le deuxième noeud de coeur, il est donc important de conserver une information relative à la répartition des paquets de chaque flux dans la quantité de paquets, lors de 30 leur entrée dans le réseau fédérateur, par le premier noeud de coeur. L'invention a également pour objet un programme d'ordinateur apte à commander la mise en oeuvre des étapes d'un procédé tel que précédemment défini. L'invention a également pour objet un support d'enregistrement de données, comprenant un programme d'ordinateur tel que précédemment défini. 35 L'invention a également pour objet un dispositif de simulation de l'état d'un réseau de télécommunications, apte à simuler la présence, à une même date et à un même 2907291 -4- premier noeud du réseau, de paquets de données et l'acheminement des paquets jusqu'à un même deuxième noeud du réseau, le dispositif étant agencé pour simuler de façon globale l'acheminement d'au moins une quantité, au moins égale à deux, desdits paquets. L'invention sera mieux comprise à la lecture de la description qui va suivre, donnée 5 uniquement à titre d'exemple et faite en se référant aux dessins annexés dans lesquels : - la figure 1 est un schéma d'un réseau de télécommunication dont on souhaite simuler l'état à l'aide du procédé de l'invention, - le figure 2 est un schéma identique à celui de la figure 1, sur lequel sont symbolisés des paquets de donnés dont l'acheminement dans le réseau 10 est simulé, et - la figure 3 est un schéma d'un noeud de coeur et de sa file d'attente. On a représenté sur la figure 1 un réseau de télécommunication 10, tel que le réseau Internet, et dont on souhaite simuler l'état au cours du temps. Le réseau Internet 10 comprend un sous-réseau 12 de type réseau fédérateur Internet, également appelé 15 backbone en anglais. Le réseau 10 comprend un ensemble d'équipements formant des noeuds du réseau, reliés entre eux. Le réseau fédérateur 12 comprend une pluralité de noeuds de coeur NC1, NO2, NC3 et NC4 et le reste du réseau comprend une pluralité de noeuds terminaux Ti à T7. Chaque noeud terminal n'est relié qu'à un noeud de coeur. Les noeuds de coeurs sont 20 par exemples des routeurs, des switchs, des DSLAM ou des stations de base et les noeuds terminaux sont des équipements d'accès au réseau comme par exemple des serveurs, des terminaux d'accès Ethernet, des lignes DSL, des points d'accès Wifi ou des téléphones mobiles. Dans l'exemple représenté, les noeuds terminaux Ti, T2 et T3 sont reliés au noeud de 25 coeur NC1, le noeud terminal T4 est relié au noeud de coeur NC2 et les noeuds terminaux T5, T6 et T, sont reliés au noeud de coeur NC4. Dans le réseau 10, les noeuds terminaux s'échangent entre eux des données sous forme de paquets. Un échange entre deux noeuds terminaux est appelé flux de données. Par exemple, le noeud terminal Ti échange avec le noeud terminal T6 un flux f,. 30 Etant donné qu'un noeud terminal n'est relié qu'à un noeud de coeur, chaque flux entre noeuds terminaux peut être caractérisé par le couple de noeuds de coeur par lesquels il entre dans le réseau fédérateur et en sort. On désigne alors par classe de flux, l'ensemble des flux qui entrent et sortent dans le réseau fédérateur 12 par un même couple de noeuds de coeur. Ainsi, la classe de flux FC(NC1, NC4) correspondant aux 35 noeuds de coeurs NC1 et NC4, comprend les flux f2 et f3 et la classe de flux FC(NC2, NC4) correspondant aux noeuds de coeurs NC2 et NC4, comprend le flux f4. 2907291 -5- Pour être acheminés d'un noeud terminal à un autre, les paquets transitent par différents noeuds du réseau. Pour simuler l'état du réseau au cours du temps, on simule l'acheminement dans le réseau de chaque paquet en fonction de l'état des noeuds du réseau, en déterminant notamment les dates auxquelles le paquet transite par les noeuds 5 du réseau. Ainsi, à chaque instant, on peut déterminer la répartition des paquets dans le réseau, et notamment l'état d'encombrement des noeuds du réseau. Pour simplifier cette simulation, le temps de simulation est discrétisé en une succession de dates et on simule l'acheminement des paquets dans le réseau à chaque date. Pour déterminer le nombre de paquets à acheminer par flux, on simule au préalable 10 l'état du réseau à une date initiale, notamment l'état des paramètres des couches application et transport du réseau, puis on détermine les informations à transmettre sur le réseau par l'intermédiaire de flux de paquets. On a représenté sur la figure 2, les flux f, à f3 émis par les noeuds terminaux T, à T3, lors de leur entrée dans le noeud de coeur NC1 et le flux f4 émis par le noeud terminal T4 15 lors de son entrée dans le noeud de coeur NO2. Ces flux sont symbolisés par un diagramme temporel en bâtons représentant le nombre de paquets émis à chaque date. On décrira par la suite le procédé de simulation de l'invention dans le cas de l'acheminement des paquets des flux f, à f4. Bien entendu, on procède de même pour tous les flux échangés dans le réseau. 20 Selon le procédé, au cours d'une première étape, on simule la présence, à une première date et au noeud de coeur NC1, des paquets de données des flux f, à f3 de la même classe de flux FC(NC1, NC4) et dont on souhaite simuler l'acheminement jusqu'au noeud de coeur NC4. Ensuite, on vérifie si, au cours de la simulation, on a déjà déterminé un chemin dans 25 le réseau fédérateur 12 pour les flux de la classe FC(NC1, NC4). Si c'est le cas, on utilise ce chemin pour acheminer les paquets des flux f, à f3. En revanche, si ce n'est pas le cas, on détermine un chemin pour acheminer les flux de la classe FC(NC1, NC4). Dans l'exemple représenté, on considère que ce chemin comprend la suite de noeuds de coeurs suivante : NC1, NO3, NC4. Ce chemin sera alors utilisé par la suite pour acheminer tous 30 les paquets des flux de la classe de flux FC(NC1, NC4). Puis, lors d'une étape suivante, on agrège tous les paquets des flux de la classe FC(NC1, NC4) présents au noeud de coeur NC1, comme représenté sur la figure 2. On détermine alors une quantité de paquets de la classe FC(NC1, NC4) présents au noeud de coeur NC1 que l'on souhaite acheminer selon le chemin déterminé. Cette quantité de 35 paquet est également appelée agrégat. Un fois que les paquets des différents flux sont agrégés, il n'est plus possible de les distinguer en fonction des flux dont ils proviennent. 2907291 -6- C'est pourquoi on conserve au préalable une information relative à la répartition des paquets de chaque flux dans la quantité de paquets. Au cours d'une étape suivante, on simule de façon globale l'acheminement de la quantité de paquets de la classe FC(NC1, NC4) initialement présents au noeud de coeur 5 NC1, jusqu'au noeud suivant du chemin, c'est-à-dire jusqu'au noeud NC3. On détermine notamment la date d'arrivée de la quantité de paquets au noeud NC3. On caractérise cette quantité de paquets acheminés par le nombre de paquets à chaque date. On détermine également, parmi la quantité desdits paquets, une information relative à au moins un paquet perdu au cours de l'acheminement, par exemple le nombre de paquets perdus. 10 Parallèlement à ces étapes, on simule de la même façon l'acheminement des paquets du flux f4 émis par le noeud terminal T4. Ce flux f4 est l'unique flux de la classe de flux FC(NC2, NC4) dont le chemin déterminé comprend la suite de noeuds de coeurs suivante : NC2, NC3, NC4. Cette simulation permet de déterminer la date d'arrivée des flux de la classe FC(NC2, NC4) au noeud NC3. 15 Etant donné que des agrégats de paquets des classes de flux FC(NC1, NC4) et FC(NC2, NC4) sont présent à une même date au même noeud NC3, et que l'on souhaite simuler leur acheminement jusqu'au noeud NC4, on peut également, au cours d'une étape suivante, agréger tous les paquets des agrégats des classes de flux FC(NC1, NC4) et FC(NC2, NC4) présents au noeud de coeur NC3, comme représenté sur la figure 2. On 20 conserve néanmoins des informations pour distinguer les paquets des agrégats des deux classes. Pour désigner l'ensemble des paquets des agrégats de plusieurs classes, on parle de super-agrégat. Ensuite, au cours d'une étape suivante, on simule de façon globale l'acheminement du super-agrégat jusqu'au noeud NC4. 25 Une fois que le super agrégat est présent au noeud NC4 de sortie du réseau fédérateur 12, il est nécessaire de simuler l'acheminement des paquets le composant vers les différents noeuds terminaux de destination. La distinction entre agrégats de classes de flux distinctes est possible du fait que l'on a conservé des informations permettant de les distinguer. Ainsi, au cours d'une étape suivante, on répartit les paquets 30 du super-agrégat entre agrégats de classes de flux. Ensuite, pour chaque classe de flux, il faut répartir les paquets agrégés par flux pour connaître les noeuds terminaux de destination. On utilise alors l'information relative à la répartition des paquets de chaque flux dans l'agrégat que l'on avait introduite lors de l'étape d'agrégation. On simule alors l'acheminement des paquets jusqu'aux noeuds 35 terminaux de destination. 2907291 -7- Puis, en fonction de nombre de paquets reçus et perdus, on détermine les informations à transmettre sur le réseau par l'intermédiaire de flux de paquets aux dates suivantes, par exemple les acquittements à envoyer en fonction des paquets reçus et perdus. 5 Les noeuds de coeurs du réseau ont une capacité de traitement des paquets reçus limitée. Pour simuler cela, on met en place un modèle de gestion des files d'attente, par exemple celui représenté sur la figure 3 et qui est de type PAPS, Premier Arrivé, Premier Servi. D'autres modèles de gestion de files d'attente peuvent être utilisés. Sur cet exemple la capacité D de traitement du noeud est de quatre paquets par 10 date. De plus, la mémoire tampon de la file d'attente du noeud a une capacité B limitée à douze paquets. A chaque date, un nouvel agrégat pour chaque classe de flux est acheminé jusqu'au noeud. On note A le nombre total de paquets de ces agrégats, q le nombre de paquets dans la file d'attente avant l'arrivée des nouveaux paquets et q' le nombre de paquets 15 dans la file d'attente après l'arrivée des nouveaux paquets. L'équation suivante est vérifiée : q'=q+A. Après l'arrivée des nouveaux paquets, on vérifie tout d'abord le niveau d'occupation de la mémoire tampon du noeud. Le nombre de paquets perdus est limité par Max(q'-B4O) dans le cas où tous les paquets arrivent simultanément et Max(q'-B-D, 0) dans le cas où 20 les paquets arrivent au noeud de coeur de manière régulièrement répartie. On rappelle que Max(a,b) désigne la plus grande valeur entre a et b. Le nombre paquets perdus dépend donc de la loi d'arrivée des paquets. Dans notre cas, on considère Max(q'-B-D,O), ou de façon plus générale une distribution aléatoire entre les deux valeurs Max(q'-B, 0) et Max(q'-B-D, 0). Les paquets 25 perdus sont alors répartis parmi les classes de flux avec une probabilité proportionnelle au nombre de paquets des derniers agrégats arrivés. D'autres modèles de répartition peuvent également être utilisés. Notamment, on peut introduire une fonction de corrélation pour le tirage successif des classes de flux auxquelles on attribue la perte d'un paquet, en fonction des tirages précédents. 30 Alors, les plus anciens agrégats sont traités en premier. Les paquets sont supprimés des agrégats et rassemblés dans des agrégats de sortie. Sur l'exemple représenté sur la figure 3, on traite à l'instant t=2 tous les paquets arrivés aux instants t=-1 et t=0, c'est-à-dire trois paquets, et on traite également un quatrième paquet choisi aléatoirement parmi les paquets arrivés à l'instant t=1. 35 L'invention ne se limite pas au mode de réalisation qui vient d'être décrit. 2907291 -8- En effet, selon une première variante, on simule de façon globale l'acheminement de paquets qui sont échangés entre deux mêmes noeuds terminaux, c'est-à-dire des paquets d'un même flux. Selon une autre variante, les paquets sont agrégés localement entre des noeuds de 5 coeurs du réseau qui ne sont pas des noeuds auxquels sont directement liés des noeuds terminaux. Cela permet de déterminer de façon globale l'acheminement de paquets ayant un sous-chemin commun, le long de ce sous-chemin commun. Pour plus de précision, on peut, selon une autre variante, conserver dans les agrégats une liste des paquets agrégés, ainsi que leur numéro de séquence. 10 Pour prendre en compte un routage qui évolue dans le temps, on peut, selon une autre variante, mettre à jour régulièrement les chemins prédéterminés, en fonction des mécanismes de routage du réseau simulé. Pour prendre en compte un routage multi-chemin ou des mécanismes de répartition de charge, on peut, selon une autre variante, utiliser plusieurs chemins prédéterminés 15 pour un même couple de noeuds de coeur et router les paquets pour ce même couple de noeuds de coeur, suivant l'un ou l'autre de ces chemins, en fonction d'un ou plusieurs critères sur ces paquets, par exemple le type d'application, l'adresse IP source, l'adresse IP destination, le port source et/ou le port destination. Enfin, selon d'autres variantes, on peut adapter la simulation à des paquets de 20 tailles différentes et/ou séparer les classes de flux par classes de service. REVENDICATIONS 1. Procédé de simulation de l'état d'un réseau de télécommunications (10), caractérisé en ce qu'il comprend les étapes consistant à : - simuler la présence, à une même date et à un même premier noeud (NC1, NC3) du réseau, de paquets de données dont on souhaite simuler l'acheminement jusqu'à un même deuxième noeud (NC4) du réseau ; et - simuler de façon globale l'acheminement d'au moins une quantité, au moins égale à deux, desdits paquets. 2. Procédé de simulation selon la revendication précédente, dans lequel durant l'étape de simulation d'acheminement, on simule l'acheminement de la quantité de paquets selon un chemin prédéterminé. 3. Procédé de simulation selon l'une quelconque des revendications précédentes, dans lequel, lors de la mise en oeuvre de l'étape d'acheminement : - si un chemin pour acheminer un paquet depuis le premier noeud (NC1, NC3) jusqu'au deuxième noeud (NC4) a déjà été déterminé antérieurement à la mise en oeuvre de cette étape, on utilise ce chemin prédéterminé pour simuler l'acheminement de la quantité de paquets, et -sinon, on détermine ce chemin et on l'utilise pour simuler l'acheminement de la quantité de paquets. 4. Procédé de simulation selon l'une quelconque des revendications précédentes, dans lequel, au cours de l'étape de simulation d'acheminement, on détermine une information relative à au moins un paquet, parmi la quantité desdits paquets, perdu au cours de l'acheminement. 5. Procédé de simulation selon l'une quelconque des revendications précédentes, dans lequel on simule au moins deux flux distincts (f,, f2, f3) de paquets acheminés sur le réseau, les flux étant agencés de telle façon qu'il existe au moins un paquet de chaque flux (f,, f2, f3) présent, à ladite date, au premier noeud (NC1) et destiné à être acheminé jusqu'au deuxième noeud (NC4). 6. Procédé de simulation selon la revendication précédente, dans lequel on conserve une information relative à la répartition des paquets de chaque flux (f,, f2, f3) dans la quantité de paquets. 7. Programme d'ordinateur caractérisé en ce qu'il est apte à commander la mise en oeuvre des étapes d'un procédé selon l'une quelconque des revendications précédentes. 8. Support d'enregistrement de données, caractérisé en ce qu'il comprend un programme selon la revendication précédente. 2907291 -10- 9. Dispositif de simulation de l'état d'un réseau de télécommunications, caractérisé en ce qu'il est apte à simuler la présence, à une même date et à un même premier noeud (NC1) du réseau, de paquets de données et l'acheminement, de façon globale, d'au moins une quantité, au moins égale à deux, desdits paquets jusqu'à un même deuxième noeud 5 (NC4) du réseau.