Path optimization for mesh access points in a wireless mesh network

• US 8,155,007 B2
• Filed: 01/25/2007
• Issued: 04/10/2012
• 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, Wetterwald, Patrick, Castagnoli, Neal Dante
• Primary Examiner(s): Shah, Chirag
• Assistant Examiner(s): YOUNG, STEVE R
• Application Number:
  US11/657,662
• Publication Number:
  US 20080181133A1
• Time in Patent Office: 1,902 Days
• Field of Search: None
• US Class Current: 370/238
• 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 in a local area network implemented as a mesh network, connecting to one of a plurality of mesh controllers in the 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,

the wireless mesh access points including first wireless mesh access points each having a wireless link connection with at least the wired mesh access point, and at least one second wireless mesh access point having the corresponding wireless connection via a wireless link connection with at least one of the first wireless mesh access points, wherein routing protocols are not implemented within any of the mesh access points;

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;

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 according to a routing protocol that is executed by the mesh controllers on behalf of the mesh access points;

creating, in each mesh controller, truncated forwarding tables for each of the corresponding connected mesh access points based on the mesh table, the truncated forwarding tables truncated to a prescribed forwarding horizon based on deletion of one or more entries relative to a forwarding table for the corresponding connected mesh access point, at least one of the truncated forwarding tables including first and second entries for reaching a prescribed destination at respective first and second costs; and

supplying, in each mesh controller, the corresponding truncated forwarding table to the corresponding connected mesh access point via a corresponding tunnel established between said each mesh controller and the corresponding connected mesh access point, the truncated forwarding table enabling said each mesh access point to execute link layer forwarding via a path distinct from the corresponding tunnel.

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, each of the truncated forwarding tables created based on the optimized paths.

3. The method of claim 2, wherein the creating of truncated 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 truncated forwarding table for the connected mesh access point.

4. The method of claim 2, wherein the creating of truncated 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 forwarding table entries to the corresponding truncated forwarding table for the connected mesh access point.

5. 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.

6. 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.

7. A method comprising:

receiving, by a mesh controller in a local area network implemented as 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,

the wireless mesh access points including first wireless mesh access points each having a wireless link connection with at least the wired mesh access point, and at least one second wireless mesh access point having the corresponding wireless connection via a wireless link connection with at least one of the first wireless mesh access points, wherein routing protocols are not implemented within any of the connected mesh access points;

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;

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 according to a routing protocol that is executed by the mesh controller on behalf of the connected mesh access points, the mesh table identifying all of the connecting links for the mesh access points connected in the mesh network;

creating truncated forwarding tables for each of the corresponding connected mesh access points based on the mesh table, the truncated forwarding tables truncated to a prescribed forwarding horizon based on deletion of one or more entries relative to a forwarding table for the corresponding connected mesh access point, at least one of the truncated forwarding tables including first and second entries for reaching a prescribed destination at respective first and second costs; and

supplying the corresponding truncated forwarding table to the corresponding connected mesh access point via a corresponding tunnel established between the mesh controller and the corresponding connected mesh access point, the corresponding truncated forwarding table enabling the corresponding connected mesh access point to execute link layer forwarding via a path distinct from the corresponding tunnel.

8. The method of claim 7, further comprising calculating, by the mesh controller, optimized paths for reaching each of the corresponding connected mesh access points based on the mesh table, each of the truncated forwarding tables created based on the optimized paths.

9. The method of claim 8, wherein the creating of truncated 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 truncated forwarding table for the connected mesh access point.

10. The method of claim 8, wherein the creating of truncated 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 forwarding table entries to the corresponding truncated forwarding table for the connected mesh access point.

11. The method of claim 8, 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.

12. The method of claim 7, 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.

13. A method comprising:

connecting, by a wireless mesh access point in a local area network implemented as a mesh network, to a mesh controller of the mesh network via a wireless connection with an intermediate wireless mesh access point, the intermediate wireless mesh access point having a corresponding wireless connection for reaching the mesh controller;

sending, by the wireless mesh access point, connection information to the mesh controller that identifies each connection by the mesh access point with any neighboring mesh access point including the intermediate wireless mesh access point, wherein routing protocols are not implemented within the wireless mesh access point; and

receiving, by the wireless mesh access point and from the mesh controller via a tunnel established between the mesh controller and the wireless mesh access point, a truncated forwarding table that specifies destination mesh access points in the mesh network, the truncated forwarding table created by the mesh controller according to a routing protocol that is executed by the mesh controller on behalf of the wireless mesh access point, the truncated forwarding table truncated by the mesh controller to a prescribed forwarding horizon based on deletion of one or more entries by the mesh controller relative to a forwarding table for the corresponding connected mesh access point, the truncated forwarding table specifying, for each destination mesh access point specified in the truncated forwarding table, at least one link identifier for reaching the corresponding destination mesh access point via one of the neighboring mesh access points, the truncated forwarding table including first and second entries for reaching a prescribed destination at respective first and second costs, the truncated forwarding table enabling the wireless mesh access point to execute link layer forwarding via a path distinct from the corresponding tunnel.

14. The method of claim 13, wherein the truncated 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.

15. An apparatus comprising:

a wired link interface configured for receiving connection information from connected mesh access points having connected to the apparatus via a wired connection in a local area network implemented as a mesh network, 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,

the wireless mesh access points including first wireless mesh access points each having a wireless link connection with at least the wired mesh access point, and at least one second wireless mesh access point having the corresponding wireless connection via a wireless link connection with at least one of the first wireless mesh access points, wherein routing protocols are not implemented within any of the connected mesh access points;

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 according to a routing protocol that is executed by the mesh controller on behalf of the connected mesh access points, the mesh table identifying all of the connecting links for the mesh access points connected in the mesh network;

the mesh controller circuit further configured for creating truncated forwarding tables for each of the corresponding connected mesh access points based on the mesh table, each truncated forwarding table truncated by the mesh controller circuit to a prescribed forwarding horizon based on deletion of one or more entries relative to a forwarding table for he corresponding connected mesh access point, at least one of the truncated forwarding tables including first and second entries for reaching a prescribed destination at respective first and second costs, and the mesh controller circuit further configured for supplying the corresponding truncated forwarding table to the corresponding connected mesh access point via a corresponding tunnel established between the mesh controller and the corresponding connected mesh access point, the corresponding truncated forwarding table enabling the corresponding connected mesh access point to execute link layer forwarding via a path distinct from the corresponding tunnel.

16. The apparatus of claim 15, 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, each of the truncated forwarding tables created based on the optimized paths.

17. The apparatus of claim 16, wherein the mesh controller circuit further is configured for creating the truncated 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 truncated forwarding table for the connected mesh access point.

18. The apparatus of claim 16, 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 forwarding table entries to the corresponding truncated forwarding table for the connected mesh access point.

19. The apparatus of claim 16, 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.

20. The apparatus of claim 15, 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.

21. An apparatus comprising:

a wireless network interface configured for connecting to a mesh controller in a local area network implemented as a mesh network and via a wireless connection with an intermediate wireless mesh access point, the intermediate wireless mesh access point having a corresponding wireless connection for reaching the mesh controller;

a mesh access point control circuit configured for sending connection information to the mesh controller that identifies each connection by the apparatus with any neighboring mesh access point including the intermediate wireless mesh access point, wherein routing protocols are not implemented within the apparatus; and

a memory circuit configured for storing a truncated forwarding table having been received from the mesh controller via a tunnel established between the mesh controller and the apparatus, the truncated forwarding table specifying destination mesh access points in the mesh network, the truncated forwarding table created by the mesh controller according to a routing protocol that is executed by the mesh controller on behalf of the apparatus, the truncated forwarding table truncated by the mesh controller to a prescribed forwarding horizon based on deletion of one or more entries relative to a forwarding table for he corresponding connected mesh access point, the truncated forwarding table specifying, for each destination mesh access point specified in the truncated forwarding table, at least one link identifier for reaching the corresponding destination mesh access point via one of the neighboring mesh access points, the truncated forwarding table including first and second entries for reaching a prescribed destination at respective first and second costs, the truncated forwarding table enabling the apparatus to execute link layer forwarding via a path distinct from the corresponding tunnel.

22. The apparatus of claim 21, further comprising a link selection circuit, wherein:

the truncated 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.

23. An apparatus comprising:

means for receiving connection information from connected mesh access points having connected to the apparatus via a wired connection in a local area network implemented as a mesh network, 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,

the wireless mesh access points including first wireless mesh access points each having a wireless link connection with at least the wired mesh access point, and at least one second wireless mesh access point having the corresponding wireless connection via a wireless link connection with at least one of the first wireless mesh access points, wherein routing protocols are not implemented within any of the connected mesh access points;

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 according to a routing protocol that is executed by the means for executing on behalf of the connected mesh access points, the mesh table identifying all of the connecting links for the mesh access points connected in the mesh network;

the means for executing further configured for creating truncated forwarding tables for each of the corresponding connected mesh access points based on the mesh table, each truncated forwarding table truncated by the means for executing to a prescribed forwarding horizon based on deletion of one or more entries relative to a forwarding table for he corresponding connected mesh access point, at least one of the truncated forwarding tables including first and second entries for reaching a prescribed destination at respective first and second costs, and the means for executing supplying the corresponding truncated forwarding table to the corresponding connected mesh access point via a corresponding tunnel established between the mesh controller and the corresponding connected mesh access point, the corresponding truncated forwarding table enabling the corresponding connected mesh access point to execute link layer forwarding via a path distinct from the corresponding tunnel.

24. An apparatus comprising:

means for connecting to a mesh controller in a local area network implemented as a mesh network and via a wireless connection with an intermediate wireless mesh access point, the intermediate wireless mesh access point having a corresponding wireless connection for reaching the mesh controller;

means for sending connection information to the mesh controller that identifies each connection by the apparatus with any neighboring mesh access point including the intermediate mesh access point, wherein routing protocols are not implemented within the apparatus; and

means for storing a truncated forwarding table having been received from the mesh controller via a tunnel established between the mesh controller and the apparatus, the truncated forwarding table specifying destination mesh access points in the mesh network, the truncated forwarding table created by the mesh controller according to a routing protocol that is executed by the mesh controller on behalf of the apparatus, the truncated forwarding table truncated by the mesh controller to a prescribed forwarding horizon based on deletion of one or more entries relative to a forwarding table for he corresponding connected mesh access point, the truncated forwarding table specifying, for each destination mesh access point in the truncated forwarding table, at least one link identifier for reaching the corresponding destination mesh access point via one of the neighboring mesh access points, the truncated forwarding table including first and second entries for reaching a prescribed destination at respective first and second costs, the truncated forwarding table enabling the apparatus to execute link layer forwarding via a path distinct from the corresponding tunnel.