Methods and apparatus for identifying a distance-vector route associated with a wireless mesh network

• US 7,697,459 B2
• Filed: 01/05/2005
• Issued: 04/13/2010
• Est. Priority Date: 01/05/2005
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Singh, Hakirat, Yarvis, Mark D., Conner, W. Steven, Rangarajan, Anand
• Primary Examiner(s): Ngo; Ricky
• Assistant Examiner(s): Kao; Wei-Po
• Application Number:
  US11/030,016
• Publication Number:
  US 20060146717A1
• Time in Patent Office: 1,924 Days
• Field of Search: 370/235, 370/236, 370/238, 370/230, 370/231, 370/254, 370/255, 370/351, 370/400, 370/431, 370/432, 370/312, 370/322, 370/348, 370/406, 370/419, 370/420, 370/437
• US Class Current: 370/255
• 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/02 Topology update or discovery
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04W 40/16 based on interference

Abstract

Embodiments of methods and apparatus for identifying a distance-vector route associated with a wireless mesh network are generally described herein. Other embodiments may be described and claimed.

Claims

1. A method for selecting a routing path in a communication network, wherein the communication network includes a plurality of serial communication links, wherein each of the plurality of serial communication links use either a first communication channel or a second communication channel, the method comprising:

determining, at a receiving wireless mesh node, a first desired path to use if the first communication channel is operating as a bottleneck channel, the first desired path including a first plurality of serial communication links between a plurality of adjacent nodes that include a source wireless mesh node, one or more intermediate wireless mesh nodes, and the receiving wireless mesh node, wherein at least one of the first plurality of serial communication links in the first desired path use the first communication channel and at least another of the first plurality of serial communication links in the first desired path use the second communication channel;

determining, at the receiving wireless mesh node, a second desired path to use if the second communication channel is operating as the bottleneck channel, the second desired path including a second plurality of serial communication links between another plurality of adjacent nodes that include the source wireless mesh node, at least one intermediate wireless mesh node, and the receiving wireless mesh node, wherein at least one of the second plurality of serial communication links in the second desired path use the first communication channel and at least another of the second plurality of serial communication links in the second desired path use the second communication channel;

generating, at the receiving wireless mesh node, a matrix of metric information to provide an indication of a number of the first plurality of serial communication links of the first desired path that use the first communication channel when the first communication channel is operating as a bottleneck channel and to further provide an indication of a number of the second plurality of serial communication links of the second desired path that use the second communication channel when the second communication channel is operating as a bottleneck channel.

2. A method as defined in claim 1, wherein generating the matrix at the receiving wireless mesh node comprises updating the matrix in response to receipt of a route request message from one or more intermediate nodes.

3. A method as defined in claim 1, further comprising selecting an end-to-end route to the source node based on route request information at the receiving wireless mesh node, and wherein the receiving wireless mesh node is a destination node of the end-to-end route.

4. A method as defined in claim 1, further comprising:

providing, by the receiving wireless mesh node, route request information based on the matrix to a second receiving wireless mesh node of the plurality of mesh nodes.

5. A method as defined in claim 4, wherein providing the route request information based on the matrix to the second receiving wireless mesh node comprises generating a route request table associated with the receiving wireless mesh node.

6. A method as defined in claim 4, wherein providing the route request information comprises generating a route request message having the route request information at the receiving wireless mesh node, wherein the receiving wireless mesh node is an intermediate node of an end-to-end route.

7. A method as defined in claim 4, wherein providing the route request information comprises generating a route reply message having the route request information at the receiving wireless mesh node, wherein the receiving wireless mesh node is a destination node of an end-to-end route.

8. A method as defined in claim 4, further comprising generating routing information based on the route request information at the receiving wireless mesh node.

9. A method as defined in claim 4, further comprising transmitting one of a route request message having the route request information to an intermediate node of an end-to-end route or a route reply message having the route request information to the source node of the end-to-end route.

10. A method as defined in claim 1, further comprising:

selecting a routing path, based at least in part on the generated matrix, for communication between the source wireless mesh node and the receiving wireless mesh node, that includes a plurality of links that use the first and/or the second communication channel.

11. An article of manufacture including a computer-readable storage medium, and instructions stored in the storage medium, configured to enable a machine to select a routing path in a communication network, wherein the communication network includes a plurality of serial communication links, wherein each of the plurality of serial communication links use either a first communication channel or a second communication channel, wherein the instructions are configured to enable machine to select the routing path by enabling the machine to:

determine, at a receiving wireless mesh node, a first desired path to use if the first communication channel is operating as a bottleneck channel, the first desired path including a first plurality of serial communication links between a plurality of adjacent nodes that include a source wireless mesh node, one or more intermediate wireless mesh nodes, and the receiving wireless mesh node, wherein at least one of the first plurality of serial communication links in the first desired path use the first communication channel and at least another of the first plurality of serial communication links in the first desired path use the second communication channel;

determine, at the receiving wireless mesh node, a second desired path to use if the second communication channel is operating as the bottleneck channel, the second desired path including a second plurality of serial communication links between another plurality of adjacent nodes that include the source wireless mesh node, at least one intermediate wireless mesh node, and the receiving wireless mesh node, wherein at least one of the second plurality of serial communication links in the second desired path use the first communication channel and at least another of the second plurality of serial communication links in the second desired path use the second communication channel;

generate, at the receiving wireless mesh node, a matrix of channel metrics to provide an indication of a number of the first plurality of serial communication links of the first desired path that use the first communication channel when the first communication channel is operating as a bottleneck channel and to further provide an indication of a number of the second plurality of serial communication links of the second desired path that use the second communication channel when the second communication channel is operating as a bottleneck channel.

12. An article of manufacture as defined in claim 11, wherein the instructions are further configured to enable the machine to generate the matrix at the receiving wireless mesh node by updating the matrix in response to receipt of a route request message.

13. An article of manufacture as defined in claim 11, wherein the instructions are further configured to enable the machine to provide route request information based on the matrix to a second receiving wireless mesh node of the plurality of mesh nodes.

14. An article of manufacture as defined in claim 13, wherein the instructions are further configured to enable the machine to provide the route request information based on the matrix to the second receiving wireless mesh node by generating a route request table associated with the receiving wireless mesh node.

15. An article of manufacture as defined in claim 13, wherein the instructions are further configured to enable the machine to provide the route request information by generating a route request message having the route request information at the receiving wireless mesh node, and wherein the receiving wireless mesh node is an intermediate node of an end-to-end route.

16. An article of manufacture as defined in claim 13, wherein the instructions are further configured to enable the machine to provide the route request information by generating a route reply message having the route request information at the receiving wireless mesh node, and wherein the receiving wireless mesh node is a destination node of an end-to-end route.

17. An article of manufacture as defined in claim 13, wherein the instructions are further configured to enable the machine to generate routing information based on the route request information at the receiving wireless mesh node.

18. An article of manufacture as defined in claim 13, wherein the instructions are further configured to enable the machine to select an end-to-end route to the source node based on the route request information at the receiving wireless mesh node, and wherein the receiving wireless mesh node is a destination node of the end-to-end route.

19. An apparatus for selecting a routing path in a communication network, wherein the communication network includes a plurality of serial communication links, wherein each of the plurality of serial communication links use either a first communication channel or a second communication channel, the apparatus comprising:

a first communication interface associated with the first communication channel;

a second communication interface associated with the second communication channel; and

a generator coupled to the first and second communication interfaces and configured to;

determine, at a receiving wireless mesh node, a first desired path to use if the first communication channel is operating as a bottleneck channel, the first desired path including a first plurality of serial communication links between a plurality of adjacent nodes that include a source wireless mesh node, one or more intermediate wireless mesh nodes, and the receiving wireless mesh node, wherein at least one of the first plurality of serial communication links in the first desired path use the first communication channel and at least another of the first plurality of serial communication links in the first desired path use the second communication channel;

determine, at the receiving wireless mesh node, a second desired path to use if the second communication channel is operating as the bottleneck channel, the second desired path including a second plurality of serial communication links between another plurality of adjacent nodes that include the source wireless mesh node, at least one intermediate wireless mesh node, and the receiving wireless mesh node, wherein at least one of the second plurality of serial communication links in the second desired path use the first communication channel and at least another of the second plurality of serial communication links in the second desired path use the second communication channel; and

generate, at the receiving wireless mesh node, a matrix of metric information to provide an indication of a number of the first plurality of serial communication links of the first desired path that use the first communication channel when the first communication channel is operating as a bottleneck channel and to further provide an indication of a number of the second plurality of serial communication links of the second desired path that use the second communication channel when the second communication channel is operating as a bottleneck channel.

20. An apparatus as defined in claim 19, wherein the generator is further configured to provide, at the receiving wireless mesh node, route request information based on the matrix to a second receiving wireless mesh node of the plurality of mesh nodes.

21. An apparatus as defined in claim 20, wherein the generator is configured to generate a route request message having the route request information at the receiving wireless mesh node, and wherein the receiving wireless mesh node is an intermediate node of an end-to-end route.

22. An apparatus as defined in claim 20, wherein the generator is configured to generate a route reply message having the route request information at the receiving wireless mesh node, and wherein the receiving wireless mesh node is a destination node of an end-to-end route.

23. An apparatus as defined in claim 20, wherein the generator is configured to generate routing information based on the route request information at the receiving wireless mesh node.

24. An apparatus as defined in claim 20 further comprising a selector to select an end-to-end route to the source node based on the route request information at the receiving wireless mesh node, and wherein the receiving wireless mesh node is a destination node of the end-to-end route.

25. A system for selecting a routing path in a communication network that includes a plurality of serial communication links, wherein each of the plurality of serial communication links use either a first communication channel or a second communication channel, the system comprising:

a flash memory; and

a processor coupled to the flash memory and configured to;

determine, at a receiving wireless mesh node, a first desired path to use when a first communication channel is operating as a bottleneck channel, the first desired path including a first plurality of serial communication links between a plurality of adjacent nodes that include a source wireless mesh node, one or more intermediate wireless mesh nodes, and the receiving wireless mesh node, wherein at least one of the first plurality of serial communication links in the first desired path use the first communication channel and at least another of the first plurality of serial communication links in the first desired path use the second communication channel;

determine, at the receiving wireless mesh node, a second desired path to use when a second communication channel is operating as the bottleneck channel, the second desired path including a second plurality of serial communication links between another plurality of adjacent nodes that include the source wireless mesh node, at least one intermediate wireless mesh node, and the receiving wireless mesh node, wherein at least one of the second plurality of serial communication links in the second desired path use the first communication channel and at least another of the second plurality of serial communication links in the second desired path use the second communication channel; and

generate, at the receiving wireless mesh node, a matrix of metric information to provide an indication of a number of the first plurality of serial communication links of the first desired path that use the first communication channel when the first communication channel is operating as a bottleneck channel and to further provide an indication of a number of the second plurality of serial communication links of the second desired path that use the second communication channel when the second communication channel is operating as a bottleneck channel.

26. A system as defined in claim 25, wherein the processor is configured to update the matrix in response to receipt of a route request message.

27. A system as defined in claim 25, wherein the processor is further configured to provide, at the receiving wireless mesh node, route request information based on the matrix to a second receiving wireless mesh node of the plurality of mesh nodes.

28. A system as defined in claim 27, wherein the processor is configured to generate a route request message having the route request information at the receiving wireless mesh node, and wherein the receiving wireless mesh node is an intermediate node of an end-to-end route.

29. A system as defined in claim 27, wherein the processor is configured to generate a route reply message having the route request information at the receiving wireless mesh node, and wherein the receiving wireless mesh node is a destination node of an end-to-end route.

30. A system as defined in claim 27, wherein the processor is configured to generate routing information based on the route request information at the receiving wireless mesh node.

31. A system as defined in claim 27, wherein the processor is configured to select an end-to-end route to the source node based on the route request information at the receiving wireless mesh node, and wherein the receiving wireless mesh node is a destination node of the end-to-end route.