High Performance Switches and Routers

Name: High Performance Switches and Routers
Brand: Wiley-IEEE Press
Price: 168.99 EUR
Availability: OnlineOnly

H. Jonathan Chao Bin Liu(Autor*in)

Wiley-IEEE Press

Erschienen am 22. August 2007

622 Seiten

E-Book

PDF mit Adobe-DRM

Systemvoraussetzungen

978-0-470-11394-3 (ISBN)

168,99 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Adobe-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Personen

Inhalt

Intro
HIGH PERFORMANCE SWITCHES AND ROUTERS
CONTENTS
PREFACE
ACKNOWLEDGMENTS
1 INTRODUCTION
1.1 Architecture of the Internet: Present and Future
1.1.1 The Present
1.1.2 The Future
1.2 Router Architectures
1.3 Commercial Core Router Examples
1.3.1 T640 TX-Matrix
1.3.2 Carrier Routing System (CRS-1)
1.4 Design of Core Routers
1.5 IP Network Management
1.5.1 Network Management System Functionalities
1.5.2 NMS Architecture
1.5.3 Element Management System
1.6 Outline of the Book
2 IP ADDRESS LOOKUP
2.1 Overview
2.2 Trie-Based Algorithms
2.2.1 Binary Trie
2.2.2 Path-Compressed Trie
2.2.3 Multi-Bit Trie
2.2.4 Level Compression Trie
2.2.5 Lulea Algorithm
2.2.6 Tree Bitmap Algorithm
2.2.7 Tree-Based Pipelined Search
2.2.8 Binary Search on Prefix Lengths
2.2.9 Binary Search on Prefix Range
2.3 Hardware-Based Schemes
2.3.1 DIR-24-8-BASIC Scheme
2.3.2 DIR-Based Scheme with Bitmap Compression (BC-16-16)
2.3.3 Ternary CAM for Route Lookup
2.3.4 Two Algorithms for Reducing TCAM Entries
2.3.5 Reducing TCAM Power - CoolCAMs
2.3.6 TCAM-Based Distributed Parallel Lookup
2.4 IPv6 Lookup
2.4.1 Characteristics of IPv6 Lookup
2.4.2 A Folded Method for Saving TCAM Storage
2.4.3 IPv6 Lookup via Variable-Stride Path and Bitmap Compression
2.5 Comparison
3 PACKET CLASSIFICATION
3.1 Introduction
3.2 Trie-Based Classifications
3.2.1 Hierarchical Tries
3.2.2 Set-Pruning Trie
3.2.3 Grid of Tries
3.2.4 Extending Two-Dimensional Schemes
3.2.5 Field-Level Trie Classification (FLTC)
3.3 Geometric Algorithms
3.3.1 Background
3.3.2 Cross-Producting Scheme
3.3.3 Bitmap-Intersection
3.3.4 Parallel Packet Classification (P(2)C)
3.3.5 Area-Based Quadtree
3.3.6 Hierarchical Intelligent Cuttings
3.3.7 HyperCuts
3.4 Heuristic Algorithms
3.4.1 Recursive Flow Classification
3.4.2 Tuple Space Search
3.5 TCAM-Based Algorithms
3.5.1 Range Matching in TCAM-Based Packet Classification
3.5.2 Range Mapping in TCAMs
4 TRAFFIC MANAGEMENT
4.1 Quality of Service
4.1.1 QoS Parameters
4.1.2 Traffic Parameters
4.2 Integrated Services
4.2.1 Integrated Service Classes
4.2.2 IntServ Architecture
4.2.3 Resource ReSerVation Protocol (RSVP)
4.3 Differentiated Services
4.3.1 Service Level Agreement
4.3.2 Traffic Conditioning Agreement
4.3.3 Differentiated Services Network Architecture
4.3.4 Network Boundary Traffic Classification and Conditioning
4.3.5 Per Hop Behavior (PHB)
4.3.6 Differentiated Services Field
4.3.7 PHB Implementation with Packet Schedulers
4.4 Traffic Policing and Shaping
4.4.1 Location of Policing and Shaping Functions
4.4.2 ATM's Leaky Bucket
4.4.3 IP's Token Bucket
4.4.4 Traffic Policing
4.4.5 Traffic Shaping
4.5 Packet Scheduling
4.5.1 Max-Min Scheduling
4.5.2 Round-Robin Service
4.5.3 Weighted Round-Robin Service
4.5.4 Deficit Round-Robin Service
4.5.5 Generalized Processor Sharing (GPS)
4.5.6 Weighted Fair Queuing (WFQ)
4.5.7 Virtual Clock
4.5.8 Self-Clocked Fair Queuing
4.5.9 Worst-Case FairWeighted Fair Queuing (WF(2)Q)
4.5.10 WF(2)Q+
4.5.11 Comparison
4.5.12 Priorities Sorting Using a Sequencer
4.6 Buffer Management
4.6.1 Tail Drop
4.6.2 Drop on Full
4.6.3 Random Early Detection (RED)
4.6.4 Differential Dropping: RIO
4.6.5 Fair Random Early Detection (FRED)
4.6.6 Stabilized Random Early Detection (SRED)
4.6.7 Longest Queue Drop (LQD)
5 BASICS OF PACKET SWITCHING
5.1 Fundamental Switching Concept
5.2 Switch Fabric Classification
5.2.1 Time-Division Switching
5.2.2 Space-Division Switching
5.3 Buffering Strategy in Switching Fabrics
5.3.1 Shared-Memory Queuing
5.3.2 Output Queuing (OQ)
5.3.3 Input Queuing
5.3.4 Virtual Output Queuing (VOQ)
5.3.5 Combined Input and Output Queuing
5.3.6 Crosspoint Queuing
5.4 Multiplane Switching and Multistage Switching
5.5 Performance of Basic Switches
5.5.1 Traffic Model
5.5.2 Input-Buffered Switches
5.5.3 Output-Buffered Switches
5.5.4 Completely Shared-Buffered Switches
6 SHARED-MEMORY SWITCHES
6.1 Linked List Approach
6.2 Content Addressable Memory Approach
6.3 Space-Time-Space Approach
6.4 Scaling the Shared-Memory Switches
6.4.1 Washington University Gigabit Switch
6.4.2 Concentrator-Based Growable Switch Architecture
6.4.3 Parallel Shared-Memory Switches
6.5 Multicast Shared-Memory Switches
6.5.1 Shared-Memory Switch with a Multicast Logical Queue
6.5.2 Shared-Memory Switch with Cell Copy
6.5.3 Shared-Memory Switch with Address Copy
7 INPUT-BUFFERED SWITCHES
7.1 Scheduling in VOQ-Based Switches
7.2 Maximum Matching
7.2.1 MaximumWeight Matching
7.2.2 Approximate MWM
7.2.3 Maximum Size Matching
7.3 Maximal Matching
7.3.1 Parallel Iterative Matching (PIM)
7.3.2 Iterative Round-Robin Matching (iRRM)
7.3.3 Iterative Round-Robin with SLIP (iSLIP)
7.3.4 FIRM
7.3.5 Dual Round-Robin Matching (DRRM)
7.3.6 Pipelined Maximal Matching
7.3.7 Exhaustive Dual Round-Robin Matching (EDRRM)
7.4 Randomized Matching Algorithms
7.4.1 Randomized Algorithm with Memory
7.4.2 A Derandomized Algorithm with Memory
7.4.3 Variant Randomize Matching Algorithms
7.4.4 Polling Based Matching Algorithms
7.4.5 Simulated Performance
7.5 Frame-based Matching
7.5.1 Reducing the Reconfiguration Frequency
7.5.2 Fixed Size Synchronous Frame-Based Matching
7.5.3 Asynchronous Variable-Size Frame-Based Matching
7.6 Stable Matching with Speedup
7.6.1 Output-Queuing Emulation with Speedup of 4
7.6.2 Output-Queuing Emulation with Speedup of 2
7.6.3 Lowest Output Occupancy Cell First (LOOFA)
8 BANYAN-BASED SWITCHES
8.1 Banyan Networks
8.2 Batcher-Sorting Network
8.3 Output Contention Resolution Algorithms
8.3.1 Three-Phase Implementation
8.3.2 Ring Reservation
8.4 The Sunshine Switch
8.5 Deflection Routing
8.5.1 Tandem Banyan Switch
8.5.2 Shuffle-Exchange Network with Deflection Routing
8.5.3 Dual Shuffle-Exchange Network with Error-Correcting Routing
8.6 Multicast Copy Networks
8.6.1 Broadcast Banyan Network
8.6.2 Encoding Process
8.6.3 Concentration
8.6.4 Decoding Process
8.6.5 Overflow and Call Splitting
8.6.6 Overflow and Input Fairness
9 KNOCKOUT-BASED SWITCHES
9.1 Single-Stage Knockout Switch
9.1.1 Basic Architecture
9.1.2 Knockout Concentration Principle
9.1.3 Construction of the Concentrator
9.2 Channel Grouping Principle
9.2.1 Maximum Throughput
9.2.2 Generalized Knockout Principle
9.3 Two-Stage Multicast Output-Buffered ATM Switch (MOBAS)
9.3.1 Two-Stage Configuration
9.3.2 Multicast Grouping Network (MGN)
9.4 Appendix
10 THE ABACUS SWITCH
10.1 Basic Architecture
10.2 Multicast Contention Resolution Algorithm
10.3 Implementation of Input Port Controller
10.4 Performance
10.4.1 Maximum Throughput
10.4.2 Average Delay
10.4.3 Cell Loss Probability
10.5 ATM Routing and Concentration (ARC) Chip
10.6 Enhanced Abacus Switch
10.6.1 Memoryless Multi-Stage Concentration Network
10.6.2 Buffered Multi-Stage Concentration Network
10.6.3 Resequencing Cells
10.6.4 Complexity Comparison
10.7 Abacus Switch for Packet Switching
10.7.1 Packet Interleaving
10.7.2 Cell Interleaving
11 CROSSPOINT BUFFERED SWITCHES
11.1 Combined Input and Crosspoint Buffered Switches
11.2 Combined Input and Crosspoint Buffered Switches with VOQ
11.2.1 CIXB with One-Cell Crosspoint Buffers (CIXB-1)
11.2.2 Throughput and Delay Performance
11.2.3 Non-Negligible Round-Trip Times in CIXB-k
11.3 OCF_OCF: Oldest Cell First Scheduling
11.4 LQF_RR: Longest Queue First and Round-Robin Scheduling in CIXB-1
11.5 MCBF: Most Critical Buffer First Scheduling
12 CLOS-NETWORK SWITCHES
12.1 Routing Property of Clos Network Switches
12.2 Looping Algorithm
12.3 m-Matching Algorithm
12.4 Euler Partition Algorithm
12.5 Karol's Algorithm
12.6 Frame-Based Matching Algorithm for Clos Network (f-MAC)
12.7 Concurrent Matching Algorithm for Clos Network (c-MAC)
12.8 Dual-Level Matching Algorithm for Clos Network (d-MAC)
12.9 The ATLANTA Switch
12.10 Concurrent Round-Robin Dispatching (CRRD) Scheme
12.11 The Path Switch
12.11.1 Homogeneous Capacity and Route Assignment
12.11.2 Heterogeneous Capacity Assignment
13 MULTI-PLANE MULTI-STAGE BUFFERED SWITCH
13.1 TrueWay Switch Architecture
13.1.1 Stages of the Switch
13.2 Packet Scheduling
13.2.1 Partial Packet Interleaving (PPI)
13.2.2 Dynamic Packet Interleaving (DPI)
13.2.3 Head-of-Line (HOL) Blocking
13.3 Stage-To-Stage Flow Control
13.3.1 Back-Pressure
13.3.2 Credit-Based Flow Control
13.3.3 The DQ Scheme
13.4 Port-To-Port Flow Control
13.4.1 Static Hashing
13.4.2 Dynamic Hashing
13.4.3 Time-Stamp-Based Resequence
13.4.4 Window-Based Resequence
13.5 Performance Analysis
13.5.1 Random Uniform Traffic
13.5.2 Hot-Spot Traffic
13.5.3 Bursty Traffic
13.5.4 Hashing Schemes
13.5.5 Window-Based Resequencing Scheme
13.6 Prototype
14 LOAD-BALANCED SWITCHES
14.1 Birkhoff-Von Neumann Switch
14.2 Load-Balanced Birkhoff-von Neumann Switches
14.2.1 Load-Balanced Birkhoff-von Neumann Switch Architecture
14.2.2 Performance of Load-Balanced Birkhoff-von Neumann Switches
14.3 Load-Balanced Birkhoff-von Neumann Switches With FIFO Service
14.3.1 First Come First Served (FCFS)
14.3.2 Earliest Deadline First (EDF) and EDF-3DQ
14.3.3 Full Frames First (FFF)
14.3.4 Full Ordered Frames First (FOFF)
14.3.5 Mailbox Switch
14.3.6 Byte-Focal Switch
15 OPTICAL PACKET SWITCHES
15.1 Opto-Electronic Packet Switches
15.1.1 Hypass
15.1.2 Star-Track
15.1.3 Cisneros and Brackett
15.1.4 BNR (Bell-North Research) Switch
15.1.5 Wave-Mux Switch
15.2 Optoelectronic Packet Switch Case Study I
15.2.1 Speedup
15.2.2 Data Packet Flow
15.2.3 Optical Interconnection Network (OIN)
15.2.4 Ping-Pong Arbitration Unit
15.3 Optoelectronic Packet Switch Case Study II
15.3.1 Petabit Photonic Packet Switch Architecture
15.3.2 Photonic Switch Fabric (PSF)
15.4 All Optical Packet Switches
15.4.1 The Staggering Switch
15.4.2 ATMOS
15.4.3 Duan's Switch
15.4.4 3M Switch
15.5 Optical Packet Switch with Shared Fiber Delay Lines Single-stage Case
15.5.1 Optical Cell Switch Architecture
15.5.2 Sequential FDL Assignment (SEFA) Algorithm
15.5.3 Multi-Cell FDL Assignment (MUFA) Algorithm
15.6 All Optical Packet Switch with Shared Fiber Delay Lines - Three Stage Case
15.6.1 Sequential FDL Assignment for Three-Stage OCNS (SEFAC)
15.6.2 Multi-Cell FDL Assignment for Three-Stage OCNS (MUFAC)
15.6.3 FDL Distribution in Three-Stage OCNS
15.6.4 Performance Analysis of SEFAC and MUFAC
15.6.5 Complexity Analysis of SEFAC and MUFAC
16 HIGH-SPEED ROUTER CHIP SET
16.1 Network Processors (NPs)
16.1.1 Overview
16.1.2 Design Issues for Network Processors
16.1.3 Architecture of Network Processors
16.1.4 Examples of Network Processors - Dedicated Approach
16.2 Co-Processors for Packet Classification
16.2.1 LA-1 Bus
16.2.2 TCAM-Based Classification Co-Processor
16.2.3 Algorithm-Based Classification Co-Processor
16.3 Traffic Management Chips
16.3.1 Overview
16.3.2 Agere's TM Chip Set
16.3.3 IDT TM Chip Set
16.3.4 Summary
16.4 Switching Fabric Chips
16.4.1 Overview
16.4.2 Switch Fabric Chip Set from Vitesse
16.4.3 Switch Fabric Chip Set from AMCC
16.4.4 Switch Fabric Chip Set from IBM (now of AMCC)
16.4.5 Switch Fabric Chip Set from Agere
INDEX

Inhalt (PDF)

Systemvoraussetzungen

Als PDF speichern Als Link merken