Fast incremental updates for pipelined forwarding engines

Pipelined ASIC architectures are increasingly being used in forwarding engines for high-speed IP routers. We explore optimization issues in the design of memory-efficient data structures that support fast incremental updates in such forwarding engines. Our solution aims to balance the memory utilization across the multiple pipeline stages. We also propose a series of optimizations that minimize the disruption to the forwarding process caused by route updates. These optimizations reduce the update overheads by over a factor of two for a variety of different core routing tables and update traces.