Efficient FIB Caching using Non-overlapping Prefixes

3/6 Department Seminar

Yaoqing Liu
Ph.D candidate in Compuer Science at the University of Memphis

3:00 p.m., March 6, 2013
235 Weir Hall

Title: Efficient FIB Caching using Non-overlapping Prefixes

Abstract:
The size of the global Routing Information Base (RIB) has been increasing at an alarming rate. This directly leads to the rapid growth of the global Forwarding Information Base (FIB) size, which raises serious concerns for ISPs as the FIB memory in line cards is much more expensive than regular memory modules and it is very costly to increase this memory capacity frequently for all the routers in an ISP. One potential solution is to install only the most popular FIB entries into the fast memory (i.e., a FIB cache), while storing the complete FIB in slow memory. In this work, we propose an effective FIB caching scheme that achieves a considerably higher hit ratio than previous approaches while preventing the cache-hiding problem. Our experimental results show that with only 20K prefixes in the cache (5.36% of the actual FIB size), the hit ratio of our scheme is higher than 99.95%. Our scheme can also handle cache misses, cache replacement and routing updates efficiently.

Bio:
Yaoqing Liu is a fifth-year PhD student in the Computer Science Department at The University of Memphis. His research interests include Networked Systems (Routing, Security, Algorithm, Measurement and Protocol), Future Internet Architecture, and Software Defined Networking. He has three years' software engineering working experience before joining the PhD program. His publications have appeared in top-ranked conferences and journals such as INFOCOM, JSAC and ACM SIGCOMM CCR. Also he was the primary inventor of one filed provisional patent (https://umdrive.memphis.edu/yliu6/web/YaoqingLiu.html).