On the scalability of LISP mappings caches

The Locator/ID Separation Protocol (LISP) limits the growth of the Default-Free Zone routing tables by creating a highly aggregatable and quasi-static Internet core. However, LISP pushes the forwarding state to edge routers whose timely operation relies on caching of location to identity bindings. In this paper we develop an analytical model to study the asymptotic scalability of the LISP cache. Under the assumptions that (i) long-term popularity can be modeled as a Generalized Zipf distribution, independent of Internet and LISP site growth and (ii) temporal locality is predominantly determined by long-term popularity, we find that LISP cache miss rate scales O(1) with respect to the amount of prefixes (Internet growth) and users (LISP site growth). We validate the model and discuss the accuracy of our assumptions using several one-day-long packet traces.