Extended service set mesh topology discovery

• US 7,522,540 B1
• Filed: 04/15/2005
• Issued: 04/21/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): CHO, HONG SOL
• Application Number:
  US11/106,764
• Time in Patent Office: 1,467 Days
• Field of Search: 370/252, 370254-256, 370/351, 370/389, 370/392, 370/400, 370/401
• 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
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

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 joining a self-configuring mesh networking system, comprising:

sending a first meshHello message from a wireless station system on a reserved multicast address to a neighboring mesh node within the self-configuring mesh networking, wherein the neighboring mesh node is configured to not forward messages received on the reserved multicast address;

receiving a second meshHello message generated by the neighboring mesh node;

determining whether the second meshHello message includes a first neighbor list that includes the wireless station attempting to join the self-configuring mesh networking system; and

adding the neighboring mesh node to a second neighbor list stored in the wireless station.

2. The method of claim 1, further comprising requesting a topology database exchange from the neighboring mesh node.

3. The method of claim 2, wherein the topology database includes mesh attributes measured by the neighboring mesh node.

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

5. The method of claim 2, wherein the neighboring node and the wireless station are configured to store a local copy of an anchor tree topology including nodes in the mesh networking system that are associated with the exactly one anchor node.

6. The method of claim 1, wherein the first meshHello message includes a digital signature.

7. The method of claim 1, further comprising outputting the second neighbor list to discover additional neighbor mesh nodes.

8. The method of claim 7, wherein the second neighbor list is sent to the neighboring mesh node or another neighbor on the reserved multicast address to discover additional neighbor mesh nodes.

9. The method of claim 7, wherein the second neighbor list is sent to the neighboring mesh node or another neighbor on the reserved multicast address to discover additional neighbor mesh nodes.

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

11. The method of claim 1, further comprising responding to a request for association received from another wireless station attempting to join the self-configuring mesh networking system.

12. The method of claim 1, further comprising the step of associating with exactly one anchor node of multiple anchor nodes that are coupled to a wired network.

13. A method for discovering a topology of a mesh networking system, comprising:

receiving, on a reserved multicast address, a first meshHello message sent by a wireless station neighboring a mesh node within the mesh networking system, wherein the mesh node is configured to not forward messages received on the reserved multicast address;

adding the wireless station to a list of neighbors stored within the mesh node, wherein the list of neighbors specifies a portion of the topology of the mesh networking system; and

sending the list of neighbors to the wireless station.

14. The method of claim 13, further comprising:

generating a database update indicating that the wireless station is a neighbor of the mesh node; and

sending the database update to other neighbors of the mesh node.

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

16. The method of claim 13, wherein the mesh node is associated with exactly one anchor node of multiple anchor nodes that are coupled to a wired network.

17. The method of claim 13, wherein the mesh node and the wireless station are configured to store a local copy of an anchor tree topology including nodes in the mesh networking system that are associated with the exactly one anchor node.