Performance enhancement of IP forwarding by reducing routing table construction time

Abstract

In previous work, Lampson et al, proposed an IP lookup algorithm which performs binary search on prefixes (BSP) [3], The algorithm is attractive for IPv6 because of its bounded worst-case memory requirement. Although for the sake of fast forwarding, the cost paid for the slowing down insertion is reasonable, the performance of routing-table reconstruction in BGP is too time-consuming to handle the frequent route updates. In this letter, we propose a fast forwarding-table construction algorithm which can handle more than 3600 route updates per second, Moreover, it is simple enough to fulfill the need of fast packet forwarding.