Multi-metric routing calculations

• US 7,948,966 B2
• Filed: 09/30/2008
• Issued: 05/24/2011
• Est. Priority Date: 10/01/2007
• Status: Active Grant

• Current Assignee: Raytheon Company (Rtx Corporation)
• Original Assignee: POWERWAVE COGNITION, INC.
• Inventors: Hughes, Timothy J., Kishaba, Wendell Y., Trinh, Chau T.
• Primary Examiner(s): Yao, Kwang B
• Assistant Examiner(s): Loo, Juvena
• Application Number:
  US12/242,747
• Publication Number:
  US 20090116393A1
• Time in Patent Office: 966 Days
• Field of Search: 370351-363, 370/395.4, 370/395.41, 370/395.42, 370/395.43, 370/395.5, 370/395.51, 370/395.52
• US Class Current: 370/351
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04W 40/04 based on wireless node resources
• CPC Class Codes: H04W 40/14 based on stability
• CPC Class Codes: H04W 40/16 based on interference
• CPC Class Codes: H04W 40/30 for proactive routing

Abstract

In a Mobile Ad Hoc Network (MANET), multi-metric information is gathered and applied to a cost-based route calculation. In particular, each node gathers resource metrics from neighboring of nodes, along with data rate and reliability information for data links to and from the node. This information is applied to a costing algorithm such as Dykstra'"'"' Open Shortest Path First algorithm to obtain routes through the network. This approach may be adapted with suitable modifications to use with unicast traffic or with a multicast forwarding group.

Claims

1. A method for determining routes in an ad hoc network comprising:

receiving a resource metric from each one of a plurality of neighbors of a node, the resource metric indicative of network resources needed by the corresponding one of the plurality of neighbors, wherein the resource metric includes a node weight representing a ratio of bandwidth required for data in to bandwidth required for data out for a corresponding one of the plurality of neighbors, thereby providing a data link layer resource metric for a route calculation;

determining a data rate for a link to each one of the plurality of neighbors using physical layer data that characterizes a rate of data selected according to the physical performance of a wireless communication channel, thereby providing a data rate metric for the route calculation;

determining a reliability for a link to each one of the plurality of neighbors using physical layer data that characterizes a physical reliability of the wireless communication channel, thereby providing a reliability metric for the route calculation;

applying the reliability metric, the data rate metric, and the data link layer bandwidth metric to the route calculation to calculate a plurality of routes within a scope of a Scoped Link State Routing (SLSR) protocol that employs multi-level scoping to reduce overhead, the plurality of routes including a route for each one of a plurality of service levels; and

sharing network reachability information between a first router in the node for an ad hoc wireless network that routes data according to the SLSR protocol and a second router in the node for at least one wired network that routes data according to a protocol selected from the group consisting of Open Shortest Path First, Border Gateway Protocol, and Routing Information Protocol.

2. The method of claim 1 further comprising:

receiving a data packet at the node, the data packet having a service level indicator; and

routing the data packet according to the route for the service level.

3. The method of claim 1 wherein each one of the plurality of service levels imposes different requirements on the route calculation, whereby two or more of the service levels achieve different routing trees through the ad hoc network.

4. The method of claim 1 wherein the route calculation includes a Dykstra Shortest Path First algorithm.

5. The method of claim 1 further comprising load balancing network traffic by providing a tie breaking mechanism to distribute traffic among a number of substantially equal cost ones of the routes.

6. The method of claim 5 wherein the tie breaking mechanism is based upon destination Internet Protocol addresses.

7. The method of claim 1 wherein the route calculation is a unicast route calculation.

8. The method of claim 1 wherein the route calculation is a multicast route calculation.

9. The method of claim 8 wherein the multicast route calculation employs a forwarding group of nodes responsible for forwarding multicast traffic.

10. The method of claim 8 further comprising periodically flooding a member advertisement packet from the node to request membership in a multicast forwarding group.

11. The method of claim 8 further comprising receiving a join request from one of the plurality of neighbors and conditionally relaying the join request when a hop count for the join request does not exceed a predetermined threshold.

12. A computer program product comprising computer executable code stored in a non-transitory computer readable medium that, when executing on one or more computing devices, determines routes in a mobile ad hoc network by performing the steps of:

receiving a resource metric from each one of a plurality of neighbors of a node, the resource metric indicative of network resources needed by the corresponding one of the plurality of neighbors, wherein the resource metric includes a node weight representing a ratio of bandwidth required for data in to bandwidth required for data out for a corresponding one of the plurality of neighbors, thereby providing a data link layer resource metric for a route calculation;

determining a data rate for a link to each one of the plurality of neighbors using physical layer data that characterizes a rate of data selected according to the physical performance of a wireless communication channel, thereby providing a data rate metric for the route calculation;

determining a reliability for a link to each one of the plurality of neighbors using physical layer data that characterizes a physical reliability of the wireless communication channel, thereby providing a reliability metric for the route calculation;

applying the reliability metric, the data rate metric, and the data link layer bandwidth metric to the route calculation to calculate a plurality of routes within a scope of a Scoped Link State Routing (SLSR) protocol that employs multi-level scoping to reduce overhead, the plurality of routes including a route for each one of a plurality of service levels; and

sharing network reachability information between a first router in the node for an ad hoc wireless network that routes data according to the SLSR protocol and a second router in the node for at least one wired network that routes data according to a protocol selected from the group consisting of Open Shortest Path First, Border Gateway Protocol, and Routing Information Protocol.

13. The computer program product of claim 12 further comprising code that performs the steps of:

receiving a data packet at the node, the data packet having a service level indicator; and

routing the data packet according to the route for the service level.

14. The computer program product of claim 12 wherein the route calculation includes a Dykstra Shortest Path First algorithm.

15. The computer program product of claim 12 further comprising code that performs the step of load balancing network traffic by providing a tie breaking mechanism to distribute traffic among a number of substantially equal cost ones of the routes.

16. The computer program product of claim 12 wherein the route calculation is a unicast route calculation.

17. The computer program product of claim 12 wherein the route calculation is a multicast route calculation.

18. The computer program product of claim 17 wherein the multicast route calculation employs a forwarding group of nodes responsible for forwarding multicast traffic.