Path selection based on hop metric distributions

• US 9,331,931 B2
• Filed: 02/28/2012
• Issued: 05/03/2016
• Est. Priority Date: 02/28/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hui, Jonathan W., Vasseur, Jean-Philippe
• Primary Examiner(s): Baig, Adnan
• Application Number:
  US13/406,795
• Publication Number:
  US 20130223229A1
• Time in Patent Office: 1,526 Days
• Field of Search: 370/238
• US Class Current: 1/1
• 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: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

In one embodiment, a network device determines, for each particular path of a plurality of paths in a computer network, a hop metric distribution that indicates, for each interval of the hop metric distribution, a number of hops along the particular path that have a hop metric value within a corresponding interval. As such, the device may then select a path from the plurality of paths that minimizes the number of hops with correspondingly poor hop metric values along the selected path based on the hop metric distribution, and may forward traffic on the selected path, accordingly.

Claims

1. A method, comprising:

determining, for each particular path of a plurality of paths in a computer network, a hop metric distribution that indicates, for each interval of a plurality of intervals in the hop metric distribution, a number of hops along the particular path that have a hop metric value within each corresponding interval of a plurality of intervals provided in the hop metric distribution, wherein each particular path includes a plurality of hops and the hop metric distribution associates each of the plurality of hops with one of the plurality of intervals, wherein the hop metric distribution is adaptive;

selecting a path from the plurality of paths that minimizes the number of hops associated with an interval within the plurality of intervals that has a poor hop metric value along the selected path based on a number of hops in each interval of the hop metric distribution; and

forwarding traffic on the selected path.

2. The method as in claim 1, further comprising:

adding a particular hop to the distribution by;

in response to a corresponding hop metric value of the particular hop being within an existing interval, incrementing the number of hops within that corresponding interval; and

in response to the corresponding hop metric value of the hop not being within an existing interval, adjusting the intervals of the hop metric distribution to include the corresponding hop metric value of the particular hop.

3. The method as in claim 2, wherein adjusting comprises one of either adding a new interval to the hop metric distribution, or extending existing interval boundaries.

4. The method as in claim 2, wherein a number of intervals within the hop metric distribution is static and configurable, and wherein adjusting comprises dynamically extending existing interval boundaries of the static number of intervals.

5. The method as in claim 1, wherein selecting comprises:

iteratively comparing distributions of two paths from the plurality of paths until a final selected path, wherein comparing comprises;

in response to a poorest hop metric interval being different between the distributions, selecting whichever path of the two paths that has a least-poor poorest hop metric interval;

in response to the poorest hop metric interval of the distributions being equal, selecting whichever path of the two paths that has a lowest number of hops within the poorest hop metric interval; and

in response to the number of hops within the equal poorest hop metric intervals being the same, comparing the two paths at a next-poorest hop metric interval.

6. The method as in claim 1, wherein selecting comprises:

selecting the path based on a plurality of different hop metric distributions.

7. The method as in claim 1, wherein selecting comprises:

utilizing the hop metric distribution as an indication of path total hop count; and

selecting the path based on the path total hop count in addition to the hop metric distribution.

8. The method as in claim 1, wherein the intervals of the hop metric distribution and their bounds are configured to be the same between the plurality of paths.

9. The method as in claim 1, further comprising:

determining the hop metric values of the hops along the particular paths according to a reactive routing protocol.

10. The method as in claim 1, further comprising:

determining the hop metric values of the hops along the particular paths according to a proactive distance vector routing protocol.

11. The method as in claim 1, further comprising:

determining the hop metric values of the hops along the particular paths according to a proactive link-state routing protocol.

12. The method as in claim 1, wherein the hop metric of the hop metric distribution is selected from a group consisting of:

link margin;

received signal strength indicator (RSSI);

link signal-to-noise ratio (SNR);

link expected transmission count (ETX);

link cost;

link bandwidth;

link packet loss;

node energy level;

node energy source type;

a node memory constraint; and

a node processing constraint.

13. An apparatus, comprising:

one or more network interfaces to communicate in a computer network;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

determine, for each particular path of a plurality of paths in a computer network, a hop metric distribution that indicates, for each interval of a plurality of intervals in the hop metric distribution, a number of hops along the particular path that have a hop metric value within each corresponding interval of a plurality of intervals provided in the hop metric distribution, wherein each particular path includes a plurality of hops and the hop metric distribution associates each of the plurality of hops with one of the plurality of intervals, wherein the hop metric distribution is adaptive;

select a path from the plurality of paths that minimizes the number of hops associated with an interval within the plurality of intervals that has a poor hop metric value along the selected path based on a number of hops in each interval of the hop metric distribution; and

forward traffic on the selected path.

14. The apparatus as in claim 13, wherein the process when executed is further operable to:

add a particular hop to the distribution by;

in response to a corresponding hop metric value of the particular hop being within an existing interval, incrementing the number of hops within that corresponding interval; and

in response to the corresponding hop metric value of the hop not being within an existing interval, adjusting the intervals of the hop metric distribution to include the corresponding hop metric value of the particular hop.

15. The apparatus as in claim 13, wherein the process when executed to select is further operable to:

iteratively compare distributions of two paths from the plurality of paths until a final selected path, the comparison comprising;

in response to a poorest hop metric interval being different between the distributions, selection of whichever path of the two paths that has a least-poor poorest hop metric interval;

in response to the poorest hop metric interval of the distributions being equal, selection of whichever path of the two paths that has a lowest number of hops within the poorest hop metric interval; and

in response to the number of hops within the equal poorest hop metric intervals being the same, comparison of the two paths at a next-poorest hop metric interval.

16. The apparatus as in claim 13, wherein the process when executed to select is further operable to:

select the path based on a plurality of different hop metric distributions.

17. The apparatus as in claim 13, wherein the process when executed to select is further operable to:

utilize the hop metric distribution as an indication of path total hop count; and

select the path based on the path total hop count in addition to the hop metric distribution.

18. The apparatus as in claim 13, wherein the intervals of the hop metric distribution and their bounds are configured to be the same between the plurality of paths.

19. The apparatus as in claim 13, wherein the process when executed is further operable to:

determine the hop metric values of the hops along the particular paths according to a routing protocol selected from a group consisting of;

a reactive routing protocol;

a proactive distance vector routing protocol; and

a proactive link-state routing protocol.

20. A tangible, non-transitory, computer-readable media having software encoded thereon, the software when executed by a processor operable to:

determine, for each particular path of a plurality of paths in a computer network, a hop metric distribution that indicates, for each interval of a plurality of intervals in the hop metric distribution, a number of hops along the particular path that have a hop metric value within each corresponding interval of a plurality of intervals provided in the hop metric distribution, wherein each particular path includes a plurality of hops and the hop metric distribution associates each of the plurality of hops with one of the plurality of intervals, wherein the hop metric distribution is adaptive;

select a path from the plurality of paths that minimizes the number of hops associated with an interval within the plurality of intervals that has a poor hop metric value along the selected path based on a number of hops in each interval of the hop metric distribution; and

forward traffic on the selected path.