Principles of Broadband Switching and Networking

by Liew, Soung C.; Lee, Tony T.

• ISBN13: 9780471139010
• ISBN10: 0471139017
• Edition: 1st
• Format: Hardcover
• Copyright: 2010-03-15
• Publisher: Wiley-Interscience

Summary

This book focuses on the design and analysis of switch architectures suitable for broad-band integrated networks. In particular, the emphasis is on packet-switched interconnection networks with distributed routing algorithms. The text examines the mathematical properties of 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.

Author Biography

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 ATT Bell and Bellcore, Dr. Lee was the recipient of the Leonard G. Abraham Prize 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 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 interuniversity ATM network testbed in Hong Kong in 1993.

Table of Contents

Preface	p. xiii
About the Authors	p. xvii
Introduction and Overview	p. 1
Switching and Transmission	p. 2
Roles of Switching and Transmission	p. 2
Telephone Network Switching and Transmission Hierarchy	p. 4
Multiplexing and Concentration	p. 5
Timescales of Information Transfer	p. 8
Sessions and Circuits	p. 9
Messages	p. 9
Packets and Cells	p. 9
Broadband Integrated Services Network	p. 10
Problems	p. 12
Circuit Switch Design Principles	p. 15
Space-Domain Circuit Switching	p. 16
Nonblocking Properties	p. 16
Complexity of Nonblocking Switches	p. 18
Clos Switching Network	p. 20
Benes Switching Network	p. 28
Baseline and Reverse Baseline Networks	p. 31
Cantor Switching Network	p. 32
Time-Domain and Time-Space-Time Circuit Switching	p. 35
Time-Domain Switching	p. 35
Time-Space-Time Switching	p. 37
Problems	p. 39
Fundamental Principles of Packet Switch Design	p. 43
Packet Contention in Switches	p. 45
Fundamental Properties of Interconnection Networks	p. 48
Definition of Banyan Networks	p. 49
Simple Switches Based on Banyan Networks	p. 51
Combinatoric Properties of Banyan Networks	p. 54
Nonblocking Conditions for the Banyan Network	p. 54
Sorting Networks	p. 59
Basic Concepts of Comparison Networks	p. 61
Sorting Networks Based on Bitonic Sort	p. 64
The Odd-Even Sorting Network	p. 70
Switching and Contention Resolution in Sort-Banyan Network	p. 71
Nonblocking and Self-Routing Properties of Clos Networks	p. 75
Nonblocking Route Assignment	p. 76
Recursiveness Property	p. 79
Basic Properties of Half-Clos Networks	p. 81
Sort-Clos Principle	p. 89
Problems	p. 90
Switch Performance Analysis and Design Improvements	p. 95
Performance of Simple Switch Designs	p. 95
Throughput of an Internally Nonblocking Loss System	p. 96
Throughput of an Input-Buffered Switch	p. 96
Delay of an Input-Buffered Switch	p. 103
Delay of an Output-Buffered Switch	p. 112
Design Improvements for Input Queueing Switches	p. 113
Look-Ahead Contention Resolution	p. 113
Parallel Iterative Matching	p. 115
Design Improvements Based on Output Capacity Expansion	p. 119
Speedup Principle	p. 119x
Channel-Grouping Principle	p. 121
Knockout Principle	p. 131
Replication Principle	p. 137
Dilation Principle	p. 138
Problems	p. 144
Advanced Switch Design Principles	p. 151
Switch Design Principles Based on Deflection Routing	p. 151
Tandem-Banyan Network	p. 151
Shuffle-Exchange Network	p. 154
Feedback Shuffle-Exchange Network	p. 158
Feedback Bidirectional Shuffle-Exchange Network	p. 166
Dual Shuffle-Exchange Network	p. 175
Switching by Memory I/O	p. 184
Design Principles for Scalable Switches	p. 187
Generalized Knockout Principle	p. 187
Modular Architecture	p. 191
Problems	p. 198
Switching Principles for Multicast, Multirate, and Multimedia Services	p. 205
Multicast Switching	p. 205
Multicasting Based on Nonblocking Copy Networks	p. 208
Performance Improvement of Copy Networks	p. 213
Multicasting Algorithm for Arbitrary Network Topologies	p. 220
Nonblocking Copy Networks Based on Broadcast Clos Networks	p. 228
Path Switching	p. 235
Basic Concept of Path Switching	p. 237
Capacity and Route Assignments for Multirate Traffic	p. 242
Trade-Off Between Performance and Complexity	p. 249
Multicasting in Path Switching	p. 254
Appendix	p. 268
A Formulation of Effective Bandwidth	p. 268
Approximations of Effective Bandwidth Based on On-Off Source Model	p. 269
Problems	p. 270
Basic Concepts of Broadband Communication Networks	p. 275
Synchronous Transfer Mode	p. 275
Delays in ATM Network	p. 280
Cell Size Consideration	p. 283
Cell Networking, Virtual Channels, and Virtual Paths	p. 285
No Data Link Layer	p. 285
Cell Sequence Preservation	p. 286
Virtual-Circuit Hop-by-Hop Routing	p. 286
Virtual Channels and Virtual Paths	p. 287
Routing, Using VCI and VPI	p. 289
Motivations for VP/VC Two-Tier Hierarchy	p. 293
ATM Layer, Adaptation Layer, and Service Class	p. 295
Transmission Interface	p. 300
Approaches Toward IP over ATM	p. 300
Classical IP over ATM	p. 301
Next Hop Resolution Protocol	p. 302
IP Switch and Cell Switch Router	p. 303
ARIS and Tag Switching	p. 306
Multiprotocol Label Switching	p. 308
ATM Cell Format	p. 311
ATM Layer	p. 311
Adaptation Layer	p. 314
Problems	p. 319
Network Traffic Control and Bandwidth Allocation	p. 323
Fluid-Flow Model: Deterministic Discussion	p. 326
Fluid-Flow On-Off Source Model: Stochastic Treatment	p. 332
Traffic Shaping and Policing	p. 348
Open-Loop Flow Control and Scheduling	p. 354
First-Come-First-Serve Scheduling	p. 355
Fixed-Capacity Assignment	p. 357
Round-Robin Scheduling	p. 358
Weighted Fair Queueing	p. 364
Delay Bound in Weighted Fair Queueing with Leaky-Bucket Access Control	p. 373
Closed-Loop Flow Control	p. 380
Problems	p. 381
Packet Switching and Information Transmission	p. 385
Duality of Switching and Transmission	p. 386
Parallel Characteristics of Contention and Noise	p. 390
Pseudo Signal-to-Noise Ratio of Packet Switch	p. 390
Clos Network with Random Routing as a Noisy Channel	p. 393
Clos Network with Deflection Routing	p. 396
Cascaded Clos Network	p. 397
Analysis of Deflection Clos Network	p. 397
Route Assignments and Error-Correcting Codes	p. 402
Complete Matching in Bipartite Graphs	p. 402
Graphical Codes	p. 405
Route Assignments of Benes Network	p. 407
Clos Network as Noiseless Channel-Path Switching	p. 410
Capacity Allocation	p. 411
Capacity Matrix Decomposition	p. 414
Scheduling and Source Coding	p. 416
Smoothness of Scheduling	p. 417
Comparison of Scheduling Algorithms	p. 420
Two-Dimensional Scheduling	p. 424
Conclusion	p. 430
Bibliography	p. 433
Table of Contents provided by Ingram. All Rights Reserved.