Reducing memory requirements for routing protocols

2009 2009

Other formats: Order a copy

Abstract (summary)

Due to the rapid growth of the Internet, routers require increasing amounts of memory to forward packets to their destinations. Lack of sufficient memory can cause routers to crash, reject new routing information, or enter into an indeterminate state, as current protocols and systems do not deal gracefully with memory exhaustion. Current “solutions” are often ineffective. Techniques such as over-provisioning memory are expensive, since networks may have thousands of routers needing upgrades; moreover, over-provisioning may be infeasible in cases where the routers are not physically accessible (e.g., routers on satellites). Other methods, such as restricting the set of routes that can be learned, are impractical; such restrictions must be loose to allow sufficient connectivity to other domains (which may be needed when primary routes fail and backup routes are required). Moreover, routers typically have two different memory structures that are at risk of overflow: a Routing Information Base (RIB) for tracking available paths, and a Forwarding Information Base (FIB) for moving packets toward their destinations.

Our study measures the deployment and characteristics of routing protocols and proposes new mechanisms to curtail associated burden. We design two different ways to reduce the two different router memory requirements, and additionally investigate how router memory requirements might change in the future, due to emerging protocols. First, we examine how to reduce RIB table size in our work known as Forgetful Routing. We explore a space-time trade-off between memory needed to store the RIB and time needed to compute a forwarding path from among all possible paths. We demonstrate how RIB memory can potentially be reduced by a factor of 3 or more. Second, we reduce the size of the FIB with a Memory Management System (MMS). The MMS can modify routing behavior such that memory is saved without introducing aberrant behavior ( i.e., without routing loops). The Memory Management System allows operators to adjust forwarding behavior in a controlled manner. The system can also operate in a transparent mode, where no forwarding behavior is changed but memory is still reduced. The MMS can reduce memory usage up to a factor of 3. Finally, we examine the growth trends of emerging protocols such as IPv6 and multicast; IPv6 is being deployed to solve the address shortage problem, and multicast’s one-to-many model has become a popular means to distribute content to many receivers, such as with IPTV. By measuring these protocols, we better understand where they are headed, and thus better understand future routing requirements.

Indexing (details)

Computer science
0984: Computer science
Identifier / keyword
Applied sciences; Memory management; Router crashes; Router memory; Routing protocols
Reducing memory requirements for routing protocols
Karpilovsky, Elliott M.
Number of pages
Publication year
Degree date
School code
DAI-B 70/09, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
Rexford, Jennifer
Princeton University
University location
United States -- New Jersey
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.