1On Routing Table Growth

Abstract — The Internet has experienced explosive growth since its commercialization. The sizes of the rout-ing tables have increased by an order of magnitude over the past six years. This dramatic growth of the routing ta-ble can decrease the packet forwarding speed and demand more router memory space. In this paper, we explore the extent that various factors contribute to the routing table growth and predict the future rate of growth of the routing table. We first perform measurement study to determine the extent that factors such as multi-homing, failure to ag-gregate, load balancing, and address fragmentation con-tribute to routing table size, and find that only of prefixes are due to multi-homing, of prefixes are due to failure to aggregate, of prefixes are due to load balancing, and more than of prefixes are due to address fragmentation. This leads us to group all prefixes that are not aggregated due to either failure to aggregate or address fragmentation. We find that the number of pre-fix clusters is no more than of the number of prefixes. We explore the extent that load balancing contributes to the number of prefix clusters. Furthermore, we predict the growth pattern of prefixes and prefix clusters by observing power-laws on prefixes and prefix clusters. The number of prefixes grows much faster than the number of prefix clus-ters does. To the best of our knowledge, this is the first study on the explosive growth of routing tables by system-atically comparing factors that contribute to the growth and by observing routing table growth patterns. I