802.11 mesh architecture

• US 8,738,013 B2
• Filed: 04/17/2007
• Issued: 05/27/2014
• Est. Priority Date: 04/24/2006
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell World Trade Limited (Marvell Technology Group Limited)
• Inventors: Banerjea, Raja, Goel, Sandesh
• Primary Examiner(s): MEHRA, INDER P
• Application Number:
  US11/736,071
• Publication Number:
  US 20070248065A1
• Time in Patent Office: 2,597 Days
• Field of Search: 370/238, 370/254, 370/315, 370/338, 370/392, 370/401, 370/351, 370/312, 370/349, 370/352, 370/389, 370/406, 455/41.2, 455/426.2, 455/445, 709/222, 709/238
• US Class Current: 455/445
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A wireless network device includes a forwarding table and a mesh routing module. The forwarding table is configured to store direct and reverse entries, each including a destination address, a next hop address, and a metric. The metric of the direct entries corresponds to a route from the wireless network device to the destination address. The metric of the reverse entries corresponds to a route from the destination address to the wireless network device. The mesh routing module is configured to (i) wirelessly receive route discovery packets, including a first route discovery packet, and (ii) create, based on the route discovery packets, corresponding direct entries and reverse entries in the forwarding table. The mesh routing module is configured to, in response to receiving the first route discovery packet, create a corresponding direct entry in the forwarding table and create a corresponding reverse entry in the forwarding table.

Claims

1. A wireless network device comprising:

a forwarding table configured to store direct entries and reverse entries, each of the direct entries and the reverse entries respectively including a destination address, a next hop address, and a metric, wherein the metric of the direct entries corresponds to a route from the wireless network device to the destination address, and wherein the metric of the reverse entries corresponds to a route from the destination address to the wireless network device; and

a mesh routing module configured to (i) wirelessly receive route discovery packets including a first route discovery packet and (ii) create, based on the route discovery packets, corresponding direct entries and reverse entries in the forwarding table,

wherein the mesh routing module is configured to, in response to receiving the first route discovery packet, create a corresponding direct entry in the forwarding table and create a corresponding reverse entry in the forwarding table.

2. The wireless network device of claim 1, wherein:

the route discovery packets include a second route discovery packet including a metric and a source address;

the mesh routing module is configured to, in response to receiving the second route discovery packet from a second wireless network device, create a second reverse entry in the forwarding table;

the next hop address of the second reverse entry is set to an address of the second wireless network device;

the destination address of the second reverse entry is set to the source address of the second route discovery packet; and

the metric of the second reverse entry is set to the metric of the second route discovery packet.

3. The wireless network device of claim 2, wherein:

the route discovery packets include a first route reply packet;

the first route reply packet includes a reply destination address; and

the mesh routing module is configured to, in response to receiving the first route reply packet, (i) identify ones of the reverse entries that have the reply destination address, and (ii) transmit the first route reply packet to the next hop address of a selected one of the identified reverse entries.

4. The wireless network device of claim 3, wherein the mesh routing module is configured to select the selected one of the identified reverse entries based on the metrics of the identified reverse entries.

5. The wireless network device of claim 3, wherein:

the reverse entries each include a sequence number; and

the mesh routing module is configured to set the sequence number of the reverse entry to a sequence number received in the second route discovery packet.

6. The wireless network device of claim 5, wherein the first route reply packet includes a reply sequence number, and wherein the mesh routing module is configured to (i) choose ones of the identified reverse entries that have the reply sequence number and (ii) select one of the chosen reverse entries based on the metrics of the chosen reverse entries.

7. The wireless network device of claim 1, wherein:

the route discovery packets include a first route request for a requested destination address; and

the mesh routing module is configured to, in response to receiving the first route request, (i) identify ones of the direct entries that have the requested destination address, and (ii) selectively respond to the first route request with the next hop address of a selected one of the identified direct entries.

8. The wireless network device of claim 7, wherein the mesh routing module is configured to select the selected one of the identified direct entries based on the metrics of the identified direct entries.

9. The wireless network device of claim 7, wherein the direct entries of the forwarding table each include an expiration indicator, and wherein the mesh routing module is configured to select the selected one of the identified direct entries based on the expiration indicators of the identified direct entries.

10. The wireless network device of claim 1, wherein the mesh routing module is configured to (i) transmit a second route discovery packet including a cumulative metric to a second wireless network device, (ii) determine the cumulative metric based on a received metric and a link metric, and (iii) determine the link metric based on a state of charge of the wireless network device and a transmission parameter of the second route discovery packet.

11. The wireless network device of claim 10, wherein the link metric increases as the state of charge decreases.

12. The wireless network device of claim 10, wherein the transmission parameter comprises energy used to transmit the second route discovery packet.

13. The wireless network device of claim 12, wherein the link metric is proportional to the energy used and inversely related to the state of charge.

14. The wireless network device of claim 12, wherein the mesh routing module is configured to transmit the second route discovery packet using increasing amounts of energy.

15. A method for operating a wireless network device, the method comprising:

wirelessly receiving route discovery packets, wherein the route discovery packets include a first route discovery packet; and

storing direct entries and reverse entries in a forwarding table based on the route discovery packets, each of the direct entries and the reverse entries including a destination address, a next hop address, and a metric, wherein the metric of the direct entries corresponds to a route from the wireless network device to the destination address, and wherein the metric of the reverse entries corresponds to a route from the destination address to the wireless network device,

wherein storing the direct entries and the reverse entries in the forwarding table includes, in response to receiving the first route discovery packet, storing a corresponding direct entry in the forwarding table and storing a corresponding reverse entry in the forwarding table.

16. The method of claim 15, further comprising:

receiving a second route discovery packet including a metric and a source address from a second wireless network device; and

creating a second reverse entry in the forwarding table, wherein the next hop address of the second reverse entry is set to an address of the second wireless network device, the destination address of the second reverse entry is set to the source address of the second route discovery packet, and the metric of the second reverse entry is set to the metric of the second route discovery packet.

17. The method of claim 16, further comprising:

wirelessly receiving a first route reply packet, the first route reply packet including a reply destination address;

identifying ones of the reverse entries that have the reply destination address; and

transmitting the first route reply packet to the next hop address of a selected one of the identified reverse entries.

18. The method of claim 17, wherein the selected one of the identified reverse entries is selected based on the metrics of the identified reverse entries.

19. The method of claim 17, wherein the reverse entries each include a sequence number, and wherein the method further comprises setting the sequence number of the second reverse entry to a sequence number received in the second route discovery packet.

20. The method of claim 19, wherein the first route reply packet includes a reply sequence number, and wherein the method further comprises:

choosing ones of the identified reverse entries that have the reply sequence number; and

selecting one of the chosen reverse entries based on the metrics of the chosen reverse entries.

21. The method of claim 15, further comprising:

receiving a route request for a requested destination address;

identifying ones of the direct entries that have the requested destination address; and

selectively responding to the route request with the next hop address of a selected one of the identified direct entries.

22. The method of claim 21, wherein the selected one of the identified direct entries is selected based on the metrics of the identified direct entries.

23. The method of claim 21, wherein the direct entries of the forwarding table each include an expiration indicator, and wherein the selected one of the identified direct entries is selected based on the expiration indicators of the identified direct entries.

24. The method of claim 15, further comprising:

receiving a second route discovery packet including a metric;

determining a link metric based on a state of charge of the wireless network device and a transmission parameter of a third route discovery packet;

determining a cumulative metric based on (i) the metric received from the second route discovery packet and the link metric; and

transmitting the third route discovery packet wirelessly to a first wireless network device, wherein the third route discovery packet includes the cumulative metric.

25. The method of claim 24 wherein the link metric increases as the state of charge decreases.

26. The method of claim 24, wherein the transmission parameter comprises energy used to transmit the third route discovery packet.

27. The method of claim 26, wherein the link metric is proportional to the energy used and inversely related to the state of charge.

28. The method of claim 26, further comprising transmitting the third route discovery packet using increasing amounts of energy.