Elliott Karpilovsky will present his preFPO on Tuesday November 11 at 3PM in Room 402. The members of his committee are: Jennifer Rexford, advisor; Larry Peterson and Aman Shaikh (AT&T), readers; Vivek Pai and Mike Freedman, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ----------------------------------- Title: "Reducing Memory Requirements for Routing Protocols" Abstract: With the rapid growth of the Internet, routers need more and more memory to forward packets to their correct destinations. Lack of sufficient memory can cause routers to crash, reject new routing information, or enter into indeterminate state, as current protocols and systems do not deal gracefully with memory exhaustion. Current "solutions" are often ineffective, as they typically rely on over-provisioning memory (an expensive and sometimes infeasible solution), or in restricting the set of routes that can be learned (and such restrictions must be very loose, to ensure routers have alternate paths to use in the event of a failure). Our study measures the deployment of routing protocols, along with the burdens they impose on routers. We evaluate two different ways to reduce router memory requirements, and additionally investigate how router memory requirements might change in the future, due to emerging protocols. First, we examine how to compress the Routing Information Base (RIB), a data structure routers use to store information about all possible paths, using Forgetful Routing. In our work, we explore a space-time trade-off and demonstrate how RIB memory can be reduced by a factor of 3 or more. Second, we reduce the size of the Forwarding Information Base (FIB), a different router data structure used for forwarding packets, with a Memory Management System. We demonstrate how to optimally compress the FIB without changing forwarding behavior, as well as how forwarding behavior can be slightly perturbed to reduce memory usage up to a factor of 3. Finally, we examine the growth trends of new protocols such as IPv6 and multicast which are rapidly emerging and expect to become widespread; 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 such as IPTV. By measuring these protocols, we better understand where they are headed, and thus better understand future routing requirements.