Principles of Broadband Switching and Networking / Edition 1

by Soung C. Liew, Tony T. Lee

Overview

An authoritative introduction to the roles of switching and transmission in broadband integrated services networks

Principles of Broadband Switching and Networking explains the design and analysis of switch architectures suitable for broadband integrated services networks, emphasizing packet-switched interconnection networks with distributed routing algorithms. The text examines the mathematical properties of these networks, rather than specific implementation technologies. Although the pedagogical explanations in this book are in the context of switches, many of the fundamental principles are relevant to other communication networks with regular topologies.

After explaining the concept of the modern broadband integrated services network and why it is necessary in today’s society, the book moves on to basic switch design principles, discussing two types of circuit switch design—space domain and time domain—and packet switch design. Throughput improvements are illustrated by some switch design variations such as Speedup principle, Channel-Grouping principle, Knockout principle, and Dilation principle.

Moving seamlessly into advanced switch design principles, the book covers switch scalability, switch design for multicasting, and path switching. Then the focus moves to broadband communications networks that make use of such switches. Readers receive a detailed introduction on how to allocate network resources and control traffic to satisfy the quality of service requirements of network users and to maximize network usage. As an epilogue, the text shows how transmission noise and packet contention have similar characteristics and can be tamed by comparable means to achieve reliable communication.

Principles of Broadband Switching and Networking is written for senior undergraduate and first-year postgraduate students with a solid background in probability theory.

Product Details

ISBN-13:	9780471139010
Publisher:	Wiley
Publication date:	03/15/2010
Series:	Wiley Series in Telecommunications and Signal Processing , #32
Pages:	480
Product dimensions:	6.30(w) x 9.40(h) x 1.20(d)

About the Author

TONY T. LEE, PhD, is Professor of Information Engineering at the Chinese University of Hong Kong and an Adjunct Professor at the Institute of Applied Mathematics of the Chinese Academy of Science. From 1991 to 1993, he was a professor of electrical engineering at the Polytechnic Institute. Previously with AT&T Bell and Bellcore, Dr. Lee was the recipient of the Leonard G. Abraham Prize Paper Award from IEEE Communication Society in 1988, and the National Natural Science Award from China in 1999. He is a Fellow of IEEE and now an associate editor of the IEEE Transactions on Communications.

SOUNG C. LIEW, PhD, is Professor and Chairman of the Department of Information Engineering at the Chinese University of Hong Kong. He is also Adjunct Professor at Southeast University in China. TCP Veno, a version of TCP that improves its performance over wireless networks, was proposed by Liew and his student, and has now been incorporated into a recent release of Linux OS. He initiated and built the first inter-university ATM network testbed in Hong Kong in 1993.

Read an Excerpt

Click to read or download

Table of Contents

Preface xiii

About the Authors xvii

1 Introduction and Overview 1

1.1 Switching and Transmission 2

1.1.1 Roles of Switching and Transmission 2

1.1.2 Telephone Network Switching and Transmission Hierarchy 4

1.2 Multiplexing and Concentration 5

1.3 Timescales of Information Transfer 8

1.3.1 Sessions and Circuits 9

1.3.2 Messages 9

1.3.3 Packets and Cells 9

1.4 Broadband Integrated Services Network 10

Problems 12

2 Circuit Switch Design Principles 15

2.1 Space-Domain Circuit Switching 16

2.1.1 Nonblocking Properties 16

2.1.2 Complexity of Nonblocking Switches 18

2.1.3 Clos Switching Network 20

2.1.4 Benes Switching Network 28

2.1.5 Baseline and Reverse Baseline Networks 31

2.1.6 Cantor Switching Network 32

2.2 Time-Domain and Time-Space-Time Circuit Switching 35

2.2.1 Time-Domain Switching 35

2.2.2 Time-Space-Time Switching 37

Problems 39

3 Fundamental Principles of Packet Switch Design 43

3.1 Packet Contention in Switches 45

3.2 Fundamental Properties of Interconnection Networks 48

3.2.1 Definition of Banyan Networks 49

3.2.2 Simple Switches Based on Banyan Networks 51

3.2.3 Combinatoric Properties of Banyan Networks 54

3.2.4 Nonblocking Conditions for the Banyan Network 54

3.3 Sorting Networks 59

3.3.1 Basic Concepts of Comparison Networks 61

3.3.2 Sorting Networks Based on Bitonic Sort 64

3.3.3 The Odd-Even Sorting Network 70

3.3.4 Switching and Contention Resolution in Sort-Banyan Network 71

3.4 Nonblocking and Self-Routing Properties of Clos Networks 75

3.4.1 Nonblocking Route Assignment 76

3.4.2 Recursiveness Property 79

3.4.3 Basic Properties of Half-Clos Networks 81

3.4.4 Sort-Clos Principle 89

Problems 90

4 Switch Performance Analysis and Design Improvements 95

4.1 Performance of Simple Switch Designs 95

4.1.1 Throughput of an Internally Nonblocking Loss System 96

4.1.2 Throughput of an Input-Buffered Switch 96

4.1.3 Delay of an Input-Buffered Switch 103

4.1.4 Delay of an Output-Buffered Switch 112

4.2 Design Improvements for Input Queueing Switches 113

4.2.1 Look-Ahead Contention Resolution 113

4.2.2 Parallel Iterative Matching 115

4.3 Design Improvements Based on Output Capacity Expansion 119

4.3.1 Speedup Principle 119x

4.3.2 Channel-Grouping Principle 121

4.3.3 Knockout Principle 131

4.3.4 Replication Principle 137

4.3.5 Dilation Principle 138

Problems 144

5 Advanced Switch Design Principles 151

5.1 Switch Design Principles Based on Deflection Routing 151

5.1.1 Tandem-Banyan Network 151

5.1.2 Shuffle-Exchange Network 154

5.1.3 Feedback Shuffle-Exchange Network 158

5.1.4 Feedback Bidirectional Shuffle-Exchange Network 166

5.1.5 Dual Shuffle-Exchange Network 175

5.2 Switching by Memory I/O 184

5.3 Design Principles for Scalable Switches 187

5.3.1 Generalized Knockout Principle 187

5.3.2 Modular Architecture 191

Problems 198

6 Switching Principles for Multicast, Multirate, and Multimedia Services 205

6.1 Multicast Switching 205

6.1.1 Multicasting Based on Nonblocking Copy Networks 208

6.1.2 Performance Improvement of Copy Networks 213

6.1.3 Multicasting Algorithm for Arbitrary Network Topologies 220

6.1.4 Nonblocking Copy Networks Based on Broadcast Clos Networks 228

6.2 Path Switching 235

6.2.1 Basic Concept of Path Switching 237

6.2.2 Capacity and Route Assignments for Multirate Traffic 242

6.2.3 Trade-Off Between Performance and Complexity 249

6.2.4 Multicasting in Path Switching 254

6.A Appendix 268

6.A.1 A Formulation of Effective Bandwidth 268

6.A.2 Approximations of Effective Bandwidth Based on On-Off Source Model 269

Problems 270

7 Basic Concepts of Broadband Communication Networks 275

7.1 Synchronous Transfer Mode 275

7.2 Delays in ATM Network 280

7.3 Cell Size Consideration 283

7.4 Cell Networking, Virtual Channels, and Virtual Paths 285

7.4.1 No Data Link Layer 285

7.4.2 Cell Sequence Preservation 286

7.4.3 Virtual-Circuit Hop-by-Hop Routing 286

7.4.4 Virtual Channels and Virtual Paths 287

7.4.5 Routing, Using VCI and VPI 289

7.4.6 Motivations for VP/VC Two-Tier Hierarchy 293

7.5 ATM Layer, Adaptation Layer, and Service Class 295

7.6 Transmission Interface 300

7.7 Approaches Toward IP over ATM 300

7.7.1 Classical IP over ATM 301

7.7.2 Next Hop Resolution Protocol 302

7.7.3 IP Switch and Cell Switch Router 303

7.7.4 ARIS and Tag Switching 306

7.7.5 Multiprotocol Label Switching 308

Appendix 7.A ATM Cell Format 311

7.A.1 ATM Layer 311

7.A.2 Adaptation Layer 314

Problems 319

8 Network Traffic Control and Bandwidth Allocation 323

8.1 Fluid-Flow Model: Deterministic Discussion 326

8.2 Fluid-Flow On-Off Source Model: Stochastic Treatment 332

8.3 Traffic Shaping and Policing 348

8.4 Open-Loop Flow Control and Scheduling 354

8.4.1 First-Come-First-Serve Scheduling 355

8.4.2 Fixed-Capacity Assignment 357

8.4.3 Round-Robin Scheduling 358

8.4.4 Weighted Fair Queueing 364

8.4.5 Delay Bound in Weighted Fair Queueing with Leaky-Bucket Access Control 373

8.5 Closed-Loop Flow Control 380

Problems 381

9 Packet Switching and Information Transmission 385

9.1 Duality of Switching and Transmission 386

9.2 Parallel Characteristics of Contention and Noise 390

9.2.1 Pseudo Signal-to-Noise Ratio of Packet Switch 390

9.2.2 Clos Network with Random Routing as a Noisy Channel 393

9.3 Clos Network with Deflection Routing 396

9.3.1 Cascaded Clos Network 397

9.3.2 Analysis of Deflection Clos Network 397

9.4 Route Assignments and Error-Correcting Codes 402

9.4.1 Complete Matching in Bipartite Graphs 402

9.4.2 Graphical Codes 405

9.4.3 Route Assignments of Benes Network 407

9.5 Clos Network as Noiseless Channel-Path Switching 410

9.5.1 Capacity Allocation 411

9.5.2 Capacity Matrix Decomposition 414

9.6 Scheduling and Source Coding 416

9.6.1 Smoothness of Scheduling 417

9.6.2 Comparison of Scheduling Algorithms 420

9.6.3 Two-Dimensional Scheduling 424

9.7 Conclusion 430

Bibliography 433