^ Top

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
This item is webcast
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: pdfA Fresh Look At Scalable Forwarding Through Router FIB Caching(PDF)
youtubeA Fresh Look At Scalable Forwarding Through Router FIB Caching
Sponsors: None.

Back to NANOG57 agenda.

NANOG57 Abstracts

  • DNS 101
    Speakers:
    John Kristoff, Team Cymru;
  • 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;
  • 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; .

 

^ Back to Top