System and method for link quality source routing

• US 7,978,672 B2
• Filed: 01/19/2010
• Issued: 07/12/2011
• Est. Priority Date: 02/23/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Padhye, Jitendra D., Zill, Brian D., Draves, Richard Powell Jr.
• Primary Examiner(s): Nguyen; Brian D
• Application Number:
  US12/689,626
• Publication Number:
  US 20100118727A1
• Time in Patent Office: 539 Days
• Field of Search: 370/252, 370/328, 370/338, 370/352, 370/351, 370/469, 370/471, 370/389, 370/392, 370/229, 370/230, 370/235
• US Class Current: 370/338
• 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/26 Route discovery packet
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing

Abstract

Systems and methods for routing packets by nodes in an ad hoc network in accordance with a link quality source routing protocol are disclosed. Route discovery, route maintenance, and metric maintenance are designed to propagate and keep current link quality measurements. Metric maintenance includes a reactive approach for links that a node is currently using to route packets, and a proactive mechanism for all links. Nodes are configured to include a send buffer, a maintenance buffer, a request table, link quality metric modules, and preferably a neighbor cache and a link cache. The invention allows for asymmetric links in the network. The invention may be implemented within a virtual protocol interlayer between the link and network layers. The invention may employ any particular link quality metrics, including metrics based on probing techniques as well as metrics based on knowledge gained in other ways.

Claims

1. A system for link-state source routing in an ad hoc network, the system comprising:

a send buffer that holds packets while route discovery is performed;

a maintenance buffer that is used for route maintenance;

a request table that is used to identify duplicate route discovery requests;

at least one link quality metric module that determines quality of links to neighboring nodes; and

a neighbor cache for translating layer 2.5 virtual addresses into physical addresses,

wherein the link-state source routing is performed using the layer 2.5 virtual addresses,

wherein a forwarding node is configured to modify a source route with one or more updated link quality measurements,

wherein a destination node is configured to update the destination node'"'"'s link cache with link quality information for a source route, and to send to a source node a route reply message that conveys link quality information for the source route, and

wherein the route reply message is sent by way of an independently-discovered route from the destination node to the source node.

2. The system of claim 1, further comprising a link cache.

3. The system of claim 1, further comprising a route cache that stores link quality metric information.

4. The system of claim 1 wherein the at least one link quality metric module uses a probing technique.

5. The system of claim 4 wherein the at least one link quality metric module comprises one or more of a per-hop round-trip time metric module, a per-hop packet pair delay metric module, and an expected transmission count metric module.

6. The system of claim 1 wherein the at least one link quality metric module determines quality of links based on received signal strength information.

7. The system of claim 1 wherein the at least one link quality metric module determines quality of links based on a sender'"'"'s IEEE 802.11 retransmission counts.

8. In a multi-hop ad hoc network, a method for discovery of a route from a first node to a target node, the method comprising:

broadcasting, by the first node, a route request message;

receiving, by a neighboring node, the route request;

appending, by the neighboring node, an address of the neighboring node to a path listed in the route request, and adding a link quality measurement;

rebroadcasting, by the neighboring node, the route request;

receiving, by the target node, the route request;

sending, by the target node, a route reply message to the first node, wherein the route reply includes a complete list of link quality measurements for links comprising the route from the first node to the target node;

by a forwarding node, modifying a source route with one or more updated link quality measurements; and

by the target node, updating the target node'"'"'s link cache with link quality information for the source route,

wherein the link quality information is conveyed using layer 2.5 virtual addresses, and

wherein the route reply message is sent by way of an independently-discovered route from the target node to the first node.

9. The method of claim 8 wherein the sending the route reply to the first node is by way of an independently-discovered source route from the target node to the first node.

10. The method of claim 8 wherein the link quality measurement is based on a probing technique.

11. The method of claim 10 wherein the link quality measurement is based on one of a per-hop round-trip time metric, a per-hop packet pair delay metric, and an expected transmission count metric.

12. The method of claim 8 wherein the link quality measurement is based on received signal strength information.

13. The method of claim 8 wherein the link quality measurement is based on a sender'"'"'s IEEE 802.11 retransmission counts.

14. In a multi-hop ad hoc network, a method for conveying link quality information for a source route listed in a data packet, the source route originating at a source node and ending at a destination node, the method comprising:

by a forwarding node, modifying the source route with one or more updated link quality measurements; and

by the destination node, updating the destination node'"'"'s link cache with link quality information for the source route, and sending to the source node a route reply message that conveys link quality information for the source route,

wherein the link quality information is conveyed using layer 2.5 virtual addresses, and

wherein the route reply message is sent by way of an independently-discovered route from the destination node to the source node.

15. The method of claim 14 wherein the one or more updated link quality measurements are based on a probing technique.

16. The method of claim 15 wherein the one or more updated link quality measurements are based on one of a per-hop round-trip time metric, a per-hop packet pair delay metric, and an expected transmission count metric.

17. The method of claim 14 wherein the one or more updated link quality measurements are based on received signal strength information.

18. The method of claim 14 wherein the one or more updated link quality measurements are based on a sender'"'"'s IEEE 802.11 retransmission counts.