Extended service set mesh path selection

• US 7,606,175 B1
• Filed: 04/15/2005
• Issued: 10/20/2009
• Est. Priority Date: 04/15/2005
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Maufer, Thomas A.
• Primary Examiner(s): Sheikh; Ayaz R
• Assistant Examiner(s): Aga; Sori A
• Application Number:
  US11/106,761
• Time in Patent Office: 1,649 Days
• Field of Search: None
• US Class Current: 370/255
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 40/30 for proactive routing
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals
• CPC Class Codes: H04W 8/24 Transfer of terminal data
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 92/18 between terminal devices

Abstract

A system and methods for wireless computing devices to become mesh member nodes within a self-configuring mesh network includes mechanisms for neighbor discovery and sharing of a common topology database including mesh topology and mesh network information. Each mesh node may use the topology database to determine optimized routing paths within the mesh network. Mesh member nodes are configured to detect and communicate topology changes and measured mesh network attributes to other members of the self-configuring wireless network.

Claims

1. A method of communicating topology database information between mesh nodes in a self-configuring mesh network, comprising:

receiving a topology database update including a database version identifier, wherein the topology database update is sent by a first mesh node in the self-configuring mesh network to a second mesh node;

sending an acknowledgement including the database version identifier to the first mesh node from the second mesh node; and

storing the topology database update in a first topology database within the second mesh node after the second mesh node determines that each adjacent neighbor mesh node of the second mesh node has received the topology database update and is synchronized to the first mesh node.

2. The method of claim 1, wherein the second mesh node is a wireless computing device in the self-configuring mesh network.

3. The method of claim 2, wherein a second topology database is stored in the first mesh node is the same as the first topology database that is stored in the second mesh node.

4. The method of claim 1, further comprising:

receiving the acknowledgement; and

verifying that the database version identifier included in the acknowledgement matches a current database version identifier stored in the first mesh node; and

storing the topology database update in a second topology database.

5. The method of claim 4, wherein the second topology database includes metrics, computed by the first mesh node, based on measured mesh attributes.

6. The method of claim 4, wherein the second topology database includes mesh topology data for the self-configuring mesh network.

7. The method of claim 6, further comprising computing path information based on the mesh topology data.

8. The method of claim 4, wherein the second topology database includes mesh attributes measured by the first mesh node.

9. The method of claim 8, further comprising computing path information based on the measured mesh attributes.

10. The method of claim 1, further comprising generating the topology database update in response to a topology change in the self-configuring mesh network.

11. The method of claim 1, further comprising generating the topology database update in response to an attribute change in the self-configuring mesh network.

12. The method of claim 1, wherein the first mesh node is coupled to a wired network.

21. The method of claim 1, further comprising the steps of:

receiving a meshHello including a first database version identifier;

comparing the first database version identifier with a second database version identifier that is stored in the first topology database; and

requesting a topology database update when the second database version identifier predates the first topology database version identifier.

13. A method of determining a routing path from a first wireless mesh node to a second wireless mesh node in a self-configuring mesh network, the method comprising:

storing a synchronized topology database specifying a topology of the self-configuring mesh network in the first wireless mesh node;

storing the synchronized topology database specifying the topology of the self-configuring mesh network in the second wireless mesh node;

computing path information for the routing path using information stored in the synchronized topology database;

receiving a topology database update from the second wireless mesh node;

updating the synchronized topology database stored in the first mesh node using the topology database update to produce an updated synchronized topology database after determining that each adjacent neighbor mesh node of the first wireless mesh node has received the topology database update and is synchronized to the second wireless mesh node; and

recomputing the path information based on the updated synchronized topology database.

14. The method of claim 13, wherein the first wireless mesh node is coupled to a wired network.

15. The method of claim 13, wherein the synchronized topology database includes mesh network attributes that are used for the computing of the path information.

16. The method of claim 13, wherein the synchronized topology database includes mesh network metrics that are used for the computing of the path information.

17. The method of claim 13, wherein the topology represents a portion of the self-configuring mesh network and the portion includes a single wireless mesh node that is coupled to a wired network.

18. The method of claim 13, wherein the topology represents all wireless mesh nodes and stations within the self-configuring mesh network.

19. The method of claim 13, further comprising the step of storing the path information in a routing table that includes an entry for each wireless mesh node in the self-configuring mesh network.

20. The method of claim 13, further comprising the step of storing the path information in a routing table that includes entries for some wireless mesh nodes in the self-configuring mesh network and includes a default entry for other wireless mesh nodes in the self-configuring mesh network.