高速网络中的QoS控制（影印版） (2008 年度畅销榜NO.16099 )

本书主要介绍的是在ATM、IP和MPLS等高速网络中实现QoS控制所涉及的基础知识。理论。体系结构和技术。书中全面地概述了现有的QoS控制技术，并讲述了其实现方法。
本书所涉及的主题还包括：
准许控制和数据通信信道接受
流量访问控制
分组计划算法
分组公平排队的实现
缓冲管理
流与拥塞控制
QoS路由
差分服务的基本体系结构与概念模型
SONET与ATM
本书全面地讨论了工科学生所需要了解的QoS技术和体系结构，以及软件、硬件和系统设计的实践。

PREFACE
1 INTRODUCTION
1.1 Nature of Traffic / 2
1.2 Network Technologies / 2
1.2.1 ATM / 2
1.2.2 Internet Integrated Services (Intserv) / 4
1.2.3 Internet Differentiated Services (Diffserv) / 5
1.2.4 Multiprotocol Label Switching (MPLS) / 6
1.3 QoS Parameters / 7
1.4 QoS Control Methods / 9
1.4.1 Admission Control / 9
1.4.2 Traffic Access Control / 10
1.4.3 Packet Scheduling / 10
1.4.4 Packet Fair Queuing Implementation / 11
1.4.5 Buffer Management / 11
1.4.6 Flow and Congestion Control / 11
1.4.7 QoS Routing / 11
1.5 Summary / 12
References / 13

2 ADMISSION CONTROL
2.1 Deterministic Bound / 18
2.2 Probabilistic Bound: Equivalent Bandwidth / 19
2.2.1 Bernoulli Trials and Binomial Distribution / 20
2.2.2 Fluid-Flow Approximation / 20
2.2.3 Gaussian Distribution / 21
2.2.4 Large-Deviation Approximation / 21
2.2.5 Poisson Distribution / 22
2.2.6 Measurement-Based Methods / 22
2.3 CAC for ATM VBR Services / 23
2.3.1 Worst-Case Traffic Model and CAC / 23
2.3.2 Effective Bandwidth / 24
2.3.3 Lucent's CAC / 25
2.3.4 NEC'sCAC / 27
2.3.5 Tagged-Probability-Based CAC / 30
2.4 CAC for Integrated Services Internet / 43
2.4.1 Guaranteed Quality of Service / 45
2.4.2 Controlled-Load Service / 49
References / 54

3 TRAFFIC ACCESS CONTROL
3.1 ATM Traffic Contract and Control Algorithms / 62
3.1.1 Traffic Contract / 62
3.1.2 PCR Conformance, SCR, and BT / 63
3.1.3 Cell Delay Variation Tolerance / 63
3.1.4 Generic Cell Rate Algorithm / 64
3.2 An ATM Shaping Multiplexer / 66
3.2.1 Regularity Condition Dual Leaky Bucket / 67
3.2.2 ATM Shaping Multiplexer Algorithm / 70
3.2.3 Implementation Architecture / 77
3.2.4 Finite Bits Overflow Problem / 79
3.2.5 Simulation Study / 86
3.2.6 Summary / 89
3.3 An Integrated Packet Shaper / 90
3.3.1 Basics of a Packet Traffic Shaper / 90
3.3.2 Integrating Traffic Shaping and WFI Scheduling / 95
3.3.3 A Logical Structure of the WFI Packet Shaper / 96
3.3.4 Implementation of the WFI Packet Shaper／97
3.4 Appendix: Bucket Size Determination／103
References／107

4 PACKET SCHEDULING
4.1 Overview / 109
4.2 First In, First Out / 111
4.3 Round-Robin / 147 / 112
4.4 Stop-and-Go / 113
4.5 Hierarchical Round-Robin / 115
4.6 Earliest Due Date / 116
4.7 Rate-Controlled Static Priority / 117
4.8 Generalized Processor Sharing / 119
4.9 Weighted Fair Queuing / 123
4.10 Virtual Clock / 127
4.11 Self-Clocked Fair Queuing / 130
4.12 Worst-case Fair Weighted Fair Queuing / 132
4.13 WF2Q+ / 136
4.14 Multiple-Node Case / 137
4.15 Comparison / 139
4.16 A Core-Stateless Scheduling Algorithm / 140
4.16.1 Shaped Virtual Clock Algorithm / 141
4.16.2 Core-Stateless Shaped Virtual Clock Algorithm / 142
4.16.3 Encoding Process / 147
4.16.4 Complexity / 150
References / 150

5 PACKET FAIR QUEUING IMPLEMENTATIONS
5.1 Conceptual Framework and Design Issues / 154
5.2 Sequencer / 156
5.2.1 Store Cells in Logical Queues / 157
5.2.2 Sort Priorities Using a Sequencer / 158
5.3 Priority Content-Addressable Memory / 163
5.3.1 Searching by the PCAM Chip / 163
5.3.2 Block Diagram / 165
5.3.3 Connecting Multiple PCAM Chips / 168
5.4 RAM-Based Searching Engine / 168
5.4.1 Hierarchical Searching / 169
5.4.2 Timestamp Overflow / 172
5.4.3 Design of the RSE / 173
5.4.4 RSE Operations / 173
5.4.5 Write-in Operation / 175
5.4.6 Reset Operation / 176
5.4.7 Search Operation / 177
5.5 General Shaper-Scheduler / 179
5.5.1 Slotted Updates of System Virtual Time / 180
5.5.2 Implementation Architecture / 182
5.6 Timestamp Aging Problem / 188
5.7 Summary / 192
References / 193

6 BUFFER MANAGEMENT
6.1 A Look at ATM Networks / 197
6.1.1 Overview / 198
6.1.2 Self-Calibrating Pushout / 201
6.1.3 TCP/IP over ATM-UBR / 209
6.1.4 Dynamic Threshold with Single Loss Priority / 212
6.2 A Look at the Internet / 213
6.2.1 Tail Drop / 214
6.2.2 Drop on Full / 214
6.2.3 Random Early Detection / 215
6.2.4 Differential Dropping: RIO / 220
6.2.5 Fair Random Early Detection (FRED) / 223
6.2.6 Stabilized Random Early Detection (SRED) / 224
6.2.7 Longest Queue Drop (LQD) / 226
6.3 Summary / 231
References / 232

7 FLOW AND CONGESTION CONTROL
7.1 Overview / 235
7.1.1 Window-Based Flow Control / 236
7.1.2 Rate-Based Flow Control / 238
7.1.3 Predictive Control Mechanism / 239
7.2 ATM Networks / 240
7.2.1 ATM Service Categories / 240
7.2.2 Backlog Balancing Flow Control / 242
7.2.3 ABR Flow Control / 267
7.3 TCP/IP Networks / 276
7.3.1 TCP Overview / 277
7.3.2 TCP Congestion Control / 281
7.3.3 Other TCP Variants / 286
7.3.4 TCP with Explicit Congestion Notification / 289
7.4 EASY Another Rate-Based Flow Control Scheme / 291
References / 292

8 QoS ROUTING
8.1 ATM Signaling and Routing / 300
8.1.1 User-to-Network (UNI) Signaling / 301
8.1.2 PNNI Signaling / 306
8.2 QoS Routing for Integrated Services Networks / 316
8.2.1 Selection of Metrics / 316
8.2.2 Weighted Graph Model / 318
8.2.3 Path Selection Algorithms / 319
8.2.4 Computational Complexity / 325
8.2.5 Further Reading / 326
References / 326

9 DIFFERENTIATED SERVICES
9.1 Service Level Agreement and Traffic Conditioning Agreement / 330
9.1.1 Service Level Agreement / 330
9.1.2 Traffic Conditioning Agreement / 331
9.2 Basic Architecture of Differentiated Services / 332
9.3 Network Boundary Traffic Classification and
Conditioning / 334
9.4 Per-Hop Behaviors and Some Implementation
Examples / 335
9.4.1 Default Behavior / 336
9.4.2 Class Selector / 336
9.4.3 Assured Forwarding / 337
9.4.4 Expedited Forwarding / 338
9.4.5 PHB Implementation with Packet Schedulers / 338
9.5 Conceptual Model / 340
9.5.1 Configuration and Management Interface / 341
9.5.2 Optional QoS Agent Module / 341
9.5.3 Diffserv Functions at Ingress and Egress Interfaces / 341
9.5.4 Shaping and Policing / 341
9.5.5 Traffic Classification / 342
9.5.6 Meters / 342
9.5.7 Action Elements / 342
9.5.8 Queuing Elements / 343
9.5.9 Traffic Conditioning Blocks / 344
References / 344

10 MULTIPROTOCOL LABEL SWITCHING
10.1 Basic Architecture / 349
10.1.1 Label and Label Binding / 349
10.1.2 Label Stack / 250
10.1.3 Route Selection / 352
10.1.4 Penultimate Hop Popping / 352
10.1.5 LSP Tunnels / 353
10.1.6 An Example: Hierarchy of LSP Tunnels / 354
10.1.7 Next-Hop Label Forwarding Entry / 355
10.2 Label Distribution / 356
10.2.1 Unsolicited Downstream vs. Downstream-on-Demand / 356
10.2.2 Label Retention Mode: Liberal vs. Conservative / 357
10.2.3 LSP Control: Ordered vs. Independent / 357
10.2.4 Label Distribution Peering and Hierarchy / 358
10.2.5 Selection of Label Distribution Protocol / 359
10.3 MPLS Support of Differentiated Services / 360
10.4 Label-Forwarding Model for Diffserv LSRs / 363
10.4.1 Incoming PHB Determination / 363
10.4.2 Outgoing PHB Determination with Optimal Traffic Conditioning / 363
10.4.3 Label Forwarding / 364
10.4.4 Encoding Diffserv Information Into Encapsulation Layer / 365
10.5 Applications of Multiprotocol Label Switching / 365
10.5.1 Traffic Engineering / 365
10.5.2 Virtual Private Networks / 370
References / 375

APPENDIX SONET AND ATM PROTOCOLS
A.1 ATM Protocol Reference Model / 379
A.2 Synchronous Optical Network (SONET) / 380
A.2.1 SONET Sublayers / 380
A.2.2 STS-N Signals / 382
A.2.3 SONET Overhead Bytes / 385
A.2.4 Scrambling and Descrambling / 387
A.2.5 Frequency Justification / 388
A.2.6 Automatic Protection Switching (APS) / 389
A.2.7 STS-3 vs. STS-3c / 391
A.2.8 OC-N Multiplexor / 392
A.3 Sublayer Functions in the Reference Model / 393
A.4 Asynchronous Transfer Mode / 395
A.4.1 Virtual Path and Virtual Channel Identifier / 396
A.4.2 Payload Type Identifier / 397
A.4.3 Cell Loss Priority / 398
A.4.4 Predefined Header Field Values / 398
A.5 ATM Adaptation Layer / 399
A.5.1 AAL Type I(AAL1) / 401
A.5.2 AAL Type 2 (AAL2) / 403
A.5.3 AAL Types 3 and 4 (AAL3/4) / 404
A.5.4 AAL Type 5 (AAL5) / 406
References / 408
INDEX

H.Johathan Chao获得了俄亥俄州立大学的博士学位。1992年受聘为纽约布鲁克林理工学院电子工程系的教授，负责指导千吉ATM交换机和，P路由器。服务质量控制和光子交换的研究工作。他是Come网络公司的创始人之一，也是该公司的首席技术官，并开发了千吉IP/MPLS交换路由器。1985年至1992年间，他曾在新泽西的Telcordia公司做技术员。他是IEEE委员，曾发表了很多与上述主题相关的文章。 XiaoLei Guo博士是位子新泽西马那拉潘的INTEC系统公司的高级集成电路设计师，主要负责宽带通信专用集成电路的研发与应用。

This book addresses the basics, theory, architectures, and technologies to implement quality-of-service (QoS)control in high-speed networks, including asynchronous transfer mode (ATM), Internet Protocol (IP), and multiprotocol label switching (MPLS) networks. For the last few years, we have witnessed an explosion of Internet demands, yielding rapid development of the corresponding technologies in the backbone network, such as terabit routers, dense wavelength division multiplexing (DWDM) transmission equipment, and optical cross-connect switches (OXCs). The success of telecommunications in supporting a wide variety of Internet services, such as multimedia conferencing and video-on-demand, depends greatly on, (in addition to high-speed transmission and switching) the reliable control in the underlying high-speed networks to provide guaranteed QoS. QoS provision in a network basically concerns the establishment of a network resource sharing policy (including link bandwidth and buffer space) and then the enforcement of that policy. As the line speed increases to 10 or 40 Gbit/s and the number of connections in each line increases to several hundreds of thousands, implementing QoS control, under the constraints of the timing and memory requirement, becomes very challenging. Unlike other books in the area, this book not only gives a comprehensive overview of the existing QoS control techniques, but also describes practical approaches to implement the techniques in the high-speed network. Most of the book is based on the material that Jonathan has been teaching to the industry and universities for the past decade. He taught a graduate course "Broadband Network" at Polytechnic University, NY, and used the draft of the book as the text. The book has incorporated feedback from both industry people and college students. We believe this book is timely to meet the demand of industry people who are looking for the solutions for meeting various QoS requirements in the high-speed network. AUDIENCE This book surveys the latest technical papers that readers can refer to for the most up-to-date development of control strategies in the high-speed network. The readers are assumed to have some knowledge of fundamental networking and telecommunications. Some of this book may require readers to have some knowledge of probability models and college-level mathematics. Since each chapter is self-contained, readers can easily choose the topic of interest for both theoretical and practical aspects. A comprehensive list of references follows each chapter. This book should be useful to software, hardware, and system engineers in networking equipment and network operation. It should be useful as a textbook for students and lecturers in electrical engineering and computer science departments who are interested in high-speed net-working. ORGANIZATION OF THE BOOK Throughout, IP and ATM networks are used as examples. The book is organized as follows: ·Chapter 1 presents a systematic overview of QoS control methods, including admission control, traffic access control, packet scheduling, buffer management, flow and congestion control, and QoS routing. It also introduces ATM, Internet integrated services (lntserv), Internet differentiated services (Diffserv), and MPLS. It also describes the traffic characterization and QoS parameters. ·Chapter 2 explores admission control and its process of deciding whether a new connection between a source-destination pair can be accepted across a network. The decision is made subject to this new connection's QoS requirement (e.g., loss and delay) without affecting the committed resource provision for the existing connections at each node on its path. ·Chapter 3 focuses on traffic access control and its mechanism of enforcing certain criteria regarding an established connection's traffic load and burstiness, for instance, at the network ingress/entry point of this connection. If the connection crosses two subnetworks under different administration, similar control (also called traffic policing) may also be needed at the egress point of the first subnetwork. ·Chapter 4 presents a historical overview of different packet scheduling algorithms. It also describes under each scheme how to regulate packet transmission orders among a set of connections multiplexed at a network node so that their QoS requirements can be satisfied. ·Chapter 5 is dedicated to discussing the implementation of packet fair queuing, an intensively studied packet scheduling algorithm due to its desirable capability of providing QoS guarantees (e.g., on delay) for connections with diversified QoS requirements. Practical examples covered in this chapter include designs based on sequencers, prioritycontent-addressable memory (PCAM), and random access memory (RAM). ·Chapter 6 presents buffer management, which controls the access of incoming packets to the buffer space and decides which packet should be discarded when, for instance, the buffer is full or a threshold-crossing event happens. ·Chapter 7 explains flow control and congestion control. Flow control addresses the needs of speed matching between a source-destination pair or any two nodes on the path of a connection. Congestion control addresses the regulation of traffic loading across a network for congestion avoidance and recovery. ·Chapter 8 covers QoS routing and describes its process of deciding which path (in a connection-oriented network like ATM) or which next-hop node (in a connectionless network like IP) should be chosen for a new connection among multiple physical paths across a network. The decision may depend on the resource availability along thc path and whether the QoS requirement of the new connection can be met. ·Chapter 9 describes basic architecture and conceptual model of Diffserv in details. It describes the network boundary traffic conditioning and per hop behaviors functions used to support Diffserv. ·Chapter 10 covers MPLS technology. It includes the basic concepts, such as the label stack, route selection, penultimate hop popping, and label-switched-path (LSP) tunnel, Label Distribution. It also describes the MPLS mechanism to support Diffserv and two applications of MPLS: traffic engineering and virtual private networks (VPNs). ·The Appendix briefly describes Synchronous Optical Networks (SONET) and ATM for readers who need to attain a basic understanding of the physical layer and link layer protocols of the high-speed network. ACKNOWLEDGMENTS We are indebted to all who contributed to this book. Especially, we thank Professor Sugih Jamin (University of Michigan), Dapeng Wu (Carnegie Mellon University), Dr. Jun-Shik Hong, Dr. Li-Sheng Chen (Alcatel), Dr. Necdet Uzun (Cisco), Dr. Yau-Ren Jenq (Fujitsu), Dr. Soung-Yue Liew, Dr. Zhigang Jing (Polytechnic University), Dr. Roberto Rojas-Cessa, and Dr. Taweesak Kijkanjanarat. We thank Dr. Jing and Dr. Liew for contributing Chapters 9 and 10, and Mike Barrett and Dr. Mukesh Taneja for reviewing the chapters. Jonathan wants to thank his wife, Ammie, and his children, Jessica, Roger, and Joshua, for their love, support, encouragement, patience and perseverance. He also thanks his parents for their encouragement. Xiaolei would also like to thank his wife, Mei Feng, for her love and support. We have done our best to accurately describe the QoS control methods, technologies, and implementation architectures. If any errors are found, please send email to chao@poly.edu. We will correct them in future editions.