Brevet FR3089738A1 — publié le 20200612

Description Titre de l'invention : Procédé de mesure d'un délai de transmission avec maîtrise de degrés de contention appliqués à une trame de données Domaine technique 100011 Le domaine de l'invention est celui de la mesure d'un temps de transmission d'une trame de données depuis un noeud source jusqu'à un noeud destinataire d'un réseau informatique, et plus particulièrement celui de la mesure d'un délai de transmission pire cas de bout en bout du chemin (délai dit WCTT pour « Worst-Case Traversai Time »). Technique antérieure [0002] Dans une architecture informatique distribuée, différentes applications s'échangent des informations à travers un réseau. Un comportement correct de ces échanges se doit d'être garanti ce qui signifie du point de vue du réseau que lorsqu'une information y est transmise, elle doit arriver à destination dans les délais. Dans un contexte temps réel strict, un résultat juste mais hors-délai est un résultat inutilisable. Il s'avère donc nécessaire d'apporter une garantie relative à un temps de transmission de bout en bout, notamment via un majorant d'un tel temps de transmission dit délai de transmission pire cas de bout en bout (WCTT). Les flux réseau considérés peuvent être échangés entre des noeuds, qu'ils soient mono-processeurs ou multi-processeurs, interconnectés par un réseau, par exemple de type Ethernet, mais également au sein de noeuds d'une architecture pluri-coeurs (« many-core ») interconnectés par un réseau sur puce (« Network on Chip », NoC). [0003] Lorsque plusieurs flux sont susceptibles de parcourir un même réseau, le calcul de tels délais de bout en bout est un problème complexe car, à la latence technologique (dépendant des équipements utilisés) et à la transmission proprement dite (variant en fonction du débit des liens) vient s'ajouter un temps d'attente clans les files de routeurs qui dépend de la présence ou de l'absence d'autres flux utilisant le même support de transmission en sortie d'un routeur (on parle alors de flux en contention ou encore de flux en concurrence de transmission). [0004] La détermination du WCTT peut être réalisée de manière analytique en utilisant dif- férentes méthodes de calcul, telles que par exemple le calcul réseau, l'approche par trajectoire, la vérification de modèles, la théorie des files d'attentes ou encore le calcul récursif Le choix d'une méthode par rapport à une autre dépend principalement du besoin d'obtenir des temps de transmission pire cas ou non et de la possibilité d'appliquer correctement la méthode de calcul au réseau considéré. Il est toutefois possible d'appliquer une méthode de calcul même lorsque toutes ses conditions 2 d'application ne sont pas satisfaites au moyen d'abstractions appropriées, mais au prix d'engendrer des sur-approximations dans les valeurs de délai de bout en bout calculées. Par ailleurs, la complexité de la méthode de calcul est un critère d'évaluation important pour s'assurer de son application en pratique sur des cas concrets. Une technique classique pour réduire cette complexité est d'abstraire le fonctionnement du réseau mais toujours au prix d'engendrer des sur-approximations sur les valeurs calculées. [0005] Une alternative à ces méthodes analytiques consiste à observer les temps de transmission de bout en bout de flux, par simulation ou directement sur le système réel. Toutefois, cette approche ne permet pas de garantir l'obtention d'une valeur pire cas du fait de la difficulté à démontrer que rensemble des possibilités a été couvert ou tout simplement de garantir que la configuration du système génère bien un tel pire cas en pratique. Exposé de l'invention [0006] L'invention a pour objectif de proposer une technique de mesure d'un temps de transmission de bout en bout qui puisse offrir l'assurance d'observer les conditions d'obtention d'une transmission pire cas et qui permette de déterminer une valeur pire cas exacte. [0007] A cet effet, l'invention propose un procédé de transmission de trame de données chacune sur un chemin comprenant au moins un routeur qui comporte des ports d'entrée, au moins un port de sortie et une unité d'arbitrage configurée pour sélectionner une trame de données parmi une pluralité de trames de données en provenance chacune d'un port d'entrée et en concurrence de transmission par un même port de sortie. Le procédé comprend, pour chaque routcur du chemin d'une trame de données cible, la spécification, pour chacun des ports d'entrée du routeur, de trames de données en concurrence avec la trame de données cible pour une transmission par un port de sortie cible du routcur. Lc procédé comprend la transmission de la trame de données cible et des trames de données en concurrence et la mesure d'un temps de transmission de bout en bout de la trame de données cible sur le chemin. La transmission de la trame de données cible comprend pour chaque routcur du chemin : [0008] en présence de la trame de données cible sur un port d'entrée du routeur, la sélection, par l'unité d'arbitrage, d'une ou plusieurs trames de données en concurrence; et [0009] la transmission par le port de sortie cible de la ou des trames de données en concurrence sélectionnées avant la transmission de la trame de données cible. [0010] Certains aspects préférés mais non limitatifs de ce procédé sont les suivants : [0011] l'étape de spécification est réalisée de manière à engendrer la transmission de la trame de données cible selon un délai de transmission de bout en bout pire cas ; 3 100121 l'unité d'arbitrage est configurée pour implémenter une politique d'arbitrage du type tourniquet et une trame de données en concurrence sélectionnée est une trame de données en concurrence associée à un port d'accès qui suit le port d'accès associé à la trame de données cible clans le tourniquet ; [0013] l'unité d'arbitrage est configurée pour implémenter une politique d'arbitrage du type à priorité fixe et la ou les trames de données en concurrence sélectionnée sont des trames de données en concurrence présentant un niveau de priorité supérieur à un niveau de priorité de la trame de données cible ; [0014] les trames de données en concurrence portent une charge utile fictive ; [0015] la présence de la trame de données cible sur un port d'accès du routeur est identifiée par reconnaissance d'un entête de référence de la trame de données cible dans une table d'entêtes de référence de trames de données associée audit port d'accès ; [0016] la trame de données cible comprend un champ indicatif d'une mise en concurrence ; [0017] à chaque port d'entrée est associée une séquence de description des trames de données spécifiées en concurrence avec la trame de données cible pour une transmission par le port de sortie cible du routeur ; [0018] les trames de données en concurrence sont désignées comme des trames de données cible qui sont également mises en contention sur chacun des routcurs de leurs chemins via une spécification de trames de données en concurrences, de manière similaire à ce qui est réalisé avec la trame de données cible. Brève description des dessins [0019] D'autres aspects, buts, avantages et caractéristiques de l'invention apparaîtront mieux à la lecture dc la description détaillée suivante de formes de réalisation préférées de celle-ci, donnée à titre d'exemple non limitatif, et faite en référence au dessin annexé sur lequel : [0020] [fig.1] illustre un exemple de mise en oeuvre du procédé selon l'invention avec une politique d'arbitrage dc type tourniquet. Description des modes de réalisation 100211 L'invention porte sur un procédé de transmission d'une trame de données sur un chemin reliant un noeud source à un noeud destinataire. Lors de sa transmission sur son chemin, cette trame peut être en contention avec d'autres trames, i.e. bloquée par ces trames. Deux trames sont dites en contention directe lorsque l'intersection de leurs chemins est non vide. Lorsque l'intersection de leurs chemins est vide, deux trames peuvent être en situation de contention indirecte via une troisième trame. Pour ce faire, cette troisième trame a avec chacun des deux autres trames une intersection non vide en termes de chemins. [0022] D'une manière générale, l'invention propose de réaliser une mesure du temps de transmission de bout en bout d'une trame cible depuis son noeud source jusqu'à son noeud destinataire alors que le degré de contention subi par la trame cible à chaque progression vers le noeud destinataire, i.c. à chaque routeur rencontré sur son chemin, est contrôlé. L'invention propose plus particulièrement d'influencer la politique d'arbitrage implémentée sur chacun des routeurs rencontrés par la trame cible en venant indiquer des trames qui devront systématiquement être transmises avant la trame cible et ainsi générer d'une manière maîtrisée des contentions directes et indirectes sur la trame cible au cours de la mesure. Il est de la sorte possible d'obtenir des enveloppes de temps de transmission de bout en bout pour la trame cible. Si le degré de contention subi par la trame cible est maximal, le temps de transmission de bout en bout obtenu est alors une valeur pire cas. [0023] Le mode d'exécution de l'arbitrage implémenté par les routcurs conformément à l'invention n'est accessible que dans une configuration du système distribué spécifique et protégée de toute utilisation non autorisée. Pour ce faire, ce mode d'exécution peut simplement être uniquement présent lors de la phase de conception du système ou sécurisé par des méthodes d'authentification adéquates si ce mode d'exécution est possible lors de l'exécution d'applicatifs. Enfin, ce mode d'exécution peut être présent dans un système distribué mais également dans un environnement de simulation de ce même système distribué. [0024] L'exposé qui suit s'intéresse principalement à un seul routeur, mais il est clair que le mode d'exécution de l'arbitrage proposé par l'invention a vocation à être mis en oeuvre par chacun des routeurs sur le chemin de la trame cible. [0025] Le routeur comporte des ports d'entrée, au moins un port de sortie et une unité d'arbitrage configurée pour sélectionner une trame de données parmi une pluralité de trames de données en provenance chacune d'un port d'entrée et en concurrence de transmission par un même port de sortie. Le rôle de l'unité d'arbitrage est ainsi de choisir parmi des trames concurrentes celle qui pourra accéder et utiliser le port de sortie pour progresser dans sa transmission. [0026] La stratégie d'arbitrage implémentée par l'unité d'arbitrage est par exemple du type tourniquet (« Round-Robin » en anglais) et consiste alors à gérer les ports d'entrée selon une file circulaire. Alternativement, elle peut être du type à priorité fixe (une priorité est alors associée à chaque trame), du type premier entré premier sorti (« First-In First-Out », FIFO), etc. L'exposé qui suit se réfère aux stratégies de type tourniquet ou de type à priorité fixe uniquement à titre d'exemples de stratégies possibles, sans que cela ne soit limitatif de l'invention. [0027] Le procédé selon l'invention comprend, pour chaque routeur du chemin de la trame cible, une étape de spécification, pour chacun des ports d'accès du routeur, de trames de données en concurrence avec la trame de données cible pour une transmission par un port de sortie cible du routcur. Ces trames de données en concurrence sont ainsi artificiellement mises en contention avec la trame cible et doivent être systématiquement transmises avant la trame cible et cela à chaque fois que cette trame cible doit être traitée par la politique d'arbitrage du routcur et en fonction de sa stratégie d'arbitrage. On vient de telle manière contrôler le degré de contention subi par la trame cible tout en restant compatible avec la stratégie d'arbitrage. [0028] Par exemple, si la stratégie est de type tourniquet et que le routcur dispose de n ports d'entrée, une trame cible peut être mise en contention avec jusqu'à n-1 trames en concurrence de transmission en provenance chacune d'un port d'entrée différent et différent du port d'entré de la trame cible. Si la stratégie est du type à priorité fixe et que le routeur dispose de n ports d'entrée, une trame cible peut être mise en contention avec p trames en concurrence de priorité supérieure ou égale à la priorité de la trame cible, potentiellement en provenance du même port d'entrée du routcur (port de la trame cible potentiellement inclus). [0029] La spécification des trames de données en concurrence se déduit d'une analyse de l'ensemble des flux réseau des applications présentes dans le système distribué considéré passant par cc routeur. Pour un système distribué, on fait plus particulièrement l'hypothèse qu'il est possible de déterminer statiquement (lors de la conception de ce système) les chemins et les tailles des trames échangées entre les différentes applications présentes. Le chemin d'une trame est décrit sous la forme d'une succession de routeurs sollicités par la trame pour atteindre son noeud destinataire depuis son noeud source. Cette hypothèse d'une description statique de l'ensemble des trames est par exemple une nécessité dans le domaine des systèmes temps réel ayant des échéances temporelles strictes. [0030] A partir de cette description statique des chemins de l'ensemble des trames, il est possible d'indiquer à chaque routeur du système distribué les trames devant être présentes sur chacun de ses ports d'entrée pour une mise en contention artificielle de manière directe avec la trame cible fA. Pour ce faire, une trame en concurrence avec la trame cible est décrite par les informations d'en-tête nécessaire à sa transmission, une charge applicative unitaire fictive, typiquement un mot, et le nombre de fois que cette charge applicative doit être reproduite pour atteindre la taille de la trame qui porte ainsi une charge utile fictive. [0031] De la même manière, pour chaque trame fB en concurrence avec la trame cible fA, il est nécessaire d'indiquer à chaque routeur du système distribué les trames devant artificiellement être présentes sur chacun de ses ports d'entrée pour une mise en contention de manière directe avec la trame fB et cela de manière récursive pour l'ensemble des trames ajoutées de cette manière. En d'autres termes, la trame fB devient elle-même 6 une trame cible pour laquelle on vient spécifier des trames en concurrence. Cette démarche de configuration récursive permet de prendre en compte les phénomènes de contentions indirectes. [0032] Ainsi, le procédé peut également comprendre la désignation de chaque trame de données en concurrence avec la trame cible comme une trame de données en concurrence cible, et pour chaque trame de données en concurrence cible, pour chaque routcur du chemin de la trame de données en concurrence cible, la spécification, pour chaque port d'entrée du routcur, de trames de données en concurrence avec la trame de données en concurrence cible pour une transmission par un port de sortie cible du routcur. [0033] Il est du ressort de l'utilisateur de spécifier l'ensemble des trames en contention qui définit le degré de contention que va subir la trame cible fA. Ainsi, si la spécification des trames en contention est exhaustive, le degré de contention que va subir la trame cible f,, est maximal et le délai de bout en bout mesuré correspondra à un délai de bout en bout pire cas. Néanmoins l'utilisateur peut volontairement spécifier unc liste partielle de trames en contention afin de mesurer des délais de bout en bout avec un degré de contention plus faible et ainsi obtenir des enveloppes de délai de bout en bout en appliquant différents degrés de contention. Enfin, il est à noter que l'invention ne porte pas sur la production des trames en contention, et qu'un homme du métier peut aisément développer un outil permettant l'automatisation de la construction de ces trames. [0034] Dans un mode de réalisation possible, à l'issue de l'étape de spécification, une structure de données flux_en_contention est associée à chaque port d'entrée du routeur et permet d'associer à chaque trame cible une séquence de description de trames mises en concurrence avec la trame cible. Une telle séquence de description de trames est triée pour représenter l'ordre de contention des trames de cette séquence sur la trame cible. Un index peut être associée à chaque séquence de description de trames en concurrence avec une trame cible afin de pointer sur la prochaine trame en concurrence avec la trame et (l'être en mesure de déterminer la fin de cette séquence (soit implicitement avec un élément identifiable en fin de séquence, soit explicitement en ajoutant un champ représentant la taille de la séquence). Le stockage de séquences de trames en concurrence est nécessaire car la situation pire cas pour une trame cible peut en effet nécessiter plusieurs décisions d'arbitrage défavorables, i.e. non gagnées par trame cible, avant de sélectionner la trame cible. [0035] La trame de données cible comprend un champ indicatif d'une mise en concurrence. Par exemple chaque entête d'une trame d'un flux est modifié pour inclure un bit indiquant si cette trame doit faire l'objet d'une mise en contention (noté contention_bit ). Le positionnement de ce bit dépend des protocoles utilisés dans la transmission 7 d'informations entre deux noeuds d'un système distribué. Par exemple, si le réseau considéré est un NoC alors la première unité de contrôle de flux FLIT (« Flow control uniT ») de chaque trame inclut un tel bit. Si le réseau considéré est basé sur Ethernet, le champ EtherType de l'entête Ethernet peut être utilisé pour contenir cette information. [0036] A chaque port d'entrée du routcur est associée une table notée flux reference qui permet à partir d'un entête de référence d'identifier le flux correspondant. Chaque trame ayant le bit contention bit positionné à 1 voit son entête recherché dans cette table afin d'identifier le flux reçu. Ainsi, la présence de la trame de données cible sur un port d'accès du routeur est identifiée par reconnaissance d'un entête de référence de la trame de données cible dans une table d'entêtes de référence de trames de données associée audit port d'accès. [0037] Les étapes du procédé selon l'invention peuvent être les suivantes pour le traitement de chaque trame entrante sur un port d'entrée PA d'un routcur. [0038] 1) Si le champ contention bit de l'entête de la trame entrante est positionné à 1, cet entête est comparé aux entêtes de références stockées dans la table flux reference par ce port pour identifier la trame reçue. Si aucune trame n'est identifiée, une erreur est signalée via un registre d'erreur approprié et le procédé attend la réception d'une trame entrante avant de redémarrer à l'étape 1. [0039] 2) Si une trame est identifiée, l'identifiant de cette trame fx est transmis à l'ensemble des autres ports d'entrée pour déterminer si des flux de ces autres ports d'entrée doivent être artificiellement mis en concurrence avec le flux G. Pour ce faire l'identifiant fx est utilisé par chaque port d'entrée comme une clé dans la structure de données flux_en_contention pour identifier le prochain flux devant être transmis par chaque port d'entrée du routeur. [0040] 3) La politique d'arbitrage implémentée par l'unité d'arbitrage est surchargée pour implémenter la situation pire cas d'arbitrage pour la trame G. Cette surcharge consiste à déterminer un port d'entrée ainsi que la trame qui devra être transmis à partir de ce port d'entrée. Par exemple, la situation pire cas pour une politique d'arbitrage de type tourniquet est de considérer que le prochain port d'entrée susceptible de transmettre une trame est le port d'entrée PH situé juste après le port d'entrée PA auquel est associé la trame f' selon l'ordre de parcours des ports d'entrée utilisé par la politique d'arbitrage du routeur. La situation pire cas pour une politique d'arbitrage à priorité fixe est de choisir systématiquement un port d'entrée ayant une trame en attente de priorité supérieure ou égale à la priorité de la trame fx. [0041] Une politique d'arbitrage de type tourniquet nécessite de mémoriser le port d'accès sélectionné pour transmettre la trame en concurrence avec la trame f, afin de pouvoir repartir de ce port d'accès dans le choix du prochain port d'entrée à choisir. A 8 contrario, une politique d'arbitrage à priorité fixe ne nécessite pas une telle mémorisation car tout port d'entrée ayant une trame de priorité supérieure ou égale à celle de la trame f constitue une décision valide pour le procédé. [0042] 4) Si une trame de données fy en concurrence avec la trame de données cible existe pour le port d'entrée PB, elle est alors transmise. La structure de données flux en contention de PB est alors mise à jour pour que l'index de la séquence associée à f, pointe sur la prochaine trame mise en concurrence si plusieurs décisions d'arbitrage sont nécessaires pour représenter le degré de contention souhaité. [0043] 5) Les étapes 3 et 4 sont répétées jusqu'à ce que la politique d'arbitrage ne puisse plus déterminer de trames fy ayant une priorité supérieure ou égale à la trame fx dans le cas d'une politique d'arbitrage à priorité fixe, ou choisisse le port PA dans le cas d'une politique d'arbitrage de type tourniquet. [0044] 6) La trame fxpcut alors être transmise et, sur chaque port d'entrée, la séquence de description de trames mises en concurrence avec la trame fx voit son index repositionné sur la tête de cette séquence pour être prise en compte lors d'une prochaine instance de la trame fx. [0045] Ainsi, le procédé selon l'invention comprend, suite à l'étape de spécification, la transmission de la trame de données cible et des trames de données en concurrence et la mesure d'un temps de transmission de bout en bout de la trame de données cible sur son chemin. La transmission de la trame de données cible comprend à chaque routeur de son chemin - [0046] - en présence de la trame de données cible sur un port d'accès du routeur, la sélection, par l'unité d'arbitrage, d'une ou plusieurs trames de données en concurrence; et [0047] - à la transmission par le port de sortie cible de la ou des trames de données en concurrence sélectionnées avant la transmission de la trame de données cible. [0048] La mesure du temps de transmission de bout en bout de la trame cible entre une date d'émission par le noeud source et une date de réception par le noeud destinataire est réalisée par toute technique connue de l'homme de l'art et n'est pas décrite plus en détail ici. Un horodatage matériel peut notamment être réalisé à cet effet, en utilisant par exemple le protocole de synchronisation d'horloge IEEE 1588. [0049] Lorsque l'unité d'arbitrage est configurée pour réaliser un arbitrage de type tourniquet, une trame de données en concurrence sélectionnée est une trame de données en concurrence associée à un port d'accès qui suit le port d'accès associé à la trame de données cible dans le tourniquet. [0050] Et lorsque l'unité d'arbitrage est configurée pour réaliser un arbitrage de type à priorité fixe tourniquet, la ou les trames de données en concurrence sélectionnées sont des trames de données en concurrence présentant un niveau de priorité supérieur à un 9 niveau de priorité de la trame de données cible. [0051] Par ailleurs lors que les phénomènes de contention indirecte sont pris en compte, la transmission de chaque trame de données en concurrence cible comprend à chaque routcur sur son chemin : i. en présence de la trame de données en concurrence cible sur un port d'entrée du routeur, la sélection d'une ou plusieurs trames de données en concurrence avec la trame de données en concurrence cible; et ii. la transmission par le port de sortie cible de la ou des trames de données en concurrence sélectionnées avant la transmission de la trame de données en concurrence cible. [0052] On décrit dans ce qui suit un exemple de mise en oeuvre du procédé selon l'invention au niveau d'un routeur R comprenant trois ports d'entrée Pl, P2 et P3 et un port de sortie PS. La trame cible est la trame fA entrante sur le port Pl. Suivant l'étape de spécification, les trames fE et fc sont artificiellement mises en concurrence avec la trame cible f,, sur le port P2, et la trame fr, est artificiellement mise en concurrence avec la trame cible fA sur le port P3. [0053] La trame cible fA contient un entête dans laquelle le bit contention bit est positionné à 1 déclenchant l'étape 1 ci-dessus. Les flux fR, fc et fp sont alors identifiés comme devant être mis en contention avec fA, respectivement sur les ports P2 (pour fs et fc) et P3 (pour fp). [0054] La politique d'arbitrage implémentée par l'unité d'arbitrage est du type tourniquet. Les ports d'entrées du routeur sont numérotés selon l'ordre de parcours par la politique d'arbitrage, i.e. un index pointe sur le port d'entrée courant qui est simplement incrémenté à chaque décision d'arbitrage pour éviter une monopolisation d'un port de sortie par un port d'entrée. [0055] A l'étape 3 du procédé, cet index est positionné sur le port d'entrée P2, cor- respondant au ph-e cas pour cette politique d'arbitrage. Une première décision d'arbitrage est prise et la trame fi, est transmise sur le port de sortie PS (#1 sur la figure 1). La séquence en contention depuis le port d'entrée P2 pour la trame cible fA est mise à jour pour pointer sur le prochain flux à mettre en contention sur le port d'entrée P2, en l'occurrence la trame fc. L'index de l'unité d'arbitrage est alors positionné au prochain port d'entrée, en l'occurrence le port P3. Une nouvelle décision d'arbitrage est alors prise engendrant la transmission de la trame fr)(étapes 3 et 4 ; #2 sur la figure 1). L'index de l'unité d'arbitrage est alors positionné au prochain port d'entrée, en l'occurrence le port Pl. Une dernière décision d'arbitrage est alors prise engendrant cette fois la transmission de la trame cible fA (étape 6 du procédé ; #3 sur la figure 1). Lors d'une prochaine mise en contention de la trame fA, lorsque l'index sera positionné sur le port d'entrée P2, la décision d'arbitrage engendrera la transmission de la trame fc [0056] Nous illustrons maintenant la différence lorsque la politique d'arbitrage est à priorité fixe, en faisant l'hypothèse que la trame f, est de priorité supérieure à la priorité de la trame f, qui est elle-même de priorité supérieure à la priorité de la trame f' qui est elle-même de priorité supérieures à la priorité de la trame f'. La différence réside dans le fait que les deux premières décisions d'arbitrages engendrent la transmission successive des trames et fc alors qu'elles sont issues du même port d'entré P2. Puis, la troisième décision d'arbitrage engendre la transmission de la trame f' et la quatrième décision d'arbitrage engendre la transmission de la trame f'.. 11 [Revendication I]