Alternate down paths for directed acyclic graph (DAG) routing

• US 8,817,665 B2
• Filed: 01/18/2013
• Issued: 08/26/2014
• 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, Wetterwald, Patrick, Vasseur, Jean-Philippe
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): LEE, ANDREW CHUNG CHEUNG
• Application Number:
  US13/745,321
• Publication Number:
  US 20130128773A1
• Time in Patent Office: 585 Days
• Field of Search: 370/225, 370/238, 370/252, 370/254, 370/255, 370400-410
• US Class Current: 370/254
• 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 that utilizes a directed acyclic graph (DAG) to route packets, may select a parent node P that is a parent to the node N in the DAG. The node N may determine a grandparent node GP within the computer network that is a parent of the parent node P in the DAG. The node N may select an alternate parent node P′ within the computer network that has connectivity to the grandparent node GP and the node N. A sibling connection may be established within the computer network between the parent node P and the alternate parent node P′. The sibling connection may provide a path for reaching prefixes reachable via the node N.

Claims

1. A method, comprising:

selecting, via a processor, for a node N within a computer network that utilizes a directed acyclic graph (DAG) to route packets, a parent node P that is a parent to node N in the DAG;

determining, via said processor, a grandparent node GP within the computer network that is a parent of the parent node P in the DAG;

selecting, via said processor, an alternate parent node P′

within the computer network that has connectivity to the grandparent node GP and the node N; and

establishing, via said processor, a sibling connection within the computer network between the parent node P and the alternate parent node P′

, wherein the sibling connection provides a path for reaching prefixes reachable via the node N.

2. The method of claim 1, further comprising:

informing both the parent node P and the alternate parent node P′

about the prefixes reachable via the node N.

3. The method of claim 1, further comprising:

determining a child node C within the computer network that is a child of the node N in the DAG; and

informing, by the node N, both the parent node P and the alternate parent node P′

about the prefixes reachable via the child node C.

4. The method of claim 3, further comprising:

selecting an alternate node N′

within the computer network that has connectivity to the parent node P, the alternate parent node P′ and

the node N, the alternate node N′

providing a path for reaching prefixes reachable via the child node C.

5. The method of claim 4, further comprising:

establishing an additional sibling connection within the computer network between node N and alternate node N′

.

6. The method of claim 1, further comprising:

informing the grandparent node GP about the existence of the alternate parent node P′

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

7. The method of claim 1, further comprising:

storing prefixes reachable via the node N at the parent node P; and

informing, by the parent node P, the grandparent node GP about the prefixes reachable via the node N.

8. The method of claim 1, further comprising:

storing prefixes reachable via the node N at the alternate parent node P′

, without the alternate parent node P′

informing the grandparent node GP about the prefixes reachable via the node N.

9. The method of claim 1, wherein the selecting selects the alternate parent node P′

at least partially based on presence of connectivity to the parent node P.

10. The method of claim 1, further comprising:

establishing a primary connection within the computer network between the grandparent node GP and the parent node P; and

establishing an alternate connection within the computer network between the grandparent node GP and the alternate parent node P′

.

11. The method of claim 10, further comprising:

determining an alternate grandparent node GP′

within the computer network that has connectivity to the alternate parent node P′

;

establishing a primary connection within the computer network between the alternate grandparent node GP′ and

the parent node P; and

establishing an alternate connection within the computer network between the alternate grandparent node GP′ and

the parent node P.

12. The method of claim 10, further comprising:

determining an alternate grandparent node GP′

within the computer network that has connectivity to the alternate parent node P′

; and

establishing an secondary path within the computer network that utilizes a secondary connection between the alternate grandparent node GP′ and

the alternate parent node P′

.

13. A node comprising:

one or more network interfaces configured to communicate with other nodes of a computer network that utilizes a directed acyclic graph (DAG) to route packets;

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

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

select a parent node P within the computer network that is a parent of the node in the DAG;

select an alternate parent node P′

within the computer network;

determine an alternate node N′

within the computer network that has connectivity to the parent node P, the alternate parent node P′ and

a child node C within the computer network, the child node C being a child of the node in the DAG;

is establish a sibling connection between the node and the alternate node N′

, the sibling connection providing a path for reaching prefixes reachable via the child node C.

14. The node of claim 13, wherein the routing process when executed is further operable to:

inform both the parent node P and the alternate parent node P′

about prefixes reachable via the node.

15. The node of claim 13, wherein the routing process when executed is further operable to:

inform both the parent node P and the alternate parent node P′

about the prefixes reachable via the child node C.

16. The node of claim 13, wherein the routing process when executed is further operable to:

determine a grandparent node GP within the computer network that is a parent of the parent node P in the DAG;

select the alternate parent node P′

to have connectivity to the grandparent node GP.

17. The node of claim 16, wherein the routing process when executed is further operable to:

inform the grandparent node GP about the existence of the alternate parent node P′

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

18. The node of claim 16, wherein the routing process when executed is further operable to:

select the alternate parent node P′

at least partially based on presence of connectivity to the parent node P.

19. A non-transitory computer readable medium having software encoded thereon, the software when executed operable to:

select, for a node N within a computer network that utilizes a directed acyclic graph (DAG) to route packets, a parent node P that is a parent to the node N in the DAG;

determine a grandparent node GP within the computer network that is a parent of the parent node P in the DAG;

select an alternate parent node P′

within the computer network that has connectivity to the grandparent node GP and the node N; and

establishing a sibling connection between the parent node P and the alternate parent node P′

within the computer network.

20. The non-transitory computer readable medium of claim 19, wherein the software when executed is further operable to:

inform both the parent node P and the alternate parent node P′

about prefixes reachable via the node N.