Path optimization for mesh access points in a wireless mesh network

• US 20080181133A1
• Filed: 01/25/2007
• Published: 07/31/2008
• Est. Priority Date: 01/25/2007
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Thubert, Pascal, Ribiere, Vincent Jean, Castagnoli, Neal Dante, Wetterwald, Patrick
• Granted Patent: US 8,155,007 B2
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: H04W 40/30 for proactive routing

Abstract

In one embodiment, a method includes, in each of a plurality of mesh access points, connecting to one of a plurality of mesh controllers in a mesh network and passing connection information to the one mesh controller. The mesh access points include a wired mesh access point having a wired connection to the one mesh controller, and wireless mesh access points having a wireless connection to the one mesh controller via the wired mesh access point. The method also includes generating, in each mesh controller, a corresponding link state table based on the passed connection information from each corresponding connected mesh access point. The method also includes generating in at least one of the mesh controllers a mesh table, identifying all of the connecting links for the mesh access points connected among the mesh controllers, based on the mesh controllers sharing the respective link state tables.

Claims

1. A method comprising:

in each of a plurality of mesh access points, connecting to one of a plurality of mesh controllers in a mesh network and passing connection information to the one mesh controller, the mesh access points including a wired mesh access point having a wired connection to the one mesh controller, and wireless mesh access points having a wireless connection to the one mesh controller via the wired mesh access point;

generating, in each mesh controller, a corresponding link state table based on the passed connection information from each corresponding connected mesh access point, the corresponding link state table identifying connecting links for connecting the corresponding connected mesh access points toward the mesh controller, at least one link state table identifying a wireless neighbor link between one of the connected mesh access points connected to one of the mesh controllers and a corresponding detected neighbor mesh access point connected to another one of the mesh controllers; and

generating in at least one of the mesh controllers a mesh table, identifying all of the connecting links for the mesh access points connected among the mesh controllers, based on the mesh controllers sharing the respective link state tables.

2. The method of claim 1, further comprising calculating, in each mesh controller, optimized paths for reaching each of the corresponding connected mesh access points based on the mesh table.

3. The method of claim 2, further comprising:

creating, in each mesh controller, forwarding tables for each of the corresponding connected mesh access points based on the optimized paths; and

supplying, in each mesh controller, the corresponding forwarding table to the corresponding connected mesh access point.

4. The method of claim 3, wherein the creating of forwarding tables includes:

creating a forwarding table entry based on parsing the optimized paths; and

accumulating the forwarding table entries for each connected mesh access point to generate the corresponding forwarding table for the connected mesh access point.

5. The method of claim 3, wherein the creating of forwarding tables further includes:

receiving one of the optimized paths for one of the mesh access points connected to another one of the mesh controllers from the another one of the mesh controllers,

parsing the one optimized path for additional forwarding table entries for the corresponding connected mesh access points, and

adding the additional table forwarding table entries to the corresponding forwarding table for the connected mesh access point.

6. The method of claim 5, wherein the creating of forwarding tables further includes selectively truncating the forwarding table to a prescribed forwarding horizon, the forwarding table including first and second entries for reaching a prescribed destination at respective first and second costs.

7. The method of claim 2, wherein the calculating of the optimized paths includes:

executing a mesh access point controller resource for each connected mesh access point;

generating in each mesh access point controller resource a directed acyclic graph for the corresponding connected mesh access point, and

forwarding by each mesh access point controller resource the directed acyclic graph to other mesh access point controller resources associated with respective other mesh access points identified in the directed acyclic graph.

8. The method of claim 1, wherein the generating in each mesh controller a corresponding link state table includes:

executing a mesh access point controller resource for each connected mesh access point, and obtaining by each mesh access point controller resource the corresponding connection information from the corresponding connected mesh access point; and

executing an aggregating resource that aggregates the connection information from the mesh access point controller resources into the link state table.

9. A method comprising:

receiving, by a mesh controller in a mesh network, connection information from connected mesh access points having connected to the mesh controller, the connected mesh access points including a wired mesh access point having a wired connection to the mesh controller, and wireless mesh access points having a wireless connection to the mesh controller via the wired mesh access point;

generating, by the mesh controller, a link state table based on the passed connection information, the link state table identifying connecting links for connecting the connected mesh access points toward the mesh controller, and further identifying at least one wireless neighbor link between one of the connected mesh access points and a detected neighbor mesh access point connected to another mesh controller in the mesh network; and

generating in the mesh controller a mesh table based on receiving a corresponding link state table from each other mesh controller in the mesh network, the mesh table identifying all of the connecting links for the mesh access points connected in the mesh network.

10. The method of claim 9, further comprising calculating, by the mesh controller, optimized paths for reaching each of the corresponding connected mesh access points based on the mesh table.

11. The method of claim 10, further comprising:

creating forwarding tables for each of the corresponding connected mesh access points based on the optimized paths; and

supplying the corresponding forwarding table to the corresponding connected mesh access point.

12. The method of claim 11, wherein the creating of forwarding tables includes:

creating a forwarding table entry based on parsing the optimized paths; and

accumulating the forwarding table entries for each connected mesh access point to generate the corresponding forwarding table for the connected mesh access point.

13. The method of claim 11, wherein the creating of forwarding tables further includes:

receiving one of the optimized paths for one of the mesh access points connected to another one of the mesh controllers from the another one of the mesh controllers,

parsing the one optimized path for additional forwarding table entries for the corresponding connected mesh access points, and

adding the additional table forwarding table entries to the corresponding forwarding table for the connected mesh access point.

14. The method of claim 13, wherein the creating of forwarding tables further includes selectively truncating the forwarding table to a prescribed forwarding horizon, the forwarding table including first and second entries for reaching a prescribed destination at respective first and second costs.

15. The method of claim 10, wherein the calculating of the optimized paths includes:

executing a mesh access point controller resource for each connected mesh access point;

generating in each mesh access point controller resource a directed acyclic graph for the corresponding connected mesh access point, and

forwarding by each mesh access point controller resource the directed acyclic graph to other mesh access point controller resources associated with respective other mesh access points identified in the directed acyclic graph.

16. The method of claim 9, wherein the generating of the link state table includes:

executing a mesh access point controller resource for each connected mesh access point, and obtaining by each mesh access point controller resource the corresponding connection information from the corresponding connected mesh access point; and

executing an aggregating resource that aggregates the connection information from the mesh access point controller resources into the link state table.

17. A method comprising:

connecting, by a mesh access point, to a mesh controller of a mesh network via a wireless connection with an intermediate mesh access point;

sending, by the mesh access point, connection information to the mesh controller that identifies each connection with any neighboring mesh access point including the intermediate mesh access point; and

receiving, by the mesh access point and from the mesh controller, a forwarding table that specifies destination mesh access points in the mesh network, each destination mesh access point having at least one link identifier for reaching the corresponding destination mesh access point via one of the neighboring mesh access points.

18. The method of claim 17, wherein the forwarding table specifies, for at least one of the destination mesh access points, an alternate link identifier for reaching the corresponding destination mesh access point, the method further including selecting the alternate link identifier based on a determined loss of link connectivity with the one neighboring mesh access point corresponding to the at least one link identifier.

19. An apparatus comprising:

a wired link interface configured for receiving connection information from connected mesh access points having connected to the apparatus in a mesh network via a wired connect-ion, the connected mesh access points including a wired mesh access point having connected to the apparatus via the wired connection, and wireless mesh access points having a wireless connection to the apparatus via the wired mesh access point;

a memory having a first memory portion and a second memory portion; and

a mesh controller circuit configured for operating as a mesh controller in the mesh network, the mesh controller circuit further configured for generating a link state table in the first memory portion based on the passed connection information, the link state table identifying connecting links for connecting the connected mesh access points toward the apparatus, and further identifying at least one wireless neighbor link between one of the connected mesh access points and a detected neighbor mesh access point connected to another mesh controller in the mesh network;

the mesh controller circuit further configured for generating in the second memory portion a mesh table based on the wired link interface receiving a corresponding link state table from each other mesh controller in the mesh network, the mesh table identifying all of the connecting links for the mesh access points connected in the mesh network.

20. The apparatus of claim 19, wherein the mesh controller circuit is further configured for calculating optimized paths for reaching each of the corresponding connected mesh access points based on the mesh table.

21. The apparatus of claim 20, wherein the mesh controller circuit further is configured for:

creating forwarding tables for each of the corresponding connected mesh access points based on the optimized paths; and

supplying the corresponding forwarding table to the corresponding connected mesh access point.

22. The apparatus of claim 21, wherein the mesh controller circuit further is configured for creating the forwarding tables based on creating a forwarding table entry based on parsing the optimized paths, and accumulating the forwarding table entries for each connected mesh access point to generate the corresponding forwarding table for the connected mesh access point.

23. The apparatus of claim 21, wherein the mesh controller circuit further is configured for:

receiving one of the optimized paths for one of the mesh access points connected to another one of the mesh controllers from the another one of the mesh controllers;

parsing the one optimized path for additional forwarding table entries for the corresponding connected mesh access points, and

adding the additional table forwarding table entries to the corresponding forwarding table for the connected mesh access point.

24. The apparatus of claim 23, wherein the mesh controller circuit further is configured for selectively truncating the forwarding table to a prescribed forwarding horizon, the forwarding table including first and second entries for reaching a prescribed destination at respective first and second costs.

25. The apparatus of claim 20, wherein:

the mesh controller circuit includes a mesh controller circuit portion for each connected mesh access point;

each mesh controller circuit portion configured for generating a directed acyclic graph for the corresponding connected mesh access point, and forwarding the directed acyclic graph to other mesh controller circuit portions associated with respective other mesh access points identified in the directed acyclic graph.

26. The apparatus of claim 19, wherein the mesh controller circuit comprises:

a mesh controller circuit portion for each connected mesh access point, each mesh controller circuit portion configured for obtaining the corresponding connection information from the corresponding connected mesh access point; and

an aggregating circuit that aggregates the connection information from the mesh controller circuit portions into the link state table.

27. An apparatus comprising:

a wireless network interface configured for connecting to a mesh controller of a mesh network via a wireless connection with an intermediate mesh access point;

a mesh access point control circuit configured for sending connection information to the mesh controller that identifies each connection with any neighboring mesh access point including the intermediate mesh access point; and

a memory circuit configured for storing a forwarding table having been received from the mesh controller, the forwarding table specifying destination mesh access points in the mesh network, each destination mesh access point having at least one link identifier for reaching the corresponding destination mesh access point via one of the neighboring mesh access points.

28. The apparatus of claim 27, further comprising a link selection circuit, wherein:

the forwarding table specifies, for at least one of the destination mesh access points, an alternate link identifier for reaching the corresponding destination mesh access point;

the link selection circuit configured for selecting the alternate link identifier based on a determined loss of link connectivity with the one neighboring mesh access point corresponding to the at least one link identifier.

29. An apparatus comprising:

means for receiving connection information from connected mesh access points having connected to the apparatus in a mesh network via a wired connection, the connected mesh access points including a wired mesh access point having connected to the apparatus via the wired connection, and wireless mesh access points having a wireless connection to the apparatus via the wired mesh access point;

means for storing a link state table,

means for executing mesh controller operations in the mesh network, the means for executing configured for generating the link state table based on the passed connection information, the link state table identifying connecting links for connecting the connected mesh access points toward the apparatus, and further identifying at least one wireless neighbor link between one of the connected mesh access points and a detected neighbor mesh access point connected to another mesh controller in the mesh network;

the means for executing further configured for generating a mesh table based on reception of a corresponding link state table from each other mesh controller in the mesh network, the mesh table identifying all of the connecting links for the mesh access points connected in the mesh network.

30. An apparatus comprising:

means for connecting to a mesh controller of a mesh network via a wireless connection with an intermediate mesh access point;

means for sending connection information to the mesh controller that identifies each connection with any neighboring mesh access point including the intermediate mesh access point; and

means for storing a forwarding table having been received from the mesh controller, the forwarding table specifying destination mesh access points in the mesh network, each destination mesh access point having at least one link identifier for reaching the corresponding destination mesh access point via one of the neighboring mesh access points.