URL: http://www.isi.edu/~johnh/PAPERS/Chang01a.html
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.58.3875 Entry Date: 2002-12-23 Abstract: Anecdotal evidence suggests that misconfiguration of backbone routers occasionally leads to an injection of large routing tables into the BGP routing system. In this paper, we investigate the detailed mechanics of router response to large BGP routing tables. We examine three commercial routers, and find that their responses vary significantly. Some routers exhibit table-size oscillations that have the potential to cause cascading failure. Others need operator intervention to recover from large routing tables. We also find that deployed resource control mechanisms, such as prefix limits and route flap damping, are only partially successful in mitigating the impact of large routing tables. Experiments: Three different commercial BGP routers were placed in simple topologies. The behaviour of individual routers under large router load was measured. In addition, the effect on other routers in the topology was measured. The routers measured were Cisco 7000 (IOS 11.1), Cisco 12008 GSR (IOS 12.0) and Juniper M20 (JUNOS 4.3 and 4.4). Results: The authors pose the following question:

How do routers from different vendors behave when confronted with routing table loads that exceed their capacity?

Their findings are:

• When confronted with a large routing table, some commercial routers disable interfaces or BGP peering until manual intervention.
• Other commercial routers repeatedly exhibit the following sequence: "malloc failure", resetting, and re-establishing BGP peering. The result is an oscillation of routing table size.
• A "malloc failure" may cascade from one router to other routers, depending on certain (relative) properties of the routers.
• None of the routers studied exhibit packet forwarding delays or drops under a large routing table load, except when flushing the forwarding table during a reset.
• Prefix limiting and route flap damping are only partially successful in mitigating the impact of large routing tables.

Previous studies of this nature focused on inter-domain routing. The authors claim that this is the first research that addresses these questions for BGP.

Finally, the authors list a number of goals for designing a graceful failure mode of a BGP router. References:

• C. Labovitz, G. R. Malan, and F. Jahanian, "Origins of internet routing instability," Proceedings of the IEEE INFOCOMM, 1999.
• C. Labovitz, G. R. Malan, and F. Jahanian, "Internet routing instability," Proceedings of the ACM SIGCOMM, 1997.
• A. Shaikh and L. Kalampoukas and R. Dube and A. Varma, "Routing stability in congested networks: Experimentation and analysis," Proceedings of the ACM SIGCOMM, 2000.