Efficient IP forwarding engine with incremental update

Shuo Cheng Hu, Chia Tai Chan, Hung Yi Chang, Pi Chung Wang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Nowadays, the commonly used table lookup scheme for IP routing is based on the so-called classless interdomain routing (CIDR). With CIDR, routers must find out the best matching prefix (BMP) for IP packets forwarding, which complicates the IP lookup. Since the IP lookup performance is a major design issue for the new generation routers, in this article we investigate the properties of the routing table and present a new IP lookup scheme. By using the proposed scheme, the size of the forwarding table can be compressed to 360 Kbytes for a large routing table with 58 000 routing entries. The data structure for the incremental update is also introduced by adding 40% storage. The new data structure, could accomplish a single route update within 100 ns. Even where route flaps impede lookup performance, the performance degrades by only 0.05% with 4000 route updates per second. Furthermore, this scheme is IPv6 scalable.

Original languageEnglish
Pages (from-to)223-232
Number of pages10
JournalJournal of High Speed Networks
Issue number3
StatePublished - Aug 2004


  • Internet
  • Routing lookup
  • Routing-table


Dive into the research topics of 'Efficient IP forwarding engine with incremental update'. Together they form a unique fingerprint.

Cite this