Learning machine-based granular segment/path characteristic probing technique

• US 9,473,364 B2
• Filed: 01/27/2014
• Issued: 10/18/2016
• Est. Priority Date: 01/06/2014
• 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, Mermoud, Grgory, Hui, Jonathan W.
• Primary Examiner(s): Chen, Alan
• Application Number:
  US14/164,544
• Publication Number:
  US 20150195184A1
• Time in Patent Office: 995 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 5/025 Extracting rules from data
• CPC Class Codes: G06N 99/00 Subject matter not provided for in other groups of this subclass
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/5025 by proactively reacting to service quality change, e.g. by reconfiguration after service quality degradation or upgrade
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04L 47/365 Dynamic adaptation of the packet size
• CPC Class Codes: H04W 24/02 Arrangements for optimising operational condition
• CPC Class Codes: H04W 24/04 Arrangements for maintaining operational condition
• 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 routing topology of a network including nodes interconnected by communication links is determined. Important nodes in the network which are of relative importance are determined based on their location in the determined routing topology. Also, one or more request messages are sent causing the important nodes to gather local network metrics. Then, in response to the one or more request messages, one or more response messages including the network metrics gathered by each important node are received.

Claims

1. A method, comprising:

determining a routing topology of a network including nodes interconnected by communication links;

determining important nodes in the network which are of relative importance based on their location in the determined routing topology;

designating a head node of the important nodes;

sending one or more request messages causing the important nodes to gather local network metrics; and

in response to the one or more request messages, receiving one or more response messages including the network metrics gathered by each important node.

2. The method as in claim 1, wherein:

only a single request message is sent, and

only a single response message, which aggregates reported values from the important nodes, is received.

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

sending the one or more request messages to the head node, wherein the head node is configured to forward the one or more request messages to the remaining important nodes; and

receiving the one or more response messages from the head node.

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

sending an instruction to the head node to request the remaining important nodes to gather the local network metrics.

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

receiving the one or more response messages as compressed data, the one or more response messages being compressed by the head node.

6. The method as in claim 1, wherein the determining of the important nodes further comprises:

determining a region of the network that experiences relatively high volumes of network traffic; and

identifying nodes that reside within the region as the important nodes.

7. The method as in claim 1, wherein the determining of the important nodes further comprises:

determining a communication route in the network that experiences relatively high volumes of network traffic; and

identifying nodes that reside along the communication route as the important nodes.

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

selecting one or more network metrics to be gathered by the important nodes; and

including an indication of the one or more selected network metrics in the one or more request messages.

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

defining a condition which, when satisfied, causes the important nodes to report the gathered network metrics; and

including an indication of the rule in the one or more request messages.

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

defining a schedule, whereby the important nodes report the gathered network metrics according to the schedule; and

including an indication of the schedule in the one or more request messages.

11. The method as in claim 1, wherein the routing topology is configured as a directed acyclic graph (DAG).

12. An apparatus, comprising:

one or more network interfaces that communicate with a network;

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

a memory configured to store program instructions which contain the process executable by the processor, the process comprising;

determining a routing topology of the network including nodes interconnected by communication links;

determining important nodes in the network which are of relative importance based on their location in the determined routing topology;

designating a head node of the important nodes;

sending one or more request messages causing the important nodes to gather local network metrics; and

in response to the one or more request messages, receiving one or more response messages including the network metrics gathered by each important node.

13. The apparatus as in claim 12, wherein:

only a single request message is sent, and

only a single response message, which aggregates reported values from the important nodes, is received.

14. The apparatus as in claim 12, wherein the process further comprises:

sending the one or more request messages to the head node, wherein the head node is configured to forward the one or more request messages to the remaining important nodes; and

receiving the one or more response messages from the head node.

15. The apparatus as in claim 12, wherein the process further comprises:

sending an instruction to the head node to request the remaining important nodes to gather the local network metrics.

16. The apparatus as in claim 12, wherein the process further comprises:

receiving the one or more response messages as compressed data, the one or more response messages being compressed by the head node.

17. The apparatus as in claim 12, wherein the determining of the important nodes further comprises:

determining a region of the network that experiences relatively high volumes of network traffic; and

identifying nodes that reside within the region as the important nodes.

18. The apparatus as in claim 12, wherein the determining of the important nodes further comprises:

determining a communication route in the network that experiences relatively high volumes of network traffic; and

identifying nodes that reside along the communication route as the important nodes.

19. The apparatus as in claim 12, wherein the process further comprises:

selecting one or more network metrics to be gathered by the important nodes; and

including an indication of the one or more selected network metrics in the one or more request messages.

20. The apparatus as in claim 12, wherein the process further comprises:

defining a condition which, when satisfied, causes the important nodes to report the gathered network metrics; and

including an indication of the rule in the one or more request messages.

21. The apparatus as in claim 12, wherein the process further comprises:

defining a schedule, whereby the important nodes report the gathered network metrics according to the schedule; and

including an indication of the schedule in the one or more request messages.

22. The apparatus as in claim 12, wherein the routing topology is configured as a directed acyclic graph (DAG).

23. A tangible non-transitory computer readable medium storing program instructions that cause a computer to execute a process, the process comprising:

determining a routing topology of a network including nodes interconnected by communication links;

determining important nodes in the network which are of relative importance based on their location in the determined routing topology;

designating a head node of the important nodes;

sending one or more request messages causing the important nodes to gather local network metrics; and

in response to the one or more request messages, receiving one or more response messages including the network metrics gathered by each important node.