Traffic monitor using leaky bucket with variable fill

• US 6,567,379 B1
• Filed: 06/09/1999
• Issued: 05/20/2003
• Est. Priority Date: 06/09/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Walker, David S., Ullum, Daniel R.
• Primary Examiner(s): Yao, Kwang Bin
• Assistant Examiner(s): NGUYEN, HANH N
• Application Number:
  US09/328,702
• Time in Patent Office: 1,441 Days
• Field of Search: 370/389, 370/392, 370/395.31, 370/400-402, 370/428-429, 370/235, 370/235.1, 370/423, 370/390, 370/396, 370/395.32, 370/229, 709/238, 709/224, 709/234, 709/235, 709/245, 709/232
• US Class Current: 370/235.1
• CPC Class Codes: H04L 2012/5637 Leaky Buckets
• CPC Class Codes: H04L 2012/5684 Characteristics of traffic flows
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/022 by sampling
• CPC Class Codes: H04L 43/024 by adaptive sampling
• CPC Class Codes: H04L 43/12 Network monitoring probes
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/21 using leaky-bucket
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/503 Policing

Abstract

An integrated circuit monitors the most active traffic flow rates on a communications network by using a leaky bucket model having a variable fill rate. As a switch receives packets, the packet identifications are sampled. A sampled packet identification is compared to record identifications in a table of identifications. If the sampled and record identifications match, an activity value for the packet identification is increased by an amount inversely proportional to an activity value associated with the record identification. If the sampled and record identifications do not match, the activity value is decreased. Record identifications are removed from the table when the activity value decreases to a specified level. New sampled identifications are added to the table if empty records exist.

Claims

1. A communications network device comprising:

a port configured to receive a communications signal from a source;

a second port configured to transmit a second communications signal to a destination;

a sampler that samples a signal characteristic;

a comparator that compares the sampled signal characteristic to a record characteristic in a table of characteristics; and

a controller that increases an activity value corresponding to the record characteristic if the sampled characteristic and the record characteristic match, and decreases the activity value if the sampled characteristic and the record characteristic do not match.

2. The device of claim 1 wherein the activity value corresponding to the record characteristic is increased by an amount depending on the activity value.

3. The device of claim 1 wherein the signal characteristic is address information within a packet.

4. The device of claim 1 wherein the sampled signal characteristic is made a record characteristic in the table of characteristics when the activity value has a specified value.

5. The device of claim 1 wherein a particular record characteristic is removed from the table of characteristics after the activity value corresponding to the particular record characteristic has a specified value.

6. The device of claim 1 wherein when the activity value has a first value, it is increased by a greater amount than when the activity value has a second value, the first value being less than the second value.

7. The device of claim 1 wherein the number of records in the table of characteristics corresponds to the rate at which the sampler samples a signal characteristic.

8. The device of claim 1 wherein the sampler, the comparator, and the controller form part of an integrated circuit.

9. The device of claim 1 wherein the sampler, the comparator, and the controller are a programmed computer.

10. A device for monitoring network activity comprising:

a sampler that samples a signal characteristic;

a comparator that compares the sampled signal characteristic to a record characteristic in a table of characteristics; and

a controller that increases an activity value corresponding to the record characteristic if the sampled characteristic and the record characteristic match, and decreases the activity value if the sampled characteristic and the record characteristic do not match.

11. The device of claim 10 wherein the activity value corresponding to the record characteristic is increased by an amount depending on the activity value.

12. The device of claim 10 wherein the signal characteristic is address information within a packet.

13. The device of claim 10 wherein the sampled signal characteristic is made a record characteristic in the table of characteristics when the activity value has a specified value.

14. The device of claim 10 wherein a particular record characteristic is removed from the table of characteristics after the activity value corresponding to the particular record characteristic has a specified value.

15. The device of claim 10 wherein when the activity value has a first value it is increased by a greater amount than when the activity value has a second value, the first value being less than the second value.

16. The device of claim 10 wherein the number of records in the table of characteristics corresponds to the rate at which the sampler samples a signal characteristic.

17. The device of claim 10 wherein the sampler, the comparator, and the controller form part of an integrated circuit.

18. The device of claim 10 wherein the sampler, the comparator, and the controller are a programmed computer.

19. A computer readable storage medium configured with instructions for a computer implemented process comprising:

sampling a signal characteristic;

comparing the sampled signal characteristic to a record characteristic in a table of characteristics; and

increasing an activity value corresponding to the record characteristic if the sampled characteristic and the record characteristic match, and decreasing the activity value if the sampled characteristic and the record characteristic do not match.

20. The medium of claim 19 wherein the activity value corresponding to the record characteristic is increased by an amount depending on the activity value.

21. The medium of claim 19 wherein the signal characteristic is address information in a packet.

22. The medium of claim 19 wherein the sampled signal characteristic is made a record characteristic in the table of characteristics when the activity value has a specified value.

23. The medium of claim 19 wherein a particular record characteristic is removed from the table of characteristics after the activity value corresponding to the particular record characteristic has a specified value.

24. The medium of claim 19 wherein when the activity value has a first value, it is increased by a greater amount than when the activity value has a second value, the first value being less than the second value.

25. The medium of claim 19 wherein the number of records in the table of characteristics corresponds to the rate at which the process samples a signal characteristic.

26. A process performed by a communications apparatus comprising:

sampling a signal characteristic;

comparing the sampled signal characteristic to a record characteristic in a table of characteristics; and

increasing an activity value corresponding to the record characteristic if the sampled characteristic and the record characteristic match, and decreasing the activity value if the sampled characteristic and the record characteristic do not match.

27. The process of claim 26 wherein the activity value corresponding to the record characteristic is increased by an amount depending on the activity value.

28. The process of claim 26 wherein the signal characteristic is address information in a packet.

29. The process of claim 26 wherein the sampled signal characteristic is made a record characteristic in the table of characteristics when the activity value has a specified value.

30. The process of claim 26 wherein a particular record characteristic is removed from the table of characteristics after the activity value corresponding to the particular record characteristic has a specified value.

31. The process of claim 26 wherein when the activity value has a first value, it is increased by a greater amount than when the activity value has a second value, the first value being less than the second value.

32. The process of claim 26 wherein the number of records in the table of characteristics corresponds to the rate at which the process samples a signal characteristic.