Mintree-based routing in highly constrained networks

• US 9,219,682 B2
• Filed: 11/05/2012
• Issued: 12/22/2015
• Est. Priority Date: 11/05/2012
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Dasgupta, Sukrit, Hui, Jonathan W.
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): Ajid, Abdeltif
• Application Number:
  US13/668,894
• Publication Number:
  US 20140126426A1
• Time in Patent Office: 1,142 Days
• Field of Search: 370/256
• US Class Current: 1/1
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/484 using multiple routing trees

Abstract

In one embodiment, a capable node in a computer network may host a path computation element, receive one or more neighborhood discovery messages including neighborhood information from a plurality of nodes in the computer network, and compute a minimum spanning tree (MinTree) for the computer network based on the neighborhood information. The MinTree may divide the plurality of nodes in the computer network into a first subset of routing nodes and a second subset of host nodes. The first subset of routing nodes may form one or more interconnected paths of routing nodes within the MinTree, and each host node within the second subset of host nodes may be located within one hop of at least one routing node. The capable node may then communicate a MinTree message to the plurality of nodes in the computer network to build the MinTree by enabling routing on each routing node.

Claims

1. A method, comprising:

hosting a path computation element (PCE) at a capable node in a computer network;

receiving, at the capable node, one or more neighborhood discovery (ND) messages including neighborhood information from a plurality of nodes in the computer network;

computing centrally in the computer network, with the PCE, a minimum spanning tree (MinTree) for the plurality of nodes in the computer network based on the neighborhood information, the MinTree dividing the plurality of nodes in the computer network into a first subset of routing nodes (R nodes) and a second subset of host nodes (H nodes), the first subset of the R nodes forming one or more interconnected paths of the R nodes within the MinTree, and each H node within the second subset of the H nodes located within one hop of at least one R node; and

communicating a MinTree message including MinTree information to the plurality of nodes in the computer network to build the MinTree, the Min Tree information providing information identifying which nodes of the plurality of nodes are R nodes and which nodes of the plurality of nodes are H nodes, the Min Tree information enabling routing on each R node in the first subset of the R nodes.

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

communicating a ranking message to the first subset of the R nodes in the MinTree, the ranking message assigning a rank to each of the R nodes in the one or more interconnected paths relative to the capable node.

3. The method as in claim 2, wherein the ranking message includes a rank counter that is incremented at each hop.

4. The method as in claim 1, wherein the MinTree information is encoded in a bloom filter.

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

building a network database based on the neighborhood information received in the one or more ND messages.

6. The method as in claim 1, wherein the neighborhood information comprises a list of neighbors, links, and metric data corresponding to each link.

7. The method as in claim 6, wherein computing further comprises:

removing all nodes from the neighborhood information with links in which the corresponding metric data is above or below a particular threshold value to create a MinTree dataset; and

performing a constrained shortest path first (CSPF) algorithm based on the MinTree dataset to solve for the MinTree.

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

computing one or more additional MinTrees; and

communicating one or more additional MinTree messages including the MinTree information about the one or more additional MinTrees to the plurality of nodes in the network to build the one or more additional MinTrees.

9. The method as in claim 8, wherein the one or more additional MinTrees are computed based on different criteria.

10. A method, comprising:

receiving, at a node in a computer network, a minimum spanning tree (MinTree) message from a capable node centrally located in the computer network, the MinTree message dividing a plurality of nodes in the computer network into a first subset of routing nodes (R nodes) and a second subset of host nodes (H nodes), the first subset of the R nodes forming one or more interconnected paths of the R nodes within a MinTree, and each H node within the second subset of the H nodes located within one hop of at least one R node;

self-identifying, based on the MinTree message, as either one of the R nodes or one of the H nodes;

in response to the node self-identifying as one of the R nodes, enabling routing functionality on the node; and

determining a relative rank of the node self-identified as one of the R nodes with respect to one or more of the R nodes in the one or more interconnected paths of the R nodes within the MinTree, wherein a higher rank indicates a further distance from a root node of the MinTree than a lower rank.

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

receiving, at the node, a message including a local multicast header from an H node located outside of the MinTree;

removing the local multicast header from the message;

determining whether the message is a duplicate of a previously received message; and

forwarding the message to a second R node in the one or more interconnected paths of the R nodes in the MinTree having the lower rank if the message is not the duplicate of the previously received message.

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

sending an acknowledgment message to the H node located outside of the MinTree.

13. The method as in claim 10, wherein the message is a packet encapsulated in an IPv6 packet including the local multicast header.

14. The method as in claim 10, wherein the message comprises a time to live (TTL) timer.

15. The method as in claim 14, wherein the TTL timer is set to 1.

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

locally multicasting, from the node self-identified as an H node, a message including a local multicast header for receipt by one of the R nodes in the MinTree.

17. An apparatus, comprising:

one or more network interfaces to communicate with 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;

host a path computation element (PCE) at a capable node in a computer network;

receive, at the capable node, one or more neighborhood discovery (ND) messages including neighborhood information from a plurality of nodes in the computer network;

compute centrally in the computer network, with the PCE, a minimum spanning tree (MinTree) for the plurality of nodes in the computer network based on the neighborhood information, the MinTree dividing the plurality of nodes in the computer network into a first subset of routing nodes (R nodes) and a second subset of host nodes (H nodes), the first subset of the R nodes forming one or more interconnected paths of the R nodes within the MinTree, and each H node within the second subset of H nodes located within one hop of at least one R node of the R nodes; and

communicate a MinTree message including MinTree information to the plurality of nodes in the computer network to build the MinTree, the Min Tree information providing information identifying which nodes of the plurality of nodes are R nodes and which nodes of the plurality of nodes are H nodes, the Min Tree information enabling routing on each R node in the first subset of the R nodes.

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

compute one or more additional MinTrees; and

communicate one or more additional MinTree messages including the MinTree information about the one or more additional MinTrees to the plurality of nodes in the network to build the one or more additional MinTrees.

19. An apparatus, comprising:

one or more network interfaces to communicate with 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;

receive, at a node in a computer network, a minimum spanning tree (MinTree) message from a capable node centrally located in the computer network, the MinTree message dividing a plurality of nodes in the computer network into a first subset of routing nodes (R nodes) and a second subset of host nodes (H nodes), the first subset of the R nodes forming one or more interconnected paths of the R nodes within a MinTree, and each H node within the second subset of the H nodes located within one hop of at least one R node;

self-identify, based on the MinTree message, as either one of the R nodes or one of the H nodes;

in response to self-identifying as one of the R nodes, enable routing functionality on the node; and

determine a relative rank of the node self-identified as one of the R nodes with respect to one or more of the R nodes in the one or more interconnected paths of the R nodes within the MinTree, wherein a higher rank indicates a further distance from a root node of the MinTree than a lower rank.

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

receive, at the node self-identified as one of the R nodes, a message including a local multicast header from an H node located outside of the MinTree;

remove the local multicast header from the message;

determine whether the message is a duplicate of a previously received message; and

forward the message to a second R node in the one or more interconnected paths of the R nodes in the MinTree having the lower rank if the message is not a duplicate of a previously received message.

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

locally multicast, from the node self-identified as one of the H nodes, a message including a local multicast header for receipt by one of the R nodes in the MinTree.