Packet Forwarding Technologies

Published:
December 17, 2007 by Auerbach Publications - 448 Pages
Author(s):
Weidong Wu, Wuhan University of Science and Technology, China

Purchasing Options

Hardback
$104.95
Add to cart
ISBN 9780849380570
Cat# AU8057
 

Features

  • Includes basic packet forwarding concepts and contemporary implementation technologies in one detailed, comprehensive source
  • Presents numerous simulation results for comparing the performance between algorithms
  • Describes the characteristics of a routing table, which is the fundamental database used for IP address lookup
  • Explores recent developments in the field, including a pipelined application-specific integrated circuit (ASIC) architecture, a dynamic data structure for a bursty access pattern, advanced caching techniques, and improved hash schemes
  • Examines the forwarding engine based on ternary content addressable memory (TCAM) and partitioning techniques based on the properties of a forwarding table

    • Summary

    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.

    Table of Contents

    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.

    Related Titles