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 constant Generalized Zipf distribution and (ii) temporal locality is predominantly determined by long-term popularity, we find that the scalability of the LISP cache is O(1) with respect to the amount of prefixes (Internet growth) and users (growth of the LISP site). We validate the model and discuss the accuracy of our assumptions using several one-day-long packet traces.
Recently, @cite_13 performed a measurement study within the operational confinement of an ISP's network and showed the feasibility of route caching. They show by means of an experimental evaluation that LRU cache eviction policy performs close to optimal and better than LFU. Also, they found that prefix popularity distribution is very skewed and that working-set size is generally stable with time. These are in line with our empirical findings and provide practical confirmation for our assumption that the popularity distribution can be described as a GZipf.
@cite_13
2141062513
Internet routers' forwarding tables (FIBs), which must be stored in expensive fast memory for high-speed packet forwarding, are growing quickly in size due to increased multihoming, finer-grained traffic engineering, and deployment of IPv6 and VPNs. To address this problem, several Internet architectures have been proposed to reduce FIB size by returning to the earlier approach of route caching : storing only the working set of popular routes in the FIB. This paper revisits route caching. We build upon previous work by studying flat, uni-class ( 24) prefix caching, with modern traffic traces from more than 60 routers in a tier-1 ISP. We first characterize routers' working sets and then evaluate route-caching performance under different cache replacement strategies and cache sizes. Surprisingly, despite the large number of deaggregated 24 subnets, caching uni-class prefixes can effectively curb the increase of FIB sizes. Moreover, uni-class prefixes substantially simplify a cache design by eliminating longest-prefix matching, enabling FIB design with slower memory technologies. Finally, by comparing our results with previous work, we show that the distribution of traffic across prefixes is becoming increasingly skewed, making route caching more appealing.