TY - GEN
T1 - Revisiting route caching
T2 - 10th International Conference on Passive and Active Network Measurement, PAM 2009
AU - Kim, Changhoon
AU - Caesar, Matthew
AU - Gerber, Alexandre
AU - Rexford, Jennifer L.
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=67649971363&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=67649971363&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-00975-4_1
DO - 10.1007/978-3-642-00975-4_1
M3 - Conference contribution
AN - SCOPUS:67649971363
SN - 9783642009747
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 3
EP - 12
BT - Passive and Active Network Measurement - 10th International Conference, PAM 2009, Proceedings
Y2 - 1 April 2009 through 3 April 2009
ER -