[talks] E Karpilovsky preFPO

[Melissa Lawson]

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.