I. Introduction
The DEPLOYMENT of the BGP routing protocol has sustained tremendous growth over the last couple of decades, and it is arguably one of the main technological reasons behind the Internet's success. Lately, however, there are significant concerns about the scalability of BGP interdomain routing. These concerns focus either on the growing routing table size (number of routable prefixes) or on BGP dynamics and instability (also known as “churn”) [17]. Both factors are important, especially for routers at the core of the Internet. The growing size of the routing table requires increasingly larger fast memory, but it does not necessarily slow down packet forwarding as long as address lookups are performed using TCAMs or constant-time longest-prefix matching algorithms [26].