Method for network configuration via third party query

• US 5,453,977 A
• Filed: 02/08/1994
• Issued: 09/26/1995
• Est. Priority Date: 02/08/1994
• Status: Expired due to Term

• Current Assignee: Google Inc. (Alphabet Inc.)
• Original Assignee: Metricom, Inc.
• Inventors: Flammer, III, George H., San Filippo, III, William E.
• Primary Examiner(s): Kizou, Hassan
• Application Number:
  US08/193,377
• Time in Patent Office: 595 Days
• Field of Search: 370/54, 370/60, 370/60.1, 370/85.8, 370/94.1, 370/94.2, 370/94.3, 370/95.2, 340/825.08, 340/825.54, 379/92, 379/58, 455/54.1, 455/54.2, 455/56.1
• US Class Current: 370/254
• 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/16 Multipoint routing

Abstract

In a mesh communication network, new network nodes acquire information about nearby nodes to which they may communicate through a third-party query whereby an established node with which a new node can communicate is queried to provide a list of nodes in the vicinity of the new nodes with which the new node is likely to be able to communicate. The new node uses this list in attempting to establish communication links and then repeats the third-party query for each node in the list to which it can communicate.

Claims

1. In network with a plurality of nodes, a method by which a node may acquire a list of communication links comprising the steps of:

transmitting on random channels link acquisition packets;

receiving a response packet from at least a first established node, said established node being a node that has acquired a plurality of links to neighboring nodes;

obtaining from said first established node a link list of said first established node;

utilizing said link list to direct acquisition packets to nodes on said link list;

receiving a response packet from each node on said link list which can hear said acquisition packets; and

adding each node from which a response packet is received to said list of communication links.

2. The method according to claim 1, further comprising the step of repeating said obtaining step, said utilizing step, said receiving step, and said adding step for each node that responds to any acquisition packet from said acquiring node.

3. The method according to claim 1 wherein said network uses non-directory-based routing.

4. In a digital mesh packet communication network having a plurality of stationary nodes and roaming nodes, each stationary node and roaming node capable of transmitting and receiving data packets on at least one of a plurality of channels to and from at least one other node, a method for configuring a node to acquire a list of new communication links comprising the steps of:

transmitting link acquisition packets on a random sequence of channels until a response is received on at least one channel from at least a first established node, said established node being a node that has acquired a plurality of links to neighboring nodes;

obtaining from said first established node a list of each node with which said first established node can communicate;

directing link acquisition packets to nodes on said list;

receiving a response packet from each node on said list which can hear said acquisition packets; and

adding each node from which a response packet is received to said list of new communication links.

5. The method according to claim 4 further comprising the step of repeating said obtaining step, said directing step, said receiving step, and said adding step for each node that responds to any acquisition packet from said acquiring node.

6. The method according to claim 4 wherein said network uses non-directory-based routing.

7. The method according to claim 4 wherein each of said stationary nodes is uniquely identified by absolute geographic coordinates.

8. The method according to claim 4 wherein a roaming node changing its geographic location from a first location at which it had established a list of communication links to a second location, transmits, at said second location, link acquisition packets to those nodes with which it was able to communicate when it was at said first location.

9. In a digital mesh packet communication network having a plurality of stationary nodes and roaming nodes, each stationary node and roaming node capable of transmitting and receiving data packets on at least one of a plurality of channels to and from at least one other node, a method for a new node to acquire information regarding available communication links in the network comprising the steps of:

transmitting link acquisition packets on a plurality of channels until a response is received on at least one channel from at least a first established node, said established node being a node that has acquired a plurality of links neighboring nodes;

storing at said new node data regarding the communication link with said first established node in a link table;

obtaining from said first established node a first list of nodes with which said first established node can communicate;

directing acquisition packets to nodes on said first list;

receiving a response packet from each node on said first list which can hear said acquisition packets;

adding data regarding communication links with each node on said first list that responds to said link table and storing information regarding nodes that do not respond in a failed communication table;

acquiring from each of said responding nodes, a second list of nodes with which each of said responding nodes can communicate;

comparing said nodes on said second lists with said nodes in said node link table and said failed communication table;

directing link acquisition packets to nodes on said second lists that are not on said link table or said failed communication table;

establishing communications links with nodes that respond by repeating said receiving step, said adding step, said acquiring step, said comparing step and said directing step for each node that is placed on said link table unit no new nodes are added to said link table.

10. The method according to claim 9 wherein said network uses non-directory-based routing.

11. The method according to claim 9 wherein each of said stationary nodes is uniquely identified by absolute geographic coordinates.

12. The communications network according to claim 9 wherein a roaming node changing its geographic location from a first location at which it had established a list of communication links to a second location, transmits, at said second location, link acquisition packets to those nodes with which it was able to communicate when it was at said first location.