Forwarding packets to a directed acyclic graph destination using link selection based on received link metrics

• US 7,924,722 B2
• Filed: 03/31/2010
• Issued: 04/12/2011
• Est. Priority Date: 10/24/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Le Faucheur, Francois Laurent, Thubert, Pascal, Levy-Abegnoli, Eric M.
• Primary Examiner(s): Yao; Kwang B
• Assistant Examiner(s): Tran; Tung Q
• Application Number:
  US12/751,841
• Publication Number:
  US 20100188979A1
• Time in Patent Office: 377 Days
• Field of Search: None
• US Class Current: 370/235
• CPC Class Codes: H04L 43/022 by sampling
• CPC Class Codes: H04L 43/08 Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update

Abstract

Each network node having at least one destination-oriented link toward a directed acyclic graph (DAG) destination can receive a corresponding set of path performance metrics via the destination-oriented link. The set of path performance metrics, initiated by the DAG destination outputting initial link metrics on each of its source-connecting links, identifies aggregate link metrics for a corresponding path to the DAG destination via the corresponding destination-oriented link. The network node outputs a corresponding updated set of path performance metrics on each of its source-connecting links based on the received set of path performance metrics and the corresponding link metric for the corresponding source-connecting link. Hence, each network node in the DAG can assess the performance of each connected path to the DAG destination, and forward a data packet via a selected destination-oriented link based on the corresponding path performance metrics and forwarding policies for the forwarded data packet.

Claims

1. A method in a network node, the method including:

receiving, via a first link of the network node, a first set of path performance metrics that identifies aggregate metrics for a corresponding path to a prescribed destination via the first link, the path performance metrics based on at least initial link metrics having been output by the prescribed destination onto a corresponding source-connecting link of the prescribed destination, the initial link metrics describing performance of the corresponding source-connecting link of the prescribed destination;

selectively determining second metrics for at least a second source-connecting link providing reachability by the network node to the prescribed destination for at least one connected network node; and

outputting, onto the second source-connecting link, an updated set of path performance metrics based on the first set of path performance metrics and the second metrics, the updated set of path performance metrics identifying the aggregate metrics for the corresponding path to the prescribed destination via the second source-connecting link and the first link;

wherein the prescribed destination is identified by the network node as a directed acyclic graph (DAG) destination and the first link is selected by the network node as a destination-oriented link that is directed toward the DAG destination.

2. The method of claim 1, further comprising:

second receiving, via a second link of the network node, a second set of path performance metrics that identifies the aggregate metrics for a corresponding path to the prescribed destination via the second link; and

selecting one of the first or second links, based on a comparison between the first and second set of path performance metrics.

3. The method of claim 2, further comprising second outputting a corresponding second updated set of path performance metrics based on the second set of path performance metrics and the second metrics, the second updated set of path performance metrics identifying the aggregate metrics for the corresponding path to the prescribed destination via the network node.

4. The method of claim 3, wherein:

the aggregate metrics for each of the first and second set of path performance metrics are specified as a corresponding plurality of link metrics for each hop in the corresponding path between the prescribed destination and the network node.

5. The method of claim 1, wherein the initial link metrics include at least one of bandwidth utilization, signal to noise ratio, signal strength, selected link speed, or bandwidth reservation level.

6. A network node comprising:

a network interface configured for receiving, via a first link, a first set of path performance metrics that identifies aggregate metrics for a corresponding path to a prescribed destination via the first link, the path performance metrics based on at least initial link metrics having been output by the prescribed destination onto a corresponding source-connecting link of the prescribed destination, the initial link metrics describing performance of the corresponding source-connecting link of the prescribed destination; and

a resource configured for;

selectively determining second metrics for at least a second source-connecting link providing reachability by the network node to the prescribed destination for at least one connected network node, and

outputting, onto the second source-connecting link having been established by the network interface with the connected network node, an updated set of path performance metrics based on the first set of path performance metrics and the second metrics, the updated set of path performance metrics identifying the aggregate metrics for the corresponding path to the prescribed destination via the second source-connecting link and the first link;

wherein the prescribed destination is identified by the network node as a directed acyclic graph (DAG) destination and the first link is selected by the network node as a destination-oriented link that is directed toward the DAG destination.

7. The network node of claim 6, wherein:

the network interface is configured for receiving, via a second link of the network node, a second set of path performance metrics that identifies the aggregate metrics for a corresponding path to the prescribed destination via the second link;

the resource configured for selecting one of the first or second links, based on a comparison between the first and second set of path performance metrics.

8. The network node of claim 7, wherein the resource is configured for outputting a corresponding second updated set of path performance metrics based on the second set of path performance metrics and the second metrics identifying the aggregate metrics for the corresponding path to the prescribed destination via the network node.

9. The network node of claim 8, wherein:

the aggregate metrics for each of the first and second set of path performance metrics are specified as a corresponding plurality of link metrics for each hop in the corresponding path between the destination and the network node.

10. The network node of claim 6, wherein the initial link metrics include at least one of bandwidth utilization, signal to noise ratio, signal strength, selected link speed, or bandwidth reservation level.

11. A non-transitory computer readable medium having stored thereon sequences of computer executable instructions for a network node to establish communications toward a prescribed destination, the sequences of computer executable instructions including instructions for:

receiving, via a first link of the network node, a first set of path performance metrics that identifies aggregate metrics for a corresponding path to the prescribed destination via the first link, the path performance metrics based on at least initial link metrics having been output by the prescribed destination onto a corresponding source-connecting link of the prescribed destination, the initial link metrics describing performance of the corresponding source-connecting link of the prescribed destination;

selectively determining second metrics for at least a second source-connecting link providing reachability by the network node to the prescribed destination for at least one connected network node; and

outputting, onto the second source-connecting link, an updated set of path performance metrics based on the first set of path performance metrics and the second metrics, the updated set of path performance metrics identifying the aggregate metrics for the corresponding path to the prescribed destination via the second source-connecting link and the first link;

wherein the prescribed destination is identified by the network node as a directed acyclic graph (DAG) destination and the first link is selected by the network node as a destination-oriented link that is directed toward the DAG destination.

12. The medium of claim 11, further comprising instructions for:

second receiving, via a second link of the network node, a second set of path performance metrics that identifies the aggregate metrics for a corresponding path to the destination via the second link; and

selecting one of the first or second links, based on a comparison between the first and second set of path performance metrics.

13. The medium of claim 12, further comprising instructions for second outputting a corresponding second updated set of path performance metrics based on the second set of path performance metrics and the second metrics, the second updated set of path performance metrics identifying the aggregate metrics for the corresponding path to the prescribed destination via the network node.

14. The medium of claim 13, wherein:

the aggregate metrics for each of the first and second set of path performance metrics are specified as a corresponding plurality of link metrics for each hop in the corresponding path between the prescribed destination and the network node.

15. The medium of claim 11, wherein the link metrics include at least one of bandwidth utilization, signal to noise ratio, signal strength, selected link speed, or bandwidth reservation level.

16. An ad hoc network comprising:

a plurality of network nodes, one of the network nodes identifiable as a prescribed destination having one or more source-connecting links enabling the other network nodes to reach the prescribed destination via paths, each of the other network nodes having at least one first link for reaching the prescribed destination, at least one of the other network nodes having a plurality of second source-connecting links connecting the one other network node to respective other ones of the other network nodes, each of the other network nodes comprising;

a network interface configured for receiving, via the corresponding first link, a first set of path performance metrics that identifies aggregate metrics for a corresponding path to the prescribed destination via the corresponding first link, the path performance metrics based on at least initial link metrics having been output by the destination onto the corresponding source-connecting link of the prescribed destination, the initial link metrics describing performance of the corresponding source-connecting link of the prescribed destination; and

a resource configured for;

selectively determining second metrics for at least one of the second source-connecting links providing reachability by the corresponding other network node to the prescribed destination for at least one connected network node, and

outputting, onto the least one of the second source-connecting links having been established by the network interface with the connected network node, an updated set of path performance metrics based on the first set of path performance metrics and the second metrics, the updated set of path performance metrics identifying the aggregate metrics for the corresponding path to the prescribed destination via the corresponding second source-connecting link and the first destination-oriented link, wherein the prescribed destination is identified by the corresponding other network node as a directed acyclic graph (DAG) destination and the first link is selected by the corresponding other network node as a destination-oriented link that is directed toward the DAG destination.

17. The network of claim 16, wherein:

the network interface is configured for receiving, via a second link of the corresponding other network node, a second set of path performance metrics that identifies the aggregate metrics for a corresponding path to the prescribed destination via the second link;

the resource configured for selecting one of the first or second links, based on a comparison between the first and second set of path performance metrics.

18. The network of claim 17, wherein the resource is configured for outputting a corresponding second updated set of path performance metrics based on the second set of path performance metrics and the second metrics identifying the aggregate metrics for the corresponding path to the prescribed destination via the corresponding other network node.

19. The network of claim 18, wherein:

the aggregate metrics for each of the first and second set of path performance metrics are specified as a corresponding plurality of link metrics for each hop in the corresponding path between the DAG destination and the corresponding network node.

20. The network of claim 16, wherein the initial link metrics include at least one of bandwidth utilization, signal to noise ratio, signal strength, selected link speed, or bandwidth reservation level.