Granted Patent B2

US 9,215,164 · App. 14/075,294 · Granted Dec 15, 2015

Abstract

Claims (50)

1. A method comprising:

receiving a first metric for a plurality of links in a network, the first metric being a routing metric used to determine routing in the network;

determining a routing path including a subset of the links based on the first metric, the routing path having an initial cost based on the first metric;

receiving second metric information including a second metric that is different from the first metric;

calculating a corrected cost for the routing path based on the second metric information, wherein at least one of the metrics is based on an element of an external gateway protocol autonomous system;

receiving a third metric, the third metric being a routing metric used to determine routing for a second plurality of links in the network; and

updating the routing path based on the third metric to include the second plurality of links,

wherein calculating a corrected cost for the routing path based on the second metric comprises calculating a corrected cost for the routing path based on the second metric and the third metric.

2. The method of claim 1 , wherein the second metric information includes a routing metric used to determine routing for a second plurality of links in the network.

3. The method of claim 2 , wherein the first metric is an interior gateway protocol (IGP) routing cost and the second metric is external gateway protocol (EGP) autonomous system (AS) path length.

4. The method of claim 1 , wherein the step of calculating a corrected cost for the routing path based on the second metric comprises determining a total value of the second metric information associated with the subset of the links.

5. The method of claim 1 , wherein the second metric is a recessive metric.

6. The method of claim 1 , further comprising:

determining that the second metric is unavailable for a missing link of the first plurality of links; and

requesting second metric data for the missing link.

7. The method of claim 1 , further comprising:

determining that a shortcut second metric is available for two non-adjacent vertices in the routing path; and

substituting the shortcut second metric for a plurality of individual second metrics associated with links between the two non-adjacent vertices.

8. The method of claim 1 , wherein the first metric and the second metric information are received from different sources.

9. The method of claim 1 , further comprising:

receiving third metric information including a point-to-point metric; and

determining that the third metric information corresponds to a portion of the routing path,

wherein calculating a corrected cost for the routing path based on the second metric comprises calculating a corrected cost for the routing path based on the second metric and the third metric.

10. The method of claim 1 , further comprising:

generating a network topology including a corrected cost for a plurality of routing paths; and

exposing the network topology to an external application.

11. A non-transitory machine-readable storage medium encoded with instructions executable by a processor, the non-transitory machine-readable storage medium comprising instructions for:

receiving a first metric for a first plurality of links in a network, the first metric being a routing metric used to determine routing in the network;

determining a routing path including a first subset of the links based on the first metric, the routing path having an initial cost based on the first metric;

receiving second metric information including a second metric that is different from the first metric;

calculating a corrected cost for the routing path based on the second metric information, wherein at least one of the metrics is based on an element of an external gateway protocol autonomous system;

receiving a third metric, the third metric being a routing metric used to determine routing for a second plurality of links in the network; and

updating the routing path based on the third metric to include the second plurality of links,

wherein the instructions for calculating a corrected cost for the routing path based on the second metric comprises calculating a corrected cost for the routing path based on the second metric and the third metric.

12. The non-transitory machine-readable storage medium of claim 11 , wherein the first metric is an interior gateway protocol (IGP) routing cost for the first plurality of links and the second metric information includes an external gateway protocol (EGP) autonomous system (AS) path length for a second plurality of links, wherein the instructions for calculating a corrected cost for the routing path based on the second metric information comprise calculating a total cost for the routing path based on a weighted formula including the IGP routing cost for the first subset of links and the AS path length for a link of the second plurality of links.

13. The non-transitory machine-readable storage medium of claim 11 , wherein instructions for calculating a corrected cost for the routing path based on the second metric comprise instructions for determining a total value of the second metric information associated with the subset of the links.

14. The non-transitory machine-readable storage medium of claim 11 , wherein the second metric is a recessive metric.

15. The non-transitory machine-readable storage medium of claim 11 , further comprising instructions for:

determining that the second metric is unavailable for a missing link of the first plurality of links; and

requesting second metric data for the missing link.

16. The non-transitory machine-readable storage medium of claim 11 , further comprising instructions for:

determining that a shortcut second metric is available for two non-adjacent vertices in the routing path; and

substituting the shortcut second metric for a plurality of individual second metrics associated with links between the two non-adjacent vertices.

17. The non-transitory machine-readable storage medium of claim 11 , further comprising instructions for:

receiving third metric information corresponding to an application layer metric; and

determining that the third metric information corresponds to a portion of the routing path,

wherein the instructions for calculating a corrected cost for the routing path based on the second metric comprise instructions for calculating a corrected cost for the routing path based on the second metric and the third metric.

18. The non-transitory machine-readable storage medium of claim 11 , further comprising instructions for:

generating a network topology including a corrected cost for a plurality of routing paths; and

exposing the network topology to an external application.

Assignments (9)