Hierarchical statistically multiplexed counters and a method thereof
Embodiments of the present invention relate to an architecture that uses hierarchical statistically multiplexed counters to extend counter life by orders of magnitude. Each level includes statistically multiplexed counters. The statistically multiplexed counters includes P base counters and S subcounters, wherein the S subcounters are dynamically concatenated with the P base counters. When a row overflow in a level occurs, counters in a next level above are used to extend counter life. The hierarchical statistically multiplexed counters can be used with an overflow FIFO to further extend counter life.
1. A counter architecture implemented in a network device, the counter architecture comprising:
a hierarchy of levels of statistically multiplexed counters, wherein each of the hierarchy of levels includes N counters arranged in rows, wherein each of the rows includes P base counters and S subcounters, wherein at least one of the P base counters can be dynamically concatenated with one or more of the S subcounters to flexibly extend the counting capacity.
2. The network device of claim 1 , wherein counters in the same row in one level of the hierarchy of levels are shuffled into different rows in a next level above of the hierarchy of levels.
3. The network device of claim 2 , wherein a randomization of the shuffle is a bit reverse of a counter identifier of a counter, a hash function or a bit arrangement in another order.
4. The network device of claim 1 , wherein the counter architecture further includes a mirrored shift logic to extend the P counters to a full width such that a full range of shifting is reduced.
5. The network device of claim 1 , wherein the counter architecture is configured to update a counter by:
determining whether a corresponding row of the counter in a current level of the hierarchy of levels overflows;
based on the determination that the corresponding row in the current level does not overflow, processing each level below the current level by using a first routine and processing the current level by using a second routine; and
based on the determination that the corresponding row in the current level does overflow, determining whether a corresponding row of the counter in a next level above overflows;
based on the determination that the corresponding row of the counter in the next level above does not overflow, processing each level below the next level above by using the first routine and processing the next level above by using the second routine; and
based on the determination that the corresponding row of the counter in the next level above does overflow, when the next level above is not the highest level in the hierarchy of levels, returning to the step of determining whether a corresponding row of the counter in a next level above overflows, and when the next level above is the highest level in the hierarchy of levels, processing the next level above and each level below the next level above by using the first routine and updating an overflow queue.
6. The network device of claim 5 , wherein the first routine includes incrementing the counter in the corresponding level and shrinking the counter in the corresponding level.
7. The network device of claim 5 , wherein the second routine includes incrementing the counter in the corresponding level.
8. The network device of claim 7 , wherein the incrementing the counter includes expanding a size of the counter in the corresponding level.
9. The network device of claim 5 , wherein updating the overflow queue includes pushing a counter identifier of the counter and an overflow width into the overflow queue.
10. The network device of claim 5 , wherein the overflow queue is shared by the N counters in the highest level in the hierarchy of levels.
11. The network device of claim 1 , wherein the N counters are stored in an on-chip SRAM memory, using the plurality of banks of memory.