ModelGraft: Accurate, Scalable, and Flexible Performance Evaluation of General Cache Networks
- 1 September 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 01, 304-312
Abstract
Large scale deployments of general cache networks, such as Content Delivery Networks or Information Centric Networking architectures, arise new challenges regarding their performance evaluation for network planning. On the one hand, analytical models can hardly represent in details all the interactions of complex replacement, replication, and routing policies on arbitrary topologies. On the other hand, the sheer size of networks and content catalogs makes event-driven simulation techniques inherently non-scalable. We propose a new technique for the performance evaluation of large-scale caching systems that intelligently integrates elements of 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 mapped to a simpler equivalent scenario that builds upon Time-To-Live (TTL) caches, it (ii) significantly downscales the scenario to lower computation and memory complexity, while, at the same time, preserving its properties to limit accuracy loss, finally, it (iii) is simple to use and robust, as it autonomously converges to a consistent state through a feedback-loop control system, regardless of the initial state. Performance evaluation shows that, with respect to classic event-driven simulation, ModelGraft gains over two orders of magnitude in both CPU time and memory complexity, while limiting accuracy loss below 2%. In addition, we show that ModelGraft extends performance evaluation well beyond the boundaries of classic approaches, by enabling study of Internet-scale scenarios with content catalogs comprising hundreds of billions objects.Keywords
This publication has 25 references indexed in Scilit:
- Performance evaluation of hierarchical TTL-based cache networksComputer Networks, 2014
- A Survey of Information-Centric Networking ResearchIEEE Communications Surveys & Tutorials, 2013
- The LCD interconnection of LRU caches and its analysisPerformance Evaluation, 2006
- Scalable fluid models and simulations for large-scale IP networksACM Transactions on Modeling and Computer Simulation, 2004
- Fluid-based analysis of a network of AQM routers supporting TCP flows with an application to REDACM SIGCOMM Computer Communication Review, 2000
- A unified framework for hybrid control: model and optimal control theoryIEEE Transactions on Automatic Control, 1998
- Rejection-inversion to generate variates from monotone discrete distributionsACM Transactions on Modeling and Computer Simulation, 1996
- Complete computer system simulation: the SimOS approachIEEE Parallel & Distributed Technology: Systems & Applications, 1995
- An approximate analysis of the LRU and FIFO buffer replacement schemesACM SIGMETRICS Performance Evaluation Review, 1990
- A cryptanalytic time-memory trade-offIEEE Transactions on Information Theory, 1980