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.