Packet Forwarding Technologies

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 The Concept of Routers Basic Functionalities of Router Evolution of Router Architecture The Key Components of a Router Concept of IP Address Lookup and Routing Table IP Address, Prefix, and Routing Table The Concept of IP Address Lookup Matching Techniques Design Criteria and Performance Requirement Difficulty of the Longest Prefix Matching Problem Characteristics of a Routing Table Constructing Optimal Routing Table Classic Schemes Linear Search Caching Binary Trie Path-Compressed Trie Dynamic Prefix Trie Multibit Trie Level Compression Trie Controlled Prefix Expansion Lulea Algorithm Elevator Algorithm Block Trees Multibit Tries in Hardware Pipelined Multibit Trie Fast Incremental Updates for the Pipelined Fixed-Stride Trie Two-Phase Algorithm Pipelined Variable-Stride Multibit Tries The EfficientData Structure for Bursty Access Pattern The Table-Driven Scheme Near-Optimal Scheme with Bounded Worst Case Performance Dynamic Biased Skip List The Collection of Trees for a Bursty Access Pattern The Caching Technologies Suez’s Lookup Algorithm Prefix Caching Schemes Multizone Caches Cache-Oriented Multistage Structure Hashing Schemes Binary Search on Hash Tables Parallel Hashing in Prefix Length Multiple Hashing Schemes Using Bloom Filter TCAM-Based Forwarding Engine Content Address Memory Efficient Updating on the Ordered TCAM Techniques to Eliminate Sorting Power-Efficient TCAM A Distributed TCAM Architecture Routing Table Partitioning Technologies Prefix and Interval Partitioning Port-Based Partitioning ROT Partitioning Comb Extraction Scheme INDEX References appear at the end of each chapter.