Reduction of the message traffic in a distributed network

• US 6,459,685 B1
• Filed: 11/02/1998
• Issued: 10/01/2002
• 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): Nguyen, Chau
• Assistant Examiner(s): LEE, CHI HO A
• Application Number:
  US09/184,034
• Time in Patent Office: 1,429 Days
• Field of Search: 370/255, 370/202, 370/396, 370/254, 370/312, 370/389, 370/381, 370/428, 370/471, 370/474, 370/382, 370/392, 370/400, 370/401, 370/238, 370/465, 370/313, 370/338, 370/328, 370/349, 370/445, 370/213, 379/220
• US Class Current: 370/313
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 12/189 in combination with wireless systems selective distribution or broadcast in wireless communication networks H04W4/06
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04W 28/06 Optimizing the usage of the radio link, e.g. header compression, information sizing , discarding information system modifying transmission characteristic according to link quality by modifying frame length H04L1/0007; dynamic adaptation of the packet size for flow control or congestion control H04L47/365
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user

Abstract

Messages are broadcast between a plurality of stations in a wireless network where each station has a memory storing a respective first table containing identifiers of final destination stations of messages associated with identifiers of intermediate destination stations of messages, wherein any station under consideration broadcasts a message when it receives a message. Data relating to a received message, including at least one message identifier and an identifier of a station sending the message, is stored in a second table. The message identifier is compared with message identifiers previously stored in the second table. In the first table of the station under consideration, a group of stations which are both a final destination station and an intermediate destination station are sought, and a second message is broadcast over the wireless network in a case where the identifier of the received message is different from the message identifiers previously stored in the second table and where the group includes at least one station different from the station which sent the message.

Claims

1. A method of broadcasting messages between a plurality of stations in a wireless network, each station having a memory storing a respective first table containing identifiers of final destination stations of messages associated with identifiers of intermediate destination stations of messages, wherein any station under consideration performs the method when it receives a message, the method comprising the steps of:

storing, in a second table, data relating to a received message including at least one message identifier and an identifier of a station sending the message;

comparing the message identifier with message identifiers previously stored in the second table;

seeking, in the first table of the station under consideration, a group of stations which are both a final destination station and an intermediate destination station; and

broadcasting over the wireless network a second message in a case where the identifier of the received message is different from the message identifiers previously stored in the second table and where the group includes at least one station different from the station which sent the message.

2. A method according to claim 1, wherein the second message has a message identifier corresponding to the received message and an intermediate sending station address corresponding to the station under consideration.

3. A method according to claim 1, wherein the message identifier of the second message includes an address of an initial sending station for a first of a set of previous messages having the same message identifier as the received message.

4. A communication station in a wireless network, having a memory storing a respective first table containing identifiers of final destination stations of messages associated with identifiers of intermediate destination stations for messages, comprising:

means of storing in a second table, data relating to a received message including at least one message identifier and an identifier of a station sending the message;

means of comparing the message identifier of the received message with message identifiers previously stored in the second table;

means of seeking in the first table a group of stations which are both a final destination station and an intermediate destination station; and

means of broadcasting over the wireless network a second message in a case where the identifier of the received message is different from the identifiers previously stored in the second table and where the group includes at least one station different from a station which sent the received message.

5. A communication station according to claim 4, wherein the second message has a message identifier corresponding to the received message and an intermediate sending station address corresponding to the communication station.

6. A communication station in a wireless network, comprising:

a memory storing a respective first table containing identifiers of final destination stations of messages associated with identifiers of intermediate destination stations for messages,

wherein, the communication station is adapted to cooperate with;

means of storing in a second table, data relating to a received message including at least one message identifier and an identifier of a station sending the message;

means of comparing the message identifier of the received message with message identifiers previously stored in the second table;

means of seeking in the first table a group of stations which are both a final destination station and an intermediate destination station; and

means of broadcasting over the wireless network a second message in a case where the identifier of the received message is different from the identifiers previously stored in the second table and where the group includes at least one station different from the station which sent the received message.

7. A method of routing messages between a plurality of stations in a wireless network, each station having a memory storing a respective first table containing identifiers of final destination stations of messages respectively associated with identifiers of intermediate destination stations of messages, wherein any station under consideration performs the method when it receives a data message, the method comprising the steps of:

storing, in a respective second table, data concerning the received message, including at least one message identifier, an intermediate sending station identifier identifying an intermediate sending station from which the received message was sent, an intermediate destination station identifier identifying an intended intermediate destination station, a final destination station identifier, and a message retransmission number (NR); and

wherein, in a case where the message retransmission number reaches a predetermined value, the station under consideration is not the intended intermediate destination station, and the station under consideration has in its first table a final destination station identifier associated with an intermediate destination station identifier different from that of the intermediate sending station,

sending a specific routing message, over the wireless network, intended for the intermediate sending station in order to indicate the existence of a path between the station under consideration and the final destination station.

8. A method according to claim 7, wherein the specific routing message includes at least an address of the station under consideration, an address of the final destination station of the received message, and a cost of transmission between the station under consideration and the final destination station for the message.

9. A method according to claim 7, wherein the specific message contains the first table of the station under consideration.

10. A method according to claim 7, wherein the message identifier includes an address of the initial sending station for a first of a set of previous messages having the same message identifier as the received message.

11. A communication station in a wireless network, having a memory for storing a respective first table containing identifiers of final destination stations of messages respectively associated with identifiers of intermediate destination stations of messages, comprising:

means of storing, in a respective second table, data concerning received messages, the data for each received message including at least one message identifier, an intermediate sending station identifier identifying an intermediate sending station, an intermediate destination station identifier identifying an intended intermediate destination station, a final destination station identifier identifying a final destination station, and a message retransmission number;

means of checking whether the message retransmission number (NR) has reached a predetermined value, whether the communication station is the intended intermediate destination station, and whether the communication station has in its first table a final destination station identifier associated with an intermediate destination station identifier which is different from that of the intermediate sending station; and

means of sending over the wireless network a specific routing message destined for the intermediate sending station in order to indicate the existence of a path between the communication station and the final destination station.

12. A communication station according to claim 11, wherein the sending means are adapted to form the specific routing message so that it includes at least an address of the communication station, an address of the final destination station of the received message, and a cost of transmission between the communication station and the final destination station of the received message.

13. A communication station according to claim 11, wherein the sending means are adapted to form the specific routing message so that it includes the first table of the communication station.

14. A communication station in a wireless network, comprising:

a memory, for storing a respective first table containing identifiers of final destination stations of messages respectively associated with identifiers of intermediate destination stations of messages,

wherein the communication station is adapted to cooperate with;

means of storing, in a respective second table, data concerning received data messages, the data including at least one message identifier, an intermediate sending station identifier identifying an intermediate sending station, an intermediate destination station identifier identifying an intended intermediate destination station, a final destination station identifier identifying a final destination station, and a message retransmission number;

means of checking whether the message retransmission number has reached a predetermined value, whether the communication station is not the intended intermediate destination station, and whether the communication station has in its first table a final destination station identifier associated with an intermediate destination station identifier which is different from that of the intermediate sending station; and

means of sending over the wireless network a specific routing message destined for the intermediate sending station in order to indicate the existence of a path between the communication station and the final destination station.

15. A storage medium storing a program for broadcasting messages between a plurality of stations in a wireless network, each station having a memory storing a respective first table containing identifiers of final destination stations of messages associated with identifiers of intermediate destination stations of messages, said program comprising executable-process steps to be performed for any station under consideration receiving a message, the executable process steps comprising:

storing, in a second table, data relating to a received message, including at least one message identifier and an identifier of a station sending the received message;

comparing the message identifier with message identifiers previously stored in the second table;

seeking, in the first table of the station under consideration, a group of stations which are both a final destination station and an intermediate destination station; and

broadcasting a second message over the wireless network in a case where the identifier of the received message is different from the identifiers previously stored in the second table and where the group includes at least one station different from the station which sent the message.

16. A storage medium according to claim 15, wherein said storage medium is a floppy disk or a CD-ROM.

17. A storage medium detachably mountable on a communication station in a wireless network having a memory storing a respective first table containing identifiers of final destination stations of messages associated with identifiers of intermediate destination stations for messages, said station comprising:

means of storing, in a second table, data relating to a received message including at least one message identifier, and an identifier of a station sending the received message;

means of comparing the message identifier with message identifiers previously stored in the second table;

means of seeking, in the first table, a group of stations which are both a final destination station and an intermediate destination station; and

means of broadcasting a second message over the wireless network in a case where the identifier of the received message is different from the identifiers previously stored in the second table and where the group includes at least one station different from the station which sent the message.

18. A storage medium storing a program for routing messages between a plurality of stations in a wireless network, each station having a memory storing a respective first table containing identifiers of final destination stations of messages respectively associated with identifiers of intermediate destination stations of messages, said program performing executable process steps in a case where any station under consideration receives a data message, the executable process steps comprising:

storing, in a respective second table, data concerning the received message including at least one message identifier, an intermediate sending station identifier identifying an intermediate sending station, an intermediate destination station identifier identifying an intermediate destination station, a final destination station identifier identifying a final destination station, and a message retransmission number; and

in a case where the message retransmission number reaches a predetermined value, the station under consideration is not the intermediate destination station, and the station under consideration has in its first table a final destination station identifier associated with an intermediate destination station identifier different from that of the intermediate sending station,

sending a specific routing message, over the wireless network, intended for the intermediate sending station in order to indicate the existence of a path between the station under consideration and the final destination station.

19. A storage medium detachably mountable on a communication station in a wireless network, said station having a memory for storing a respective first table containing identifiers of final destination stations of messages respectively associated with identifiers of intermediate destination stations of messages, said station comprising:

means of storing, in a respective second table, data concerning received data messages, the data including at least one message identifier, an intermediate sending station identifier identifying an intermediate sending station, an intermediate destination station identifier identifying an intended intermediate destination station, a final destination station identifier identifying a final destination station, and a message retransmission number;

means of checking whether the message retransmission number has reached a predetermined value, whether the communication station is not the intended intermediate destination station, and whether the communication station has in its first table a final destination station identifier associated with an intermediate destination station identifier which is different from that of the intermediate sending station; and

means of sending over the wireless network a specific routing message destined for the intermediate sending station in order to indicate the existence of a path between the communication station and the final destination station.