Using forgetful routing to control BGP table size

Elliott Karpilovsky, Jennifer L. Rexford

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations


Running the Border Gateway Protocol (BGP), the Internet's interdomain routing protocol, consumes a large amount of memory. A BGP-speaking router typically stores one or more routes, each with multiple attributes, for more than 170,000 address blocks, and growing. When the router does not have enough memory to store a new route, it may crash or enter into other unspecified behavior, causing serious dis- ruptions for the data traffic. In this paper, we propose a new mechanism for routers to handle memory limitations with- out modifying the underlying routing protocol and without negatively affecting convergence delay. Upon running out of memory, the router simply discards information about some alternate routes, and requests a quot;refresh" from its neighbors later if necessary. We present an optimal offline algorithm for deciding which alternate routes to evict, and explore the trade-off between memory size and refresh overhead using a large BGP message trace. Based on these promising re- sults, we design and evaluate efficient online algorithms that achieve most of the performance benefits. We believe that our scheme can significantly improve the scalability and ro- bustness of IP routers in the future.

Original languageEnglish (US)
Title of host publicationProceedings of CoNEXT'06 - 2nd Conference on Future Networking Technologies
StatePublished - 2006
Event2nd Conference on Future Networking Technologies, CoNEXT'06 - Lisboa, Portugal
Duration: Dec 4 2006Dec 7 2006

Publication series

NameProceedings of CoNEXT'06 - 2nd Conference on Future Networking Technologies


Other2nd Conference on Future Networking Technologies, CoNEXT'06

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Computer Science Applications
  • Electrical and Electronic Engineering


  • Communication networks
  • Performance optimization
  • Workload characterization


Dive into the research topics of 'Using forgetful routing to control BGP table size'. Together they form a unique fingerprint.

Cite this