Selective topology routing for distributed data collection

• US 8,619,576 B2
• Filed: 07/12/2011
• Issued: 12/31/2013
• Est. Priority Date: 07/12/2011
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Hui, Jonathan W.
• Primary Examiner(s): Thier, Michael
• Assistant Examiner(s): Elliott, IV, Benjamin H
• Application Number:
  US13/180,998
• Publication Number:
  US 20130016612A1
• Time in Patent Office: 903 Days
• Field of Search: 370/235, 370/252
• US Class Current: 370/235
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/488 using root node determination
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion

Abstract

In one embodiment, a device, such as a network management server, determines a traffic matrix of a mesh network, where the traffic matrix indicates an amount of traffic per type of traffic transitioning between the mesh network and a global computer network via one or more current root devices. One or more optimized root devices may then be selected for corresponding directed acyclic graphs (DAGs) based on the amount of traffic and type of traffic. As such, a DAG formation request may be transmitted to the selected root devices, carrying a characteristic for a corresponding DAG to form by the respective selected root devices that indicates which one or more types of traffic correspond to the corresponding DAG.

Claims

1. A method, comprising:

determining a traffic matrix of a mesh network, the traffic matrix indicating an amount of traffic per type of traffic transitioning between the mesh network and a global computer network via one or more current root devices;

selecting one or more optimized root devices from a plurality of capable devices in the mesh network for corresponding directed acyclic graphs (DAGs) based on the amount of traffic and type of traffic; and

transmitting a DAG formation request to the selected one or more optimized root devices, the DAG formation request carrying a characteristic for a corresponding DAG to be formed by the respective selected optimized root devices that indicates which one or more types of traffic correspond to the corresponding DAG.

2. The method as in claim 1, wherein the traffic matrix further indicates the amount of traffic and type of traffic per time of day, and wherein selecting the one or more optimized root devices for corresponding DAGs is further based on the amount of traffic and type of traffic per time of day.

3. The method as in claim 2, wherein the characteristic for a particular corresponding DAG to form further indicates a time of day during which the particular corresponding DAG is active.

4. The method as in claim 1, wherein the type of traffic is selected from a group consisting of:

a particular class of service;

a particular application;

a particular priority of traffic;

a particular data type;

a particular head-end server; and

a particular size of traffic.

5. The method as in claim 1, wherein selecting comprises:

selecting a plurality of optimized root devices for corresponding DAGs, wherein the characteristics for the corresponding DAGs indicate at least one overlapping type of traffic between the corresponding DAGs.

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

adjusting the selected optimized root devices based on an updated traffic matrix.

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

utilizing hysteresis to limit a frequency of adjusting the selected one or more optimized root devices.

8. The method as in claim 1, wherein selecting the one or more optimized root devices for corresponding DAGs is in response to an event-driven trigger.

9. The method as in claim 8, wherein the event-driven trigger is in response to congestion in the mesh network.

10. An apparatus, comprising:

one or more network interfaces to communicate with nodes of a mesh network;

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

a memory configured to store the one or more processes executable by the processor, the one or more processes when executed operable to;

determine a traffic matrix of the mesh network, the traffic matrix indicating an amount of traffic per type of traffic transitioning between the mesh network and a global computer network via one or more current root devices;

select one or more optimized root devices from a plurality of capable devices in the mesh network for corresponding directed acyclic graphs (DAGs) based on the amount of traffic and type of traffic; and

transmit a DAG formation request to the selected one or more selected root devices, the DAG formation request carrying a characteristic for a corresponding DAG to be formed by the respective selected optimized root devices that indicates which one or more types of traffic correspond to the corresponding DAG.

11. The apparatus as in claim 10, wherein the traffic matrix further indicates the amount of traffic and type of traffic per time of day, and wherein selecting the one or more optimized root devices for corresponding DAGs is further based on the amount of traffic and type of traffic per time of day.

12. The apparatus as in claim 11, wherein the characteristic for a particular corresponding DAG to form further indicates a time of day during which the particular corresponding DAG is active.

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

adjust the selected optimized root devices based on an updated traffic matrix.

14. The apparatus as in claim 10, wherein selecting the one or more optimized root devices for corresponding DAGs is in response to an event-driven trigger.

15. A method, comprising:

receiving a directed acyclic graph (DAG) formation request at a selected root device of a mesh network, the DAG formation request carrying a characteristic for a corresponding DAG to be formed by the selected root device that indicates which one or more types of traffic correspond to the corresponding DAG;

initializing the corresponding DAG as requested in the DAG formation request; and

advertising the characteristic for the corresponding DAG to indicate, to nodes in the mesh network joining the corresponding DAG, which one or more types of traffic are served by the corresponding DAG.

16. The method as in claim 15, wherein the characteristic for the corresponding DAG further indicates a time of day during which the corresponding DAG is active.

17. A method, comprising:

receiving, at a node in a mesh network, a first directed acyclic graph (DAG) advertisement having a first characteristic for a corresponding first DAG to join with that indicates a first type of traffic that is served by the first DAG;

joining the first DAG;

receiving, at the node, a second DAG advertisement having a second characteristic for a corresponding second DAG to join with that indicates a second type of traffic that is served by the second DAG;

joining the second DAG;

transmitting, by the node, traffic of the first type on the first DAG; and

transmitting, by the node, traffic of the second type on the second DAG.

18. The method as in claim 17, wherein the characteristic for the second DAG further indicates a time of day during which the second DAG is active, the method further comprising:

transmitting, by the node, traffic of the second type on the first DAG in response to the second DAG being inactive.

19. The method as in claim 17, wherein the traffic of at least one of the first and second type of traffic is generated by the node.

20. The method as in claim 17, wherein the traffic of at least one of the first and second type of traffic is received and forwarded by the node.