Packet Forwarding Technologies: 1st Edition (Hardback) book cover

Packet Forwarding Technologies

1st Edition

By Weidong Wu

Auerbach Publications

448 pages | 164 B/W Illus.

Purchasing Options:$ = USD
Hardback: 9780849380570
pub: 2007-12-17
SAVE ~$27.00
eBook (VitalSource) : 9780429074936
pub: 2007-12-17
from $37.48

FREE Standard Shipping!


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



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 


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


References appear at the end of each chapter.

About the Author

Weidong Wu received his PhD in electronics and information engineering from Huazhong University of Science and Technology, China. In 2006, he joined Wuhan University of Science and Technology. His research involves algorithms to improve Internet router performance, network management, network security, and traffi c engineering.

Subject Categories

BISAC Subject Codes/Headings:
COMPUTERS / Information Technology
COMPUTERS / Networking / General
TECHNOLOGY & ENGINEERING / Telecommunications
TECHNOLOGY & ENGINEERING / Mobile & Wireless Communications