Negotiated Parent Joining in Directed Acyclic Graphs (DAGS)

• US 20120117213A1
• Filed: 11/09/2010
• Published: 05/10/2012
• Est. Priority Date: 11/09/2010
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Shaffer, Shmuel, Vasseur, Jean-Philippe, Shetty, Sandeep Jay
• Granted Patent: US 8,447,849 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: H04L 47/726 Reserving resources in multiple paths to be used simultaneously by balancing the load H04L47/125

Abstract

In one embodiment, a node may request to join a parent node in a directed acyclic graph (DAG) in a computer network, and may notify the parent node of a load associated with the request, and whether the node has any other parent node options. The response received from the parent node may be either an acceptance or a denial (based on the load and other parent node options), where in the case of an acceptance, the node may join the parent node in the DAG. Alternatively, in response to a denial, in one embodiment, the node may perform load shedding to become acceptable to the parent node. In another embodiment, a node receiving a join request from a child node may determine an impact associated with allowing the child node (and its load) to join the receiving node in the DAG prior to returning an acceptance or denial, accordingly.

Claims

1. A method, comprising:

requesting, by a particular node, to join a parent node in a directed acyclic graph (DAG) in a computer network;

notifying the parent node of a load associated with the request;

notifying the parent node as to whether the particular node has any other parent node options;

receiving a response to the request from the parent node, the response being one of either an acceptance or a denial; and

in response to a response indicating an acceptance, joining the parent node in the DAG.

2. The method as in claim 1, wherein the denial comprises a counter request to shed load, the method further comprising:

propagating a shed load request to one or more child nodes of the particular node, the shed load request requesting that the one or more child nodes attempt to join any other parent node option, and if unable to, then to attempt to shed load; and

in response to shedding load according to the counter request, re-requesting to join the parent node.

3. The method as in claim 1, wherein load is selected from at least one attribute selected from a group consisting of:

a number of child nodes;

an amount of traffic;

a frequency of traffic; and

an amount of planned traffic.

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

in response to notifying the parent node of at least one other parent node option, notifying the parent node of a quality associated with the at least one other parent node option.

5. The method as in claim 1, wherein the particular node has already joined the parent node in the DAG, and wherein the request to join the parent node is in response to a load increase due to a join request received at the particular node.

6. An apparatus, comprising:

one or more network interfaces;

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;

request to join a parent node in a directed acyclic graph (DAG) in a computer network;

notify the parent node of a load associated with the request;

notify the parent node as to whether the apparatus has any other parent node options;

receive a response to the request from the parent node, the response being one of either an acceptance or a denial; and

join the parent node in the DAG in response to an acceptance.

7. The apparatus as in claim 6, wherein the denial comprises a counter request to shed load, the process when executed further operable to:

propagate a shed load request to one or more child nodes of the apparatus, the shed load request requesting that the one or more child nodes attempt to join any other parent node option, and if unable to, then to attempt to shed load; and

in response to shedding load according to the counter request, re-request to join the parent node.

8. The apparatus as in claim 6, wherein load is selected from at least one attribute selected from a group consisting of:

a number of child nodes;

an amount of traffic;

a frequency of traffic; and

an amount of planned traffic.

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

in response to notifying the parent node of at least one other parent node option, notify the parent node of a quality associated with the at least one other parent node option.

11. A method, comprising:

receiving, by a particular node in a directed acyclic graph (DAG) in a computer network, a join request from a child node;

receiving, from the child node, notification of a load associated with the request and whether the child node has any other parent node options;

determining an impact associated with allowing the child node to join the particular node in the DAG based on the load;

transmitting an acceptance response to the request in response to the determined impact being below a threshold level; and

transmitting a denial response to the request in response to the determined impact being above the threshold level.

10. The apparatus as in claim 16, wherein the apparatus has already joined the parent node in the DAG, and wherein the request to join the parent node is in response to a load increase due to a join request received at the particular node.

12. The method as in claim 11, wherein the denial response comprises a counter request requesting that the child node attempt to join any other parent node option, and if unable to, then to attempt to shed load.

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

determining the threshold level dynamically in response to network statistics.

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

prior to transmitting an acceptance response, transmitting a second join request to a parent node of the particular node in the DAG, the second join request requesting a load increase based on the load of the received join request at the particular node.

15. The method as in claim 11, further comprising, prior to transmitting a denial response in response to the child node having no other parent node options:

propagating a shed load request to one or more child nodes of the particular node, the shed load request requesting that the one or more child nodes attempt to join any other parent node option, and if unable to, then to attempt to shed load; and

in response to shedding load such that the addition of the join request load results in an impact below the threshold, transmitting an acceptance response to the child node.

16. The method as in claim 11, wherein load is selected from at least one attribute selected from a group consisting of:

a number of child nodes;

an amount of traffic;

a frequency of traffic; and

an amount of planned traffic.

17. An apparatus, comprising:

one or more network interfaces configured to communicate in a directed acyclic graph (DAG) in 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 a join request from a child node;

receive, from the child node, notification of a load associated with the request and whether the child node has any other parent node options;

determine an impact associated with allowing the child node to join the apparatus in the DAG based on the load;

transmit an acceptance response to the request in response to the determined impact being below a threshold level; and

transmit a denial response to the request in response to the determined impact being above the threshold level.

18. The apparatus as in claim 17, wherein the denial response comprises a counter request requesting that the child node attempt to join any other parent node option, and if unable to, then to attempt to shed load.

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

determine the threshold level dynamically in response to network statistics.

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

prior to transmitting an acceptance response, transmit a second join request to a parent node of the apparatus in the DAG, the second join request requesting a load increase based on the load of the received join request at the apparatus.

21. The apparatus as in claim 17, wherein the process when executed is further operable to, prior to transmission of a denial response in response to the child node having no other parent node options:

propagate a shed load request to one or more child nodes of the apparatus, the shed load request requesting that the one or more child nodes attempt to join any other parent node option, and if unable to, then to attempt to shed load; and

in response to shedding load such that the addition of the join request load results in an impact below the threshold, transmit an acceptance response to the child node.

22. The apparatus as in claim 17, wherein load is selected from at least one attribute selected from a group consisting of:

a number of child nodes;

an amount of traffic;

a frequency of traffic; and

an amount of planned traffic.