Time efficient counters and meters architecture

Patent metadata

Field	Value
Publication number	US-9781018-B2
Application number	US-201414269664-A
Country	US
Kind code	B2
Filing date	May 5, 2014
Priority date	May 3, 2013
Publication date	Oct 3, 2017
Grant date	Oct 3, 2017

Abstract

A network device includes a plurality of interfaces configured to receive, from a network, packets to be processed by the network device. A load determination circuit of the network device is configured to determine whether a packet traffic load of the network device is above a traffic load threshold, and a dual-mode counter module is configured to (i) determine a count of quanta associated with the received packets using a first counting mode in response to the load determination unit determining that the packet traffic load is above the traffic load threshold, and (ii) determine a count of quanta associated with the received packets using a second counting mode, different than the first counting mode, in response to the load determination unit determining that the packet traffic load is not above the traffic load threshold.

First claim

What is claimed:

1. A network device comprising:
a plurality of interfaces configured to receive, from a network, packets to be processed by the network device;
a load determination circuit configured to determine whether a rate at which events associated with the received packets occur exceeds a maximum update rate at which a counter associated with a memory of the network device is able to be updated; and
a dual-mode counter module configured to (i) estimate a count of quanta associated with the received packets without counting every event using a first counting mode, which uses non-deterministic sampling, in response to the load determination unit determining that the rate at which events associated with the received packets occur exceeds the maximum update rate, and (ii) determine a count of quanta associated with the received packets using a second counting mode, which uses deterministic sampling in response to the load determination unit determining that the rate at which events associated with the received packets occur is less than the maximum update rate.

2. The network device of claim 1 , wherein the first counting mode uses statistical sampling of events associated with the received packets.

3. The network device of claim 2 , wherein the dual-mode counter module is configured to store the determined counts of quanta in a counter memory using exact value representations.

4. The network device of claim 2 , wherein the dual-mode counter module is configured to store the determined counts of quanta in a counter memory using truncated representations or mantissa-exponent representations.

5. The network device of claim 1 , wherein the load determination circuit is configured to determine whether the rate at which events associated with the received packets occur exceeds the maximum update rate based on one or both of (i) an amount of sampled events associated with the received packets, and (ii) a state of a meter configured to monitor the rate at which events associated with the received packets occur prior to sampling.

6. The network device of claim 1 , wherein the dual-mode counter module is configured to:
estimate the count of quanta associated with the received packets using the first counting mode by determining (i) a count of packets within the received packets using the first counting mode, or (ii) a count of blocks of length q within the received packets using the first counting mode, q being an integer greater than or equal to one; and
determine the count of quanta associated with the received packets using the second counting mode by determining (i) a count of packets within the received packets using the second counting mode, or (ii) a count of blocks of length q within the received packets using the second counting mode.

7. A method for counting events in a network device, the method comprising:
receiving, from a network, packets to be processed by the network device;
determining whether a rate at which events associated with the received packets occur exceeds a maximum update rate at which a counter associated with a memory of the network device is able to be updated;
responsively to determining that the rate at which events associated with the received packets occur exceeds the maximum update rate, estimating a count of quanta associated with the received packets without counting every event using a first counting mode that uses non-deterministic sampling; and
responsively to determining that the rate at which events associated with the received packets occur is less than the maximum update rate, determining a count of quanta associated with the received packets using a second counting mode that uses deterministic sampling.

8. The method of claim 7 , wherein:
estimating the count of quanta associated with the received packets using the first counting mode includes using statistical sampling of events associated with the received packet.

9. The method of claim 8 , further comprising:
storing the determined counts of quanta in the memory using exact value representations.

10. The method of claim 8 , further comprising:
storing the determined counts of quanta in the memory using truncated representations or mantissa/exponent representations.

11. The method of claim 7 , wherein determining whether the rate at which events associated with the received packets occur exceeds the maximum update rate is based on one or both of (i) an amount of sampled events associated with the received packets, and (ii) a state of a meter configured to monitor the rate at which events associated with the received packets occur prior to sampling.

12. The method of claim 7 , wherein:
estimating the count of quanta associated with the received packets using the first counting mode includes determining (i) a count of packets within the received packets using the first counting mode, or (ii) a count of blocks of length q within the received packets using the first counting mode, q being an integer greater than or equal to one; and
determining the count of quanta associated with the received packets using the second counting mode includes determining (i) a count of packets within the received packets using the second counting mode, or (ii) a count of blocks of length q within the received packets using the second counting mode.

13. A network device comprising:
a plurality of interfaces configured to receive, from a network, packets to be processed by the network device; and
a counter module configured to estimate, using a statistical sampling operation, a count of quanta associated with packets received via the plurality of interfaces, the statistical sampling operation being performed according to a control parameter that is bounded based on i) a bandwidth metric of the network device and ii) a maximum update rate at which a counter associated with a memory of the network device is able to be updated.

14. The network device of claim 13 , wherein the bandwidth metric is a maximal theoretical event rate of the network device.

15. The network device of claim 14 , wherein the control parameter is bounded by a function of i) the maximum update rate at which the counter is able to be updated, and ii) a maximal theoretical event rate of the network device.

16. The network device of claim 13 , wherein the statistical sampling operation samples events associated with the received packets according to a probability that is calculated based on the control parameter.

17. The network device of claim 13 , wherein the statistical sampling operation samples events associated with the received packets according to a probability that is calculated based on (i) the control parameter and (ii) lengths of the packets received via the plurality of interfaces.

18. The network device of claim 13 , wherein the statistical sampling operation samples all events associated with those packets, of the received packets, having a length greater than a threshold length.

19. The network device of claim 13 , wherein the counter module is configured to estimate the count of quanta associated with the received packets by estimating (i) a count of packets within the received packets, or (ii) a count of blocks of length q within the received packets.

20. A method for counting events in a network device, the method comprising:
receiving, from a network, packets to be processed by the network device; and
estimating, using a statistical sampling operation performed according to a control parameter that is bounded based on i) a bandwidth metric of the netwo

Assignees

• Marvell World Trade Ltd

Inventors

• Arad Carmi
• Boden Kurt Thomas
• Levy Gil
• Carlstrom Jakob

Classifications

• H04L41/147

  for predicting network behaviour · CPC title

• H04L43/024 Primary

  by adaptive sampling · CPC title

• H04L43/16

  Threshold monitoring · CPC title

• H04L43/02

  Capturing of monitoring data · CPC title

• H04L43/0876

  Network utilisation, e.g. volume of load or congestion level · CPC title