Path shortening in a wireless mesh network

• US 8,111,684 B2
• Filed: 03/30/2007
• Issued: 02/07/2012
• Est. Priority Date: 03/30/2007
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Thubert, Pascal, Wetterwald, Patrick, Ribiere, Vincent Jean, Moon, Billy Gayle, Kruys, Johannes Petrus
• Primary Examiner(s): Corsaro, Nick
• Assistant Examiner(s): PATEL, MAHENDRA R
• Application Number:
  US11/729,886
• Publication Number:
  US 20080240078A1
• Time in Patent Office: 1,775 Days
• Field of Search: 370/338, 370/254, 370/351, 370/312, 370/331, 370/401, 455/411, 455/41, 709/223
• US Class Current: 370/351
• CPC Class Codes: H04W 40/08 based on transmission power
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point

Abstract

In one embodiment, a method includes a mesh point receiving mesh advertisement messages from advertising mesh points of a wireless mesh network having a mesh portal with a wired connection to a wired network. Each mesh advertisement message specifies a corresponding metric for reaching the mesh portal and has a corresponding signal strength indicator. An ordered group of parent access points, ordered based on the respective metrics, is generated from among the advertising mesh points, starting with a first parent access point having a corresponding optimum metric for reaching the mesh portal and independent of the corresponding signal strength indicator. A registration message is sent to each of the parent access points identifying a corresponding specified priority based on a corresponding position in the ordered group, for use by the corresponding parent access point in selecting a minimum interframe spacing for forwarding a wireless packet received from the mesh point.

Claims

1. A method comprising:

receiving, by a mesh point, mesh advertisement messages from respective advertising mesh points of a wireless mesh network having a mesh portal, the mesh portal having a wired connection to a wired network, each mesh advertisement message specifying a corresponding metric for the corresponding advertising mesh point reaching the mesh portal and having a corresponding signal strength indicator;

generating by the mesh point from among the advertising mesh points an ordered group of parent access points each providing a corresponding mesh link for reachability for the mesh point to the mesh portal, the ordered group ordered based on the respective metrics specified in the respective mesh advertisement messages, the ordered group starting with a first parent access point chosen by the mesh point based on the first parent access point having a corresponding optimum metric for reaching the mesh portal and chosen independent of the corresponding signal strength indicator, and

sending by the mesh point to each of the parent access points a corresponding registration message identifying a corresponding specified priority based on a corresponding position in the ordered group, for use by the corresponding parent access point in selecting a corresponding distinct minimum interframe spacing for forwarding toward the mesh portal a wireless packet received from the mesh point via the corresponding mesh link;

wherein the generating includes;

identifying the first parent access point based solely on the corresponding metric being the optimum metric relative to the other received metrics,

identifying from among the advertising mesh points a second parent access point based on correlating the corresponding metric relative to an average of the received metrics, and based on correlating the corresponding signal strength indicator relative to an average of the received signal strength indicators, and

identifying from among the advertising mesh points a third parent access point based on the corresponding signal strength indicator having a maximum value relative to the other received signal strength indicators, the ordered group of parent access points including an order of the first parent access point, the second parent access point, and the third parent access point.

2. The method of claim 1, wherein the corresponding priority value of the corresponding first parent access point corresponds to a minimum spacing value for the minimum interframe spacing relative to the other parent access points, each successive parent access point following the first parent access point having a successively longer spacing value for the minimum interframe spacing.

3. The method of claim 1, wherein the sending includes one of specifying the specified priority according to one of an enhanced distributed channel access (EDCA) according to IEEE 802.11e protocol, or specifying the specified priority as a corresponding Short Interframe Spacing (SIFS) value to be used as the minimum interframe spacing according to IEEE 802.11 protocol.

4. The method of claim 1, wherein each received metric is expressed as a corresponding cost to reach the mesh portal, the optimum metric identified as having a minimum cost to reach the mesh portal relative to the other received metrics.

5. The method of claim 1, wherein each received metric is expressed as a corresponding ease in reaching the mesh portal, the optimum metric identified as having a highest ease in reaching the mesh portal relative to the other received metrics.

6. The method of claim 1, further comprising:

calculating a revised metric for the mesh point reaching the mesh portal, and

outputting by the mesh point an advertisement message specifying the mesh point can reach the mesh portal according to the revised metric.

7. The method of claim 6, further comprising:

receiving a second registration message from an attached mesh point and that identifies a corresponding specified priority to be used by the mesh point in selecting the minimum interframe spacing in forwarding a transmitted packet having been transmitted by the attached mesh point;

receiving the transmitted packet from the attached mesh point via a wireless link;

if the wireless link is inactive for the selected minimum interframe spacing following completed transmission of the transmitted packet, initiating broadcasting the transmitted packet to the parent access points upon the wireless link having been inactive for the selected minimum interframe spacing;

if the wireless link becomes active following completed transmission of the transmitted packet and before completion of the selected minimum interframe spacing, dropping the transmitted packet.

8. The method of claim 6, wherein the calculating includes:

identifying the average metric from among the parent access points; and

determining the revised metric based on adding to the average metric a corresponding link cost for reaching the corresponding parent access point having the average metric.

9. An apparatus comprising:

a wireless mesh interface circuit configured for receiving mesh advertisement messages from respective advertising mesh points of a wireless mesh network having a mesh portal, the mesh portal having a wired connection to a wired network, each mesh advertisement message specifying a corresponding metric for the corresponding advertising mesh point reaching the mesh portal and having a corresponding signal strength indicator; and

a parent selection circuit configured for generating, in the apparatus, from among the advertising mesh points an ordered group of parent access points each providing a corresponding mesh link for reachability for the apparatus to the mesh portal, the ordered group ordered based on the respective metrics specified in the respective mesh advertisement messages, the ordered group starting with a first parent access point chosen by the parent selection circuit based on the first parent access point having a corresponding optimum metric for reaching the mesh portal and chosen independent of the corresponding signal strength indicator;

the parent selection circuit further configured for generating, for output via the wireless mesh interface circuit to each of the parent access points, a corresponding registration message identifying a corresponding specified priority based on a corresponding position in the ordered group, for use by the corresponding parent access point in selecting a corresponding distinct minimum interframe spacing for forwarding toward the mesh portal a wireless packet received from the apparatus via the corresponding mesh link;

wherein the parent selection circuit is configured for generating the ordered group based on;

identifying the first parent access point based solely on the corresponding metric being the optimum metric relative to the other received metrics,

identifying from among the advertising mesh points a second parent access point based on correlating the corresponding metric relative to an average of the received metrics, and based on correlating the corresponding signal strength indicator relative to an average of the received signal strength indicators, and

identifying from among the advertising mesh points a third parent access point based on the corresponding signal strength indicator having a maximum value relative to the other received signal strength indicators, the ordered group of parent access points including an order of the first parent access point, the second parent access point, and the third parent access point.

10. The apparatus of claim 9, wherein the corresponding priority value of the corresponding first parent access point corresponds to a minimum spacing value for the minimum interframe spacing relative to the other parent access points, each successive parent access point following the first parent access point having a successively longer spacing value for the minimum interframe spacing.

11. The apparatus of claim 9, wherein the parent selection circuit is configured for specifying the specified priority according to one of an enhanced distributed channel access (EDCA) according to IEEE 802.11e protocol, or specifying the specified priority as a corresponding Short Interframe Spacing (SIFS) value according to IEEE 802.11 protocol.

12. The apparatus of claim 9, wherein each received metric is expressed as a corresponding cost to reach the mesh portal, the optimum metric identified as having the minimum cost to reach the mesh portal relative to the other received metrics.

13. The apparatus of claim 9, wherein each received metric is expressed as a corresponding ease in reaching the mesh portal, the optimum metric identified as having a highest ease in reaching the mesh portal relative to the other received metrics.

14. The apparatus of claim 9, further comprising a routing circuit configured for calculating a revised metric for the apparatus reaching the mesh portal, and generating, for output by the wireless mesh interface circuit, an advertisement message specifying the apparatus can reach the mesh portal according to the revised metric.

15. The apparatus of claim 14, further comprising a memory circuit, wherein:

the wireless mesh interface circuit is configured for receiving a second registration message from an attached mesh point and that identifies a corresponding specified priority to be used by the apparatus in selecting the minimum interframe spacing in forwarding a transmitted packet having been transmitted by the attached mesh point;

the routing circuit configured for storing an address of the attached mesh point and the corresponding specified priority in the memory circuit;

the wireless mesh interface circuit is configured for responding to reception of the transmitted packet from the attached mesh point, via a wireless link, by initiating broadcasting the transmitted packet to the parent access points if the wireless link has been inactive for selected minimum interframe spacing following completed transmission of the transmitted packet, else dropping the transmitted packet if the wireless link becomes active following completed transmission of the transmitted packet and before completion of the selected minimum interframe spacing.

16. The apparatus of claim 14, wherein routing circuit is configured for:

identifying the average metric from among the parent access points; and

determining the revised metric based on adding to the average metric a corresponding link cost for reaching the corresponding parent access point having the average metric.

17. An apparatus comprising:

means for receiving mesh advertisement messages from respective advertising mesh points of a wireless mesh network having a mesh portal, the mesh portal having a wired connection to a wired network, each mesh advertisement message specifying a corresponding metric for the corresponding advertising mesh point reaching the mesh portal and having a corresponding signal strength indicator; and

means for generating, in the apparatus, from among the advertising mesh points an ordered group of parent access points each providing a corresponding mesh link for reachability for the apparatus to the mesh portal, the ordered group ordered based on the respective metrics specified in the respective mesh advertisement messages, the ordered group starting with a first parent access point chosen by the means for generating based on the first parent access point having a corresponding optimum metric for reaching the mesh portal and chosen independent of the corresponding signal strength indicator;

the means for generating further configured for generating, for output to each of the parent access points, a corresponding registration message identifying a corresponding specified priority based on a corresponding position in the ordered group, for use by the corresponding parent access point in selecting a corresponding distinct minimum interframe spacing for forwarding toward the mesh portal a wireless packet received from the apparatus via the corresponding mesh link;

wherein the means for generating further is configured for generating the ordered group based on;

identifying the first parent access point based solely on the corresponding metric being the optimum metric relative to the other received metrics,

identifying from among the advertising mesh points a second parent access point based on correlating the corresponding metric relative to an average of the received metrics, and based on correlating the corresponding signal strength indicator relative to an average of the received signal strength indicators, and

identifying from among the advertising mesh points a third parent access point based on the corresponding signal strength indicator having a maximum value relative to the other received signal strength indicators, the ordered group of parent access points including an order of the first parent access point, the second parent access point, and the third parent access point.