NANOG Meeting Presentation Abstract

A Fresh Look At Scalable Forwarding Through Router FIB Caching
Meeting:	NANOG57
Date / Time:	2013-02-06 10:00am - 10:30am
Room:	Crystal Ballroom A-C
Presenters:	Speakers: Kaustubh Gadkari, Colorado State University Kaustubh Gadkari is a Ph.D. student in the Computer Science Department at Colorado State University. He received his Bachelor's in Engineering (Information Technology) from the University of Pune in 2006 and a Master's Degree in Computer Science from Colorado State University in 2010. His research interests lie in the field of network measurements and security. He is currently working with Dr. Dan Massey and Dr. Christos Papadopoulos and his research is about scaling the FIB on Internet routers.
Abstract:	The rate of growth of the global routing (RIBs) and forwarding tables (FIBs) has been increasing exponentially for the past several years. The growth of these is due to fac- tors such as multihoming, traffic engineering and prefix deaggregation. IPv6 and future architectures that route on name prefixes could lead to an even faster table growth. The FIB growth is a more pressing concern since FIBs are stored on fast but expensive card memory, costing thousand of dollars per GB. In this paper, we introduce a FIB caching system that in- troduces a novel hole filling algorith to overcome the cache hiding problem. We use LRU caching to substantially re- duce the number of FIB entries required to serve the entire routing table from the current 350K to 5K while achieving over 99% hit rates. We investigate trends over a period of four years and show that the required cache size remains virtually constant. For cache misses, we estimate the buffer requirements to hold packets while the new route is loaded into the cache and show that only a few hundred packets need to be buffered. Further, we investigate the robustness of our caching solution, where an adversary attempts to poison the cache. Finally, we investigate the impact of dynamic BGP updates on the performace of our caching solution.
Files:	A Fresh Look At Scalable Forwarding Through Router FIB Caching(PDF) A Fresh Look At Scalable Forwarding Through Router FIB Caching
Sponsors:	None.

Back to NANOG57 agenda.

NANOG57 Abstracts

• Show All

• DNS 101
  Speakers:
  John Kristoff, Team Cymru;

• Introduction to OpenFlow with Hands-On Exercises
  Speakers:
  Steve Wallace, Indiana University; Christopher SmallIndiana University; .
  

• Introduction to OpenFlow with Hands-On Exercises
  Speakers:
  Steve Wallace, Indiana University; Christopher SmallIndiana University; .
  

• There Are More Layers Than Just Layer 3...
  Speakers:
  Paul Ebersman, Infoblox;

• Optical Networking 101
  Speakers:
  Richard Steenbergen, GTT;

• Newcomers Lunch
  Speakers:
  Sponsor: Verisign .
  

• Keynote: ITU and the WCIT: Where We Are Now
  Speakers:
  Sally Wentworth, Internet Society;

• Super Storm Sandy: Infrastructure Impacts
  Moderators:
  Daniel Golding, Datacenter Insight; Panelists:
  Scott A. Davis, DuPont Fabros Technology; Michael Poleshuk, Equinix; Michael J. Parks, Datapipe; Neil Crowley, Internap;

• Super Storm Sandy: Infrastructure Impacts
  Moderators:
  Daniel Golding, Datacenter Insight; Panelists:
  Scott A. Davis, DuPont Fabros Technology; Michael Poleshuk, Equinix; Michael J. Parks, Datapipe; Neil Crowley, Internap;

• Super Storm Sandy: Infrastructure Impacts
  Moderators:
  Daniel Golding, Datacenter Insight; Panelists:
  Scott A. Davis, DuPont Fabros Technology; Michael Poleshuk, Equinix; Michael J. Parks, Datapipe; Neil Crowley, Internap;

• Super Storm Sandy: Infrastructure Impacts
  Moderators:
  Daniel Golding, Datacenter Insight; Panelists:
  Scott A. Davis, DuPont Fabros Technology; Michael Poleshuk, Equinix; Michael J. Parks, Datapipe; Neil Crowley, Internap;

• Super Storm Sandy: Infrastructure Impacts
  Moderators:
  Daniel Golding, Datacenter Insight; Panelists:
  Scott A. Davis, DuPont Fabros Technology; Michael Poleshuk, Equinix; Michael J. Parks, Datapipe; Neil Crowley, Internap;

• BCOP - Best Current Operational Practices
  Speakers:
  Chris GrundemannCableLabs; .
  

• 2012 Infrastructure Security Report
  Speakers:
  Gary Sockrider, Arbor Networks;

• Internet Impacts of Hurricane Sandy
  Moderators:
  Jim CowieRenesys; .
  Panelists:
  John HeidemannUSC/Information Sciences Institute; .
  Emile AbenRIPE NCC; .
  Patrick GilmoreAkamai; .
  Doug MadoryRenesys; .
  

• Internet Impacts of Hurricane Sandy
  Moderators:
  Jim CowieRenesys; .
  Panelists:
  John HeidemannUSC/Information Sciences Institute; .
  Emile AbenRIPE NCC; .
  Patrick GilmoreAkamai; .
  Doug MadoryRenesys; .
  

• Internet Impacts of Hurricane Sandy
  Moderators:
  Jim CowieRenesys; .
  Panelists:
  John HeidemannUSC/Information Sciences Institute; .
  Emile AbenRIPE NCC; .
  Patrick GilmoreAkamai; .
  Doug MadoryRenesys; .
  

• Internet Impacts of Hurricane Sandy
  Moderators:
  Jim CowieRenesys; .
  Panelists:
  John HeidemannUSC/Information Sciences Institute; .
  Emile AbenRIPE NCC; .
  Patrick GilmoreAkamai; .
  Doug MadoryRenesys; .
  

• Internet Impacts of Hurricane Sandy
  Moderators:
  Jim CowieRenesys; .
  Panelists:
  John HeidemannUSC/Information Sciences Institute; .
  Emile AbenRIPE NCC; .
  Patrick GilmoreAkamai; .
  Doug MadoryRenesys; .
  

• International Submarine Cable Development: New Infrastructure, New Prices?
  Speakers:
  Tim Stronge, TeleGeography;

• Measuring YouTube Quality of Experience for Users in Residential ISPs
  Speakers:
  Deep Medhi, University of Missouri-Kansas City;

• What's Up With Poor Performance Towards MAC Addresses Starting With 4 or 6?
  Speakers:
  Job Snijders, Atrato IP Networks; Jeff WheelerInconcepts; .
  

• What's Up With Poor Performance Towards MAC Addresses Starting With 4 or 6?
  Speakers:
  Job Snijders, Atrato IP Networks; Jeff WheelerInconcepts; .
  

• Topology Aware Blackbox Monitoring
  Speakers:
  Nicolas Guilbaud, Google; Ross Cartlidge, Google;

• Topology Aware Blackbox Monitoring
  Speakers:
  Nicolas Guilbaud, Google; Ross Cartlidge, Google;

• The Costs of IPv4-IPv6 Dual Stack
  Speakers:
  Lee Howard, Time Warner Cable;

• Network Operations Security
  Speakers:
  John Kristoff, Team Cymru;

• ARIN Public Policy Consultation
  Speakers:
  Paul AndersenARIN; .
  John SweetingARIN; .
  

• ARIN Public Policy Consultation
  Speakers:
  Paul AndersenARIN; .
  John SweetingARIN; .
  

• Building a Scalable Telemetry Collection Pipeline using Big-Data Approach
  Speakers:
  Petr Lapukhov, Microsoft;

• A Fresh Look At Scalable Forwarding Through Router FIB Caching
  Speakers:
  Kaustubh Gadkari, Colorado State University;

• Unified and Efficient Approach to Energy Management Across the Network
  Speakers:
  Brian Hedstrom, CableLabs;

• The BGP Visibility Scanner
  Speakers:
  Andra Lutu, Institute IMDEA Networks - UC3M;

• Advanced Cloud Network Services with SDN and BGP
  Speakers:
  Florin Balus, Nuage Networks;

• BIRD Update, Route Servers
  Speakers:
  Ondrej Filip, CZ.NIC/NIX.CZ;

• IPv6 Adoption
  Speakers:
  Michael Bailey, University of Michigan;

• ARIN Update
  Speakers:
  John Curran, ARIN;