A Chip for a Routing Table Based on a Novel Modified Trie Algorithm

[摘要] The design for a routing table circuit for Ethernet-, IP- and ATM-applications ispresented. Starting point for the design was an object-oriented general behavior of therouting table. The selected data structure for the routing table is based on amodificationof the structure denominatedtrie, saving one search level and memory space. Thearchitecture for searching and sorting of data, implemented in hardware, is explained.Thismodified triestores 64 K addresses and the associated data, achieving a highperformance too. The circuit, which can support a flow of 500000 frames/s, is connectedto the PCI Bus. For the implementation a FLEX10K100 from Altera Company wasused.

[学科分类] 电子、光学、磁材料