A randomized interleaved DRAM architecture for the maintenance of exact statistics counters
Bill Lin, Jun Jim Xu, Nan Hua, Hao Henry Wang, Haiquan Zhao · ACM SIGMETRICS Performance Evaluation Review · 2009
We extend a previously proposed randomized interleaved DRAM architecture [1] that can maintain wirespeed updates (say 40 Gb/s) to a large array (say millions) of counters. It works by interleaving updates to randomly distributed counters across multiple memory banks. Though unlikely, an adversary can conceivably overload a memory bank by triggering frequent updates to the same counter. In this work, we show this "attack" can be mitigated through caching pending updates, which can catch repeated updates to the same counter within a sliding time window. While this architecture of combining randomization with caching is simple and straightforward, the primary contribution of this work is to rigorously prove that it can handle with overwhelming probability all adversarial update patterns, using a combination of tail bound techniques, convex ordering theory, and queueing analysis.