Atjaunināt sīkdatņu piekrišanu

E-grāmata: Packet Forwarding Technologies

  • Formāts: 448 pages
  • Izdošanas datums: 17-Dec-2007
  • Izdevniecība: Auerbach
  • Valoda: eng
  • ISBN-13: 9781000654004
Citas grāmatas par šo tēmu:
  • Formāts - EPUB+DRM
  • Cena: 70,13 €*
  • * ši ir gala cena, t.i., netiek piemērotas nekādas papildus atlaides
  • Ielikt grozā
  • Pievienot vēlmju sarakstam
  • Šī e-grāmata paredzēta tikai personīgai lietošanai. E-grāmatas nav iespējams atgriezt un nauda par iegādātajām e-grāmatām netiek atmaksāta.
Packet Forwarding TechnologiesPalielināt
  • Formāts: 448 pages
  • Izdošanas datums: 17-Dec-2007
  • Izdevniecība: Auerbach
  • Valoda: eng
  • ISBN-13: 9781000654004
Citas grāmatas par šo tēmu:

DRM restrictions

  • Kopēšana (kopēt/ievietot):

    nav atļauts

  • Drukāšana:

    nav atļauts

  • Lietošana:

    Digitālo tiesību pārvaldība (Digital Rights Management (DRM))
    Izdevējs ir piegādājis šo grāmatu šifrētā veidā, kas nozīmē, ka jums ir jāinstalē bezmaksas programmatūra, lai to atbloķētu un lasītu. Lai lasītu šo e-grāmatu, jums ir jāizveido Adobe ID. Vairāk informācijas šeit. E-grāmatu var lasīt un lejupielādēt līdz 6 ierīcēm (vienam lietotājam ar vienu un to pašu Adobe ID).

    Nepieciešamā programmatūra
    Lai lasītu šo e-grāmatu mobilajā ierīcē (tālrunī vai planšetdatorā), jums būs jāinstalē šī bezmaksas lietotne: PocketBook Reader (iOS / Android)

    Lai lejupielādētu un lasītu šo e-grāmatu datorā vai Mac datorā, jums ir nepieciešamid Adobe Digital Editions (šī ir bezmaksas lietotne, kas īpaši izstrādāta e-grāmatām. Tā nav tas pats, kas Adobe Reader, kas, iespējams, jau ir jūsu datorā.)

    Jūs nevarat lasīt šo e-grāmatu, izmantojot Amazon Kindle.

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 xiii
Acknowledgments xv
About the Author xvii
Introduction
1(30)
Introduction
1(1)
Concept of Routers
2(1)
Basic Functionalities of Routers
2(5)
Route Processing
2(2)
Packet Forwarding
4(1)
Router Special Services
5(2)
Evolution of Router Architecture
7(7)
First Generation---Bus-Based Router Architectures with Single Processor
7(1)
Second Generation---Bus-Based Router Architectures with Multiple Processors
8(1)
Architectures with Route Caching
8(1)
Architectures with Multiple Parallel Forwarding Engines
9(2)
Third Generation---Switch Fabric-Based Router Architecture
11(1)
Fourth Generation---Scaling Router Architecture Using Optics
12(2)
Key Components of a Router
14(17)
Linecard
14(1)
Transponder/Transceiver
14(1)
Framer
14(1)
Network Processor
15(1)
Traffic Manager
15(1)
CPU
16(1)
Network Processor (NP)
16(3)
Switch Fabric
19(1)
Shared Medium Switch
19(1)
Shared Memory Switch Fabric
20(1)
Distributed Output Buffered Switch Fabric
21(1)
Crossbar Switch
22(3)
Space-Time Division Switch
25(2)
IP-Address Lookup: A Bottleneck
27(1)
References
27(4)
Concept of IP-Address Lookup and Routing Table
31(38)
IP Address, Prefix, and Routing Table
31(1)
Concept of IP-Address Lookup
32(1)
Matching Techniques
33(3)
Design Criteria and Performance Requirement
34(2)
Difficulty of the Longest-Prefix Matching Problem
36(3)
Comparisons with ATM Address and Phone Number
36(1)
Internet Addressing Architecture
36(3)
Routing Table Characteristics
39(13)
Routing Table Structure
40(1)
Routing Table Growth
41(2)
Impact of Address Allocation on Routing Table
43(1)
Migration of Address Allocation Policy
44(1)
Impact of Address Allocations on Routing Table Size
45(1)
Impact of Address Allocation on Prefixes with 24-Bit Length
46(1)
Contributions to Routing Table Growth
46(2)
Multi-Homing
48(1)
Failure to Aggregate
48(1)
Load Balancing
49(1)
Address Fragmentation
50(1)
Route Update
50(2)
Constructing Optimal Routing Tables
52(17)
Filtering Based on Address Allocation Policies
52(1)
Three Filtering Rules
52(2)
Performance Evaluation
54(1)
Minimization of the Routing Table with Address Reassignments
55(1)
Case of a Single IP Routing Table
56(3)
General Case
59(4)
Optimal Routing Table Constructor
63(1)
Description of the Algorithm
63(3)
Improvements
66(1)
Experiments and Results
67(1)
References
68(1)
Classic Schemes
69(38)
Linear Search
69(1)
Caching
69(20)
Management Policies
70(1)
Cache Modeling
70(1)
Trace Generation
71(1)
Measurement Results
72(7)
Caching Cost Analysis
79(1)
Characteristics of Destination Address Locality
80(1)
Locality: Concepts
80(1)
Cache Replacement Algorithms
81(2)
Stack Reference Frequency
83(3)
Analysis of Noninteractive Traffic
86(1)
Cache Design Issues
87(2)
Discussions
89(1)
Binary Trie
89(2)
Path-Compressed Trie
91(1)
Dynamic Prefix Trie
92(15)
Definition and Data Structure
93(2)
Properties of DP-Tries
95(2)
Algorithms for DP-Tries
97(1)
Insertion
97(5)
Deletion
102(2)
Search
104(1)
Performance
105(1)
References
105(2)
Multibit Tries
107(58)
Level Compression Trie
107(6)
Level Compression
107(2)
Representation of LC-Tries
109(2)
Building LC-Tries
111(1)
Experiments
112(1)
Modified LC-Tries
113(1)
Controlled Prefix Expansion
113(10)
Prefix Expansion
114(1)
Constructing Multibit Tries
115(1)
Efficient Fixed-Stride Tries
116(2)
Variable-Stride Tries
118(5)
Lulea Algorithms
123(5)
Level 1 of the Data Structure
124(3)
Levels 2 and 3 of the Data Structure
127(1)
Growth Limitations in the Current Design
128(1)
Performance
128(1)
Elevator Algorithm
128(10)
Elevator-Stairs Algorithm
129(3)
log W-Elevators Algorithm
132(4)
Experiments
136(2)
Block Trees
138(11)
Construction of Block Trees
138(2)
Lookup
140(2)
Updates
142(1)
Stockpiling
143(2)
Worst-Case Performance
145(3)
Experiments
148(1)
Multibit Tries in Hardware
149(16)
Stanford Hardware Trie
149(1)
Tree Bitmap
150(4)
Tree Bitmap Optimizations
154(3)
Hardware Reference Design
157(5)
References
162(3)
Pipelined Multibit Tries
165(40)
Fast Incremental Updates for the Pipelined Fixed-Stride Tries
165(20)
Pipelined Lookups Using Tries
165(2)
Forwarding Engine Model and Assumption
167(2)
Routing Table and Route Update Characteristics
169(1)
Constructing Pipelined Fixed-Stride Tries
170(7)
Reducing Write Bubbles
177(1)
Separating Out Updates to Short Routes
177(1)
Node Pullups
178(2)
Eliminating Excess Writes
180(1)
Caching Deleted SubTrees
181(3)
Summary and Discussion
184(1)
Two-Phase Algorithm
185(13)
Problem Statements
186(1)
Computing MMS(W-1, k)
186(4)
Computing T(W-1, k)
190(2)
Faster Two-Phase Algorithm for k = 2, 3
192(2)
Partitioning Scheme
194(1)
Experimental Results
195(3)
Pipelined Variable-Stride Multibit Tries
198(7)
Construction of Optimal PVST
199(1)
Mapping onto a Pipeline Architecture
200(2)
Experimental Results
202(2)
References
204(1)
Efficient Data Structures for Bursty Access Patterns
205(32)
Table-Driven Schemes
205(6)
Table-Driven Models
205(2)
Dynamic Programming Algorithm
207(2)
Lagrange Approximation Algorithm
209(2)
Near-Optimal Scheme with Bounded Worst-Case Performance
211(6)
Definition
211(2)
Algorithm MINDPQ
213(3)
Depth-Constrained Weight Balanced Tree
216(1)
Simulation
217(1)
Dynamic Biased Skip List
217(8)
Regular Skip List
218(1)
Biased Skip List
219(1)
Data Structure
219(1)
Search Algorithm
220(1)
Dynamic BSL
221(1)
Constructing Data Structure
221(1)
Dynamic Self-Adjustment
222(1)
Lazy Updating Scheme
223(1)
Experimental Results
224(1)
Collection of Trees for Bursty Access Patterns
225(12)
Prefix and Range
225(1)
Collection of Red-Black Trees (CRBT)
226(1)
Biased Skip Lists with Prefix Trees (BSLPT)
227(2)
Collection of Splay Trees
229(1)
Experiments
230(4)
References
234(3)
Caching Technologies
237(38)
Suez Lookup Algorithm
237(11)
Host Address Cache
237(1)
HAC Architecture
237(3)
Network Address Routing Table
240(2)
Simulations
242(1)
Host Address Range Cache
243(1)
Intelligent HARC
244(1)
Index Bit Selection
244(2)
Comparisons between IHARC and HARC
246(2)
Selective Cache Invalidation
248(1)
Prefix Caching Schemes
248(8)
Liu's Scheme
249(1)
Prefix Cache
249(1)
Prefix Memory
250(1)
Experiments
251(1)
Reverse Routing Cache (RRC)
252(1)
RRC Structure
252(1)
Handling Parent Prefixes
252(1)
Updating RRC
253(2)
Performance Evaluation
255(1)
Multi-Zone Caches
256(10)
Two-Zone Full Address Cache
256(1)
Multi-Zone Pipelined Cache
257(1)
Architecture of MPC
257(1)
Search in MPC
258(1)
Outstanding Miss Buffer
258(2)
Lookup Table Transformation
260(1)
Performance Evaluation
261(1)
Design Method of Multi-Zone Cache
261(1)
Design Model
262(2)
Two-Zone Design
264(1)
Optimization Tableau
265(1)
Cache-Oriented Multistage Structure
266(9)
Bi-Directional Multistage Interconnection
267(1)
COMS Operations
267(2)
Cache Management
269(1)
Details of SEs
270(1)
Routing Table Partitioning
271(1)
References
272(3)
Hashing Schemes
275(42)
Binary Search on Hash Tables
275(12)
Linear Search of Hash Tables
275(1)
Binary Search of Hash Tables
276(1)
Precomputation to Avoid Backtracking
277(1)
Refinements to Basic Scheme
278(1)
Asymmetric Binary Search
278(3)
Mutating Binary Search
281(5)
Performance Evaluation
286(1)
Parallel Hashing in Prefix Length
287(3)
Parallel Architecture
287(1)
Simulation
288(2)
Multiple Hashing Schemes
290(7)
Multiple Hash Function
290(2)
Multiple Hashing Using Cyclic Redundancy Code
292(2)
Data Structure
294(1)
Searching Algorithms
295(1)
Update and Expansion to IPv6
295(2)
Performance Comparison
297(1)
Using Bloom Filter
297(20)
Standard Bloom Filter
297(2)
Counting Bloom Filter
299(1)
Basic Configuration of LPM Using Bloom Filter
299(2)
Optimization
301(1)
Asymmetric Bloom Filters
302(2)
Direct Lookup Array
304(1)
Reducing the Number of Filters
305(2)
Fast Hash Table Using Extended Bloom Filter
307(1)
Basic Fast Hash Table
307(2)
Pruned Fast Hash Table
309(3)
Shared-Node Fast Hash Table
312(2)
References
314(3)
TCAM-Based Forwarding Engine
317(54)
Content-Address Memory
317(4)
Basic Architectural Elements
317(2)
Binary versus Ternary CAMs
319(1)
Longest-Prefix Match Using TCAM
320(1)
Efficient Updating on the Ordered TCAM
321(4)
Algorithm for the Prefix-Length Ordering Constraint
321(1)
Algorithm for the Chain-Ancestor Ordering Constraint (CAO_OPT)
322(1)
Level-Partitioning Technology
322(3)
VLMP Technique to Eliminate Sorting
325(3)
VLMP Forwarding Engine Architecture
325(2)
Search Algorithm
327(1)
First Stage
327(1)
Second Stage
327(1)
Performance of VLMP Architecture
327(1)
Power-Efficient TCAM
328(28)
Pruned Search and Paged-TCAM
329(1)
Pruned Search
329(1)
Paged TCAM
330(1)
Heuristic Partition Techniques
331(1)
Bit-Selection Architecture
331(3)
Trie-Based Table Partitioning
334(6)
Experiments
340(1)
Route Updating
341(2)
Compaction Techniques
343(1)
Mask Extension
343(3)
Prefix Aggregation and Expansion
346(1)
EaseCAM: A Two-Level Paged-TCAM Architecture
347(3)
Algorithms for Bursty Access Pattern
350(1)
Static Architecture
350(2)
Dynamic Architecture
352(3)
Discussions
355(1)
A Distributed TCAM Architecture
356(15)
Analysis of Routing Tables
356(2)
Distributed Memory (TCAM) Organization
358(1)
LBBTC Algorithm
358(1)
Mathematical Model
359(2)
Adjusting Algorithm
361(1)
Analysis of the Power Efficiency
362(2)
Complete Implementation Architecture
364(1)
Index Logic
364(1)
Priority Selector (Adaptive Load Balancing Logic)
365(1)
Ordering Logic
366(1)
Performance Analysis
366(3)
References
369(2)
Routing-Table Partitioning Technologies
371(44)
Prefix and Interval Partitioning
371(17)
Partitioned Binary Search Table
371(1)
Encoding Prefixes as Ranges
372(1)
Recomputation
373(2)
Insertion into a Modified Binary Search Table
375(1)
Multiway Binary Search: Exploiting the Cache Line
376(2)
Performance Measurements
378(1)
Multilevel and Interval Partitioning
379(1)
Multilevel Partitioning
380(3)
Interval Partitioning
383(2)
Experimental Results
385(3)
Port-Based Partitioning
388(13)
IFPLUT Algorithm
388(1)
Primary Lookup Table Transformation
388(3)
Partition Algorithm Based on Next Hops
391(2)
IFPLUT Architecture
393(1)
Basic Architecture
393(1)
Imbalance Distribution of Prefixes
393(1)
Concept of Search Unit
394(1)
Memory Assignment Scheme
395(1)
Selector Block
395(2)
IFPLUT Updates
397(1)
Implementation Using TCAM
398(1)
Design Optimization
399(1)
Experimental Results
400(1)
ROT-Partitioning
401(6)
Concept of ROT-Partitioning
401(1)
Generalization of ROT-Partition
402(2)
Complexity Analysis
404(1)
Results of ROT-Partitioning
405(1)
Storage Sizes
405(1)
Worst-Case Lookup Times
406(1)
Comb Extraction Scheme
407(8)
Splitting Rule
408(4)
Comparison Set
412(1)
Implementation Using Binary Trie
413(1)
References
414(1)
Index 415


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.
Biežāk uzdotie jautājumi par e-grāmatām Biežāk uzdotie jautājumi par e-grāmatām
Permanent link: https://www.kriso.lv/db/97810006540046e.html
Keywords: