COMPUTING PATH INFORMATION TO A DESTINATION NODE IN A DATA COMMUNICATION NETWORK

• US 20090067330A1
• Filed: 09/06/2007
• Published: 03/12/2009
• Est. Priority Date: 09/06/2007
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Shand, Ian Michael Charles, Bryant, Stewart Frederick
• Granted Patent: US 7,965,642 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

Approaches for computing path information to a destination node in a data communications network are described. A data communications network comprises as components nodes and links therebetween and comprising a core subdomain of components and a plurality of non-core subdomains of components and having a common identifier for each non-core subdomain. An apparatus comprises first logic which when executed is operable to receive reachability information for a destination node and an associated identifier; and second logic which when executed is operable to perform a computation of path information for a path in the network to a destination node dependent on a particular identifier of a subdomain associated with the destination node, and to forward data for the destination over the path according to the path information.

Claims

1. An apparatus, comprising:

first logic which when executed is operable to receive reachability information for a destination node and an associated identifier;

second logic which when executed is operable to perform a computation of path information for a path in the network to a destination node dependent on a particular identifier of a subdomain associated with the destination node, and to forward data for the destination over the path according to the path information;

wherein the network comprises nodes and links therebetween as components and comprises a core subdomain of components and a plurality of non-core subdomains of components and wherein each non-core subdomain comprises a common identifier.

2. An apparatus as claimed in claim 1, further comprising logic which when executed is operable to perform the path computation dependent on a number of non-core subdomain identifiers associated with components on the path to the destination.

3. An apparatus as claimed in claim 2, further comprising logic which when executed is operable to suppress a path to a destination node in a non-core subdomain.

4. An apparatus as claimed in claim 3, further comprising logic which when executed is operable to suppress a path if the number of non-core subdomain identifiers exceeds a suppression threshold.

5. An apparatus as claimed in claim 4, further comprising logic which when executed is operable to identify a second path to the destination node as an alternative to the suppressed path.

6. An apparatus as claimed in claim 2, further comprising logic which when executed is operable to install a path to a destination node in a core subdomain if the number of identifiers exceeds a suppression threshold.

7. An apparatus as claimed in claim 2, further comprising logic which when executed is operable to exclude a subdomain identifier of the apparatus from the number of subdomain identifiers associated with the nodes from the path when the apparatus comprises a non-core subdomain node.

8. An apparatus as claimed in claim 2, further comprising logic which when executed is operable to determine whether the path has an equal cost path split and to include identifiers on each path in the number of identifiers.

9. An apparatus as claimed in claim 2 further comprising logic which when executed is operable to identify the number of subdomain identifiers by performing a shortest path first computation.

10. An apparatus as claimed in claim 9 in which, if the destination node comprises a core subdomain node then it is added during a further shortest path first computation.

11. An apparatus as claimed in claim 1 wherein each non-core subdomain comprises any one of a respective distinctive identifier, a common identifier, or a common identifier comprising an identifier bit.

12. An apparatus as claimed in claim 1 wherein the subdomain identifier is associated with any one of the destination node or an adjacent link over which the destination node is reached.

13. An apparatus as claimed in claim 1, further comprising logic which when executed is operable to compute the path information using any one of a link state protocol, border gateway protocol, or routing vector protocol.

14. An apparatus, comprising:

means for receiving reachability information for a destination node and an associated identifier;

means for performing a computation of path information for a path in the network to a destination node dependent on a particular identifier of a subdomain associated with the destination node;

means for forwarding data for the destination over the path according to the path information;

wherein the network comprises nodes and links therebetween as components and comprises a core subdomain of components and a plurality of non-core subdomains of components and wherein each non-core subdomain comprises a common identifier.

15. An apparatus as claimed in claim 14, further comprising means for performing the path computation dependent on a number of non-core subdomain identifiers associated with components on the path to the destination.

16. An apparatus as claimed in claim 15, further comprising means for suppressing a path to a destination node in a non-core subdomain.

17. An apparatus as claimed in claim 16, further comprising means for suppressing a path if the number of non-core subdomain identifiers exceeds a suppression threshold.

18. An apparatus as claimed in claim 17, further comprising means for identifying a second path to the destination node as an alternative to the suppressed path.

19. A method, comprising:

receiving reachability information for a destination node and an associated identifier;

performing a path information computation for a destination node dependent on the associated subdomain identifier;

forwarding data for the destination over the path according to the path information;

wherein the network comprises nodes and links therebetween as components and comprises a core subdomain of components and a plurality of non-core subdomains of components and wherein each non-core subdomain comprises a common identifier.

20. A computer readable medium comprising one or more sequences of instructions which, when executed by one or more processors cause the one or more processors to perform:

receiving reachability information for a destination node and an associated identifier;

performing a path information computation for a destination node dependent on the associated subdomain identifier;

forwarding data for the destination over the path according to the path information;

wherein the network comprises nodes and links therebetween as components and comprises a core subdomain of components and a plurality of non-core subdomains of components and wherein each non-core subdomain comprises a common identifier.