Brevet FR2984657A1 — publié le 20130621

SYSTEME D'EMISSION DE FLOTS DE DONNEES CONCURRENTS SUR UN RESEAU Domaine technique de l'invention L'invention est relative aux réseaux sur puce et plus particulièrement à un système 5 d'ordonnancement chargé d'émettre des flots de données sur le réseau au niveau d'un routeur. État de la technique Il existe de nombreux algorithmes de canalisation de trafic visant à améliorer l'utilisation de la bande passante et la qualité de service sur un réseau. Dans le contexte 10 des réseaux de communication, les travaux initiés par Cruz [« A Calculus for Network Delay », Part I: Network Elements in Isolation and part II: Network Analysis, R.L. Cruz, IEEE Transactions on Information Theory, vol 37, n°1, Jan 1991] puis par Stiliadis [« Latency-Rate Servers: A General Model for Analysis of Traffic Scheduling Algorithms », Dimitrios Stiliadis et al., IEEE/ACM TRANSACTIONS ON 15 NETWORKING, VOL. 6, NO. 5, OCTOBER 1998] ont construit une théorie qui relie les notion de taux de service, la latence pire cas d'un canal de communication partagé, et les taux d'utilisation des ressources de stockage sur les éléments du réseau. Cette théorie a servi de fondement pour différents systèmes de gestion de trafic. La méthode la plus fréquente au niveau des routeurs est la méthode d'attente équitable 20 pondérée décrite dans « Réseaux 4eme édition » de Andrew Tannenbaum en page 441. Une alternative mieux adaptée aux réseaux sur puce est d'injecter le trafic en utilisant le mécanisme de seau percé (« leaky bucket »), décrit en page 434 et suivantes dans « Réseaux 4eme édition » de Andrew Tannenbaum. Dans tous les cas, cela revient à associer un débit moyen p, à une « session » S sur un 25 lien réseau. A chaque session d'émission de données S, (i = 1, 2,... n), par exemple un canal, une connexion, ou un flot, on alloue une mémoire tampon, ou file. Les contenus de ces files sont transférés séquentiellement sur un lien réseau L au débit nominal r du lien. Un régulateur de débit opère sur chaque file, de sorte à limiter le débit moyen de la 30 session correspondante Si à une valeur pi Pour comprendre de façon globale le fonctionnement, on peut imaginer que les contenus des files sont vidés en parallèle dans le réseau à des débits pi respectifs. En réalité, les files sont scrutées de manière séquentielle, et la régulation de débit est opérée en scrutant moins fréquemment les files associées aux débits inférieurs, en cherchant un effet de moyenne sur plusieurs cycles de scrutation. Dans ces conditions, Stiliadis et al. démontrent que la latence entre l'instant de lecture d'un premier mot d'un paquet dans une file et l'envoi du dernier mot du paquet sur le lien L est bornée pour certains types d'algorithmes d'ordonnancement. Dans le cas de l'attente équitable pondérée ou WFQ (de l'anglais « Weighted Fair-Queuing »), cette latence est bornée par Spi/pi+ Spmax/r, où Spi est la taille de paquet maximale de la session i, et Spm la taille de paquet maximale sur l'ensemble des sessions en cours. Cette composante de latence est indépendante de la taille des files. Or il est connu que, dans les systèmes utilisant plusieurs files pour canaliser plusieurs flux sur un lien partagé, la taille des files introduit une autre composante de latence, entre l'écriture d'une donnée dans une file et la lecture de cette même donnée pour l'émettre sur le réseau. Résumé de l'invention On souhaite disposer d'un système d'émission de plusieurs flots de données permettant de réduire la latence totale entre l'arrivée des données dans une file et l'émission de ces 20 mêmes données sur le réseau. On tend à satisfaire ce besoin grâce à un système d'émission de flots de données concurrents sur un réseau, comprenant une mémoire organisée pour recevoir les données en cours de production des flots ; plusieurs files affectées respectivement aux flots de données, organisées pour recevoir les données sous forme d'unités de 25 transmission atomiques ; un régulateur de débit configuré pour scruter les files en séquence et, si la file scrutée contient une unité de transmission complète, l'émettre sur le réseau au débit nominal du réseau ; un séquenceur configuré pour scruter les files de manière circulaire et activer un signal de requête de données lorsque l'état de remplissage de la file scrutée n'a pas atteint un seuil commun à toutes les files, lequel 30 seuil est supérieur à la taille maximale des unités de transmission ; et un circuit de gestion de transferts mémoire configuré pour recevoir le signal de requête de données et y répondre en transférant des données de la mémoire vers la file correspondante à la vitesse maximale du système, jusqu'à atteindre le seuil commun. On tend également à satisfaire ce besoin grâce à un système d'émission de flots de données concurrents sur un réseau, comprenant une mémoire contenant des données en cours de production des flots ; plusieurs files affectées respectivement aux flots de données, organisées pour recevoir les données sous forme d'unités de transmission atomiques ; un régulateur de débit configuré pour scruter les files en séquence et, si la file scrutée contient une unité de transmission complète, l'émettre sur le réseau au débit nominal du réseau ; un circuit de gestion de files configuré pour remplir individuellement chaque file à partir des données contenues dans la mémoire, à la vitesse nominale du système, jusqu'à atteindre un seuil commun à toutes les files ; un circuit de configuration paramétrable pour fournir le seuil commun des files ; et un processeur programmé pour produire les flots et gérer leur affectation aux files, et connecté au circuit de configuration pour ajuster dynamiquement le seuil en fonction de la taille d'unité de transmission maximale utilisée par les flots en cours d'émission. Selon un mode de réalisation, le seuil commun des files est inférieur au double de la 15 taille maximale des unités de transmission. Selon un mode de réalisation, le système comprend une interface réseau incluant les files, le régulateur de débit, et le séquenceur ; un processeur programmé pour produire les données des flots, gérer l'affectation des files aux flots, et déterminer les débits moyens des flots ; un bus système interconnectant le processeur, la mémoire et le circuit 20 de gestion de transferts mémoire ; et un circuit de calcul du seuil commun à partir des contenus de deux registres programmables par le processeur, l'un contenant la taille maximale de l'unité de transmission, et l'autre un coefficient multiplicatif compris entre 1 et 2. Selon un mode de réalisation, le régulateur de débit est configuré pour ajuster le débit 25 moyen d'un flot en bornant le nombre d'unités de transmission émises sur le réseau dans une fenêtre temporelle consécutive. Description sommaire des dessins Des modes de réalisation seront exposés dans la description suivante, faite à titre non limitatif en relation avec les figures jointes parmi lesquelles : 30 - la figure 1 représente schématiquement un système d'émission de plusieurs flots concurrents sur un lien réseau partagé, tel qu'il pourrait être réalisé de manière classique avec les enseignements précédemment évoqués ; - la figure 2 est un graphe illustrant le fonctionnement du système de la figure 1 ; - la figure 3 représente schématiquement un mode de réalisation optimisé d'un système d'émission de plusieurs flots concurrents sur un ou plusieurs liens réseau partagés ; - la figure 4 est un graphe illustrant le fonctionnement du système de la figure 3 ; - la figure 5 est un graphe illustrant des évolutions de remplissage d'une file du système de la figure 3 ; - la figure 6 est un graphe illustrant l'évolution de l'efficacité de l'utilisation moyenne de la bande passante du système en fonction de la taille effective des files ; et - la figure 7 représente un mode de réalisation de système d'émission permettant un réglage dynamique du seuil de signalisation de file pleine. Description d'un mode de réalisation préféré de l'invention La figure 1 représente schématiquement un exemple de système d'émission de plusieurs 15 flots concurrents sur un lien réseau partagé L, tel qu'il serait réalisé en mettant en oeuvre de manière traditionnelle les enseignements de Cruz, Stiliadis et Tannenbaum, évoqués en introduction. Le système comprend un processeur CPU, une mémoire MEM, et un circuit d'accès mémoire direct DMA, interconnectés par un bus système B. Une interface réseau NI est 20 connectée pour envoyer sur le lien réseau L des données fournies par le circuit DMA. Cette interface réseau comprend plusieurs files 10 agencées, par exemple, pour mettre en oeuvre une attente équitable pondérée (WFQ). Le remplissage des files est géré par un circuit d'arbitrage ARB, tandis que le vidage des files sur le lien réseau L est géré par un circuit de régulation de débit REGL. 25 Le circuit DMA est conçu pour émettre un signal de requête REQ vers l'interface réseau NI lorsque des données sont prêtes à émettre. Le circuit DMA est de préférence muni d'une mémoire cache servant à stocker ces données pendant l'émission, de sorte que le bus système soit libéré. Le circuit d'arbitrage de l'interface réseau est conçu pour traiter le signal de requête et renvoyer un signal d'acquittement ACK vers le circuit DMA. Alors que les transferts de données de la mémoire vers le circuit DMA et vers les files 10 peuvent être effectués par mots de la largeur du bus système, par salves de taille quelconque, les transferts des files 10 vers le lien réseau L doivent être compatibles avec le type de réseau. Du point de vue du réseau, les données dans les files sont 5 organisées en « unités de transmission », par exemple des « paquets » tels qu'utilisés dans les réseaux de type ATM, et le plus souvent dans les réseaux sur puce, ou des « trames » telles qu'utilisées dans les réseaux de type Ethernet. Comme la présente description est faite dans le cadre d'un réseau sur puce, on parlera ci-après plutôt de « paquets », sachant que les principes décrits s'appliquent de manière plus générale à 10 des unités de transmission. Un paquet est le plus souvent « atomique », c'est-à-dire qu'on cherche à transmettre les mots qui le constituent de manière contiguë sur le lien réseau L, sans les mélanger à des mots appartenant à des flots concurrents. Ce n'est que lorsqu'un paquet complet a été émis sur le lien qu'on pourra émettre un nouveau paquet. En outre, ce n'est que quand 15 une file contient un paquet complet que le régulateur de débit REGL pourra décider de l'émettre. La figure 2 est un graphe illustrant plus en détail le déroulement d'une émission d'un lot de données dans le système de la figure 1. Il représente sur des lignes temporelles verticales les interactions entre les composants du système. Par « lot de données » on 20 entend une partie sécable d'un flot de données normalement produit en continu. Un flot de données peut correspondre à la transmission d'une vidéo, alors qu'un lot correspond, par exemple, à une image ou à une ligne d'image. En TO le processeur CPU, après avoir produit un lot de données dans un emplacement de la mémoire MEM, initialise le circuit DMA avec l'adresse source du lot et l'adresse 25 destination, à laquelle est associée une des files 10 de l'interface réseau. En Ti, le circuit DMA transfère le lot de données de la mémoire MEM vers sa mémoire cache interne, et libère le bus système. En T2, le circuit DMA émet une requête d'accès REQ vers l'interface réseau NI. Cette requête identifie la file 10 dans laquelle les données doivent être écrites. 30 En T3, l'interface réseau acquitte la requête par un signal ACK, signifiant que la file 10 sélectionnée dispose de place pour recevoir des données. En T4, le circuit DMA réagit à l'acquittement par la transmission de données de sa mémoire cache vers l'interface réseau NI, où elles sont écrites dans la file 10 correspondante. En T5, l'interface réseau détecte l'état plein de la file et signale au circuit DMA la fin 5 du transfert. En T6, le circuit DMA, ayant encore des données à transmettre, émet une nouvelle requête pour demander un nouveau transfert, et le cycle recommence. Le vidage des files 10 dans le réseau s'effectue de manière décorrélée de l'arbitrage des requêtes, selon un mécanisme de régulation de débit qui ne peut traiter une file que si 10 elle contient un paquet complet. Ce protocole de transfert fonctionne convenablement lorsque les producteurs de données sollicitent le réseau de manière ponctuelle, en d'autres termes lorsqu'un producteur n'occupe pas la bande passante de son lien réseau de manière soutenue. C'est le cas dans les réseaux de communication. 15 Dans un réseau sur puce, on cherche à occuper la bande passante des liens réseau au maximum et les producteurs sont pour cela conçus pour saturer leurs liens réseau de manière soutenue. Comme on l'a précédemment indiqué, un producteur peut émettre plusieurs flots concurrents sur son lien réseau. Cela se traduit en figure 2 par le transfert de plusieurs 20 lots de données correspondants dans la mémoire cache du circuit DMA et par la présentation de plusieurs requêtes concurrentes à l'interface réseau NI. Une seule requête est acquittée à la fois, à la suite d'un arbitrage qui prend également en compte la place disponible dans les files 10. Dans le cas d'une phase soutenue de remplissage des files 10 survenant pour répondre à 25 de nombreuses requêtes instantes, les délais d'arbitrage peuvent prendre une proportion non négligeable sur la bande passante disponible. Dans ce contexte, il est possible que la file de destination reste vide pendant un intervalle de temps et donc « passe son tour » pour des opportunités d'accès au réseau, ce qui a pour effet de diminuer la bande passante effectivement utilisée. D'après la 30 théorie des files d'attente, la probabilité que la file soit vide est d'autant moins élevée que la file est grande : c'est pourquoi on surdimensionne souvent la taille de cette file. Une autre solution pour réduire cette probabilité est d'augmenter la fréquence des requêtes du processus producteur. Ces deux solutions sont coûteuses en efficacité dans le contexte d'un réseau sur puce, c'est pourquoi on propose ici un système alternatif d'accès au réseau. La figure 3 représente schématiquement un mode de réalisation d'un tel système. Ce mode de réalisation est décrit dans le cadre d'un réseau sur puce de structure matricielle torique, tel que décrit dans la demande de brevet US2011-0026400. Chaque noeud du réseau est formé d'un routeur à cinq voies bidirectionnelles, comprenant une voie locale attribuée à au circuit DMA et quatre voies (nord LN, sud LS, est LE, et ouest LW) reliées respectivement aux quatre routeurs adjacents de la matrice. On considère ici la voie locale comme le point d'entrée du réseau. Les paquets pénétrant par cette voie locale peuvent être aiguillés, selon leur destination dans le réseau, par l'une quelconque des quatre autres voies, que l'on considèrera comme des liens réseau indépendants. Ainsi, au lieu d'être émis dans le réseau par un seul lien L, comme à la figure 1, les paquets peuvent ici être émis par l'un des quatre liens LN, LS, LE et LW. Cette multitude de liens réseau n'affecte pas les principes décrits ici, qui peuvent s'appliquer à un lien unique. Un flot est en principe associé à un seul lien réseau, qui peut être considéré comme le lien unique de la figure 1. Une différence existe au niveau de la bande passante globale du réseau lorsque plusieurs flots concurrents sont affectés à des liens différents : ces flots peuvent être émis en parallèle par le régulateur de débit, de sorte que la bande passante globale est temporairement un multiple de la bande passante d'un lien isolé. Le système de la figure 3 diffère de celui de la figure 1 essentiellement par le protocole de communication mis en oeuvre entre le circuit DMA et l'interface réseau NI. Le circuit DMA n'émet plus de requêtes vers l'interface réseau pour transmettre des données, mais attend que l'interface réseau NI demande des données par l'activation d'un signal de sélection SELi identifiant la file 10 à servir. Le signal SELi est produit par un séquenceur SEQ qui remplace le circuit d'arbitrage de requêtes de la figure 1. Le séquenceur SEQ est conçu simplement pour scruter de manière circulaire les files 10 30 et activer le signal de sélection SELi dès que la file scrutée dispose de place pour recevoir des données. Alors le séquenceur s'arrête, attend que la file soit remplie par le circuit DMA, désactive le signal SELi et passe à la file suivante. La figure 4 illustre ce fonctionnement plus en détail. En TO, le système est inactif et toutes les files 10 sont vides. Le séquenceur SEQ active le signal de sélection SEL1 de la première file et attend des données. En Ti, le processeur CPU a produit plusieurs lots de données dans la mémoire MEM. Il initialise l'interface réseau NI pour associer des files respectives 10 à ces lots, par 5 exemple en écrivant ces informations dans des registres du séquenceur SEQ. En T2, le processeur initialise le circuit DMA pour transférer les multiples lots dans les files correspondantes. En T3, le circuit DMA lit les lots de données dans sa mémoire cache. Pratiquement simultanément, comme le signal SEL1 est actif, le circuit DMA commence à transférer 10 les données du premier lot (Txl) vers l'interface réseau NI, où elles sont écrites dans la première file 10. En T4, la première file est pleine. Le séquenceur désactive le signal SEL1 et active le signal SEL2 identifiant la deuxième file à remplir. En T5, le circuit DMA transfère des données du deuxième lot (Tx2) vers l'interface 15 réseau, où elles sont écrites dans la deuxième file 10, jusqu'à ce que le signal SEL2 soit désactivé et un nouveau signal SEL3 activé pour le transfert du lot suivant. Avec ce système, on traite les différents transferts de flots de manière séquentielle, sans besoin d'arbitrage pour décider du flot à traiter. La bande passante entre le circuit DMA et les files peut être utilisée à 100 %. 20 On cherche maintenant à réduire la latence introduite par les files 10. Pour cela, la taille des files doit être minimisée. La taille minimale est la taille de paquet Sp, puisque le régulateur de débit ne traite une file que si elle contient un paquet complet. Il reste à établir si cette taille minimale est satisfaisante ou, sinon, quelle taille minimale il est souhaitable de prendre. 25 La figure 5 est un graphe illustrant un exemple d'évolution du remplissage d'une file 10 en cours de fonctionnement. On prend l'exemple d'un débit de remplissage 7C deux fois supérieur au débit nominal r du réseau. Le débit 7C est le débit nominal de transmission du circuit DMA, et il est en règle générale supérieur au débit nominal d'un lien réseau. La taille de paquet est notée Sp et la taille de la file est notée a. 30 A un instant tO, la file est sélectionnée pour être remplie par le séquenceur SEQ. Son taux de remplissage résiduel vaut al A un instant tl, le taux remplissage de la file atteint Sp. La file contient un paquet complet, et son vidage dans le réseau peut commencer. Si le régulateur de débit REGL sélectionne effectivement cette file à tl, la file est vidée au débit r. La file continue à se remplir plus lentement, à un débit apparent de n-r. A un instant t2, le taux de remplissage de la file atteint sa limite a. Le remplissage s'arrête, mais le vidage continue. La file se vide au débit r. Le séquenceur SEQ sélectionne la file suivante pour le remplissage. A un instant t3, on a émis un paquet complet sur le réseau. La file atteint un taux de remplissage résiduel a2 Les contenus des registres 12 et 14 sont multipliés en 16 pour produire le seuil a. Ce seuil est utilisé par des comparateurs 30 associés respectivement aux files 10. Chaque comparateur 30 active un signal Full à l'attention du séquenceur SEQ lorsque le taux de remplissage de la file 10 correspondante atteint la valeur a. A l'activation d'un signal Full, le séquenceur sélectionne la file suivante pour le remplissage. Bien qu'on préfèrera utiliser le seuil réglable dans le système de la figure 3, les bénéfices que cette solution apporte sont indépendants du système. Ainsi, on pourra l'utiliser dans le système de la figure 1 ou tout autre système. REVENDICATIONS1. Système d'émission de flots de données concurrents sur un réseau, comprenant : - une mémoire (MEM) organisée pour recevoir les données en cours de production des flots ; - plusieurs files (10) affectées respectivement aux flots de données, organisées pour recevoir les données sous forme d'unités de transmission atomiques ; - un régulateur de débit (REGL) configuré pour scruter les files en séquence et, si la file scrutée contient une unité de transmission complète, l'émettre sur le réseau au débit nominal du réseau ; - un séquenceur (SEQ) configuré pour scruter les files de manière circulaire et activer un signal de requête de données (SELi) lorsque l'état de remplissage de la file scrutée n'a pas atteint un seuil (a) commun à toutes les files, lequel seuil est supérieur à la taille maximale des unités de transmission ; et - un circuit de gestion de transferts mémoire (DMA) configuré pour recevoir le signal de requête de données et y répondre en transférant des données de la mémoire vers la file correspondante à la vitesse maximale du système, jusqu'à atteindre le seuil commun. 2. Système selon la revendication 1, dans lequel le seuil commun des files est inférieur au double de la taille maximale des unités de transmission. 3. Système selon la revendication 2, dans lequel le seuil commun est réglable dynamiquement pour tenir compte des tailles d'unité de transmission effectivement utilisées par les flots en cours d'émission. 4. Système selon la revendication 2, comprenant : - une interface réseau (NI) incluant les files, le régulateur de débit, et le séquenceur ; - un processeur (CPU) programmé pour produire les données des flots, gérer l'affectation des files aux flots, et déterminer les débits moyens des flots ;- un bus système (B) interconnectant le processeur, la mémoire et le circuit de gestion de transferts mémoire (DMA) ; et - un circuit de calcul du seuil commun à partir des contenus de deux registres programmables par le processeur, l'un contenant la taille maximale de l'unité de transmission (Sp), et l'autre un coefficient multiplicatif (K) compris entre 1 et 2. 5. Système selon la revendication 1, dans lequel le régulateur de débit est configuré pour ajuster le débit moyen d'un flot en bornant le nombre d'unités de transmission émises sur le réseau dans une fenêtre temporelle consécutive.