Putting routing tables in silicon
- 1 January 1992
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Network
- Vol. 6 (1) , 42-50
- https://doi.org/10.1109/65.120723
Abstract
Moving routing tables from RAM to custom or semicustom VLSI can lower cost and boost performance. The routing table problem is presented by discussing the available architectures and how they are related. It is shown that simple table lookup is just a special case of the standard trie structure and that the use of partitioning combined with the trie structure provides a continuum that can lead to a CAM implementation at one extreme. The high-level tradeoffs in the choice of various parameters for the trie are estimated. A careful choice of word size can balance the requirements for speed with the costs of area. Also considered are the costs and benefits of splitting the table into a number of tries, which are searched simultaneously. VLSI implementations are outlined, and the costs are compared. General CAM structures are not needed for the routing table application, and custom CAMs can be very efficient. Tries, however, can be competitive in many cases, due to the resources available for building conventional memories.Keywords
This publication has 9 references indexed in Scilit:
- ATM and its challenges to VLSIPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Improving gateway performance with a routing-table cachePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Network locality at the scale of processesPublished by Association for Computing Machinery (ACM) ,1991
- Design of an Integrated ServicesPacketNetworkIEEE Journal on Selected Areas in Communications, 1986
- Dynamic cross-coupled bitline content addressable memory cell for high density arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Analysis of a heuristic for full trie minimizationACM Transactions on Database Systems, 1981
- The Complexity of Trie Index ConstructionJournal of the ACM, 1977
- Compressed triesCommunications of the ACM, 1976
- Trie memoryCommunications of the ACM, 1960