Methods and apparatus for scheduling network probes

• US 7,912,934 B1
• Filed: 01/09/2006
• Issued: 03/22/2011
• Est. Priority Date: 01/09/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Aldrin, Sam K., Nadeau, Thomas D., Melton, David Richard
• Primary Examiner(s): Flynn; Nathan
• Assistant Examiner(s): CHANG, STEPHANIE L
• Application Number:
  US11/328,436
• Time in Patent Office: 1,898 Days
• Field of Search: 709/224, 709/223, 709/227, 370/395.5, 370/254, 370/252, 370/392, 370/410, 718/100
• US Class Current: 709/223
• CPC Class Codes: H04L 41/083 for increasing network speed
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0895 Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 43/12 Network monitoring probes
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/70 Routing based on monitoring results

Abstract

A system identifies a plurality of probes used for verifying network operation, and classifies the plurality of probes into probe groups, according to at least one parameter associated with the network operation. The system schedules operation of the probe group in accordance with a classification associated with each probe group, and operates the probe group to verify network operation.

Claims

1. A method of scheduling network processing, the method comprising:

identifying a plurality of probes, each respective one of the probes assigned to a network operation to verify connectivity in at least one virtual network, each one of the probes including a destination network address and a probe rate, the probe rate being indicative of a rate at which the respective one of the probes is propagated;

classifying, with a processor, the probes into a plurality of probe groups based on at least one parameter of the probes to verify connectivity in the at least one virtual network, the probes in each respective one of the probe groups sharing a respective common classification based on the at least one parameter of the probes, the at least one parameter of the probes including the probe rate;

optimizing, with the processor, network load resulting from the probes by scheduling, with the processor, operation of each respective one of the probe groups in accordance with the respective common classification, wherein scheduling the operation of each respective one of the probe groups comprises determining start times of the probe groups and probe group rates of the probe groups, the start times being distributed over time; and

operating the probe groups as scheduled to verify connectivity in the at least one virtual network.

2. The method of claim 1 further comprising:

identifying a plurality of paths in communication with the destination network address; and

associating the plurality of paths with the respective probe associated with the destination network address.

3. The method of claim 1 wherein classifying the probes into probe groups comprises:

for each probe group, determining a probe group maximum time indicative of a maximum time period during which the probe group must successfully complete the network operation.

4. The method of claim 3 wherein determining a probe group maximum time comprises:

classifying at least one of the probe groups into probe sub-groups; and

determining, for each probe sub-group, a probe sub-group maximum time indicative of a maximum time period during which the probe sub-group must successfully complete the network operation, the probe sub-group maximum time equal to or less than the probe group maximum time.

5. The method of claim 1 wherein determining the probe group rates of the probe groups comprises:

identifying a normal rate indicative of a rate at which the probe groups are propagated; and

identifying a failure rate indicative of a rate at which the probe groups are propagated when the probe groups fail to successfully reach a destination network address.

6. The method of claim 1 wherein classifying the probes into probe groups comprises:

configuring addressing information associated with a virtual network with the at least one parameter.

7. The method of claim 6 wherein configuring addressing information associated with a virtual network with the at least one parameter comprises:

identifying the destination network address associated with the addressing information; and

determining a respective probe group associated with the virtual network.

8. The method of claim 7 wherein determining a respective probe group associated with the virtual network comprises, in response to determining the respective group has not been configured for the virtual network, configuring the respective probe group for the virtual network.

9. The method of claim 1 wherein operating the probe groups as scheduled to verify connectivity in the at least one virtual network comprises:

computing a projected system resource usage to result from operation of at least one probe group, the at least one probe group included in the probe groups;

monitoring a system resource usage resulting from operation of the at least one probe group; and

deriving a performance metric from the system resource usage and the projected system resource usage for use in scheduling the at least one probe group.

10. The method of claim 9 comprising:

determining that at least one new probe has been added to the at least one probe group;

deriving an impact of the at least one new probe on the performance metric;

scheduling the probe groups further based on the impact of the at least one new probe; and

sending notification that the at least one new probe has been added to the at least one probe group.

11. The method of claim 10 wherein deriving the impact of the at least one new probe on the performance metric comprises:

determining that the impact of the at least one new probe on the performance metric will exceed a threshold for the performance metric; and

sending a notification notifying that the impact of the at least one new probe on the performance metric will exceed a threshold for the performance metric.

12. The method of claim 9 wherein computing the projected system resource usage of the at least one probe group comprises:

computing a projected system resource usage for a network operating at a maximum capacity for the network.

13. A computerized device comprising:

a memory;

a processor;

a communications interface;

an interconnection mechanism coupling the memory, the processor and the communications interface;

wherein the memory is encoded with a network processing scheduling application that, when executed with the processor, schedules network processing on the computerized device by performing the operations of;

identifying a plurality of probes, each respective one of the probes assigned to a network operation to verify connectivity in the at least one virtual network, each one of the probes including a destination network address and a probe rate, the probe rate being indicative of a rate at which the respective one of the probes is propagated;

classifying the probes into a plurality of probe groups according to at least one parameter of the probes, wherein classifying the probes into the probe groups results in the probes in each respective one of the probe groups sharing a respective common classification based on the at least one parameter of the probes, the at least one parameter of the probes including a priority;

optimizing network load resulting from the probes by scheduling operation of each respective one of the probe groups in accordance with the respective common classification, wherein scheduling the operation of each respective one of the probe groups comprises determining start times of the probe groups and probe group rates of the probe groups, the start times being distributed over time; and

operating the probe groups as scheduled to verify connectivity in the at least one virtual network.

14. The computerized device of claim 13 wherein when the computerized device performs the operation of operating the probe groups as scheduled, the computerized device further performs the operations of:

computing a projected system resource usage of at least one probe group, the at least one probe group included in the probe groups;

monitoring a system resource usage of the at least one probe group; and

deriving a performance metric from the system resource usage and the projected system resource usage for use in scheduling the at least one probe group.

15. The computerized device of claim 14 wherein the computerized device further performs the operations of:

identifying that at least one new probe has been added to the at least one probe group;

deriving an impact of the at least one new probe on the performance metric;

scheduling the probe groups also based on the impact of the at least one new probe; and

sending notification that the at least one new probe has been added to the at least one probe group.

17. The computerized device of claim 13 wherein when the computerized device performs the operation of scheduling the operation of the probe groups, the computerized device further schedules overlapping operation of the probe groups to maximize network resources while also limiting network load that results from operation of the probe groups as scheduled to remain below a predefined network operation threshold.

18. The computerized device of claim 13 wherein when the computerized device performs the operation of optimizing the network load resulting from the probes, the computerized device further performs the operations of:

scheduling a respective start time of each respective one of the probe groups to limit utilization of network resources caused by propagation of the probe groups to within a predefined network operation threshold; and

dynamically readjusting the predefined network operation threshold.

16. A non-transitory computer readable storage medium encoded with computer programming logic that when executed with a processor in a computerized device produces a network processing scheduling process that schedules network processing by causing the computerized device to perform the operations of:

identifying a plurality of probes, each respective one of the probes assigned to verify connectivity in the at least one virtual network, each one of the probes including a destination network address and a probe rate, the probe rate indicating a rate at which the respective one of the probes is transmitted;

classifying the probes into a plurality of probe groups according to at least one parameter of the probes, wherein classifying the probes into the probe groups results in the probes classified in each respective one of the probe groups sharing a respective common classification;

optimizing network load resulting from the probes by scheduling operation of the each respective one of the probe groups based on the respective common classification, wherein scheduling the operation of each respective one of the probe groups comprises determining start times of the probe groups and probe group rates of the probe groups, the start times being distributed over time; and

operating the probe groups as scheduled to verify connectivity in the at least one virtual network.