Performance enhancement of IP forwarding by reducing routing table construction time

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