Maintaining exact statistics counters with a multi-level counter memory

For monitoring and measuring high-speed networks accurately in real-time, a large number of statistics counters may need to be maintained at wirespeeds (e.g. 10 Gbit/s), Expensive, but fast. SRAM is needed for storing the counters to satisfy the speed requirements. However, high-density, but slower, DRAM is needed to provide the necessary storage capacity for storing all counter values exactly. Recent papers by Shah et al. (2003) and Ramabhadran and Varghese (2003) have addressed the problem using counter memory architectures based on one level of fast SRAM for storing partial counter values and a high-capacity DRAM for storing full counter values. In this paper, we propose to extend their work with a multi-level counter memory architecture to reduce the amount of fast memory required. Our multi-level counter memory architecture can reduce the amount of equivalent fast memory storage required by as much as 28%.