Path detection in a distributed network

Details Path detection in a distributed network Path detection in a distributed network

1998-11-03

2003-03-18

Cangialosi, Salvatore (Department: 2661)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S238100

Reexamination Certificate

active

06535488

ABSTRACT:

The present invention concerns the routing of communications between the stations of a distributed type network.
The network is for example a local wireless network, the stations of which communicate with one another by sharing a radio channel.
A distributed type network does not have a base station to manage the communications between the stations. A routing function makes communications possible between the stations of the network, by determining the communication paths in the network. This function is adapted to the constraints of a local wireless network, notably the limited passband, and the mobility of the stations or alterations in the station environment which produce changes in the network topology.
Known routing methods are based on periodic exchanges of routing messages in order 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, otherwise the risk of faulty routing and loss of messages is great. It is therefore necessary for the routing messages to be frequent.
However, the routing messages occupy the radio channel, to the detriment of useful data. The routing function must therefore generate as few routing messages as possible, in order to occupy little passband.
These constraints are conflicting and make the operation of the routing function complex.
The present invention aims to remedy the drawbacks of the prior art, firstly by providing a method of path detection in a distributed network, which makes it possible to detect new paths quickly and with no increase in routing traffic.
To this end, the invention proposes a method of message routing between stations of a network, characterised in that each of the stations performs the following operations:
storage of data concerning each message it receives and including at least a message identifier, an identifier of the sending station of the message and a message transmission cost,
and, after having stored the data of two messages whose message identifiers are identical and sending station identifiers are different,
comparison of the transmission costs of the two messages in order to determine the sending station associated with the lowest cost.
The method according to the invention resolves the problem stated above, by using the data messages transported in the network in order to derive therefrom routing information.
The data storage is carried out in a specific table, or log, intended to gather information on the messages heard by the station under consideration.
The method makes it possible to evaluate the performance of the current routing algorithm.
The method is adapted to any known routing function, the execution of which is independent of the method according to the invention.
According to a preferred characteristic, the method includes the transmission of the routing information formed by the knowledge of the sending station associated with the lowest cost to a processing station, which then uses this information.
According to a preferred characteristic, the cost is the cumulative number of all the previous messages having the same message identifier as the message under consideration. In other words, the cost is the number of jumps made from an initial message sending station, and thus measures a path length.
According to another preferred characteristic, the message identifier includes the address of the initial sending station of the first of the previous messages having the same message identifier as the message under consideration. The messages are thus identified simply and reliably.
The invention also concerns a network communication station, characterised in that it includes, or in that it is adapted to cooperate with:
means of storing data concerning each message it receives, these data including at least a message identifier, an identifier of the sending station of the message and a message transmission cost,
means of checking that the data of two messages whose message identifiers are identical and sending station identifiers are different, have been stored, and
means of comparing the transmission costs of two messages whose message identifiers are identical and whose sending station identifiers are different, in order to determine the sending station associated with the lowest cost.
The station according to the invention has the same advantages as those of the method which were described previously.
Secondly, the present invention providing a method of path detection and transmission of routing information in a distributed network, which makes it possible to detect new paths and transmit the corresponding information, quickly and with no increase in routing traffic.
To this end, the invention proposes a method of message routing between stations of a network, characterised in that any station under consideration performs the following operations:
storage of data concerning each message it receives and including at least a message identifier, an identifier of the sending station of the message and a message transmission cost,
and, after having stored the data of at least two messages whose message identifiers are identical and sending station identifiers are different,
sending of a specific message which includes on the one hand an acknowledgement intended for one of the sending stations of the said at least two messages and on the other hand routing data intended for at least the other of the sending stations of the said at least two messages.
The method according to the invention solves the problem stated above, by using the data messages transported in the network to derive routing information from these which is then transmitted to other stations of the network.
The specific message is not an additional message, but rather an acknowledgement message supplemented by routing information. The traffic is thus not increased, since an acknowledgement is always sent in the case of point-to-point transmission.
The data storage is carried out in a specific table, or log, intended to gather information on the messages heard by the station under consideration.
The method is adapted to any known routing function, the execution of which is independent of the method according to the invention.
The method makes it possible to modify the routing tables of stations of the network very quickly, independently of the periodicity of execution of the routing algorithm.
By virtue of the method according to the invention, the mobile stations know the alterations in the paths in the network. Taking these alterations into account to modify their routing table, the mobile stations can transport the messages by shorter paths, the consequence of which is to decrease the transportation times of the messages in the network.
According to preferred characteristics, the routing data include at least the address of the station under consideration, the address of a final destination station of the said at least two messages, and a cost of transmission between the station under consideration and the final destination station of the said at least two messages, or the routing data include even the whole routing table of the station under consideration.
These data make it possible to modify the routing table of the destination station of the routing data.
According to a preferred characteristic, the message identifier includes the address of the initial sending station of the first of a set of previous messages having the same message identifier as the said at least two messages. The messages are thus identified simply and reliably.
According to a preferred characteristic, the station for which the acknowledgement is intended sent one of the said at least two messages, this message being addressed to the station under consideration. The invention thus allows conventional processing of this part of the specific message.
According to another aspect, the invention proposes a method of message routing between stations of a network, the stations each having a respective rou

Affiliated with

Also associated with

Rating

Path detection in a distributed network does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Path detection in a distributed network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Path detection in a distributed network will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3014511