E-Book, Englisch, 448 Seiten
Wu Packet Forwarding Technologies
Erscheinungsjahr 2007
ISBN: 978-0-8493-8058-7
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)
E-Book, Englisch, 448 Seiten
ISBN: 978-0-8493-8058-7
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)
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.
Zielgruppe
Engineers involved in IP networks and router design and from network equipment and service providers; senior undergraduate and graduate students of electrical and computer engineering and computer science.
Autoren/Hrsg.
Fachgebiete
Weitere Infos & Material
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.
