As Internet traffic grows and demands for quality of service become stringent, researchers and engineers can turn to this go-to guide for tested and proven solutions. This text presents the latest developments in high performance switches and routers, coupled with step-by-step design guidance and more than 550 figures and examples to enable readers to grasp all the theories and algorithms used for design and implementation.
Autorentext
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.
Klappentext
Learn to Design High Performance Switches and Routers for Today's Ever Growing Internet Traffic
As Internet traffic continues to grow, and demands for quality of service become more stringent, researchers and engineers can turn to High Performance Switches and Routers for tested and proven solutions. This text presents the latest developments in high performance switches and routers, coupled with step-by-step design guidance.
More than 550 figures and examples enable readers to grasp all the theories and algorithms used for design and implementation.
The authors begin with an examination of the architecture of the Internet, as it is now and as it will be in the future. Then, they examine router architectures and their building blocks, and the challenging issues involved in designing high performance, high-speed routers. Examples of commercial high-end routers are provided.
Next, the authors discuss the main functions of the line cards of a core router, including route lookup, packet classification, and traffic management for quality of service control. The bulk of the text is then dedicated to packet switching designs. Coverage includes the various available architectures, algorithms, and technologies. Among the topics covered, readers will find detailed discussions of the latest innovations in electrical and optical packet switching. The final chapter discusses state-of-the-science commercial chipsets used to build routers. Readers learn their architecture and functions, using the theories and conceptual designs presented in the previous chapters as a foundation.
Although implementation techniques for switches and routers will continue to evolve, the fundamental theories and principles of this text will serve readers for years to come. In addition to bringing researchers and engineers up to date with the latest designs, this text, with its focus on illustrations and examples, is an ideal graduate-level textbook.
Inhalt
Preface xv
Acknowledgments xvii
1 Introduction 1
1.1 Architecture of the Internet: Present and Future 2
1.1.1 The Present 2
1.1.2 The Future 4
1.2 Router Architectures 5
1.3 Commercial Core Router Examples 9
1.3.1 T640 TX-Matrix 9
1.3.2 Carrier Routing System (CRS-1) 11
1.4 Design of Core Routers 13
1.5 IP Network Management 16
1.5.1 Network Management System Functionalities 16
1.5.2 NMS Architecture 17
1.5.3 Element Management System 18
1.6 Outline of the Book 19
2 IP Address Lookup 25
2.1 Overview 25
2.2 Trie-Based Algorithms 29
2.2.1 Binary Trie 29
2.2.2 Path-Compressed Trie 31
2.2.3 Multi-Bit Trie 33
2.2.4 Level Compression Trie 35
2.2.5 Lulea Algorithm 37
2.2.6 Tree Bitmap Algorithm 42
2.2.7 Tree-Based Pipelined Search 45
2.2.8 Binary Search on Prefix Lengths 47
2.2.9 Binary Search on Prefix Range 48
2.3 Hardware-Based Schemes 51
2.3.1 DIR-24-8-BASIC Scheme 51
2.3.2 DIR-Based Scheme with Bitmap Compression (BC-16-16) 53
2.3.3 Ternary CAM for Route Lookup 57
2.3.4 Two Algorithms for Reducing TCAM Entries 58
2.3.5 Reducing TCAM Power CoolCAMs 60
2.3.6 TCAM-Based Distributed Parallel Lookup 64
2.4 IPv6 Lookup 67
2.4.1 Characteristics of IPv6 Lookup 67
2.4.2 A Folded Method for Saving TCAM Storage 67
2.4.3 IPv6 Lookup via Variable-Stride Path and Bitmap Compression 69
2.5 Comparison 73
3 Packet Classification 77
3.1 Introduction 77
3.2 Trie-Based Classifications 81
3.2.1 Hierarchical Tries 81
3.2.2 Set-Pruning Trie 82
3.2.3 Grid of Tries 83
3.2.4 Extending Two-Dimensional Schemes 84
3.2.5 Field-Level Trie Classification (FLTC) 85
3.3 Geometric Algorithms 90
3.3.1 Background 90
3.3.2 Cross-Producting Scheme 91
3.3.3 Bitmap-Intersection 92
3.3.4 Parallel Packet Classification (P2C) 93
3.3.5 Area-Based Quadtree 95
3.3.6 Hierarchical Intelligent Cuttings 97
3.3.7 HyperCuts 98
3.4 Heuristic Algorithms 103
3.4.1 Recursive Flow Classification 103
3.4.2 Tuple Space Search 107
3.5 TCAM-Based Algorithms 108
3.5.1 Range Matching in TCAM-Based Packet Classification 108
3.5.2 Range Mapping in TCAMs 110
4 Traffic Management 114
4.1 Quality of Service 114
4.1.1 QoS Parameters 115
4.1.2 Traffic Parameters 116
4.2 Integrated Services 117
4.2.1 Integrated Service Classes 117
4.2.2 IntServ Architecture 117
4.2.3 Resource ReSerVation Protocol (RSVP) 119
4.3 Differentiated Services 121
4.3.1 Service Level Agreement 122
4.3.2 Traffic Conditioning Agreement 123
4.3.3 Differentiated Services Network Architecture 123
4.3.4 Network Boundary Traffic Classification and Conditioning 124
4.3.5 Per Hop Behavior (PHB) 126
4.3.6 Differentiated Services Field 127
4.3.7 PHB Implementation with Packet Schedulers 128
4.4 Traffic Policing and Shaping 129
4.4.1 Location of Policing and Shaping Functions 130
4.4.2 ATM's Leaky Bucket 131
4.4.3 IP's Token Bucket 133
4.4.4 Traffic Policing 134
4.4.5 Traffic Shaping 135
4.5 Packet Scheduling 136
4.5.1 Max-Min Scheduling 136
4.5.2 Round-Robin Service 138
4.5.3 Weighted Round-Robin Service 139
4.5.4 Deficit Round-Robin Service 140
4.5.5 Generalized Processor Sharing (GPS) 141
4.5.6 Weighted Fair Queuing (WFQ) 146
4.5.7 Virtual Clock 150
4.5.8 Self-Clocked Fair Queuing 153