Secure Cache Provision: Provable DDOS Prevention for Randomly Partitioned Services with Replication

In this paper we show a small but fast popularity-based front-end cache can provide provable DDOS prevention for randomly partitioned cluster services with replication. To achieve this, we first give the best strategy for an adversary to overload the system, and then prove that the cache size is lower bounded by O(n log log n/ log d), where n is the number of back-end nodes and d is the replication factor. Since log log n/ log d <; 2 holds for almost all the current clusters (i.e., the number of back-end nodes n <; 10⁵ and the replication factor d ≥ 3), this result implies an O(n) lower bound on the required cache size. Our analysis and results are well validated through extensive simulations.