FR2770714A1 - PATH DETECTION IN A DISTRIBUTED NETWORK - Google Patents
PATH DETECTION IN A DISTRIBUTED NETWORK Download PDFInfo
- Publication number
- FR2770714A1 FR2770714A1 FR9713784A FR9713784A FR2770714A1 FR 2770714 A1 FR2770714 A1 FR 2770714A1 FR 9713784 A FR9713784 A FR 9713784A FR 9713784 A FR9713784 A FR 9713784A FR 2770714 A1 FR2770714 A1 FR 2770714A1
- Authority
- FR
- France
- Prior art keywords
- message
- station
- sei
- cost
- identifier
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/12—Shortest path evaluation
- H04L45/122—Shortest path evaluation by minimising distances, e.g. by selecting a route with minimum of number of hops
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/20—Hop count for routing purposes, e.g. TTL
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
Un procédé de routage de message entre des stations d'un réseau est caractérisé en ce que chacune des stations effectue les opérations suivantes :- mémorisation (E104, E102) de données concernant chaque message qu'elle reçoit et comportant au moins un identificateur (ID, SEI) de message, un identificateur (SET) de la station émettrice du message et un coût (CT) de transmission de message,et, après avoir mémorisé les données de deux messages dont les identificateurs (ID, SEI) de message sont identiques et les identificateurs (SET) de station émettrice sont différents,- comparaison des coûts de transmission (CT) des deux messages pour déterminer la station émettrice associée au coût le plus faible.L'invention permet de détecter des chemins dans le réseau.A method of routing a message between stations of a network is characterized in that each of the stations performs the following operations: - storage (E104, E102) of data relating to each message that it receives and comprising at least one identifier (ID , SEI) of message, an identifier (SET) of the station sending the message and a cost (CT) for transmission of the message, and, after having stored the data of two messages whose message identifiers (ID, SEI) are identical and the transmitting station identifiers (SET) are different, - comparison of the transmission costs (CT) of the two messages to determine the transmitting station associated with the lowest cost. The invention makes it possible to detect paths in the network.
Description
La présente invention concerne le routage des communications entre les stations d'un réseau de type distribué. The present invention relates to the routing of communications between stations of a distributed type network.
Le réseau est par exemple un réseau local sans fil dont les stations communiquent entre elles en se partageant un canal radio. The network is for example a local wireless network whose stations communicate with each other by sharing a radio channel.
Un réseau de type distribué ne possède pas de station de base pour gérer les communications entre les stations. Une fonction de routage rend possible les communications entre les stations du réseau, en déterminant les chemins de communication dans le réseau. Cette fonction est adaptée aux contraintes d'un réseau local sans fil, notamment la bande passante limitée, et la mobilité des stations ou les modifications de l'environnement des stations qui provoquent des changements de topologie du réseau. A distributed type network does not have a base station to manage communications between stations. A routing function makes communication between stations in the network possible, by determining the communication paths in the network. This function is adapted to the constraints of a wireless local area network, in particular the limited bandwidth, and the mobility of the stations or the modifications of the environment of the stations which cause changes in the topology of the network.
Des procédés connus de routage reposent sur des échanges périodiques de messages de routage pour détecter les changements de topologie du réseau. La fonction de routage doit modifier le plus rapidement possible les chemins de communication dans le réseau, pour que les chemins connus correspondent aux chemins réels existant dans le réseau, faute de quoi le risque de mauvais acheminement et de perte de message est grand. II est donc nécessaire que les messages de routage soient fréquents. Known routing methods rely on periodic exchanges of routing messages to detect changes in network topology. The routing function must modify the communication paths in the network as quickly as possible, so that the known paths correspond to the actual paths existing in the network, failing which the risk of misdirection and loss of message is great. It is therefore necessary that the routing messages are frequent.
Cependant, les messages de routage occupent le canal radio, au détriment des données utiles. II faut donc que la fonction de routage génère le moins possible de messages de routage1 pour occuper peu de bande passante. However, routing messages occupy the radio channel, to the detriment of useful data. It is therefore necessary that the routing function generates the least possible of routing messages 1 to occupy little bandwidth.
Ces contraintes sont contradictoires et rendent complexe le fonctionnement de la fonction de routage. These constraints are contradictory and make the operation of the routing function complex.
La présente invention vise à remédier aux inconvénients de la technique antérieure, en fournissant un procédé de détection de chemin dans un réseau distribué, qui permet de détecter rapidement de nouveaux chemins sans augmenter le trafic de routage. The present invention aims to remedy the drawbacks of the prior art, by providing a path detection method in a distributed network, which makes it possible to rapidly detect new paths without increasing the routing traffic.
A cette fin, I'invention propose un procédé de routage de message entre des stations d'un réseau, caractérisé en ce que chacune des stations effectue les opérations suivantes:
- mémorisation de données concernant chaque message qu'elle reçoit et comportant au moins un identificateur de message, un identificateur de la station émettrice du message et un coût de transmission de message,
et, après avoir mémorisé les données de deux messages dont les identificateurs de message sont identiques et les identificateurs de station émettrice sont différents,
- comparaison des coûts de transmission des deux messages pour déterminer la station émettrice associée au coût le plus faible.To this end, the invention proposes a method for routing messages between stations of a network, characterized in that each of the stations performs the following operations:
storage of data relating to each message which it receives and comprising at least one message identifier, an identifier of the station sending the message and a message transmission cost,
and, after having stored the data of two messages whose message identifiers are identical and the transmitting station identifiers are different,
- comparison of the transmission costs of the two messages to determine the transmitting station associated with the lowest cost.
Le procédé selon l'invention résout le problème énoncé cidessus, en utilisant les messages de données acheminés dans le réseau pour en déduire de l'information de routage. The method according to the invention solves the problem stated above, by using the data messages conveyed in the network to deduce routing information therefrom.
La mémorisation de données est effectuée dans une table spécifique, ou journal, destinée à recueillir des informations sur les messages entendus par la station considérée. Data storage is carried out in a specific table, or journal, intended to collect information on the messages heard by the station considered.
Le procédé permet d'évaluer les performances de l'algorithme de routage en cours. The method makes it possible to evaluate the performance of the current routing algorithm.
Le procédé s'adapte à toute fonction de routage connue, dont l'exécution est indépendante du procédé selon l'invention. The method adapts to any known routing function, the execution of which is independent of the method according to the invention.
Selon une caractéristique préférée, le procédé comporte la transmission de l'information de routage formée par la connaissance de la station émettrice associée au coût le plus faible à une station de traitement, qui exploite alors cette information. According to a preferred characteristic, the method comprises the transmission of the routing information formed by the knowledge of the transmitting station associated with the lowest cost to a processing station, which then uses this information.
Selon une caractéristique préférée, le coût est le nombre cumulé de tous les messages précédents ayant le même identificateur de message que le message considéré. En d'autres termes, le coat est le nombre de sauts effectués depuis une station émettrice initiale de message, et mesure ainsi une longueur de chemin. According to a preferred characteristic, the cost is the cumulative number of all the preceding messages having the same message identifier as the message considered. In other words, the coat is the number of hops made from an initial message sending station, and thus measures a path length.
Selon une autre caractéristique préférée, I'identificateur de message comporte l'adresse de la station émettrice initiale du premier des messages précédents ayant le même identificateur de message que le message considéré. Les messages sont ainsi identifiés de manière simple et fiable. According to another preferred characteristic, the message identifier comprises the address of the initial sending station of the first of the preceding messages having the same message identifier as the message considered. The messages are thus identified in a simple and reliable manner.
L'invention conceme aussi une station de communication d'un réseau, caractérisée en ce qu'elle comporte, ou en ce qu'elle est adaptée à coopérer avec:
- des moyens de mémorisation de données concemant chaque message qu'elle reçoit, ces données comportant au moins un identificateur de message, un identificateur de la station émettrice du message et un coût de transmission de message,
- des moyens de vérification qu'ont été mémorisées les données de deux messages dont les identificateurs de message sont identiques et les identificateurs de station émettrice sont différents, et
- des moyens de comparaison des coûts de transmission de deux messages dont les identificateurs de message sont identiques et les identificateurs de station émettrice sont différents, pour déterminer la station émettrice associée au coût le plus faible.The invention also relates to a communication station of a network, characterized in that it comprises, or in that it is adapted to cooperate with:
data storage means relating to each message it receives, this data comprising at least one message identifier, an identifier of the station transmitting the message and a message transmission cost,
means of verification that the data of two messages have been memorized, the message identifiers of which are identical and the transmitting station identifiers are different, and
- Means of comparing the costs of transmitting two messages whose message identifiers are identical and the transmitting station identifiers are different, to determine the transmitting station associated with the lowest cost.
La station selon l'invention présente les mêmes avantages que ceux précédemment exposés du procédé. The station according to the invention has the same advantages as those described above of the method.
Les caractéristiques et avantages de la présente invention apparaîtront plus clairement à la lecture d'un mode préféré de réalisation illustré par les dessins ci-joints, dans lesquels:
- la figure 1 représente un réseau distribué de stations1
- la figure 2 représente une station mobile du réseau de la figure 1,
- la figure 3 représente une table de routage de l'une des stations mobiles du réseau de la figure 1,
- la figure 4 représente un message de données transmis d'une station mobile à une autre,
- la figure 5 représente un extrait d'une table de messages entendus par l'une des stations mobiles du réseau, selon l'invention,
- la figure 6 est un algorithme de traitement de message de données et de détection de chemin, selon l'invention.The characteristics and advantages of the present invention will appear more clearly on reading a preferred embodiment illustrated by the attached drawings, in which:
- Figure 1 shows a distributed network of stations1
FIG. 2 represents a mobile station of the network of FIG. 1,
FIG. 3 represents a routing table of one of the mobile stations of the network of FIG. 1,
FIG. 4 represents a data message transmitted from one mobile station to another,
FIG. 5 represents an extract from a table of messages heard by one of the mobile stations of the network, according to the invention,
- Figure 6 is a data message processing algorithm and path detection, according to the invention.
Selon le mode de réalisation choisi et représenté à la figure 1, un réseau local sans fil comporte des stations, dont cinq, référencée SM a à S Me sont représentées. Les stations sont ici mobiles. La connectivité des stations mobiles évolue en permanence, en fonction des déplacements des stations et des modifications de leur environnement. De plus, il est possible que le nombre de stations mobiles effectivement connectées au réseau évolue également. Les stations communiquent entre elles par transmission radio, ou en variante par transmission infrarouge. Chaque station, ou noeud du réseau, est repérée par une adresse unique. On s'intéresse ici plus particulièrement aux communications en mode point à point. According to the embodiment chosen and represented in FIG. 1, a wireless local area network comprises stations, five of which, referenced SM a to S Me are represented. The stations are mobile here. The connectivity of mobile stations is constantly evolving, depending on the movements of the stations and changes in their environment. In addition, the number of mobile stations actually connected to the network may also change. The stations communicate with each other by radio transmission, or alternatively by infrared transmission. Each station, or node of the network, is identified by a unique address. We are particularly interested here in point-to-point communications.
Le réseau est de type distribué, c'est-à-dire qu'il ne comporte pas de station de base pour gérer les communications entre stations. Les communications entre stations sont rendues possibles par une fonction de routage. Si deux stations, par exemple les stations SMa et SMb, sont en écoute directe, c'est-à-dire si ces deux stations sont suffisamment proches l'une de l'autre et sans obstacle à la transmission radio, elles peuvent communiquer directement sur le segment "ab". La station SMa peut envoyer un message, détaillé dans la suite, à la station SMb. La station SMa est dite station émettrice initiale, et la station SMb est dite station destinataire finale. The network is of the distributed type, that is to say that it does not include a base station for managing communications between stations. Communication between stations is made possible by a routing function. If two stations, for example the stations SMa and SMb, are in direct listening, that is to say if these two stations are close enough to each other and without obstacle to the radio transmission, they can communicate directly on the "ab" segment. The station SMa can send a message, detailed below, to the station SMb. The station SMa is called the initial transmitting station, and the station SMb is called the final destination station.
En revanche, si deux stations, par exemple les stations SMa et SMd, ne peuvent pas communiquer directement, la communication passe par d'autres stations intermédiaires, ici les stations SMb et SMC, qui jouent le rôle de relais entre les deux stations SM a et SMd. Le message est alors transmis successivement sur les segments "ab", puis "bc", et enfin "cd". Ces trois segments forment un chemin entre les stations SMa et SMd. On the other hand, if two stations, for example the stations SMa and SMd, cannot communicate directly, the communication passes through other intermediate stations, here the stations SMb and SMC, which play the role of relay between the two stations SM a and SMd. The message is then transmitted successively on the "ab", then "bc", and finally "cd" segments. These three segments form a path between the stations SMa and SMd.
La fonction de routage s'exécute au-dessus d'un mécanisme d'accès
MAC contrôle d'accès au support (Medium Access Control) de type CSMA/CA accès multiple par détection de porteuse et évitement de collision (Carrier
Sense Multiple Access / Collision Avoidance) qui permet de partager le canal de transmission. Dans le cas des communications point à point, telles qu'envisagées ici, la fiabilité des communications de données est assurée par l'utilisation d'un mécanisme classique d'acquittement, ou accusé de réception, et de retransmission des données, si l'accusé de réception n'est pas reçu.Routing function runs over an access mechanism
MAC medium access control (Medium Access Control) of CSMA / CA type multiple access by carrier detection and collision avoidance (Carrier
Sense Multiple Access / Collision Avoidance) which allows sharing the transmission channel. In the case of point-to-point communications, as envisaged here, the reliability of data communications is ensured by the use of a conventional mechanism of acknowledgment, or acknowledgment of receipt, and retransmission of data, if the acknowledgment is not received.
La fonction de routage est connue en soi et ne sera pas plus décrite. The routing function is known per se and will not be described further.
Un mode de réalisation de l'une quelconque des stations, par exemple la station SMC, est représenté à la figure 2. Les moyens de mise en oeuvre de l'invention sont intégrés dans un ordinateur, qui comporte des interfaces utilisateurs classiques, non décrits ici. En variante, les moyens de mise en oeuvre de l'invention ne sont pas intégrés à une station mobile proprement dite, mais ces moyens et la station mobile sont adaptés à communiquer et coopérer ensemble. An embodiment of any of the stations, for example the SMC station, is shown in FIG. 2. The means of implementing the invention are integrated into a computer, which comprises conventional user interfaces, not described. here. As a variant, the means of implementing the invention are not integrated into a mobile station proper, but these means and the mobile station are adapted to communicate and cooperate together.
La station SMC intègre une unité centrale de traitement sous la forme d'un processeur 10 relié par un bus d'une part à une mémoire morte (ROM) 30 dans laquelle sont enregistrés les programmes exécutés par le processeur et d'autre part à une mémoire vive (RAM) 20 comportant une zone de travail, des registres de données et une zone réservée au stockage des messages reçus ou en attente d'émission. La mémoire vive 20 stocke entre autres, un journal, exposé dans la suite, correspondant à la table des derniers messages reçus et entendus par la station mobile SMC. The SMC station integrates a central processing unit in the form of a processor 10 connected by a bus on the one hand to a read only memory (ROM) 30 in which the programs executed by the processor are recorded and on the other to a random access memory (RAM) 20 comprising a working area, data registers and an area reserved for storing messages received or awaiting transmission. The RAM 20 stores, among other things, a log, described below, corresponding to the table of the last messages received and heard by the mobile station SMC.
La station mobile SMC comporte un module de communication radiofréquences 50, connu en soi, permettant à la station mobile SMC d'émettre et de recevoir des données vers et depuis d'autres stations mobiles. The mobile station SMC comprises a radio frequency communication module 50, known per se, allowing the mobile station SMC to transmit and receive data to and from other mobile stations.
L'interface entre le module de communication radiofréquences 50 et le processeur 10 se fait par:
- le port de contrôle 15, dont la valeur binaire représente l'état d'occupation du support de transmission sans fil à un instant donné,
- le port de lecture 16, dans lequel le processeur 10 lit les données reçues par la station mobile SMC,
- le port d'écriture 17, où la station mobile SMC peut aller écrire les données qu'elle souhaite émettre via le support de transmission radiofréquences.The interface between the radio frequency communication module 50 and the processor 10 is done by:
the control port 15, the binary value of which represents the state of occupation of the wireless transmission medium at a given time,
the read port 16, in which the processor 10 reads the data received by the mobile station SMC,
- the write port 17, where the mobile station SMC can write the data it wishes to transmit via the radio frequency transmission medium.
Une horloge 40, reliée au processeur 10, permet à ce dernier de réaliser des opérations à intervalles réguliers, telles que par exemple, les opérations de lecture / écriture dans les ports 15, 16, 17. A clock 40, connected to the processor 10, allows the latter to perform operations at regular intervals, such as for example, the read / write operations in the ports 15, 16, 17.
La station mobile SMC permet aux utilisateurs du réseau local sans fil d'échanger des données le long de chemins pouvant varier dans le temps et pouvant emprunter plusieurs stations intermédiaires, ces chemins étant établis à partir de tables de routage des stations mobiles du réseau. The mobile station SMC allows users of the wireless local area network to exchange data along paths which can vary over time and which can borrow several intermediate stations, these paths being established from routing tables of the mobile stations of the network.
Pour mettre en oeuvre la fonction de routage, chaque station mobile a en mémoire une table de routage représentée à la figure 3. La table de routage TRC de la station SMC comporte une liste de chacune des stations accessibles à partir de la station considérée, la prochaine station à atteindre pour atteindre chacune des stations accessibles et le coût pour atteindre chacune des stations accessibles. Le coût est par exemple le nombre de sauts nécessaires, c'est-à-dire le nombre de segments à parcourir, pour atteindre chacune des stations accessibles. Selon des variantes de réalisation, le coût peut tenir compte par exemple du rapport signal à bruit, du niveau de réception des messages, des délais d'acheminement, ou du nombre de stations voisines de la station considérée, ou encore être une combinaison de ces paramètres. To implement the routing function, each mobile station has in memory a routing table represented in FIG. 3. The routing table TRC of the station SMC comprises a list of each of the stations accessible from the station considered, the next station to reach to reach each of the accessible stations and the cost to reach each of the accessible stations. The cost is for example the number of hops required, that is to say the number of segments to be traversed, to reach each of the accessible stations. According to alternative embodiments, the cost can take into account for example the signal to noise ratio, the level of reception of messages, the delivery times, or the number of stations neighboring the station considered, or even be a combination of these settings.
Ainsi, par exemple, il est possible d'atteindre la station SMe depuis la station SMC, la prochaine station étant SMd, et le coût, c'est-à-dire ici le nombre de sauts, étant de deux. Thus, for example, it is possible to reach the station SMe from the station SMC, the next station being SMd, and the cost, that is to say here the number of hops, being two.
La table de routage d'une station est valable à un instant donné, et est susceptible d'évoluer dans le temps. The routing table of a station is valid at a given time, and is likely to change over time.
D'autre part, la table de routage d'une station peut comporter d'autres informations, telles que numéro de séquence, drapeau, par exemple, qui ne sont pas utiles pour la présente invention. On the other hand, the routing table of a station can include other information, such as sequence number, flag, for example, which is not useful for the present invention.
Comme représenté à la figure 4, les données sont échangées entre stations sous la forme de message 60 comportant au moins les champs suivants:
- le champ 61 contenant l'adresse SEI de la station émettrice initiale du message,
- le champ 62 contenant l'adresse SDF de la station destinataire finale du message,
- le champ 63 contenant l'adresse SET de la station émettrice intermédiaire,
- le champ 64 contenant l'adresse SDT de la station destinataire intermédiaire,
- le champ 65 contenant un identificateur ID de message créé par la station émettrice initiale,
- le champ 66 contenant le coût CT du message, mis à jour par chaque station intermédiaire et par la station destinataire finale,
- le champ 67 de données proprement dites,
- le champ 68 contenant le type IT du message, ici message de données.As shown in FIG. 4, the data is exchanged between stations in the form of a message 60 comprising at least the following fields:
- field 61 containing the SEI address of the initial station transmitting the message,
field 62 containing the SDF address of the final destination station of the message,
- field 63 containing the SET address of the intermediate transmitting station,
- field 64 containing the SDT address of the intermediate destination station,
- field 65 containing an identifier message ID created by the initial transmitting station,
field 66 containing the cost CT of the message, updated by each intermediate station and by the final destination station,
- field 67 of data proper,
- field 68 containing the IT type of the message, here a data message.
Les stations émettrice initiale et destinataire finale sont les extrémités du chemin à parcourir par le message. Les stations émettrice intermédiaire et destinataire intermédiaire sont les extrémités d'un segment du chemin. The initial transmitting and final destination stations are the ends of the path to be covered by the message. The intermediate transmitting and intermediate receiving stations are the ends of a segment of the path.
Chacune des stations mémorise des données sur chacun des messages de données qu'elle entend, même pour les messages qui ne lui sont pas destinés. Ces données sont mémorisées dans une table spécifique, ou journal, dont la taille prédéterminée, correspondant à une fenêtre temporelle, est choisie en fonction d'un délai d'acheminement maximal de message dans le réseau. Comme représenté à la figure 5, pour chaque message de données entendu, la station SMd mémorise les données suivantes:
- le champ 71 contenant l'adresse SEI de la station émettrice initiale du message,
- le champ 72 contenant l'adresse SDF de la station destinataire finale du message,
- le champ 73 contenant l'adresse SET de la station émettrice intermédiaire,
- le champ 74 contenant l'adresse SDT de la station destinataire intermédiaire,
- le champ 75 contenant l'identificateur ID de message créé par la station émettrice initiale,
- le champ 76 contenant le coût CT du message, mis à jour par chaque station qui entend le message,
- le champ 77 contenant la date DT d'audition du message,
- le champ 78 contenant le nombre NR de retransmission.Each of the stations stores data on each of the data messages it hears, even for messages that are not intended for it. These data are stored in a specific table, or log, the predetermined size of which corresponds to a time window, is chosen as a function of a maximum message delivery time in the network. As shown in FIG. 5, for each data message heard, the station SMd stores the following data:
- field 71 containing the SEI address of the initial sending station of the message,
field 72 containing the SDF address of the final destination station of the message,
- field 73 containing the SET address of the intermediate transmitting station,
- field 74 containing the SDT address of the intermediate destination station,
- field 75 containing the identifier message ID created by the initial transmitting station,
the field 76 containing the cost CT of the message, updated by each station which hears the message,
- field 77 containing the date DT of hearing the message,
- field 78 containing the number NR of retransmission.
Les valeurs des six premiers champs sont déduites du message entendu et les deux demières sont mises à jour par la station SMd. La date d'audition DT et le nombre de retransmission NR ne sont pas utilisés par la présente invention et peuvent servir notamment à contrôler les délais d'acheminement et les retransmissions. Le coût CT est ici égal au nombre cumulé de tous les messages précédents ayant le même identificateur que le message considéré. The values of the first six fields are deduced from the message heard and the last two are updated by the station SMd. The date of hearing DT and the number of retransmission NR are not used by the present invention and can be used in particular to control the delivery times and retransmissions. The cost CT is here equal to the cumulative number of all the previous messages having the same identifier as the message considered.
La figure 6 représente un algorithme mis en oeuvre dans chacune des stations mobiles du réseau, lorsqu'un message de données est reçu, pour traiter ce message, et pour détecter s'il existe un chemin plus court. FIG. 6 represents an algorithm implemented in each of the mobile stations of the network, when a data message is received, to process this message, and to detect if there is a shorter path.
L'algorithme comporte des étapes E100 à E112 qui sont mémorisées en mémoire morte 30.The algorithm includes steps E100 to E112 which are stored in read-only memory 30.
L'étape E100 est la réception d'un message de données par la station mobile. Pour cela, le processeur 10 lit régulièrement le port 16 pour vérifier si le module radio 50 a reçu des données. Lorsqu'un message est reçu, le processeur lit le type de message dans le champ 68 indiquant qu'il s'agit d'un message de données. Step E100 is the reception of a data message by the mobile station. For this, the processor 10 regularly reads the port 16 to check whether the radio module 50 has received data. When a message is received, the processor reads the message type in field 68 indicating that it is a data message.
Après la réception d'un message de données, L'étape E100 est suivie de l'étape E101, qui est un test pour vérifier si le message correspond à un message déjà mémorisé dans le journal de la station. Le test consiste à comparer le couple formé de l'identificateur ID du message et de l'adresse SEI de la station émettrice initiale du message avec les couples formés d'identificateur de message et d'adresse de station émettrice initiale de message qui sont mémorisés dans le journal de la station considérée. After the reception of a data message, Step E100 is followed by step E101, which is a test to check whether the message corresponds to a message already stored in the station log. The test consists in comparing the pair formed of the identifier ID of the message and the address SEI of the initial sending station of the message with the pairs formed of message identifier and address of initial sending station of message which are memorized. in the journal of the station considered.
Si la réponse est négative, L'étape ElOl est suivie de l'étape E102 à laquelle les données relatives au message en cours de traitement sont mémorisées dans le joumal de la station. Les données mémorisées sont celles représentées à la figure 5. L'étape E102 comporte la mise à jour du coût. Dans le cas où le coût est le nombre de sauts, ou de segments parcourus, le coût mémorisé est égal au coût lu dans le champ 66 du message, incrémenté de une unité. L'étape E102 est suivie de l'étape E107 qui sera décrite dans la suite. If the answer is negative, step E101 is followed by step E102 in which the data relating to the message being processed are stored in the station log. The data stored is that shown in FIG. 5. Step E102 includes updating the cost. In the case where the cost is the number of hops, or of segments traveled, the stored cost is equal to the cost read in field 66 of the message, incremented by one. Step E102 is followed by step E107 which will be described below.
Si la réponse à l'étape E101 est positive, cela signifie qu'il y a correspondance entre le message en cours de traitement et un message précédemment reçu et mémorisé. L'étape E101 est alors suivie de l'étape E103 qui est un test pour vérifier si le message en cours de traitement et le message déjà mémorisé qui lui correspond ont été émis par la même station émettrice intermédiaire. Le test consiste à comparer l'adresse de station émettrice intermédiaire du message en cours de traitement avec celle, mémorisée dans le champ 73 respectif, du message qui lui correspond. Si la réponse est positive, cela signifie que le message en cours de traitement est une retransmission d'un message précédent, entre les mêmes stations émettrice et destinataire intermédiaires, cette retransmission étant provoquée par une absence de réception d'accusé de réception par la station émettrice intermédiaire. Les données relatives au message en cours de traitement ne sont pas mémorisées et le nombre de retransmission NR du message précédent est incrémenté de une unité. L'étape E103 est suivie de l'étape E107 qui sera décrite dans la suite
Si la réponse à l'étape E103 est négative, cela signifie que le message en cours de traitement et le message déjà mémorisé qui lui correspond ont été émis par deux stations émettrices intermédiaires distinctes.If the response to step E101 is positive, this means that there is a correspondence between the message being processed and a message previously received and stored. Step E101 is then followed by step E103 which is a test to check whether the message being processed and the already memorized message which corresponds to it have been transmitted by the same intermediate transmitting station. The test consists in comparing the address of the intermediate sending station of the message being processed with that, stored in the respective field 73, of the message which corresponds to it. If the response is positive, this means that the message being processed is a retransmission of a previous message, between the same intermediate sending and receiving stations, this retransmission being caused by an absence of receipt of acknowledgment by the station. intermediate transmitter. The data relating to the message being processed is not stored and the number of retransmission NR of the previous message is incremented by one. Step E103 is followed by step E107 which will be described below
If the response to step E103 is negative, this means that the message being processed and the already stored message which corresponds to it have been transmitted by two separate intermediate transmitting stations.
Cette étape est suivie de l'étape E104 à laquelle les données relatives au message en cours de traitement sont mémorisées dans le journal de la station, tel que représenté à la figure 5. L'étape E104 comporte la mise à jour du coût.This step is followed by step E104 in which the data relating to the message being processed is stored in the station log, as shown in FIG. 5. Step E104 includes updating the cost.
Dans le cas où le coût est le nombre de sauts, ou de segments parcourus, le coût mémorisé est égal au coût lu dans le champ 66 du message, incrémenté de une unité.In the case where the cost is the number of hops, or of segments traveled, the stored cost is equal to the cost read in field 66 of the message, incremented by one.
L'étape E104 est suivie de l'étape E105 qui est un test pour déterminer si la station considérée est la station destinataire intermédiaire du message en cours de traitement. Le test consiste à comparer l'adresse de la station et l'adresse SDT de station destinataire intermédiaire du message. Step E104 is followed by step E105 which is a test to determine if the station considered is the intermediate destination station of the message being processed. The test consists in comparing the address of the station and the SDT address of the intermediate destination station of the message.
Si la réponse est négative, I'exécution de l'algorithme est terminée. If the answer is negative, the execution of the algorithm is finished.
Le message n'est pas retransmis par la station, puisqu'elle n'est pas la station destinataire intermédiaire du message.The message is not retransmitted by the station, since it is not the intermediate destination station of the message.
Si la réponse à l'étape E105 est positive, cela signifie que le message en cours de traitement a d'une part été émis à destination de la station considérée, et que d'autre part il correspond à un message précédemment entendu par la station. Cela signifie que la station considérée peut être atteinte, depuis la station émettrice initiale du message en cours de traitement, par deux chemins distincts. Les chemins sont déterminés notamment par les stations émettrices intermédiaires, dont les adresses SET sont lues dans le journal. If the response to step E105 is positive, this means that the message being processed has on the one hand been sent to the station considered, and on the other hand it corresponds to a message previously heard by the station . This means that the station considered can be reached, from the initial sending station of the message being processed, by two separate paths. The paths are determined in particular by the intermediate transmitting stations, whose SET addresses are read in the newspaper.
Le coût respectif de chacun des chemins est connu. II est donc possible de déterminer le chemin présentant le plus faible coût, ce qui constitue une information de routage. Dans le cas où le coût est le nombre de segments parcourus, le message précédemment entendu par la station sera celui qui a été acheminé selon le chemin présentant le plus faible coût, c'est-à-dire le chemin le plus court. The respective cost of each path is known. It is therefore possible to determine the path having the lowest cost, which constitutes routing information. In the case where the cost is the number of segments traveled, the message previously heard by the station will be the one which has been routed according to the path presenting the lowest cost, that is to say the shortest path.
L'étape suivante E106 est l'envoi de l'information de routage déterminée à l'étape E105 vers une application de gestion de réseau. Cette application de gestion peut être intégrée à la station considérée, ou être localisée dans une station spécifique du réseau, ou encore dans une station de traitement ne faisant pas partie du réseau. Dans le dernier cas, la station de traitement peut être fixe, ou peut être reliée par une liaison filaire à l'une des stations du réseau. L'étape E106 est suivie de l'étape E108 qui sera décrite dans la suite. The next step E106 is the sending of the routing information determined in step E105 to a network management application. This management application can be integrated into the station considered, or be located in a specific station of the network, or even in a processing station not forming part of the network. In the latter case, the processing station can be fixed, or can be connected by a wired link to one of the stations on the network. Step E106 is followed by step E108 which will be described below.
En variante, l'information de routage est également formée et envoyée vers l'application de gestion de réseau, même dans le cas où le message en cours de traitement n'a pas été émis à destination de la station considérée. As a variant, the routing information is also formed and sent to the network management application, even in the case where the message being processed has not been sent to the station in question.
Les étapes E102 et E103 sont suivies de l'étape E107 qui est identique à l'étape E105 précédemment décrite. L'étape E107 est un test pour déterminer si la station considérée est la station destinataire intermédiaire du message en cours de traitement. Le test consiste à comparer l'adresse de la station et l'adresse SDT de station destinataire intermédiaire du message en cours de traitement. Steps E102 and E103 are followed by step E107 which is identical to step E105 previously described. Step E107 is a test to determine whether the station considered is the intermediate destination station of the message being processed. The test consists in comparing the address of the station and the SDT address of the intermediate destination station of the message being processed.
Si la réponse est négative, l'exécution de l'algorithme est terminée. If the answer is negative, the execution of the algorithm is finished.
Si la réponse est positive, l'étape E107 est suivie de l'étape E108 qui est l'envoi d'un message d'accusé de réception à destination de la station émettrice intermédiaire du message en cours de traitement. If the response is positive, step E107 is followed by step E108 which is the sending of an acknowledgment message to the intermediate transmitting station of the message being processed.
L'étape suivante E109 est un test pour déterminer si la station considérée est la station destinataire finale du message en cours de traitement. The next step E109 is a test to determine whether the station considered is the final destination station of the message being processed.
Le test consiste à comparer l'adresse de la station et l'adresse SDF de station destinataire finale du message.The test consists in comparing the address of the station and the SDF address of the final destination station of the message.
Si la réponse est positive, l'acheminement du message est terminé, et l'étape E109 est suivie de l'étape E110 qui est la transmission des données contenues dans le champ de données 67 du message vers la couche applicative de la station pour traiter les informations reçues. If the response is positive, the routing of the message is finished, and step E109 is followed by step E110 which is the transmission of the data contained in the data field 67 of the message to the application layer of the station for processing. the information received.
Si la réponse à l'étape E109 est négative, cette étape est suivie de l'étape El Il qui est la consultation de la table de routage de la station considérée, pour déterminer quelle est la station destinataire intermédiaire vers laquelle la station considérée doit envoyer un message contenant les données à acheminer, en fonction de la station destinataire finale du message. If the response to step E109 is negative, this step is followed by step E11 which is the consultation of the routing table of the station considered, to determine which is the intermediate destination station to which the station considered must send. a message containing the data to be sent, depending on the final destination station of the message.
L'étape suivante E112 est la formation d'un message et l'envoi de ce message vers la station destinataire intermédiaire précédemment déterminée, dont l'adresse est écrite dans le champ 64 de ce nouveau message. L'adresse SEI de la station émettrice initiale, L'adresse SDF de station destinataire finale,
I'identificateur ID de message et les données proprement dites de ce nouveau message sont recopiés dans les champs correspondants du message en cours de traitement. Le coût CT est mis à jour par la station considérée. L'adresse
SET de la station émettrice intermédiaire de ce nouveau message est celle de la station considérée.The next step E112 is the formation of a message and the sending of this message to the previously determined intermediate destination station, the address of which is written in field 64 of this new message. The SEI address of the initial transmitting station, The SDF address of the final destination station,
The message ID identifier and the actual data of this new message are copied into the corresponding fields of the message being processed. The CT cost is updated by the station considered. The address
SET of the intermediary transmitting station of this new message is that of the station considered.
En référence à nouveau à la figure 1, on suppose que des données sont à émettre depuis la station SMa (station émettrice initiale) à destination de la station SMe (station destinataire finale). Ces données sont mises sous la forme d'un message émis sur le segment "ab", qui va ensuite provoquer l'émission de messages, contenant les mêmes données, successivement sur les segments "bc", "cd" et "de", selon les tables de routage des stations concernées. Les stations SMa, SMb, SMC, SMd sont successivement stations émettrices intermédiaires, et les stations SMb, SMC, SMd et SMe sont successivement stations destinataires intermédiaires. Referring again to FIG. 1, it is assumed that data is to be transmitted from the station SMa (initial transmitting station) to the station SMe (final destination station). These data are put in the form of a message sent on the segment "ab", which will then cause the emission of messages, containing the same data, successively on the segments "bc", "cd" and "of", according to the routing tables of the stations concerned. The stations SMa, SMb, SMC, SMd are successively intermediate transmitting stations, and the stations SMb, SMC, SMd and SMe are successively intermediate destination stations.
Lorsque la station SMb émet le message à destination de la station SMC, on suppose que la station SMd entend le message et le mémorise dans son journal. When the station SMb transmits the message to the station SMC, it is assumed that the station SMd hears the message and stores it in its log.
Lorsque la station SMC émet à son tour le message vers la station
SMd, celle-ci détermine que ce message correspond à un message déjà entendu et mémorisé. La station SMd a ainsi déterminé qu'il existe un chemin plus court entre elle-même et les stations SM a et SMb, ce chemin empruntant le segment "bd".When the SMC station in turn transmits the message to the station
SMd, this determines that this message corresponds to a message already heard and stored. The station SMd has thus determined that there is a shorter path between itself and the stations SM a and SMb, this path taking the segment "bd".
Cette information de routage peut être exploitée par une couche applicative. Par exemple, lors de la mise en place d'un réseau de stations dans des locaux, I'invention permet de déterminer des emplacements préférés des stations, ou du moins de leur partie émission/réception, dans le but de favoriser la fluidité et la rapidité des échanges de données. II est ainsi possible de raccourcir les chemins en en diminuant le nombre de segments, ou encore d'éviter qu'une station donnée soit un point de passage obligé d'un trop grand nombre de chemin. This routing information can be used by an application layer. For example, when setting up a network of stations in premises, the invention makes it possible to determine the preferred locations of the stations, or at least of their transmission / reception part, with the aim of promoting fluidity and speed of data exchange. It is thus possible to shorten the paths by reducing the number of segments, or even to avoid that a given station is a forced crossing point with too many paths.
La connaissance des chemins dans le réseau permet par exemple de choisir la disposition d'antennes d'émission/réception, ce qui permet d'optimiser la couverture radio du réseau. Le procédé peut être mis en oeuvre à chaque fois que l'on souhaite vérifier la topologie du réseau. Knowledge of the paths in the network makes it possible, for example, to choose the arrangement of transmit / receive antennas, which allows the radio coverage of the network to be optimized. The method can be implemented each time it is desired to check the network topology.
Bien entendu, la présente invention n'est nullement limitée aux modes de réalisation décrits et représentés, mais englobe, bien au contraire, toute variante à la portée de l'homme du métier. Of course, the present invention is not limited to the embodiments described and shown, but encompasses, quite the contrary, any variant within the reach of ordinary skill in the art.
Notamment, I'invention s'applique à tout type de réseau distribué comportant des stations mobiles. A titre d'exemple, une constellation de satellites en orbite basse (non géostationnaires) peut constituer un tel réseau. In particular, the invention applies to any type of distributed network comprising mobile stations. For example, a constellation of satellites in low orbit (not geostationary) can constitute such a network.
Le routage des communications entre ces satellites peut être analysé par la présente invention The routing of communications between these satellites can be analyzed by the present invention
Claims (10)
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FR9713784A FR2770714A1 (en) | 1997-11-03 | 1997-11-03 | PATH DETECTION IN A DISTRIBUTED NETWORK |
| EP98402690A EP0935368A1 (en) | 1997-11-03 | 1998-10-28 | Path detection in a distributed network |
| US09/184,657 US6535488B1 (en) | 1997-11-03 | 1998-11-03 | Path detection in a distributed network |
| JP31363598A JPH11234307A (en) | 1997-11-03 | 1998-11-04 | Method of setting message path in distributed network and network communication station |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| FR9713784A FR2770714A1 (en) | 1997-11-03 | 1997-11-03 | PATH DETECTION IN A DISTRIBUTED NETWORK |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| FR2770714A1 true FR2770714A1 (en) | 1999-04-30 |
Family
ID=9512964
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| FR9713784A Pending FR2770714A1 (en) | 1997-11-03 | 1997-11-03 | PATH DETECTION IN A DISTRIBUTED NETWORK |
Country Status (1)
| Country | Link |
|---|---|
| FR (1) | FR2770714A1 (en) |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO1996019887A1 (en) * | 1994-12-19 | 1996-06-27 | Salbu Research And Development (Proprietary) Limited | Multi-hop packet radio networks |
| WO1997002677A2 (en) * | 1995-07-03 | 1997-01-23 | Philips Electronics N.V. | Building management system with packet hopping communication |
-
1997
- 1997-11-03 FR FR9713784A patent/FR2770714A1/en active Pending
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO1996019887A1 (en) * | 1994-12-19 | 1996-06-27 | Salbu Research And Development (Proprietary) Limited | Multi-hop packet radio networks |
| WO1997002677A2 (en) * | 1995-07-03 | 1997-01-23 | Philips Electronics N.V. | Building management system with packet hopping communication |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6459685B1 (en) | Reduction of the message traffic in a distributed network | |
| EP2235890B1 (en) | Ip communication system between the ground and a vehicle | |
| US6535488B1 (en) | Path detection in a distributed network | |
| EP3549352B1 (en) | Electricity metering device comprising a powerline interface and at least a radiofrequency interface. | |
| WO2009007563A1 (en) | Method of communication between a source node and a destination node, the nodes belonging to a vehicular network | |
| EP3804408A1 (en) | Method of selecting a route in an ad hoc network | |
| EP0786916A1 (en) | Method for updating data between subscriber cards in a cellular radio communication system and terminals therefor | |
| EP2172074B1 (en) | Access point and node for controlling routing in a hybrid network | |
| EP0692891A1 (en) | System and equipment for the interconnection of LAN's using a source routing protocol | |
| WO2008037916A1 (en) | Method for evaluating the reliability of a route in a cooperative network | |
| EP1122919A1 (en) | Routing method for ad hoc networks | |
| EP3675562B1 (en) | Data processing methods in an ad hoc radio communication network, associated mobile radio communication stations and computer programs | |
| EP3934108A1 (en) | Method for determining a mode for communication between two neighbouring devices of a network | |
| FR2770714A1 (en) | PATH DETECTION IN A DISTRIBUTED NETWORK | |
| FR2770713A1 (en) | PATH DETECTION IN A DISTRIBUTED NETWORK | |
| EP2232816B1 (en) | Management of a communication in a heterogeneous network | |
| FR2770715A1 (en) | LINK BREAK DETECTION IN A DISTRIBUTED NETWORK | |
| FR2883440A1 (en) | METHOD AND EQUIPMENT FOR DATA TRANSMISSION BY AD HOC NETWORK | |
| EP2039208B1 (en) | Scheduling of terminals for sending data to a terminal on an hsdpa channel via several base stations | |
| FR2839407A1 (en) | METHOD AND DEVICE FOR ADJUSTING THE MAXIMUM SIZE OF INFORMATION SEQUENCES TRANSMITTED IN A TELECOMMUNICATIONS NETWORK | |
| FR3112255A1 (en) | PROCESS FOR SELECTING A COMMUNICATION ROUTE | |
| FR2818058A1 (en) | Mobile data distribution system for vehicle fleets selects long range route to cluster with internal LAN. | |
| FR3141586A1 (en) | METHOD AND DEVICE FOR MANAGING MESSAGES BROADCAST IN A LOCAL NETWORK | |
| FR3109852A1 (en) | METHOD AND DEVICE FOR RELAYING A MESSAGE RECEIVED FROM A FIRST DEVICE BY A SECOND NODE DEVICE TO A THIRD NODE DEVICE | |
| FR3002101A1 (en) | LOCATION OF MOBILE TERMINALS |