ROUTE TREE BUILDING IN A WIRELESS MESH NETWORK

• US 20080043637A1
• Filed: 08/15/2006
• Published: 02/21/2008
• Est. Priority Date: 08/15/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Rahman, Shahriar I.
• Granted Patent: US 7,496,078 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update

Abstract

In one embodiment, a tree-topology building method for a wireless mesh network includes using a centralized parent selection process to select a parent and join offer messages to a selected child of the selected parent.

Claims

1. A method comprising:

receiving at a controller radio measurement reports from at least one mesh access point about neighbors of the at least one mesh access points, the mesh access points being mesh points of a wireless mesh network, wherein the access point functionality of each mesh access point is controlled by the controller using messages between each mesh access point and the controller using a first protocol, the controller connected to a root mesh access point that forms the root of the mesh network;

determining a tree topology for the wireless mesh network, including determining a potential parent access point and a selected parent access point to the parent of the potential parent access point; and

sending a JOIN OFFER message to the potential parent access point and via the selected parent access point to offer the potential parent access point to join the mesh with the selected parent mesh access point as its parent, such that the selected parent mesh access point forms a secure link to the potential parent mesh access point, and relay the JOIN OFFER message to the potential parent mesh access point, such that the potential parent mesh access point can join the controller via the selected parent mesh access point.

2. A method as recited in claim 1, further comprising detecting whether there has been a link failure in the tree topology, and in the case there is a link failure, re-calculating the tree topology and sending out one or more JOIN OFFER messages to re-establish the tree topology.

3. A method as recited in claim 2, wherein the detecting link failure uses reports sent by parent mesh access points.

4. A method as recited in claim 2, wherein the detecting link failure uses a heartbeat mechanism.

5. A method as recited in claim 1, further comprising determining alternate/backup potential parents, and sending the alternate/backup potential parents to mesh points of the mesh network.

6. A method comprising:

receiving one or more beacon and/or probe response frames in a particular lightweight mesh access point that has a secure tunnel to a controller, the beacons and/or probe responses being from one or more neighboring access points, the controller being configured for controlling the access point functionality of a set of lightweight access points including the particular mesh access point using messages between each lightweight mesh access point and the controller using a first protocol;

sending a radio measurement report to the controller, including information on the one or more neighboring access points;

receiving from the controller a JOIN OFFER message to relay to a second mesh access point so that the second mesh access point can become a child mesh access point of the particular mesh access point, the JOIN OFFER frame sent by the controller as a result of the controller determining a tree topology, including determining the tree with the particular mesh access point a selected parent access point to the second mesh access point;

relaying the JOIN OFFER message to the second mesh access point; and

receiving a JOIN REQUEST message from the second mesh access point as a result of the second mesh access point receiving the JOIN OFFER message to join the mesh, such that the second mesh access point joins the controller, including forming a secure tunnel to the controller.

7. A method as recited in claim 6, further comprising repeating through with one or more additional mesh access points.

8. A method as recited in claim 6, further comprising:

prior to the relaying of the JOIN OFFER message to the second mesh access point, securing an L2 link between the second mesh access point and particular mesh access point.

9. A method comprising:

in a particular lightweight access point, receiving a JOIN OFFER message from a first parent mesh access point, the particular lightweight access point having the capability of being a mesh access point of a wireless mesh network by joining the mesh via a parent mesh access point that has a secure tunnel to a controller and that is part of the wireless mesh network, the controller configured for controlling the access point functionality of a set of lightweight access points including the parent mesh access point using messages between each lightweight mesh access point and the controller using a first protocol, wherein the JOIN OFFER message is generated at the controller as a result of the controller carrying out a parent selection process including;

the controller receiving radio measurement report from one or more mesh access points about neighboring access points to the one or more mesh access points, and

the controller determining a tree topology, including determining the tree with the first parent mesh access point a selected parent access point to the particular mesh access point; and

the particular lightweight access point joining the mesh network by joining the controller via the first parent mesh access point, including forming a secure tunnel to the controller.

10. A method as recited in claim 9, further comprising:

prior to the receiving of the JOIN OFFER message from the first parent mesh access point, securing an L2 link between the first parent mesh access point and the particular mesh access point.

11. A method as recited in claim 9, further comprising:

after, receiving a different JOIN OFFER message via a second parent mesh access point indicating a different selected parent mesh access point than the first parent mesh access point;

after receiving the different JOIN OFFER message, leaving the first parent mesh access point and joining the mesh network by joining the controller via the different selected parent mesh access point, including forming a secure tunnel to the controller via the different selected parent mesh access point.

12. A method as recited in claim 9, wherein the joining via the different selected parent mesh access point is a rapid roam using a rapid roaming method.

13. A method as recited in claim 9, further comprising:

after, in the case of losing connection to the first parent mesh access point, waiting for a new JOIN OFFER message via a second parent mesh access point indicating a different selected parent mesh access point than the first parent mesh access point;

after receiving the different JOIN OFFER message, joining the mesh network by joining the controller via the different selected parent mesh access point, including forming a secure tunnel to the controller via the different selected parent mesh access point.

14. A method as recited in claim 13, wherein the waiting is for at most a pre-defined waiting period, and wherein, after waiting and not receiving a NEW JOIN OFFER for the pre-defined waiting period, the particular mesh access point finds a parent using a local tree building method.

15. Logic encoded in one or more tangible media for execution and when executed operable to:

receive one or more beacon and/or probe response frames in a particular lightweight mesh access point that has a secure tunnel to a controller, the beacons and/or probe responses being from one or more neighboring access points, the controller being configured for controlling the access point functionality of a set of lightweight access points including the particular mesh access point using messages between each lightweight mesh access point and the controller using a first protocol;

send a radio measurement report to the controller, including information on the one or more neighboring access points;

receive from the controller a JOIN OFFER message to relay to a second mesh access point so that the second mesh access point can become a child mesh access point of the particular mesh access point, the JOIN OFFER frame sent by the controller as a result of the controller determining a tree topology, including determining the tree with the particular mesh access point a selected parent access point to the second mesh access point;

relay the JOIN OFFER message to the second mesh access point; and

receive a JOIN REQUEST message from the second mesh access point as a result of the second mesh access point receiving the JOIN OFFER message to join the mesh, such that the second mesh access point joins the controller, including forming a secure tunnel to the controller.

16. Logic encoded in one or more tangible media for execution and when executed operable to:

receive at a controller radio measurement reports from at least one mesh access point about neighbors of the at least one mesh access points, the mesh access points being mesh points of a wireless mesh network, wherein the access point functionality of each mesh access point is controlled by the controller using messages between each mesh access point and the controller using a first protocol, the controller connected to a root mesh access point that forms the root of the mesh network;

determine a tree topology for the wireless mesh network, including determining a potential parent access point and a selected parent access point to the parent of the potential parent access point; and

send a JOIN OFFER message to the potential parent access point and via the selected parent access point to offer the potential parent access point to join the mesh with the selected parent mesh access point as its parent, such that the selected parent mesh access point forms a secure link to the potential parent mesh access point, and relay the JOIN OFFER message to the potential parent mesh access point, such that the potential parent mesh access point can join the controller via the selected parent mesh access point.

17. Logic encoded in one or more tangible media for execution and when executed operable to:

receive a JOIN OFFER message in a particular lightweight access point from a first parent mesh access point, the particular lightweight access point having the capability of being a mesh access point of a wireless mesh network by joining the mesh via a parent mesh access point that has a secure tunnel to a controller and that is part of the wireless mesh network, the controller configured for controlling the access point functionality of a set of lightweight access points including the parent mesh access point using messages between each lightweight mesh access point and the controller using a first protocol, wherein the JOIN OFFER message is generated at the controller as a result of the controller carrying out a parent selection process including;

the controller receiving radio measurement report from one or more mesh access points about neighboring access points to the one or more mesh access points, and

the controller determining a tree topology, including determining the tree with the first parent mesh access point a selected parent access point to the particular mesh access point; and

cause the particular lightweight access point to join the mesh network by joining the controller via the first parent mesh access point, including forming a secure tunnel to the controller.

18. An apparatus comprising:

means in a controller for receiving radio measurement reports from at least one mesh access point about neighbors of at least one mesh access points of a wireless network of mesh access points, wherein the access point functionality of each mesh access point is controlled by the controller using messages between each mesh access point and the controller using a first protocol, the controller connected to a root mesh access point that forms the root of the mesh network;

means in the controller for determining a tree topology for the mesh network, including determining a potential parent access point and a selected parent access point to the parent of the potential parent access point; and

means for sending a JOIN OFFER message to the potential parent access point and via the selected parent access point to offer the potential parent access point to join the mesh with the selected parent mesh access point as its parent, such that the selected parent mesh access point forms a secure link to the potential parent mesh access point, and relay the JOIN OFFER message to the potential parent mesh access point, such that the potential parent mesh access point can join the controller via the selected parent mesh access point.

19. An apparatus comprising:

means in a particular lightweight mesh access point for receiving one or more beacon and probe response frames from one or more neighboring access points, the particular lightweight mesh access point having a secure tunnel to a controller and being a mesh access point of a wireless mesh network, the controller configured for controlling the access point functionality of a set of lightweight access points including the particular mesh access point using messages between each lightweight mesh access point and the controller using a first protocol;

means in the particular lightweight mesh access point for sending a radio measurement report to the controller, including information on the one or more neighboring access points;

means in the particular lightweight mesh access point for receiving from the controller a JOIN OFFER message to relay to a second mesh access point so that the second mesh access point can become a child mesh access point of the particular mesh access point, the JOIN OFFER frame sent by the controller as a result of the controller determining a tree topology of the mesh network, including determining the tree with the particular mesh access point a selected parent access point to the second mesh access point;

means in the particular lightweight mesh access point for relaying the JOIN OFFER message to the second mesh access point; and

means in the particular lightweight mesh access point for receiving a JOIN REQUEST message from the second mesh access point as a result of the second mesh access point receiving the JOIN OFFER message to join the mesh, such that the second mesh access point joins the controller, including forming a secure tunnel to the controller.

20. An apparatus comprising:

means for receiving a JOIN OFFER message, the means for receiving being in a lightweight mesh access point that can be a mesh access point of a mesh network by joining the mesh via a parent mesh access point that has a secure tunnel to a controller and that is part of the wireless mesh network, the controller configured for controlling the access point functionality of a set of lightweight access points including the parent mesh access point using messages between each lightweight mesh access point and the controller using a first protocol from a first parent mesh access point, the JOIN OFFER message generated at the controller as a result of the controller carrying out a parent selection process including;

the controller receiving radio measurement report from one or more mesh access points about neighboring access points to the one or more mesh access points, and

the controller determining a tree topology, including determining the tree with the first parent mesh access point a selected parent access point to the particular mesh access point; and

means in the lightweight mesh access point for joining the mesh network by joining the controller via the first parent mesh access point, including forming a secure tunnel to the controller.