ModelGraft: Accurate, Scalable, and Flexible Performance Evaluation of General Cache Networks

Large scale deployments of general cache networks,such as Content Delivery Networks or Information CentricNetworking architectures, arise new challenges regarding theirperformance evaluation for network planning. On the one hand,analytical models can hardly represent in details all the interactions of complex replacement, replication, and routing policieson arbitrary topologies. On the other hand, the sheer size ofnetworks and content catalogs makes event-driven simulationtechniques inherently non-scalable.We propose a new technique for the performance evaluation oflarge-scale caching systems that intelligently integrates elementsof stochastic analysis within a MonteCarlo simulative approach,that we colloquially refer to as ModelGraft. Our approach (i)leverages the intuition that complex scenarios can be mappedto a simpler equivalent scenario that builds upon Time-To-Live(TTL) caches; it (ii) significantly downscales the scenario tolower computation and memory complexity, while, at the sametime, preserving its properties to limit accuracy loss; finally, it(iii) is simple to use and robust, as it autonomously convergesto a consistent state through a feedback-loop control system,regardless of the initial state.Performance evaluation shows that, with respect to classicevent-driven simulation, ModelGraft gains over two orders ofmagnitude in both CPU time and memory complexity, whilelimiting accuracy loss below 2%. In addition, we show thatModelGraft extends performance evaluation well beyond theboundaries of classic approaches, by enabling study of Internet-scale scenarios with content catalogs comprising hundreds ofbillions objects