High Performance Switches and Routers

H. Jonathan Chao, PhD, is Department Head and Professor of Electrical and Computer Engineering at Polytechnic University, Brooklyn, New York. He holds more than twenty-six patents and is an IEEE Fellow. His research focuses on terabit switches and routers, network security, quality of service control, and optical switching. Bin Liu, PhD, is Professor in the Department of Computer Science at Tsinghua University, Beijing, China. His research interests include high performance switches and routers, network security, network processors, and traffic engineering. Dr. Liu holds more than ten patents in China.

"Unique in its approach and scope, and written in an easy-to-follow manner, I strongly recommend it to the interested reading community." (ComputingReviews.com, December 17, 2007)

• Preface xvAcknowledgments xvii1 Introduction 11.1 Architecture of the Internet: Present and Future 21.1.1 The Present 21.1.2 The Future 41.2 Router Architectures 51.3 Commercial Core Router Examples 91.3.1 T640 TX-Matrix 91.3.2 Carrier Routing System (CRS-1) 111.4 Design of Core Routers 131.5 IP Network Management 161.5.1 Network Management System Functionalities 161.5.2 NMS Architecture 171.5.3 Element Management System 181.6 Outline of the Book 192 IP Address Lookup 252.1 Overview 252.2 Trie-Based Algorithms 292.2.1 Binary Trie 292.2.2 Path-Compressed Trie 312.2.3 Multi-Bit Trie 332.2.4 Level Compression Trie 352.2.5 Lulea Algorithm 372.2.6 Tree Bitmap Algorithm 422.2.7 Tree-Based Pipelined Search 452.2.8 Binary Search on Prefix Lengths 472.2.9 Binary Search on Prefix Range 482.3 Hardware-Based Schemes 512.3.1 DIR-24-8-BASIC Scheme 512.3.2 DIR-Based Scheme with Bitmap Compression (BC-16-16) 532.3.3 Ternary CAM for Route Lookup 572.3.4 Two Algorithms for Reducing TCAM Entries 582.3.5 Reducing TCAM Power – CoolCAMs 602.3.6 TCAM-Based Distributed Parallel Lookup 642.4 IPv6 Lookup 672.4.1 Characteristics of IPv6 Lookup 672.4.2 A Folded Method for Saving TCAM Storage 672.4.3 IPv6 Lookup via Variable-Stride Path and Bitmap Compression 692.5 Comparison 733 Packet Classification 773.1 Introduction 773.2 Trie-Based Classifications 813.2.1 Hierarchical Tries 813.2.2 Set-Pruning Trie 823.2.3 Grid of Tries 833.2.4 Extending Two-Dimensional Schemes 843.2.5 Field-Level Trie Classification (FLTC) 853.3 Geometric Algorithms 903.3.1 Background 903.3.2 Cross-Producting Scheme 913.3.3 Bitmap-Intersection 923.3.4 Parallel Packet Classification (P2C) 933.3.5 Area-Based Quadtree 953.3.6 Hierarchical Intelligent Cuttings 973.3.7 HyperCuts 983.4 Heuristic Algorithms 1033.4.1 Recursive Flow Classification 1033.4.2 Tuple Space Search 1073.5 TCAM-Based Algorithms 1083.5.1 Range Matching in TCAM-Based Packet Classification 1083.5.2 Range Mapping in TCAMs 1104 Traffic Management 1144.1 Quality of Service 1144.1.1 QoS Parameters 1154.1.2 Traffic Parameters 1164.2 Integrated Services 1174.2.1 Integrated Service Classes 1174.2.2 IntServ Architecture 1174.2.3 Resource ReSerVation Protocol (RSVP) 1194.3 Differentiated Services 1214.3.1 Service Level Agreement 1224.3.2 Traffic Conditioning Agreement 1234.3.3 Differentiated Services Network Architecture 1234.3.4 Network Boundary Traffic Classification and Conditioning 1244.3.5 Per Hop Behavior (PHB) 1264.3.6 Differentiated Services Field 1274.3.7 PHB Implementation with Packet Schedulers 1284.4 Traffic Policing and Shaping 1294.4.1 Location of Policing and Shaping Functions 1304.4.2 ATM’s Leaky Bucket 1314.4.3 IP’s Token Bucket 1334.4.4 Traffic Policing 1344.4.5 Traffic Shaping 1354.5 Packet Scheduling 1364.5.1 Max-Min Scheduling 1364.5.2 Round-Robin Service 1384.5.3 Weighted Round-Robin Service 1394.5.4 Deficit Round-Robin Service 1404.5.5 Generalized Processor Sharing (GPS) 1414.5.6 Weighted Fair Queuing (WFQ) 1464.5.7 Virtual Clock 1504.5.8 Self-Clocked Fair Queuing 1534.5.9 Worst-Case Fair Weighted Fair Queuing (WF2Q) 1554.5.10 WF2Q+ 1584.5.11 Comparison 1594.5.12 Priorities Sorting Using a Sequencer 1604.6 Buffer Management 1634.6.1 Tail Drop 1634.6.2 Drop on Full 1644.6.3 Random Early Detection (RED) 1644.6.4 Differential Dropping: RIO 1674.6.5 Fair Random Early Detection (FRED) 1684.6.6 Stabilized Random Early Detection (SRED) 1704.6.7 Longest Queue Drop (LQD) 1725 Basics of Packet Switching 1765.1 Fundamental Switching Concept 1775.2 Switch Fabric Classification 1815.2.1 Time-Division Switching 1815.2.2 Space-Division Switching 1835.3 Buffering Strategy in Switching Fabrics 1875.3.1 Shared-Memory Queuing 1885.3.2 Output Queuing (OQ) 1885.3.3 Input Queuing 1895.3.4 Virtual Output Queuing (VOQ) 1895.3.5 Combined Input and Output Queuing 1905.3.6 Crosspoint Queuing 1915.4 Multiplane Switching and Multistage Switching 1915.5 Performance of Basic Switches 1955.5.1 Traffic Model 1965.5.2 Input-Buffered Switches 1975.5.3 Output-Buffered Switches 1995.5.4 Completely Shared-Buffered Switches 2016 Shared-memory Switches 2076.1 Linked List Approach 2086.2 Content Addressable Memory Approach 2136.3 Space-Time-Space Approach 2156.4 Scaling the Shared-Memory Switches 2176.4.1 Washington University Gigabit Switch 2176.4.2 Concentrator-Based Growable Switch Architecture 2186.4.3 Parallel Shared-Memory Switches 2186.5 Multicast Shared-Memory Switches 2206.5.1 Shared-Memory Switch with a Multicast Logical Queue 2206.5.2 Shared-Memory Switch with Cell Copy 2206.5.3 Shared-Memory Switch with Address Copy 2227 Input-buffered Switches 2257.1 Scheduling in VOQ-Based Switches 2267.2 Maximum Matching 2297.2.1 Maximum Weight Matching 2297.2.2 Approximate MWM 2297.2.3 Maximum Size Matching 2307.3 Maximal Matching 2317.3.1 Parallel Iterative Matching (PIM) 2327.3.2 Iterative Round-Robin Matching (iRRM) 2337.3.3 Iterative Round-Robin with SLIP (iSLIP) 2347.3.4 Firm 2417.3.5 Dual Round-Robin Matching (DRRM) 2417.3.6 Pipelined Maximal Matching 2457.3.7 Exhaustive Dual Round-Robin Matching (EDRRM) 2487.4 Randomized Matching Algorithms 2497.4.1 Randomized Algorithm with Memory 2507.4.2 A Derandomized Algorithm with Memory 2507.4.3 Variant Randomize Matching Algorithms 2517.4.4 Polling Based Matching Algorithms 2547.4.5 Simulated Performance 2587.5 Frame-based Matching 2627.5.1 Reducing the Reconfiguration Frequency 2637.5.2 Fixed Size Synchronous Frame-Based Matching 2677.5.3 Asynchronous Variable-Size Frame-Based Matching 2707.6 Stable Matching with Speedup 2737.6.1 Output-Queuing Emulation with Speedup of 4 2747.6.2 Output-Queuing Emulation with Speedup of 2 2757.6.3 Lowest Output Occupancy Cell First (LOOFA) 2788 Banyan-based Switches 2848.1 Banyan Networks 2848.2 Batcher-Sorting Network 2878.3 Output Contention Resolution Algorithms 2888.3.1 Three-Phase Implementation 2888.3.2 Ring Reservation 2888.4 The Sunshine Switch 2928.5 Deflection Routing 2948.5.1 Tandem Banyan Switch 2948.5.2 Shuffle-Exchange Network with Deflection Routing 2968.5.3 Dual Shuffle-Exchange Network with Error-Correcting Routing 2978.6 Multicast Copy Networks 3038.6.1 Broadcast Banyan Network 3048.6.2 Encoding Process 3088.6.3 Concentration 3098.6.4 Decoding Process 3108.6.5 Overflow and Call Splitting 3108.6.6 Overflow and Input Fairness 3119 Knockout-based Switches 3169.1 Single-Stage Knockout Switch 3179.1.1 Basic Architecture 3179.1.2 Knockout Concentration Principle 3189.1.3 Construction of the Concentrator 3209.2 Channel Grouping Principle 3239.2.1 Maximum Throughput 3249.2.2 Generalized Knockout Principle 3259.3 Two-Stage Multicast Output-Buffered ATM Switch (MOBAS) 3279.3.1 Two-Stage Configuration 3279.3.2 Multicast Grouping Network (MGN) 3309.4 Appendix 33310 The Abacus Switch 33610.1 Basic Architecture 33710.2 Multicast Contention Resolution Algorithm 34010.3 Implementation of Input Port Controller 34210.4 Performance 34410.4.1 Maximum Throughput 34410.4.2 Average Delay 34710.4.3 Cell Loss Probability 34910.5 ATM Routing and Concentration (ARC) Chip 35110.6 Enhanced Abacus Switch 35410.6.1 Memoryless Multi-Stage Concentration Network 35410.6.2 Buffered Multi-Stage Concentration Network 35710.6.3 Resequencing Cells 35910.6.4 Complexity Comparison 36110.7 Abacus Switch for Packet Switching 36210.7.1 Packet Interleaving 36210.7.2 Cell Interleaving 36411 Crosspoint Buffered Switches 36711.1 Combined Input and Crosspoint Buffered Switches 36811.2 Combined Input and Crosspoint Buffered Switches with VOQ 37011.2.1 CIXB with One-Cell Crosspoint Buffers (CIXB-1) 37111.2.2 Throughput and Delay Performance 37111.2.3 Non-Negligible Round-Trip Times in CIXB-k 37611.3 OCF_OCF: Oldest Cell First Scheduling 37611.4 LQF_RR: Longest Queue First and Round-Robin Scheduling in CIXB-1 37811.5 MCBF: Most Critical Buffer First Scheduling 37912 Clos-network Switches 38212.1 Routing Property of Clos Network Switches 38312.2 Looping Algorithm 38712.3 m-Matching Algorithm 38812.4 Euler Partition Algorithm 38812.5 Karol’s Algorithm 38912.6 Frame-Based Matching Algorithm for Clos Network (f-MAC) 39112.7 Concurrent Matching Algorithm for Clos Network (c-MAC) 39212.8 Dual-Level Matching Algorithm for Clos Network (d-MAC) 39512.9 The ATLANTA Switch 39812.10 Concurrent Round-Robin Dispatching (CRRD) Scheme 40012.11 The Path Switch 40412.11.1 Homogeneous Capacity and Route Assignment 40612.11.2 Heterogeneous Capacity Assignment 40813 Multi-plane Multi-stage Buffered Switch 41313.1 TrueWay Switch Architecture 41413.1.1 Stages of the Switch 41513.2 Packet Scheduling 41713.2.1 Partial Packet Interleaving (PPI) 41913.2.2 Dynamic Packet Interleaving (DPI) 41913.2.3 Head-of-Line (HOL) Blocking 42013.3 Stage-To-Stage Flow Control 42013.3.1 Back-Pressure 42113.3.2 Credit-Based Flow Control 42113.3.3 The DQ Scheme 42213.4 Port-To-Port Flow Control 42413.4.1 Static Hashing 42413.4.2 Dynamic Hashing 42513.4.3 Time-Stamp-Based Resequence 42813.4.4 Window-Based Resequence 42813.5 Performance Analysis 43113.5.1 Random Uniform Traffic 43113.5.2 Hot-Spot Traffic 43213.5.3 Bursty Traffic 43213.5.4 Hashing Schemes 43213.5.5 Window-Based Resequencing Scheme 43413.6 Prototype 43414 Load-balanced Switches 43814.1 Birkhoff–Von Neumann Switch 43814.2 Load-Balanced Birkhoff–von Neumann Switches 44114.2.1 Load-Balanced Birkhoff–von Neumann Switch Architecture 44114.2.2 Performance of Load-Balanced Birkhoff–von Neumann Switches 44214.3 Load-Balanced Birkhoff–von Neumann Switches With FIFO Service 44414.3.1 First Come First Served (FCFS) 44614.3.2 Earliest Deadline First (EDF) and EDF-3DQ 45014.3.3 Full Frames First (FFF) 45114.3.4 Full Ordered Frames First (FOFF) 45514.3.5 Mailbox Switch 45614.3.6 Byte-Focal Switch 45915 Optical Packet Switches 46815.1 Opto-Electronic Packet Switches 46915.1.1 Hypass 46915.1.2 Star-Track 47115.1.3 Cisneros and Brackett 47215.1.4 BNR (Bell-North Research) Switch 47315.1.5 Wave-Mux Switch 47415.2 Optoelectronic Packet Switch Case Study I 47515.2.1 Speedup 47615.2.2 Data Packet Flow 47715.2.3 Optical Interconnection Network (OIN) 47715.2.4 Ping-Pong Arbitration Unit 48215.3 Optoelectronic Packet Switch Case Study II 49015.3.1 Petabit Photonic Packet Switch Architecture 49015.3.2 Photonic Switch Fabric (PSF) 49515.4 All Optical Packet Switches 50315.4.1 The Staggering Switch 50315.4.2 Atmos 50415.4.3 Duan’s Switch 50515.4.4 3M Switch 50615.5 Optical Packet Switch with Shared Fiber Delay Lines Single-stage Case 50915.5.1 Optical Cell Switch Architecture 50915.5.2 Sequential FDL Assignment (SEFA) Algorithm 51215.5.3 Multi-Cell FDL Assignment (MUFA) Algorithm 51815.6 All Optical Packet Switch with Shared Fiber Delay Lines – Three Stage Case 52415.6.1 Sequential FDL Assignment for Three-Stage OCNS (SEFAC) 52615.6.2 Multi-Cell FDL Assignment for Three-Stage OCNS (MUFAC) 52615.6.3 FDL Distribution in Three-Stage OCNS 52815.6.4 Performance Analysis of SEFAC and MUFAC 53015.6.5 Complexity Analysis of SEFAC and MUFAC 53216 High-speed Router Chip Set 53816.1 Network Processors (NPs) 53816.1.1 Overview 53816.1.2 Design Issues for Network Processors 53916.1.3 Architecture of Network Processors 54216.1.4 Examples of Network Processors – Dedicated Approach 54316.2 Co-Processors for Packet Classification 55416.2.1 LA-1 Bus 55416.2.2 TCAM-Based Classification Co-Processor 55616.2.3 Algorithm-Based Classification Co-Processor 56216.3 Traffic Management Chips 56716.3.1 Overview 56716.3.2 Agere’s TM Chip Set 56716.3.3 IDT TM Chip Set 57316.3.4 Summary 57916.4 Switching Fabric Chips 57916.4.1 Overview 57916.4.2 Switch Fabric Chip Set from Vitesse 58016.4.3 Switch Fabric Chip Set from AMCC 58916.4.4 Switch Fabric Chip Set from IBM (now of AMCC) 59316.4.5 Switch Fabric Chip Set from Agere 597Index 606