Brevet FR2931602A1 — publié le 20091127

PROCÉDÉ DE CALCUL DE TEMPS DE LATENCE D'ÉMISSIONS DE MESSAGES D'ÉQUIPEMENTS CONNECTÉS À UN BUS MULTIPLEXÉ L'invention concerne les réseaux de communication, par exemple de type CAN (� Controller Area Network �), dans lesquels des messages sont transmis au moyen de bus multiplexés, et plus particulièrement le calcul prévisionnel des temps de latence des émissions de tels messages par des équipements qui sont connectés en parallèle à de tels bus multiplexés. Dans un réseau à bus multiplexé(s), par exemple de véhicule automobile, plusieurs équipements connectés en parallèle peuvent vouloir émettre sensiblement en même temps. Dans la situation précitée et en l'absence de règles d'émission les messages les moins prioritaires doivent attendre que les messages plus prioritaires qu'eux aient été transmis avant de pouvoir être transmis à leur tour. Il en résulte qu'il est impossible de définir (ou prévoir) la valeur maximale du temps de latence (ou temps d'attente) des messages au sein d'un équipement. Il est rappelé que cette valeur maximale (également appelée temps de latence � pire cas �) est une information importante pour les vérifications des performances de certaines fonctions impliquant plusieurs équipements. Ainsi, pour garantir un délai entre un changement d'état d'un premier équipement, tel qu'un interrupteur, et le changement d'état correspondant d'un second équipement associé au premier, tel qu'un voyant, il est indispensable de maîtriser le temps de transfert du message qui va requérir le changement d'état du second équipement (ici le voyant), lequel est fonction du temps de latence de ce message dans l'équipement qui veut l'émettre. Par conséquent, si l'on ne connaît pas de façon anticipée les valeurs maximales (pire cas) des temps de latence des messages périodiques que sont susceptibles d'émettre des équipements d'un réseau à bus multiplexé(s), on sera dans l'obligation de limiter la charge moyenne des bus afin d'éviter d'avoir à effectuer un trop grand nombre d'arbitrages entre messages. L'invention a notamment pour but de proposer une solution permettant, lors de la conception ou de la modification d'un réseau de communication, de calculer les valeurs maximales, des temps de latence des émissions des équipements de ce réseau de communication, qui correspondent au pire cas. Elle propose à cet effet un procédé, dédié au calcul des temps de latence des émissions de messages associés à des niveaux de priorité différents par des équipements qui sont connectés en parallèle à un bus multiplexé d'un réseau de communication, et consistant, en cas de réception d'informations définissant la longueur de messages périodiques que chaque équipement veut émettre dans une tranche de cycle d'émission : - à calculer la durée d'émission de chaque message périodique à transmettre en fonction de sa longueur désignée, puis - à définir des combinaisons différentes de tranches d'équipements susceptibles d'émettre en même temps, afin de calculer pour chaque combinaison définie un temps de latence pour chaque message périodique placé dans chaque tranche de cette combinaison, compte tenu de son niveau de priorité, et - à déterminer parmi tous les temps de latence, calculés pour les messages des différentes combinaisons, les valeurs maximales qui correspondent au pire cas. Ce procédé de calcul selon l'invention peut comporter d'autres caractéristiques qui peuvent être prises séparément ou en combinaison : - en présence d'une combinaison pour laquelle la somme des durées d'émission des messages périodiques dans une tranche est supérieure à la durée de cette dernière, on peut analyser la somme des durées d'émission des messages périodiques au moins dans la tranche suivante jusqu'à la découverte d'une tranche de cette combinaison pour laquelle la somme des durées d'émission des messages périodiques est inférieure à sa propre durée, et on peut retenir cette tranche afin de déterminer les temps de latence des messages périodiques qu'elle contient ; - en présence d'un message événementiel dont la priorité n'est pas maximale, on peut prendre en compte la durée d'émission de ce message événementiel dans la somme des durées d'émission des messages contenus dans la tranche considérée dans la combinaison considérée ; - en présence de messages périodiques de faible(s) priorité(s), dédiés à la transmission de messages longs devant être segmentés, on peut considérer que le réseau de transmission est occupé pendant la durée de transmission du message qui a la plus grande longueur (les messages sont donc retardés lors de la première tranche d'un cycle). D'autres caractéristiques et avantages de l'invention apparaîtront à l'examen de la description détaillée ci-après, et des dessins annexés, sur lesquels : - la figure 1 illustre schématiquement et fonctionnellement une partie d'un bus multiplexé auquel sont connectés en parallèle trois équipements équipés chacun d'un contrôleur, et - la figure 2 illustre schématiquement trois exemples de tranches de trois équipements utilisées pour former une tranche virtuelle (TV) d'une combinaison de tranches selon l'invention. Les dessins annexés pourront non seulement servir à compléter l'invention, mais aussi contribuer à sa définition, le cas échéant. On a schématiquement représenté sur la figure 1 un exemple de bus multiplexé B d'un réseau de communication auquel sont connectés en parallèle trois équipements Ei (i = 1 à 3) propres à transmettre des messages périodiques de niveaux de priorité différents ainsi qu'éventuellement des messages événementiels de niveau de priorité maximal ou non. Dans ce qui suit, on considère à titre d'exemple non limitatif que le réseau de communication est un réseau de type CAN d'un véhicule automobile, et que les équipements Ei sont des calculateurs équipés d'un contrôleur CRi. Mais, l'invention n'est limitée ni à ce type de réseau, ni à ce type d'équipement. Elle concerne en effet tout type de réseau de communication comprenant au moins un bus multiplexé, et tout type d'équipement capable de transmettre des messages de niveaux de priorité différents sur un bus multiplexé. Il est rappelé que dans un réseau tel que celui présenté ci-avant, chaque équipement Ei est associé à un cycle d'émission Ci d'une durée donnée, et que chaque cycle Ci est décomposé en Ni tranches Tij (j = 1 à Ni) au cours desquelles l'équipement Ei concerné peut être autorisé par son contrôleur CRi à transmettre ses messages périodiques. On notera que le nombre Ni de tranches Tij peut être identique pour tous les cycles Ci. Dans ce cas, Ni est égal à une constante N. Par ailleurs, les durées des tranches Tij sont de préférence identiques, mais cela n'est pas obligatoire. Lorsqu'un contrôleur CRi autorise son équipement Ei à émettre un (des) message(s) périodique(s) qui ont été placés dans une tranche Tij, alors cet équipement Ei émet ce(s) message(s) périodique(s) dans le bus B afin qu'il(s) diffusent. L'invention propose de mettre en oeuvre un procédé permettant de calculer des temps de latence dits � pire cas � pour chaque message périodique que chaque équipement Ei, connecté en parallèle au bus multiplexé B du réseau de communication présenté ci-avant, veut émettre. Ce procédé comprend trois étapes principales. Une première étape principale du procédé consiste à déterminer la durée d'émission de chaque message périodique à transmettre en fonction de sa longueur (désignée dans une demande d'émission reçue). Il existe en effet une relation entre le nombre de bits d'un message (et donc sa longueur) et le temps qu'il faut pour émettre ces bits au niveau d'un équipement Ei. Par exemple, on peut considérer le pire cas pour lequel on ajoute tous les cinq bits un bit dit de � stuffing � qui sert à compléter la valeur de la somme des bits précédents pour l'amener à une valeur choisie. Dans ce cas, la durée d'émission Tmsg d'un message peut être donnée par la formule Tmsg = 34 + (8 x L) + (34 + (8 x L-1)) / 4, où le chiffre 34 désigne le nombre de bits d'enrobage (entêtes) pour une trame de type standard et L est la longueur du message en terme de nombre d'octets (lequel est généralement compris entre 1 et 8 octets). Une deuxième étape principale du procédé consiste ensuite à déterminer toutes les combinaisons possibles (différentes) de tranches Tij d'équipements Ei susceptibles d'émettre en même temps. Par exemple, si l'on a n équipements susceptibles d'émettre en même temps et que les cycles respectifs Cl à Cn du premier équipement El au dernier équipement En contiennent respectivement A, B, C, ..., N tranches, alors le nombre de combinaisons possibles est égal à AxBxCx...xN, ce qui est égal à Nn lorsque tous les cycles Ci des n équipements Ei (i = 1 à n) comprennent le même nombre N de tranches Tij (j = 1 à N). Il est important de noter que chaque combinaison formée constitue en quelque sorte un cycle virtuel subdivisé en tranches virtuelles TV qui comprennent chacune tous les messages périodiques que les différents équipements Ei veulent émettre pour l'une des tranches de leur cycle d'émission Ci. Il est également important de noter qu'au sein de chaque tranche virtuelle TV de chaque combinaison, les messages périodiques sont placés en fonction de leurs niveaux de priorité respectifs, du plus prioritaire vers le moins prioritaire. Une fois que toutes les combinaisons différentes ont été formées, on détermine pour chaque combinaison le temps de latence de chaque message faisant partie de chaque tranche virtuelle TV de cette combinaison, compte tenu de son niveau de priorité. On comprendra que chaque temps de latence d'un message dépend de la position de ce message dans la tranche virtuelle TV considérée et donc de la somme des longueurs des messages qui le précèdent éventuellement au sein de cette tranche virtuelle TV. On a schématiquement illustré sur la figure 2 un exemple non limitatif de tranche virtuelle TV résultant de la combinaison de trois tranches T12, T21 et T33 de trois équipements El à E3. Dans cet exemple, la deuxième tranche T12 du premier équipement El comprend trois messages ayant les niveaux de priorité 1, 6 et 9, la première tranche T21 du deuxième équipement E2 comprend trois messages ayant les niveaux de priorité 3, 7 et 8, et la troisième tranche T33 du troisième équipement E3 comprend deux messages ayant les niveaux de priorité 4 et 5. La tranche virtuelle TV, résultant de la combinaison des trois tranches T12, T21 et T33, comprend alors les huit messages de ces trois tranches T12, T21 et T33, placés en fonction de leurs niveaux de priorité décroissants (en commençant par le plus important (1)), à savoir 1, 3, 4, 5, 6, 7, 8, 9. Si cette combinaison est jugée satisfaisante, alors l'ordre des émissions sur le bus multiplexé B sera : message de niveau de priorité 1 du premier équipement E1, puis message de niveau de priorité 3 du deuxième équipement E2, puis message de niveau de priorité 4 du troisième équipement E3, puis message de niveau de priorité 5 du troisième équipement E3, puis message de niveau de priorité 6 du premier équipement El, puis message de niveau de priorité 7 du deuxième équipement E2, puis message de niveau de priorité 8 du deuxième équipement E2, et message de niveau de priorité 9 du premier équipement E1. 1 o Une troisième étape principale du procédé selon l'invention consiste à déterminer parmi tous les temps de latence, qui ont été calculés (lors de la deuxième étape principale) pour les messages des différentes combinaisons, ceux qui présentent respectivement des valeurs maximales qui correspondent au pire cas (c'est-à-dire au plus défavorable et donc à la plus longue durée). 15 On comprendra qu'il peut arriver que dans une tranche virtuelle TV d'une combinaison, le temps de latence calculé pour un message soit supérieur à la durée de cette tranche virtuelle TV. En d'autres termes, la somme des durées d'émission des messages dans une tranche virtuelle TV peut être supérieure à la durée de cette dernière. Une telle tranche virtuelle TV 20 comprend trop de messages, si bien qu'ils ne pourront pas tous être émis par les différents équipements Ei demandeurs dans leur tranche Tij en cours. Dans ce cas, on peut par exemple analyser la somme des durées d'émission des messages au moins dans la tranche virtuelle suivante de la combinaison considérée jusqu'à ce que l'on découvre une tranche virtuelle de 25 cette combinaison pour laquelle la somme des durées d'émission des messages est inférieure à sa propre durée. Le mécanisme de passage d'une tranche virtuelle à la suivante peut par exemple être défini comme suit. Tant que la tranche virtuelle posant problème n'est pas la dernière de la combinaison considérée on analyse la 30 tranche virtuelle suivante, et lorsque la tranche virtuelle posant problème est la dernière de la combinaison considérée on analyse la première tranche virtuelle de cette combinaison considérée. On réitère le mécanisme de passage d'une tranche virtuelle à la suivante tant que l'on n'est pas revenu à la tranche virtuelle posant initialement problème. Si l'on revient à la tranche virtuelle posant initialement problème cela veut dire que l'on est en présence d'une combinaison offrant un cycle virtuel provoquant une charge du bus multiplexé B de 100% pour lequel les temps de latence des messages périodiques ne peuvent pas être garantis. Dans ce cas, on ne pourra pas garantir de temps de latence maximal pour les messages restants à transmettre. On notera que le procédé de calcul, selon l'invention, peut également permettre de prendre en compte certains messages événementiels (c'est-à-dire non périodiques). Il existe deux types de message événementiel. Un premier type regroupe les messages événementiels de priorité maximale qui sont généralement des messages d'alarme ou d'alerte (par exemple transmis lorsqu'un véhicule fait l'objet d'une situation critique). Un second type regroupe les messages événementiels qui ne présentent pas une priorité maximale. Le procédé peut prendre en compte les messages événementiels du second type dans les calculs de temps de latence qu'il effectue pour les différentes combinaisons. Les messages événementiels du premier type ne sont pas ici pris en compte car on considère que les temps de latence pourraient ne plus être respectés durant leur transmission. Plus précisément, on peut par exemple prendre en compte la durée d'émission d'un message événementiel dans la somme des durées d'émission des messages qui sont contenus dans la tranche virtuelle TV considérée dans la combinaison considérée. En effet, les messages événementiels pouvant être transmis à n'importe quel moment, ils sont ajoutés à chaque tranche virtuelle TV dans la première combinaison puis lors de chacune de leurs éventuelles réémissions. On notera que le placement d'un message événementiel du second type dans une tranche virtuelle TV se fait de préférence en fonction de son niveau de priorité (lequel est généralement élevé, bien que non prioritaire, permettant ainsi de le transmettre en premier ou dans les premiers). On notera également que le procédé selon l'invention peut éventuellement prendre en compte des messages périodiques dédiés à la transmission de messages longs qui doivent être segmentés, sous réserve que leur niveau de priorité soit le plus faible. En présence d'un tel message segmenté, on considère que le réseau de transmission est occupé pendant la durée de transmission du message qui a la plus grande longueur. Cela revient à retarder les messages lors de la première tranche d'un cycle. En effet, lors de l'émission d'une tranche virtuelle TV, un message événementiel segmenté peut être en cours d'émission. Il occupe donc le bus B dans le pire des cas durant l'émission d'un message de 8 octets. On notera également que l'invention peut prendre en considération le fait que les durées des périodes peuvent ne pas être rigoureusement précises, en raison principalement de l'imprécision des oscillateurs internes des calculateurs des équipements Ei. Pour ce faire, on peut par exemple se placer dans le pire cas qui correspond aux plus petites durées de période, ce qui revient à effectuer les calculs avec une durée de tranche minimale. On notera également que le procédé selon l'invention peut être mis en oeuvre au moyen d'un dispositif de calcul qui peut par exemple être implanté dans un ordinateur. Un tel dispositif de calcul est de préférence réalisé sous la forme de modules logiciels (ou informatiques) pouvant être stockés sur tout type de support (ou médium) de stockage (ou mémorisation). Mais, il peut être également réalisé sous la forme de circuits électroniques ou d'une combinaison de circuits électroniques et de modules logiciels. L'invention ne se limite pas aux modes de réalisation de procédé et dispositif de calcul décrits ci-avant, seulement à titre d'exemple, mais elle englobe toutes les variantes que pourra envisager l'homme de l'art dans le cadre des revendications ci-après. REVENDICATIONS1. Procédé de calcul de temps de latence des émissions de messages associés à des niveaux de priorité différents par des équipements (Ei) connectés en parallèle à un bus multiplexé (B) d'un réseau de communication, caractérisé en ce qu'il consiste, en cas de réception d'informations définissant la longueur de messages périodiques que chaque équipement (Ei) veut émettre dans une tranche de cycle d'émission, i) à calculer la durée d'émission de chaque message périodique à transmettre en fonction de sa longueur définie, puis ii) à définir des combinaisons différentes de tranches d'équipements (Ei) susceptibles d'émettre en même temps, afin de calculer pour chaque combinaison définie un temps de latence pour chaque message périodique placé dans chaque tranche de cette combinaison, compte tenu de son niveau de priorité, et iii) à déterminer parmi tous lesdits temps de latence, calculés pour les messages des différentes combinaisons, les valeurs maximales qui correspondent au pire cas. 2. Procédé selon la revendication 1, caractérisé en ce qu'en présence d'une combinaison pour laquelle la somme des durées d'émission des messages périodiques dans une tranche est supérieure à la durée de cette dernière, on analyse la somme des durées d'émission des messages périodiques au moins dans la tranche suivante jusqu'à ce que l'on découvre une tranche de cette combinaison pour laquelle la somme des durées d'émission des messages périodiques est inférieure à sa propre durée, puis on retient cette tranche afin de déterminer les temps de latence des messages périodiques qu'elle contient. 3. Procédé selon l'une des revendications 1 et 2, caractérisé en ce qu'en présence d'un message événementiel dont la priorité n'est pas maximale, on prend en compte la durée d'émission de ce message événementiel dans la somme des durées d'émission des messages contenus dans la tranche considérée dans la combinaison considérée. 4. Procédé selon l'une des revendications 1 à 3, caractérisé en ce qu'en 2931602 io présence de messages périodiques de faible(s) priorité(s), dédiés à la transmission de messages longs devant être segmentés, on considère que ledit réseau de transmission est occupé pendant la durée de transmission du message qui a la plus grande longueur.