Data flow monitoring at a network node using periodically incremented counters for comparison to predetermined data flow thresholds

• US 6,381,649 B1
• Filed: 02/05/1999
• Issued: 04/30/2002
• Est. Priority Date: 02/05/1999
• Status: Expired due to Term

• Current Assignee: Parity Networks LLC
• Original Assignee: Pluris, Inc
• Inventors: Carlson, James D.
• Primary Examiner(s): Lim, Krisna
• Application Number:
  US09/234,082
• Time in Patent Office: 1,180 Days
• Field of Search: 709/224, 709/232, 709/233, 709/234, 709/235, 709/238, 370/230, 370/232, 370/233, 370/234, 370/235, 710/29
• US Class Current: 709/235
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5637 Leaky Buckets
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/026 using flow identification
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/31 by tagging of packets, e.g. using discard eligibility [DE] bits
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04Q 2213/13103 Memory
• CPC Class Codes: H04Q 2213/13106 Microprocessor, CPU
• CPC Class Codes: H04Q 2213/1325 Priority service
• CPC Class Codes: H04Q 2213/13251 Restricted service, class of service
• CPC Class Codes: H04Q 2213/13296 Packet switching, X.25, frame relay
• CPC Class Codes: H04Q 2213/13389 LAN, internet

Abstract

An apparatus and method for monitoring data flow at a node on a network are disclosed. A memory location or “bucket” is allocated to each of a plurality of links and classes of service at the node. A free-running counter is incremented at a rate determined by the maximum allowable data rates on the various links and classes of service. When a data packet is received at a particular link and class of service, the corresponding memory location or bucket is adjusted or “leaked” by subtracting the present counter value from the present bucket contents. That difference is then added to the number of units of data, i.e., bytes or groups of bytes of data, contained in the incoming packet. That sum is then compared with a predetermined threshold determined by the allowable data rate associated with the link and class of service. If the threshold is exceeded, then the incoming data packet is marked accordingly. The system can include multiple stages of monitoring such that multiple thresholds can be used to assign one of multiple discard eligibility values to the incoming packet.

Claims

1. A method of monitoring data traffic at a node on a network, the node facilitating data transfer on at least one link having at least one class of service, the data being transferred in data packets and each data packet including at least one unit of data, said method comprising:

for each of at least one selected link and class of service, storing an updatable value in a storing device;

periodically incrementing a counter value in a counter at a rate determined by an allowable data rate associated with the selected link and class of service;

receiving a data packet;

counting a number of units of data in the data packet;

computing an adjusted updatable value by adjusting the updatable value according to the counter value when the data packet was received and the number of units of data in the data packet;

comparing the adjusted updatable value to a predetermined threshold associated with the selected link and class of service; and

marking the data packet with respect to the allowable data rate based on whether the adjusted updatable value exceeds the predetermined threshold.

2. The method of claim 1 wherein computing an adjusted updatable value comprises computing a difference between the updatable value and the counter value when the data packet was received.

3. The method of claim 2 wherein computing an adjusted updatable value further comprises computing a sum of the number of units of data in the data packet and the difference between the updatable value and the counter value when the data packet was received.

4. The method of claim 3 further comprising updating the updatable value using the adjusted updatable value.

5. The method of claim 4 wherein updating the updatable value comprises computing a sum of the adjusted updatable value and the number of units of data in the data packet.

6. The method of claim 1 further comprising updating the updatable value using the adjusted updatable value.

7. The method of claim 1 wherein each link can include multiple classes of service.

8. The method of claim 7 wherein each class of service can have a unique allowable data rate.

9. The method of claim 1 wherein the storing device stores a plurality of updatable values for each of a plurality of links.

10. The method of claim 1 wherein the storing device stores a plurality of updatable values for each of a plurality of classes of service.

11. The method of claim 1 wherein marking the data packet comprises setting a priority for discarding the data packet.

12. The method of claim 1 wherein marking the data packet comprises altering a discard eligibility value for the data packet.

13. The method of claim 1 further comprising associating the predetermined threshold with a priority for discarding a packet of data.

14. The method of claim 1 further comprising associating the predetermined threshold with a discard eligibility value for the packet.

15. The method of claim 1 wherein the unit of data is a byte of data.

16. The method of claim 1 wherein the unit of data is a plurality of bytes of data.

17. The method of claim 1 wherein a link and class of service can be associated with multiple predetermined thresholds related to the allowable data rate of the link and class of service such that the data packet can be classified according to which of the predetermined thresholds are exceeded.

18. The method of claim 17 further comprising associating each predetermined threshold with a priority for discarding a packet of data.

19. The method of claim 17 further comprising associating each predetermined threshold with a discard eligibility value for the packet.

20. The method of claim 17 further comprising associating each predetermined threshold with an updatable value.

21. The method of claim 1 further comprising:

storing a second updatable value associated with the selected link and class of service in a second storing device;

computing a second adjusted updatable value according to the counter value when the data packet was received and the number of units of data in the data packet;

comparing the second adjusted updatable value to a second predetermined threshold associated with the selected link and class of service; and

marking the data packet with respect to the allowable data rate based on whether the second adjusted updatable value exceeds the second predetermined threshold.

22. The method of claim 21 further comprising, if the first adjusted updatable value exceeds the first predetermined threshold, updating the first updatable value by adding the number of units of data in the received data packet that do not cause the first predetermined threshold to be exceeded to the first updatable value.

23. The method of claim 1 further comprising:

if the first adjusted updatable value exceeds the first predetermined threshold, storing a second updatable value associated with the selected link and class of service in a second storing device;

computing a second adjusted updatable value according to the counter value when the data packet was received and the number of units of data in the data packet;

comparing the second adjusted updatable value to a second predetermined threshold associated with the selected link and class of service; and

marking the data packet with respect to the allowable data rate based on whether the second adjusted updatable value exceeds the second predetermined threshold.

24. The method of claim 1 further comprising receiving a data packet with zero units of data to update the updatable value in the storing device.

25. An apparatus for monitoring data traffic at a node on a network, the node facilitating data transfer on at least one link having at least one class of service, the data being transferred in data packets and each data packet including at least one unit of data, said apparatus comprising:

a storing device for storing an updatable value for each of at least one selected link and class of service;

a counter for holding a counter value, said counter value being periodically incremented at a rate determined by a maximum allowable data rate associated with the selected link and class of service;

an input unit for receiving a data packet; and

a processor for (i) counting a number of units of data in the data packet, (ii) computing an adjusted updatable value by adjusting the updatable value according to the counter value when the data packet was received and the number of units of data in the data packet, (iii) comparing the adjusted updatable value to a predetermined threshold associated with the selected link and class of service, and (iv) marking the data packet with respect to the allowable data rate based on whether the adjusted updatable value exceeds the predetermined threshold.

26. The apparatus of claim 25 wherein the storing device stores a plurality of updatable values for each of a plurality of links.

27. The apparatus of claim 25 wherein the storing device stores a plurality of updatable values for each of a plurality of classes of service.

28. The apparatus of claim 25 wherein the storing device comprises a SRAM.

29. The apparatus of claim 25 wherein the processor marks the incoming data packet by setting a priority for discarding the data packet.

30. The apparatus of claim 25 wherein the predetermined threshold is associated with a priority for discarding a packet of data.

31. The apparatus of claim 25 wherein the unit of data is a byte of data.

32. The apparatus of claim 25 wherein the unit of data is a plurality of bytes of data.

33. The apparatus of claim 25 wherein the processor updates the updatable value based on the number of units of data in the packet of data.

34. The apparatus of claim 25 wherein a link and class of service can be associated with multiple predetermined thresholds related to the maximum allowable data rate of the link and class of service such that the incoming data packet can be classified according to which of the predetermined thresholds are exceeded.

35. The apparatus of claim 25 further comprising:

a second storing device for storing a second updatable value associated with the selected link and class of service; and

a second processor for (i) computing a second adjusted updatable value by adjusting the second updatable value according to the counter value when the data packet was received and the number of units of data in the data packet, (ii) comparing the second adjusted updatable value to a second predetermined threshold associated with the selected link and class of service, and (iii) marking the data packet with respect to the allowable data rate based on whether the second adjusted updatable value exceeds the second predetermined threshold.

36. The apparatus of claim 25 further comprising:

a second storing device for storing a second updatable value associated with the selected link and class of service if the first adjusted updatable value exceeds the first predetermined threshold; and

a second processor for (i) computing a second adjusted updatable value by adjusting the second updatable value according to the counter value when the data packet was received and the number of units of data in the data packet, (ii) comparing the second adjusted updatable value to a second predetermined threshold associated with the selected link and class of service, and (iii) marking the data packet with respect to the allowable data rate based on whether the second adjusted updatable value exceeds the second predetermined threshold.