Reducing Memory Requirements for Routing Protocols (thesis)

Abstract:

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.