ALTERNATE DOWN PATHS FOR DIRECTED ACYCLIC GRAPH (DAG) ROUTING

• US 20110228788A1
• Filed: 03/19/2010
• Published: 09/22/2011
• Est. Priority Date: 03/19/2010
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Thubert, Pascal, Vasseur, Jean-Philippe, Wetterwald, Patrick
• Granted Patent: US 8,363,662 B2
• Time in Patent Office: Days
• US Class Current: 370/400
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/488 using root node determination
• CPC Class Codes: Y04S 40/00 Systems for electrical power generation, transmission, distribution or end-user application management characterised by the use of communication or information technologies, or communication or information technology specific aspects supporting them

Abstract

In one embodiment, a node “N” within a computer network utilizing directed acyclic graph (DAG) routing selects a parent node “P” within the DAG, and, where P is not a DAG root, may determine a grandparent node “GP” as a parent node to the parent node P. The node N may then also select an alternate parent node “P′” that has connectivity to GP and N. N may then inform P and P′ about prefixes reachable via N, and also about P′ as an alternate parent node to P to reach the prefixes reachable via N. Also, in one embodiment, P may be configured to inform GP about the prefixes reachable via N and also about P′ as an alternate parent node to P to reach the prefixes reachable via N, and P′ may be configured to store the prefixes reachable via N without informing other nodes about those prefixes.

Claims

1. A method, comprising:

selecting, by a node N within a computer network utilizing directed acyclic graph (DAG) routing, a parent node P within the DAG;

in response to P not being a root of the DAG, determining, by N, a grandparent node GP as a parent node to the parent node P;

selecting, by N, an alternate parent node P′

that has connectivity to GP and N; and

informing, from N, P and P′

about prefixes reachable via N and also about P′

as an alternate parent node to P to reach the prefixes reachable via N.

2. The method as in claim 1, wherein P is configured to inform GP about the prefixes reachable via N and also about P′

as an alternate parent node to P to reach the prefixes reachable via N, and wherein P′

is configured to store the prefixes reachable via N without informing other nodes about the prefixes reachable via N.

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

receiving, by N, information about one or more of the prefixes from a child node C of N, the information having an indication of an alternate parent N′

of C that has connectivity to P and C; and

informing, from N, P and P′

about prefixes reachable via C and also about N′

as an alternate parent node to N to reach the prefixes reachable via C.

4. The method as in claim 3, wherein N has connectivity to N′

, the method further comprising;

establishing a sibling connection between N and N′

.

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

receiving, by N, information about one or more of the prefixes from a plurality of child nodes of N, the information having an indication of an alternate parent for each of the plurality of child nodes of N that has connectivity to P and the respective child node; and

informing, from N, P and P′

about prefixes reachable via each of the plurality of child nodes and also about each respective alternate parent as an alternate parent node to N to reach the prefixes reachable via a corresponding child node.

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

receiving, by N, information about one or more of the prefixes from a child node C of N, the information having an indication of that N is an alternate parent of C that has connectivity to a grandparent of C and to C; and

storing, by N, prefixes reachable via C.

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

receiving, by N, information about one or more of the prefixes from a child node C of N, the information having an indication that the prefixes are reachable via a grandchild node of N through C and an indication of an alternate parent C′

of GC that has connectivity to N and GC; and

storing, by N, prefixes reachable via GC using a path through C with an alternate path through C′

.

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

advertising, into the DAG from N, a list of neighbors visible to N.

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

advertising, into the DAG from N, that P is a parent node of N.

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

selecting, by N, the alternate parent node P′

that has connectivity to GP and N and P.

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

selecting P and P′

based on an objective function (OF) of the DAG.

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

utilizing DAG routing according to a Routing Protocol for Low Power and Lossy Networks (RPL).

13. An apparatus, comprising:

one or more network interfaces adapted to communicate with nodes of a computer network configured to utilize directed acyclic graph (DAG) routing;

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

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

select a parent node P within the DAG;

determine a grandparent node GP as a parent node to the parent node P in response to P not being a root of the DAG;

select an alternate parent node P′

that has connectivity to GP and the apparatus; and

inform P and P′

about prefixes reachable via the apparatus and also about P′

as an alternate parent node to P to reach the prefixes reachable via the apparatus.

14. The apparatus as in claim 13, wherein P is configured to inform GP about the prefixes reachable via the apparatus and also about P′

as an alternate parent node to P to reach the prefixes reachable via the apparatus, and wherein P′

is configured to store the prefixes reachable via the apparatus without informing other nodes about the prefixes reachable via the apparatus

receive information about one or more of the prefixes from a child node C of the apparatus, the information having an indication of an alternate parent N′

of C that has connectivity to P and C; and

inform P and P′

about prefixes reachable via C and also about N′

as an alternate parent node to the apparatus to reach the prefixes reachable via C.

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

receive information about one or more of the prefixes from a child node C of the apparatus, the information having an indication of an alternate parent N′

of C that has connectivity to P and C; and

inform P and P′

about prefixes reachable via C and also about N′

as an alternate parent node to the apparatus to reach the prefixes reachable via C.

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

receive information about one or more of the prefixes from a plurality of child nodes of the apparatus, the information having an indication of an alternate parent for each of the plurality of child nodes of the apparatus that has connectivity to P and the respective child node; and

inform P and P′

about prefixes reachable via each of the plurality of child nodes and also about each respective alternate parent as an alternate parent node to the apparatus to reach the prefixes reachable via a corresponding child node.

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

receive information about one or more of the prefixes from a child node C of the apparatus, the information having an indication of that the apparatus is an alternate parent of C that has connectivity to a grandparent of C and to C; and

store prefixes reachable via C.

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

receive information about one or more of the prefixes from a child node C of the apparatus, the information having an indication that the prefixes are reachable via a grandchild node of the apparatus through C and an indication of an alternate parent C′

of GC that has connectivity to the apparatus and GC; and

store prefixes reachable via GC using a path through C with an alternate path through C′

.

20. The tangible computer-readable media as in claim 17, wherein P is configured to inform GP about the prefixes reachable via N and also about P′

as an alternate parent node to P to reach the prefixes reachable via N, and wherein P′

is configured to store the prefixes reachable via N without informing other nodes about the prefixes reachable via N.

19. A tangible computer-readable media having software encoded thereon, the software, when executed on a node N utilizing directed acyclic graph (DAG) routing, operable to:

select a parent node P within the DAG;

determine a grandparent node GP as a parent node to the parent node P in response to P not being a root of the DAG;

select an alternate parent node P′

that has connectivity to GP and N; and

inform P and P′

about prefixes reachable via N and also about P′

as an alternate parent node to P to reach the prefixes reachable via N.

21. The tangible computer-readable media as in claim 19, wherein the software when executed is further operable to:

receive information about one or more of the prefixes from a child node C of N, the information having an indication of an alternate parent N′

of C that has connectivity to P and C; and

inform P and P′

about prefixes reachable via C and also about N′

as an alternate parent node to N to reach the prefixes reachable via C.

22. The tangible computer-readable media as in claim 19, wherein the software when executed is further operable to:

receive information about one or more of the prefixes from a child node C of N, the information having an indication of that N is an alternate parent of C that has connectivity to a grandparent of C and to C; and

store prefixes reachable via C.

23. The tangible computer-readable media as in claim 19, wherein the software when executed is further operable to:

receive information about one or more of the prefixes from a child node C of N, the information having an indication that the prefixes are reachable via a grandchild node of N through C and an indication of an alternate parent C′

of GC that has connectivity to N and GC; and

store prefixes reachable via GC using a path through C with an alternate path through C′

.