Path detection in a distributed network

• US 6,535,488 B1
• Filed: 11/03/1998
• Issued: 03/18/2003
• Est. Priority Date: 11/03/1997
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Mahe, Jean-Michel
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US09/184,657
• Time in Patent Office: 1,596 Days
• Field of Search: 370/238, 370/238.1, 455/422, 455/428, 379/114.02
• US Class Current: 370/238
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/26 Route discovery packet

Abstract

A method of routing messages between stations of a network is characterised in that each of the stations performs the following operations: storage (E104, E102) of data concerning each message which it receives and including at least one message identifier (ID, ISS), an identifier (TSS) for the station sending the message, and a message transmission cost (CT), and, after having stored the data of two messages whose message identifiers (ID, ISS) are identical and whose sending station identifiers (TSS) are different, comparison of the transmission costs (CT) of the two messages in order to determine the sending station associated with the lowest cost. The invention makes it possible to detect paths in the network.

Claims

1. A method of message routing between stations of a network, wherein each of the stations performs the method, the method comprising the steps of:

storing data concerning each message the station receives, including at least a message identifier, an identifier of a sending station of the message, and a message transmission cost, the message transmission cost being a number of stations which have relayed the message; and

after having stored the data of two messages whose message identifiers are identical and whose sending station identifiers are different, comparing transmission costs of the two messages in order to determine the sending station associated with the lowest cost.

2. The method according to claim 1, further comprising the step of transmitting the information about the sending station associated with the lowest cost to a processing station.

3. The method according to claim 1, wherein the message identifier includes an address of an initial sending station of a first of previous messages having the same message identifier as the message under consideration.

4. A method of message routing between stations of a network, wherein any station under consideration performs the method, the method comprising the steps of:

storing data concerning each message the station receives, including at least a message identifier, an identifier of a sending station of the message, and a message transmission cost, the message transmission cost being a number of stations which have relayed the message; and

after having stored the data of at least two messages whose message identifiers are identical and whose sending station identifiers are different, sending a specific message which includes an acknowledgment intended for one of the sending stations of the at least two messages and routing data intended for at least the other of the sending stations of the at least two messages.

5. The method according to claim 4, wherein the routing data includes at least an address of the station under consideration, an address of a final destination station of the at least two messages, and a cost of transmission between the station under consideration and a final destination station of the at least two messages.

6. The method according to claim 4, wherein the routing data includes a routing table of the station under consideration.

7. The method according to claim 4, wherein the message identifier includes an address of an initial sending station of a first of a set of previous messages having the same message identifier as the at least two messages.

8. The method according to claim 4, wherein the station for which the acknowledgment is intended sent one of the at least two messages, the message being addressed to the station under consideration.

9. A method of message routing between stations of a network, the stations each having a respective routing table, wherein any station under consideration performs the method when it receives a specific message including an acknowledgment intended for one station and routing data intended for at least one other station, the method comprising the steps of:

ascertaining whether the station under consideration is a destination of the routing data of the specific message; and

if a result of the ascertaining step is positive, modifying the routing table of the station under consideration according to the routing data of the specific message.

10. A network communication station, comprising:

means for storing data concerning each message the station receives, the data including at least a message identifier, an identifier of a sending station of the message, and a message transmission cost, the message transmission cost being a number of stations which have relayed the message;

means for checking whether the data of two messages whose message identifiers are identical and whose sending station identifiers are different have been stored; and

means for comparing the transmission costs of two messages whose message identifiers are identical and whose sending station identifiers are different, in order to determine a sending station associated with a lowest cost.

11. The station according to claim 10, further comprising means adapted to transmit information about the sending station associated with the lowest cost to a proccessing station.

12. A network communication station that is adapted to cooperate with communication means, the communication means comprising:

means for storing data concerning each message the communication means receives, the data including at least a message identifier, an identifier of a sending station of the message, and a message transmission cost, the message transmission cost being a number of stations which have relayed the message;

means for checking whether the data of two messages whose message identifiers are identical and whose sending station identifiers are different have been stored; and

means for comparing the transmission costs of two messages whose message identifiers are identical and whose sending station identifiers are different, in order to determine a sending station associated with a lowest cost.

13. The station according to claim 12, wherein the communication means further comprises means for transmitting information on the sending station associated with the lowest cost to a processing station.

14. A network communication station, comprising:

means for storing data concerning each message the station receives, including at least a message identifier, an identifier of a sending station of the message, and a message transmission cost, the message transmission cost being a number of stations which have relayed the message;

means for checking whether the data of at least two messages have been stored whose message identifiers are identical and whose sending station identifiers are different; and

means for sending a specific message which includes an acknowledgment intended for one of the sending stations of the at least two messages and routing data intended for at least the other of the sending stations of the at least two messages.

16. The station according to claim 14, wherein the sending means is adapted to form the specific message, routing data of which includes at least an address of the station, an address of a final destination station of the at least two messages, and a cost of transmission between the station and the final destination station of the at least two messages.

17. The station according to claim 14, wherein the sending means is adapted to form the specific message, the routing data of which includes a routing table of the station.

15. A network communication station that is adapted to cooperate with communication means, the communication means comprising:

means for storing data concerning each message it receives, including at least a message identifier, an identifier of a sending station of the message, and a message transmission cost, the message transmission cost being a number of stations which have relayed the message;

means for checking whether the data of at least two messages have been stored whose message identifiers are identical and whose sending station identifiers are different; and

means for sending a specific message which includes an acknowledgment intended for one of the sending stations of the at least two messages and routing data intended for at least the other of the sending stations of the at least two messages.

18. A network communication station including a respective routing table for transporting messages between stations of a network, comprising:

means for receiving a specific message which includes an acknowledgment intended for one station and routing data intended for at least one other station;

means for ascertaining whether the station is a destination of the routing data of the specific message; and

means for modifying the routing table of the station according to the routing data of the specific message, wherein the routing table is modified in a case where a positive result is obtained by the ascertaining means.

19. A network communication station including a respective routing table for transporting messages between stations of a network, the station being adapted to cooperate with communication means, the communication means comprising:

means for receiving a specific message including an acknowledgment intended for one station and routing data intended for at least one other station;

means for ascertaining whether the station is a destination of the routing data of the specific message; and

means for modifying the routing table of the station according to the routing data of the specific message, wherein the routing table is modified in a case where a positive result is obtained by the ascertaining means.

20. A storage medium storing a program for message routing between stations of a network, said program being performed by each of the stations, the program comprising the steps of:

storing data concerning each message the station receives, including at least a message identifier, an identifier of a sending station of the message, and a message transmission cost, the message transmission cost being a number of stations which have relayed the message; and

after having stored the data of two messages whose message identifiers are identical and whose sending station identifiers are different, comparing the transmission costs of the two messages in order to determine a sending station associated with a lowest cost.

21. The storage medium according to claim 20, wherein said storage medium is detachably mountable on a network communication station, wherein said network communication station comprises:

means for storing data concerning each message the station receives, the data including at least a message identifier, an identifier of a sending station of the message, and a message transmission cost, the message transmission cost being a number of stations which have relayed the message;

means for checking whether the data of two messages whose message identifiers are identical and whose sending station identifiers are different have been stored; and

means for comparing the transmission costs of two messages whose message identifiers are identical and whose sending station identifiers are different, in order to determine a sending station associated with a lowest cost.

26. The storage medium according to claim 20, wherein said storage medium is a floppy disk or a CD-ROM.

22. A storage medium storing a program for routing messages between stations of a network, said program being performed by any station under consideration, the program comprising the steps of:

storing data concerning each message the station receives, including at least a message identifier, an identifier of a sending station of the message, and a message transmission cost, the message transmission cost being a number of stations which have relayed the message; and

after having stored the data of at least two messages whose message identifiers are identical and whose sending station identifiers are different, sending a specific message which includes an acknowledgment intended for one of the sending stations of the at least two messages and routing data intended for at least the other of the sending stations of the at least two messages.

23. The storage medium according to claim 22, wherein said storage medium is detachably mountable on a network communication station, wherein said network communication station comprises:

means for storing data concerning each message the station receives, including at least a message identifier, an identifier of a sending station of the message, and a message transmission cost, the message transmission cost being a number of stations which have relayed the message;

means for checking whether the data of at least two messages have been stored whose message identifiers are identical and whose sending station identifiers are different; and

means for sending a specific message which includes an acknowledgment intended for one of the sending stations of the at least two messages and routing data intended for at least the other of the sending stations of the at least two messages.

24. A storage medium storing a program for routing messages between stations of a network, the stations each having a respective routing table, said program being performed when any station under consideration receives a specific message including an acknowledgment intended for one station and routing data intended for at least one other station, the program comprising the steps of:

ascertaining whether the station under consideration is a destination of the routing data of the specific message; and

in a case where a positive result is ascertained, modifying the routing table of the station under consideration according to the routing data of the specific message.

25. The storage medium according to claim 24, wherein said storage medium is detachably mountable on a network communication station including a respective routing table for transporting messages between stations of the network, wherein said network communication station comprises:

means for receiving a specific message including an acknowledgment intended for one station and routing data intended for at least one other station;

means for ascertaining whether the station is a destination of the routing data of the specific message; and

means for modifying the routing table of the station according to the routing data of the specific message, wherein the routing table is modified in a case where a positive result is obtained by the ascertaining means.