As Internet traffic continues to grow exponentially, there is a great need to build Internet protocol (IP) routers with high-speed and high-capacity packet networking capabilities. The first book to explore this subject, Packet Forwarding Technologies explains in depth packet forwarding concepts and implementation technologies. It covers the data structures, algorithms, and architectures used to implement high-speed routers.
Following an introduction to the architecture of IP routers, the author discusses how IP address lookup is one of the major bottlenecks in high-performance routers. He describes the characteristics of a routing table and addresses the difficulty of the longest-matching prefix search. The remainder of the book deals with fast IP address lookup. Coverage includes the various available architectures, data structures, and algorithms based on software and hardware as well as detailed discussions on state-of-the-art innovations.
With many illustrations, tables, and simulations, this practical guide to packet forwarding technologies facilitates understanding of IP routers and the latest router designs.
Preface. Introduction. Concept of IP Address Lookup and Routing Table. Classic Schemes. Multibit Trie. Pipeline Multibit Scheme. The Efficient Data Structure for Bursty Access Pattern. The Caching Technologies. Hashing Schemes. TCAM-Based Forwarding Engine. Routing Table Partitioning Technologies.