Sampling packets for network monitoring

• US 6,920,112 B1
• Filed: 06/29/1998
• Issued: 07/19/2005
• Est. Priority Date: 06/29/1998
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bierman, Andrew, Robert, Stephan, McCloghrie, Keith, Walrand, Jean
• Primary Examiner(s): Phunkulh, Bob A.
• Application Number:
  US09/106,519
• Time in Patent Office: 2,577 Days
• Field of Search: 370/252, 370/253, 370/230, 370/231, 370/232, 370/392, 370/412, 370/428, 370/429, 370/474, 370/477, 710/33, 710/34
• US Class Current: 370/252
• CPC Class Codes: H04L 43/022 by sampling

Abstract

The invention provides a method and system for collecting aggregate information about network traffic, while maintaining processor load relatively constant despite substantial variation in network traffic, and capable of substantially accurate frequency measurement even for relatively infrequent events. A packet monitoring system includes an input port for receiving network packets, a sampling element for selecting a fraction of those packets for review, and a queue of selected packets. The packets in the queue are coupled to a packet-type detector for detecting packets of a selected type; the system applies a measurement technique for determining a frequency measure for those detected packets. The system includes a feedback technique for adaptively altering the sampling rate fraction, responsive to the queue length and possibly other factors, such as processor load or the detected frequency measure. The measurement technique also determines an error range and a measure of confidence that the actual frequency is within the error range of the measured frequency. The system can detect packets of multiple selected types essentially simultaneously, and provide measured frequencies and error ranges for all of the multiple selected types at once. Also, the measurement technique is selected so as to impose relatively light processor load per packet.

Claims

1. A system including an input port for receiving network packets;

a sampling element for selecting a fraction of those packets for review, said sampling element including a feedback element for adaptively altering said fraction;

a queue of selected packets;

a packet-type detector to detect packets of a particular type, said packet type detector coupled to said queue; and

a frequency measurement element to determine an expected frequency of a particular packet type, said frequency measurement element coupled to said packet-type detector;

wherein said feedback element is responsive to a length of said queue.

2. A system as in claim 1, wherein said feedback element is responsive to a load on said frequency measurement element.

3. A system as in claim 1, wherein said feedback element is responsive to a frequency measure determined by said frequency measurement element.

4. A system as in claim 1, wherein a default value for said fraction is selected response to a bandwidth of said input type.

5. A system as in claim 4, wherein said fraction is adaptively altered based on a presence or absence of a particular type of packet selected from among plural types of packets.

6. A method, including steps for sampling a set of packets at a network interface of a switch, said steps for sampling including steps for adaptively altering a fraction of said packets for selection;

wherein said steps for adaptively altering a fraction of said packets for selection include steps for maintaining a queue of selected packets; and

altering said fraction in response to a length of said queue and;

wherein the method includes steps for determining a frequency of packets of a known type within said selected packets.

7. A method as in claim 6, wherein said steps for adaptively altering a fraction of said packets for selection include steps for measuring a frequency of packets of a known type within said selected packets;

altering said fraction in response to a load imposed by said steps for measuring.

8. A method as in claim 6, wherein said steps for adaptively altering a fraction of said packets for selection include steps for altering said fraction in response to two or more factors responsive to said selected packets.

9. A method as in claim 6, including steps for determining an error range for said measured frequency.

10. A method as in claim 6, including steps for setting a control parameter;

sampling said received packets in response to said control parameter, to provide a queue of sampled packets;

comparing a length of said queue with a threshold;

altering said control parameter in response to said threshold.

11. A method as in claim 10, wherein said control parameter is a fraction of said received packets to sampled for said queue.

12. A method as in claim 10, wherein said threshold includes at least one of:

a lower bound for said length, an upper bound for said length.

13. A method as in claim 10, wherein said threshold includes a lower bound for said length and said steps for altering said control parameter operate to lengthen said queue in response to said steps for comparing.

14. A method as in claim 10, wherein said control parameter is a fraction of said received packets to sample for said queue;

said threshold includes a lower bound for said length; and

said steps for altering said control parameter decrease said control parameter in response to said steps for comparing.

15. A method as in claim 10, wherein said threshold includes an upper bound for said length and said steps for altering said control parameter operate to shorten said queue in response to said steps for comparing.

16. A method as in claim 10, wherein said control parameter is a fraction of said received packets to sample for said queue;

said threshold includes an upper bound for said length; and

said steps for altering said control parameter increase said control parameter in response to said steps for comparing.

17. A method as in claim 10, wherein said steps for altering said control parameter operate to maintain said control parameter constant for at least a selected number of sampled packets.

18. A method as in claim 10, wherein said steps for sampling do not produce skew.

19. A method as in claim 6, wherein a default value for said fraction is selected response to a bandwidth of said network interface.

20. A method as in claim 19, wherein said fraction is adaptively altered based on a presence or absence of a particular type of packet selected from among plural types of packets.

21. A system including

means for collecting aggregate information about network traffic;

means for maintaining processor load relatively constant for a processor controlling said means for collecting despite substantial variation in network traffic;

wherein said means for collecting and said means for maintaining include an input port for receiving network packets, a sampling element for selecting a fraction of those packets for review, said sampling element including a feedback element for adaptively altering said fraction, a queue of selected packets, a packet-type detector to detect packets of a particular type, said packet-type detector coupled to said queue, and a frequency measurement element to determine an expected frequency of a particular packet type, said frequency measurement element coupled to said packet-type detector; and

wherein said feedback element is responsive to a length of said queue.

22. A system as in claim 21, wherein a default value for said fraction is selected response to a bandwidth of said input port.

23. A system as in claim 22, wherein said fraction is adaptively altered based on a presence or absence of a particular type of packet selected from among plural types of packets.

24. A computer-readable medium carrying one or more instructions, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

sampling a set of packets at a network interface of a switch, said step for sampling including steps for adaptively altering a fraction of said packets for selection;

wherein said steps for adaptively altering a fraction of said packets for selection include steps for maintaining a queue of selected packets; and

altering said fraction in response to a length of said queue; and

determining a frequency of packets of a known type within said selected packets.

25. The computer-readable medium of claim 24, wherein said steps for adaptively altering a fraction of said packets for selection include steps for measuring a frequency of packets of a known type within said selected packets;

altering said fraction in response to a load imposed by said steps for measuring.

26. The computer-readable medium of claim 24, wherein said steps for adaptively altering a fraction of said packets for selection include steps for altering said fraction in response to two or more factors responsive to said selected packets.

27. The computer-readable medium of claim 24, wherein the computer-readable medium further includes sequences of instructions for performing steps for determining an error range for said measured frequency.

28. The computer-readable medium of claim 24, wherein the computer-readable medium further includes sequences of instructions for performing steps for setting a control parameter;

sampling said received packets in response to said control parameter, to provide a queue of sampled packets;

comparing a length of said queue with a threshold;

altering said control parameter in response to said threshold.

29. The computer-readable medium of claim 28, wherein said control parameter is a fraction of said received packets to sampled for said queue.

30. The computer-readable medium of claim 28, wherein said threshold includes at least one of:

a lower bound for said length, an upper bound for said length.

31. The computer-readable medium of claim 28, wherein said threshold includes a lower bound for said length and said steps for altering said control parameter operate to lengthen said queue in response to said steps for comparing.

32. The computer-readable medium of claim 28, wherein said control parameter is a fraction of said received packets to sample for said queue;

said threshold includes a lower bound for said length; and

said steps for altering said control parameter decrease said control parameter in response to said steps for comparing.

33. The computer-readable medium of claim 28, wherein said threshold includes an upper bound for said length and said steps for altering said control parameter operate to shorten said queue in response to said steps for comparing.

34. The computer-readable medium of claim 28, wherein said control parameter is a fraction of said received packets to sample for said queue;

said threshold includes an upper bound for said length; and

said steps for altering said control parameter increase said control parameter in response to said steps for comparing.

35. The computer-readable medium of claim 28, wherein said steps for altering said control parameter operate to maintain said control parameter constant for at least a selected number of sampled packets.

36. A computer-readable medium as recited in claim 28, wherein said steps for sampling do not produce skew.

37. A computer-readable medium as recited in claim 24, wherein a default value for said fraction is selected response to a bandwidth of said network interface.

38. A computer-readable medium as recited in claim 37, wherein said fraction is adaptively altered based on a presence or absence of a particular type of packet selected from among plural types of packets.